Struct bridgetree::BridgeTree

pub struct BridgeTree<H, C, const DEPTH: u8> { /* private fields */ }

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

Implementations

impl<H, C, const DEPTH: u8> BridgeTree<H, C, DEPTH>

pub fn new(max_checkpoints: usize) -> Self

Construct an empty BridgeTree value with the specified maximum number of checkpoints.

Panics if max_checkpoints < 1 because mark/rewind logic depends upon the presence of checkpoints to function.

pub fn prior_bridges(&self) -> &[MerkleBridge<H>]

Returns the prior bridges that make up this tree

pub fn current_bridge(&self) -> &Option<MerkleBridge<H>>

Returns the current bridge at the tip of this tree

pub fn marked_indices(&self) -> &BTreeMap<Position, usize>

Returns the map from leaf positions that have been marked to the index of the bridge whose tip is at that position in this tree’s list of bridges.

pub fn checkpoints(&self) -> &VecDeque<Checkpoint<C>>

Returns the checkpoints to which this tree may be rewound.

pub fn max_checkpoints(&self) -> usize

Returns the maximum number of checkpoints that will be maintained by the data structure. When this number of checkpoints is exceeded, the oldest checkpoints are discarded when creating new checkpoints.

pub fn frontier(&self) -> Option<&NonEmptyFrontier<H>>

Returns the bridge’s frontier.

impl<H: Hashable + Clone + Ord, C: Clone + Ord, const DEPTH: u8> BridgeTree<H, C, DEPTH>

pub fn from_frontier( max_checkpoints: usize, frontier: NonEmptyFrontier<H> ) -> Self

Construct a new BridgeTree that will start recording changes from the state of the specified frontier.

pub fn from_parts( prior_bridges: Vec<MerkleBridge<H>>, current_bridge: Option<MerkleBridge<H>>, saved: BTreeMap<Position, usize>, checkpoints: VecDeque<Checkpoint<C>>, max_checkpoints: usize ) -> Result<Self, BridgeTreeError>

Construct a new BridgeTree from its constituent parts, checking for internal consistency.

pub fn append(&mut self, value: H) -> bool

Appends a new value to the tree at the next available slot. Returns true if successful and false if the tree would exceed the maximum allowed depth.

pub fn root(&self, checkpoint_depth: usize) -> Option<H>

Obtains the root of the Merkle tree at the specified checkpoint depth by hashing against empty nodes up to the maximum height of the tree. Returns None if there are not enough checkpoints available to reach the requested checkpoint depth.

pub fn current_position(&self) -> Option<Position>

Returns the most recently appended leaf value.

pub fn current_leaf(&self) -> Option<&H>

Returns the most recently appended leaf value.

pub fn mark(&mut self) -> Option<Position>

Marks the current leaf as one for which we’re interested in producing a witness.

Returns an optional value containing the current position if successful or if the current value was already marked, or None if the tree is empty.

pub fn marked_positions(&self) -> BTreeSet<Position>

Return a set of all the positions for which we have marked.

pub fn get_marked_leaf(&self, position: Position) -> Option<&H>

Returns the leaf at the specified position if the tree can produce a witness for it.

pub fn remove_mark(&mut self, position: Position) -> bool

Marks the value at the specified position as a value we’re no longer interested in maintaining a mark for. Returns true if successful and false if we were already not maintaining a mark at this position.

pub fn checkpoint(&mut self, id: C) -> bool

Creates a new checkpoint for the current tree state, with the given identifier.

It is valid to have multiple checkpoints for the same tree state, and each rewind call will remove a single checkpoint. Successive checkpoint identifiers must always be provided in increasing order.

pub fn rewind(&mut self) -> bool

Rewinds the tree state to the previous checkpoint, and then removes that checkpoint record. If there are multiple checkpoints at a given tree state, the tree state will not be altered until all checkpoints at that tree state have been removed using rewind. This function return false and leave the tree unmodified if no checkpoints exist.

pub fn witness( &self, position: Position, checkpoint_depth: usize ) -> Result<Vec<H>, WitnessingError>

Obtains a witness for the value at the specified leaf position, as of the tree state at the given checkpoint depth. Returns None if there is no witness information for the requested position or if no checkpoint is available at the specified depth.

pub fn garbage_collect(&mut self)

Remove state from the tree that no longer needs to be maintained because it is associated with checkpoints or marks that have been removed from the tree at positions deeper than those reachable by calls to rewind.

Trait Implementations

impl<H: Clone, C: Clone, const DEPTH: u8> Clone for BridgeTree<H, C, DEPTH>

fn clone(&self) -> BridgeTree<H, C, DEPTH>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<H: Debug, C: Debug, const DEPTH: u8> Debug for BridgeTree<H, C, DEPTH>

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl<H: PartialEq, C: PartialEq, const DEPTH: u8> PartialEq<BridgeTree<H, C, DEPTH>> for BridgeTree<H, C, DEPTH>

fn eq(&self, other: &BridgeTree<H, C, DEPTH>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<H: Eq, C: Eq, const DEPTH: u8> Eq for BridgeTree<H, C, DEPTH>

impl<H, C, const DEPTH: u8> StructuralEq for BridgeTree<H, C, DEPTH>

impl<H, C, const DEPTH: u8> StructuralPartialEq for BridgeTree<H, C, DEPTH>