rs-merkle-tree

Merkle tree implementation in Rust with the following features: * Fixed depth: All proofs have a constant size equal to the Depth. * Append-only: Leaves are added sequentially starting at index 0. Once added, a leaf cannot be modified. * Optimized for Merkle proof retrieval: Intermediate leaves are stored so that Merkle proofs can be fetched from memory without needing to be calculated lazily, resulting in very fast retrieval times. * Configurable storage backends to store the bottom and intermediate leaves up the root. * Configurable hash functions to hash nodes. * Simple and easy to use interface: add_leaves, root, num_leaves, proof.

Add rs-merkle-tree as a dependency to your Rust Cargo.toml.

[dependencies]
rs-merkle-tree = "0.1.0"

You can create a Merkle tree, add leaves, get the number of leaves and get the Merkle proof of a given index as follows. This creates a simple merkle tree using keccak256 hashing algorithm, a memory storage and a depth 32.

use rs_merkle_tree::to_node;
use rs_merkle_tree::tree::MerkleTree32;

fn main() {
    let mut tree = MerkleTree32::default();
    tree.add_leaves(&[to_node!(
        "0x532c79f3ea0f4873946d1b14770eaa1c157255a003e73da987b858cc287b0482"
    )])
    .unwrap();

    println!("root: {:?}", tree.root().unwrap());
    println!("num leaves: {:?}", tree.num_leaves());
    println!("proof: {:?}", tree.proof(0).unwrap().proof);
}

You can customize your tree by choosing a different store, hash function, and depth as follows. Note that you have to modify the feature for the stores. This avoids importing the stuff you don't need. See the following examples.

Depth: 32 | Hashing: Keccak | Store: sled

[dependencies]
rs-merkle-tree = { version = "0.1.0", features = ["sled_store"] }

use rs_merkle_tree::hasher::Keccak256Hasher;
use rs_merkle_tree::stores::SledStore;
use rs_merkle_tree::tree::MerkleTree;

fn main() {
    let mut tree: MerkleTree<Keccak256Hasher, SledStore, 32> =
        MerkleTree::new(Keccak256Hasher, SledStore::new("sled.db", true));
}

Depth: 32 | Hashing: Poseidon | Store: rocksdb

rs-merkle-tree = { version = "0.1.0", features = ["rocksdb_store"] }

use rs_merkle_tree::hasher::PoseidonHasher;
use rs_merkle_tree::stores::RocksDbStore;
use rs_merkle_tree::tree::MerkleTree;

fn main() {
    let mut tree: MerkleTree<PoseidonHasher, RocksDbStore, 32> =
        MerkleTree::new(PoseidonHasher, RocksDbStore::new("rocksdb.db"));
}

Depth: 32 | Hashing: Poseidon | Store: sqlite

rs-merkle-tree = { version = "0.1.0", features = ["sqlite_store"] }

use rs_merkle_tree::hasher::PoseidonHasher;
use rs_merkle_tree::stores::SqliteStore;
use rs_merkle_tree::tree::MerkleTree;

fn main() {
    let mut tree: MerkleTree<PoseidonHasher, SqliteStore, 32> =
        MerkleTree::new(PoseidonHasher, SqliteStore::new("tree.db"));
}

Depth: 32 | Hashing: Keccak | Store: file

rs-merkle-tree = { version = "0.1.0", features = ["file_store"] }

use rs_merkle_tree::hasher::Keccak256Hasher;
use rs_merkle_tree::stores::FileStore;
use rs_merkle_tree::tree::MerkleTree;

fn main() {
    // Stores one flat file per level inside the given directory.
    let mut tree: MerkleTree<Keccak256Hasher, FileStore, 32> =
        MerkleTree::new(Keccak256Hasher, FileStore::new("filestore.db"));
}

Tests

Run all tests

cargo test --all-features

Stores

The following stores are supported: * rusqlite * rocksdb * sled * file: a flat store (no database engine) that keeps one file per level in a directory.

Hash functions

The following hash functions are supported: * keccak256 * Poseidon BN254 Circom T3

Benchmarks

The following benchmarks measure in a MacBook Pro M4 24GB the following: * Consumed disk size * Leaf insertion throughput in thousands per second. * Merkle proof generation times.

You can run them with

cargo bench --features=all

And you can generate the following table with this.

python benchmarks.py

add_leaves throughput

proof time

License

MIT License