Merkle 山脉

这个包是 Tari 加密货币项目的组成部分：Tari 加密货币。

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

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

lib.rs:

Merkle 山脉是由 Peter Todd 发明的，更多关于它们的信息可以在这里阅读：https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md https://github.com/mimblewimble/grin/blob/master/doc/mmr.md

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

让我们通过一个例子来说明如何构建一个。假设您已经有了以下 MMR：''' /
/
/\ /\ /
////\ //\ /
''' 从这里我们可以看到我们有 3 座山。我们已经构建了可能的最大树。如果我们想要计算 Merkle 路径，我们将按以下方式打包每一座山 ''' /
/\
/ \
/\ \
/ \ \
/\ /\ /\
///////
''' 让我们继续这个例子，通过添加一个单独的对象。现在我们的 MMR 如下所示 ''' /
/
/\ /\ /
////\ //\ /\ / ''' 我们现在有 4 座山。让我们再次打包和计算 Merkle 根 ''' /
/\
/\ \
/ \ \
/\ \ \
/ \ \ \
/\ /\ /\ \
///////\
''' 让我们继续这个例子，通过添加一个单独的对象。我们的 Merkle 树现在看起来如下 ''' /
/
/
/
/\ /
/ \ /
/\ /\ /\ /
////////
''' 现在我们只有一个二叉树，我们不需要打包山来计算 Merkle 根。当你向 MMR 添加更多对象时，这个过程会继续。 ''' /
/
/
/
/
/
/
/\
/\ \ /
/ \ \ /
/\ \ \ /\
/ \ \ \ / \
/\ /\ /\ \ /\ /\ /
///////\ //////
''' 由于 MMR 构造的独特方式，我们可以很容易地将 MMR 表示为节点列表，因为当你添加节点时，你只需要附加。让我们看一下下面的 MMR，并按我们创建它们的顺序编号节点。 ''' 7 /
/
3 6 / \ /
1 2 4 5 ''' 从上面创建节点的例子中，你会看到节点将按照它们命名的顺序创建。这意味着我们可以很容易地将它们表示为列表：高度：0 | 0 | 1 | 0 | 0 | 1 | 2 节点：1 | 2 | 3 | 4 | 5 | 6 | 7

由于 MMR 的列表性质，我们可以轻松地使用以下公式在 MMR 中导航：跳转到兄弟节点：2^(H+1) -1 寻找峰值：2^(H+1) -2 其中 < 总元素剩余：2^H 右下：-1 注意，这些公式是为数组的直接索引，这意味着节点从 0 开始计数，而不是像上面例子中的 1。H - 高度 I - 索引

修剪 MMR 意味着将节点标记为已修剪，并且只有在它的兄弟节点被移除后才会移除它。我们这样做是因为我们需要兄弟节点来证明节点的哈希。以上面的例子为例，让我们修剪叶节点 1。 ''' /
/
/
/
/
/
/
/\
/\ \ /
/ \ \ /
/\ \ \ /\
/ \ \ \ / \
/\ /\ /\ \ /\ /\ /
///////\ //////
''' 节点 1 现在已经被标记为已修剪，但我们还不能移除它，因为我们仍然需要它来证明节点 2。当我们修剪节点 2 时，MMR 看起来如下 ''' /
/
/
/
/
/
/
/\
/\ \ /
/ \ \ /
/\ \ \ /\
/ \ \ \ / \
/\ /\ /\ \ /\ /\ /
//////\ //////
''' 尽管我们没有从 MMR 中移除节点 1 和节点 2，但我们还不能移除节点 3，因为我们还需要节点 3 来证明节点 6。让我们修剪 4 和 5。 ''' /
/
/
/
/
/
/
/\
/\ \ /
/ \ \ /
/\ \ \ /\
/ \ \ \ / \
/\ /\ \ /\ /\ /
/////\ //////
''' 现在我们已经从 MMR 中移除了 3