Module canopy

Canopy is way to cache the upper N levels of a SPL ConcurrentMerkleTree.

By caching the upper N levels of a depth D SPL ConcurrentMerkleTree, proofs can be truncated to the first D - N nodes. This helps reduce the size of account compression transactions, and makes it possible to modify trees up to depth 31, which store more than 1 billion leaves.

Note: this means that creating a tree of depth > 24 without a canopy will be impossible to modify on-chain until TransactionV2 is launched.

To initialize a canopy on a ConcurrentMerkleTree account, you must initialize the ConcurrentMerkleTree account with additional bytes. The number of additional bytes needed is (pow(2, N+1)-1) * 32, where N is the number of levels of the merkle tree you want the canopy to cache.

The canopy will be updated everytime the concurrent merkle tree is modified. No additional work needed.

Functions

• check_canopy_bytes
• check_canopy_no_nodes_to_right_of_index
  Checks the canopy doesn’t have any nodes to the right of the provided index in the full tree. This is done by iterating through the canopy nodes to the right of the provided index and finding the top-most node that has the node as its left child. The node should be empty. The iteration contains following the previous checked node on the same level until the last node on the level is reached.
• check_canopy_root
  Checks the root of the canopy against the expected root.
• fill_in_proof_from_canopy
• set_canopy_leaf_nodes
  Sets the leaf nodes of the canopy. The leaf nodes are the lowest level of the canopy, representing the leaves of the canopy-tree. The method will update the parent nodes of all the modified subtrees up to the uppermost level of the canopy. The leaf nodes indexing for the start_index is 0-based without regards to the full tree indexes or the node indexes. The start_index is the index of the first leaf node to be updated.
• update_canopy