默克尔树（Merkle tree），也称为二进制哈希树，是一种用于计算机科学应用的数据结构。在区块链技术的背景下，默克尔树用于更高效、更安全地编码区块链数据。^[1]​

概述

在比特币的区块链中，一组交易区块通过算法运行以生成哈希值，哈希值是一串数字和字母，可用于验证给定的一组数据是否与原始交易集相同。每笔交易都会被哈希处理，然后每两笔交易连接在一起并再次进行哈希处理，依此类推，直到整个区块产生一个哈希值。这种结构类似于一棵树，底层的哈希被称为“叶子”，中间的哈希被称为“分支”，顶部的哈希被称为“根”。

给定区块的默克尔根存储在区块头中。默克尔树允许用户在不下载整个区块链的情况下验证特定交易。例如，如果有人想验证某个特定交易是否包含在区块中，可以向网络查询该交易的哈希值，网络将返回必要的哈希值以验证一切都已入账。^[1]​^[4]​^[7]​

默克尔树的主要目的是验证数据的完整性。默克尔树是确保区块链技术安全性和效率的基础。在区块链技术背景下，它具有以下几个重要用途：

• 高效且安全的数据验证： 默克尔树允许对大型数据集进行高效且安全的验证。这在数据量巨大且不断增长的区块链技术中至关重要。
• 交易验证： 例如，在比特币区块链中，默克尔树允许用户在不下载整个区块链的情况下验证特定交易。这对于轻量级的 SPV（简单支付验证）客户端特别有用，它们只下载区块链的一个子集来验证交易。
• 数据完整性和一致性： 存储在区块头中的默克尔根有助于确保区块中所有交易的完整性和一致性。如果任何一笔交易发生变化，都会导致不同的默克尔根。
• 防止双重支出： 通过确保每个交易区块都引用前一个区块，默克尔树有助于防止双重支出，这是数字现金方案中的一个潜在缺陷，即用户可以多次消费同一笔钱。

历史

默克尔树的概念最早由 Ralph Merkle 在 1987 年的一篇题为《基于传统加密函数的数字签名》的论文中提出。他还发明了加密哈希技术。默克尔树背后的技术于 1989 年获得专利。

在比特币发明之前，密码学被用于软件开发以保护数据安全。在以公钥密码学闻名的 Merkle 引入默克尔树用于验证点对点网络中的数据完整性后，他随后引入了哈希概念，作为一种新的验证行为模式。默克尔树现在用于各种应用，包括点对点网络、分布式系统和区块链技术。它们是比特币和以太坊等加密货币运行的基础。^[1]​^[5]​^[9]​

默克尔树的类型

根据每个父节点可以拥有的子节点数量，默克尔树有不同的类型。一些例子包括：^[8]​

• 二进制默克尔树：这是最简单且最常见的默克尔树类型，每个父节点只有两个子节点。它们用于高效地总结和验证大型数据集，如文件或交易。
• 帕特里夏树（Patricia trees）：这是一种更复杂的默克尔树类型，在以太坊中用于处理智能合约的交易。帕特里夏树每个父节点可以有更多的子节点，使其适用于更复杂的操作。

使用案例

默克尔树具有广泛的应用，特别是在需要数据完整性检查的系统中。以下是一些著名的应用，默克尔树的应用也扩展到了许多其他领域：^[2]​^[7]​^[10]​

• 加密货币： 默克尔树是比特币和以太坊等加密货币运行的基础。它们用于高效地存储和验证区块中的交易。
• 分布式系统： 诸如点对点网络之类的分布式系统使用默克尔树来确保从其他节点接收的数据块未损坏且未被篡改。
• 文件系统： 诸如星际文件系统 (IPFS)、Btrfs 和 ZFS 等文件系统使用默克尔树来对抗数据降解。
• 数据库： 像 Dynamo DB 和 Apache Cassandra 这样可扩展的数据库使用默克尔树。
• 证书透明度： 证书颁发机构使用默克尔树来验证证书透明度。
• 数字签名： 默克尔树用于数字签名中。
• 数据完整性检查： 任何需要检查不一致性的系统都可以使用默克尔树。
• 股票交易： 需要跟踪每日股票交易活动的应用程序是默克尔树可能派上用场的完美示例。

示例

默克尔树实现的一些示例如下：^[7]​

• IPFS：IPFS 是一种用于在分布式文件系统中存储和共享文件的点对点协议。IPFS 使用默克尔树将文件和目录表示为默克尔 DAG（有向无环图）。DAG 中的每个节点都由唯一的哈希标识，指向其他节点的链接作为数据的一部分进行编码。这允许在网络上进行高效的数据去重、验证和同步。
• ZFS：ZFS 是一种提供数据完整性、压缩、加密和快照等功能的文件系统。ZFS 使用默克尔树来存储文件系统的元数据，如文件名、大小、权限和校验和。每个数据块都有一个存储在其父块中的校验和，形成一棵终止于根块的树。这允许检测和纠正数据损坏，并验证快照和备份的一致性。
• 以太坊：以太坊是一个支持智能合约和去中心化应用的区块链平台。以太坊使用默克尔树来存储网络状态，如账户、余额、交易和合约代码。以太坊使用一种称为帕特里夏树的默克尔树变体，它每个父节点可以有两个以上的子节点，并且可以高效地存储键值对。帕特里夏树能够实现数据存在与否的快速证明，以及轻客户端协议。