Gene

lib.rs:

Gene: Over the Mountains

• MMR
• 动态累加器

默克尔山脉范围

介绍

默克尔山脉范围（MMR）是由Peter Todd发明的，更多关于它们的信息可以在Open Timestamps和Grin项目中找到。

默克尔山脉范围（MMR）是一种二叉树，其中每个父节点是其两个子节点的哈希值连接。MMR底部的叶子是数据的哈希值。MMR允许在树内轻松添加存在证明。MMR总是试图拥有尽可能大的单个二叉树，因此实际上可以拥有多个二叉树。每次您必须获取默克尔根（整个MMR的单个默克尔证明）时，您都会有各个树的山峰，或者说是山峰。

让我们用一个例子来说明如何构建一个。假设您已经有了以下MMR

      /\
     /  \
    /\  /\   /\
   /\/\/\/\ /\/\ /\

从这张图中我们可以看出我们有3座山。我们已经构建了可能的最大树。如果我们想计算默克尔根，我们只需将三个山峰连接起来然后进行哈希即可。

让我们继续这个例子，通过添加一个单个对象。现在我们的MMR如下所示

      /\
     /  \
    /\  /\   /\
   /\/\/\/\ /\/\ /\ /

我们现在有4座山。计算根意味着对（现在）四个山峰的连接进行哈希。

让我们继续这个例子，通过添加一个单个对象。现在我们的MMR如下所示

          /\
         /  \
        /    \
       /      \
      /\      /\
     /  \    /  \
    /\  /\  /\  /\
   /\/\/\/\/\/\/\/\

现在我们只有一个二叉树，根现在是对单个山峰哈希的哈希。随着向MMR添加更多对象，这个过程将继续。

                /\
               /  \
              /    \
             /      \
            /        \
           /          \
          /            \
         /\             \
        /\ \            /\
       /  \ \          /  \
      /\   \ \        /\   \
     /  \   \ \      /  \   \
    /\  /\  /\ \    /\  /\  /\
   /\/\/\/\/\/\/\  /\/\/\/\/\/\

由于MMR的独特构建方式，我们可以轻松地将MMR表示为节点线性列表。让我们取以下MMR并按我们创建它们的顺序编号节点。

        6
      /  \
     /    \
    2      5
   / \    / \
  0   1  3   4

在上面的节点创建示例中，您会看到MMR节点将按照它们命名的顺序创建。这意味着我们可以轻松地将它们表示为一个列表：高度：0 | 0 | 1 | 0 | 0 | 1 | 2 节点：0 | 1 | 2 | 3 | 4 | 5 | 6

由于MMR具有列表性质，我们可以使用以下公式轻松地在MMR中导航

跳转到右兄弟节点：$$ n + 2^{H+1} - 1 $$ 跳转到左兄弟节点：$$ n - 2^{H+1} - 1 $$ 二叉树顶点：$$ 2^{ H+1 } - 2 $$ 左下：$$ n - 2^H $$ 右下：$$ n-1 $$

节点编号

在Merkle Mountain Range (MMR)中节点编号可能存在一些混淆。以下是在本库中使用的约定。

• 所有索引均从0开始编号。
• MMR节点指的是Merkle Mountain Range中的所有节点，并按照上述描述的规范mmr排序。
• 叶子节点从0开始编号，每次添加叶子节点时递增1。

为了说明，考虑以下MMR

//! ```plaintext 14 /
/
6 13 21 <-- MMR索引 / \ / \ /
/ \ / \ /
2 5 9 12 17 21 / \ / \ / \ / \ / \ /
0 1 3 4 7 8 10 11 15 16 18 19 22 ---------------------------------- 0 1 2 3 4 5 6 7 8 9 10 11 12 <-- 叶子节点索引 ----------------------------------