🌲Merkle Tree

Merkle Tree is a data structure that is used to store and verify the integrity of data. It is a binary tree where each node has two children. The leaves of the tree are the data blocks that are stored and the internal nodes of the tree are the hashes of children below them. Consequently, the root of the tree is the culmination of all data blocks in the tree. This means that if any data blocks at the leaf nodes are changed or corrupted it will propagate to the root which will change too. The root hash of the Merkle tree can be compared to a reference to verify the integrity of the data. This makes the Merkle trees very efficient.

In our protocol, two Merkle trees are maintained on-chain:

1. Commitment tree: for storing note commitments.

2. Address tree: for storing the rootAddress of a shielded address, inserted during registration of a user with the Labyrinth protocol.