案例库 · 软件与 IT · 技术决策 · 1979
默克尔哈希树：用少量哈希证明一条记录在巨型文件中
拉尔夫·默克尔1979年提出的哈希树，将整个数据集提交到一个根哈希，验证任意单条记录只需约log n个哈希，而非整个文件。
斯坦福大学
那一手
证明一条记录属于大型数据集，过去通常需要发送整个数据集。这对于备份、交易文件或网络缓存来说并不现实。
默克尔1979年的学位论文和1989年的论文描述了一棵树，其中每个数据块都被哈希，哈希值成对组合，直到只剩一个根哈希。验证一个成员只需路径上的log n个哈希，而非整个文件。
这棵树将成员测试转化为对根哈希的相等性测试，任何位置的变化都会表现为路径变化。这就是无需看到每个字节就能为整个数据结构作保的方式。
为什么管用
- 证明规模是对数级的，因此即使数据集极大，验证仍然廉价。
- 根哈希提交了整个数据集，因此任何篡改都能被发现。
- 验证者只需要根哈希和短路径，无需信任服务器。
- 它是单向哈希链，因此不会泄露关于数据的任何信息。
值了多少通过两两哈希将叶节点提交到一个根节点神来之笔
可以搬走什么
要证明一个巨大整体的某个事实，不要发送整体。将它压缩成一个摘要，然后只给出连接该单一主张与摘要的短路径。
后来呢
默克尔树是Git、加密货币区块链、证书透明度和分布式存储的基础。它让客户端通过仅信任一个短的根，就能验证大型未认证存储中的一小部分。
资料来源
发现哪里写错了？告诉我们。