# 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
and**simple****lightweight**, butand**fast****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>`

.