Crate monotree

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

Refer to examples/basic.rs for a complete working example.

Regarding non-inclusion proof and inclusion proof, See Merkle proof section in More Examples below.

§Initialize

// If no database or hash function is specified,
// the tree defaults to using a HashMap and the Blake3 hash function.
let mut tree = Monotree::default();

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

§Insert

// Generate a random key and leaf pair.
// random_hash() creates a fixed-length random array of 32 bytes.
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);

§Retrieve

// Retrieve 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

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

// The tree is empty now and the root back to 'None'
assert_eq!(tree.get(root.as_ref(), &key)?, None);
assert_eq!(root, None);

§Batch: Atomic Transaction

Instead of executing each operation one by one, write them in a batch and then commit them all at once. One can do the same thing above using batch operation for performance gain and atomicity. In short,

prepare → many of {insert, get, remove} → commit

§Prepare Transaction

// initialize an empty batch: prepare transaction
tree.prepare();

§Freely `insert`, `get`, and `remove`

// Insert the entry (key, leaf) within the batch
let root = tree.insert(root.as_ref(), &key, &leaf)?;
assert_ne!(root, None);

// Retrieve the inserted leaf using the batch root
let found = tree.get(root.as_ref(), &key)?;
assert_eq!(found, Some(leaf));

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

// Ensure the entry was removed within the batch
assert_eq!(tree.get(root.as_ref(), &key)?, None);

§Commit Transaction

// Commit the batch operations: commit transaction
tree.commit();

// Verify that the final root is `None` after commit
assert_eq!(tree.get(root.as_ref(), &key)?, None);

§Initialize with a specific database and hash function

// Init a monotree instance with a database and hash function
//
// Monotree::<DATABASE, HASHER>::new(DB_PATH)
//      where DATABASE = {MemoryDB, RocksDB, Sled}
//            HASHER = {Blake3, Blake2s, Blake2b, Sha2, Sha3}
let mut tree = Monotree::<RocksDB, Blake2b>::new("/tmp/monotree");

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

§Intrinsic batch processing: `inserts` and `removes`.

As shown in Quick Start above, operations executed between tree.prepare() and tree.commit() can be viewed as a single batch operation. By default, they are automatically cached and are written together in a batch unit.

However, if you need to repeat the same operation, such as insert or remove, you can easily optimize performance by using inserts and removes.

inserts() is significantly faster than insert() for the following reason:

Batch writes
Sorting keys prior to insertion
In-memory caching

// Prepare 100 random pairs of key and leaf.
// random_hash(SIZE) creates a vector of fixed-length random array of 32 bytes.
let keys = random_hashes(100);
let leaves = random_hashes(100);

// Insert a vector of entries of (key, leaf) into tree.
let root = tree.inserts(root.as_ref(), &keys, &leaves)?;
assert_ne!(root, None);

Similarly, gets() and removes() also are designed for batch usage.

let result = tree.gets(root.as_ref(), &keys)?;
assert_eq!(result.len(), keys.len());

let root = tree.removes(root.as_ref(), &keys)?;
// surely, the tree has nothing nad the root back to 'None'
assert_eq!(root, None);

§Non-inclusion proof and inclusion proof, Merkle Proof

monotree has compressed representations, but it fully retains the core property of the Sparse Merkle Trie. 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 inclusion proof is outlined below:

§Generate a Merkle Proof

Prepare a random tree for testing.

// random insertions for testing Merkle proof generation
let root = tree.inserts(root.as_ref(), &keys, &leaves)?;

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

Generate a Merkle proof for a given root and key.

let proof = tree.get_merkle_proof(root.as_ref(), &key)?;

§Verify the Merkle Proof

Prepare a target leaf matched with the target root above.

// where the Merkle proof verification starts off
let leaf = leaves[99];

To verify the proof correctly, you need to provide a hasher matched.

// Previously the tree was initialized with `Blake2b`
let hasher = Blake2b::new();

Just call verify_proof(&HASHER, &ROOT, &LEAF, &PROOF). That’s all!

let verified = verify_proof(&hasher, root.as_ref(), &leaf, proof.as_ref());
assert_eq!(verified, true);

§Tracking the Latest Root

Sparse Merkle Trie is a space where multiple states (roots) coexist simultaneously. There is no reason why a particular state must be stored more preciously than another. The lastest root is nothing more than the most recently updated state.

monotree has a minimal design. It does not automatically update or track the latest root. However, monotree provides tools to update and fetch the latest root.

Use set_headroot(&LATEST_ROOT) to set the latest root to the database.

tree.set_headroot(root.as_ref());

Use get_headroot() to get the latest root from the database.

let headroot = tree.get_headroot()?;
assert_eq!(headroot, root);

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.

Structs§

Errors: An Error type defiend for handling general errors.

Constants§

HASH_LEN: Size of fixed length byte-array from a Hasher. Equivalent to key length of monotree.
ROOT_KEY: The key to be used to restore the latest root

Type Aliases§

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>.

Crate monotreeCopy item path