Let's track one of the notes and track it. For example H. H is the first note, i.e. at position p = 0.
Initial Merkle Proof
What is its Merkle Proof ?
From the position p, we figure out the path from the root: L, L, L.
At the moment the note was added, there are no notes after it since it is an incremental tree.
Therefore whenever we have a L node, we know that the right node is the empty root.
If we have a R node, we must have the left node.
For example, node I has position 1 and path L, R, L. The path is therefore [H, EMPTY, EMPTY].
We do not need to store the EMPTY hashes because they can be shared/cached.
Then a witness is
pub struct Path {
pub value: Hash,
pub pos: usize,
pub left: Vec<Hash>,
}
The path changes later as nodes are added to the tree.
Right Nodes
Left nodes will never change, but right nodes are different.
They all start equal to the empty root of their corresponding depth but then they start to evolve into their final value.
For example for I, the layer 1 starts as empty root of depth 1. Then with J, the value at E changes.
However, just like when we were working to calculate the root, we do not want to compute intermediate hashes.
The Right nodes are not stored until we get to K.
If the Merkle Proof needs to be obtained before we get K, for example after receiving [H, I, J], then E is the current Edge of the tree. See Edge.
The definition of a Witness is
pub struct Witness {
pub path: Path, // path when the witness was created
pub right: Vec<Hash>, // right nodes added after
}
Where the right nodes are added when we hash them as part of the process described in the Algorithm used to compute the root.
Merkle Proof
To get the Merkle Proof, we follow the same principle as before:
- From the position, we deduce the path;
- We follow the path, looking for the Left or the Right sibling;
- If we need the Left node, we have
it in the
path.left
vector; - If we need the right node, we have it
in
right
vector. However, when we run out right nodes, we pick up the node from the tree Edge (at the current depth, only once), and then from the empty roots (for the remaining ones).
In the next and final section, we'll discuss Bridges, an important performance optimization.