merkle-cbt-lean

适用于受限内存环境的 Merkle 树实现

此 crate 基于 https://crates.io/crates/merkle-cbt 中的 CBMT 实现

尽管上述 crate 在性能和内存要求方面确实高效，但发现其内存消耗对于实际受限的嵌入式环境（如 Kampela 设备 或 Ledger）来说太高。我们创建了此 crate，以尽可能小的内存访问和消耗处理证明检查，以便证明引理可以存储在外部内存或通过串行数据接口传输。请注意，证明构建并未优化，因为在典型应用中它是在常规内存环境中执行的，其难度可以忽略不计。此 crate 和 merkle-cbt 计算的根值设计和检查以确保它们相同，在内存限制不是关键的情况下，应使用上述 crate 而不是此 one。

我们决定将其作为单独的 crate，以避免证明结构上的混淆，并保持两个模块尽可能简约。

概念

为了限制内存，我们将宽度图遍历替换为深度。因此，一次只存储一个分支，并且 CMBT 总是比它高得多。为了实现这一点，我们必须相应地更改引理的排序，否则构建在概念上是相同的。这里的主要缺点是，与线性的宽度遍历相比，大约是二次的遍历时间，因为从底部开始，我们必须为每个叶子节点遍历整个树。

详细操作

证明构建

目前证明是以宽泛的方式构建的，未使用的节点合并在一起，直到没有合并可能；然后结果引理严格从左到右排序；这是引理传输顺序。

证明检查存储

一个深度与树高相对应的缓冲区存储当前路径中已计算出的左节点值。此缓冲区应位于“内部”快速内存中，而不是位于该项目中词元所在的区域，以显示性能提升。这包括所有存储，除了路径存储本身和为Merge过程所需的空间，这些都是证明检查所使用的。

每次将一个节点合并到这个缓冲区中时，如果它是左节点，就写入相应的层；如果是从右侧合并，则与它所在层的值合并并移动以进行合并。

证明检查算法

找到最左边的叶子节点并构建其到根的路径。将新路径左侧和最后路径右侧的所有证明从左到右合并到缓冲区中：首先将最后路径右侧立即的词元从下往上合并，然后将从新路径左侧的词元从上往下合并，保留路径交点以上的节点不变。然后，将叶子节点合并到缓冲区中。对每个叶子节点重复此过程，直到所有叶子节点都被使用。然后，从下往上（从左到右）合并最后路径右侧剩余的所有证明。应检查词元池以确定总词元消耗。

注释

当然，这个crate支持'no-std'