Wawancara umum: Memverifikasi bukti inklusi Merkle

Petunjuk dan cakupan

Ini adalah masalah implementasi protokol dan struktur data kriptografi. Bukti inklusi Merkle hanya mengirimkan simpul sibling yang diperlukan untuk menghubungkan leaf target ke sebuah root, bukan keseluruhan pohon. RFC 9162 memisahkan domain hash leaf dan simpul interior serta mewajibkan verifier menggunakan leaf_index dan tree_size saat menentukan kiri dan kanan pada setiap tingkat. Asumsikan klien memperoleh root_hash melalui saluran tepercaya; verifier tidak bertugas membangun kepercayaan tersebut.

Hal yang diuji oleh pewawancara

Membedakan hash leaf, hash interior, dan informasi arah jalur.
Menggunakan leaf_index dan tree_size untuk validasi batas dan jalur.
Memahami pemisahan domain agar byte leaf tidak tertukar dengan input simpul interior.
Menjelaskan ukuran bukti O(log n) dan waktu verifikasi, ditambah batasan root tepercaya.

Klarifikasi yang perlu ditanyakan terlebih dahulu

Konfirmasikan spesifikasi pohon: pohon berukuran variabel RFC 9162 atau pohon biner penuh tetap; kanonikalisasi leaf; algoritma hash dan konstanta prefiks; serta apakah jalur diurutkan dari leaf ke root. Klarifikasi juga apakah bukti konsistensi append-only atau tanda tangan diperlukan, atau hanya satu bukti inklusi. Tanpa konvensi ini, daftar hash tidak secara unik mendefinisikan sebuah root.

Jawaban 30 detik

Periksa 0 <= leaf_index < tree_size dan batasi panjang jalur. Kanonikalisasi leaf sebagai HASH(0x00 || leaf_bytes), lalu simpan fn = leaf_index, sn = tree_size - 1, dan hash saat ini r. Pada setiap tingkat, gunakan bit rendah dari fn atau kondisi fn == sn untuk menentukan apakah sibling berada di kiri atau kanan, lakukan hash dengan prefiks interior 0x01, dan geser kedua indeks. Berhasil hanya jika sn == 0 dan r == root_hash.

Solusi langkah demi langkah

1. Menetapkan kontrak input dan pemisahan domain

Verifier memerlukan algoritma hash berversi, pengodean leaf, urutan jalur, dan semantik ukuran pohon. Merkle Tree Hash RFC 9162 menggunakan 0x00 untuk leaf dan 0x01 untuk simpul interior, mencegah string byte yang sama diinterpretasikan dalam dua peran. Jangan melakukan hash pada leaf || sibling tanpa pemisahan domain atau membiarkan pemanggil mengganti prefiks secara sembarangan.

2. Melakukan pemeriksaan batas dan sumber daya terlebih dahulu

leaf_index >= tree_size harus gagal; pohon kosong tidak memiliki leaf yang valid. Batasi jalur, misalnya pada ceil(log2(tree_size)) + 1, dan wajibkan panjang byte tetap untuk setiap hash. Tolak luapan bilangan bulat, pengodean negatif, penguraian duplikat, dan jalur yang terlalu besar sehingga bukti berbahaya tidak dapat menghabiskan sumber daya tanpa batas. Jalur yang pendek tidak otomatis valid; status akhir harus konvergen ke satu root.

3. Membangun kembali root tingkat demi tingkat

Untuk pohon berukuran variabel RFC 9162, paritas saja tidak cukup: kondisi batas fn == sn mengubah arah penggabungan. Geser fn dan sn setelah setiap tingkat untuk memetakan simpul saat ini ke induknya. Pseudocode:

text

verify(leaf, leafIndex, treeSize, path, expectedRoot):
  if treeSize <= 0 or leafIndex < 0 or leafIndex >= treeSize: return false
  r = HASH(0x00 || leaf)
  fn = leafIndex
  sn = treeSize - 1
  for sibling in path:
    if sn == 0: return false
    if (fn & 1) == 1 or fn == sn:
      r = HASH(0x01 || sibling || r)
    else:
      r = HASH(0x01 || r || sibling)
    fn = fn >> 1
    sn = sn >> 1
  return sn == 0 and r == expectedRoot

4. Memeriksa kesesuaian jalur dan ukuran pohon

tree_size pada bukti berpartisipasi dalam penghitungan arah; ini bukan metadata log dekoratif. Saat jalur habis digunakan, sn harus bernilai nol. Jika tetap positif, bukti tidak mencapai root; jika sn sudah nol dan masih ada sibling yang tersisa, tolak bukti tersebut. Implementasi pohon tetap mungkin menggunakan aturan berbeda, tetapi generator dan verifier-nya harus berbagi konvensi pohon tersebut alih-alih mencampurnya dengan jalur RFC 9162.

5. Kompleksitas, komunikasi, dan kepercayaan

Pohon yang seimbang biasanya memiliki O(log n) hash sibling. Verifikasi membutuhkan O(log n) operasi hash dan status O(1) di luar jalur; komunikasinya adalah O(log n * hashSize). Bukti hanya mengikat leaf ke root yang diberikan. Jika root berasal dari respons yang tidak tepercaya, penyerang dapat mengganti root dan bukti sekaligus. Protokol produksi melindungi root dan ukuran pohon dengan tanda tangan, log head tepercaya, atau transportasi yang terotentikasi.

Contoh jawaban

Saya akan mengikat verifier ke spesifikasi pohon berversi. Pertama, periksa tree_size > 0, 0 <= leaf_index < tree_size, panjang hash, dan batas anggaran jalur, lalu hitung r = HASH(0x00 || leaf). Simpan fn = leaf_index dan sn = tree_size - 1; pada setiap tingkat letakkan sibling di sebelah kiri saat fn ganjil atau fn == sn, jika tidak di sebelah kanan, dan perbarui dengan HASH(0x01 || left || right). Geser kedua indeks. Pada akhirnya, hanya sn == 0 dan kesetaraan dengan root tepercaya yang berhasil. Ukuran bukti dan biaya verifikasi adalah O(log n), sedangkan protokol harus mengautentikasi root, ukuran pohon, dan urutan jalur.

Kesalahan umum

Memilih arah hanya dari paritas indeks dan mengabaikan batas pohon variabel fn == sn.
Menggunakan satu prefiks hash untuk leaf dan simpul interior, sehingga kehilangan pemisahan domain.
Hanya membandingkan root yang dibangun kembali tanpa memeriksa batas leaf, panjang jalur, atau konvergensi sn.
Memperlakukan root dari respons yang tidak tepercaya sebagai jangkar autentikasi.
Membangun dengan satu konvensi pohon dan memverifikasi dengan aturan pohon biner penuh yang berbeda.
Menghilangkan urutan jalur, urutan byte hash, atau kanonikalisasi leaf dari kontrak berversi.

Pertanyaan lanjutan

Bagaimana Anda memverifikasi bukti konsistensi append-only?

Bukti inklusi menjawab apakah satu leaf termasuk dalam satu root. Bukti konsistensi merekonstruksi root lama dan baru serta membuktikan bahwa pohon lama merupakan prefiks dari pohon baru. Input mencakup ukuran lama dan baru, sebuah jalur, dan kedua root tepercaya. Transisi statusnya berbeda, sehingga tidak boleh disembunyikan di dalam fungsi inklusi yang hanya mengembalikan Boolean.

Mengapa mengirimkan tree_size alih-alih hanya jalurnya?

Dalam pohon berukuran variabel, simpul terakhir mungkin tidak memiliki sibling kanan pada tingkatnya. Arah bergantung pada batas subtree saat ini. tree_size memberi tahu verifier simpul mana saja yang ada dan mencegah hash ekstra diselundupkan ke dalam jalur root palsu.

Bagaimana Anda mencegah penurunan versi (downgrade) algoritma hash?

Buat versi pengenal algoritma, panjang output, prefiks leaf/interior, dan kanonikalisasi. Hanya terima allowlist dan tolak algoritma yang tidak dikenal atau lemah. Migrasi membuat namespace root baru; digest dari algoritma berbeda tidak boleh berbagi satu pohon.

Bagaimana leaf duplikat memengaruhi bukti?

Bukti inklusi mengikat byte ke suatu posisi; bukti ini tidak membuktikan bahwa nilai tersebut hanya muncul sekali. Keunikan memerlukan indeks kunci terpisah atau bukti set. Satu Merkle root tidak dapat membuktikan ketiadaan nilai lain yang sama.

Bagaimana generator dapat bersifat inkremental tanpa menyimpan seluruh pohon?

Simpan digest subtree sisi kanan terbaru pada setiap tingkat sebagai akumulator prefiks dan gabungkan leaf baru seperti perambatan carry biner. Membuktikan leaf lama masih memerlukan penyimpanan sibling yang diperlukan atau penyimpanan eksternal; root saja tidak dapat membuat ulang sebuah jalur.

Bagaimana verifier harus menangani jalur yang terlalu besar?

Hitung batas dari ukuran pohon dan panjang hash sebelum mengurai, tolak jalur yang lebih panjang, dan periksa panjang tetap setiap elemen untuk menghindari luapan perkalian. Selesaikan pemeriksaan anggaran sumber daya sebelum melakukan hashing sehingga bukti yang salah bentuk tidak dapat memicu loop tak terbatas atau alokasi memori yang besar.