3 releases
0.0.6 | Oct 18, 2024 |
---|---|
0.0.5 | Aug 6, 2024 |
0.0.4 | Aug 6, 2024 |
#618 in Data structures
141 downloads per month
43KB
759 lines
Sparse Merkle tree
Sparse Merkle tree implementation in Rust.
A sparse Merkle tree is a data structure useful for storing a key/value map where every leaf node of the tree contains the cryptographic hash of a key/value pair and every non leaf node contains the concatenated hashes of its child nodes. Sparse Merkle trees provides a secure and efficient verification of large data sets and they are often used in peer-to-peer technologies. This implementation is an optimized version of the traditional sparse Merkle tree and it is based on the concepts expressed in the papers and resources below.
References
- Rasmus Dahlberg, Tobias Pulls and Roel Peeters. Efficient Sparse Merkle Trees: Caching Strategies and Secure (Non-)Membership Proofs. Cryptology ePrint Archive: Report 2016/683, 2016. https://eprint.iacr.org/2016/683.
- Faraz Haider. Compact sparse merkle trees. Cryptology ePrint Archive: Report 2018/955, 2018. https://eprint.iacr.org/2018/955.
- Jordi Baylina and Marta Bellés. Sparse Merkle Trees. https://docs.iden3.io/publications/pdfs/Merkle-Tree.pdf.
- Vitalik Buterin Fichter. Optimizing sparse Merkle trees. https://ethresear.ch/t/optimizing-sparse-merkle-trees/3751.
🛠 Install
You can install zk-kit-smt
crate with cargo
:
cargo add zk-kit-smt
📜 Usage
use zk_kit_smt::smt::{Key, Node, Value, SMT};
fn hash_function(nodes: Vec<Node>) -> Node {
let strings: Vec<String> = nodes.iter().map(|node| node.to_string()).collect();
Node::Str(strings.join(","))
}
fn main() {
// Initialize the Sparse Merkle Tree with a hash function.
let mut smt = SMT::new(hash_function, false);
let key = Key::Str("aaa".to_string());
let value = Value::Str("bbb".to_string());
// Add a key-value pair to the Sparse Merkle Tree.
smt.add(key.clone(), value.clone()).unwrap();
// Get the value of the key.
let get = smt.get(key.clone());
assert_eq!(get, Some(value));
// Update the value of the key.
let new_value = Value::Str("ccc".to_string());
let update = smt.update(key.clone(), new_value.clone());
assert!(update.is_ok());
assert_eq!(smt.get(key.clone()), Some(new_value));
// Create and verify a proof for the key.
let create_proof = smt.create_proof(key.clone());
let verify_proof = smt.verify_proof(create_proof);
assert!(verify_proof);
// Delete the key.
let delete = smt.delete(key.clone());
assert!(delete.is_ok());
assert_eq!(smt.get(key.clone()), None);
}
Dependencies
~480KB
~10K SLoC