pmtree

Persistent Merkle Tree (optimized & sparse & fixed-size) in Rust

How to use

[dependencies]
pmtree = { git = "https://github.com/Rate-Limiting-Nullifier/pmtree" }

Example

In-Memory DB (HashMap) + Keccak

structMemoryDB(HashMap<DBKey,Value>);structMyKeccak(Keccak);#[derive(Default)]structMemoryDBConfig;implDatabaseforMemoryDB{typeConfig = MemoryDBConfig;fnnew(_db_config:MemoryDBConfig) -> PmtreeResult<Self>{Ok(MemoryDB(HashMap::new()))}fnload(_db_config:MemoryDBConfig) -> PmtreeResult<Self>{Err(DatabaseError(DatabaseErrorKind::CannotLoadDatabase))}fnget(&self,key:DBKey) -> PmtreeResult<Option<Value>>{Ok(self.0.get(&key).cloned())}fnput(&mutself,key:DBKey,value:Value) -> PmtreeResult<()>{self.0.insert(key, value);Ok(())}fnput_batch(&mutself,subtree:HashMap<DBKey,Value>) -> PmtreeResult<()>{self.0.extend(subtree.into_iter());Ok(())}}implHasherforMyKeccak{typeFr = [u8;32];fndefault_leaf() -> Self::Fr{[0;32]}fnserialize(value:Self::Fr) -> Value{
value.to_vec()}fndeserialize(value:Value) -> Self::Fr{
value.try_into().unwrap()}fnhash(input:&[Self::Fr]) -> Self::Fr{letmut output = [0;32];letmut hasher = Keccak::v256();for element in input {
hasher.update(element);}
hasher.finalize(&mut output);
output
}}fnmain(){letmut mt = MerkleTree::<MemoryDB,MyKeccak>::new(2,MemoryDBConfig).unwrap();assert_eq!(mt.capacity(),4);assert_eq!(mt.depth(),2);
mt.update_next(hex!("c1ba1812ff680ce84c1d5b4f1087eeb08147a4d510f3496b2849df3a73f5af95")).unwrap();}