package octez-libs

  1. Overview
  2. Docs
package octez-libs
Legend:
Library
Module
Module type
Parameter
Class
Class type
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 : Tezos_stdlib.Compare.Int64.t -> 'a list -> 'a list * 'a list
val hash : height:int -> tree -> tree -> H.t
val insert : tree -> int -> Tezos_stdlib.Compare.Int64.t -> C.Commitment.t list -> tree
val insert_node : tree -> tree -> int -> Tezos_stdlib.Compare.Int64.t -> C.Commitment.t list -> tree
val get_cm_height : tree -> Tezos_stdlib.Compare.Int64.t -> int -> C.Commitment.t
val get_witness_height : tree -> int -> Tezos_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:Tezos_stdlib.Compare.Int64.t -> f:('a -> C.Commitment.t -> 'a) -> init:'a -> tree -> int -> 'a
type t = int64 * tree
val encoding : (int64 * tree) Data_encoding.encoding
val empty : int64 * tree
val size : ('a * 'b) -> 'a
val default_height : int
val max_size : int64
val get_root : ('a * tree) -> H.t
val add : (Tezos_stdlib.Compare.Int64.t * tree) -> C.Commitment.t list -> int64 * tree
val get_witness : (Tezos_stdlib.Compare.Int64.t * tree) -> Tezos_stdlib.Compare.Int64.t -> bytes option
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct