订阅 wiki
Share wiki
Bookmark
Merkle Tree
Merkle Tree
Merkle 树，也称为二叉哈希树，是一种用于计算机科学应用中的数据结构。在区块链技术的背景下，Merkle 树用于更高效、安全地编码区块链数据。[1]
概述
在比特币的区块链中，一个区块的交易通过一个算法运行，以生成一个哈希值，这是一个数字和字母的字符串，可用于验证给定的数据集与原始交易集是否相同。每个交易都被哈希，然后每对交易被连接并一起哈希，依此类推，直到整个区块只有一个哈希值。这种结构类似于一棵树，底部行的哈希值被称为“叶子”，中间的哈希值被称为“分支”，顶部的哈希值被称为“根”。
给定区块的 Merkle 根存储在头部。Merkle 树允许用户在不下载整个区块链的情况下验证特定交易。例如，如果有人想验证特定交易是否包含在一个区块中，他们可以查询网络关于该交易的哈希值，它将返回必要的哈希值来验证一切都已考虑在内。[1][4][7]
- 高效、安全的数据验证： Merkle 树允许对大型数据集进行高效、安全的验证。这在区块链技术中至关重要，因为数据量可能非常大并且不断增长。
- 交易验证： 例如，在比特币的区块链中，Merkle 树允许用户在不下载整个区块链的情况下验证特定交易。这对于轻量级的 SPV（简化支付验证）客户端特别有用，它们仅下载区块链的一个子集来验证交易。
- 数据完整性和一致性： 存储在区块头中的 Merkle 根有助于确保区块中所有交易的完整性和一致性。如果任何单个交易发生更改，都将导致不同的 Merkle 根。
- 防止双重支付： 通过确保每个交易区块都引用前一个区块，Merkle 树有助于防止双重支付，这是一种数字现金方案中潜在的缺陷，用户可以多次花费同一笔钱。
历史
Merkle 树的概念最初由 Ralph Merkle 在 1987 年发表的一篇题为“基于传统加密功能的数字签名”的论文中提出。他还发明了密码哈希。Merkle 树背后的技术于 1989 年获得专利。
在比特币发明之前，密码学被用于软件开发中以保护数据。在以公钥密码学闻名的 Merkle 引入 Merkle 树以验证对等网络中的数据完整性之后，他随后引入了哈希的概念，作为一种新的验证行为模式。Merkle 树现在用于各种应用中，包括对等网络、分布式系统和区块链技术。它们是比特币和以太坊等加密货币运行的基础。[1][5][9]
Merkle 树的类型
根据每个父节点可以拥有的子节点数量，Merkle 树有不同的类型。一些例子是：[8]
- 二叉 Merkle 树： 这些是最简单、最常见的 Merkle 树类型，其中每个父节点只有两个子节点。它们用于有效地总结和验证大型数据集，例如文件或交易。
- Patricia 树： 这是一种更复杂的 Merkle 树类型，在以太坊中用于处理智能合约的交易。Patricia 树每个父节点可以有更多的子节点，使其适用于更复杂的操作。
用例
Merkle 树具有广泛的应用，尤其是在需要数据完整性检查的系统中。以下是一些值得注意的应用，Merkle 树的应用也扩展到许多其他领域：[2][7][10]
- 加密货币： Merkle 树是比特币和以太坊等加密货币运行的基础。它们用于有效地存储和验证区块中的交易。
- 分布式系统： 诸如对等网络之类的分布式系统使用 Merkle 树来确保从其他对等方接收的数据块以未损坏和未更改的方式接收。
- 文件系统： 诸如 InterPlanetary File System (IPFS)、Btrfs 和 ZFS 之类的文件系统使用 Merkle 树来对抗数据降级。
- 数据库： 诸如 Dynamo DB 和 Apache Cassandra 之类的可扩展数据库使用 Merkle 树。
- 证书透明度： 证书颁发机构使用 Merkle 树来验证证书透明度。
- 数字签名： Merkle 树用于数字签名。
- 数据完整性检查： 任何需要检查不一致性的系统都可以使用 Merkle 树。
- 股票交易： 需要跟踪每日股票交易活动的应用程序是 Merkle 树可能有用处的一个完美例子。
例子
Merkle 树的一些实现示例是：[7]
- IPFS： IPFS 是一种对等协议，用于在分布式文件系统中存储和共享文件。IPFS 使用 Merkle 树将文件和目录表示为 Merkle DAG（有向无环图）。DAG 中的每个节点都由唯一的哈希标识，并且与其他节点的链接被编码为数据的一部分。这允许跨网络高效地进行数据去重、验证和同步。
- ZFS： ZFS 是一种文件系统，提供诸如数据完整性、压缩、加密和快照之类的功能。ZFS 使用 Merkle 树来存储文件系统的元数据，例如文件名、大小、权限和校验和。每个数据块都有一个校验和，该校验和存储在其父块中，形成一棵以根块结尾的树。这允许检测和纠正数据损坏，以及验证快照和备份的一致性。
- 以太坊： 以太坊 是一个区块链平台，支持智能合约和去中心化应用程序。以太坊使用 Merkle 树来存储网络的状态，例如帐户、余额、交易和合约代码。以太坊使用 Merkle 树的一种变体，称为 Patricia 树，每个父节点可以有两个以上的子节点，并且可以有效地存储键值对。Patricia 树能够快速证明数据的存在和不存在，以及轻客户端协议。
发现错误了吗？