默克尔山脉

一种通用默克尔山脉实现。

特性

• 叶子积累
• 多叶子默克尔证明
• 从最后一个叶子的默克尔证明累积

构建

# An 11 leaves MMR

          14
       /       \
     6          13
   /   \       /   \
  2     5     9     12     17
 / \   /  \  / \   /  \   /  \
0   1 3   4 7   8 10  11 15  16 18

在MMR中，我们使用插入顺序来引用叶子和节点。

我们通过以下方式将新叶子插入到MMR中

1. 将叶子或节点插入到下一个位置。
2. 如果当前位置有一个左兄弟节点，我们将左右节点合并以生成一个新的父节点，然后回到步骤1插入节点。

例如，我们将叶子插入到示例MMR中

1. 将叶子插入到下一个位置： 19。
2. 现在检查左兄弟 18 并计算父节点： merge(mmr[18], mmr[19])。
3. 将父节点插入到位置 20。
4. 因为节点 20 也有一个左兄弟节点 17，计算父节点： merge(mmr[17], mmr[20])。
5. 将新节点插入到下一个位置 21。
6. 因为节点 21 没有左兄弟节点，插入完成。

插入新叶子后的示例 MMR

          14
       /       \
     6          13            21
   /   \       /   \         /   \
  2     5     9     12     17     20
 / \   /  \  / \   /  \   /  \   /  \
0   1 3   4 7   8 10  11 15  16 18  19

默克尔根

MMR 是由一个或多个子默克尔树（或山脉）构建的。每个子默克尔树的根是 MMR 中的一个高峰，我们通过从右到左将这些高峰打包来计算 MMR 根。

例如，在 11 叶 MMR 中，我们有 3 个高峰：14, 17, 18，我们从右到左打包这些高峰以获得根：merge(mmr[14], merge(mmr[17], mmr[18]))。

默克尔证明

默克尔证明是由以下部分组成的哈希数组

1. 从叶子的兄弟节点到包含叶子的高峰的默克尔证明。
2. 打包所有右侧高峰的哈希，如果没有右侧高峰则跳过此部分。
3. 从右到左所有左侧高峰的哈希，如果没有左侧高峰则跳过此部分。

我们可以从证明中重建默克尔根。预先计算 MMR 的大小从高峰位置可能有助于我们进行打包。

参考文献

• 默克尔山脉
• Grin 文档