Merkle Tree

Apa Itu Merkle Tree?

Merkle Tree adalah struktur data kriptografis yang mengatur banyak data ke dalam tree berisi hash.

Dalam kripto, Merkle Tree membantu blockchain memverifikasi transaksi, saldo, akun, nilai penyimpanan, klaim airdrop, whitelist NFT, dan kumpulan data besar lainnya secara efisien.

Merkle Tree juga disebut hash tree karena setiap tingkat tree dibangun dari nilai hash kriptografis.

Tingkat paling bawah berisi item data individual yang disebut leaf.

Setiap leaf di-hash, dipasangkan dengan hash lain, lalu di-hash kembali untuk membuat tingkat berikutnya.

Proses ini berlanjut hingga tersisa satu hash akhir di bagian atas.

Hash akhir tersebut disebut Merkle root.

Panduan developer Bitcoin menjelaskan bahwa hash transaksi dipasangkan dan di-hash berulang kali hingga tersisa satu Merkle root di header blok.

Gagasan utamanya sederhana: satu root kecil dapat merepresentasikan kumpulan data yang besar.

Jika ada item dalam kumpulan data yang berubah, hash di atasnya juga berubah, sehingga Merkle root ikut berubah.

Cara Kerja Merkle Tree

Merkle Tree dimulai dengan data mentah seperti transaksi, alamat wallet, catatan akun, atau entri klaim.

Setiap item diproses menggunakan fungsi hash kriptografis untuk membuat hash leaf.

Dua hash leaf digabungkan dan di-hash bersama untuk membuat hash parent.

Hash parent kemudian dipasangkan dan di-hash kembali untuk membuat hash tingkat yang lebih tinggi.

Proses ini berlanjut hingga hanya tersisa satu hash.

Hash akhir tersebut adalah Merkle root.

Merkle root berfungsi seperti fingerprint ringkas untuk seluruh kumpulan data.

Jika data tidak berubah, metode pembuatan tree yang sama seharusnya menghasilkan root yang sama.

Jika satu transaksi, alamat, saldo, atau jumlah klaim berubah, root akhir juga seharusnya berubah.

Mengapa Merkle Tree Penting dalam Kripto

Merkle Tree penting karena blockchain harus memverifikasi banyak data tanpa mengharuskan setiap pengguna memproses semuanya setiap saat.

Satu blok blockchain dapat berisi banyak transaksi.

Airdrop token dapat mencakup ribuan atau jutaan wallet yang memenuhi syarat.

Database state blockchain dapat mencakup akun, saldo, penyimpanan contract, dan kode.

Merkle Tree memungkinkan sistem membuat komitmen terhadap kumpulan data besar menggunakan satu root, sambil tetap memungkinkan item individual diverifikasi kemudian.

Hal ini meningkatkan efisiensi, skalabilitas, dan integritas data.

Merkle Tree juga mengurangi kebutuhan penyimpanan dan bandwidth untuk banyak aplikasi kripto.

Tanpa Merkle Tree atau struktur data terautentikasi serupa, banyak tugas verifikasi blockchain akan lebih lambat, berat, dan mahal.

Merkle Root

Merkle root adalah hash akhir di bagian atas Merkle Tree.

Merkle root merepresentasikan seluruh data di bawahnya.

Dalam sebuah blok blockchain, Merkle root dapat merangkum seluruh transaksi yang dimasukkan ke dalam blok tersebut.

Dalam contract airdrop, Merkle root dapat merangkum seluruh alamat wallet dan jumlah klaim yang memenuhi syarat.

Dalam state tree, root dapat merangkum banyak akun atau nilai penyimpanan.

Root tidak mengungkapkan seluruh kumpulan data dengan sendirinya.

Root hanya berfungsi sebagai komitmen kriptografis terhadap kumpulan data tersebut.

Pengguna tetap memerlukan proof dan aturan verifikasi yang tepat untuk memastikan bahwa satu item merupakan bagian dari tree.

Leaf dan Cabang Merkle

Leaf adalah hash pada tingkat paling bawah di Merkle Tree.

Setiap leaf biasanya merepresentasikan satu item data.

Contohnya, leaf dapat merepresentasikan hash transaksi, alamat wallet, catatan klaim, izin mint NFT, atau nilai akun.

Cabang adalah hash perantara di antara leaf dan root.

Cabang menghubungkan setiap leaf dengan Merkle root akhir.

Merkle proof menggunakan hash cabang ini untuk membuktikan bahwa satu leaf merupakan bagian dari tree.

Desain ini memungkinkan verifikasi tanpa menampilkan atau mengunduh semua leaf lainnya.

Proof Merkle Tree

Proof Merkle Tree adalah kumpulan hash sibling yang diperlukan untuk membuktikan bahwa sebuah leaf termasuk dalam tree dengan root yang diketahui.

Verifier memulai dari leaf yang dituju dan menggabungkannya dengan hash dalam proof sesuai urutan yang benar.

Jika hash akhir yang dihitung cocok dengan root tepercaya, proof tersebut valid.

Jika hash akhir yang dihitung tidak cocok dengan root tepercaya, proof tersebut tidak valid.

Dokumentasi MerkleProof OpenZeppelin menjelaskan alat smart contract untuk memverifikasi apakah suatu leaf dapat dibuktikan sebagai bagian dari Merkle Tree yang ditentukan oleh sebuah root.

Inilah alasan Merkle Tree berguna untuk whitelist on-chain, klaim, reward, dan pemeriksaan akses.

Merkle Tree di Bitcoin

Bitcoin menggunakan Merkle Tree untuk mengatur transaksi di dalam blok.

Setiap transaksi di-hash, lalu hash transaksi dipasangkan dan di-hash ke tingkat yang lebih tinggi hingga dihasilkan satu Merkle root.

Merkle root disimpan di header blok.

Hal ini membantu node Bitcoin mendeteksi apakah data transaksi telah diubah.

Merkle Tree juga mendukung verifikasi transaksi yang ringan.

Light client dapat menggunakan Merkle proof untuk memeriksa apakah suatu transaksi dimasukkan ke dalam blok tanpa mengunduh setiap transaksi di blok tersebut.

Hal ini mendukung simplified payment verification, yang sering disebut SPV.

SPV tidak selengkap validasi full node, tetapi lebih efisien untuk perangkat dan wallet dengan sumber daya terbatas.

Merkle Tree di Ethereum

Ethereum menggunakan struktur data terautentikasi terkait yang disebut Merkle Patricia Trie.

Dokumentasi Merkle Patricia Trie Ethereum menjelaskan bahwa struktur Ethereum bersifat deterministik dan dapat diverifikasi secara kriptografis.

Struktur ini membantu Ethereum merepresentasikan state akun, penyimpanan, dan data key-value lainnya.

Jika state berubah, state root juga berubah.

Hal ini memungkinkan client dan aplikasi Ethereum memverifikasi data state terhadap root yang diketahui.

Standar EIP-1186 eth_getProof menjelaskan metode RPC untuk memperoleh Merkle proof bagi akun dan nilai penyimpanan Ethereum.

Struktur Ethereum tidak sama dengan binary Merkle Tree sederhana, tetapi menggunakan konsep dasar yang sama, yaitu verifikasi melalui hash yang saling terhubung.

Merkle Tree dalam Airdrop

Airdrop kripto sering menggunakan Merkle Tree untuk mengelola daftar klaim yang besar.

Proyek dapat membuat daftar alamat wallet dan jumlah token yang memenuhi syarat.

Setiap pasangan alamat dan jumlah menjadi leaf dalam Merkle Tree.

Proyek hanya menyimpan Merkle root di smart contract.

Saat pengguna mengklaim airdrop, pengguna mengirimkan Merkle proof.

Contract memverifikasi bahwa wallet dan jumlah tersebut termasuk dalam tree yang direpresentasikan oleh root tersimpan.

Metode ini menghemat gas karena contract tidak perlu menyimpan setiap wallet yang memenuhi syarat secara langsung di on-chain.

Metode ini juga membuat kampanye klaim berskala besar lebih praktis.

Merkle Tree dalam Whitelist NFT

Proyek NFT sering menggunakan Merkle Tree untuk whitelist, presale, dan akses mint lebih awal.

Alih-alih menyimpan setiap alamat wallet yang disetujui dalam contract, proyek menyimpan satu Merkle root.

Setiap wallet yang disetujui menerima proof yang menunjukkan bahwa wallet tersebut termasuk dalam whitelist.

Saat mint, smart contract memeriksa proof terhadap root yang tersimpan.

Jika proof valid, wallet dapat melakukan mint sesuai aturan whitelist.

Metode ini dapat mengurangi biaya penyimpanan on-chain dan membuat verifikasi whitelist lebih efisien.

Pengguna tetap perlu memastikan bahwa halaman mint, alamat contract, dan Merkle root berasal dari sumber resmi.

Merkle Tree pada Light Client

Light client menggunakan metode verifikasi ringkas untuk mengurangi jumlah data blockchain yang perlu diunduh.

Merkle Tree membantu light client memverifikasi transaksi atau data state tertentu terhadap header blok atau root tepercaya.

Hal ini berguna untuk wallet seluler, browser, dan perangkat dengan kapasitas penyimpanan atau bandwidth terbatas.

Light client tidak memberikan model keamanan yang sama dengan node yang melakukan validasi penuh.

Namun, verifikasi berbasis Merkle dapat memberikan jaminan yang lebih baik daripada begitu saja memercayai satu penyedia data.

Hal ini menjadikan Merkle Tree sebagai komponen penting untuk infrastruktur kripto yang lebih mudah diakses.

Merkle Tree dalam Game Blockchain dan Aplikasi Metaverse

Game blockchain dan aplikasi metaverse dapat menggunakan Merkle Tree untuk memverifikasi daftar besar aset, reward, pemain, atau izin.

Game dapat menggunakan Merkle root untuk membuat komitmen atas kelayakan reward dalam satu musim.

Aplikasi metaverse dapat menggunakan Merkle root untuk memverifikasi klaim lencana acara atau izin lahan virtual.

Proyek NFT dapat menggunakan Merkle Tree untuk mengelola pengungkapan trait atau akses whitelist.

Metode ini memungkinkan aplikasi menyimpan kumpulan data besar secara off-chain sambil tetap memverifikasi entri tertentu secara on-chain.

Hasilnya dapat berupa biaya lebih rendah dan skalabilitas yang lebih baik.

Komprominya adalah proses pembuatan tree secara off-chain harus transparan dan benar.

Merkle Tree dan Integritas Data

Merkle Tree menjaga integritas data dengan membuat perubahan mudah dideteksi.

Jika satu leaf berubah, hash-nya juga berubah.

Perubahan itu memengaruhi hash parent, lalu hash parent berikutnya, dan akhirnya Merkle root.

Dengan demikian, verifier dapat membandingkan root untuk mendeteksi apakah kumpulan data tetap sama.

Merkle Tree tidak mencegah seseorang membuat kumpulan data palsu.

Merkle Tree membantu membuktikan apakah data cocok dengan root tertentu yang telah dikomitmenkan.

Karena itu, root harus berasal dari sumber tepercaya atau terverifikasi melalui konsensus.

Merkle Tree vs. Daftar Hash

Daftar hash adalah daftar sederhana yang berisi hash.

Merkle Tree adalah tree hash terstruktur yang mendukung proof ringkas.

Dengan daftar hash, verifikasi satu item mungkin memerlukan lebih banyak data dari seluruh daftar.

Dengan Merkle Tree, verifier biasanya hanya memerlukan leaf yang dituju dan sejumlah kecil hash sibling.

Hal ini membuat Merkle Tree lebih efisien untuk kumpulan data besar.

Keunggulan efisiensinya semakin penting seiring bertambahnya ukuran kumpulan data.

Merkle Tree vs. Merkle Patricia Trie

Merkle Tree adalah struktur data hash tree yang umum.

Merkle Patricia Trie adalah struktur yang lebih khusus dan digunakan untuk data key-value.

Ethereum menggunakan Merkle Patricia Trie yang telah dimodifikasi untuk penyimpanan dan verifikasi state yang efisien.

Merkle Tree sederhana sering digunakan untuk penyertaan transaksi, whitelist NFT, dan klaim airdrop.

Trie lebih sesuai ketika data perlu dicari berdasarkan key, seperti alamat akun atau slot penyimpanan.

Kedua struktur tersebut menggunakan hash kriptografis agar manipulasi data dapat dideteksi.

Merkle Tree vs. Verkle Tree

Verkle Tree adalah struktur data terautentikasi yang lebih baru dan menggunakan komitmen vektor, bukan hanya pasangan hash.

Verkle Tree sering dibahas sebagai peningkatan masa depan untuk sistem state blockchain karena dapat membuat beberapa proof menjadi lebih kecil.

Dokumentasi Ethereum menyebutkan bahwa Ethereum berencana beralih dari struktur Merkle Patricia Trie saat ini ke struktur Verkle Tree di masa depan.

Ini bukan berarti Merkle Tree sudah tidak relevan.

Merkle Tree masih banyak digunakan karena sederhana, andal, dan telah dipahami dengan baik.

Untuk banyak kasus penggunaan seperti airdrop dan whitelist, Merkle Tree tetap praktis dan efisien.

Manfaat Merkle Tree

Manfaat pertama adalah verifikasi yang efisien.

Pengguna dapat memverifikasi satu item tanpa mengunduh seluruh kumpulan data.

Manfaat kedua adalah integritas data.

Setiap perubahan pada data dasar akan mengubah hash di atasnya.

Manfaat ketiga adalah biaya penyimpanan on-chain yang lebih rendah.

Smart contract dapat menyimpan satu root alih-alih banyak catatan individual.

Manfaat keempat adalah skalabilitas.

Kumpulan data besar dapat direpresentasikan oleh satu root ringkas.

Manfaat kelima adalah privasi parsial.

Pengguna dapat membuktikan penyertaan tanpa mengungkapkan semua item lain dalam kumpulan data.

Risiko dan Keterbatasan Merkle Tree

Risiko pertama adalah root yang keliru.

Merkle proof hanya membuktikan penyertaan dalam kumpulan data yang direpresentasikan oleh root tersebut, sehingga root harus tepercaya atau terverifikasi.

Risiko kedua adalah konstruksi tree yang keliru.

Jika proyek menggunakan metode hashing, encoding, pengurutan, atau format leaf yang salah, proof dapat gagal atau menjadi tidak aman.

Risiko ketiga adalah kesalahan replay atau klaim ganda.

Contract klaim harus melacak apakah wallet telah menggunakan proof-nya jika klaim hanya boleh dilakukan satu kali.

Risiko keempat adalah phishing.

Scammer dapat membuat situs klaim palsu yang seolah-olah menggunakan Merkle proof, tetapi meminta pengguna menandatangani transaksi berbahaya.

Risiko kelima adalah kesalahpahaman.

Merkle Tree membuktikan penyertaan data, tetapi tidak membuktikan bahwa suatu proyek jujur, bernilai, atau aman.

Cara Mengevaluasi Sistem Merkle Tree

Mulailah dengan memeriksa apakah Merkle root berasal dari sumber resmi atau sumber yang terverifikasi melalui konsensus.

Tinjau cara leaf di-encode.

Periksa fungsi hash yang digunakan.

Pastikan apakah tree menggunakan pasangan yang diurutkan atau urutan kiri-kanan yang tetap.

Periksa apakah proof dibuat menggunakan alat resmi atau kode open-source.

Untuk smart contract, tinjau fungsi verifikasi proof dan logika pelacakan klaim.

Untuk airdrop dan whitelist NFT, verifikasi alamat contract resmi sebelum mengirimkan proof atau menandatangani transaksi.

Sistem Merkle Tree yang dirancang dengan baik seharusnya menjelaskan root, aturan, dan proses verifikasi dengan jelas.

Kesalahpahaman Umum tentang Merkle Tree

Salah satu kesalahpahaman umum adalah bahwa Merkle Tree menyimpan seluruh data secara on-chain.

Di banyak aplikasi kripto, hanya Merkle root yang disimpan secara on-chain, sedangkan seluruh kumpulan data dibuat dan disimpan secara off-chain.

Kesalahpahaman lainnya adalah bahwa Merkle root mengungkapkan seluruh kumpulan data.

Root hanya merupakan komitmen hash dan tidak menampilkan semua leaf dengan sendirinya.

Kesalahpahaman ketiga adalah bahwa Merkle proof yang valid membuktikan bahwa pengguna berhak mendapatkan reward secara moral atau hukum.

Proof tersebut hanya membuktikan bahwa data yang dikirimkan termasuk dalam kumpulan data yang direpresentasikan oleh root.

Kesalahpahaman keempat adalah bahwa semua Merkle Tree dibuat dengan cara yang sama.

Sistem yang berbeda dapat menggunakan fungsi hash, metode encoding, aturan pengurutan, dan struktur tree yang berbeda.

FAQ

Apa itu Merkle Tree secara sederhana?

Merkle Tree adalah tree berisi hash yang memungkinkan pengguna memverifikasi satu data di dalam kumpulan data besar menggunakan proof kecil.

Apa itu Merkle root?

Merkle root adalah hash akhir di bagian atas Merkle Tree dan berfungsi sebagai fingerprint ringkas untuk seluruh kumpulan data.

Mengapa blockchain menggunakan Merkle Tree?

Blockchain menggunakan Merkle Tree untuk memverifikasi kumpulan data besar secara efisien, mengurangi kebutuhan data, dan mendeteksi perubahan pada data transaksi atau state.

Bagaimana Bitcoin menggunakan Merkle Tree?

Bitcoin menggunakan Merkle Tree untuk merangkum transaksi di dalam blok, dan Merkle root disimpan di header blok.

Bagaimana Ethereum menggunakan struktur Merkle?

Ethereum menggunakan Merkle Patricia Trie yang dimodifikasi untuk menyimpan dan memverifikasi state akun serta data penyimpanan contract.

Apa itu Proof Merkle Tree?

Proof Merkle Tree adalah kumpulan hash sibling yang membuktikan bahwa leaf tertentu merupakan bagian dari tree dengan Merkle root yang diketahui.

Bagaimana Merkle Tree digunakan dalam airdrop?

Contract airdrop dapat menyimpan satu Merkle root dan memverifikasi klaim pengguna dengan Merkle proof, alih-alih menyimpan setiap wallet yang memenuhi syarat secara on-chain.

Bagaimana Merkle Tree digunakan dalam whitelist NFT?

Proyek NFT dapat menggunakan Merkle root untuk merepresentasikan wallet yang disetujui dan memverifikasi setiap wallet dengan proof saat mint.

Apakah Merkle Tree bersifat privat?

Merkle Tree dapat memberikan privasi parsial karena pengguna dapat membuktikan penyertaan tanpa mengungkapkan seluruh kumpulan data.

Apakah Merkle Tree sama dengan zero-knowledge proof?

Tidak. Merkle Tree membuktikan penyertaan data dalam kumpulan yang telah dikomitmenkan, sedangkan zero-knowledge proof dapat membuktikan pernyataan yang lebih luas tanpa mengungkapkan input pribadi.

Kesimpulan

Merkle Tree adalah struktur data inti dalam kripto yang memudahkan verifikasi kumpulan data besar.

Struktur ini mengubah banyak item data menjadi tree berisi hash dan menghasilkan satu Merkle root akhir.

Root tersebut dapat merepresentasikan transaksi, saldo, alamat, klaim, nilai penyimpanan, atau data blockchain lainnya.

Merkle Tree penting karena mendukung verifikasi yang efisien, biaya penyimpanan lebih rendah, integritas data, light client, airdrop, whitelist NFT, dan proof state blockchain.

Bitcoin menggunakan Merkle Tree untuk merangkum transaksi di dalam blok.

Ethereum menggunakan struktur terkait bernama Merkle Patricia Trie untuk state akun dan penyimpanan.

Aplikasi kripto menggunakan Merkle Tree ketika perlu membuktikan bahwa satu item termasuk dalam kumpulan data besar tanpa menempatkan seluruh kumpulan data tersebut di on-chain.

Merkle Tree sangat bermanfaat, tetapi bergantung pada hashing yang benar, encoding yang aman, root tepercaya, dan verifikasi proof yang aman.

Jika digunakan dengan baik, Merkle Tree membuat sistem kripto lebih ringan, murah, dan mudah diverifikasi.