[−][src]Crate monotree

Monotree

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.

Features

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);
    Ok(())
}

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:

Example

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);
    Ok(())
}

Re-exports

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;

Modules

bits	A module for representing `BitVec` in terms of bytes slice.
database	A module for implementing database supporting `monotree`.
hasher	A module for implementing hash functions supporting `monotree`.
node	A module for defining `Node` used in `monotree`.
tree	A module implementing `monotree`.
utils	A module for implementing some helpful functions for `monotree`.

Macros

fmtime	Convert elapsed time in nano second (`u128`) into appropriate format of time (`String`).
hex	Convert `bytes` slice into `hex` string.
max	std::cmp::max() extension for use with multiple arguments.
min	std::cmp::min() extension for use with multiple arguments.
perf	Simple benchmark tool for runtime measure of a code block.

BitsLen	A type representing length of `Bits`.
DefaultDatabase	A type indicating database selected by default.
DefaultHasher	A type indicating hasher selected by default.
Hash	A type indicating fixed length byte-array. This has the length of `HASH_LEN`.
Proof	A type representing Merkle proof.
Result	A `Result` type redefined for error handling. The same as `std::result::Result<T, Errors>`.