Pohon Merkle

Sebuah blok dapat berisi ribuan transaksi. Bagaimana perangkat ringan dapat memverifikasi bahwa satu transaksi tertentu tercakup tanpa mengunduh semuanya?

Jawabannya adalah Merkle tree — struktur yang memungkinkan Anda membuktikan keanggotaan hanya dengan beberapa hash.

Pohon Merkle (atau pohon hash) adalah pohon biner dengan ketentuan berikut:

• Setiap daun adalah hash dari satu transaksi
• Setiap simpul internal adalah hash gabungan dari kedua anaknya
• Satu-satunya simpul teratas adalah akar Merkle

Pembangunannya dilakukan dari bawah ke atas. Hash setiap transaksi untuk membentuk daun, lalu hash pasangan-pasangan tersebut berulang kali hingga hanya tersisa satu hash.

Akar Merkle adalah satu hash yang mewakili setiap transaksi dalam blok. Hash ini disimpan di header blok.

Jika satu transaksi saja berubah, akarnya ikut berubah—sehingga akar tersebut menjadi sidik jari ringkas dari seluruh kumpulan transaksi.

Jika suatu tingkat memiliki jumlah simpul ganjil, simpul terakhir biasanya digandakan agar dapat dipasangkan.

Hal ini menjaga keseimbangan pohon dan memastikan setiap simpul memiliki saudara untuk di-hash bersamanya.

Bukti Merkle adalah kumpulan kecil hash saudara yang diperlukan untuk menghitung ulang akar dari satu daun.

Untuk membuktikan bahwa tx2 disertakan, Anda hanya memerlukan simpul-simpul saudara di sepanjang jalurnya—bukan transaksi lainnya.

Untuk N transaksi, bukti Merkle hanya memerlukan sekitar log2(N) hash.

Untuk satu juta transaksi, jumlahnya kira-kira 20 hash, bukan satu juta—penghematan besar bagi klien ringan dan dompet seluler.

Klien Verifikasi Pembayaran Sederhana hanya mengunduh header blok, bukan blok lengkap.

Dengan menggunakan bukti Merkle dari simpul penuh, klien SPV dapat memastikan bahwa suatu transaksi berada dalam blok tanpa memercayai simpul tersebut secara membabi buta.

Karena setiap transaksi berkontribusi pada akar Merkle, perubahan pada transaksi apa pun akan menghasilkan akar yang berbeda.

Akar pada header tidak lagi cocok dengan akar yang dihitung ulang, sehingga perubahan tersebut segera terungkap.

Pohon Merkle digunakan jauh melampaui daftar transaksi. Ethereum menggunakan varian yang disebut Trie Patricia Merkle untuk mengikat seluruh keadaan dunia dan tanda terima.

Git, IPFS, dan banyak basis data juga mengandalkan struktur Merkle untuk menjaga integritas.

Pohon Merkle mengubah kumpulan besar transaksi menjadi satu hash akar, sekaligus tetap memungkinkan bukti keanggotaan yang ringkas dan dapat diverifikasi.

Pohon ini adalah salah satu struktur data paling elegan di balik verifikasi yang dapat diskalakan dan tanpa kepercayaan.

Anda telah mempelajari bahwa:

• Pohon Merkle melakukan hash pada transaksi secara berpasangan hingga menjadi satu akar
• Akar Merkle adalah sidik jari yang disimpan di header
• Bukti Merkle hanya memerlukan sekitar ~log2(N) hash
• Hal ini memungkinkan klien ringan yang efisien dan deteksi perubahan

Selanjutnya kita akan membahas hashing yang menjadi dasar semua ini.