Struct bridgetree::BridgeTree

source ·

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

Expand description

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§

source §

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

source

pub fn new(max_checkpoints: usize) -> Self

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

source

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

Returns the prior bridges that make up this tree

source

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

Returns the current bridge at the tip of this tree

source

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.

source

pub fn checkpoints(&self) -> &[Checkpoint]

Returns the checkpoints to which this tree may be rewound.

source

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.

source

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

Returns the bridge’s frontier.

source §

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

source

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.

source

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

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

source

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.

source

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.

Examples found in repository ?

src/lib.rs (line 1093)

    fn witness_inner(&self, position: Position, as_of_root: &H) -> Result<Vec<H>, WitnessingError> {
        #[derive(Debug)]
        enum AuthBase<'a> {
            Current,
            Checkpoint(usize, &'a Checkpoint),
            NotFound,
        }

        let max_alt = Level::from(DEPTH);

        // Find the earliest checkpoint having a matching root, or the current
        // root if it matches and there is no earlier matching checkpoint.
        let auth_base = self
            .checkpoints
            .iter()
            .enumerate()
            .rev()
            .take_while(|(_, c)| c.position(&self.prior_bridges) >= Some(position))
            .filter(|(_, c)| &c.root(&self.prior_bridges, max_alt) == as_of_root)
            .last()
            .map(|(i, c)| AuthBase::Checkpoint(i, c))
            .unwrap_or_else(|| {
                if self.root(0).as_ref() == Some(as_of_root) {
                    AuthBase::Current
                } else {
                    AuthBase::NotFound
                }
            });

        let saved_idx = self
            .saved
            .get(&position)
            .or_else(|| {
                if let AuthBase::Checkpoint(i, _) = auth_base {
                    // The saved position might have been forgotten since the checkpoint,
                    // so look for it in each of the subsequent checkpoints' forgotten
                    // items.
                    self.checkpoints[i..].iter().find_map(|c| {
                        // restore the forgotten position, if that position was not also marked
                        // in the same checkpoint
                        c.forgotten
                            .get(&position)
                            .filter(|_| !c.marked.contains(&position))
                    })
                } else {
                    None
                }
            })
            .ok_or(WitnessingError::PositionNotMarked(position))?;

        let prior_frontier = &self.prior_bridges[*saved_idx].frontier;

        // Fuse the following bridges to obtain a bridge that has all
        // of the data to the right of the selected value in the tree,
        // up to the specified checkpoint depth.
        let fuse_from = saved_idx + 1;
        let successor = match auth_base {
            AuthBase::Current => {
                // fuse all the way up to the current tip
                MerkleBridge::fuse_all(
                    self.prior_bridges[fuse_from..]
                        .iter()
                        .chain(&self.current_bridge),
                )
                .map(|fused| fused.unwrap()) // safe as the iterator being fused is nonempty
                .map_err(WitnessingError::BridgeFusionError)
            }
            AuthBase::Checkpoint(_, checkpoint) if fuse_from < checkpoint.bridges_len => {
                // fuse from the provided checkpoint
                MerkleBridge::fuse_all(self.prior_bridges[fuse_from..checkpoint.bridges_len].iter())
                    .map(|fused| fused.unwrap()) // safe as the iterator being fused is nonempty
                    .map_err(WitnessingError::BridgeFusionError)
            }
            AuthBase::Checkpoint(_, checkpoint) if fuse_from == checkpoint.bridges_len => {
                // The successor bridge should just be the empty successor to the
                // checkpointed bridge.
                if checkpoint.bridges_len > 0 {
                    Ok(self.prior_bridges[checkpoint.bridges_len - 1].successor(false))
                } else {
                    Err(WitnessingError::CheckpointInvalid)
                }
            }
            AuthBase::Checkpoint(_, checkpoint) => {
                // if the saved index is after the checkpoint, we can't generate
                // an auth path
                Err(WitnessingError::CheckpointTooDeep(
                    fuse_from - checkpoint.bridges_len,
                ))
            }
            AuthBase::NotFound => {
                // we didn't find any suitable auth base
                Err(WitnessingError::AuthBaseNotFound)
            }
        }?;

        successor.witness(DEPTH, prior_frontier)
    }

source

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

Returns the most recently appended leaf value.

source

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

Returns the most recently appended leaf value.

source

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.

Examples found in repository ?

src/lib.rs (line 1054)

    pub fn rewind(&mut self) -> bool {
        match self.checkpoints.pop() {
            Some(mut c) => {
                // drop marked values at and above the checkpoint height;
                // we will re-mark if necessary.
                self.saved.append(&mut c.forgotten);
                self.saved.retain(|_, i| *i + 1 < c.bridges_len);
                self.prior_bridges.truncate(c.bridges_len);
                self.current_bridge = self.prior_bridges.last().map(|b| b.successor(c.is_marked));
                if c.is_marked {
                    self.mark();
                }
                true
            }
            None => false,
        }
    }

source

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

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

source

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.

Examples found in repository ?

src/lib.rs (line 1012)

    pub fn checkpoint(&mut self) {
        match self.current_bridge.take() {
            Some(cur_b) => {
                let is_marked = self.get_marked_leaf(cur_b.position()).is_some();

                // Do not create a duplicate bridge
                if self
                    .prior_bridges
                    .last()
                    .map_or(false, |pb| pb.position() == cur_b.position())
                {
                    self.current_bridge = Some(cur_b);
                } else {
                    self.current_bridge = Some(cur_b.successor(false));
                    self.prior_bridges.push(cur_b);
                }

                self.checkpoints
                    .push(Checkpoint::at_length(self.prior_bridges.len(), is_marked));
            }
            None => {
                self.checkpoints.push(Checkpoint::at_length(0, false));
            }
        }

        if self.checkpoints.len() > self.max_checkpoints {
            self.drop_oldest_checkpoint();
        }
    }

source

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.

source

pub fn checkpoint(&mut self)

Creates a new checkpoint for the current tree state. It is valid to have multiple checkpoints for the same tree state, and each rewind call will remove a single checkpoint.

source

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.

source

pub fn witness(&self, position: Position, as_of_root: &H) -> Option<Vec<H>>

Obtains a witness to the value at the specified position, as of the tree state corresponding to the given root. Returns None if there is no available witness to that position or if the root does not correspond to a checkpointed root of the tree.

source

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.