特性

• no_std支持，但需要alloc。

• 将每个树操作所需的哈希操作次数降低到O(k)，其中k是树中非空元素的数量。

• 内部实现使用浅拷贝，由bytes::Bytes提供支持。

• 性能几乎取决于加密库，例如sha2。

• 可适配RustCrypto的crate。所有实现了digest::Digest trait的加密结构都可以与此crate兼容。

• 易于与其他任何加密crate压缩。当你想使用未实现digest::Digest trait的加密crate时，实际上你不需要完全实现digest::Digest trait。

  例如，只需要实现5个方法（new、update、digest、output_size、finalize，实际上只有3个方法）并只留下其他方法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!()
      }
  }
  

安装

[dependencies]
lsmtree = "0.1"

示例

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"));
}

致谢

• 感谢celestiaorg的开发者提供了出色的Go版本smt实现。

许可证

lsmtree受MIT许可证和Apache许可证（版本2.0）的约束。

请参阅LICENSE-APACHE、LICENSE-MIT以获取详细信息。

版权所有（c）2022 Al Liu。