哈希树
一种树，其中每个非叶子节点都用它的子节点的标签或值（如果是叶子）的哈希值来标记
哈希树（hash tree；Merkle tree），在密码学及计算机科学中是一种树形数据结构，每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签 。哈希树能够高效、安全地验证大型数据结构的内容，是哈希链的推广形式[1]。
概述
哈希树中，哈希值的求取通常使用诸如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