默克尔树 维基百科，自由的百科全书 跳转到导航跳转到搜索
二进制哈希树的示例。哈希0-0和0-1分别是数据块L1和L2的哈希值，哈希0是哈希0-0和0-1串联的哈希。 在密码学和计算机科学中，哈希树或Merkle树是一棵树，其中每个叶节点都用数据块的密码哈希标记，每个非叶节点都用其子节点的标签密码哈希标记。 。哈希树允许对大型数据结构的内容进行有效且安全的验证。哈希树是哈希列表和哈希链的概括。
为了证明叶节点是给定的二叉哈希树的一部分，需要计算与树的叶节点数的对数成正比的哈希数。[1]这与哈希列表相反，哈希列表的数量与叶节点本身的数量成正比。
哈希树的概念以Ralph Merkle的名字命名，他于1979年申请了专利。[2] [3]
内容 1个 用途 2 概述 2.1 第二次原像攻击 2.2 老虎树哈希 2.2.1 例子 3 也可以看看 4 参考 5 进一步阅读 6 外部链接 使用 哈希树可用于验证在计算机之间以及计算机之间存储，处理和传输的任何类型的数据。它们可以帮助确保从对等网络中从其他对等方接收的数据块不会受到损坏和更改，甚至可以检查其他对等方是否在说谎并发送伪造的数据块。
哈希树用于基于哈希的加密中。哈希树还用于IPFS，Btrfs和ZFS文件系统[4]（以应对数据降级[5]）；Dat协议；Apache Wave协议；[6] Git和Mercurial分布式修订控制系统；的太浩-LAFS备份系统; 零网络; 的比特币和复仇的对等网络; [7]的证书透明度框架; 和一些NoSQL系统，例如Apache Cassandra，Riak和Dynamo。[8] 已提出在可信计算系统中使用哈希树的建议。[9]
中本聪（Satoshi Nakamoto）最初对Merkle树进行比特币实现时，过度使用了哈希函数的压缩步骤，这可以通过使用Fast Merkle Trees来缓解。[10]
概述 哈希树是树的哈希值，其中叶数据的哈希值块中，例如，一个或多个文件的集合。树中更远的节点是其各自子节点的哈希值。例如，在图像的散列0是散列的结果级联的散列0-0和散列0-1。也就是说，哈希0 = hash（hash（0-0）+ hash（0-1）），其中+表示串联。
大多数哈希树实现都是二进制的（每个节点下有两个子节点），但它们也可以在每个节点下使用更多的子节点。
通常，加密散列函数（例如SHA-2）用于散列。如果哈希树仅需要防止意外损坏，则可以使用不安全的校验和，例如CRC。
在哈希树的顶部，有一个顶部哈希（或根哈希或主哈希）。在p2p网络上下载文件之前，大多数情况下，顶部哈希是从可信任的来源获取的，例如，众所周知的朋友或网站对下载文件有很好的建议。当顶部哈希可用时，可以从任何不受信任的来源（如p2p网络中的任何对等方）接收哈希树。然后，针对受信任的顶级哈希检查接收到的哈希树，如果哈希树已损坏或伪造，则将尝试使用另一来源的另一哈希树，直到程序找到与顶级哈希匹配的哈希树为止。[11]
与哈希列表的主要区别在于，即使尚无法使用整个哈希树，也可以一次下载哈希树的一个分支，并且可以立即检查每个分支的完整性。例如，在图片中，如果树已经包含哈希0-0和哈希1，则可以通过对数据块进行哈希处理并将结果与哈希0-0进行迭代组合，然后再将哈希1与最终哈希进行组合，从而立即验证数据块L2的完整性比较结果与顶部哈希。类似地，如果树已经具有哈希1-1和哈希0，则可以验证数据块L3的完整性。。这是一个优势，因为将文件分割成非常小的数据块非常有效，这样，如果损坏了，只有很小的块需要重新下载。如果散列文件很大，则此类散列树或散列表会变得相当大。但是，如果它是一棵树，则可以快速下载一个小分支，可以检查分支的完整性，然后可以开始下载数据块。[需要引用]
第二次原像攻击 Merkle散列根不指示树的深度，因此可以进行二次原像攻击，在这种攻击中，攻击者创建的文档不同于具有相同Merkle散根的原始文档。对于上面的示例，攻击者可以创建一个包含两个数据块的新文档，其中第一个是哈希0-0 +哈希0-1，第二个是哈希1-0 +哈希1-1。[12] [13]
证书透明性中定义了一个简单的解决方法：在计算叶节点哈希时，哈希数据前添加0x00字节，而在计算内部节点哈希时前添加0x01。[11] 限制哈希树的大小是一些正式的安全证明的先决条件，并且有助于使某些证明更加严格。一些实现使用散列在散列之前的哈希树深度前缀来限制树的深度，因此，只有当前缀在每一步减小时，并且当到达叶时仍为正，任何提取的散列链才被定义为有效。
老虎树哈希 老虎树哈希是哈希树的一种广泛使用的形式。它使用二进制哈希树（每个节点下有两个子节点），通常数据块大小为1024字节，并使用Tiger哈希。[14]
老虎树哈希用于Gnutella，[15] Gnutella2和Direct Connect P2P文件共享协议[16]，以及文件共享应用程序中，例如Phex，[17] BearShare，LimeWire，Shareaza，DC ++ [18]和Valknut。[19]
例子 Base32：R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ
URN：urn:tree:tiger:R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ
磁铁：magnet:?xt=urn:tree:tiger:R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ
