Temu duga umum: Pengesahan bukti rangkuman Merkle

Gesaan dan skop

Ini ialah masalah pelaksanaan struktur data kriptografi dan protokol. Bukti rangkuman Merkle hanya menghantar nod adik-beradik yang diperlukan untuk menyambungkan daun sasaran ke punca, bukannya keseluruhan pokok. RFC 9162 mengasingkan domain hash daun dan nod dalaman serta memerlukan pengesah menggunakan leaf_index dan tree_size semasa menentukan kiri dan kanan pada setiap tahap. Andaikan klien memperoleh root_hash melalui saluran yang dipercayai; pengesah tidak mewujudkan kepercayaan tersebut.

Perkara yang diuji oleh penemu duga

Membezakan hash daun, hash dalaman dan maklumat arah laluan.
Menggunakan leaf_index dan tree_size untuk pengesahan batas dan laluan.
Memahami pengasingan domain supaya bait daun tidak dikelirukan dengan input nod dalaman.
Menerangkan saiz bukti O(log n) dan masa pengesahan, serta sempadan punca yang dipercayai.

Penjelasan untuk ditanya terlebih dahulu

Sahkan spesifikasi pokok: pokok bersaiz pemboleh ubah RFC 9162 atau pokok binari penuh yang tetap; pengkanonikan daun; algoritma hash dan pemalar awalan; serta sama ada laluan disusun dari daun ke punca. Jelaskan juga sama ada bukti ketekalan tambah sahaja (append-only) atau tandatangan diperlukan, atau hanya satu bukti rangkuman. Tanpa konvensyen ini, senarai hash tidak mentakrifkan punca secara unik.

Jawapan 30 saat

Semak 0 <= leaf_index < tree_size dan hadkan panjang laluan. Kanonikal daun sebagai HASH(0x00 || leaf_bytes), kemudian simpan fn = leaf_index, sn = tree_size - 1 dan hash semasa r. Pada setiap tahap, gunakan bit rendah fn atau syarat fn == sn untuk memutuskan sama ada adik-beradik berada di kiri atau kanan, hash dengan awalan dalaman 0x01 dan anjakkan kedua-dua indeks. Berjaya hanya apabila sn == 0 dan r == root_hash.

Penyelesaian langkah demi langkah

1. Tetapkan kontrak input dan pengasingan domain

Pengesah memerlukan algoritma hash berversi, pengekodan daun, susunan laluan dan semantik saiz pokok. Merkle Tree Hash RFC 9162 menggunakan 0x00 untuk daun dan 0x01 untuk nod dalaman, menghalang rentetan bait yang sama daripada ditafsirkan dalam dua peranan. Jangan hash leaf || sibling tanpa pengasingan domain atau membenarkan pemanggil menggantikan awalan secara sewenang-wenangnya.

2. Lakukan semakan batas dan sumber terlebih dahulu

leaf_index >= tree_size mesti gagal; pokok kosong tidak mempunyai daun yang sah. Hadkan laluan, contohnya pada ceil(log2(tree_size)) + 1, dan tetapkan keperluan panjang bait tetap bagi setiap hash. Tolak limpahan integer, pengekodan negatif, penghuraian pendua dan laluan bersaiz berlebihan supaya bukti yang berniat jahat tidak dapat menggunakan sumber tanpa batas. Laluan yang pendek tidak sah secara automatik; keadaan akhir mesti menumpu kepada satu punca.

3. Bina semula punca tahap demi tahap

Untuk pokok bersaiz pemboleh ubah RFC 9162, pariti sahaja tidak mencukupi: syarat sempadan fn == sn mengubah arah penggabungan. Anjakkan kedua-dua fn dan sn selepas setiap tahap untuk memetakan nod semasa kepada induknya. Pseudokod:

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. Semak persetujuan laluan dan saiz pokok

tree_size bukti terlibat dalam pengiraan arah; ia bukan metadata log hiasan. Apabila laluan habis digunakan, sn mestilah sifar. Jika ia kekal positif, bukti tidak mencapai punca; jika sn sudah sifar dan masih ada adik-beradik yang tinggal, tolak bukti tersebut. Pelaksanaan pokok tetap mungkin menggunakan peraturan berbeza, tetapi penjana dan pengesahnya mesti berkongsi konvensyen pokok tersebut dan bukannya mencampurkannya dengan laluan RFC 9162.

5. Kerumitan, komunikasi dan kepercayaan

Pokok yang seimbang biasanya mempunyai O(log n) hash adik-beradik. Pengesahan mengambil masa O(log n) operasi hash dan O(1) keadaan di luar laluan; komunikasi ialah O(log n * hashSize). Bukti hanya mengikat daun pada punca yang dibekalkan. Jika punca datang daripada respons yang tidak dipercayai, penyerang boleh menggantikan kedua-dua punca dan bukti. Protokol pengeluaran melindungi punca dan saiz pokok dengan tandatangan, kepala log yang dipercayai atau pengangkutan yang disahkan.

Jawapan model

Saya akan mengikat pengesah pada spesifikasi pokok berversi. Pertama, semak tree_size > 0, 0 <= leaf_index < tree_size, panjang hash dan bajet laluan, kemudian kira r = HASH(0x00 || leaf). Simpan fn = leaf_index dan sn = tree_size - 1; pada setiap tahap letakkan adik-beradik di sebelah kiri apabila fn ganjil atau fn == sn, jika tidak di sebelah kanan, dan kemas kini dengan HASH(0x01 || left || right). Anjakkan kedua-dua indeks. Pada akhirnya, hanya sn == 0 dan kesamarataan dengan punca yang dipercayai akan berjaya. Saiz bukti dan kos pengesahan ialah O(log n), manakala protokol mesti mengesahkan punca, saiz pokok dan susunan laluan.

Kesilapan biasa

Memilih arah hanya daripada pariti indeks dan mengabaikan sempadan pokok pemboleh ubah fn == sn.
Menggunakan satu awalan hash untuk daun dan nod dalaman, kehilangan pengasingan domain.
Hanya membandingkan punca yang dibina semula tanpa menyemak batas daun, panjang laluan atau penumpuan sn.
Menganggap punca daripada respons yang tidak dipercayai sebagai sauh pengesahan.
Membina dengan satu konvensyen pokok dan mengesahkan dengan peraturan pokok binari penuh yang berbeza.
Meniadakan susunan laluan, susunan bait hash atau pengkanonikan daun daripada kontrak berversi.

Soalan susulan

Bagaimanakah anda mengesahkan bukti ketekalan tambah sahaja (append-only)?

Bukti rangkuman menjawab sama ada satu daun tergolong dalam satu punca. Bukti ketekalan membina semula kedua-dua punca lama dan baharu serta membuktikan bahawa pokok lama ialah awalan bagi pokok baharu. Input merangkumi saiz lama dan baharu, laluan serta kedua-dua punca yang dipercayai. Peralihan keadaannya berbeza, jadi ia tidak boleh disembunyikan di dalam fungsi rangkuman Boolean sahaja.

Mengapakah tree_size dihantar dan bukannya laluan sahaja?

Dalam pokok bersaiz pemboleh ubah, nod terakhir mungkin tidak mempunyai adik-beradik kanan pada tahapnya. Arah bergantung pada sempadan subpokok semasa. tree_size memberitahu pengesah nod mana yang wujud dan menghalang hash tambahan daripada diseludup ke dalam laluan punca palsu.

Bagaimanakah anda menghalang penurunan gred algoritma hash?

Versikan pengecam algoritma, panjang output, awalan daun/dalaman dan pengkanonikan. Terima senarai dibenarkan sahaja dan tolak algoritma yang tidak diketahui atau lemah. Penghijrahan mencipta ruang nama punca baharu; ringkasan daripada algoritma berbeza tidak boleh berkongsi satu pokok.

Bagaimanakah daun pendua mempengaruhi bukti?

Bukti rangkuman mengikat bait pada satu kedudukan; ia tidak membuktikan bahawa nilai itu hanya muncul sekali. Keunikan memerlukan indeks kunci berasingan atau bukti set. Satu punca Merkle tidak boleh membuktikan ketiadaan nilai lain yang sama.

Bagaimanakah penjana boleh bersifat bertambah (incremental) tanpa menyimpan keseluruhan pokok?

Simpan ringkasan subpokok sebelah kanan yang paling baharu pada setiap tahap sebagai pengumpul awalan dan gabungkan daun baharu seperti perambatan bawaan binari. Membuktikan daun lama masih memerlukan pengekalan adik-beradik yang diperlukan atau stor luaran; punca sahaja tidak boleh mencipta semula laluan.

Bagaimanakah pengesah harus mengendalikan laluan bersaiz berlebihan?

Kira batas daripada saiz pokok dan panjang hash sebelum menghurai, tolak laluan yang lebih panjang dan semak panjang tetap setiap elemen untuk mengelakkan limpahan pendaraban. Selesaikan bajet sumber sebelum melakukan hashing supaya bukti yang tidak terbentuk dengan betul tidak boleh mencetuskan gelung tak terhingga atau peruntukan memori yang besar.