Monotree

Rust语言实现的优化稀疏默克尔树。这是一种基于位分支的二叉基数树，目前 没有使用任何字节。现在，分支单元只是一个 单个位，既不是4位也不是字节字节。

功能

• 非常 简单 和 轻量级，但 快速 且 健壮。
• 功能齐全 的稀疏默克尔树 (SMT) 作为存储
• 包括：非包含证明，以及 包含证明 和其验证。
• 再次强调，一点也不冗长。

此库主要依赖 Rust标准库，除了 数据库API 和 哈希函数。目前，monotree 支持以下数据库和哈希函数，但设计得非常容易定制和添加

数据库包括:

• HashMap
• RocksDB
• Sled

哈希函数包括:

• Blake3
• Blake2s 和 Blake2b
• SHA-2
• SHA-3 (Keccak)

快速入门

从 examples/basic.rs

有关 非包含证明 和 包含证明，请参阅以下 更多示例 中的 默克尔证明 部分。

use monotree::{Monotree, Result};
use monotree::utils::random_hash;

fn main() -> Result<()> {
    // Init a monotree instance
    // by default, with 'HashMap' and 'Blake3' hash function
    let mut tree = Monotree::default();

    // It is natural the tree root initially has 'None'
    let root = None;

    // Prepare a random pair of key and leaf.
    // random_hash() gives a fixed length of random array,
    // where Hash -> [u8; HASH_LEN], HASH_LEN = 32
    let key = random_hash();
    let leaf = random_hash();

    // Insert the entry (key, leaf) into tree, yielding a new root of tree
    let root = tree.insert(root.as_ref(), &key, &leaf)?;
    assert_ne!(root, None);

    // Get the leaf inserted just before. Note that the last root was used.
    let found = tree.get(root.as_ref(), &key)?;
    assert_eq!(found, Some(leaf));

    // Remove the entry
    let root = tree.remove(root.as_ref(), &key)?;

    // surely, the tree has nothing and the root back to 'None'
    assert_eq!(tree.get(root.as_ref(), &key)?, None);
    assert_eq!(root, None);
    Ok(())
}

性能

所有基准测试都是累积进行的，即后续操作使用仅在进行操作之前生成的根。它们使用随机生成的字节条目和从空树根开始执行。（删除从最后一个根开始。）

测试环境：Intel Core i5-3570 CPU @ 3.4GHz 和 16 GB RAM / Ubuntu 18.04，使用 rustc stable 1.42.0，作为哈希器，本次基准测试使用了 Blake3。

集成测试和基准测试

执行包含数据库和哈希器的所有操作和树类型的组合的集成测试。

    ## Some tests are time consuming.
    ## --release is optional, but without it, it will take a longer time to complete the tests
    $ cargo test --release --features "db_rocksdb, db_sled"

基于 Criterion 执行微基准测试，包括数据库和哈希器的所有操作和树类型的组合。

    $ cargo bench --features "db_rocksdb, db_sled"

以及所有树类型的宏观时间基准测试（但误差范围较宽），已在 examples/perf.rs 中准备。

    $ cargo run --release --example perf --features "db_rocksdb, db_sled"

以及一些描述如何操作 monotree 的示例。

    $ cargo run --example basic
    $ cargo run --example advanced --features "db_rocksdb"

进一步改进

monotree 是广义二叉基数树中的特殊情况，我将其称为 PoT (Power Of Two) 基数树。如果使用 pow(2, n) 的十六进制数作为分支单元对 monotree 进行泛化，那么将有机会进一步改进性能。

这项泛化正在进行中。

更多示例

来自 examples/advanced.rs

use monotree::database::*;
use monotree::hasher::*;
use monotree::utils::*;
use monotree::*;

fn main() -> Result<()> {
    // Init a monotree instance:
    // manually select a db and a hasher as your preference
    // Monotree::<DATABASE, HASHER>::new(DB_PATH)
    // where DATABASE = {MemoryDB, RocksDB, Sled}
    //         HASHER = {Blake3, Blake2s, Blake2b, Sha2, Sha3}
    let mut tree = Monotree::<RocksDB, Blake2b>::new("/tmp/monotree");

    // It is natural the tree root initially has 'None'
    let root = None;

    // Prepare 500 random pairs of key and leaf.
    // random_hashes() gives Vec<Hash>
    // where Hash is a fixed length of random array or [u8; HASH_LEN]
    let n = 500;
    let keys = random_hashes(n);
    let leaves = random_hashes(n);

    // Insert a bunch of entries of (key, leaf) into tree.
    // looks quite similar with 'monotree::insert()', but for insertion using batch.
    // 'inserts()' is much faster than 'insert()' since it's based on the following:
    // (1) DB batch-write, (2) sorting keys before insertion, and (3) mem-cache.
    let root = tree.inserts(root.as_ref(), &keys, &leaves)?;
    assert_ne!(root, None);

    // Similarly, there are methods 'gets()' and 'removes()' for batch use of
    // 'get()' and 'remove()', respectively.
    let result = tree.gets(root.as_ref(), &keys)?;
    assert_eq!(result.len(), keys.len());

    let root = tree.removes(root.as_ref(), &keys)?;
    // surely, the tree has nothing nad the root back to 'None'
    assert_eq!(root, None);

    /////////////////////////////////////////////////////////////////////
    // `Merkle proof` secion: verifying inclusion of data (inclusion proof)

    // `Monotree` has compressed representation, but it fully retains
    // the properties of the Sparse Merkle Tree (SMT).
    // Thus, `non-inclusion proof` is quite straightforward. Just go walk down
    // the tree with a key (or a path) given. If we cannot successfully get a leaf,
    // we can assure that the leaf is not a part of the tree.
    // The process of inclusion proof is below:

    // random pre-insertion for Merkle proof test
    let root = tree.inserts(root.as_ref(), &keys, &leaves)?;

    // pick a random key from keys among inserted just before
    let key = keys[99];

    // generate the Merkle proof for the root and the key
    let proof = tree.get_merkle_proof(root.as_ref(), &key)?;

    // To verify the proof correctly, you need to provide a hasher matched
    // Previously the tree was initialized with `Blake2b`
    let hasher = Blake2b::new();

    // get a leaf matched with the key: where the Merkle proof verification starts off
    let leaf = leaves[99];

    // verify the Merkle proof using all those above
    let verified = verify_proof(&hasher, root.as_ref(), &leaf, proof.as_ref());
    assert_eq!(verified, true);

    /////////////////////////////////////////////////////////////////////
    // Usage examples with some functional tests
    // Carefully trace the variable `root` as they are frequently shadowed.

    let mut tree = Monotree::default();
    let mut root = None;
    let hasher = Blake3::new();

    //--- insert/get and gen_proof/verify_proof over iterator
    for (i, (key, value)) in keys.iter().zip(leaves.iter()).enumerate() {
        // insert a key into tree
        root = tree.insert(root.as_ref(), key, value)?;

        // inserted a key and yields a root, where cumulative check-up goes on
        for (k, v) in keys.iter().zip(leaves.iter()).take(i + 1) {
            // check if the key-value pair was correctly inserted so far
            assert_eq!(tree.get(root.as_ref(), k)?, Some(*v));

            // generates a Merkle proof with all keys so far
            let proof = tree.get_merkle_proof(root.as_ref(), k)?;

            // verify the Merkle proof with all keys so far
            assert_eq!(
                verify_proof(&hasher, root.as_ref(), v, proof.as_ref()),
                true
            );
        }
    }
    assert_ne!(root, None);

    //--- insert/get and gen_proof/verify_proof after each deletion of entry
    for (i, (key, _)) in keys.iter().zip(leaves.iter()).enumerate() {
        assert_ne!(root, None);

        // assert that all other values are fine after each deletion
        for (k, v) in keys.iter().zip(leaves.iter()).skip(i) {
            // check in the same way as the previous example
            assert_eq!(tree.get(root.as_ref(), k)?, Some(*v));
            let proof = tree.get_merkle_proof(root.as_ref(), k)?;
            assert_eq!(
                verify_proof(&hasher, root.as_ref(), v, proof.as_ref()),
                true
            );
        }
        // delete a key and check if it was correctly removed
        root = tree.remove(root.as_ref(), key)?;
        assert_eq!(tree.get(root.as_ref(), key)?, None);
    }
    // must be back to inital state of tree
    assert_eq!(root, None);

    //--- faster way to insert/remove entries
    // Now tree is empty, and root is back to `None` again
    // Redo all those above using methods supporting batch operations
    root = tree.inserts(root.as_ref(), &keys, &leaves)?;
    assert_ne!(root, None);

    // Even if we shuffle the keys when removing,
    shuffle(&mut keys);

    // there's no difference. Back to `None` of root and empty tree again.
    // that's why the `root` plays a role as "state index of tree"
    root = tree.removes(root.as_ref(), &keys)?;
    assert_eq!(root, None);

    Ok(())
}