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"));
}

Stores

The following stores are supported:

• rusqlite
• rocksdb
• sled

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

Disk space usage

Store	Depth	Leaves	Size (MiB)
sled	32	1000000	290.00
sqlite	32	1000000	159.18
rocksdb	32	1000000	183.27

add_leaves throughput

Depth	Hash	Store	Throughput (Kelem/s)
32	keccak256	rocksdb	21.945
32	keccak256	sqlite	30.170
32	keccak256	sled	64.759
32	keccak256	memory	143.700

proof time

Depth	Hash	Store	Time
32	keccak256	memory	188.250 ns
32	keccak256	sled	6.436 µs
32	keccak256	sqlite	11.366 µs
32	keccak256	rocksdb	30.235 µs

License

MIT License