雜湊樹

雜湊樹（hash tree；Merkle tree），在密碼學及電腦科學中是一種樹形數據結構，每個葉節點均以數據塊的雜湊作為標籤，而除了葉節點以外的節點則以其子節點標籤的加密雜湊作為標籤 。雜湊樹能夠高效、安全地驗證大型數據結構的內容，是雜湊鏈的推廣形式^[1]。

二元雜湊樹範例。雜湊 0-0 和 0-1 分別是數據塊 L1 和 L2 的雜湊值。雜湊 0 是將雜湊 0-0 和 0-1 連接後所取得的雜湊值。

雜湊樹的概念由瑞夫·墨克於 1979 年申請專利^[2][3]，故亦稱墨克樹（Merkle tree）。

概述

雜湊樹中，雜湊值的求取通常使用諸如SHA-2的加密雜湊函數，但如果只是用於防止非故意的數據破壞，也可以使用不安全的校驗和取得，比如CRC。

雜湊樹的頂部為頂部雜湊（top hash），亦稱根雜湊（root hash）或主雜湊（master hash）。以從 P2P 網絡下載檔案為例：通常先從可信的來源取得頂部雜湊，如朋友告知、網站分享等。得到頂部雜湊後，則整棵雜湊樹就可以通過 P2P 網絡中的非受信來源取得。下載得到雜湊樹後，即可根據可信的頂部雜湊對其進行校驗，驗證數據是否完整、是否遭受破壞。

參考文獻

1. Farooq Anjum,Petros Mouchtaris. 无线Ad Hoc 网络安全. 北京：清華大學出版社. 2009.03: 86. ISBN 978-7-302-19337-1. 請檢查|date=中的日期值 (幫助)
2. 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.
3. 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