Merkle 樹結構

默克爾樹(又叫哈希樹)是一種典型的二叉樹結構,由一個根節點、一組中間節點和一組葉節點組成。默克爾樹最早由 Merkle Ralf 在 1980 年提出,曾廣泛用於文件系統和 P2P 系統中。

其主要特點爲:

  • 最下面的葉節點包含存儲數據或其哈希值。

  • 非葉子節點(包括中間節點和根節點)都是它的兩個孩子節點內容的哈希值。

進一步地,默克爾樹可以推廣到多叉樹的情形,此時非葉子節點的內容爲它所有的孩子節點的內容的哈希值。

默克爾樹逐層記錄哈希值的特點,讓它具有了一些獨特的性質。例如,底層數據的任何變動,都會傳遞到其父節點,一層層沿着路徑一直到樹根。這意味樹根的值實際上代表了對底層所有數據的“數字摘要”。

目前,默克爾樹的典型應用場景包括如下幾種。

快速比較大量數據

對每組數據排序後構建默克爾樹結構。當兩個默克爾樹根相同時,則意味着所代表的兩組數據必然相同。否則,必然不同。

由於 Hash 計算的過程可以十分快速,預處理可以在短時間內完成。利用默克爾樹結構能帶來巨大的比較性能優勢。

快速定位修改

以下圖爲例,基於數據 D0……D3 構造默克爾樹,如果 D1 中數據被修改,會影響到 N1,N4 和 Root。

因此,一旦發現某個節點如 Root 的數值發生變化,沿着 Root --> N4 --> N1,最多通過 O(lgN) 時間即可快速定位到實際發生改變的數據塊 D1。

零知識證明

仍以上圖爲例,如何向他人證明擁有某個數據 D0 而不暴露其它信息。挑戰者提供隨機數據 D1,D2 和 D3,或由證明人生成(需要加入特定信息避免被人複用證明過程)。

證明人構造如圖所示的默克爾樹,公佈 N1,N5,Root。驗證者自行計算 Root 值,驗證是否跟提供值一致,即可很容易檢測 D0 存在。整個過程中驗證者無法獲知與 D0 相關的額外信息。

Last updated