默克尔二叉索引树（Merkle-BIT）

这种树结构是一种通过分裂索引进行分支压缩的二叉 Merkle 树。这种结构可以用来存储多个版本的树状态，而不会在内存或磁盘上存储重复的数据。有关其基本用途的说明，请参阅此处和此处。

基本用法

要快速开始并感受 Merkle-BIT，您可以使用已实现的 HashTree 结构。

    use std::error::Error;
    use starling::hash_tree::HashTree;
    
    fn main() -> Result<Ok(), Error> {
        let tree = HashTree::new(8)?;
        
        // Keys must be of fixed size
        let mut key: Array<32> = [0xFF; 32].into();
        
        // Value to be put into the tree
        let value: Vec<u8> = vec![0xDDu8];
        
        // Inserting an element changes the root node
        let root = tree.insert(None, &mut [&key], &[value])?;
        
        let retrieved_value = tree.get(&root, &mut [&key])?;
        
        // Removing a root only deletes elements that are referenced only by that root
        tree.remove(&root)?;
        Ok(())
    }

此结构可用于存储少量数据，但除非明确修剪，否则树中的所有数据都将持久保存在内存中。

对于要存储在树中的大量项目，建议通过为您数据库实现 Database 特性来将结构连接到数据库。如果您的数据库支持，此结构还将利用批量写入。

基准测试

以下是使用 starling 在内存数据库上进行的基准测试，在速度合理的机器上

功能

Starling 支持许多用于树中的序列化和哈希方案，应根据您的性能和应用程序需求进行选择。

目前，集成的序列化方案包括

• bincode
• serde-json
• serde-cbor
• serde-yaml
• serde-pickle
• ron

请注意，只要您为节点类型实现了 Encode 和 Decode 特性，任何序列化方案都可以与 Starling 一起使用。

目前，集成树哈希方案包括

• Blake2b 通过 blake2_rfc
• Groestl 通过 groestl
• SHA2 通过 openssl
• SHA3 通过 tiny-keccak
• Keccak 通过 tiny-keccak
• SeaHash 通过 seahash
• FxHash 通过 fxhash
• 以及来自 RustCrypto 的最新哈希

您还可以使用默认的 Rust 哈希器，或者实现自己的 Hasher 特性以创建自己的哈希方案（除非使用 RustCrypto 的哈希，此时您需要启用 digest 特性，该特性为 Digest 实现了 Hasher）。

您还可以使用 RocksDB 来处理存储和从磁盘加载数据。您可以使用具有序列化方案的 RocksTree，通过命令行标志 --features="rocksdb bincode" 或在您的 Cargo.toml 清单中启用特性来实现。

一些启用的特性必须组合使用，或者您必须自己实现所需的特性（例如，仅使用 rocksdb 特性将生成编译器错误，您还必须选择一个序列化方案，例如 bincode 或为您的数据实现它）。

最后，您可以利用 hashbrown 来使用 hasbrown 包代替标准库中的 HashMap。

完全定制

为了充分利用 Merkle-BIT 结构的威力，您应该根据需要定制存储在树中的结构。

如果您为树结构中的每个组件提供自己的特性实现，则树可以使用这些实现而不是默认实现。

    use starling::merkle_bit::MerkleBIT;
    use starling::Array;
    use std::path::Path;
    use std::error::Error;
    
    fn main() -> Result<Ok, Error> {
        // A path to a database to be opened
        let path = Path::new("some path");
        
        // Your own database library
        let db = YourDB::open(&path);
        
        // These type annotations are required to specialize the Merkle BIT
        // Check the documentation for the required trait bounds for each of these types.
        pub struct MyTree;
        
        impl MerkleTree for MyTree {
            type Database = MyDatabase;
            type Branch = MyBranch;
            type Leaf = MyLeaf;
            type Data = MyData;
            type Node = MyNode;
            type Hasher = MyHasher;
            type Value = Myvalue;
        }
        let mbit = MerkleBIT<MyTree, 32>::from_db(db, depth);
                             
        // Keys must be of fixed size
        let key: Array<32> = [0xFF; 32].into();
        
        // An example value created from `MyValue`.  
        let value: MyValue = MyValue::new("Some value");
        
        // You can specify a previous root to add to, in this case there is no previous root
        let root: Array<32> = mbit.insert(None, &mut [key], &[value])?;

        // Every time an element is added or removed a new root is created.
        let new_key: Array<32> = [0xEE; 32].into();
        let new_value: ValueType = MyValue::new("Some new value");
        let new_root: Array<32> = mbit.insert(&root, &mut [key], &[value])?;
        
        // Retrieving the inserted value
        let inserted_values: HashMap<&Array<32>, Option<MyValue>> = mbit.get(&root, &mut [key])?;

        // You must ensure that the root you supply matches a root where the key existed when retrieving items
        // This line will fail to find the `new_value`
        let empty_map = mbit.get(&root, &mut [new_key])?;

        // This line will succeed in finding values for both `key` and `new_key`
        let inhabited_map = mbit.get(&new_root, &mut [key, new_key])?;

        
        // Removing a tree root
        mbit.remove(&root)?;

        // This line will fail to find a value for `key` but will succeed in finding the value for `new_key`
        let partially_inhabited_map = mbit.get(&new_root, &mut [key, new_key])?;
        Ok(())
    }

验证

MerkleBIT 还支持生成和验证梅克尔包含证明，可以使用以下方式使用：

    use starling::hash_tree::HashTree;
    use std::error::Error;
    
    fn main() -> Result<Ok, Error> {
        let tree = HashTree::new(8)?;
        
        let mut key: Array<32> = [0xFF; 32].into();
        let value: Vec<u8> = vec![0xDDu8];
        
        let root: Array<32> = tree.insert(None, &mut [&key], &[value])?;
        
        // An inclusion proof that proves membership of a key in the tree
        let proof: Vec<(Array<32>, bool)> = tree.generate_inclusion_proof(&root, key)?;
        
        // If the proof is valid, it will return Ok(())
        HashTree::verify_inclusion_proof(&root, key, &value, &proof)?;
        Ok(())
    }

许可证

在以下任一许可证下发布：

• Apache License，版本 2.0，（LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0）
• MIT 许可证（LICENSE-MIT 或 http://opensource.org/licenses/MIT）

由您选择。

贡献

除非您明确说明，否则根据 Apache-2.0 许可证定义，您有意提交的任何贡献都应按照上述方式双许可，不附加任何额外条款或条件。

报告

该项目目前正在快速发展，应注意的是，小版本可能包含对 API 的破坏性更改。这些更改将在每个版本的变更日志中注明，但如果我们破坏了某些内容或忘记提及此类更改，请提交一个问题或提交一个拉取请求，我们将尽快审查。

支持

您是否使用此包并希望确保持续的支持？请考虑通过我的赞助页面赞助我。

致谢

特别感谢 Niall Moore 和 Owen Delahoy 在该项目的早期阶段提供的协助。