shardtree

这是一个 Rust 包，提供了一种从左到右密集填充的固定深度 Merkle 树结构的实现。

• 无序插入：叶子节点可以任意顺序插入到树中。结构将跟踪树的最右侧填充位置作为树的边界；在此位置左侧的未填充叶子被视为“缺失”，而在此位置右侧的未填充叶子被视为“空”。
• 见证：Merkle 树的个别叶子可以被标记，以便在插入树时维护标记叶子的见证，但不需要保留以维护这些见证的特定叶子节点和节点数据，以提高空间效率。
• 检查点：树可以重置到之前检查点的状态，最多为固定数量的检查点。

树被表示为有序的固定深度子树集合，或称为“碎片”。碎片的最顶层形成“帽”中的叶子。

Level
  3           root         \
              / \           |
            /     \         |
  2       /         \        } cap
        / \         / \     |
       /   \       /   \    |
  1   A     B     C     D  /  \
     / \   / \   / \   / \     } shards
  0 /\ /\ /\ /\ /\ /\ /\ /\   /

这种结构允许将标记叶子的见证推进到最近的检查点或树的最新状态，而无需单独插入每个中间叶子。相反，只需插入包含标记叶子的碎片和树边界的所有完整碎片的根，以及从标记叶子到其所在碎片根的路径所需必要的节点。

文档

许可

在以下任一许可下授权：

• Apache License，版本 2.0，(LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0)
• 麻省理工学院许可证（LICENSE-MIT 或 http://opensource.org/licenses/MIT）

由您选择。

贡献

除非您明确声明，否则任何根据Apache-2.0许可证定义的、有意提交以包含在作品中的贡献，都将根据上述方式双重授权，不附加任何额外的条款或条件。