哈希樹

哈希樹（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 網絡中的非受信來源獲取。下載得到哈希樹後，即可根據可信的頂部哈希對其進行校驗，驗證數據是否完整、是否遭受破壞。