Merkle Patricia Tree
Basic: Radix Tree
A Radix Tree using address as the key looks like below:
- Addresses are represented as Hex Characters
- Each node in the Tree is a 16-elements array, 16 branch-slots(0123...def)
- leaf node: value can be any binary data carried by the address
- non-leaf node: value is the hash value calculated based on the children’s data
As for a 160-bits address, the max height of the tree is 40
Problems: much space for a single entry 40 steps for each lookup
Advanced: Merkle Patricia Tree
In order to reduce the storage of Radix Tree. The nodes in Merkle Patricia Tree are divided into three kinds,
- extension node: compress nodes using common prefix
- leaf node: compress nodes using unique suffix
- branch node: same as node in Radix Tree
How to store Merkle Patricia Tree
hash(value) = sha3(serialize(value))
key = hash(value)
How to update Merkle Patricia Tree
DFS from top to bottom
Update, Delete or Insert
1.Query the node from top to bottom
2.update the hash along the path from bottom to top
Performance Each operation costs O(log(n))
How to verify using Merkle Patricia Tree
1.Same merkle trees must have same root hash.
2.Different merkle trees must have different root hash.
Using the theorems, we can verify the result of the execution of transactions.
A light client, without sync huge transactions, can immediately determine the exact balance and status of any account by simply asking the network for a path from the root to the account node.