Merkle Mountain Range

这个crate是Tari加密货币项目的一部分。

Merkle mountain range是由Peter Todd发明的。更多关于它们的信息可以在这里阅读 这里 和 这里

Merkle mountain range(MMR)是一种二叉树，其中每个父节点是其两个子节点哈希值的连接。MMR底部的叶子是数据的哈希。MMR允许在树内轻松添加和证明存在。MMR总是试图拥有尽可能大的单个二叉树，因此实际上可能存在多个二叉树。每次需要获取Merkle根（整个MMR的单个Merkle证明）时，你都会有袋中的山峰，或者说是山峰。

lib.rs:

Merkle Mountain Ranges

简介

默克尔山脊由彼得·托德发明。更多详情可以阅读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 $$

节点编号

在MMR中节点编号可能会引起一些混淆。在这个crate中使用了以下约定

• 所有索引都是从零开始的。
• MMR节点指的是默克尔山脊中的所有节点，并按上述标准MMR排序。
• 叶子节点编号从零开始，每次添加一个叶子节点时递增。

为了说明，考虑以下MMR

           14
         /     \
        /       \
       6        13          21          <-- MMR indices
     /  \      /  \        /  \
    /    \    /    \      /    \
    2    5    9    12    17    20
   / \  / \  / \  / \   / \   / \
   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  <-- Leaf node indices
   ----------------------------------