雜湊樹

一种树,其中每个非叶子节点都用它的子节点的标签或值(如果是叶子)的哈希值来标记

雜湊樹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. 
  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 

延伸閱讀

參見

外部連結