Module penumbra_tct::internal::frontier

Available on crate feature internal only.

Frontier things can be inserted into and updated, always representing the rightmost (most recently inserted) element of a tree.

In sketch: the structure of a single Tier contains eight Nodes, the bottom-most of which contains a Leaf. Alternatively, a tier can be a summarized Hash of what its contents would be, and contain nothing at all besides this hash.

At every level of a frontier::Tier, the rightmost child of a frontier::Node is a frontier::Node; all leftward siblings are complete::Nodes. When the child of a frontier::Node becomes entirely full (all its possible leaves are inserted), it is transformed into a complete::Node and appended to the list of complete siblings of its parent, thus shifting the frontier rightwards.

At any given time, the frontier is always fully materialized; no node within it is ever summarized as a hash. It is at the point when a frontier::Node becomes full and is then finalized into a complete::Node that it is pruned, if it contains no witnessed children.

At the tip of the frontier, however deeply nested (perhaps within multiple Tiers), there is a single Item, which is either a Commitment or a hash of one. Commitments can be inserted either with the intent to remember them, or with the intent to immediately forget them; this determines whether the Item is a commitment or merely its hash.

Structs

• Full
  The result of Frontier::insert_owned when the Frontier is full.
• Item
  The hash of the most-recently-inserted item, stored at the tip of the frontier.
• Leaf
  The frontier (rightmost) leaf in a frontier of a tree.
• Node
  A frontier of a node in a tree, into which items can be inserted.
• Tier
  A frontier of a tier of the tiered commitment tree, being an 8-deep quad-tree of items.
• Top
  The frontier of the top level of some part of the commitment tree, which may be empty, but may not be finalized or hashed.

Enums

• Insert
  Either an item or just its hash, to be used when inserting into a tree.
• InsertMut
  The mutable-reference version of an Insert<T>, distinct from Insert<&mut T> because it also allows mutation of the contained hash.
• TrackForgotten
  Whether or not to track forgotten elements of the tree.

Traits

• Focus
  A type which can be the focus of an Frontier tree: it can be finalized to make a Complete tree.
• Forget
  Forget about the authentication path to a given index.
• Frontier
  A frontier of a tree supporting the insertion of new elements and the updating of the most-recently-inserted element.
• GetPosition
  Get the position of the next insertion into the tree.