Merkle and Verkle trees
Notes
Blockchain
08/19/2022
Merkle Practicia Trie
In general, data structures are used to efficiently store and retrieve data. In the world of blockchain, merkle trees are quite popular as it is being used in bitcoin and in the ethereum blockchain to store and verify the state (Modified Merkle Patricia Trie - Fig1). Now-a-days the merkle proofs are being utilized for various usecases like whitelisting address for token airdrops, NFT minting and so on...
What are Merke trees?
In a nutshell, a merkle tree is a tree data structure in which all the non-leaf nodes are the hash (sha256) of its child nodes. It is constructed by recursively hashing all the nodes until only one node is left which is called the merkle root. Every node is either (i) empty, (ii) a leaf node containing a key and value, or (iii) an intermediate node that has some fixed number of children (the "width" of the tree). The value of an intermediate node is computed as a hash of the values of its children.Merkle Trees are computationally fast, and a Merkle Tree over n nodes can be constructed in O(n) time.
Binary Merkle Tree (Fig-2)
Use cases:
- Consensus Protocols
- Public-Key Directories
- Cryptocurrencies
- Encrypted Web Applications
- Secure File Systems
Verification of merkle proof:
Consider Fig-2 as a file storage system, and we need to validate the file F3 returned by the file system (fs from now on) is valid. So in-order to compute the proof, the fs sends the following nodes along with the file F3.
The Merkle Proof (in yellow)
The Merkle proof of a leaf in a Merkle tree consists of the siblings of each of the nodes in the path from the leaf to the Merkle root.
The problem here is, the size of the merkle proof is directly proportional to the number of nodes. If Alice has around 1 billion files (230), the depth of the tree will be around 30. The proof size will be around 1KB. hence the Merkle Proof itself could create a large and expensive bandwidth overhead.
To overcome this issue, one can introduce a k-ary Merkle tree where k ( > 2 ) is the branching factory to reduce the depth of the tree. Giving our Merkle tree
a branching factor of k reduces the height of the tree, unfortunately, the Merkle proof actually grows larger, from O(log2 n) to
O(k logk n)
A 3-ary Merkle Tree
Verkle trees:
Verkle trees are similar to merkle trees with a difference that the hash function is replaced by Vector commitments.
According to Vitalik, a vector commitment scheme is a special type of hash function, hashing a list
. But vector commitments have the special property that for a commitment C and a value zi, it's possible to make a short proof that is the commitment to some list where the value at the i'th position is zi. In a Verkle proof, this short proof replaces the function of the sister nodes in a Merkle Patricia proof, giving the verifier confidence that a child node really is the child at the given position of its parent node.
Verkle Tree
Comparision:
| Operation | Construction | Proof size |
|---|---|---|
| Merkle Tree | O(n) | O(log2n) |
| k-ary Merkle Tree | O(n) | O(klogkn) |
| (k-ary) Verkle Tree | O(kn) | O(logkn) |
Conclusion:
Verkle trees are efficient than merkle trees as they eliminate the need of siblings for proof calculation. Though they are cryptographically complex to implement, it faciliates improvements in ZK-SNARKs, ethereum scaling and more...