Merkle Tree#
Problem: Hashing an array (n elements)
Traditional solution: Concatenate each data and then hash, with both time and space complexity being $O(n)$.
Using Merkle tree: Only need to compute the hashes along the path, with both time and space complexity being $O(logn)$; the cost is that the total storage space increases (needs to store the hash tree), but it is still $O(n)$.
Trie Tree#
Indexing based on prefixes, suitable for storing data with similar prefixes.
The worst depth is the length of the longest string (which is the time complexity), but it is not necessarily a binary tree.
Suitable for prefix dictionary lookups.
Merkle Patricia Tree#
Transforms the binary Merkle tree into a 16-way tree.
The parent node records pointers to 16 branches, plus a value field representing its own value.
Here, the pointers are the hash values of the child nodes, stored in a key-value DB to assist with reverse lookups.
Simultaneously responsible for both hashing and indexing functions.
16-way reduces depth -> reduces the number of database requests.
Rollup's State Tree#
Separates map and value.
Verkle Tree#
Based on KZG.
Constructs a 16-way tree accordingly.
