科普 | 什么是 Merkle Pollard

在密码学货币领域， 默克尔树是一种很高效的方法，用于证明一大组数值中存在一个特定的数值，而且将数据存储量降到了最低 。本文介绍了默克尔树，并且展示了如何通过存储多个层级的默克尔树分支而非根节点的方式来大量减少重复证明（即 “默克尔树截顶（Merkle pollard）”）。

哈希函数

哈希函数可以把一段任意长度的数据（即下图中的水果名）变成一个固定长度的值（即“哈希值”）。例如，下图中 “Apple” 和 “Orange” 的哈希值如下所示：

哈希函数有很多特征，其中最显著的两点是：（1）即使输入值仅有毫厘之差，得到的哈希值也会迥然不同；（2）从数学上来说很难根据哈希值倒推出输入值（通常来说，没有比反复试错更快的方法）。

默克尔树

默克尔树指的是将多个输入值和它们的哈希值结合起来压缩成某个固定长度的值。

默克尔树的顶端是各种输入值，被称为“叶节点”。每个叶节点经过哈希得到上一层分支，相邻两个分支拼接在一起之后哈希得到中间支。一层一层哈希之后，最后得到一个哈希值，即默克尔根节点。默克尔树的示例图如下：

上图所示的默克尔树有 8 个输入值，分为 4 层。根节点就是位于最末端的 0xd576...ffd9 。

正如上文所述，即使输入值极为近似，得到的哈希值也是迥然不同的。如果输入值发生了变化，会影响到默克尔树的各个层次，最后得出完全不同的根节点。例如，将输入值中的 “Peach” 改为 “Pear” 之后，这个默克尔树都会发生变化，如下图所示：

默克尔树是可再生的：如果把完全相同的输入值按照同样的顺序排列，默克尔树的分支和根节点始终会得出同样的哈希值。

默克尔路径

默克尔路径指的是某个输入值到默克尔根节点之间所有哈希值的集合。下图显示了输入值 “Peach” 的默克尔路径：

默克尔证明

默克尔证明指的是不需要知道一个数据集合中的其他值就能证明某个值属于这个集合。

默克尔证明需要三样东西：输入值（红色标记）、中间支哈希值（绿色标记）和默克尔根节点（蓝色标记）。每个输入值对应的中间支哈希值集合各不相同。

区块链系统经常会用到默克尔证明，证明某个数据集合内存在某个输入值，这样就不需要将整个数据集合都存储在区块链上了。假设一个以太币合约内有一个白名单列表， 只允许列表内的账户购买以太币。如果将白名单内每个账户信息都存储在区块链上，势必要付出很高的成本。在这种情况下，只需要创建一个默克尔树，再将根节点存储在区块链上即可。

例如，如果将根节点存储在一个智能合约上，这个智能合约很容易就能证明某个账户包含在白名单内：这个账户需提供中间支哈希值（合约所有者通过某种链下方式提供给账户持有者），智能合约将这个账户的哈希值依次与中间支哈希值进行哈希计算。如果最后得出的结果与默克尔根节点一致的话，就证明这个账户确实在白名单里。

请注意最后两张图中默克尔路径和默克尔证明的哈希值之间的关系。在同一棵树的同一个层级中，默克尔证明的哈希值与默克尔路径的哈希值是相互关联的。 由此可见，默克尔证明能够重塑输入值的默克尔路径 ，这就是为什么最终结果是默克尔根节点的原因。

至此，可以看出默克尔证明具有以下特征：

• 在链上存储默克尔证明所需的空间远远小于直接存储输入值所需的空间
• 在链上公开存储默克尔证明也不会暴露整个输入值集合
• 要证明某个输入值集合内是否存在某个值，验证默克尔证明的成本低于核对整个输入值集合的成本

重复证明

在上文的例子中，每个账户只需要发送一个默克尔证明，就能够验证自己是否在白名单上。

此外，默克尔树还可以用作概率性知识证明（通常被称为 STARKs ），每一次知识证明都能使我们（即 “验证者、挑战者”）更加确信：默克尔树的创建者（即 “证明者” ）知道所有的构成值。在这种情况下，证明者通常会根据包含几十个乃至成百上千个输入值的默克尔树生成上百个证明。这些证明会连同默克尔根节点一起发送给验证者，来验证它们的有效性。

让我们紧接着上面的例子来探究重复证明，下面三幅图分别是由同一个默克尔树生成的三个不同的证明：

可以看出总共发送了一个默克尔根节点和三个证明，加起来共有 10 个哈希值：根节点有 1 个，其余三个证明各有 3 个。

有没有效率更高的做法？可以看出默克尔树的第一个层次只有两个值 c0b7...da30 和 6ff9...8e3d ，但（在提供这一层次的哈希值时）三个证明总共发送了 3 个哈希值（每个证明 1 个）。那么，如果一开始提供的部分不仅包括最低层次的哈希值（即默克尔根），还提供更上一层次的哈希值，效率会不会更高？

（校对注：对比上两组图可以发现，第一种证明方式需要发送 10 个哈希值，但第二种证明方式只需要发送 9 个，所以确实提高了效率）

默克尔树截顶

扩展默克尔根也可以说是给默克尔树截顶，也就是只保留默克尔根节点和少数几层中间支。默克尔树截顶的顺序是按照根节点上方的中间支层数决定的（一个 0 阶默克尔截顶即是默克尔根）。1 阶默克尔截顶包含一层中间支，如下图所示：

2 阶默克尔截顶包含两层中间支，如下图所示：

如果同一个默克尔树存在多个重复证明，采用默克尔树截顶会减少证明的大小（因为每个证明所含的哈希值会减少）以及验证证明所需的时间（因为每次验证所需计算的哈希值会减少）。要求得默克尔截顶的最佳阶数，只需对证明数量取 2 的对数，再向下取整。下图是一个低阶默克尔树截顶表，显示了包含 4096 个输入值的默克尔树可节省的空间和时间，如下所示：

使用默克尔树截顶能够节省大量存储空间。例如，一个 STARK 测试证明如果使用的是默克尔根节点，需要 564 KB 的存储空间，如果使用的是默克尔树截顶，只需要 346 KB 的存储空间，减少了 40% 。传输并验证证明所需的时间也会减少。

实现样例

https://github.com/wealdtech/go-merkletree/ 提供了采用 Go 语言实现的默克尔树截顶。

原文链接: https://medium.com/@jgm.orinoco/understanding-merkle-pollards-1547fc7efaa

作者:Jim McDonald

翻译&校对:闵敏 & 阿剑