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
from
examples/basic.rs
Regarding non-inclusion proof and inclusion proof, See Merkle proof section in More Examples below.
use ;
use random_hash;
Performance
All benchmarks were performed in a cumulative way, where the root resulting from an operation just before was reused for subsequent operations. They were carried out with randomly-generated bytes entries and from the root of an empty tree. (Deletion starts from the last root.)
Tested on: Intel Core i5-3570 CPU @ 3.4GHz and 16 GB RAM / Ubuntu 18.04 with
rustc stable 1.42.0
As a hasher,Blake3
was used in this benchmark.
Op. | DB used | #Entries | Time Measured | Std Error | per Op. |
---|---|---|---|---|---|
Insert | HashMap | 10 | 8.50 us | 0.01 us | 0.85 us |
Insert | HashMap | 100 | 165.71 us | 0.14 us | 1.66 us |
Insert | HashMap | 1000 | 2.32 ms | 0.01 ms | 2.32 us |
Insert | HashMap | 10000 | 37.39 ms | 0.02 ms | 3.74 us |
Get | HashMap | 10 | 7.82 us | 0.01 us | 0.78 us |
Get | HashMap | 100 | 114.51 us | 0.14 us | 1.15 us |
Get | HashMap | 1000 | 1.52 ms | 0.01 ms | 1.52 us |
Get | HashMap | 10000 | 20.40 ms | 0.01 ms | 2.40 us |
Remove | HashMap | 10 | 15.65 us | 0.01 us | 1.57 us |
Remove | HashMap | 100 | 282.68 us | 0.09 us | 2.83 us |
Remove | HashMap | 1000 | 4.23 ms | 0.01 ms | 4.23 us |
Remove | HashMap | 10000 | 69.15 ms | 0.07 ms | 6.92 us |
Insert | RocksDB | 10 | 34.80 us | 0.27 us | 3.48 us |
Insert | RocksDB | 100 | 602.55 us | 2.72 us | 6.03 us |
Insert | RocksDB | 1000 | 10.35 ms | 0.06 ms | 10.35 us |
Insert | RocksDB | 10000 | 145.83 ms | 0.20 ms | 14.58 us |
Get | RocksDB | 10 | 10.20 us | 0.06 us | 1.02 us |
Get | RocksDB | 100 | 142.20 us | 0.79 us | 1.42 us |
Get | RocksDB | 1000 | 1.74 ms | 0.01 ms | 1.74 us |
Get | RocksDB | 10000 | 22.94 ms | 0.03 ms | 2.29 us |
Remove | RocksDB | 10 | 58.33 us | 0.50 us | 5.83 us |
Remove | RocksDB | 100 | 1.02 ms | 6.40 us | 10.20 us |
Remove | RocksDB | 1000 | 20.22 ms | 0.10 ms | 20.22 us |
Remove | RocksDB | 10000 | 394.95 ms | 1.46 ms | 39.50 us |
Integration tests and benchmark
performs integration tests with full combinations of operations and tree types consisting of Databases and Hashers included.
## Some tests are time consuming.
## --release is optional, but without it, it will take a longer time to complete the tests
performs a micro-benchmark based on Criterion
, with full combinations of operations and tree types consisting of Databases and Hashers included.
and macroscopic-time benchmarks (but rather wider error bars) with all tree types were also prepared in examples/perf.rs
.
and some examples describing how to manipulate monotree
Further improvement
monotree
is a special case among the generalized binary radix trees, I'd like to call it PoT (Power Of Two) radix tree
.
If monotree
were generalized with pow(2, n)
of nibbles as a branching unit, there would have been room for further performance improvement.
This generalization is now on progress.
More Examples
from
examples/advanced.rs
use *;
use *;
use *;
use *;