譯者注：以太坊網路是一臺富狀態（stateful）的世界計算機，其狀態包括狀態餘額、交易流水號（nonce）、合約程式碼及合約儲存內容等。在技術上，這些狀態資料是靠一種叫做 “默克爾樹” 的結構來組織的，因此，以太坊世界狀態及其訪問、更新，便可表達為一棵默克爾樹及其訪問、更新。同樣地，所有跟默克爾樹相關的資料證明及驗證操作，都可以在以太坊協議的語境下被理解為狀態的證明及驗證操作。實際上，默克爾樹是我們理解、利用、改進以太坊協議不可或缺的一環。
本文介紹了一種可以證明多個值存在於同一棵默克爾樹上的方法，因此也可以說，這就是在介紹如何證明多個以太坊狀態隸屬於同一時刻的世界狀態的方法。
什麼是默克爾截頂
稀疏默克爾樹多值證明（sparse merkle multiproofs）是對默克爾樹截頂（merkle pollard）的一種替代方案，可在為證明一棵默克爾樹上存在多個值時提供空間上較為節約的證明。什麼是默克爾證明、默克爾樹截頂，我已在前一篇文章中解釋過了；推薦您先閱讀並理解這些概念再來閱讀本文。接下來，文字將用下圖的默克爾樹來解釋多值證明：
-圖 1：一棵默克爾樹-
稀疏多值證明最早由 vitalik buterin 提出。
多值證明
多值證明（multiproof）就是把一棵默克爾樹中的一組證明打包在一起，從而節省儲存空間。例如，下面是上圖所示默克爾樹的 3 條默克爾證明：
-圖 2、3、4：分別對應 banana、peach 和kumquat 的默克爾證明-
從上圖可以看出，3 個證明總共包含 9 箇中間分支的雜湊值（即由綠色標出的部分）：每條證明有 3 個雜湊值。將這 3 個證明組合成如下圖所示的結構，即成多值證明：
-圖 5：對應 banana、peach 和kumquat 的默克爾多值證明-
相比於單條證明時總共需要的 9 箇中間分支雜湊值，默克爾多值證明只需要 7 個雜湊值，這就節省了儲存空間。
稀疏的多值證明
雖然默克爾樹的多值證明確實節省了一些儲存空間，但其中一些資料可以用其他方式得到，所以移除這些資料可以進一步節省儲存空間。（譯者注：可透過其他方式得到的資料，就不需要儲存在證明中，只要在需要時能夠得到即可）
以上圖的默克爾樹多值證明為例，許多中間分支的雜湊值都可以被計算出來。 比如驗證者將已知的值 banana 和 peach 透過雜湊函式計算後，可以得到雜湊值 bc4f…8d3f 和 59a0…421d。對於與根節點相連的兩個節點的雜湊值 c0b7…da30 和 6ff9…8e3d，可以透過其孩子節點（與兩個節點直接相連的，並處於上方的節點）的雜湊值計算出來。因為孩子節點的雜湊值要麼是證明中包含的，要麼可以透過再上一層的雜湊值計算出來。下圖中黃色的節點標記了這 4 個可由計算得到的雜湊值：
-圖 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
至此可以把最終得到的雜湊值與默克爾樹的根雜湊值做比較，如果二者一致，則認定所有的值都在該默克爾樹中。
下圖對比了默克爾樹中值和證明的數量變化時，默克爾樹截頂和默克爾樹中稀疏的多值證明在儲存默克爾證明時可以節約的空間儲存量：
| 底層值的數量 | 證明個數 | 截頂方法節約率 | 多值證明節約率（近似） |
|---|---|---|---|
| 1024 | 16 | 20% | 44% |
| 1024 | 32 | 29% | 55% |
| 1024 | 64 | 38% | 64% |
| 1024 | 128 | 48% | 75% |
| 4096 | 128 | 40% | 61% |
| 16384 | 128 | 34% | 50% |
| 65536 | 128 | 30% | 42% |
值得注意的是，多值證明的節省量是近似值，因為能節省多少取決於被證明的值在默克爾樹中的位置以及可以被移除的中間分支雜湊值個數。
對比稀疏多值證明與默克爾截頂
從上表中可以看出，稀疏的多值證明比默克爾樹截頂節省更多的儲存空間，那麼為什麼還要使用默克爾樹截頂呢？因為稀疏的多值證明相對於默克爾樹截頂，擁有一些不同的特性，主要有以下幾點：
- 在多值證明方法中，所有值的證明都是一起生成、一起得到驗證的；而在截頂方法中，各個值的證明是分別生成、分別驗證的（譯者注：生成及驗證時，對截頂來說，具體是哪個值，只需要這個值和相關的證明即可，對於多值證明，則需要把要驗證的多個值，以及多個值對應的證明都拿出來）
- 稀疏的多值證明在生成及驗證證明時，需要更多的記憶體和 cpu 週期
- 稀疏的多值證明很難並行地生成和驗證
- 稀疏的多值證明的大小是可變的，而默克爾樹截頂在給定默克爾樹和總證明數時，其證明大小是固定的
- 一些情況下，因為用於傳輸資訊的編碼系統不同，可能會導致稀疏的多值證明比默克爾樹截頂需要更多的空間；因此建議使用之前做一下測試
總的來說，還要看單個應用的需求來決定哪個更合適。但是這兩種方法都比單獨的默克爾證明節省更多的儲存空間，因此當需要對同一棵默克爾樹提供多個證明時，可以考慮使用這兩種方法。
實現樣例
https://github.com/wealdtech/go-merkletree/ 提供了稀疏的默克爾樹多值證明的實現，採用了 go 語言。
本文僅作分享學習用。原文連結: https://www.wealdtech.com/articles/understanding-sparse-merkle-multiproofs/ 作者: jim mcdonald 翻譯&校對: 裴奇 & 阿劍
