在密码学和计算机科学的哈希树或Merkle树类型的数据结构,其中包含一个树一块较大的数据的汇总信息-例如:一个文件用来验证其内容。哈希树的组合由哈希列表和哈希链,进而扩展成为哈希。 哈希树可以用来验证任何一种存储,处理和和计算机之间传输数据。目前,哈希树的主要用途是确保收到从其他同行在对等网络接收到的数据块损坏和改变,甚至检查的其他同龄人不撒谎,并发送伪造的块。建议使用哈希树可信计算系统。Sun公司已经在哈希树的ZFS文件系统[ 1 ]哈希树中使用谷歌Wave协议,[ 2 ] Git的分布式版本控制系统,塔霍LAFS备份。系统,Bitcoin同行-to-peer网络,和一些像 Apache 的NoSQL系统的卡桑德拉及Riak [ 3 ] 拉尔夫Merkle哈希树在1979年发明的。[ 4 ]的最初目的是使有可能有效地处理许多兰波特一次性签名。兰波特签名被认为仍然是安全的事件,量子计算机成为现实。不幸的是每个兰波特密钥只能用于签署一个单一的消息。但结合哈希树,可用于许多消息,然后成为一个相当有效的数字签名方案。 在哈希树的顶部有一个哈希(或根哈希或主哈希)。在P2P网络上下载一个文件之前,在大多数情况下,最高的哈希从信任的来源取得,例如朋友或一个网站,被称为有好的建议下载文件。当顶部的哈希,哈希树可以接收任何非信任的来源,就像任何P2P网络中的同行。然后,收到的散列树对信任的顶级哈希检查,如果哈希树被损坏或假冒,另一个将尝试从其他来源的哈希树,直到找到一个相匹配的顶级哈希程序。 哈希列表从一个主要区别是哈希树的一个分支,可以下载的时间和各分支的完整性,可以立即进行检查,整棵树,即使是尚未公布。例如,在图片的完整数据块2可以核实立即如果树已经包含哈希0-0和1哈希散列数据块和迭代相结合的结果与哈希0-0,然后哈希1,终于比较顶部哈希结果。同样,完整的数据块3,可以验证,如果树已有哈希1-1和哈希0的。这可以是一个优势,因为它是在非常小的数据块分割的文件,这样只有小块,如果他们被损坏,必须redownloaded高效。如果哈希文件是非常大的,这样一个哈希树或哈希列表变得相当大。但如果它是一棵树,一个小分支可以快速下载,可以检查的分支的完整性,然后可以开始下载数据块。 |