Ada baiknya kita memahami sedikit mengenai tree data structure, karena digunakan dalam blockchain untuk menyimpan data transaksi didalam masing-masing block.
Ethereum menggunakan gabungan antara merkle dan patricia tree. Kita akan bahas sedikit apa itu merkle dan patricia.
Merkle Tree
Untuk struktur data yang besar, Merkle Tree sangat efisien dan aman dalam melakukan verifikasi. Untuk melakukan verifisikasi tree, cukup memeriksa hash root.
Aturan dari Merkle Tree adalah
- Setiap leaf merupakan berisi hash data.
- Setiap node(bukan leaf) berisi hash dari child node.
Dalam kasus blockchain, Merkle Tree digunakan untuk menyimpan sekumpulan transaksi. Berikut contoh diagram Merkle Tree
Contoh, untuk T4 valid atau tidak, diperlukan data 3 node, yaitu data sibling dari parent T4, yaitu H3, kemudian sibling dari parent H4, yaitu H(H1,H2), dan sibling dari parent H(H1,H2), yaitu H(H(H5, H6), H(H7, H8).
Patricia Tree
adalah struktur data yang space optimized di mana setiap node paling banyak memiliki 2 child.
Fitur Patricia Tree:
- Menggunakan key/value pairs, key digunakan untuk melakukan traversal untuk mencari value dari sebuah leaf.
- Dapat dilakukan insert dan deletion.
- Efisien untuk dataset yang besar.
Ethereum menggunakan kombinasi dari Merkle dan Patricia tree.