Struct bridgetree::MerkleBridge

pub struct MerkleBridge<H> { /* private fields */ }

The information required to “update” witnesses from one state of a Merkle tree to another.

The witness for a particular leaf of a Merkle tree consists of the siblings of that leaf, plus the siblings of the parents of that leaf in a path to the root of the tree. When considering a Merkle tree where leaves are appended to the tree in a linear fashion (rather than being inserted at arbitrary positions), we often wish to produce a witness for a leaf that was appended to the tree at some point in the past. A MerkleBridge from one position in the tree to another position in the tree contains the minimal amount of information necessary to produce a witness for the leaf at the former position, given that leaves have been subsequently appended to reach the current position.

MerkleBridge values have a semigroup, such that the sum (fused) value of two successive bridges, along with a NonEmptyFrontier with its tip at the prior position of the first bridge being fused, can be used to produce a witness for the leaf at the tip of the prior frontier.

Implementations

impl<H> MerkleBridge<H>

pub fn new(value: H) -> Self

Construct a new Merkle bridge containing only the specified leaf.

pub fn from_parts( prior_position: Option<Position>, tracking: BTreeSet<Address>, ommers: BTreeMap<Address, H>, frontier: NonEmptyFrontier<H> ) -> Self

Construct a new Merkle bridge from its constituent parts.

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

Returns the position of the final leaf in the frontier of the bridge that this bridge is the successor of, or None if this is the first bridge in a tree.

pub fn position(&self) -> Position

Returns the position of the most recently appended leaf.

pub fn tracking(&self) -> &BTreeSet<Address>

Returns the set of internal node addresses that we’re searching for the ommers for.

pub fn ommers(&self) -> &BTreeMap<Address, H>

Returns the set of internal node addresses that we’re searching for the ommers for.

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

Returns the non-empty frontier of this Merkle bridge.

pub fn current_leaf(&self) -> &H

Returns the value of the most recently appended leaf.

pub fn check_continuity(&self, next: &Self) -> Result<(), ContinuityError>

Checks whether this bridge is a valid successor for the specified bridge.

pub fn position_range(&self) -> Range<Position>

Returns the range of positions observed by this bridge.

impl<'a, H: Hashable + Clone + Ord + 'a> MerkleBridge<H>

pub fn successor(&self, track_current_leaf: bool) -> Self

Constructs a new bridge to follow this one. If mark_current_leaf is true, the successor will track the information necessary to create a witness for the leaf most recently appended to this bridge’s frontier.

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

Advances this bridge’s frontier by appending the specified node, and updates any auth path ommers being tracked if necessary.

Trait Implementations

impl<H: Clone> Clone for MerkleBridge<H>

fn clone(&self) -> MerkleBridge<H>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<H: Debug> Debug for MerkleBridge<H>

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

Formats the value using the given formatter.

impl<H: PartialEq> PartialEq<MerkleBridge<H>> for MerkleBridge<H>

fn eq(&self, other: &MerkleBridge<H>) -> 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> Eq for MerkleBridge<H>

impl<H> StructuralEq for MerkleBridge<H>

impl<H> StructuralPartialEq for MerkleBridge<H>