哈希树
(重定向自默克尔树)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/9/95/Hash_Tree.svg/220px-Hash_Tree.svg.png)
哈希树(hash tree;Merkle tree),在密码学及计算机科学中是一种树形数据结构,每个叶节点均以数据块的哈希作为标签,而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签 。哈希树能够高效、安全地验证大型数据结构的内容,是哈希链的推广形式[1]。
哈希树的概念由瑞夫·墨克于 1979 年申请专利[2][3],故亦称墨克树(Merkle tree)。
概述
哈希树中,哈希值的求取通常使用诸如SHA-2的加密哈希函数,但如果只是用于防止非故意的数据破坏,也可以使用不安全的校验和取得,比如CRC。
哈希树的顶部为顶部哈希(top hash),亦称根哈希(root hash)或主哈希(master hash)。以从 P2P 网络下载文件为例:通常先从可信的来源获取顶部哈希,如朋友告知、网站分享等。得到顶部哈希后,则整棵哈希树就可以通过 P2P 网络中的非受信来源获取。下载得到哈希树后,即可根据可信的顶部哈希对其进行校验,验证数据是否完整、是否遭受破坏。
参考文献
- ^ Farooq Anjum,Petros Mouchtaris. 无线Ad Hoc 网络安全. 北京:清华大学出版社. 2009.03: 86. ISBN 978-7-302-19337-1.
- ^ Merkle, R. C. A Digital Signature Based on a Conventional Encryption Function. Advances in Cryptology — CRYPTO '87. Lecture Notes in Computer Science 293. 1988: 369. ISBN 978-3-540-18796-7. doi:10.1007/3-540-48184-2_32.
- ^ US patent 4309569,Ralf Merkle,「Method of providing digital signatures」,发表于Jan 5, 1982,指定于The Board Of Trustees Of The Leland Stanford Junior University
延伸閱讀
- Merkle tree patent 4,309,569 – explains both the hash tree structure and the use of it to handle many one-time signatures
- Tree Hash EXchange format (THEX) – a detailed description of Tiger trees
参见
外部連結
- A C implementation of a dynamically re-sizeable binary SHA-256 hash tree (Merkle Tree)(页面存档备份,存于互联网档案馆)
- Merkle Tree implementation in Java(页面存档备份,存于互联网档案馆)
- Tiger Tree Hash (TTH) source code in C#(页面存档备份,存于互联网档案馆), by Gil Schmidt
- Tiger Tree Hash (TTH) implementations in C and Java(页面存档备份,存于互联网档案馆)
- RHash (页面存档备份,存于互联网档案馆), an open source command-line tool, which can calculate TTH and magnet links with TTH
|