Crate monotree[−][src]
Expand description
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
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
.
Macros
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.
Structs
An Error
type defiend for handling general errors.
Constants
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>
.