Apa itu pohon Merkle?

Konsep pohon Merkle diusulkan pada awal tahun 80an oleh Ralph Merkle – seorang ilmuwan komputer yang terkenal karena karyanya mengenai kriptografi kunci publik.

Pohon Merkle adalah struktur yang digunakan untuk memverifikasi integritas data dalam suatu kumpulan secara efisien. Hal ini sangat menarik dalam konteks jaringan peer-to-peer, di mana peserta perlu berbagi dan memvalidasi informasi secara independen.

Fungsi hash adalah inti dari struktur pohon Merkle, jadi kami sarankan Anda membaca Apa itu Hashing? sebelum melanjutkan.


Bagaimana cara kerja pohon Merkle?

Misalkan Anda ingin mendownload file berukuran besar. Dengan perangkat lunak sumber terbuka, Anda biasanya ingin memeriksa apakah hash file yang Anda unduh cocok dengan hash yang dipublikasikan oleh pengembang. Jika ya, Anda tahu bahwa file yang Anda miliki di komputer Anda sama persis dengan file mereka.

Jika hashnya tidak cocok, Anda mempunyai masalah. Anda mungkin mengunduh file berbahaya yang menyamar sebagai perangkat lunak, atau file tersebut tidak diunduh dengan benar sehingga tidak berfungsi. Jika yang terakhir adalah kasusnya, Anda mungkin tidak akan terlalu senang jika harus menunggu beberapa saat hingga file diunduh. Sekarang, Anda perlu memulai ulang prosesnya dan berharap prosesnya tidak rusak lagi.

Andai saja ada cara yang lebih mudah untuk melakukan hal ini, menurut Anda. Untungnya, di situlah peran pohon Merkle. Dengan salah satu dari ini, file Anda akan dipecah menjadi beberapa bagian. Jika file tersebut berukuran 50 GB, Anda dapat membaginya menjadi seratus bagian, sehingga masing-masing berukuran 0,5 GB. Kemudian, itu akan diunduh sepotong demi sepotong. Ini pada dasarnya adalah apa yang Anda lakukan saat melakukan torrent file.

Dalam hal ini, sumber Anda akan memberi Anda hash yang dikenal sebagai akar Merkle. Hash tunggal ini adalah representasi dari setiap potongan data yang membentuk file Anda. Namun akar Merkle mempermudah verifikasi data.

Untuk mempermudahnya, mari kita ambil contoh di mana kita menggunakan file berukuran 8 GB yang dipecah menjadi delapan bagian. Panggil berbagai fragmen A hingga H. Setiap fragmen kemudian dilewatkan melalui fungsi hash, sehingga menghasilkan delapan hash berbeda.

We pass each of our eight fragments through a hash function to get their hashes.

Kami meneruskan masing-masing delapan fragmen kami melalui fungsi hash untuk mendapatkan hashnya.


Oke, jadi kita punya sesuatu yang lebih masuk akal. Kami memiliki hash dari semua fragmen, jadi jika ada yang salah, kami akan mengetahuinya dengan membandingkannya dengan yang sumbernya, bukan? Mungkin saja, tapi itu juga sangat tidak efisien. Jika file Anda memiliki ribuan fragmen, apakah Anda benar-benar akan meng-hash semuanya dan membandingkan hasilnya dengan cermat?

Tidak. Sebaliknya, kita akan mengambil masing-masing pasangan hash, menggabungkannya, lalu melakukan hash bersama-sama. Jadi kita hash hA + hB, hC + hD, hE + hF, dan hG + hH. Kami berakhir dengan empat hash. Kemudian kita melakukan putaran hashing lagi dengan ini hingga menghasilkan dua. Terakhir, kita melakukan hash pada dua sisanya untuk mendapatkan hash master kita – root Merkle (atau hash root).

The structure looks like an upside-down tree. On the bottom row, we have the leaves, which are combined to produce the nodes and, finally, the root.

Strukturnya terlihat seperti pohon yang terbalik. Di baris paling bawah, kita memiliki daun, yang digabungkan untuk menghasilkan simpul dan, terakhir, akar.


Kami sekarang memiliki root Merkle yang mewakili file yang kami unduh. Kita dapat membandingkan hash root ini dengan yang disediakan oleh sumbernya. Jika cocok, sempurna! Namun jika hashnya berbeda, bisa dipastikan data tersebut telah diubah. Dengan kata lain, satu atau lebih fragmen menghasilkan hash yang berbeda. Jadi, sedikit modifikasi data akan memberi kita akar Merkle yang sangat berbeda.

Untungnya, ada cara praktis bagi kita untuk memeriksa fragmen mana yang salah. Dalam kasus kita, katakanlah itu dia. Anda akan mulai dengan menanyakan dua hash yang menghasilkan root Merkle (hABCD dan hEFGH) kepada rekan Anda. Nilai hABCD Anda harus sesuai dengan nilai mereka karena tidak ada kesalahan pada subpohon tersebut. Tapi hEFGH tidak akan melakukannya, jadi Anda tahu untuk memeriksanya di sana. Anda kemudian meminta hEF dan hGH, dan membandingkannya dengan milik Anda. hGH akan terlihat baik-baik saja, jadi Anda tahu bahwa hEF adalah pelakunya. Terakhir, Anda membandingkan hash hE dan hF. Anda sekarang tahu bahwa dia salah, sehingga Anda dapat mengunduh ulang potongan tersebut.

Kesimpulannya, pohon Merkle dibuat dengan membagi data menjadi beberapa bagian, yang kemudian di-hash berulang kali untuk membentuk akar Merkle. Anda kemudian dapat memverifikasi secara efisien apakah ada yang salah dengan suatu data. Seperti yang akan kita lihat di bagian selanjutnya, ada aplikasi menarik lainnya juga.


Ingin memulai dengan cryptocurrency? Beli Bitcoin di Binance!


Mengapa akar Merkle digunakan dalam Bitcoin?

Ada beberapa kasus penggunaan pohon Merkle, namun di sini kita akan fokus pada pentingnya pohon Merkle dalam blockchain. Pohon Merkle sangat penting dalam Bitcoin dan banyak mata uang kripto lainnya. Mereka merupakan komponen integral dari setiap blok, yang dapat ditemukan di header blok. Untuk mendapatkan daun pohon kita, kita menggunakan hash transaksi (TXID) dari setiap transaksi yang termasuk dalam blok.

Akar Merkle memiliki beberapa tujuan dalam kasus ini. Mari kita lihat aplikasinya dalam penambangan mata uang kripto dan verifikasi transaksi.


Pertambangan

Satu blok Bitcoin terdiri dari dua bagian. Bagian pertama adalah header blok, segmen berukuran tetap yang berisi metadata untuk blok tersebut. Bagian kedua adalah daftar transaksi yang ukurannya bervariasi, namun cenderung jauh lebih besar dari header.

Penambang perlu melakukan hashing data berulang kali untuk menghasilkan keluaran yang sesuai dengan kondisi tertentu untuk menambang blok yang valid. Mereka dapat melakukan triliunan upaya sebelum menemukannya. Dengan setiap upaya, mereka mengubah nomor acak di header blok (nonce) untuk menghasilkan keluaran yang berbeda. Namun sebagian besar bloknya tetap sama. Ada ribuan transaksi, dan Anda masih perlu melakukan hashing setiap saat.

Akar Merkle menyederhanakan prosesnya secara signifikan. Saat Anda mulai menambang, Anda menyusun semua transaksi yang ingin Anda sertakan dan membuat pohon Merkle. Anda meletakkan hash root yang dihasilkan (32 byte) di header blok. Kemudian, saat Anda menambang, Anda hanya perlu melakukan hash pada header blok, bukan keseluruhan blok.

Ini berfungsi karena tahan terhadap kerusakan. Anda secara efektif merangkum semua transaksi blok dalam format yang ringkas. Anda tidak dapat menemukan header blok yang valid dan kemudian mengubah daftar transaksi, karena itu akan mengubah root Merkle. Ketika blok dikirim ke node lain, mereka menghitung root dari daftar transaksi. Jika tidak cocok dengan yang ada di header, mereka menolak pemblokiran.


Verifikasi

Ada properti menarik lainnya dari akar Merkle yang dapat kita manfaatkan. Yang ini menyangkut klien ringan (node ​​yang tidak menyimpan salinan lengkap dari blockchain). Jika Anda menjalankan node pada perangkat dengan sumber daya terbatas, Anda tidak ingin mengunduh dan melakukan hashing pada semua transaksi blok. Yang dapat Anda lakukan hanyalah meminta bukti Merkle – bukti yang diberikan oleh node lengkap yang membuktikan bahwa transaksi Anda berada di blok tertentu. Hal ini lebih sering disebut sebagai Verifikasi Pembayaran Sederhana, atau SPV, dan dijelaskan secara rinci oleh Satoshi Nakamoto dalam whitepaper Bitcoin.

To check hD, we only need the hashes shown in red.

Untuk memeriksa hd, kita hanya perlu hash yang ditunjukkan dengan warna merah.


Pertimbangkan skenario di mana kita ingin mengetahui informasi tentang transaksi yang TXID-nya adalah hD. Jika hC diberikan kepada kita, kita dapat mengerjakan hCD. Kemudian, kita memerlukan hAB untuk menghitung hABCD. Terakhir, dengan hEFGH, kita dapat memeriksa apakah akar Merkle yang dihasilkan cocok dengan yang ada di header blok. Jika ya, ini adalah bukti bahwa transaksi tersebut termasuk dalam blok – hampir tidak mungkin untuk membuat hash yang sama dengan data yang berbeda.

Dalam contoh di atas, kita hanya perlu melakukan hash tiga kali. Tanpa bukti Merkle, kami perlu melakukannya sebanyak tujuh kali. Karena blok saat ini berisi ribuan transaksi, penggunaan bukti Merkle menghemat banyak waktu dan sumber daya komputasi.


Pohon Merkle telah terbukti sangat berguna dalam berbagai aplikasi ilmu komputer – seperti yang telah kita lihat, pohon Merkle sangat berharga dalam blockchain. Dalam sistem terdistribusi, pohon Merkle memungkinkan verifikasi informasi dengan mudah tanpa membanjiri jaringan dengan data yang tidak diperlukan.

Tanpa pohon Merkle (dan akar Merkle), blok Bitcoin dan mata uang kripto lainnya tidak akan sekompak sekarang. Dan meskipun klien ringan kurang dalam hal privasi dan keamanan, bukti Merkle memungkinkan pengguna untuk memeriksa apakah transaksi mereka telah dimasukkan dalam blok dengan overhead minimal.