Merkle Binary Indexed Tree (Merkle-BIT)
This tree structure is a binary merkle tree with branch compression via split indexes. This structure can be used to store multiple versions of tree state without any duplication of the stored data, either in memory or on disk. See here and here for a basic explanation of its purpose.
Basic Usage
To quickly get started and get a feel for the Merkle-BIT, you can use the already implemented HashTree structure.
use Error;
use HashTree;
This structure can be used for small amounts of data, but all the data in the tree will persist in memory unless explicitly pruned.
For larger numbers of items to store in the tree, it is recommended to connect the structure to a database by implementing the
Database
trait for your database. This structure will also take advantage of batch writes if your database supports it.
Benchmarks
Below are the benchmarks when using starling
on an in-memory database on a reasonably fast machine:
Operation | Num. Entries | Is Tree Empty? | Measured Benchmark |
---|---|---|---|
insertion | 1 | yes | 0.407μs |
insertion | 10 | yes | 5.136μs |
insertion | 100 | yes | 46.796μs |
insertion | 1000 | yes | 480.060μs |
insertion | 10000 | yes | 7,219.300μs |
insertion | 1 | no | 6.315μs |
insertion | 10 | no | 19.400μs |
insertion | 100 | no | 149.710μs |
insertion | 1000 | no | 1,517.700μs |
insertion | 10000 | no | 15,043.000μs |
retrieval | 4096 | no | 2,889.100μs |
retrieval | 10000 | no | 9,437.100μs |
removal | 4096 | no | 0.070μs |
removal | 10000 | no | 0.071μs |
Features
Starling supports a number of serialization and hashing schemes for use in the tree, which should be selected based on your performance and application needs.
Currently integrated serialization schemes include:
bincode
serde-json
serde-cbor
serde-yaml
serde-pickle
ron
It should be noted that any serialization scheme will work with starling, provided you implement the Encode
and Decode
traits for the node types.
Currently integrated tree hashing schemes include:
Blake2b
viablake2_rfc
Groestl
viagroestl
SHA2
viaopenssl
SHA3
viatiny-keccak
Keccak
viatiny-keccak
SeaHash
viaseahash
FxHash
viafxhash
- and most updated hashes from RustCrypto
You may also use the default Rust hasher, or implement the Hasher
trait for your own hashing scheme (unless using a hash from
RustCrypto, then you will want to enable the use_digest
feature, which implements Hasher
for Digest
).
You can also use RocksDB to handle storing and loading from disk.
You can use the RocksTree
with a serialization scheme via the --features="use_rocksdb use_bincode"
command line flags
or by enabling the features in your Cargo.toml manifest.
Some enabled features must be used in combination, or you must implement the required traits yourself (E.g. using the
use_rocksdb
feature alone will generate a compiler error, you must also select a serialization scheme, such as use_bincode
or implement it for your data).
Finally, you can take advantage of the use_hashbrown
to use the hasbrown
crate instead of the standard library HashMap
.
Full Customization
To use the full power of the Merkle-BIT structure, you should customize the structures stored in the tree to match your needs.
If you provide your own implementation of the traits for each component of the tree structure, the tree can utilize them over the default implementation.
use MerkleBIT;
use PathBuf;
use Error;
Verification
The MerkleBIT
also supports generating and verifying merkle inclusion proofs, and may be used like below:
use HashTree;
use Error;
License
Licensed under either of
- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.
Reporting
The project is currently undergoing rapid development and it should be noted that minor releases may include breaking changes to the API. These changes will be noted in the Changelog of each release, but if we broke something or forgot to mention such a change, please file an issue or submit a pull request and we will review it at our earliest convenience.
Support
Do you use this crate and would like to ensure continued support? Please consider supporting me via Github Sponsors at my sponsor page.
Acknowledgments
Special thanks to Niall Moore and Owen Delahoy for assistance with the early phases of this project.