package tezos-base

  1. Overview
  2. Docs
Legend:
Library
Module
Module type
Parameter
Class
Class type
type elt

The element type elt of the Merkle tree.

val elt_bytes : elt -> Stdlib.Bytes.t

elt_bytes x returns the byte sequence representation of the element x.

include HASH
include MINIMAL_HASH
type t
val name : string
val title : string
val pp : Stdlib.Format.formatter -> t -> unit
val pp_short : Stdlib.Format.formatter -> t -> unit
include Tezos_stdlib.Compare.S with type t := t
val (=) : t -> t -> bool
val (<>) : t -> t -> bool
val (<) : t -> t -> bool
val (<=) : t -> t -> bool
val (>=) : t -> t -> bool
val (>) : t -> t -> bool
val compare : t -> t -> int
val equal : t -> t -> bool
val max : t -> t -> t
val min : t -> t -> t
val hash_bytes : ?key:Stdlib.Bytes.t -> Stdlib.Bytes.t list -> t
val hash_string : ?key:string -> string list -> t
val zero : t
include RAW_DATA with type t := t
val size : int
val to_hex : t -> Hex.t
val of_hex_opt : Hex.t -> t option
val of_hex_exn : Hex.t -> t
val to_string : t -> string
val of_string : string -> t Tezos_error_monad.Error_monad.tzresult
val of_string_opt : string -> t option
val of_string_exn : string -> t
val to_bytes : t -> Stdlib.Bytes.t
val of_bytes : Stdlib.Bytes.t -> t Tezos_error_monad.Error_monad.tzresult
val of_bytes_opt : Stdlib.Bytes.t -> t option
val of_bytes_exn : Stdlib.Bytes.t -> t
include B58_DATA with type t := t
val to_b58check : t -> string
val to_short_b58check : t -> string
val of_b58check : string -> t Tezos_error_monad.Error_monad.tzresult
val of_b58check_exn : string -> t
val of_b58check_opt : string -> t option
type Tezos_crypto.Base58.data +=
  1. | Data of t
val b58check_encoding : t Tezos_crypto.Base58.encoding
include ENCODER with type t := t
val encoding : t Data_encoding.t
val rpc_arg : t Tezos_rpc.RPC_arg.t
include INDEXES with type t := t
val hash : t -> int
val seeded_hash : int -> t -> int
val to_path : t -> string list -> string list
val of_path : string list -> t option
val of_path_exn : string list -> t
val prefix_path : string -> string list
val path_length : int
module Set : sig ... end
module Map : sig ... end
module Table : sig ... end
module Error_table : sig ... end
module WeakRingTable : sig ... end
val compute : elt list -> t

compute xs computes a full binary tree from the list xs.

In this tree the ith leaf (from left to right) is the ith element of the list xs. If xs is the empty list, then the result is the empty tree. If the length of xs is not a power of 2, then the tree is padded with leaves containing the last element of xs such that a full tree is obtained.

Example: given the list [1; 2; 3], the tree

           /\
          /  \
         /\  /\
        1 2  3 3

is built.

val empty : t

The empty Merkle tree.

type path =
  1. | Left of path * t
  2. | Right of t * path
  3. | Op

A path to an element in a Merkle tree.

A path is either:

  • Left (p, r), indicating that the element is in the left subtree, from which the path p should be taken to find the element. r is the left subtree where this branching decision is made.
  • Right (l, p), indicating that the element is in the right subtree, from which the path p should be taken to find the element. l is the left subtree where this branching decision is made.
  • Op, indicating that the path traversal has reached the element.

Example:

           /\
          /  \
         /\  /\
        4 5  6 7

The path to the third leaf, containing 6 will be:

Right (node (leaf 4, leaf 5), Left (Op, leaf 7))

Consequently, the path will contain all the information to reconstruct the full tree, except the element to which the path lead.

val path_encoding : path Data_encoding.t

Encoding of a path.

val bounded_path_encoding : ?max_length:int -> unit -> path Data_encoding.t

Encoding of a path, with optional bound max_length.

The encoding is bounded to log2(max_length) * (size + 1) + 1 bytes.

val compute_path : elt list -> int -> path

compute_path xs i computes the path to the ith leaf of the Merkle tree computed from xs, that will also contain the ith element of xs.

val check_path : path -> elt -> t * int

check_path p x returns a pair (t, i) where t is the full Merkle tree reconstructed from the path t with x at the last position of the path, and i is the index of x in that tree.

OCaml

Innovation. Community. Security.