通用Merkle树

此crate提供了一种通用的、可组合的、可并行化的方法来从输入数据构建Merkle树，也称为哈希树。其基本设计对哈希算法的选择、输入数据的类型以及存储在叶子节点中的从输入数据派生出的信息是中立的。

设计假设

• Merkle树通常在哈希内容“密封”时一次性构建。向先前计算出的树追加操作只能通过在密封树根上添加新的层级来完成。需要反复重新计算Merkle树以适应可变内容的应用程序设计，其有用性和效率值得怀疑。因此，表示完全构建的树的数据结构可以是不可变的。

• Merkle树通常不用于包含哈希输入数据。然而，一些有关输入的信息可能需要存储在叶子节点中。因此，设计应提供灵活的叶子数据提取选择，包括无叶子数据树和将输入作为叶子数据拥有的树。

• 应用程序应在哈希算法方面具有选择权，而不仅仅限于特定的摘要API。然而，Rust Crypto项目的API应直接支持。

• 应用程序应具有灵活性，以确定如何计算子节点的哈希以供其父节点使用。默认情况下，可以通过在区分叶子节点和非叶子节点的字节值前添加来提供一种流行的默认方式，以防止第二预映像攻击。

• 应支持构建左填充、具有均匀叶子深度的二叉树，允许最右边的“角度”内部节点（如比特币），以及完整但不一定是平衡的二叉树（如证书透明度）作为主要用例。

• Merkle树的计算可以高度并行化，因此应提供一个作为可选功能的具有工作窃取线程池的实现。

设计说明

设计使用构建者模式将Merkle树数据模型（不可变）与各种构建设施分开，这些设施由tree::Builder、tree::parallel::Builder和相关类型表示。

未来添加

需要支持审计路径，包括根哈希和验证叶子数据完整性的所需侧节点哈希链。

构建叶节点的输入还不能增量提供。有一个想法如何优雅地实现这一点。

可以提供一种扩展，用于从迭代输入中构建树，其中要散列的数据与存储为叶数据的值（如 std::iter::Enumerate 的项值）一起多路复用。

许可证

根据您选择以下之一授权：

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

由您选择。

贡献

除非您明确表示，否则，根据 Apache-2.0 许可证的定义，您有意提交的任何贡献，包括但不限于以下内容，均应按上述方式双重授权，不附加任何额外的条款或条件。