在加密货币的世界中，Merkle树被用作证明特定值存在于具有最小存储空间的大量值中的有效方式。本文介绍了Merkle树，并展示了如何通过存储多个级别的分支（称为“Merkle pollards”）来显着减少同一树的重复校样。

哈希

散列函数将可变大小的数据块（在这种情况下，水果的名称）转换为固定大小的值（称为“散列值”）。下面是一个显示“Apple”和“Orange”哈希值的示例。:

散列函数有各种各样的函数，但最重要的是即使稍微不同的值会产生非常不同的散列，并且从散列值返回到值在数学上非常困难（通常意味着没有它比猜测散列更快）看到匹配方法）。

Merkle树

Merkle树是一种组合多个值及其哈希值的方法，可将它们减少为单个固定大小的值。

树的顶部是值，称为“叶子”。每个叶子散列用于创建顶级分支，并且相邻的子散列值被添加在一起以创建中间分支。最后，这将产生一个名为Merkle root的哈希值。下面是Merkle树:

的图形示例

上面的例子显示了一个具有8个值和4个级别的树;根位于底部，标记为0xd576 ... ffd9。

如前所述，即使略有不同的值也会产生非常不同的哈希值。此更改将对树的所有级别产生后续影响，并最终生成不同的根。例如，将单个值“Peach”更改为“Pear”会导致Merkle树发生变化，如下所示。:

单个更改对树的影响（以灰色显示）

Merkle树是可重复的。:在相同的顺序中给定相同的值，Merkle树的分支和根总是具有相同的散列值。

Merkle路径

Merkle路径是从值到Merkle根的散列值的集合。以下示例显示值“Peach”:
的Merkle路径

桃子的Merkle路径

Merkle证明

Merkle proof是一种证明值是一组数据的一部分而无需暴露任何其他值的方法。

Merkle证明

Merkle证明需要三件事。:一个值（用红色表示），一个中间散列（用绿色表示）和一个Merkle根（用蓝色表示）。对于每个值，存在一组不同的中间散列值。

Merkle样张通常用于区块链中，表示某个值在集合中，而不将整个集合存储在区块链中。例如，以太坊令牌合同可能具有白名单功能，允许选择帐户来购买令牌。不是将帐户存储在区块链中的每个白名单上（如果白名单上有数千个帐户，这将是非常昂贵的），最好创建帐户的Merkle树并将其仅存储在区块链中。在根上。

注意Merkle路径中的哈希值与最后两个图中所示的证明中的哈希值之间的关系。:证明中的每个哈希值都是树中同一级别路径中哈希值的兄弟。 。这生动地展示了为值重建路径的能力，这就是为什么最终结果将是Merkle根。

如上所述，使用Merkle证明的一些好处是:

·所需的链式存储远小于存储值
·完整的值集不会公开存储在链中
·通过检查证明确认一组值中特定值的成本更低（更快，更便宜）

重复的证明

在上面的示例中，每个帐户只发送一个证明它们在白名单上的证据。 Merkle树的另一个用途是作为概率知识证明（通常称为STARK）的一部分，其中每个证明都增加了Merkle树的创建者（称为“证明者”）知道所有值的可能性。在树上。性别。在这种情况下，验证器通常为包含数十甚至数十万个值的单个Merkle树生成数百个证明。 Merkle的根与证据一起发送给验证者以确认其有效性。

在我们的原始示例的上下文中检查重复的证明。以下是同一棵树的三个证明:

用相同的Merkle根重复证明

正如您所看到的，发送Merkle根（一次）以及需要发送总共10个哈希的证明:哈希值用于根，并且每个证明使用三个哈希值。

这更有效吗？可以看出，在树的第一层中，只有两个值c0b7 ... da30和6 ff9 ... 8e3d，这证明总共发送了三个哈希值（每个哈希值一个）证明）。

使用扩展的Merkle根重复证明

正如你所看到的，发送扩展的Merkle根（一次）和证明现在涉及发送9个哈希值为:的根有3个哈希值，每个哈希值证明有2个哈希值。尽管这种减少似乎很小，但随着样张数量的增加，它会显着增加。

Merkle pollards

我们将延伸的Merkle根称为Merkle pollards。它被定义为Merkle根加上几层中间分支。 Merkle pollards是在树的根部上方形成bullards的分支数（树的Merkle pollards顺序为0，相当于树的根）。第一级Merkle pollard包含一级中间分支，如下所示。:

二阶Merkle pollards由两个中间分支组成，如下所示。:

Merkleplarlard使用Merklepollard来减少相同Merkle树的两个样张的大小和时间验证，在许多重复样张的情况下。计算Merkle pollards最优阶的数学是证明基2对数的基数。下面是一个低级表，以及由它保存的空间和时间:

使用Merkle pollard可以快速提高Merkle pollard的优势，节省不同的订单使用量。例如，使用Merkle pollards充分测试564KB Merkle根的使用减少到346KB，减少了40％。在传输和验证证书所花费的时间内也出现了减少。