LSMTree

A Rust library that implements a Sparse Merkle tree for a key-value map. 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.
Performance almost depends on the cryptographic crate, e.g. sha2.
Adaptable with RustCrypto's crates. All cryptographic structs which implement digest::Digest trait are adaptable with this crate.

Easily to compitable any other cryptographic crates. When you want to use a cryptographic crate which does not implement digest::Digest trait, you actually do not need to fully implement digest::Digest 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<Self> {
    // your implementation here
}

fn update(&mut self, data: impl AsRef<[u8]>) {
    // your implementation here
}

fn output_size() -> usize {
    <Self as OutputSizeUser>::output_size()
}

fn digest(data: impl AsRef<[u8]>) -> digest::Output<Self> {
    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<Self>) {
    unreachable!()
}

fn finalize_reset(&mut self) -> digest::Output<Self> {
    unreachable!()
}

fn finalize_into_reset(&mut self, _out: &mut digest::Output<Self>) {
    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<Option<Bytes>, 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<Bytes, Self::Error> {
    self.data.remove(key).ok_or(Error::NotFound)
}

fn contains(&self, key: &[u8]) -> Result<bool, Self::Error> {
    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 implementation.

License

lsmtree is under the terms of both the MIT license and the Apache License (Version 2.0).

See LICENSE-APACHE, LICENSE-MIT for details.