Merkle trees
zkProver’s data is stored in the form of a special Sparse Merkle Tree (SMT), which is a tree that combines the concept of a Merkle Tree and that of a Patricia tree. The design is based on how the Sparse Merkle Trees are constructed and how they store keys and values.
Tip
The content of this document is rather elementary. Experienced developers can fast-forward to later sections and only refer back as the need arises.
A typical Merkle tree has leaves, branches and a root. A leaf is a node with no child-nodes, while a branch is a node with child-nodes. The root is therefore the node with no parent-node.
See the below figure for an example of how a hash function
Firstly, each leaf is nothing but the hash value
Secondly, the branch nodes are computed as follows;
Thirdly, the root is computed as
Leaves that share a parent-node are called siblings. The same terminology applies to branches. For example,
Keys and navigating a Merkle tree¶
Note the bits used to label edges in figure above. The strings of these bits are called Keys, and they indicated where a node is located in a Merkle Tree. Since these keys uniquely locate nodes, they are used to navigate from the root to the leaves (and backwards).
Suppose one is given the key-value pair
In order to locate the key-value pair
-
a zero-key-bit “
” means “follow the edge going to the left”, -
a key-bit “
” means “follow the edge going to the right”.
Since
- Read the least-significant bit of
, which is , hence traverse the tree to the left, and reach . - Then read the second significant key-bit, which is “
” in this case. So take the edge going to the right, reaching . - Again, read the next key-bit, which is “
”, hence follow the edge going to the right, reaching the leaf .
Since
One can similarly climb the tree, going in the reverse direction, by using the key-bits of the given key in the reverse order. That is, starting with the last key-bit used to reach the leaf and ending with the least-significant bit of the key.
The tree-address of the value
In the above example, the tree-address of 011
.
A Merkle proof example¶
Merkle Trees can be used as commitment schemes. And here is an example that follows the (key,value)-pair approach used in the zkProver. Consider the Merkle Tree shown in the figure above.
If the prover has committed to a value
- The Merkle root, denoted by
, - The value
, and - The siblings;
, and .
Instead of searching through all hash values stored in the tree, the verifier uses only a few hash values of relevant siblings. That is, three siblings in this case.
The verifier then checks the prover’s claim by computing the Merkle root as follows;
-
He computes
, which is the hash of the value . -
Then uses the sibling
to compute , which should be the same as the branch node . -
Next, he computes
, corresponding to the branch node . -
Now, uses
.
The Merkle proof is concluded by checking whether
Note
The symbol tilde
denoted