Struct LazyMerkleTree 

pub struct LazyMerkleTree<H: Hasher, V: VersionMarker = Derived> { /* private fields */ }

A storage-optimized merkle tree.

It has a certain linear-buffer represented prefix subtree and the rest of the tree is represented using lazy, pointer-based structures. This makes it possible to hold even large trees in memory, assuming only a relatively small subset is ever modified.

It exposes an immutable API, so that multiple versions can be kept in memory while reusing as much structure as possible.

The update method also allows the specification of a mutability hint, which can be used to vastly improve storage characteristics, but also requires the caller to ensure certain additional invariants hold. See LazyMerkleTree::update_with_mutation for details.

Implementations

impl<H, Version> LazyMerkleTree<H, Version>

where H: Hasher, <H as Hasher>::Hash: Hash, Version: VersionMarker,

pub fn new(depth: usize, empty_value: H::Hash) -> LazyMerkleTree<H, Canonical>

Creates a new, fully lazy (without any dense prefix) tree.

pub fn new_with_dense_prefix( depth: usize, prefix_depth: usize, empty_value: &H::Hash, ) -> LazyMerkleTree<H, Canonical>

Creates a new tree with a dense prefix of the given depth.

pub fn new_with_dense_prefix_with_initial_values( depth: usize, prefix_depth: usize, empty_value: &H::Hash, initial_values: &[H::Hash], ) -> LazyMerkleTree<H, Canonical>

Creates a new tree with a dense prefix of the given depth, and with initial leaves populated from the given slice.

pub fn new_mmapped_with_dense_prefix_with_init_values( depth: usize, prefix_depth: usize, empty_value: &H::Hash, initial_values: &[H::Hash], file_path: &str, ) -> Result<LazyMerkleTree<H, Canonical>, DenseMMapError>

Creates a new memory mapped file specified by path and creates a tree with dense prefix of the given depth with initial values

pub fn attempt_dense_mmap_restore( depth: usize, prefix_depth: usize, empty_leaf: &H::Hash, file_path: &str, ) -> Result<LazyMerkleTree<H, Canonical>, DenseMMapError>

Attempts to restore previous tree state from memory mapped file

Errors

• dense mmap tree restore failed

pub const fn depth(&self) -> usize

Returns the depth of the tree.

pub fn root(&self) -> H::Hash

Returns the root of the tree.

pub fn update( &self, index: usize, value: &H::Hash, ) -> LazyMerkleTree<H, Derived>

Sets the value at the given index to the given value. This is fully immutable, returning a new tree and leaving the old one unchanged. Reuses as much memory as possible, allocating only depth nodes.

pub fn proof(&self, index: usize) -> InclusionProof<H>

Returns the Merkle proof for the given index.

pub fn verify(&self, value: H::Hash, proof: &InclusionProof<H>) -> bool

Verifies the given proof for the given value.

pub fn get_leaf(&self, index: usize) -> H::Hash

Returns the value at the given index.

pub fn leaves(&self) -> impl Iterator<Item = H::Hash> + '_

Returns an iterator over all leaves.

impl<H> LazyMerkleTree<H, Canonical>

where H: Hasher, <H as Hasher>::Hash: Hash,

pub fn update_with_mutation(self, index: usize, value: &H::Hash) -> Self

Sets the value at the given index to the given value. This is a mutable operation, that will modify any dense subtrees in place.

This has potential consequences for the soundness of the whole structure: it has the potential to invalidate some trees that share nodes with this one, so if many versions are kept at once, special care must be taken when calling this. The only trees that are guaranteed to still be valid after this operation, are those that already specify the same value at the given index. For example, if a linear history of updates is kept in memory, this operation is a good way to “flatten” updates into the oldest kept version.

This operation is useful for storage optimizations, as it avoids allocating any new memory in dense subtrees.

pub fn derived(&self) -> LazyMerkleTree<H, Derived>

Gives a Derived version of this tree. Useful for initializing versioned trees.

Trait Implementations

impl<H> Clone for LazyMerkleTree<H, Derived>

where H: Hasher, <H as Hasher>::Hash: Hash,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.