图解丨什么是默克尔树（Merkle Tree），又称哈希树

默克尔树（Merkle Tree）又称哈希树，是区块链的底层加密技术，是一种有效验证和维护数据集完整性的结构，被比特币和以太坊区块链广泛采用。验证链上交易往往需要大量空间和算力，但通过构建默克尔树和生成默克尔根，交易可以被打包验证，而不一定非要每一笔交易单独验证。

什么是默克尔树

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

默克尔树是一种自下而上构建的加密树，每个叶子是对应数据的哈希，而每个非叶子为它的2个子节点的哈希，能有效验证数据集的完整性，在需要参与者共享并独立验证信息的点对点网络中更能发挥效用。

默克尔树是一种用于计算机科学应用的数据结构，由各种数据块的哈希函数组成的数学数据结构，汇总了一个块中的所有事务。它还可以跨大型数据集实现快速、安全和一致的内容验证。

在比特币和加密货币类型中，默克尔树树用于更有效、更安全地加密货币区块链数据，因为默克尔树结构提供了一个易于访问的区块中交易记录。

默克尔树图解

什么是默克尔根（Merkle Root）

默克尔根是默克尔树上所有交易的哈希值。 当一个区块上的所有交易都成功配对并得出哈希值后，最终得到的值就是默克尔根，更改任意数据都会导致默克尔根发生变化。

因此，一旦默克尔根生成，即可确保网络上没有任何数据被更改。

默克尔树的工作原理

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

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

你是否考虑过，有没有更简单的方法解决这个问题？这正是默克尔树的用武之地。默克尔树能将文件分解为多个数据块。例如，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，就能检查计算出来的默克尔根是否与区块头中的根哈希值一致。如果成功匹配，就证明交易被计入了区块，因为要想使用不同的数据生成相同的哈希值几乎不可能实现。

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

区块链开发

由于默克尔树是由许多不同数据块的哈希函数（hash）组成的数学数据结构，它总结了一个块中的所有交易，从默克尔树可以实现在大数据上快速安全的内容验证数据集并验证数据一致性。

图-1-4

想象一下，如果比特币不使用默克尔树，网络上的每个节点都必须保留每笔比特币交易的完整副本。正如你可以想象的那样，信息量是巨大的。Merkle Trees 是解决这个问题的一个方案，Merkle Tree 将证明数据与原始数据本身分离，从而减少了必须保存在区块链上的信息量。

区块链中默克尔树的好处

默克尔树有许多不同的用途，以下是五个优势：

验证数据完整性

默克尔树可用于有效验证数据的完整性。当一笔交易完成哈希运算并被存储在区块链上时，初始信息的变化也会导致哈希值的变化。所以，可以通过比较当前哈希值和存储在区块头的哈希值来检测信息是否被篡改。

占用存储空间小

当一笔加密货币交易按照默克尔树结构执行时，经过哈希处理，然后给出一个等价的哈希值。在默克尔树树中对每笔交易进行散列后，生成的散列与另一个散列值连接，然后再次散列。

与其他数据结构相比，默克尔树结构占用的存储空间非常小。

易于验证的有组织和结构化的数据

默克尔树可以分解成小块数据进行验证。哈希值’AB’和’AC’组合起来产生’ABC’。重复连接这些散列的过程，直到生成最终散列。最终哈希提供了块中包含的所有交易的摘要。

验证有效性

默克尔树提供了高效的交易验证方式，数据格式和数据完整性验证只需几分钟。

快速交易

由于所有交易会按对分组并产生单一哈希值，所以信息的链上传输会变得更快。这也是加密货币传输速度非常快的主要原因之一。