Konsep pohon Merkle atau Merkle tree diusulkan pada awal tahun 80-an oleh Ralph Merkle – seorang ilmuwan komputer yang dikenal karena karyanya pada
kriptografi public-key.
Merkle tree merupakan struktur yang digunakan untuk memverifikasi integritas data secara efisien dalam satu set. Sangat menarik dalam konteks jaringan
peer-to-peer, di mana para peserta perlu berbagi dan memvalidasi informasi secara independen.
Fungsi hash adalah inti dari struktur Merkle tree, jadi, sebaiknya Anda melihat
Apa itu Hashing? sebelum melanjutkan pembahasan ini.
Bayangkan Anda ingin mengunduh file besar. Dengan
perangkat lunak open-source, umumnya, Anda akan memeriksa apakah hash file yang Anda unduh cocok dengan yang dipublikasikan oleh pengembangnya. Jika ya, Anda tahu bahwa file yang Anda miliki di komputer Anda persis sama dengan file mereka.
Jika hash tidak cocok, berarti ada masalah. Bisa jadi Anda telah mengunduh file berbahaya yang menyamar sebagai perangkat lunak, atau Anda tidak mengunduh dengan benar, karenanya, file tidak berfungsi. Jika masalahnya adalah yang terakhir, Anda mungkin akan sedikit kecewa karena telah membuang-buang waktu dengan percuma. Sekarang, Anda harus memulai kembali prosesnya dan berharap kali ini tidak terdapat kerusakan.
Anda pun berpikir, kalau saja ada cara yang lebih mudah untuk melakukan hal ini. Kabar baiknya, Merkle tree muncul. Dengan Merkle tree, file Anda akan dipecah menjadi beberapa bagian. Jika file berukuran 50GB, misalnya, Anda dapat membaginya menjadi seratus bagian, sehingga masing-masing berukuran 0,5GB. Kemudian, akan diunduh sepotong demi sepotong. Pada dasarnya, inilah yang Anda lakukan ketika melakukan torrent terhadap file.
Dalam hal ini, sumber akan memberi hash kepada Anda, yang dikenal sebagai akar Merkle atau Merkle root. Hash tunggal ini merupakan representasi setiap potongan data yang membentuk file. Merkle root membuat proses verifikasi data jauh lebih mudah.
Agar lebih gampang dimengerti, mari kita ambil contoh di mana kita menggunakan file 8GB yang dipecah menjadi delapan bagian. Fragmen-fragmen yang berbeda ini sebut saja A sampai H. Setiap fragmen kemudian melewati fungsi hash, memberikan delapan hash yang berbeda.
Kita melewatkan masing-masing dari delapan fragmen melalui fungsi hash untuk mendapatkan hash masing-masing.
Nah, jadi sekarang mungkin lebih masuk akal. Kita memiliki hash dari semua fragmen, jadi jika ada yang salah, kita akan mengetahuinya dengan membandingkan ke sumber, benar? Bisa saja, tetapi ternyata cara ini juga sangat tidak efisien. Jika file Anda memiliki ribuan fragmen, apakah Anda benar-benar akan melakukan proses hashing terhadap semuanya dan membandingkan hasilnya satu per satu?
Tidak. Sebaliknya, kita akan mengambil setiap pasangan hash, menggabungkannya, lalu melakukan proses hashing. Jadi, proses hashing akan dilakukan terhadap hash hA + hB, hC + hD, hE + hF, dan hG + hH. Akhirnya akan ada empat hash. Lalu kita melakukan hashing lagi sehingga akhirnya tinggal dua. Selanjutnya, proses hashing dilakukan lagi terhadap keduanya, sehingga yang tersisa adalah hash master – Merkle root (atau root hash).
Strukturnya terlihat seperti pohon terbalik. Di baris paling bawah, kita memiliki daun-daun, yang digabungkan untuk menghasilkan simpul atau node, dan akhirnya, akar.
Kita sekarang memiliki Merkle root yang mewakili file yang diunduh. Kita dapat membandingkan root hash ini dengan yang disediakan oleh sumber. Jika cocok, sempurna! Tetapi jika hash berbeda, kita bisa yakin bahwa data telah dimodifikasi. Dengan kata lain, satu atau lebih fragmen telah menghasilkan hash yang berbeda. Jadi sedikit modifikasi data akan menghasilkan Merkle root yang sama sekali berbeda.
Untungnya, ada cara praktis bagi kita untuk memeriksa fragmen mana yang salah. Dalam kasus ini, katakan saja yang salah adalah hE. Anda akan mulai dengan meminta dua hash yang menghasilkan Merkle root (hABCD dan hEFGH) ke peer. Nilai hABCD Anda harus sesuai dengan nilai yang mereka miliki karena tidak ada kesalahan di subtree. Tapi hEFGH tidak akan cocok, jadi Anda tahu bagaimana harus memeriksanya. Anda kemudian meminta hEF dan hGH, dan membandingkannya dengan milik Anda. hGH akan terlihat baik-baik saja, jadi Anda tahu bahwa hEF adalah biang masalahnya. Terakhir, Anda membandingkan hash hE dan hF. Anda sekarang tahu bahwa hE salah, sehingga Anda dapat mengunduh ulang potongan tersebut.
Ringkasnya, Merkle tree dibuat dengan membagi data menjadi banyak bagian, yang kemudian dilakukan proses hashing berulang kali untuk membentuk Merkle root. Anda kemudian dapat memverifikasi secara efisien jika ada yang tidak beres dengan sepotong data. Seperti yang akan kita lihat segera, akan ada aplikasi menarik lainnya juga.
Anda ingin memiliki mata uang kripto? Beli Bitcoin di Binance!
Ada beberapa penggunaan Merkle tree, tetapi kita akan fokus pada pentingnya struktur ini dalam
blockchain. Merkle tree sangat penting dalam
Bitcoin dan banyak mata uang kripto lainnya. Merupakan komponen integral dari setiap
blok, dapat ditemukan di
header blok. Demi mendapatkan daun untuk pohon kita, kita menggunakan hash transaksi (
TXID) dari setiap transaksi yang dimasukkan ke dalam blok.
Dalam hal ini, Merkle root memiliki beberapa tujuan. Mari kita lihat penerapannya dalam penambangan mata uang kripto dan verifikasi transaksi.
Penambangan
Blok Bitcoin terdiri dari dua bagian. Bagian pertama adalah header blok, segmen berukuran tetap berisi
metadata blok. Bagian kedua adalah daftar transaksi yang ukurannya bervariasi, tetapi cenderung jauh lebih besar dari header.
Penambang perlu berulang kali melakukan hashing data untuk menghasilkan output yang cocok dengan persyaratan tertentu dalam menambang blok yang valid. Mereka dapat melakukan triliunan upaya sebelum menemukannya. Dalam setiap upaya, mereka mengubah angka acak di header blok (yaitu
nonce) untuk menghasilkan output yang berbeda. Tetapi banyak blok yang masih tetap sama. Mungkin sudah ada ribuan transaksi, tetapi penambang masih harus melakukan hashing.
Merkle root menyederhanakan proses ini secara signifikan. Sebelum menambang, Anda mengatur semua transaksi yang ingin Anda masukkan dan membangun struktur Merkle tree. Anda menempatkan root hash yang dihasilkan (32 byte) di header blok. Lalu, saat Anda menambang, Anda tidak perlu melakukan hashing terhadap semua blok, tetapi cukup terhadap header blok.
Proses ini akan berhasil karena memiliki sifat tamper-proof. Anda secara efektif mempersingkat semua transaksi blok dalam format yang ringkas. Anda tidak dapat menemukan header blok yang valid dan kemudian mengubah daftar transaksi, karena itu akan mengubah Merkle root. Ketika blok dikirim ke node lain, root dihitung dari daftar transaksi. Jika tidak cocok dengan yang ada di header, blok akan ditolak.
Verifikasi
Terdapat sifat Merkle tree yang menarik lainnya yang dapat kita manfaatkan. Yang ini menyangkut klien ringan (node yang tidak memiliki salinan lengkap blockchain). Jika menjalankan node pada perangkat dengan sumber daya terbatas, Anda tidak akan mengunduh dan melakukan hashing terhadap semua transaksi blok. Sebaliknya, yang dapat Anda lakukan adalah hanya meminta Merkle proof – bukti yang diberikan oleh full node yang menunjukkan bahwa transaksi Anda berada di blok tertentu. Ini lebih sering disebut sebagai Verifikasi Pembayaran Sederhana atau Simplified Payment Verification (SPV), dijelaskan secara terperinci oleh
Satoshi Nakamoto dalam whitepaper Bitcoin.
Untuk memeriksa hD, kita hanya membutuhkan hash yang diwarnai merah.
Bayangkan skenario di mana kita ingin mengetahui informasi mengenai transaksi yang TXID-nya hD. Jika hC diberikan, kita dapat memeriksa hCD. Kemudian, kita memerlukan hAB untuk menghitung hABCD. Terakhir, dengan hEFGH, kita dapat memeriksa apakah Merkle root yang dihasilkan cocok dengan yang ada di header blok. Jika ya, itu membuktikan bahwa transaksi telah dimasukkan ke dalam blok – hampir mustahil untuk membuat hash yang sama dengan data yang berbeda.
Dalam contoh di atas, kita hanya perlu melakukan hashing sebanyak tiga kali. Tanpa Merkle proof, kita harus melakukannya tujuh kali. Karena blok-blok saat ini mengandung ribuan transaksi, menggunakan Merkle proof menghemat banyak waktu dan sumber daya komputasi.
Merkle tree telah membuktikan diri sangat berguna dalam berbagai aplikasi ilmu komputer – seperti yang telah kita lihat, struktur ini sangat bernilai di dalam blockchain. Dalam sistem terdistribusi, Merkle tree mempermudah verifikasi informasi tanpa membanjiri jaringan dengan data yang tidak perlu.
Tanpa Merkle tree (dan Merkle root), blok-blok
Bitcoin dan
mata uang kripto lainnya tidak akan sesederhana dan seringkas sekarang. Dan sementara klien ringan memiliki kelemahan dalam hal privasi dan keamanan, Merkle proof memungkinkan pengguna untuk memeriksa apakah transaksi mereka telah dimasukkan ke dalam blok dengan biaya pengeluaran yang minimal.
