什么是 Merkle Tree？
Merkle Tree 是一种数据结构，可以将大量记录压缩为一个简短的指纹。它允许你只检查少量片段而非全部内容，就能证明某项存在于巨大的列表中。想象一棵家谱树，每个父节点都是其子节点的摘要，最终汇总到一个顶端祖先。
常见误解
有人认为 Merkle Tree 会“存储”所有交易本身。并非如此。它只存储交易的紧凑指纹，并且可以在需要时由原始记录重建整棵树。
Merkle Tree 的工作原理
想象一组付款需要一个快速且可验证的摘要。下面用通俗的话介绍 Merkle Tree 的做法：
- 步骤 1：从事务等项目列表开始，每项作为树的叶节点。
- 步骤 2：使用 哈希函数 将每项变成简短的指纹。
- 步骤 3：将相邻指纹配对，合并后再哈希，生成父节点。
- 步骤 4：重复配对与哈希的过程，直到只剩一个顶端指纹。那就是该集合的 Merkle root。
- 步骤 5：要证明某项属于该集合，只需该项及一条短的兄弟节点指纹路径。既快又小。
要点是：证明小且验证可靠。
为何 Merkle Tree 很重要
通过将大量的 交易数据 归纳为一个紧凑的指纹，Merkle Tree 使验证变得快速且成本低。
- 优点：你可以检查包含性而无需下载整个区块，从而节省时间和带宽。
- 视角：它符合当下互联网的氛围：相信但要验证，就像名表遇上 Reddit 讨论。
- 相关性：你会在 Bitcoin 区块、Ethereum 回执、NFT 允许名单、空投以及 rollups 中遇到它。
提示
如果叶子节点数量为奇数，许多实现会在上行哈希前复制最后一个节点。此外，请仔细核对你的链或库所使用的具体 哈希过程，因为细微规则差异可能改变证明。
Merkle Tree 的主要特性
以下是让它特别且实用的几点：
- 效率：即便数据集非常庞大，证明仍然很小，因此轻客户端可以保持轻量。
- 完整性：修改叶子中的一个字节会连带影响到顶端，使篡改变得明显。
- 根：一切汇总为一个单一的 Merkle root，可以被存储或签名以便后续校验。
变体
Merkle Tree 有几种常见变体：
- 二叉：经典的成对树结构，用于 Bitcoin 区块。
- Merkle Patricia：基于 trie 的结构，用于键值数据，应用于 Ethereum 状态和回执。
- 稀疏：一个巨大的索引树，大多数叶子为空，适合简洁的存在与不存在证明。
- Verkle：一种较新的变体，对大分支提供更短的证明，正在为未来升级进行探索。
提醒
Merkle Tree 的证明可信度取决于你所接受的区块头或检查点。如果信任了错误的根，即便证明再完整也没有实际意义。
示例
一种类似 Bitcoin 的轻钱包可以通过检查从你的交易到区块头的一条短哈希路径来验证付款，而无需下载整个 交易历史。
趣闻
Ralph Merkle 在七十年代末作为学生项目勾勒出这个想法，它在学术界沉淀多年，直到 Satoshi 在 Bitcoin 中采用。证明了好点子经得起时间考验。
总结
结论？Merkle Tree 提供快速且微小的证明，能表明某项属于大集合，无需繁琐操作或大量下载。