A Rust library that implements a Sparse Merkle tree for a key-value store. The tree implements the same optimisations specified in the [Libra whitepaper][libra whitepaper], to reduce the number of hash operations required per tree operation to O(k) where k is the number of non-empty elements in the tree.
[
][Github-url]
[
][CI-url]
[
][codecov-url]
[
][doc-url]
[
][crates-url]
[
][rustc-url]
[
][license-apache-url]
[
][license-mit-url]
English | [简体中文][zh-cn-url]
## Features
- `no_std` supports, but needs `alloc`.
- Reduce the number of hash operations required per tree operation to O(k) where k is the number of non-empty elements in the tree.
- Internal implementation uses shallow copy, which powered by [`bytes::Bytes`](https://crates.io/crates/bytes).
- Performance almost depends on the cryptographic crate, e.g. `sha2`.
- Adaptable with [RustCrypto's crates](https://github.com/RustCrypto). All cryptographic structs which implement [`digest::Digest`](https://docs.rs/digest/latest/digest/trait.Digest.html) trait are adaptable with this crate.
- Easily compactable with any other cryptographic crates. When you want to use a cryptographic crate which does not implement [`digest::Digest`](https://docs.rs/digest/latest/digest/trait.Digest.html) trait, you actually do not need to fully implement [`digest::Digest`](https://docs.rs/digest/latest/digest/trait.Digest.html) trait.
e.g. only need to implement 5 methods (`new`, `update`, `digest`, `output_size`, `finalize`, actually only 3 methods) and just leave other methods `unreachable!()`.
```rust
pub struct DummyHasher {
data: Vec