DeFi之道丨V神發文詳述Verkle樹結構，與以太坊現在的證明大小相比小30倍

原文作者：以太坊創始人Vitalik Buterin。

V神認為Verkle 樹正在成為以太坊即將進行的擴展升級的重要組成部分。Verkle 樹是 Merkle 證明的強大升級，允許更小的證明尺寸。不需要在每個層級提供所有“姐妹節點”，證明者只需要提供一個證明來證明沿着從每個葉節點到根的路徑的所有承諾之間的所有父子關係。這使得證明大小與理想的 Merkle 樹相比小了約 6-8 倍，與以太坊今天使用的十六進制 Patricia 樹相比小了 20-30 倍以上（！！）。

特別感謝 Dankrad Feist 和 Justin Drake 的反饋和審查。

Verkle 樹正在成為以太坊即將進行的擴展升級的重要組成部分。它們具有與默克爾（Merkle） 樹相同的功能：您可以將大量數據放入 Verkle 樹中，並對可以通過以下方式驗證的任何單個或一組數據進行簡短證明（“見證witness”），並且僅擁有樹根的人都可以對此進行驗證。然而，Verkle 樹提供的關鍵特性是它們在證明大小方面效率更高。如果一個樹包含 10 億條數據，在傳統的二叉 Merkle 樹中進行證明將需要大約 1 KB，但在 Verkle 樹中，此證明將少於 150B——這一減少足以使無狀態客戶端最終在實踐中可行。

Verkle 樹仍然是一個新想法；它們由 John Kuszmaul 在 2018 年發表的論文中首次提出，但它們至今仍然不如許多其他重要的新密碼結構那樣為人所知。這篇文章將解釋什麼是 Verkle 樹以及它們背後的密碼學魔法是如何工作的。其短證明大小的代價是對更複雜的密碼學的依賴程度更高。也就是說，在我看來，密碼學仍然比現代 ZK SNARK 方案中的高級密碼學簡單得多。在這篇文章中，我將盡我所能來解釋它。

Merkle Patricia樹 vs. Verkle樹節點結構

就樹的結構（樹中節點的排列方式以及它們包含的內容）而言，Verkle 樹與目前以太坊中使用的 Merkle Patricia 樹非常相似。每個節點要麼是 (i) 空的，要麼是包含一個密鑰（key）和值的葉節點，要麼是 (iii) 具有固定數量子節點（樹的“寬度”）的中間節點。中間節點的值計算為其子節點值的哈希。

值在樹中的位置基於其key：在下圖中，要到達key為 4cc 的節點，從根開始，然後向下到達位置 4 處的子節點，然後向下到達子節點在位置 c（記住：十六進制中的 c = 12），然後再次下降到位置 c 的子位置。要到達帶有key baaa 的節點，請轉到根節點的位置 b 子節點，然後是該節點的位置 a 子節點。路徑 (b,a) 處的節點直接包含key為 baaa 的節點，因為樹中沒有其他以 ba 開頭的key。

Verkle 樹和 Merkle Patricia 樹結構的唯一真正區別在於 Verkle 樹在實踐中更廣泛。 當寬度（width） = 2 時，Patricia 樹的效率最高（因此以太坊的十六進制Patricia 樹實際上是次優的）。 另一方面，Verkle 樹的寬度越高，證明越短； 唯一的限制是，如果寬度變得太高，則證明的創建時間會過長。 為以太坊提議的 Verkle 樹的寬度為 256，有些人甚至贊成將其提高到 1024 (!!)。

承諾(Commitments)和證明

在 Merkle 樹（包括 Merkle Patricia 樹）中，值的證明由整個姐妹節點集組成：證明必須包含樹中的所有節點，這些節點與路徑中的任何節點共享一個父節點 您要證明的節點。 理解起來可能有點複雜，所以這裡有一張證明 4ce 位置值的圖片。 必須包含在證明中的姐妹節點以紅色突出顯示。

這是很多節點！您需要在每個級別提供姐妹節點，因為您需要一個節點的整個子節點集來計算該節點的值，並且您需要繼續這樣做直到到達根節點。您可能認為這並沒有那麼糟糕，因為大多數節點都是零，但這只是因為這棵樹的節點很少。如果這棵樹有 256 個隨機分配的節點，則頂層幾乎可以肯定所有 16 個節點都已滿，而第二層將平均滿 63.3%。

另一方面，在 Verkle 樹中，您不需要提供姐妹節點；相反，您只需提供路徑，並提供一點額外的證明。這就是為什麼 Verkle 樹受益於更大的寬度而 Merkle Patricia 樹則沒有：在這兩種情況下，更大寬度的樹會導致更短的路徑，但在 Merkle Patricia 樹中，這種效果被需要提供所有寬度的更高成本所淹沒，因為需要提供一個證明中每級中所有width-1的姐妹節點。在 Verkle 樹中，該成本不存在。

那麼作為一個證明，我們需要這個額外的東西是什麼？ 要理解這一點，我們首先需要回到一個關鍵細節：用於從其子節點計算內部節點的哈希函數不是常規哈希。 相反，這是一個向量承諾（Vector commitment）。

向量承諾方案是一種特殊類型的哈希函數，對一個列表進行哈希化。 但是向量承諾具有特殊屬性，即對於一個承諾和一個值 ，可以做一個簡短的證明，即對某個列表的承諾，也就是第 i 個位置的值的位置 。 在 Verkle 證明中，這個簡短的證明取代了 Merkle Patricia 證明中姐妹節點的功能，讓驗證者相信子節點確實是其父節點給定位置上的子節點。

在實踐中，我們使用比向量承諾更強大的原語，稱為多項式承諾。多項式承諾讓您可以對多項式進行哈希，並在任何時候為哈希多項式的評估提供證明。您可以使用多項式承諾作為向量承諾：如果我們就一組標準化坐標（c1,c2,……cn）達成一致，則給定一個列表（y1,y2,…yn），您可以承諾多項式P，其中P（ci）=Yi，i屬於[1…n]（您可以通過拉格朗日插值找到這個多項式）。我在關於 ZK-SNARKs 的文章中詳細討論了多項式承諾。最容易使用的兩種多項式承諾方案是 KZG 承諾和防彈式（bulletproof）承諾（在這兩種情況下，一個承諾都是一個 32-48 字節的橢圓曲線點）。多項式承諾為我們提供了更大的靈活性，讓我們能夠提高效率，而且恰好可用的最簡單和最有效的向量承諾是多項式承諾。

該方案已經非常強大：如果您使用 KZG 承諾和證明，則證明大小為每個中間節點 96 字節，如果我們設置寬度 = 256，則空間效率比簡單的 Merkle 證明高近 3 倍。然而，它事實證明，我們可以進一步提高空間效率。

合併證明

通過使用多項式承諾的額外屬性，我們不需要為路徑上的每個承諾提供一個證明，而是可以製作一個固定大小的證明，以為無限數量的密鑰證明路徑上承諾之間的所有父子鏈接。我們使用通過隨機評估實現多重證明的方案來做到這一點。

但是要使用這個方案，我們首先需要將問題轉換成一個更結構化的問題。我們有 Verkle 樹中一個或多個值的證明。該證明的主要部分由通往每個節點的路徑上的中間節點組成。對於我們提供的每個節點，我們還必須證明它實際上是它上面（並且在正確位置）節點的子節點。在上面的單值證明示例中，我們需要證明（proof）來證明：

• key: 4ce 節點實際上是前綴: 4c 中間節點的位置e 子節點。
• 前綴（prefix）：4c中間節點實際上是前綴：4中間節點的位置c子節點。
• 前綴(prefiex)：4中間節點實際上是根的位置4子節點

如果我們有證明多個值的證明（例如 4ce 和 420），我們將擁有更多節點和更多鏈接。但無論如何，我們要證明的是一系列形式為“節點 A 實際上是節點 B 的位置 i 子節點”的語句。如果我們使用多項式承諾，這將變成等式：A(xi)=y ，其中y是承諾的哈希值。

這個證明的細節是技術性的，Dankrad Feist比我自己解釋得更好。到目前為止，證明生成中最笨重和耗時的步驟涉及計算以下形式的多項式：

如果該表達式是多項式（而不是分數），則只能計算每個項

。 這需要Ai（X）在位置xi上等於yi。

我們可以通過一個例子看到這一點。 假如：

Ai（X）=X²+X+3

我們正在證明（xi=2;y2=9） . 如果Ai（2）=9，則這會起作用。

Ai（X）-9=X²+X+6，且（X²+X-6）/（X-2）能被X-3整除。如果我們用（xi=2,yi=10），公式不成立。(X²+X-7)並不能被X-2整除且沒有小數餘數。

證明的其餘部分涉及提供一個多項式承諾g(X)，然後證明承諾實際上是正確的。 再一次，請參閱 Dankrad 的更多技術說明以了解證明的其餘部分。

一個證明可以證明無限數量的父子關係。

我們有了它，這就是最大效率的 Verkle 證明的樣子。

使用此方案的證明大小的關鍵屬性

• Dankrad 的多隨機評估證明允許證明者證明任意數量的定值Ai（xi）=yi，給定對每個Ai承諾以及正在證明的值。此證明大小恆定（一個多項式承諾、一個數字和兩個證明；128-1000 字節取決於所使用的方案）。
• 不需要明確提供yi值，因為它們可以直接從 Verkle 證明中的其他值計算出來：每個yi值本身就是路徑中下一個值的哈希值（一個承諾或一個葉（leaf））。
• 也不需要明確提供xi值，因為可以從key和從路徑導出的坐標計算路徑（以及xi值）。
• 因此，我們所需要的只是我們正在證明的葉（key和值），以及從每個葉到根的路徑上的承諾。
• 假設一個寬度為 256 的樹和2的32次方個節點，證明將需要被證明的key和值，加上（平均）從該值到根的路徑上的每個值的三個承諾。
• 如果我們要證明許多值，則可以進一步節省：無論您要證明多少個值，您都不需要提供超過 256 個頂層值。

證明大小（字節）。行：樹大小；列：已證明的key/值對

假設寬度為 256 和 48 字節的 KZG 承諾/證明。 另請注意，這假設樹最大為偶數； 對於現實的隨機樹，添加 ~0.6 的深度（因此每個元素 ~30 字節）。 如果使用防彈風格的承諾而不是 KZG，那麼減少到 32 字節是安全的，因此這些大小可以減少 1/3。

證明者和驗證者計算負載

生成證明的大部分成本是計算每個

表達式。 這需要大約四次字段運算（即 256 位模算術運算）乘以樹的寬度。 這是限制 Verkle 樹寬度的主要約束。 幸運的是，四個字段操作的成本很小：單個橢圓曲線乘法通常需要數百個字段操作。 因此，Verkle 樹的寬度可以非常高； 寬度 256-1024 似乎是最佳範圍。

要編輯樹，我們需要從葉子到根“沿着樹向上走”，在每一步更改中間承諾以反映發生在較低位置的更改。 幸運的是，我們不必從頭開始重新計算每個承諾。 相反，我們利用同態性質：給定一個多項式承諾 C=com（F） ，我們可以通過取C‘=C+com（F）來計算C’=com（F+G）。 在我們的例子中，G=Li *（Vnew-Vold），其中Li是多項式的預先計算的承諾，在我們試圖改變的位置等於 1，在其他地方等於 0。

因此，單次編輯需要約 4 次橢圓曲線乘法（葉和根之間的每個承諾一個，這次包括根），儘管可以通過預先計算和存儲每個Li 的許多倍數來大大加快速度。

證明驗證非常有效。 對於 N 個值的證明，驗證者需要執行以下步驟，對於甚至數千個值，所有這些步驟都可以在一百毫秒內完成：

• 一種大小為N的橢圓曲線快速線性組合
• 大約 4N 個字段操作（即 256 位模算術運算）
• 不依賴於證明大小的少量恆定工作量

另請注意，與 Merkle Patricia 證明一樣，Verkle 證明為驗證者提供了足夠的信息來修改被證明的樹中的值，並在應用更改後計算新的根哈希。 這對於驗證例如。 區塊中的狀態更改已正確處理。

結論

Verkle 樹是 Merkle 證明的強大升級，允許更小的證明尺寸。不需要在每個層級提供所有“姐妹節點”，證明者只需要提供一個證明來證明沿着從每個葉節點到根的路徑的所有承諾之間的所有父子關係。這使得證明大小與理想的 Merkle 樹相比小了約 6-8 倍，與以太坊今天使用的十六進制 Patricia 樹相比小了 20-30 倍以上（！！）。

Verkle樹確實需要更複雜的密碼學來實現，但它們提供了獲得可擴展性巨大收益的機會。從中期來看，SNARK 可以進一步改進：我們可以對已經高效的 Verkle 證明驗證器進行 SNARK 以將見證大小減少到接近於零，或者如果/當 SNARK 變得更好時（例如通過 GKR）切換回 SNARKed Merkle 證明，或非常 SNARK 友好的哈希函數，或 ASIC）。更進一步，量子計算的興起將迫使使用哈希的 STARKed Merkle 證明進行更改，因為它使 Verkle 樹所依賴的線性同態變得不安全。但就目前而言，它們為我們提供了與使用這些更先進的技術相同的擴展好處，而且我們已經擁有有效實施它們所需的所有工具。