#merkletree #merkle #merkle-tree #sparse-merkle-tree #smt

no-std lsmtree

Implements a Sparse Merkle tree for a key-value store. The tree implements the same optimisations specified in the 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.

9 releases

Uses new Rust 2021

0.1.1 Aug 7, 2022
0.1.0 Aug 7, 2022
0.0.8 Aug 7, 2022

#235 in Data structures

MIT/Apache

90KB
1.5K SLoC

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, 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 Build codecov

docs.rs crates.io rustc

license-apache license-mit

English | 简体中文

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 compactable with 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!().

    pub struct DummyHasher { 
        data: Vec<u8>,
    }
    
    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

[dependencies]
lsmtree = "0.1"

Example

use lsmtree::{bytes::Bytes, BadProof, KVStore, SparseMerkleTree};
use sha2::Sha256;
use std::collections::HashMap;

#[derive(Debug)]
pub enum Error {
    NotFound,
    BadProof(BadProof),
}

impl From<BadProof> 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<Bytes, Bytes>,
}

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::<SimpleStore>::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.

Copyright (c) 2022 Al Liu.

Dependencies

~445KB