Crate bridgetree

bridgetree

This crate provides an implementation of an append-only Merkle tree structure. Individual leaves of the merkle tree may be marked such that witnesses will be maintained for the marked leaves as additional nodes are appended to the tree, but leaf and node data not specifically required to maintain these witnesses is not retained, for space efficiency. The data structure also supports checkpointing of the tree state such that the tree may be reset to a previously checkpointed state, up to a fixed number of checkpoints.

The crate also supports using “bridges” containing the minimal possible amount of data to advance witnesses for marked leaves data up to recent checkpoints or the the latest state of the tree without having to append each intermediate leaf individually, given a bridge between the desired states computed by an outside source. The state of the tree is internally represented as a set of such bridges, and the data structure supports fusing and splitting of bridges.

Marking

Merkle trees can be used to show that a value exists in the tree by providing a witness to a leaf value. We provide an API that allows us to mark the current leaf as a value we wish to compute witnesses for even after the tree has been appended to in the future; this is called maintaining a witness. When we’re later no longer in a leaf, we can remove the mark and drop the now unnecessary information from the structure.

Checkpoints and Rollbacks

This data structure supports a limited capability to restore previous states of the Merkle tree. It is possible identify the current state of the tree as a “checkpoint” to which the tree can be reset, and later remove checkpoints that we’re no longer interested in being able to reset the state to.

In this module, the term “ommer” is used as for the sibling of a parent node in a binary tree.

Structs

Address

The address of an internal node of the Merkle tree. When level == 0, the index has the same value as the position.

BridgeTree

A sparse representation of a Merkle tree with linear appending of leaves that contains enough information to produce a witness for any marked leaf.

Checkpoint

A data structure used to store the information necessary to “rewind” the state of a BridgeTree to a particular leaf position.

Frontier

A possibly-empty Merkle frontier.

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.

MerkleBridge

The information required to “update” witnesses from one state of a Merkle tree to another.

NonEmptyFrontier

A NonEmptyFrontier is a reduced representation of a Merkle tree, containing a single leaf value, along with the vector of hashes produced by the reduction of previously appended leaf values that will be required when producing a witness for the current leaf.

Position

A type representing the position of a leaf in a Merkle tree.

Enums

BridgeTreeError

Errors that can appear when validating the internal consistency of a [BridgeTree] value when constructing a tree from its constituent parts.

ContinuityError

Errors that can be discovered during checks that verify the compatibility of adjacent bridges.

FrontierError

Validation errors that can occur during reconstruction of a Merkle frontier from its constituent parts.

WitnessingError

Errors that can be discovered during the process of attempting to create the witness for a leaf node.

Traits

Hashable

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