稀疏梅克尔树

Rust中的稀疏梅克尔树实现。

稀疏梅克尔树是一种数据结构，用于存储键/值映射，其中每个叶子节点包含键/值对的加密哈希，每个非叶子节点包含其子节点的连接哈希。稀疏梅克尔树提供了对大数据集的安全和高效验证，它们常用于对等网络技术。此实现是传统稀疏梅克尔树的优化版本，并基于以下论文和资源中表达的概念。

参考

1. Rasmus Dahlberg, Tobias Pulls 和 Roel Peeters. 高效稀疏梅克尔树：缓存策略和安全（非）成员证明. 密码学电子档案：报告 2016/683，2016. https://eprint.iacr.org/2016/683.
2. Faraz Haider. 紧凑的稀疏梅克尔树. 密码学电子档案：报告 2018/955，2018. https://eprint.iacr.org/2018/955.
3. Jordi Baylina 和 Marta Bellés. 稀疏梅克尔树. https://docs.iden3.io/publications/pdfs/Merkle-Tree.pdf.
4. Vitalik Buterin Fichter. 优化稀疏梅克尔树. https://ethresear.ch/t/optimizing-sparse-merkle-trees/3751.

🛠 安装

您可以使用 zk-kit-smt crate 通过 cargo 安装。

cargo add zk-kit-smt

📜 使用方法

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