如何在同一棵默克爾樹上提供多個證明

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

科普 | 什么是默克爾截頂

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

如何在同一棵默克爾樹上提供多個證明

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

多值證明

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

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

如何在同一棵默克爾樹上提供多個證明

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

稀疏的多值證明

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

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

如何在同一棵默克爾樹上提供多個證明