Crate incrementalmerkletree
source ·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, anda
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 ofc
is at Level 1 and index 1, the Address off
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§
- testing
test-dependencies
Traits and types used to permit comparison testing between tree implementations. - witness
legacy-api
Structs§
- The address of a node of the Merkle tree. When
level == 0
, the index has the same value as the position. - A type-safe wrapper for indexing into “levels” of a binary tree, such that nodes at level
0
are leaves, nodes at level1
are parents of nodes at level0
, and so forth. This type is capable of representing levels in trees containing up to 2^255 leaves. - A path from a position in a particular commitment tree to the root of that tree.
- A type representing the position of a leaf in a Merkle tree.
Enums§
- A type for metadata that is used to determine when and how a leaf can be pruned from a tree.
Traits§
- A trait describing the operations that make a type suitable for use as a leaf or node value in a merkle tree.