什麼是稀疏默克爾樹多值證明

編者按：本文來自：以太坊愛好者（ID：ethfans）編者按：本文來自：

以太坊愛好者（ID：ethfans）

以太坊愛好者（ID：ethfans）

一級標題

編者按：本文來自：

一級標題

圖片描述

一級標題

稀疏默克爾樹多值證明（Sparse Merkle multiproofs）是對默克爾樹截頂（Merkle pollard）的一種替代方案，可在為證明一棵默克爾樹上存在多個值時提供空間上較為節約的證明。什麼是默克爾證明、默克爾樹截頂，我已在前一篇··文章中解釋過了；推薦您先閱讀並理解這些概念再來閱讀本文。接下來，文本將用下圖的默克爾樹來解釋多值證明：

圖片描述

圖片描述

圖片描述

圖片描述

多值證明

圖片描述

圖片描述

圖片描述

-圖5：對應Banana、Peach 和Kumquat 的默克爾多值證明-

圖片描述

圖片描述

雖然默克爾樹的多值證明確實節省了一些存儲空間，但其中一些數據可以用其他方式得到，所以移除這些數據可以進一步節省存儲空間。 （譯者註：可通過其他方式得到的數據，就不需要存儲在證明中，只要在需要時能夠得到即可）

• 圖片描述

• 圖片描述

• -圖6：默克爾樹多值證明中可以被移除的哈希值（見黃色標記）-

• 移除這些哈希值後，可以得到默克爾樹中稀疏的多值證明，如下圖所示：

• 圖片描述

• -圖7：稀疏的默克爾樹多值證明-

• 稀疏的默克爾樹多值證明將需要包含的哈希值數量從9 個減少到了3 個。證明效果相同時，稀疏的多值證明也比默克爾截頂更有效，因為後者需要6 個哈希值。

• 驗證者得到稀疏的多值證明後，為了驗證那些值是默克爾樹的一部分，需要執行以下的步驟（在默克爾樹中，依照從左到右，從上到下的順序）：

（譯者註：“將某個值哈希”指：將值作為哈希函數的輸入，得到隨機的一串輸出）

將Banana 哈希得到bc4f…8d3f

將Peach 哈希得到59a0…421d

將Kumquat 哈希得到2aab…6f791

將bc4f…8d3f 和59a0…421d哈希得到9c15…5dec

• 將2aab…6f79 和45cf…14d9哈希得到a6e4…87df

• 將d596…66ef 和9c15…5dec 哈希得到c0b7…da30

• 將e336…ed14 和a6e4…87df 哈希得到6ff9…8e3d

• 將c0b7…da30 和6ff9…8e3d 哈希得到d576…ffd9

• 至此可以把最終得到的哈希值與默克爾樹的根哈希值做比較，如果二者一致，則認定所有的值都在該默克爾樹中。

下圖對比了默克爾樹中值和證明的數量變化時，默克爾樹截頂和默克爾樹中稀疏的多值證明在存儲默克爾證明時可以節約的空間存儲量：

值得注意的是，多值證明的節省量是近似值，因為能節省多少取決於被證明的值在默克爾樹中的位置以及可以被移除的中間分支哈希值個數。