Module Make_Storage.Tree

module H = C.Hash
val max_uint32 : int64

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.

type tree =
  1. | Empty
  2. | Leaf of C.Commitment.t
  3. | Node of H.t * tree * tree
val tree_encoding : tree Data_encoding.encoding
val get_root_height : tree -> int -> H.t
val pow2 : int -> int64
val split_at : Mavryk_stdlib.Compare.Int64.t -> 'a list -> 'b list * 'a list
val hash : height:int -> tree -> tree -> H.t
val insert : tree -> int -> Mavryk_stdlib.Compare.Int64.t -> C.Commitment.t list -> tree
val insert_node : tree -> tree -> int -> Mavryk_stdlib.Compare.Int64.t -> C.Commitment.t list -> tree
val get_cm_height : tree -> Mavryk_stdlib.Compare.Int64.t -> int -> C.Commitment.t
val get_witness_height : tree -> int -> Mavryk_stdlib.Compare.Int64.t -> bytes

Create the witness in the format required by Sapling.

  • height of the merkle tree (32 for Sapling)
  • a list of size of hash (32 for Pedersen hash) and hash
  • the position as little-endian uint64
val fold_from_height : pos:Mavryk_stdlib.Compare.Int64.t -> f:('a -> C.Commitment.t -> 'b) -> init:'c -> tree -> int -> 'd
type t = int64 * tree
val encoding : (int64 * tree) Data_encoding.encoding
val empty : int64 * tree
val size : ('a * 'b) -> 'c
val default_height : int
val max_size : int64
val get_root : ('a * tree) -> H.t
val add : (Mavryk_stdlib.Compare.Int64.t * tree) -> C.Commitment.t list -> int64 * tree
val get_witness : (Mavryk_stdlib.Compare.Int64.t * tree) -> Mavryk_stdlib.Compare.Int64.t -> bytes option