默克尔哈希树：用少量哈希证明一条记录在巨型文件中

证明一条记录属于大型数据集，过去通常需要发送整个数据集。这对于备份、交易文件或网络缓存来说并不现实。

默克尔1979年的学位论文和1989年的论文描述了一棵树，其中每个数据块都被哈希，哈希值成对组合，直到只剩一个根哈希。验证一个成员只需路径上的log n个哈希，而非整个文件。

这棵树将成员测试转化为对根哈希的相等性测试，任何位置的变化都会表现为路径变化。这就是无需看到每个字节就能为整个数据结构作保的方式。

通过两两哈希将叶节点提交到一个根节点

证明规模是对数级的，因此即使数据集极大，验证仍然廉价。

根哈希提交了整个数据集，因此任何篡改都能被发现。

验证者只需要根哈希和短路径，无需信任服务器。

它是单向哈希链，因此不会泄露关于数据的任何信息。

要证明一个巨大整体的某个事实，不要发送整体。将它压缩成一个摘要，然后只给出连接该单一主张与摘要的短路径。

默克尔树是Git、加密货币区块链、证书透明度和分布式存储的基础。它让客户端通过仅信任一个短的根，就能验证大型未认证存储中的一小部分。