譯者注：以太坊網(wǎng)絡(luò)是一臺(tái)富狀態(tài)（stateful）的世界計(jì)算機(jī)，其狀態(tài)包括狀態(tài)余額、交易流水號(hào)（nonce）、合約代碼及合約存儲(chǔ)內(nèi)容等。在技術(shù)上，這些狀態(tài)數(shù)據(jù)是靠一種叫做 “默克爾樹(shù)” 的結(jié)構(gòu)來(lái)組織的，因此，以太坊世界狀態(tài)及其訪問(wèn)、更新，便可表達(dá)為一棵默克爾樹(shù)及其訪問(wèn)、更新。同樣地，所有跟默克爾樹(shù)相關(guān)的數(shù)據(jù)證明及驗(yàn)證操作，都可以在以太坊協(xié)議的語(yǔ)境下被理解為狀態(tài)的證明及驗(yàn)證操作。實(shí)際上，默克爾樹(shù)是我們理解、利用、改進(jìn)以太坊協(xié)議不可或缺的一環(huán)。本文介紹了一種可以證明多個(gè)值存在于同一棵默克爾樹(shù)上的方法，因此也可以說(shuō)，這就是在介紹如何證明多個(gè)以太坊狀態(tài)隸屬于同一時(shí)刻的世界狀態(tài)的方法。

科普 | 什么是默克爾截頂

稀疏默克爾樹(shù)多值證明（Sparse Merkle multiproofs）是對(duì)默克爾樹(shù)截頂（Merkle pollard）的一種替代方案，可在為證明一棵默克爾樹(shù)上存在多個(gè)值時(shí)提供空間上較為節(jié)約的證明。什么是默克爾證明、默克爾樹(shù)截頂，我已在前一篇··文章中解釋過(guò)了；推薦您先閱讀并理解這些概念再來(lái)閱讀本文。接下來(lái)，文本將用下圖的默克爾樹(shù)來(lái)解釋多值證明：

稀疏多值證明最早由 Vitalik Buterin 提出。

多值證明

多值證明（multiproof）就是把一棵默克爾樹(shù)中的一組證明打包在一起，從而節(jié)省存儲(chǔ)空間。例如，下面是上圖所示默克爾樹(shù)的 3 條默克爾證明：

從上圖可以看出，3 個(gè)證明總共包含 9 個(gè)中間分支的哈希值（即由綠色標(biāo)出的部分）：每條證明有 3 個(gè)哈希值。將這 3 個(gè)證明組合成如下圖所示的結(jié)構(gòu)，即成多值證明：

相比于單條證明時(shí)總共需要的 9 個(gè)中間分支哈希值，默克爾多值證明只需要 7 個(gè)哈希值，這就節(jié)省了存儲(chǔ)空間。

稀疏的多值證明

雖然默克爾樹(shù)的多值證明確實(shí)節(jié)省了一些存儲(chǔ)空間，但其中一些數(shù)據(jù)可以用其他方式得到，所以移除這些數(shù)據(jù)可以進(jìn)一步節(jié)省存儲(chǔ)空間。（譯者注：可通過(guò)其他方式得到的數(shù)據(jù)，就不需要存儲(chǔ)在證明中，只要在需要時(shí)能夠得到即可）

以上圖的默克爾樹(shù)多值證明為例，許多中間分支的哈希值都可以被計(jì)算出來(lái)。比如驗(yàn)證者將已知的值 Banana 和 Peach 通過(guò)哈希函數(shù)計(jì)算后，可以得到哈希值 bc4F…8d3f 和 59a0…421d。對(duì)于與根節(jié)點(diǎn)相連的兩個(gè)節(jié)點(diǎn)的哈希值 c0b7…da30 和 6ff9…8e3d，可以通過(guò)其孩子節(jié)點(diǎn)（與兩個(gè)節(jié)點(diǎn)直接相連的，并處于上方的節(jié)點(diǎn)）的哈希值計(jì)算出來(lái)。因?yàn)楹⒆庸?jié)點(diǎn)的哈希值要么是證明中包含的，要么可以通過(guò)再上一層的哈希值計(jì)算出來(lái)。下圖中黃色的節(jié)點(diǎn)標(biāo)記了這 4 個(gè)可由計(jì)算得到的哈希值：

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

稀疏的默克爾樹(shù)多值證明將需要包含的哈希值數(shù)量從 9 個(gè)減少到了 3 個(gè)。證明效果相同時(shí)，稀疏的多值證明也比默克爾截頂更有效，因?yàn)楹笳咝枰?6 個(gè)哈希值。

驗(yàn)證者得到稀疏的多值證明后，為了驗(yàn)證那些值是默克爾樹(shù)的一部分，需要執(zhí)行以下的步驟（在默克爾樹(shù)中，依照從左到右，從上到下的順序）：

（譯者注：“將某個(gè)值哈?！敝福簩⒅底鳛楣：瘮?shù)的輸入，得到隨機(jī)的一串輸出）

將 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

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

下圖對(duì)比了默克爾樹(shù)中值和證明的數(shù)量變化時(shí)，默克爾樹(shù)截頂和默克爾樹(shù)中稀疏的多值證明在存儲(chǔ)默克爾證明時(shí)可以節(jié)約的空間存儲(chǔ)量：

值得注意的是，多值證明的節(jié)省量是近似值，因?yàn)槟芄?jié)省多少取決于被證明的值在默克爾樹(shù)中的位置以及可以被移除的中間分支哈希值個(gè)數(shù)。

對(duì)比稀疏多值證明與默克爾截頂

從上表中可以看出，稀疏的多值證明比默克爾樹(shù)截頂節(jié)省更多的存儲(chǔ)空間，那么為什么還要使用默克爾樹(shù)截頂呢？因?yàn)橄∈璧亩嘀底C明相對(duì)于默克爾樹(shù)截頂，擁有一些不同的特性，主要有以下幾點(diǎn)：

· 在多值證明方法中，所有值的證明都是一起生成、一起得到驗(yàn)證的；而在截頂方法中，各個(gè)值的證明是分別生成、分別驗(yàn)證的（譯者注：生成及驗(yàn)證時(shí)，對(duì)截頂來(lái)說(shuō)，具體是哪個(gè)值，只需要這個(gè)值和相關(guān)的證明即可，對(duì)于多值證明，則需要把要驗(yàn)證的多個(gè)值，以及多個(gè)值對(duì)應(yīng)的證明都拿出來(lái)）

· 稀疏的多值證明在生成及驗(yàn)證證明時(shí)，需要更多的內(nèi)存和 CPU 周期

· 稀疏的多值證明很難并行地生成和驗(yàn)證

· 稀疏的多值證明的大小是可變的，而默克爾樹(shù)截頂在給定默克爾樹(shù)和總證明數(shù)時(shí)，其證明大小是固定的

· 一些情況下，因?yàn)橛糜趥鬏斝畔⒌木幋a系統(tǒng)不同，可能會(huì)導(dǎo)致稀疏的多值證明比默克爾樹(shù)截頂需要更多的空間；因此建議使用之前做一下測(cè)試

總的來(lái)說(shuō)，還要看單個(gè)應(yīng)用的需求來(lái)決定哪個(gè)更合適。但是這兩種方法都比單獨(dú)的默克爾證明節(jié)省更多的存儲(chǔ)空間，因此當(dāng)需要對(duì)同一棵默克爾樹(shù)提供多個(gè)證明時(shí)，可以考慮使用這兩種方法。
責(zé)任編輯；zl