SMTree :: 可填充的稀疏 Merkle 树

SMTree 是一个灵活的稀疏树累加器，可以通过 traits 支持各种树类型，这些 traits 用于自定义节点合并和树填充逻辑。该 API 支持单个或多个叶子（批量证明）的包含证明，高效的 logN 填充以隐藏叶子数（由树的高度暗示）以及通过返回输入索引最近的叶子进行随机采样。

上述功能是利用稀疏 Merkle 树隐藏基于累加器的树中叶子种群的应用程序所必需的，例如 HashWires 范围证明和 DAPOL 审计证明构建。同样，可以轻松实现类似于比特币中的 Maxwell 负债树、简单的求和、XOR 或按字典顺序合并的 Merkle 树，并尝试使用不同的哈希函数进行比较性能。

文档

要构建 SparseMerkleTree 对象，您需要首先定义树节点的值类型，并实现为其实现的 Clone、Default、Mergeable、Paddable、ProofExtractable traits。您还需要为您证明节点类型 ProofExtractable::ProofNode 实现 Debug、Clone、Default、Eq、Mergeable、Serializable traits。

假设您的节点值只是哈希，并且合并函数是经典的，即对两个子节点连接的哈希进行哈希。因此，证明节点类型与树节点类型相同。

您可以在 node_template.rs 中找到各种树类型的参考实现。

如果您想为您的稀疏Merkle树启用随机采样，您需要进一步实现PaddingProvable特质。我们在node_template.rs结构体中提供了一个参考实现。

现在，您已经准备好构建您的稀疏Merkle树了！

贡献者

此代码的原始作者是Konstantinos Chalkias（@kchalkias）和Yan Ji（@iseriohn），Kevin Lewi（@kevinlewi）和Irakliy Khaburzaniya（@irakliyk）做出了贡献。想了解更多关于如何为此项目做出贡献的信息，请参阅此文档。

许可协议

本项目采用MIT许可协议。