Merkleberg

Merkleberg is a library providing asynchronous Merkle Mountain Range data structures.

Features

• Simple bagged peaks MMR and accumulator based MMRIVER (based on the IETF draft) with consistency proofs
• Fully asynchronous API without reliance on any specific runtime
• Fully extensible with custom hashing via Merge trait and custom storage via other traits
• Protects against second preimage attacks by default
• Compatible with no_std, just disable the std feature

Core Concepts

MMR

An MMR is a series of complete binary trees ("mountains") stored in post-order traversal:

# An 11 leaves MMR

          14
       /       \
     6          13
   /   \       /   \
  2     5     9     12     17
 / \   /  \  / \   /  \   /  \
0   1 3   4 7   8 10  11 15  16 18

Nodes are indexed by insertion order. To add a leaf:

1. Append leaf at next position
2. If position has left sibling at same height, merge them into parent node
3. Repeat step 2 until no more merging possible

use merkleberg::{MMR, DigestMerge, util::MemStore, Merge};
use sha2::Sha256;

#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Create MMR with SHA-256 hashing
    let store = MemStore::default();
    let mut mmr: MMR<DigestMerge<Sha256>, _> = MMR::new(0, store);

    // Add elements
    let pos0 = mmr.push(b"first").await?;
    let pos1 = mmr.push(b"second").await?;

    // Persist to storage
    mmr.commit().await?;

    // Compute Merkle root
    let root = mmr.get_root().await?;

    // Generate inclusion proof
    let proof = mmr.gen_proof(vec![pos0]).await?;

    // Verify proof
    let leaf_hash = DigestMerge::<Sha256>::leaf_hash(b"first")?;
    assert!(proof.verify(root, vec![(pos0, leaf_hash)])?);

    Ok(())
}

MMRIVER

MMRIVER (Merkle Mountain Range for Immediately Verifiable and Replicable Commitments) is an experimental draft IETF RFC. It differs from regular MMR by storing a list (i.e., the accumulator) of peaks instead of bagging from right to left into a single hash.

This approach allows for consistency proofs alongside the existing inclusion proofs already supported by MMR, where any new accumulator can be verified against an existing old accumulator (also known as the Reyzin-Yakoubov property), which is useful for blockchain header chains, verifiable log replication, state evolution proofs, etc.

use merkleberg::{MMRIVER, DigestMerge, util::MemStore, Merge};
use sha2::Sha256;

#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error>> {
    let store = MemStore::default();
    let mut mmriver: MMRIVER<DigestMerge<Sha256>, _> = MMRIVER::new(0, store);

    // Add elements
    for i in 0u64..10 {
        mmriver.push(&i.to_be_bytes()).await?;
    }
    mmriver.commit().await?;

    // Get accumulator (list of peaks) instead of single root
    let accumulator = mmriver.get_accumulator().await?;

    // Generate inclusion proof
    let proof = mmriver.gen_inclusion_proof(0).await?;
    let leaf_hash = DigestMerge::<Sha256>::leaf_hash(&0u64.to_be_bytes())?;
    assert!(proof.verify(leaf_hash, &accumulator)?);

    // Generate consistency proof between tree states
    let old_size = mmriver.mmr_size();
    for i in 10u64..20 {
        mmriver.push(&i.to_be_bytes()).await?;
    }
    mmriver.commit().await?;

    let consistency_proof = mmriver.gen_consistency_proof(old_size).await?;
    let new_accumulator = mmriver.get_accumulator().await?;
    assert!(consistency_proof.verify(accumulator, &new_accumulator)?);

    Ok(())
}

The Merge Trait

Merkleberg does not specify any hashing logic internally. Hashing logic is specified by implementing the Merge trait.

use merkleberg::Merge;
use std::convert::Infallible;

struct MyMerge;

impl Merge for MyMerge {
    type Item = [u8; 32];  // Hash output type
    type Error = Infallible;

    fn leaf_hash(data: &[u8]) -> Result<Self::Item, Self::Error> {
        // Hash leaf with domain prefix (e.g., 0x00)
    }

    fn merge_pos(pos: u64, left: &Self::Item, right: &Self::Item)
        -> Result<Self::Item, Self::Error> {
        // Hash node with position prefix for domain separation
    }
}

However, a DigestMerge generic type is provided for convenience which provides a simple implementation without specifying a hashing algorithm. Any algorithm implementing the Digest trait can be supplied to it. Common hashing algorithms can be found as a part of the RustCrypto project.

By default, DigestMerge uses domain prefixes to prevent second preimage attacks:

• Leaves: prefixed with 0x00
• Nodes: prefixed with 0x01

This ensures a leaf hash cannot be crafted to match a node hash.

Should you choose to opt-out of this much recommended protection, the unsafe-digest feature may be enabled to make use of DigestMergeUnsafe instead.

Custom Storage Backends

Implement MMRStoreReadOps and MMRStoreWriteOps:

use merkleberg::{MMRStoreReadOps, MMRStoreWriteOps};

struct MyStore {
    // Your storage backend (database, file, memory, etc.)
}

impl<T: Clone + Send + Sync> MMRStoreReadOps<T> for MyStore {
    type Error = MyError;

    async fn get_elem(&self, pos: u64) -> Result<Option<T>, Self::Error>;
    async fn get_elems(&self, positions: impl Iterator<Item = u64> + Send)
        -> Result<Vec<Option<T>>, Self::Error>;
}

impl<T: Send + Sync> MMRStoreWriteOps<T> for MyStore {
    type Error = MyError;

    async fn append(&mut self, pos: u64, elems: Vec<T>) -> Result<(), Self::Error>;
}

For convenience, a lightweight MemStore backend is provided by default, which stores trees in memory. Storage backends also support batching via MMRBatch; multiple items can be pushed before committing and actually updating the underlying structure.

Error Handling

Errors use trait objects for flexibility:

type UserError = Box<dyn Error + Send + Sync + 'static>;

pub enum Error {
    StoreError(UserError),
    MergeError(UserError),
    // ...
}

Custom store / merge errors need only implement Error + Send + Sync + 'static.

Serde Support

Enabling the serde feature makes all proof types implement Serialize and Deserialize:

use merkleberg::mmriver::InclusionProof;
use serde_json;

// Serialize proof to JSON
let proof = mmriver.gen_inclusion_proof(0).await?;
let json = serde_json::to_string(&proof)?;

// Deserialize from JSON
let decoded: InclusionProof<DigestMerge<Sha256>> = serde_json::from_str(&json)?;

[!NOTE] The Item type of the Merge implementation being used must also implement Serialize and Deserialize for the proofs to implement them. The provided merge implementations already do so.

References

• OpenTimestamps MMR spec
• Grin documentation
• Nervos implementation
• IETF MMRIVER Draft - Merkle Mountain Range for Immediately Verifiable and Replicable Commitments
• Wikipedia: Merkle tree

License

This project is dual-licensed under:

• MIT License (original)
• Mozilla Public License 2.0 - MMRIVER and other modifications made by @pesde-pkg

See LICENSE for full details.