Module Hashed.Operation_list_hash

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.

type t
val name : string
val title : string
val pp : Stdlib.Format.formatter -> t -> unit
val pp_short : Stdlib.Format.formatter -> t -> unit
include Mavryk_stdlib.Compare.S with type t := t
val (=) : t -> t -> bool

x = y iff compare x y = 0

val (<>) : t -> t -> bool

x <> y iff compare x y <> 0

val (<) : t -> t -> bool

x < y iff compare x y < 0

val (<=) : t -> t -> bool

x <= y iff compare x y <= 0

val (>=) : t -> t -> bool

x >= y iff compare x y >= 0

val (>) : t -> t -> bool

x > y iff compare x y > 0

val compare : t -> t -> int

compare an alias for the functor parameter's compare function

val equal : t -> t -> bool

equal x y iff compare x y = 0

val max : t -> t -> t

max x y is x if x >= y otherwise it is y

val min : t -> t -> t

min x y is x if x <= y otherwise it is y

val hash_bytes : ?key:Stdlib.Bytes.t -> Stdlib.Bytes.t list -> t
val hash_string : ?key:string -> string list -> t

hash_string ?key inputs returns a hash.

Raises an Assert_failure if String.length key > 64.

val zero : t
val size : int
val to_hex : t -> Mavryk_stdlib.Hex.t
val of_hex_opt : Mavryk_stdlib.Hex.t -> t option
val of_hex_exn : Mavryk_stdlib.Hex.t -> t
val to_string : t -> string
val of_string : string -> t Mavryk_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 Mavryk_error_monad.Error_monad.tzresult
val of_bytes_opt : Stdlib.Bytes.t -> t option
val of_bytes_exn : Stdlib.Bytes.t -> t
val to_b58check : t -> string
val to_short_b58check : t -> string
val of_b58check : string -> t Mavryk_error_monad.Error_monad.tzresult
val of_b58check_exn : string -> t
val of_b58check_opt : string -> t option
type Base58.data +=
  1. | Data of t
val b58check_encoding : t Base58.encoding
val encoding : t Data_encoding.t
val rpc_arg : t Mavryk_rpc.Arg.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.