Struct Grafting 

pub struct Grafting<'a, H: CHasher> { /* private fields */ }

Hasher for computing leaf, node and root digests when the tree is being grafted onto another MMR.

Terminology

• Peak Tree: The MMR or Merkle tree that is being grafted.
• Base MMR: The MMR onto which we are grafting (cannot be a Merkle tree).

Grafting involves mapping the leaves of the peak tree to corresponding nodes in the base MMR. It allows for shorter inclusion proofs over the combined trees compared to treating them as independent.

One example use case is the crate::adb::current::Current authenticated database, where a MMR is built over a log of operations, and a merkle tree over a bitmap indicating the activity state of each operation. If we were to treat the two trees as independent, then an inclusion proof for an operation and its activity state would involve a full branch from each structure. When using grafting, we can trim the branch from the base MMR at the point it “flows” up into the peak tree, reducing the size of the proof by a constant factor up to 2.

For concreteness, let’s assume we have a base MMR over a log of 8 operations represented by the 8 leaves:

   Height
     3              14
                  /    \
                 /      \
                /        \
               /          \
     2        6            13
            /   \        /    \
     1     2     5      9     12
          / \   / \    / \   /  \
     0   0   1 3   4  7   8 10  11

Let’s assume each leaf in our peak tree corresponds to 4 leaves in the base MMR. The structure of the peak tree can be obtained by chopping off the bottom log2(4)=2 levels of the base MMR structure:

   Height
     1              2 (was 14)
                  /    \
                 /      \
                /        \
               /          \
     0        0 (was 6)    1 (was 13)

The inverse of this procedure provides our algorithm for mapping a peak tree leaf’s position to a base MMR node position: take the leaf’s position in the peak tree, map it to any of the corresponding leaves in the base MMR, then walk up the base MMR structure exactly the number of levels we removed.

In this example, leaf 0 in the peak tree corresponds to leaves [0,1,3,4] in the base MMR. Walking up two levels from any of these base MMR leaves produces node 6 of the base MMR, which is thus its grafting point. Leaf 1 in the peak tree corresponds to leaves [7,8,10,11] in the base MMR, yielding node 13 as its grafting point.

Implementations

impl<'a, H: CHasher> Grafting<'a, H>

pub fn new(hasher: &'a mut Standard<H>, height: u32) -> Self

pub fn standard(&mut self) -> &mut Standard<H>

Access the underlying Standard (non-grafting) hasher.

pub async fn load_grafted_digests( &mut self, leaves: &[u64], mmr: &impl Storage<H::Digest>, ) -> Result<(), Error>

Loads the grafted digests for the specified leaves into the internal map. Does not clear out any previously loaded digests. This method must be used to provide grafted digests for any leaf whose leaf_digest needs to be computed.

Warning

Panics if any of the grafted digests are missing from the MMR.

Trait Implementations

impl<H: CHasher> Hasher<H> for Grafting<'_, H>

fn leaf_digest(&mut self, pos: u64, element: &[u8]) -> H::Digest

Computes the digest of a leaf in the peak_tree of a grafted MMR.

Warning

Panics if the grafted_digest was not previously loaded for the leaf.

fn fork(&self) -> impl Hasher<H>

Fork the hasher to provide equivalent functionality in another thread. This is different than Clone::clone because the forked hasher need not be a deep copy, and may share non-mutable state with the hasher from which it was forked.

fn node_digest( &mut self, pos: u64, left_digest: &H::Digest, right_digest: &H::Digest, ) -> H::Digest

Computes the digest for a node given its position and the digests of its children.

fn root<'a>( &mut self, size: u64, peak_digests: impl Iterator<Item = &'a H::Digest>, ) -> H::Digest

Computes the root for an MMR given its size and an iterator over the digests of its peaks in decreasing order of height.

fn digest(&mut self, data: &[u8]) -> H::Digest

Compute the digest of a byte slice.

fn inner(&mut self) -> &mut H

Access the inner CHasher hasher.