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.
. 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:
Hash functions
The following hash functions are supported:
Benchmarks
The following benchmarks measure in a AMD Ryzen 7 7700 8-Core Processor with 64GB of RAM 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 18.280 32 keccak256 sqlite 22.348 32 keccak256 sled 43.280 32 keccak256 memory 86.084
proof time
Depth Hash Store Time 32 keccak256 memory 560.990 ns 32 keccak256 sled 7.878 µs 32 keccak256 sqlite 14.562 µs 32 keccak256 rocksdb 34.391 µs
License
MIT License