Struct Tree

pub struct Tree { /* private fields */ }

A sparse merkle tree witnessing up to 65,536 epochs of up to 65,536 blocks of up to 65,536 [Commitment]s.

Implementations

impl Tree

pub fn new() -> Self

Create a new empty Tree for storing all commitments to the end of time.

pub fn root(&self) -> Root

Get the root hash of this Tree.

Internal hashing is performed lazily to prevent unnecessary intermediary hashes from being computed, so the first hash returned after a long sequence of insertions may take more time than subsequent calls.

Computed hashes are cached so that subsequent calls without further modification are very fast.

pub fn insert( &mut self, witness: Witness, commitment: StateCommitment, ) -> Result<Position, InsertError>

Add a new [Commitment] to the most recent block of the most recent epoch of this Tree.

If successful, returns the Position at which the commitment was inserted.

Errors

Returns InsertError if any of:

• the Tree is full,
• the current epoch is full, or
• the current block is full.

pub fn witness(&self, commitment: StateCommitment) -> Option<Proof>

Get a Proof of inclusion for the commitment at this index in the tree.

If the index is not witnessed in this tree, return None.

pub fn forget(&mut self, commitment: StateCommitment) -> bool

Forget about the witness for the given [Commitment].

Returns true if the commitment was previously witnessed (and now is forgotten), and false if it was not witnessed.

pub fn position_of(&self, commitment: StateCommitment) -> Option<Position>

Get the position in this Tree of the given [Commitment], if it is currently witnessed.

pub fn insert_block( &mut self, block: impl Into<Finalized>, ) -> Result<Root, InsertBlockError>

Add a new block all at once to the most recently inserted epoch of this Tree, returning the block root of the finalized block.

This can be used for two purposes:

1. to insert a block::Root into the tree as a stand-in for an entire un-witnessed block, or
2. to insert a block::Builder into the tree that was constructed separately.

The latter block::Builder API only accelerates tree construction when used in parallel, but the former block::Root insertion can be used to accelerate the construction of a tree even in a single thread, because if the root is already known, only one set of hashes need be performed, rather than performing hashing for each commitment in the block.

This function can be called on anything that implements Into<block::Finalized>, in particular:

• block::Root (treated as a finalized block with no witnessed commitments).
• block::Builder (the block is finalized as it is inserted), and of course
• block::Finalized.

Errors

Returns InsertBlockError containing the inserted block without adding it to the Tree if the Tree is full or the current epoch is full.

pub fn end_block(&mut self) -> Result<Root, InsertBlockError>

Explicitly mark the end of the current block in this tree, advancing the position to the next block, and returning the root of the block which was just finalized.

pub fn current_block_root(&self) -> Root

Get the root hash of the most recent block in the most recent epoch of this Tree.

pub fn insert_epoch( &mut self, epoch: impl Into<Finalized>, ) -> Result<Root, InsertEpochError>

Add a new epoch all at once to this Tree, returning the root of the finalized epoch which was inserted.

This can be used for two purposes:

1. to insert an epoch::Root into the tree as a stand-in for an entire un-witnessed block, or
2. to insert an epoch::Builder into the tree that was constructed separately.

The latter epoch::Builder API only accelerates tree construction when used in parallel, but the former epoch::Root insertion can be used to accelerate the construction of a tree even in a single thread, because if the root is already known, only one set of hashes need be performed, rather than performing hashing for each commitment in the epoch.

This function can be called on anything that implements Into<epoch::Finalized>, in particular:

• epoch::Root (treated as a finalized epoch with no witnessed commitments).
• epoch::Builder (the epoch is finalized as it is inserted), and of course
• epoch::Finalized.

Errors

Returns InsertEpochError containing the epoch without adding it to the Tree if the Tree is full.

pub fn end_epoch(&mut self) -> Result<Root, InsertEpochError>

Explicitly mark the end of the current epoch in this tree, advancing the position to the next epoch, and returning the root of the epoch which was just finalized.

pub fn current_epoch_root(&self) -> Root

Get the root hash of the most recent epoch in this Tree.

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

The position in this Tree at which the next [Commitment] would be inserted.

If the Tree is full, returns None.

The maximum capacity of a Tree is 281,474,976,710,656 = 65,536 epochs of 65,536 blocks of 65,536 [Commitment]s.

Note that forgetting a commitment does not decrease this; it only decreases the witnessed_count.

pub fn forgotten(&self) -> Forgotten

The count of how many commitments have been forgotten explicitly using forget, or implicitly by being overwritten by a subsequent insertion of the same commitment (this case is rare in practice).

This does not include commitments that were inserted using Witness::Forget, only those forgotten subsequent to their insertion.

pub fn witnessed_count(&self) -> usize

The number of [Commitment]s currently witnessed in this Tree.

Note that forgetting a commitment decreases this count, but does not decrease the position of the next inserted [Commitment].

pub fn is_empty(&self) -> bool

Check whether this Tree is empty.

pub fn commitments( &self, ) -> impl Iterator<Item = (Position, StateCommitment)> + Send + Sync + '_

Get an iterator over all commitments currently witnessed in the tree, ordered by position.

Unlike commitments_unordered, this guarantees that commitments will be returned in order, but it may be slower by a constant factor.

pub fn commitments_unordered( &self, ) -> impl Iterator<Item = (StateCommitment, Position)> + Send + Sync + '_

Get an iterator over all commitments currently witnessed in the tree.

Unlike commitments, this does not guarantee that commitments will be returned in order, but it may be faster by a constant factor.

pub fn structure(&self) -> Node<'_>

Get a dynamic representation of the internal structure of the tree, which can be traversed and inspected arbitrarily.

pub fn from_reader<R: Read>(reader: &mut R) -> Result<Tree, R::Error>

Deserialize a tree from a storage::Read of its contents, without checking for internal consistency.

This can be more convenient than Tree::load, since it is able to internally query the storage for the last position and forgotten count.

⚠️ WARNING: Do not deserialize trees you did not serialize yourself, or risk violating internal invariants.

pub fn to_writer<W: Write>(&self, writer: &mut W) -> Result<(), W::Error>

Serialize the tree incrementally from the last stored Position and Forgotten specified, into a storage::Write, performing only the operations necessary to serialize the changes to the tree.

This can be more convenient than using Tree::updates, because it is able to internally query the storage for the last position and forgotten count, and drive the storage operations itself.

pub async fn from_async_reader<R: AsyncRead>( reader: &mut R, ) -> Result<Tree, R::Error>

Deserialize a tree from a storage::AsyncRead of its contents, without checking for internal consistency.

This can be more convenient than Tree::load, since it is able to internally query the storage for the last position and forgotten count.

⚠️ WARNING: Do not deserialize trees you did not serialize yourself, or risk violating internal invariants.

pub async fn to_async_writer<W: AsyncWrite>( &self, writer: &mut W, ) -> Result<(), W::Error>

Serialize the tree incrementally from the last stored Position and Forgotten specified, into a storage::AsyncWrite, performing only the operations necessary to serialize the changes to the tree.

This can be more convenient than using Tree::updates, because it is able to internally query the storage for the last position and forgotten count, and drive the storage operations itself.

pub fn load( last_position: impl Into<StoredPosition>, last_forgotten: Forgotten, ) -> LoadCommitments

Deserialize a tree using externally driven iteration, without checking for internal consistency.

Reconstructing a Tree using this method requires stepping through a series of states, as follows:

1. Tree::load returns an object LoadCommitments which can be used to insert positioned commitments.
2. When all commitments have been inserted, call .load_hashes() to get an object LoadHashes.
3. LoadHashes can be used to insert positioned, heighted hashes.
4. Finally, call .finish() on the LoadHashes to get the Tree.

⚠️ WARNING: Do not deserialize trees you did not serialize yourself, or risk violating internal invariants. You must insert all the commitments and hashes corresponding to the stored tree, or the reconstructed tree will not match what was serialized, and further, it may have internal inconsistencies that will mean that the proofs it produces will not verify.

ℹ️ NOTE: You may prefer to use from_reader or from_async_reader, which drive the iteration over the underlying storage internally rather than requiring the caller to drive the iteration. Tree::load is predominanly useful in circumstances when this inversion of control does not make sense.

pub fn updates( &self, last_position: impl Into<StoredPosition>, last_forgotten: Forgotten, ) -> impl Iterator<Item = Update> + Send + Sync + '_

Serialize the tree incrementally from the last stored Position and Forgotten specified, into an iterator of storage::Updates.

This returns only the operations necessary to serialize the changes to the tree, synchronizing the in-memory representation with what is stored.

The iterator of updates may be .collect()ed into a storage::Updates, which is more compact in-memory than .collect()ing into a Vec<Update>.

ℹ️ NOTE: You may prefer to use to_writer or to_async_writer, which drive the operations on the underlying storage internally rather than requiring the caller to drive iteration. Tree::updates is predominantly useful in circumstances when this inversion of control does not make sense.

Trait Implementations

impl Clone for Tree

fn clone(&self) -> Tree

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Tree

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

Formats the value using the given formatter.

impl Default for Tree

fn default() -> Self

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for Tree

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl From<Top<Tier<Tier<Item>>>> for Tree

fn from(inner: Top<Tier<Tier<Item>>>) -> Self

Converts to this type from the input type.

impl PartialEq for Tree

fn eq(&self, other: &Tree) -> bool

Tests for self and other values to be equal, and is used by ==.

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

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

impl Serialize for Tree

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl Eq for Tree