Crate incrementalmerkletree

source ·
Expand description

Common types and utilities used in incremental Merkle tree implementations.

Several different abstractions are used for navigating tree structure. Consider this example binary tree:

     a
    / \
   /   \
  /     \
  b      c
 / \    / \
d   e  f   g

Location Abstractions:

  • Level represents the height from the leaves. Examples: e is level 0, c is level 1, a is level 2.
  • index is the 0-based distance from the left-most node on a given Level. Examples: f has index 2, c has index 1, and a has index 0.
  • Position is a type abstraction of the index of a leaf at Level 0.
  • Address locates any node within a tree by representing the Level and index. Examples: the Address of c is at Level 1 and index 1, the Address of f is at Level 0, index 2.

Relationship Abstractions:

A given node has these navigational relationships:

  • parent - the node directly above at one higher Level.
  • child - the complementary relationship to parent; a parent may have up to two children because only binary trees are supported.
  • sibling - the other node with the same parent.
  • cousin - a node at the same Level excluding the sibling.
  • ommer - the parent’s sibling.
  • root - the single node with the largest Level.
  • ancestor - the parent or an ancestor of the parent; the root is an ancestor of every other node.

Note: we often refer to ommers (plural) when describing leaf-to-root paths, so in that context ommers refers to the node’s ommer, plus each ancestor’s ommer.

Modules§

  • frontier
  • testingtest-dependencies
    Traits and types used to permit comparison testing between tree implementations.
  • witnesslegacy-api

Structs§

  • Address
    The address of a node of the Merkle tree. When level == 0, the index has the same value as the position.
  • Level
    A type-safe wrapper for indexing into “levels” of a binary tree, such that nodes at level 0 are leaves, nodes at level 1 are parents of nodes at level 0, and so forth. This type is capable of representing levels in trees containing up to 2^255 leaves.
  • MerklePath
    A path from a position in a particular commitment tree to the root of that tree.
  • Position
    A type representing the position of a leaf in a Merkle tree.

Enums§

  • Retention
    A type for metadata that is used to determine when and how a leaf can be pruned from a tree.
  • Source

Traits§

  • Hashable
    A trait describing the operations that make a type suitable for use as a leaf or node value in a merkle tree.