Sparse Merkle tree for a key-value map.

Overview

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.

You might also like...
The fallen leaves tell a story... of a colorful file tree visualizer for the command-line.
The fallen leaves tell a story... of a colorful file tree visualizer for the command-line.

Erdtree A bLazInGlY fAsT, simplified version of the ancient tree command which displays a colorful depth indented listing of files with their memory s

HD wallet BIP-32 related key derivation utilities.

HDWallet Docs HD wallet(BIP-32) key derivation utilities. This crate is build upon secp256k1 crate, this crate only provides BIP-32 related features,

X25519 elliptic curve Diffie-Hellman key exchange in pure-Rust, using curve25519-dalek.
X25519 elliptic curve Diffie-Hellman key exchange in pure-Rust, using curve25519-dalek.

x25519-dalek A pure-Rust implementation of x25519 elliptic curve Diffie-Hellman key exchange, with curve operations provided by curve25519-dalek. This

An implementation of the OPAQUE password-authenticated key exchange protocol

The OPAQUE key exchange protocol OPAQUE is an asymmetric password-authenticated key exchange protocol. It allows a client to authenticate to a server

A safe implementation of the secure remote password authentication and key-exchange protocol (SRP), SRP6a and legacy are as features available.

Secure Remote Password (SRP 6 / 6a) A safe implementation of the secure remote password authentication and key-exchange protocol (SRP version 6a). Ver

Keyhouse is a skeleton of general-purpose Key Management System written in Rust.

Keyhouse Keyhouse is a skeleton of general-purpose Key Management System. Keyhouse is not an off-the-shelf system, and it's not ready for production.

Manage secret values in-repo via public key cryptography

amber Manage secret values in-repo via public key cryptography. See the announcement blog post for more motivation. Amber provides the ability to secu

FS-DKR: One Round Distributed Key Rotation
FS-DKR: One Round Distributed Key Rotation

FS-DKR: One Round Distributed Key Rotation Intro In this note we aim to re-purpose the Fouque-Stern Distributed Key Generation (DKG) to support a secu

A suite of programs for Solana key management and security.
A suite of programs for Solana key management and security.

🔑 goki Goki is a suite of programs for Solana key management and security. It currently features: Goki Smart Wallet: A wallet loosely based on the Se

Owner
Al Liu
Rustacean/Gopher, distributed system engineer. In the previous two years, writing Go, but now, writing Rust most of the time.
Al Liu
DAPOL+ Proof of Liabilities using Bulletproofs and Sparse Merkle trees

DAPOL+ implementation Implementation of the DAPOL+ protocol introduced in the "Generalized Proof of Liabilities" by Yan Ji and Konstantinos Chalkias A

Mysten Labs 5 Apr 9, 2023
The most advanced Merkle tree library for Rust

rs-merkle rs-merkle is the most advanced Merkle tree library for Rust. Basic features include building a Merkle tree, creation, and verification of Me

Anton Suprunchuk 85 Dec 31, 2022
Bootstrap your merkle tree.

Merkle Generator Bootstrap your merkle tree, in Rust. Table of Contents Features Installation Usage Contributing Features Merkle Tree creation Merkle

DeGatchi 40 Feb 14, 2023
Prefix tree (ordered map and set) data structure using 100% safe Rust

PFX: A 100% safe, blob-oriented prefix tree This crate provides a prefix tree map and set data structure, implemented purely in safe Rust. The API is

Árpád Goretity  4 Apr 3, 2024
A simple key-value store with a log-structured, append-only storage architecture where data is encrypted with AES GCM.

akvdb A simple key-value store with a log-structured, append-only storage architecture where data is encrypted with AES GCM. Modified from the actionk

Olle W 3 Oct 10, 2022
Uses Plonky2 proof system to build recursive circuits for Merkle Trees.

ProvableMerkleTrees Introduction This repo provides Rust code to build Merkle Trees, equipped with a Provable interface to generate Zero Knowledge pro

null 5 Aug 18, 2023
A value transfer bridge between the Monero blockchain and the Secret Network.

Secret-Monero-Bridge A value transfer bridge between the Monero blockchain and the Secret Network. Proof-of-Concept Video Demonstration: https://ipfs.

null 28 Dec 7, 2022
A rust binding for nodejs to generate md5 hash value

Hasher A rust binding for creating node module to generate md5 hash value This project was bootstrapped by create-neon. Installing hasher Installing h

Md. Al-Amin 0 Nov 7, 2021
AMCOS - A high-peformance parallel monte-carlo simulation for estimating the fair value of options in finance

antoons-monte-carlo-options-sim A high-peformance parallel monte-carlo simulation for estimating the fair value of options in finance. Written in Rust

null 4 Jun 18, 2022
Trait that allows comparing a value to a range of values.

range_cmp Docs This Rust crate provides the RangeComparable trait on all types that implement Ord. This traits exposes a rcmp associated method that a

Akvize 3 Nov 8, 2023