Expand description
shardtree
is a space-efficient fixed-depth Merkle tree structure that is densely
filled from the left. It supports:
- Out-of-order insertion: leaves and nodes may be inserted into the tree in arbitrary order. The structure will keep track of the right-most filled position as the frontier of the tree; any unfilled leaves to the left of this position are considered “missing”, while any unfilled leaves to the right of this position are considered “empty”.
- Witnessing: Individual leaves of the Merkle tree may be marked such that witnesses will be maintained for the marked leaves as additional nodes are inserted into the tree, but leaf and node data not specifically required to maintain these witnesses is not retained, for space efficiency.
- Checkpointing: the tree may be reset to a previously checkpointed state, up to a fixed number of checkpoints.
Due to its structure (described in the store
module), witnesses for marked leaves
can be advanced up to recent checkpoints or the latest state of the tree, without
having to insert each intermediate leaf individually. Instead, only the roots of all
complete shards between the one containing the marked leaf and the tree frontier need
to be inserted, along with the necessary nodes to build a path from the marked leaf to
the root of the shard containing it.
Modules§
Structs§
- Batch
Insertion Result - A type for the result of a batch insertion operation.
- Incomplete
At - A data structure describing the nature of a
Node::Nil
node in the tree that was introduced as the consequence of an insertion. - Located
Tree - A binary Merkle tree with its root at the given address.
- Retention
Flags - Flags storing the
Retention
state of a leaf. - Shard
Tree - A sparse binary Merkle tree of the specified depth, represented as an ordered collection of subtrees (shards) of a given maximum height.
- Tree
- An immutable binary tree with each of its nodes tagged with an annotation value.
Enums§
- Node
- A “pattern functor” for a single layer of a binary tree.
Type Aliases§
- Located
Prunable Tree - A
LocatedTree
annotated with Merkle hashes. - Prunable
Tree - A
Tree
annotated with Merkle hashes.