Crate incrementalmerkletree
source · [−]Expand description
incrementalmerkletree
Incremental Merkle Trees are fixed-depth Merkle trees with two primary capabilities: appending (assigning a value to the next unused leaf and advancing the tree) and obtaining the root of the tree. Importantly the tree structure attempts to store the least amount of information necessary to continue to function; other information should be pruned eagerly to avoid waste when the tree state is encoded.
Witnessing
Merkle trees are typically used to show that a value exists in the tree via an authentication path. We need an API that allows us to identify the current leaf as a value we wish to compute authentication paths for even as the tree continues to be appended to in the future; this is called maintaining a witness. When we’re later uninterested in such a leaf, we can prune a witness and remove all unnecessary information from the structure as a consequence.
Checkpoints and Rollbacks
The structure is not append-only in the strict sense. It is possible to identify the current state of the tree as a “checkpoint” and to remove older checkpoints that we’re no longer interested in. It should be possible to roll back to any previous checkpoint.
Modules
A space-efficient implementation of the Tree interface.
Structs
A type-safe wrapper for indexing into “levels” of a binary tree, such that
nodes at altitude 0 are leaves, nodes at altitude 1 are parents
of nodes at altitude 0, and so forth. This type is capable of
representing altitudes in trees containing up to 2^256 leaves.
A type representing the position of a leaf in a Merkle tree.