什么是默克尔树？ 该区块链组件的初学者指南

默克尔树是区块链的基本组成部分，支撑其功能。 它们允许对大型数据结构进行高效、安全的验证，对于区块链来说，还可以验证潜在的无限数据集。

默克尔树在区块链中的实施具有多重效果。 它允许它们进行扩展，同时还为它们提供基于哈希的架构来维护数据完整性以及验证数据完整性的简单方法。

加密哈希函数是默克尔树发挥作用的基础技术，因此首先了解什么是加密哈希函数非常重要。

快速裁决： Merkle 树是由加密哈希组成的数据结构，允许高效的完整性验证和大型数据集的映射，使它们成为区块链和分布式版本控制等系统的组成部分。

重点速览

加密哈希函数

简而言之，哈希函数是用于将任意大小（输入）的数据映射到固定大小输出的任何函数。 哈希算法应用于数据输入，所得的固定长度输出称为哈希。

许多哈希算法已广泛公开提供，可以根据您的需要进行选择。

任意输入产生的散列不仅长度固定，而且对于输入来说也是完全唯一的，并且函数本身是确定性的。 也就是说，无论对同一输入运行该函数多少次，输出始终是相同的。

例如，如果您有以下数据集作为输入，则每个输入的结果输出都是唯一的。 请注意，在第二个和第三个示例中，即使输入的差异只有一个单词，但生成的输出却完全不同。

这非常重要，因为它允许对数据进行“指纹识别”。

加密哈希函数，图片来自维基百科

由于输出（示例中的哈希和）长度始终与所使用的哈希算法确定的长度相同，因此可以仅通过生成的哈希来识别大量数据。

对于包含大量数据的系统，能够存储和识别具有固定长度输出的数据的好处可以节省大量存储空间并有助于提高效率。

在区块链中，哈希算法用于确定区块链的状态。

区块链是包含数据和指向前一个块的哈希指针的链表，创建了连接块的链，因此称为“区块链”。

每个块通过哈希指针相互连接，该指针是前一个块内的数据的哈希值以及前一个块的地址。 通过以这种格式链接数据块，前一个块的每个结果哈希代表了区块链的整个状态，因为前一个块的所有哈希数据都被哈希为一个哈希。

这由如下输出（哈希）表示（在 SHA-256 算法的情况下）：

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

上面的哈希是之前区块链整个状态的指纹。 新块之前的区块链状态（作为散列数据）是输入，产生的散列是输出。

尽管可以在没有 Merkle 树的情况下使用加密哈希，但它效率极低且不可扩展。 使用哈希值以系列格式将数据存储在块中既耗时又麻烦。

正如您将看到的，Merkle 树允许对数据完整性进行简单解析，并使用 Merkle 证明在整个树中映射该数据。

Merkle 树和 Merkle 证明

Merkle 树以 Ralph Merkle 的名字命名，他于 1979 年获得了该概念的专利，Merkle 树本质上是一种数据结构树，其中每个非叶节点都是其各自子节点的哈希值。

叶节点是树中最低层的节点。 乍一听可能很难理解，但是看看下面常用的图，就会变得容易理解多了。

二叉哈希树的示例，图片来自维基百科

重要的是，请注意左侧的非叶节点或“分支”（由哈希 0-0 和哈希 0-1 表示）是其各自子节点 L1 和 L2 的哈希值。 此外，请注意分支 Hash 0 是其串联子分支、分支 Hash 0-0 和 Hash 0-1 的哈希。

上面的例子是最常见和最简单的 Merkle 树形式，称为二元 Merkle 树。 正如你所看到的，有一个顶部哈希，它是整个树的哈希，称为根哈希。 本质上，默克尔树是一种数据结构，可以采用“n”个哈希值并用单个哈希值表示。

树的结构允许有效映射任意大量的数据，并能够轻松识别数据发生变化的位置。 这个概念使得 Merkle 证明成为可能，通过该证明，人们可以验证数据的哈希值在树上一直一致并且处于正确的位置，而无需实际查看整个哈希集。

相反，他们可以通过仅检查哈希的一小部分而不是整个数据集来验证数据块与根哈希是否一致。

只要根哈希是公开已知和可信的，任何想要在数据库上进行键值查找的人都可以使用 Merkle 证明来验证数据库中某条数据的位置和完整性。一个特定的根。

当根哈希可用时，可以从任何不可信源接收哈希树，并且可以一次下载树的一个分支，并立即验证数据完整性，即使整棵树尚不可用。

Merkle 树结构最重要的好处之一是能够通过类似的哈希机制来验证任意大的数据集，该哈希机制用于验证更少量的数据。

该树有利于将大量数据分布到可管理的较小部分中，尽管整体数据大小较大，但完整性验证的障碍却大大减少。

根哈希可以用作整个数据集的指纹，包括整个数据库或代表区块链的整个状态。 在下面的部分中，我们将讨论比特币和其他系统如何实现 Merkle 树。

比特币中的默克尔树

比特币采用的加密哈希函数是 SHA-256 算法。 这代表“安全哈希算法”，其输出长度固定为 256 位。 比特币中默克尔树的基本功能是存储并最终修剪每个区块中的交易。

如前所述，区块链中的块通过前一个块的哈希值连接。 在比特币中，每个块包含该块内的所有交易以及块头，块头包括：

• 区块版本号
• 上一个区块哈希
• 时间戳
• 挖矿难度目标
• 杜撰
• 默克尔根哈希

下图来自比特币白皮书，说明了 Merkle 树如何融入每个区块。

矿工将交易包含到区块中，并作为 Merkle 树的一部分进行哈希处理，从而得出存储在区块头中的 Merkle 根。 这种设计有许多独特的优点。

最值得注意的是，正如白皮书中所述，这允许存在简单支付验证（SPV）节点，也称为“轻量级客户端”。 这些节点不必下载整个比特币区块链，只需下载最长链的区块头。

SPV 节点可以通过查询其对等节点直到确信它们正在操作的存储块头是最长链的一部分来实现此目的。 然后，SPV 节点能够使用 Merkle 证明将交易映射到特定 Merkle 树，并在作为最长链一部分的块头中使用相应 Merkle 树的根哈希来确定交易的状态。

此外，比特币的 Merkle 树实现允许对区块链进行修剪以节省空间。 这是因为只有根哈希存储在块头中的结果，因此，可以通过删除 Merkle 树不必要的分支来修剪旧块，同时只保留 Merkle 证明所需的分支。

Merkle Tree 在其他区块链和系统中的实现

尽管比特币是第一个实现 Merkle 树的区块链，但许多其他区块链也实现了类似的 Merkle 树结构甚至更复杂的版本。

此外，默克尔树的实现不仅限于区块链，还应用于各种其他系统。

以太坊是另一种最知名的加密货币，也是不同 Merkle 树实现的一个很好的例子。 由于以太坊是图灵完备的平台，可用于构建更复杂的应用程序，因此它使用更复杂版本的 Merkle 树，称为 Merkle Patricia 树，它实际上是用于三种对象的 3 个独立的 Merkle 树。 您可以在这里了解有关这些树的更多信息。

最后，Merkle 树是 Git 和 IPFS 等分布式版本控制系统的重要组成部分。 它们能够轻松确保和验证计算机之间以 P2P 格式共享的数据的完整性，这使得它们对于这些系统来说非常宝贵。

结论

默克尔树是区块链不可或缺的组成部分，有效地允许它们以可证明的不变性和交易完整性来运行。

随着加密货币不断发展成为更大、更复杂的系统，了解它们在分布式网络中所扮演的角色及其加密哈希函数的底层技术对于掌握加密货币的基本概念至关重要。