Struct MerkleTree 

pub struct MerkleTree<Db, M>
where
    M: MerkleHash,
{ /* private fields */ }

Implements an RFC 6962 compatible merkle tree over an in-memory data store which maps preimages to hashes.

Implementations

impl<Db, M> MerkleTree<Db, M>

where Db: PreimageDb<M::Output>, M: MerkleHash + Default,

pub fn new() -> Self

Constructs an empty merkle tree with a default hasher

impl<Db, M> MerkleTree<Db, M>

where Db: PreimageDb<M::Output>, M: MerkleHash,

pub fn with_hasher(hasher: M) -> Self

Constructs an empty merkle tree with the given hasher

pub fn push_raw_leaf(&mut self, raw_leaf: &[u8])

Appends the given leaf to the tree

pub fn push_leaf_with_hash(&mut self, leaf_with_hash: LeafWithHash<M>)

Appends a pre-hashed leaf to the tree

pub fn root(&mut self) -> M::Output

Returns the root of the tree, computing it if necessary. Repeated queries return a cached result.

pub fn get_leaves(&self, range: Range<usize>) -> Vec<Vec<u8>>

Returns the requested range of leaves

pub fn leaves(&self) -> &[LeafWithHash<M>]

Returns all leaves in the tree

pub fn check_range_proof( &self, root: &M::Output, leaves: &[M::Output], proof: &[M::Output], leaves_start_idx: usize, ) -> Result<(), RangeProofError>

Checks a given range proof

pub fn build_range_proof(&mut self, leaf_range: Range<usize>) -> Proof<M>

Creates a range proof providing the sibling hashes required to show that a set of values really does occur in the merkle tree at some half-open range of indices. Intermediate hashes are identified by an in-order traversal and are returned in that same order. Panics if the range to prove is larger than the tree’s leaf array.

Example: consider the following merkle tree with leaves [C, D, E, F]

         root
       /      \
      A        B
     / \      /  \
    C   D    E    F

A range proof of build_range_proof(1..3) would return the vector [C, F], since those two hashes, together with the two leaves in the range, are sufficient to reconstruct the tree

pub fn narrow_range_proof( &mut self, left_extra_leaves: &[M::Output], narrowed_leaf_range: Range<usize>, right_extra_leaves: &[M::Output], current_proof: &mut &[M::Output], leaves_start_idx: usize, ) -> Result<Proof<M>, RangeProofError>

Narrows the proof range: uses an existing proof to create a new proof for a subrange of the original proof’s range.

Effectively, we have two ranges of leaves provided, which can make the range narrower from the left or the right respectively (alongside the original proof). The high level logic of building a proof out of that is very similar to the normal build_range_proof logic, with two exceptions: we don’t have the root (or most inner nodes), so we recurse based on the leaves and calculate the intermediate hashes we need as we go; and we don’t have all the leaves either, so the partial_tree_subroot_inner function calculates inner node roots using information from both the original proof and the leaves we do have.

Example: consider the following merkle tree with eight leaves:

                   root
               /          \
           A                  B
        /    \             /    \
      C        D         E        F
     / \      /  \      / \      /  \
    G   H    I    J    K   L    M    N

A proof of [H, I, J, K] will contain nodes [G, L, F]. If we want to turn that into a proof of [J], that would need nodes [I, C, B]. We recursively subdivide the total leaf range to find the subtrees that don’t overlap the final desired range, just as in the normal build_range_proof - in this case, [G, H], [I], and [K, L, M, N]. We can then combine the information from the proof and the {left|right}_extra_leaves to calculate the subroots of each of those trees - for example, B = hash(E | F), where F is from the original proof, and E is calculated using K (from right_extra_leaves) and L (from the original proof). Thus we arrive at the new proof for the narrower range.

pub fn get_range_with_proof( &mut self, leaf_range: Range<usize>, ) -> (Vec<Vec<u8>>, Proof<M>)

Fetches the requested range of leaves, along with a proof of correctness.

pub fn get_index_with_proof(&mut self, idx: usize) -> (Vec<u8>, Proof<M>)

Fetches the leaf at the given index, along with a proof of inclusion.

Trait Implementations

impl<Db: PreimageDb<<M as MerkleHash>::Output>, M: MerkleHash + Default> Default for MerkleTree<Db, M>

fn default() -> Self

Returns the “default value” for a type.