Pohon Merkle: Integritas Transaksi dalam Skala Besar

Blok Bitcoin memuat ~2000 transaksi. Untuk membuktikan transaksi T disertakan tanpa mengunduh seluruh 2000 transaksi, kita memerlukan bukti ringkas. Pohon Merkle mengatasi ini: ukuran bukti = hash O(log n), bukan transaksi O(n).

Daun: SHA256d (SHA-256 ganda) dari setiap transaksi. Induk: SHA256d(left_child_hash || right_child_hash). Ulangi hingga tersisa satu hash akar. Jika jumlah simpul ganjil, gandakan simpul terakhir. Akar tersebut adalah akar Merkle yang disimpan di kepala blok (32 byte).

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

Untuk membuktikan transaksi T berada di posisi i: berikan hash saudara pada setiap tingkat, dari daun T ke akar (hash O(log n)). Verifikator menghitung ulang akar dari T dan jalur saudara. Jika akar hasil perhitungan cocok dengan akar Merkle pada kepala blok, T terbukti disertakan.

1024 transaksi → bukti Merkle = 10 hash = 320 byte. Blok penuh = ~1 MB. Klien SPV hanya mengunduh kepala 80 byte + bukti Merkle 320 byte untuk setiap transaksi yang diperlukan — penghematan bandwidth 99.97% dibandingkan mengunduh blok penuh.

Jika transaksi mana pun dalam pohon berubah, hash daunnya berubah, lalu perubahan itu merambat ke atas dan mengubah akar Merkle. Akar yang berubah tidak lagi cocok dengan kepala blok (yang disegel oleh PoW). Setiap perubahan dapat dideteksi dengan menghitung akar dari transaksi.

Ethereum memperluas pohon Merkle dengan trie (Trie Merkle Patricia): trie radix berkode awalan heksadesimal yang setiap simpulnya di-hash dengan Merkle. Digunakan untuk: trie status (saldo akun), trie transaksi, trie tanda terima. Memungkinkan pembuktian status akun secara efisien tanpa data simpul penuh.

Rentang Pegunungan Merkle (MMR) adalah struktur Merkle yang hanya dapat ditambahi untuk data seperti catatan. Elemen baru ditambahkan; puncak (akar subtree berukuran pangkat 2) dipertahankan. Digunakan di Grin/MimbleWimble dan ZCash untuk bukti ringkas yang efisien atas catatan yang hanya dapat ditambahi.

Pohon Verkle menggantikan pohon Merkle dalam peta jalan Ethereum (EIP-6800): gunakan komitmen vektor (komitmen polinomial KZG), bukan hash. Ukuran bukti: O(1) dibandingkan O(log n) untuk Merkle. Memungkinkan klien tanpa status memverifikasi status tanpa menyimpan trie lengkap.

Transparansi Sertifikat (RFC 6962) menggunakan catatan Merkle yang hanya dapat ditambahi: setiap sertifikat yang diterbitkan CA adalah daun. Bukti inklusi memverifikasi bahwa sertifikat telah dicatat. Bukti konsistensi memverifikasi bahwa catatan hanya ditambahi (tanpa penghapusan atau penyisipan). Vendor peramban memverifikasi SCT melalui catatan ini.

Pohon Git (cuplikan direktori) adalah pohon Merkle: setiap simpul pohon menghitung hash objek data berkas dan subtree-nya. Hash komit secara unik mengidentifikasi keadaan seluruh basis kode. Inilah sebabnya git checkout selalu menghasilkan berkas yang persis sama.

Berapa banyak hash yang diperlukan oleh bukti Merkle untuk membuktikan inklusi dalam pohon dengan 1024 daun?

Pohon Merkle memungkinkan bukti inklusi O(log n). Bitcoin menyimpan akar Merkle di kepala blok; klien SPV menggunakan bukti. Ethereum memperluasnya menjadi Trie Merkle Patricia. Pohon Verkle akan menggantikan pohon Merkle untuk bukti O(1). Berikutnya: penambangan Bukti Kerja dan kesulitan.