LSMTree

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, } impl digest::OutputSizeUser for DummyHasher { type OutputSize = digest::typenum::U32; } impl digest::Digest for DummyHasher { fn new() -> Self { // your implementation here } fn finalize(mut self) -> digest::Output { // your implementation here } fn update(&mut self, data: impl AsRef<[u8]>) { // your implementation here } fn output_size() -> usize { ::output_size() } fn digest(data: impl AsRef<[u8]>) -> digest::Output { let mut h = Self::new(); h.update(data); h.finalize() } fn new_with_prefix(_data: impl AsRef<[u8]>) -> Self { unreachable!() } fn chain_update(self, _data: impl AsRef<[u8]>) -> Self { unreachable!() } fn finalize_into(self, _out: &mut digest::Output) { unreachable!() } fn finalize_reset(&mut self) -> digest::Output { unreachable!() } fn finalize_into_reset(&mut self, _out: &mut digest::Output) { unreachable!() } fn reset(&mut self) { unreachable!() } } ``` ## Installation ```toml [dependencies] lsmtree = "0.1" ``` ## Example ```rust use lsmtree::{bytes::Bytes, BadProof, KVStore, SparseMerkleTree}; use sha2::Sha256; use std::collections::HashMap; #[derive(Debug)] pub enum Error { NotFound, BadProof(BadProof), } impl From for Error { fn from(e: BadProof) -> Self { Error::BadProof(e) } } impl core::fmt::Display for Error { fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result { write!(f, "Error") } } impl std::error::Error for Error {} #[derive(Debug, Clone, Default)] pub struct SimpleStore { data: HashMap, } impl SimpleStore { pub fn new() -> Self { Self { data: HashMap::new(), } } } impl KVStore for SimpleStore { type Error = Error; type Hasher = Sha256; fn get(&self, key: &[u8]) -> Result, Self::Error> { Ok(self.data.get(key).map(core::clone::Clone::clone)) } fn set(&mut self, key: Bytes, value: Bytes) -> Result<(), Self::Error> { self.data.insert(key, value); Ok(()) } fn remove(&mut self, key: &[u8]) -> Result { self.data.remove(key).ok_or(Error::NotFound) } fn contains(&self, key: &[u8]) -> Result { Ok(self.data.contains_key(key)) } } fn main() { let mut smt = SparseMerkleTree::::new(); // insert smt.update(b"key1", Bytes::from("val1")).unwrap(); // get assert_eq!(smt.get(b"key1").unwrap(), Some(Bytes::from("val1"))); // prove let proof = smt.prove(b"key1").unwrap(); assert!(proof.verify(smt.root_ref(), b"key1", b"val1")); } ``` ## Acknowledge - Thanks celestiaorg's developers for providing amazing Go version [smt](https://github.com/celestiaorg/smt) implementation. #### License `lsmtree` is under the terms of both the MIT license and the Apache License (Version 2.0). See [LICENSE-APACHE](LICENSE-APACHE), [LICENSE-MIT](LICENSE-MIT) for details. Copyright (c) 2022 Al Liu. [Github-url]: https://github.com/al8n/lsmtree/ [CI-url]: https://github.com/al8n/lsmtree/actions/workflows/ci.yml [doc-url]: https://docs.rs/lsmtree [crates-url]: https://crates.io/crates/lsmtree [codecov-url]: https://app.codecov.io/gh/al8n/lsmtree/ [license-url]: https://opensource.org/licenses/Apache-2.0 [rustc-url]: https://github.com/rust-lang/rust/blob/master/RELEASES.md [license-apache-url]: https://opensource.org/licenses/Apache-2.0 [license-mit-url]: https://opensource.org/licenses/MIT [zh-cn-url]: https://github.com/al8n/lsmtree/tree/main/README-zh_CN.md [libra whitepaper]: https://diem-developers-components.netlify.app/papers/the-diem-blockchain/2020-05-26.pdf