區塊鍊技術之密碼學技術之默克爾樹

Merkle 樹

默克爾樹（又叫哈希樹）是一種二叉樹，由一個根節點、一組中間節點和一組葉節點組成。

最下面的葉節點包含存儲資料或其哈希值，每個中間節點是它的兩個孩子節點内容的哈希值，根節點也是由它的兩個子節點内容的哈希值組成。

進一步的，默克爾樹可以推廣到多叉樹的情形。

默克爾樹的特點是，底層資料的任何變動，都會傳遞到其父親節點，一直到樹根。

默克爾樹的典型應用場景包括：

• 快速比較大量資料：當兩個默克爾樹根相同時，則意味着所代表的資料必然相同。
• 快速定位修改：例如上例中，如果 D1 中資料被修改，會影響到 N1，N4 和 Root。是以，沿着 Root --> N4 --> N1，可以快速定位到發生改變的 D1；
• 零知識證明：例如如何證明某個資料（D0……D3）中包括給定内容 D0，很簡單，構造一個默克爾樹，公布 N0，N1，N4，Root，D0 擁有者可以很容易檢測 D0 存在，但不知道其它内容。

有關零知識證明的材料請參考：http://mp.weixin.qq.com/s/ObaVu2-7iGvSrmceNDlQrQ

轉載于:https://www.cnblogs.com/bruceshao/p/8535408.html