哈希樹
![](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
|