Module internal

Available on crate feature internal only.

The internal implementation of the tree, exposed here for documentation.

This module and its submodules should not be expected to follow semantic versioning.

Structure of Implementation

The tiered commitment tree is not accessed directly as a tree; rather, the Tree, epoch::Builder, epoch::Finalized, block::Builder, and block::Finalized structs from the top level of the crate contain a tree together with a hashmap which maps commitments to their corresponding index within the tree. This internal module and all its submodules concern themselves solely with the implementation of the tree itself, wherein commitments and their authentication paths are accessed by index. The surrounding pieces of the crate make use of the internal-facing API exposed by this module to implement an external API specific to the three-tiered tree/epoch/block commitment tree required by Penumbra.

The tiered commitment tree has a very specific structure, and in this implementation we make strong Rust’s type system to enforce that structure. In particular, we ensure that internal nodes are non-empty, and that leaves occur only at the bottom-most level of the tree. A consequence of this is that it is unrepresentable to build a tree which fails to be pruned of internal nodes holding no witnessed leaves, or whose leaves are of mismatched depth. A lesser benefit of this design is that recursive methods on trees can be monomorphized and therefore potentially inlined to the height of tree they are called upon, avoiding ever performing runtime checks about the tree structure (there no need to check whether a particular part of the tree is a leaf, internal node, etc., because this is statically known).

This structural guarantee is achieved by defining these tree structures as nested generic types, and defining their methods as recursive trait implementations (rather than as inductive non-generic enumeration types with recursive methods). These traits are all defined in interface, but they are re-exported from frontier and complete as relevant.

Tiers of Nodes of Leaves of Items: Frontier and Complete

The primary exports of this module is the type frontier::Tier. It is in terms of this type that the Tree and builder structs are defined: a Tree is a Top<Tier<Tier<Item>>>, an epoch is a Top<Tier<Item>>, and a Block is a Top<Item> (each with a managed index of commitments alongside).

Internally, a Tier is a quadtree where every internal node is annotated with the hash of its children, into which leaves (all at depth 8) are inserted in left to right order. The “frontier” represents the path from the root to the rightmost leaf, at every level containing any leftward siblings of a given frontier node, each of which is a complete tree which stores the finalized bulk of the items inserted into the tree. As new leaves are created, the frontier zig-zags rightwards, pushing finalized portions of itself into the leftward complete tree.

All Tiers must contain at least one child, and may be either unfinalized or finalized; a Top is like a tier, but it may be empty, and may not be finalized. Stacking a Top on top of Tiers allows there to be a canonical representation for empty trees, and prevents the illegal state of a finalized top-level tree.

As described above, a variety of recursively defined traits are used to define the behavior of trees. The Frontier trait defines the operations possible on a frontier of a tree, while the Focus trait defines how to operate over the tip of a frontier, and the Forget trait defines how to remove witnessed leaves from a frontier.

While the frontier changes on every inserted leaf, within the complete portion of the tree the only changes that occur are when leaves are forgotten and their containing nodes pruned. As a result, the traits exposed by the complete module are merely Complete, which is a marker trait used to ensure that every Frontier type is paired with a unique corresponding type of complete tree, and the ForgetOwned trait, which defines an equivalent to frontier::Forget that is applicable to the by-value usage pattern of complete trees.

Modules

• complete
  Complete things are sparse representations of only the data that was inserted using Witness::Keep, with the data that was inserted using Witness::Forget being pruned eagerly.
• frontier
  Frontier things can be inserted into and updated, always representing the rightmost (most recently inserted) element of a tree.
• hash
  The core Hash type, which is used internally to represent hashes, the GetHash trait for computing and caching hashes of things, and the CachedHash type, which is used internally for lazy evaluation of hashes.
• height
  Type level machinery used to statically determine the height of a tree, to ensure the correct domain separator is used when hashing at any height.
• interface
  This module contains trait definitions for the entire interface of the internal tree. All of them are exported from either frontier or complete, but they are also exported from here for ease of reading.
• path
  Authentication paths into the tree, generically for trees of any height.
• proof
  Transparent merkle inclusion proofs defined generically for trees of any height.
• three
  A wrapper around Vec for vectors whose length is at most 3 elements.