Crate incrementalmerkletree

Expand description

Common types and utilities used in incremental Merkle tree implementations.

§Navigating Tree Structure

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
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§

Marking: An enumeration of the additional marking states that can be applied to leaves with Retention::Checkpoint retention.
Retention: A type for metadata that is used to determine when and how a leaf can be pruned from a tree.
Source

Traits§