In the simpler version, we don't care about our notes and witnesses. We just want to calculate the root (hash) of the tree.
But there is a caveat, we do not receive all the commitments at once. We receive them in chunks1.
We must be able to return the root after every chunk.
Let's consider this nearly full tree:
and suppose we do not get like that.
We get [H, I, J],
then [K, L],
and then finally [M, N].
How can we keep the least amount of data, not repeat any calculation and still return the same value of A at the end2?
Trivial (not optimal) solution
We can keep [H, I, ...] until we are asked to compute the root.
However,
- We keep all the leaves. For Zcash, we already have ~100 million entries;
- If we need to calculate the root at a later time, we will be repeating many of the same hash calculations. For example D = Hash(H|I).
This is not efficient at all.
Minimal but wrong
The smallest amount of data would be the current root hash. But then it is impossible to update it correctly. This solution clearly does not work.
Right Solution
To get a better solution, we want to avoid repeating the Hash calculations3.
Let's look at the first chunk. Once we received [H, I, J], we can notice that D = Hash(H|I). D will not change anymore because H and I cannot change. However, E will change because now E = Hash(J|.). Eventually, E = Hash(J|K).
Therefore we don't want to calculate the intermediate E. Same thing applies to B: B = Hash(D|E) but our E will change later and so will B.
Tree State
When we get the first chunk [H, I, J], we can merge (hash) H & I, but if we merge (J, EMPTY) we are going to compute unnecessary hashes. The hash we need is (J, K) but K is not available yet. It's better to keep J for later.
If we generalize to every layer, the state is either "null" or the node that forms the left side of the last incomplete pair.
Algorithm
When we receive a chunk, we do the following:
- align the nodes by prepending the previous left over node if there is one. If we did not do that, then we would be hashing (K, L) instead of (J, K);
- if there is an odd number of nodes, save the last node;
- hash each pair to get the next layer up.
Repeat until you reach the root.
Example
Initial State
Each layer starts with no left over node: state = (null, null, null)
Chunk [H, I, J]
Layer 0 (leaves)
- Prepend previous node if needed. It's null so we skip this step;
- Save the last node if the length is odd: J;
- Hash the remaining pairs: D = Hash(H, I).
State for layer 0: J
Layer 1
- Prepend previous node if needed. It's null so we skip this step;
- We have [D]. The length is odd, we save it;
- We have nothing left so we stop
State for layer 1: D
Layer 2
- Nothing changed
State for layer 2: null
Tree State
[J, D, null]
Chunk [K, L]
Layer 0 (leaves)
- Prepend previous node if needed. It's J, so we get [J, K, L];
- Save the last node if the length is odd: L;
- Hash the remaining pairs: E = Hash(J, K).
State for layer 0: L
Layer 1
- Prepend previous node if needed. It's D so we get [D, E];
- The length is odd, we set the state to null;
- We hash B = Hash(D, E)
State for layer 1: null
Layer 2
- We just have [B]. It's odd length therefore we save B.
State for layer 2: B
Tree State
[L, null, B]
Chunk [M, O]
We'll leave the detailed steps as an exercise.
The final tree state is [N, F, B]
Final pass
We do not have the root value A but we have the hashes needed to calculate it.
The root is obtained by using the tree state as the Merkle Path of the next leaf (which is empty by definition).
Starting with the first item of the tree state, N, we calculate G = Hash(N, .). Then we use the second item of the tree state, F: C = Hash(F, G). Then finally A = Hash(B, C).
At every step we combine the current hash H.
- if there is saved hash X, we calculate Hash(X, H);
- otherwise, we calculate Hash(H, ER) where ER is the empty root for that depth.
Note that this algorithm overflows if the tree is full. If we add [O], the tree state resets to [null, null, null] and we have an empty tree. In practice, this is not an issue because the capacity of the tree is much greater than what we need.
Edge
The Intermediate Hashes calculated as we walk up the tree to the root form the Edge of the tree.
This will be used in the section regarding witnesses.
Summary
We saw how we can maintain the tree state with a small amount of data (at most 32 hashes for Zcash). It is logarithmic in the capacity of the tree ().
Next, we'll consider how we can adapt this technique to produce Merkle Proofs for arbitrary notes.