Merkle树与根：数据验证利器

什么是 Merkle 树？

Merkle 树的概念由计算机科学家 Ralph Merkle 在 80 年代早期提出，他以其在公钥密码学领域的贡献而闻名。Merkle 树是一种用于高效验证数据集完整性的结构，尤其在点对点网络中，它允许参与者共享和独立验证信息。Merkle 树的核心是哈希函数，所以在继续阅读前，建议了解一下什么是哈希。

Merkle 树的工作原理

假设你想要下载一个大文件。在使用开源软件时，你通常会希望检查你下载的文件的哈希值是否与开发者公布的哈希值相匹配。如果匹配，那么你可以确定你的电脑上的文件与他们的文件完全一致。

如果哈希值不匹配，那就麻烦了。你可能下载了一个伪装成软件的恶意文件，或者文件没有正确下载，因此无法正常工作。如果是后者，你可能会对等待了那么长时间却无法使用文件感到不满。现在，你需要重新开始下载过程，并希望文件不会再次损坏。

幸运的是，Merkle 树在这里派上了用场。使用 Merkle 树，你可以将文件分成小块。如果是一个 50GB 的文件，你可能会将其分成一百个 0.5GB 大小的片段，然后逐块下载。这与你通过 torrent 下载文件的方式类似。

在这种情况下，源文件会提供给你一个称为 Merkle 根的哈希值。这个单一的哈希值代表了构成文件的每个数据块。但 Merkle 根使得数据验证变得更加容易。

为了简单起见，我们以一个 8GB 的文件为例，将其分成八个片段，分别标记为 A 到 H。每个片段通过哈希函数处理后，得到八个不同的哈希值。我们将每对哈希值组合并再次哈希，比如 hA 和 hB，hC 和 hD，hE 和 hF，hG 和 hH，这样我们得到四个哈希值。然后我们再次对这四个哈希值进行哈希处理，得到两个哈希值。最后，我们对剩下的两个哈希值进行哈希处理，得到最终的 Merkle 根（或根哈希）。

这个结构看起来像是一棵倒置的树。底部一行是叶子，它们被组合起来产生节点，最终形成根。我们现在有了代表我们下载的文件的 Merkle 根。我们可以将这个根哈希与源文件提供的进行比较。如果匹配，完美！但如果哈希值不同，我们可以确定数据被修改了。换句话说，一个或多个片段产生了不同的哈希值。任何微小的数据修改都会导致完全不同的 Merkle 根。

幸运的是，我们有办法检查哪个片段有问题。假设是 hE 出错了。你会先向一个对等节点请求产生 Merkle 根的两个哈希值（hABCD 和 hEFGH）。你的 hABCD 应该与他们的匹配，因为那部分子树没有错误。但 hEFGH 不会匹配，所以你知道问题出在那儿。然后你请求 hEF 和 hGH，并与你的进行比较。hGH 看起来没问题，所以你知道 hEF 有问题。最后，你比较 hE 和 hF 的哈希值。现在你知道 hE 不正确，你可以重新下载那个块。

总的来说，Merkle 树是通过将数据分成许多小块，然后反复进行哈希处理来形成 Merkle 根的。你可以高效地验证数据是否出错。下一节我们将看到还有其他有趣的应用。

为什么在比特币中使用 Merkle 根？

Merkle 树有许多用例，但这里我们将重点讨论它们在区块链中的重要性。Merkle 树在比特币和其他许多加密货币中是必不可少的。它们是每个区块的重要组成部分，可以在区块头中找到。我们使用区块中每笔交易的交易哈希（TXID）作为树的叶子。

挖矿

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

矿工需要反复哈希数据以生成符合特定条件的输出，从而挖掘出一个有效的区块。他们可能需要尝试上万亿次。在每次尝试中，他们更改区块头中的一个随机数（nonce）以产生不同的输出。但区块的大部分内容保持不变。尽管有数千笔交易，你仍然需要每次都对它们进行哈希处理。

Merkle 根大大简化了这个过程。当你开始挖矿时，你排列所有你想要包含的交易并构建一个 Merkle 树。你将生成的根哈希（32 字节）放入区块头中。然后，在挖矿时，你只需要对区块头进行哈希处理，而不是整个区块。

这是因为它是防篡改的。你有效地将区块的所有交易以紧凑的格式进行了总结。你不能找到一个有效的区块头然后再更改交易列表，因为这会改变 Merkle 根。当区块发送给其他节点时，他们会从交易列表中计算根。如果它与头中的不匹配，他们会拒绝该区块。

验证

Merkle 根还有另一个我们可以利用的有趣属性。这与轻客户端（不持有区块链完整副本的节点）有关。如果你在资源有限的设备上运行一个节点，你不希望下载和哈希整个区块的所有交易。你可以做的就是请求一个 Merkle 证明——由完整节点提供的证据，证明你的交易在特定区块中。这通常被称为简化支付验证（SPV），由 Satoshi Nakamoto 在比特币白皮书中详细描述。

假设我们想知道 TXID 为 hD 的交易的信息。如果提供了 hC，我们可以计算出 hCD。然后，我们需要 hAB 来计算 hABCD。最后，使用 hEFGH，我们可以检查生成的 Merkle 根是否与区块头中的匹配。如果匹配，这就是证明该交易被包含在区块中——使用不同的数据几乎不可能生成相同的哈希值。

在上面的例子中，我们只需要哈希三次。没有 Merkle 证明，我们需要哈希七次。由于现在的区块包含数千笔交易，使用 Merkle 证明为我们节省了大量的时间和计算资源。

结语

Merkle 树在计算机科学的多个应用中证明了它们的价值——正如我们所见，它们在区块链中非常有用。在分布式系统中，Merkle 树允许轻松验证信息，而无需向网络发送不必要的数据。

没有 Merkle 树（和 Merkle 根），比特币和其他加密货币的区块不会像今天这样紧凑。虽然轻客户端在隐私和安全方面有所欠缺，但 Merkle 证明使用户能够以最小的开销检查他们的交易是否已被包含在区块中。