Merkle Tree

Merkle Tree Property Notes

• NOTE: During _resetMerkleTree() there is no need to delete the siblingNodes values because _leafIndex is 0. Therefore it explicitly overwrites each siblingNodes[i] value at every level with the correct currentLevelHash value because _leafIndex % 2 == 0 is true for each iteration.

• Tree height 12 is used in the contract, meaning the largest anonymity set is 4,096 with 2^12 nodes.

• A height of n indicates there are n diagonally vertical edges from a leaf node to the root.

• There are n+1 total "levels" of nodes, including the root. (Ex: Height = 4, total levels of nodes = 5)

• 2^(n+1) - 1 total nodes in the tree, including the root. (Ex: Height = 4, total nodes = 2^5-1 = 31)

• There is always exactly one merkle path per leaf, per root.

• When recreating a merkle proof, the number of values in the path indices array and path elements array are equal to the height n.

• The path indices array for a given merkle path is the binary representation of the leaf index. Ex: Tree height of 4, path indices [1,0,1,1] means the proof is for leaf Index 13, and shows we are hashing up the tree [L,R,L,L]. We can always derive the leaf index from the path indices, and vice versa. Binary is typical feed into circom circuit logic in reverse order so it can smoothly loop and regenerate the correct numeric value from the bits.

• Algorithm for generating a merkle path for a normal binary tree. When the path index is 0 (R), the path element (sibling node needed to hash up the tree) will always be the zero value at that level. When the path index is 1, we always take the previously generated sibling node at that level.

• In a zero value initial state tree, with sequential leaf insertions, subtrees of height n are finalized after 2^n leaf insertions, shown in graphics as red.

• The latest sibling node values calculated on-chain are constantly changing based on the current leaf deposit.

Example Tree Illustration with Height 4

Green = New node value.

Yellow = Node value about to be set in stone.

Red = Node value has been set in stone.

C = Commitment

Z = Zero value (for that height)

. and | symbol used to represent a poseidon hashing of the left and right side.

(X,Y) coordinates for each node in the tree