Module Make_Storage.TreeSource

Incremental Merkle Tree * * A tree of height h contains 2^h leaves and h+1 levels of nodes with * leaves at level 0 and root at level h. * * The leaves are commitments and the tree is treated as always filled * with a default value H.uncommitted. This allows to have proofs of * membership, or witnesses, of fixed size. * * All the nodes at the same level of an empty tree have the same hash, * which can be computed from the default value of the leaves. This is * stored in the uncommitted list. * * Any subtree filled with default values is represented by the Empty * constructor and given its height it's possible to compute its hash * using the uncommitted list. * * The leaves are indexed by their position pos, ranging from 0 to * (2^h)-1. The encoding of pos limits the possible size of the tree. * In any case the only valid height for the Sapling library is 32, so even * if the library encodes positions as uint64, they never exceed uint32. * * The tree is incremental in the sense that leaves cannot be modified but * only added and exclusively in successive positions. * The type t contains the size of the tree which is also the next position * to fill. * * Given that elements are added and retrieved by position, it is possible * to use this information to efficiently navigate the tree. * Given a tree of height h and a position pos, if pos < pow2 (h-1) only * the left subtree needs to be inspected recursively. Otherwise only the * right needs to be visited, decreasing pos by pow2 (h-1). * * In order to avoid storing the height for each subtree (or worse * recomputing it), each function with suffix `_height` expects the height * of the tree as parameter. These functions are only for internal use and * are later aliased by functions using the default height of a Sapling * incremental Merkle tree.