Crate monotree[][src]

Expand description


Rust implementation of an optimized Sparse Merkle Tree.
This is a kind of binary-radix tree based on bitwise branching, currently, no nibble of bit. For now, branching unit is just a single bit, neither a 4-bit nor a byte nibble.


  • Very simple and lightweight, but fast and robust.
  • Fully featured Sparse Merkle Tree (SMT) as a storage
  • This includes: non-inclusion proof , as well as inclusion proof, and its verification.
  • Again, NOT verbose at all.

This library mostly relies on the Rust standard library only except for database APIs and hashers.
Currently, monotree supports these databases and hash functions following,
but is designed to be super easy to customize and add:

Databases include:

Hashers include:

Quick start

use monotree::{Monotree, Result};
use monotree::utils::random_hash;

fn example() -> Result<()> {
    // Init a monotree instance
    // by default, with 'HashMap' and 'Blake3' hash function
    let mut tree = Monotree::default();

    // It is natural the tree root initially has 'None'
    let root = None;

    // Prepare a random pair of key and leaf.
    // random_hashes() gives a fixed length of random array,
    // where Hash -> [u8; HASH_LEN], HASH_LEN = 32
    let key = random_hash();
    let leaf = random_hash();

    // Insert the entry (key, leaf) into tree, yielding a new root of tree
    let root = tree.insert(root.as_ref(), &key, &leaf)?;
    assert_ne!(root, None);

    // Get the leaf inserted just before. Note that the last root was used.
    let found = tree.get(root.as_ref(), &key)?;
    assert_eq!(found, Some(leaf));

    // Remove the entry
    let root = tree.remove(root.as_ref(), &key)?;

    // surely, the tree has nothing and the root back to 'None'
    assert_eq!(tree.get(root.as_ref(), &key)?, None);
    assert_eq!(root, None);

Generate/verify Merkle proof

monotree has compressed representation, but it fully retains the properties of the Sparse Merkle Tree (SMT).
Thus, non-inclusion proof is quite straightforward. Just go walk down the tree with a key (or a path) given. If we cannot successfully get a leaf, we can assure that the leaf is not a part of the tree.

The process of verifying inclusion of data (inclusion proof) is below:


use monotree::utils::random_hashes;
use monotree::hasher::Blake3;
use monotree::{verify_proof, Hasher, Monotree, Result};

fn example() -> Result<()> {
    // random pre-insertion for Merkle proof test
    let mut tree = Monotree::default();
    let root = None;
    let keys = random_hashes(500);
    let leaves = random_hashes(500);
    let root = tree.inserts(root.as_ref(), &keys, &leaves)?;

    // pick a random key from keys among inserted just before
    let key = keys[99];

    // generate the Merkle proof for the root and the key
    let proof = tree.get_merkle_proof(root.as_ref(), &key)?;

    // To verify the proof correctly, you need to provide a hasher matched
    // the default tree was initialized with `Blake3`
    let hasher = Blake3::new();

    // get a leaf matched with the key: where the Merkle proof starts off
    let leaf = leaves[99];

    // verify the Merkle proof using all those above
    let verified = verify_proof(&hasher, root.as_ref(), &leaf, proof.as_ref());
    assert_eq!(verified, true);


pub use self::bits::Bits;
pub use self::database::Database;
pub use self::hasher::Hasher;
pub use self::node::Cell;
pub use self::node::Node;
pub use self::node::Unit;
pub use self::tree::verify_proof;
pub use self::tree::Monotree;


A module for representing BitVec in terms of bytes slice.

A module for implementing database supporting monotree.

A module for implementing hash functions supporting monotree.

A module for defining Node used in monotree.

A module implementing monotree.

A module for implementing some helpful functions for monotree.


Convert elapsed time in nano second (u128) into appropriate format of time (String).

Convert bytes slice into hex string.

std::cmp::max() extension for use with multiple arguments.

std::cmp::min() extension for use with multiple arguments.

Simple benchmark tool for runtime measure of a code block.


An Error type defiend for handling general errors.


Size of fixed length byte-array from a Hasher. Equivalent to key length of monotree.

Type Definitions

A type representing length of Bits.

A type indicating database selected by default.

A type indicating hasher selected by default.

A type indicating fixed length byte-array. This has the length of HASH_LEN.

A type representing Merkle proof.

A Result type redefined for error handling. The same as std::result::Result<T, Errors>.