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
- Level represents the height from the leaves. Examples:
eis level 0,
cis level 1,
ais level 2.
indexis the 0-based distance from the left-most node on a given Level. Examples:
fhas index 2,
chas index 1, and
ahas 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
cis at Level 1 and index 1, the Address of
fis at Level 0, index 2.
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
ommers refers to the node’s ommer, plus each ancestor’s ommer.
test-dependenciesTraits and types used to permit comparison testing between tree implementations.
- 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
0are leaves, nodes at level
1are parents of nodes at level
0, 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.
- A type for metadata that is used to determine when and how a leaf can be pruned from a tree.
- A trait describing the operations that make a type suitable for use as a leaf or node value in a merkle tree.