Lib.rs

› 加密学
#tree

merkle_tree

Merkle树实现

由 Rust 编写

1个不稳定版本

使用旧的Rust 2015

0.1.0 2017年6月5日

#1369 in 加密学

46 每月下载量

MIT 许可证

56KB
792 行

Merkle Tree在Rust

Build Status

Coverage Status

技术解决方案

思想迭代 0

如果大多数任务都很简单，那么第三项就不太简单。一个务实的API应该如何设计？

已经确定，Merkle Tree没有所谓的“标准”实现，因此

  1. 所使用的哈希函数可能与SHA-2不同。我们得出结论，用户应该有选择在创建此结构实例时选择所需哈希函数的方式。在Rust中，有一个解决此问题的加密库——这是rust-crypto。类型Digest实现了最大数量的哈希函数，包括SHA-1、SHA-2、MD5和其他，因此决定使用它。

  2. 树中叶子数据的类型在它们被直接哈希之前是未知的，同样用户将使用的数据类型也是未知的。这不仅可以是字符串（如Merkle Tree的实现/示例中通常所做的那样），还可以是原始类型、自定义结构、集合。因此，需要某种类型，允许用户在客户端指定其数据可序列化，如果这些数据表示结构，则自动输出序列化代码。为此，社区开发了Serde库。类型Serialize允许传递任何实现其类型的用户类型。类型Serializer允许传递用户所需格式的序列化器。

  3. 用户应该具备以下能力：初始化一个空树，这将使用标准库中的类型Default；初始化基于多个“叶子”的树；以及单个“叶子”。在这种情况下，初始化函数应接受向量和数组——这是函数签名中应使用切片（它抽象了具体集合）的明确标志。

思想迭代 1

  1. 曾尝试实现一个接受Serializer并序列化任何Serialize-value的函数。由于目前存在一些问题，未能成功：[https://github.com/serde-rs/serde/issues/552](https://github.com/serde-rs/serde/issues/552)。我决定使用具有三种类型的枚举。可以抛入作为树叶-交易的任何类型，只要它们实现Serialize。

  2. 放弃了不同哈希选项的想法——转而存储固定大小的数组。

  3. 曾尝试使用SmallVec来优化处理小型树在栈上的性能。没有带来速度提升，已经放弃了。

  4. 添加了使用Rayon库并行化生成树新层的能力。随着叶子数量的增加，速度的提升越来越明显。Rayon在处理不同大小的树时，提供了从50%到100%的速度构建优势。

     test tests::build_1000000_tree_parallel_bincode ... bench: 608,845,363 ns/iter (+/- 139,315,093)
 test tests::build_1000000_tree_sequence_bincode ... bench: 1,062,443,268 ns/iter (+/- 74,610,158)

  5. 尝试了多种存储二叉树的方法

  • 存储为枚举 enum，其变体表示树节点（Root { left, right, hash }，Interior { parent, left, right, hash }，Leaf { parent, hash }）- 认为叶子节点的访问速度会较低，加上存储链接的开销，以及在使用封装类型的类型时出错的可能性较大，这会导致编译器“吞噬”同一类型的循环引用。

  • “标准”存储方式是平面向量，简单索引，快速访问 - 一个缺点是难以预先分配每个层的内存块，+ 如果将叶子存储在开头，索引公式不如下一种方式简单，无论如何，即使将叶子存储在末尾，在添加新节点时也会发生内存重新分配，但“上层”层；

  • 找到了一种折衷方案，即向量向量，其中每个向量表示树的一层，提前分配内存以优化树的插入操作 - 最终选择了这种方法。

  1. 了解到树不仅用于计算默克尔树根哈希，还可以从中获得审计证明路径 - 包括从交易哈希到根的路径哈希，通常在操作过程中也会检查这些哈希的有效性。已将相应的操作添加到库中。

  2. 在初始构建树之后，添加了添加新节点并自动重构剩余节点以向上遍历树的功能。

  3. 说实话，我在检查过程中一度陷入混乱，制作了一个基于字符串存储的树副本，其中使用字符串连接代替哈希。这样调试了算法。之后，我回到了存储字节数组的哈希。为了记录历史，我在代码中保留了MerkleTreeString结构。

  4. 最初，我使用了树层上的奇偶性规则，即元素数量为奇数时 - 必定添加最后一个节点的副本到层，后来我意识到这是一个多余的步骤，可以省略它；

实现缺点

  • 不知道这算不算缺点，但与许多示例不同，这里没有使用双重哈希；
  • 用户端规范化；
  • 可能有优化，允许在插入新节点到树时更有效地使用内存；
  • 没有选择哈希函数的功能，Digest类型实现适用于不同的哈希函数，因此它们会产生自己的哈希字节数量；
  • 我认为添加新节点后的算法不是最好的；
  • 它不会阻止将重复的交易添加到叶子，而可能确实需要这样做；
  • 没有内置的保存树叶到磁盘的功能（手动保存，然后将其加载到内存，重建并验证）；

实现优点

  • 通过使用Rayon的迭代器，在构建树时可以进行并行化；
  • 可以将任何实现Serialize的任何类型作为添加的交易；
  • 内存效率高；

示例

// подключаем крэйт
extern crate merkle_tree;

// подключаем структуру дерева и перечисление отвечающее за формат сериализации
use merkle_tree::{MerkleTree, SerializationFormat};

fn main() {
    // создаём дерево на основе 3-ёх "листьев"
    let mut merkle_tree = MerkleTree::from(&mut ["a", "b", "c"], SerializationFormat::Json);
    // вызываем построение дерева    
    merkle_tree.build().unwrap();
    // печатаем вычисленный хэш рут дерева
    println!("Merkle tree root hash: {:?}", merkle_tree.get_merkle_root());
    // печатаем пруф-путь для транзакции b
    println!("Merkle tree audit proot: {:?}", merkle_tree.audit_proof(&[172, 141, 131, 66, 187, 178, 54, 45, 19, 240, 165, 89, 163, 98, 27, 180, 7, 1, 19, 104, 137, 81, 100, 182, 40, 165, 79, 127, 195, 63, 196, 60]).unwrap());
    // добавляем в дерево хэш транзакции d
    merkle_tree.push(&String::from("d"));
    // печатаем рут хэш дерева
    println!("Merkle tree root hash: {:?}", merkle_tree.get_merkle_root());
    // печатаем пруф-путь для транзакции b
    println!("Merkle tree audit proot: {:?}", merkle_tree.audit_proof(&[172, 141, 131, 66, 187, 178, 54, 45, 19, 240, 165, 89, 163, 98, 27, 180, 7, 1, 19, 104, 137, 81, 100, 182, 40, 165, 79, 127, 195, 63, 196, 60]).unwrap());
}

使用的材料

依赖关系

~11MB
~200K SLoC