默克尔树与默克尔根详解

什么是默克尔树？

80年代初，著名的公钥密码学领域的计算机科学家拉尔夫·默克尔(Ralph Merkle)提出了默克尔树概念。

默克尔树结构能有效验证数据集的完整性，在需要参与者共享并独立验证信息的点对点网络中更能发挥效用。

哈希函数是默克尔树结构的核心。因此，我们建议大家先了解什么是哈希运算，然后再继续阅读本文。

默克尔树的工作原理是什么？

假设您想要下载一个大型文件。使用开源软件下载，通常需要检查下载文件的哈希值是否与开发人员公开的相匹配。如果匹配则说明两份文件一致。

如果哈希值不匹配，那就遇到麻烦了。要么您下载了伪装成软件的恶意文件，要么您就是下载不正确，最终结果都是文件不可用。如果下载不正确，您的心情肯定烦躁，毕竟等待文件下载已经耗费很长时间。现在重头来过，还得期望不再出现同样的问题。

您是否考虑过，有没有更简单的方法解决这个问题？这正是默克尔树的用武之地。默克尔树能将文件分解为多个数据块。例如，50GB的文件可以分解为100份，每份大小为0.5GB。随后，就能逐份下载。这就是种子文件的原理。

此时的文件源就是一个哈希值，称之为默克尔根。这个单一哈希值代表了组成文件的所有数据块。而且，默克尔根能让数据验证变得更加简单。

为了便于理解，我们举例说明。下面将一个8GB的文件分为八份，每个片段分别以A到H命名。随后，每个片段代入哈希函数，得出八个不同的哈希值。

通过哈希函数，计算出八个片段的哈希值。

希望以上示例解释还算易懂。我们有了所有片段的哈希值，如果其中一个出错，是不是对比源文件就能找出问题呢？或许可以，但是这样效率仍然极低。如果文件有成千上万个片段，难道要对所有片段进行哈希运算，再细致对比结果吗？

不需要。我们只需组合一对哈希值，再进行合并哈希运算即可。也就是说，我们用hA + hB、hC + hD、hE + hF以及hG + hH进行哈希运算。结果会得出四个哈希值。随后我们进行下一轮合并哈希运算，直到获得两个哈希值。这两个哈希值再合并运算，最终得出主哈希值，也就是默克尔根（亦称为根哈希值）。

这个结构看起来像一棵倒置的树。底部一排叶子，相互结合产生节点，最后生成根。

现在我们就得到了代表下载文件的默克尔根。将根哈希值与源文件的值进行比较，如果匹配，皆大欢喜！一旦哈希值不同，则证明数据遭到了篡改。换言之，一个或多个片段生成了不同的哈希值。因此，再小的数据修改都会彻底改变默克尔根。

幸好，要检查出错的片段也很方便。假设出错的是hE。首先，我们先向他人要来生成默克尔根的两个哈希值（hABCD和hEFGH）。我们的hABCD值应与他人的匹配，就能证明子树没有错误。如果hEFGH不匹配，我们就能从这里纠错。之后再询问他人的hEF和hGH哈希值，并与自己的比较，如果hGH没问题，则说明hEF是罪魁祸首。最后，我们比较hE和hF的哈希值，一旦发现错误源是hE，那就可以重新下载该数据块。

综上所述，默克尔树的功能就是把数据划分为多份，然后反复哈希运算，最终形成默克尔根，这样就能有效验证究竟是哪里出现了错误数据。下一节中，我们将介绍其他的有趣应用。

比特币中为何使用默克尔根？

默克尔树的用例不算少，但本文着重讨论它在区块链中发挥的重要作用。比特币和众多加密货币都离不开默克尔树。默克尔树是每个区块的组成部分，通常位于区块头。通过区块中每笔交易的交易哈希值(TXID)，我们就能获得树叶。 

在这种情况下，默克尔根有多种用途。我们来看看默克尔根在加密货币挖矿和交易验证中的应用。

挖矿

比特币区块由两部分组成。第一部分为区块头，大小固定，包含区块元数据。第二部分为区块体，大小可变，但通常比区块头要大得多，包含交易列表。

矿工需重复哈希运算数据，直至产出符合特定条件的结果，才能挖出有效区块。为了获得正确结果，他们需要进行数万亿次尝试。每次尝试时，矿工改变区块头的随机数，即Nonce值，以此生成不同的结果。然而，区块的其他部分保持不变，其中的数千笔交易，每次仍需哈希运算。

默克尔根则大大简化了这个流程。开始挖矿时，所有的交易列队打包并构建为默克尔树，生成的32位根哈希值放入区块头。随后，无需再对整个区块进行哈希运算，只要针对区块头运算即可。

这种方式能防止数据篡改，因此切实有效，能够让区块的所有交易以紧凑的形式进行高效汇总。有效区块头的交易列表无法修改，否则将改变默克尔根。区块发送至其他节点后，将从交易列表中计算根哈希值。如果与区块头中的数值不匹配，则可拒绝该区块。

验证

我们还能使用默克尔根另一个有意思的属性，这关系到轻量级客户端（没有保存完整区块链副本的节点）的应用。如果您是在资源有限的设备中运行节点，肯定不希望下载区块中的所有交易并对其进行哈希运算。相反，您只需索要默克尔证明，即由全节点提供的证明交易被计入到特定区块的证据。这个证明更为人熟知的名称是“简单支付验证”或SPV，由中本聪在比特币白皮书中进行了详细说明。

要想检查hD，只需验证红色的哈希值即可。

假设，我们希望获取关于TXID为hD的交易信息。如果hC已知，则可以计算出hCD。然后，通过hAB，就能计算出hABCD。最后，参照hEFGH，就能检查计算出来的默克尔根是否与区块头中的根哈希值一致。如果成功匹配，就证明交易被计入了区块，因为要想使用不同的数据生成相同的哈希值几乎不可能实现。

在上面的示例中，我们只进行三次哈希运算。没有默克尔证明的话，则需要七次。现在的区块包含数千笔交易，而默克尔证明为我们节省了大量的时间和算力。

总结

默克尔树已经证明了自己在计算机科学应用领域的重要作用，正如我们所见，它在区块链中也颇具价值。默克尔树让分布式系统中的信息验证变得更加方便，避免了网络中冗余数据的拥堵。

如果没有默克尔树和默克尔根，比特币和其他加密货币区块不会像如今这般紧凑。虽然轻量级客户端在隐私和安全性方面缺乏优势，但有了默克尔证明，用户就能以最低的费用来验证交易是否计入了区块。