1. 簡介

2023 年的最後一天，維塔利克在 Twitter 上分享了以太坊 2023 年的路線圖，總結了以太坊一年來的進展。路線圖 “The Verge ”部分描述了以太坊技術如何更簡單、更高效地驗證區塊鏈狀態。其中提到的一個核心概念就是 Verkle 樹。那麼，什麼是 Verkle Trees，爲什麼以太坊需要它，Verkle Trees 又是如何解決問題的呢？本文的目的是在不深入研究密碼學和數學的前提下爲讀者解答這些問題，幫助那些對以太坊有一定了解的讀者快速掌握 Verkle Trees 的概念。

2. 可驗證的查詢

可驗證查詢技術在傳統數據庫領域被廣泛研究，主要用於解決與外部數據庫的信任問題。在很多場景中，數據所有者可能不會選擇自己存儲數據，而是將數據庫需求委托給第三方提供數據庫服務（如雲數據庫）。然而，由於第三方並不總是可信的，因此他們返回給用戶的查詢結果的可信度很難保證。目前針對傳統數據庫的可驗證查詢解決方案主要分爲兩類：基於ADS（認證數據結構）的解決方案和基於可驗證計算的解決方案。

ADS 是一種在傳統數據庫中廣泛使用的可驗證查詢技術，大多建立在哈希樹（Merkle Trees）或類似的累積結構之上。隨着密碼學工具的發展，許多研究人員逐漸開始探索使用可驗證計算技術來解決不可信查詢的問題。一些基於零知識證明協議的可驗證計算方案（如 SNARKs）可以間接支持外部數據庫的可驗證查詢。這些方案支持多種查詢類型，生成的驗證信息較少，但計算開銷較高。

目前，以太坊使用哈希樹來實現可驗證查詢，而 Verkle 樹技術也是基於哈希樹技術。因此，我們先以哈希樹爲例，介紹一下哈希樹，幫助讀者理解可驗證查詢的作用。

3. 哈希樹

3.1. 哈希樹的定義和特點

哈希樹是密碼學中常用的樹狀結構，適用於解決數據完整性問題。下面是一個典型的哈希樹結構：葉子節點代表原始數據或其哈希值，每個非葉子（內部）節點包含其子節點的哈希值組合。

哈希樹有兩個重要特徵：

1. 抗篡改性： 梅克爾樹通常使用抗碰撞散列函數構建，因此要找到產生相同散列值的兩個不同信息在計算上是不可行的。從哈希樹的結構可以看出，對葉節點內的交易數據進行任何修改，都會導致樹根哈希值發生變化。
2. 高效驗證大型數據集的完整性： 驗證者只需存儲哈希樹的根散列值，即可驗證任何數據的完整性。要做到這一點，無需傳輸完整的數據集，而是通過使用從葉到根的路徑上的同級節點-梅克爾路徑（Merkle Path）。這些同級節點可用於重建根散列，以便驗證。

3.2.如何構造Merkles證明？

在常見的可驗證查詢場景中，有一個證明者和一個驗證者。證明者需要生成一個證明並發送給驗證者。與以太坊網路相對應，典型的應用場景是輕節點（只存儲區塊頭的客戶端）從全節點或歸檔節點（擁有所有數據的客戶端）查詢交易數據，並獲取 Merkle 證明來本地驗證查詢結果是否正確。

1. Merkle 證明由以下三部分組成：
2. 完整數據集的 Merkle 樹根哈希值。
3. 需要證明其完整性的數據塊。
4. Merkle 路徑，包括從葉節點到根節點路徑上所有同級節點的值。

其中，哈希樹的根哈希值需要提前通過可信的方式發送給驗證者，驗證者必須信任這個值。在以太坊中，區塊數據的可信度由共識算法來保證，而哈希樹的根哈希值包含在區塊頭中。

下面是一個具體的例子：當證明者需要向驗證者證明 “4 ”是數據集中存在的一個數據塊，而驗證者持有完整數據集哈希樹的可信根哈希值 “1d25 ”時，證明者只需提供所有標爲藍色的數據。假設數據集中有 n 個數據塊，驗證任何數據塊的正確性最多需要進行 𝘭𝘰𝘨₂(𝘯) 次哈希計算。

以太坊的輕節點只同步區塊頭，其中包含各種數據集（狀態樹、交易樹、收據樹）的哈希樹根。當輕節點向完整節點查詢樹中某個葉節點的數據時，完整節點會返回原始數據以及相應的 Merkle 證明路徑。這樣，輕節點就可以相信查詢結果的正確性。

3.3. 哈希樹的變體

在哈希樹的基礎上，可以根據不同的目標，將其與其他數據結構進行組合和修改，以實現新的特徵。爲了滿足各種可驗證的查詢場景，哈希樹可以擴展爲各種索引數據結構，如梅克爾-B 樹（MBT）。爲了高效執行插入、刪除和查詢等操作，以太坊團隊提出了默克爾-帕特裏夏樹（Merkle Patricia Tree，MPT）。

3.3.1. Merkle-B 樹

Merkle-B 樹（MBT）主要用於處理可驗證範圍查詢。設 𝑓 爲 MBT 的扇出數（每個節點的子節點數）。基於 B+ 樹結構，MBT 的每個內部節點除了存儲 𝑓 - 1 個索引鍵和指向 𝑓 個子節點的指針外，還以摘要形式維護其所有子節點的哈希值。下面是 MBT 中葉節點和內部節點的結構示意圖。

當需要證明從某個範圍查詢返回的數據符合指定範圍時，計算驗證對象（VO）的服務器必須首先執行兩次自上而下的搜索操作，以找到左邊界和右邊界。它還必須返回該邊界內的所有數據以及所有分支的哈希值，以便構建通向根哈希值的路徑。

這種數據結構的缺點是，返回的 VO 只能證明查詢結果在請求的查詢範圍內，但不能證明返回的結果是完整的。

3.3.2.Merkle Patricia Tree

如果使用純粹的哈希樹來提供可驗證的查詢，則每次插入或刪除數據後重新生成哈希樹根的過程都會非常耗時。此外，它還需要維護額外的數據搜索樹以進行存儲。Merkle Patricia Tree，（簡稱 MPT）結合了 Radix 樹（緊湊前綴樹）和哈希樹的屬性，可以在 O(log(N)) 時間內完成插入、刪除和查詢。要全面了解 MPT，讀者可以參考相關的詳細技術文章。本文僅介紹一些基本定義，並舉例說明，以幫助讀者快速理解 MPT。

以太坊的底層結構採用鍵值數據庫進行存儲，即數據以鍵值對的形式存儲。MPT 也分解成鍵值對進行存儲。我們將 MPT 節點的邏輯結構定義如下：

• 索引
• 路徑
• 數據

在 Merkle Patricia Tree（MPT）的語境中，“索引 ”指的是鍵值對的鍵，而 “路徑 ”與 “數據 ”相結合則構成了鍵值對的值。索引實際上存儲了哈希樹節點的哈希值，而路徑則對應於前綴樹中用於查找目標節點的路徑字符串。以太坊使用十六進制字符串作爲路徑字符串，因此 MPT 的寬度爲 16。數據是與路徑相對應的目標數據。

下面是一個用壓縮前綴優化過的 MPT 示例，其中存儲了以下鍵值對數據：

{

cab8’: ‘dog’、

cabe’：’貓

39’：’雞

395’：’鴨

56f0’：’馬

}

要使用路徑 “395 ”找到數據 “鴨子”，就必須從根散列開始，經過散列 A、散列 C 和散列 D，最終找到目標數據。下面是一個詳細步驟指南：

1. 根散列： 這是 Merkle Patricia Tree (MPT) 的入口點，您可以用它找到第一個節點。
2. hashA：根據根切細值，您將檢索由 hashA 標識的節點或內容。由於路徑是 “395”，因此您要查找的是樹中通向 “3 ”的部分。
3. hashC：訪問完 hashA 的內容後，繼續沿着路徑查找。下一個片段 “9 ”會將你引向 hashC。
4. hashD： 最後，繼續沿着路徑前進，最後一個數據段 “5 ”將指向 hashD，其中包含值 “duck”。

在路徑的每一步，MPT 都利用了 Radix 樹和 Merkle 樹的特性，前者可以根據密鑰找到正確的路徑，後者可以通過散列連結確保數據的完整性。樹中的 “路徑 ”通常用十六進制編碼表示，與樹的分支因子 16 相對應。路徑中的每個節點都包含足夠的哈希指針（指向子節點）和值，用於驗證數據的完整性和在樹中導航。

請注意，在真正的 MPT 中，路徑和數據將以特定格式編碼和存儲，而額外類型的節點（如擴展節點和葉節點）有助於優化結構，以提高不同場景下的效率。

4.矢量承諾

承諾[1] 方案是確保數據隱私和完整性的加密原語。它們廣泛應用於零知識證明和安全多方計算等場景。基本的承諾方案分爲兩個階段：承諾階段和揭示（或開放）階段。

1. 承諾階段： 在這一階段，提交者使用加密算法將信息與承諾值綁定，並將承諾值發送給接收者。在這一階段，承諾具有兩個屬性：隱藏和綁定。隱藏確保除承諾者外，其他人都不知道承諾信息的內容。綁定確保一旦做出承諾，包括承諾者在內的任何人都無法更改。
2. 揭示（公開）階段： 在此階段，提交者可以向接收者證明他們收到的承諾值是對原始信息的有效承諾。承諾具有正確性，這意味着如果提交者和接收者都正確地遵守協議，接收者就會確信他們在提交階段收到的承諾值是對原始信息的有效承諾。

矢量承諾是 Catalano 等人 [2] 提出的一種特殊的承諾方案，它允許承諾者對一組有序的信息 𝑚 = ⟨𝑚1 , 𝑚2 , …, 𝑚△ ⟩ 作出承諾，並在任何指定位置揭示（打開）以證明信息 𝑖 𝑚 是第 ↔ 個承諾的信息。在矢量承諾中，綁定意味着任何人都不能在相同的位置來揭示不同的信息。

向量承諾方案通常由以下算法組成：

5. Verkle 樹

5.1. Verkle樹的定義和特徵

定義：Verkle 樹 = 矢量承諾 + Merkle 樹。

請注意：以太坊聯合創始人維塔利克-布特林（Vitalik Buterin）有一篇專門介紹 Verkle 樹的博文。本章根據他的博客補充了一些背景和數學知識。下文中的部分數據和插圖來自他的博客。

與哈希樹相比，Verkle 樹（VT）的特點是提供更小的證明。對於數十億條目的數據規模，哈希樹可能會生成約 1KB 大小的證明，而 Verkle 樹的證明可能小於 150 字節。這種緊湊的證明大小有利於實現 “無狀態客戶端”。

Verkle 樹的結構與 Merkle Patricia 樹（MPT）有些相似。下面是一個結構示例。Verkle 樹的節點可以是：(i) 空節點，(ii) 包含鍵及其相應值的葉節點，或 (iii) 帶有固定數量子節點的內部節點。子節點的數量也稱爲樹的 “寬度”。

VT（Verkle 樹）和 MPT（Merkle Patricia 樹）之間的區別主要在於樹寬（或扇出，指樹上一個節點的子節點數）如何影響它們的效率。就 MPT 而言，如果寬度越大，效率往往越低，因爲寬度越大意味着同級節點越多，這可能導致 MPT 更新時間更長，證明大小更大。相反，對於 VT 來說，樹的寬度越寬，證明就越小。唯一的限制是，如果寬度過大，生成證明所需的時間就會變長。

在以太坊的 VT 設計提案中，建議的樹寬爲 256，比目前 MPT 的 16 大得多。在 VT 中使用如此大的寬度是可行的，因爲使用了先進的加密技術，如向量承諾，無論樹的寬度如何，都能實現緊湊的證明。這種壓縮技術使 Verkle 樹能更有效地擴展證明大小。下文將更詳細地解釋上述特點。

5.2. Verkle Trees的承諾和證明

讓我們來看看 MPT 是如何生成證明的： 證明需要包括從根節點到目標葉節點路徑上所有邊節點（或姐妹節點）的哈希值。以 “4ce ”爲例，下圖中紅色標記的部分就是返回的證明中需要包含的節點。

在 Verkle 樹中，你不需要提供同級節點；相反，你只需要提供路徑和一些額外的數據作爲證據。

那麼，如何爲 VT 生成承諾呢？用於計算的哈希函數不是傳統的哈希函數，而是使用向量承諾。

用向量承諾生成算法取代散列函數後，所謂的根散列就是根承諾了。如果任何節點的數據被篡改，最終都會影響根承諾。

如何生成證明？如下圖所示，只需提供三個子證明，每個子證明都能證明路徑上的節點存在於其父節點的某個位置。寬度越寬，層數越少，所需的子證明也就越少。

在實際應用中，使用多項式承諾（可以簡單有效地實現向量承諾），允許對多項式進行承諾。最方便用戶使用的兩種多項式承諾方案是 “KZG 承諾 ”和 “防彈式多項式承諾”（前者的承諾大小爲 48 字節，後者爲 32 字節）。

如果採用 KZG 承諾和證明，每個中間節點的證明只需 96 字節，與基本梅克爾樹（假設寬度爲 256）相比，節省了近三倍的空間。

對哈希樹和 Verkle 樹進行操作的理論時間復雜度如下：

迄今爲止介紹的 Verkle 證明方案是相當基本的；事實上，還有更高級的優化策略可供選擇。

5.3.優化：合並證明

5.3.1.概念

與爲路徑上的每一層承諾生成一個證明相比，可以利用多項式承諾的特性，實現 “用一個固定大小的證明來證明路徑上所有承諾之間的上下級關係，這個證明可以包括無限多的元素”。要具體理解如何實現這一點，有必要引入一些數學知識進行解釋。本文將涉及一些數學公式，但原則上不涉及證明的加密部分。具體方法請參考通過隨機評估實現多重證明的方案。

5.3.2.數學推導

首先，讓我們介紹數學中有關多項式的一些基本概念：我們如何進行多項式還原，也稱爲多項式的度數還原？

假設我們知道一個多項式 𝑃(𝑥)及其在 𝑥₁處的值 𝑦₁，即 𝑃(𝑥₁)=𝑦₁。

現在，考慮一個新的多項式 𝑃(𝑥) - 𝑦₁ ，它在（𝑥 = 𝑥₁）處的值爲零，因爲 𝑃(𝑥₁) - 𝑦₁ =𝑦₁ - 𝑦₁ = 0。

因此，多項式 𝑃(𝑥) - 𝑦₁ 在 𝑥 = 𝑥₁ 有一個根，這意味着 (𝑥 - 𝑥₁ ) 是 𝑃(𝑥) - 𝑦₁ 的因子。

換句話說，我們可以用下面的形式表示它： [ 𝑃(𝑥) - 𝑦₁ = (𝑥 - 𝑥₁ )𝑄(𝑥)] 。

𝑄(𝑥)是另一個多項式，其階數比𝑃(𝑥) 少一級。這是因爲 (𝑥 -𝑥₁ ) 是一個一級因子，它減小了多項式的總階數。

如何使用 KZG 證明向量中的單值？

以 KZG10 承諾爲例，對於多項式 𝑃(𝑥) ，假設其多項式承諾爲 [ 𝑃(𝑠) ]₁ 。

如前所述，對於多項式 𝑃(𝑥) ，如果 𝑃(𝑧) = 𝑦 ，則 𝑄(𝑥) = (𝑃(𝑥) - 𝑦 )/(𝑥 - 𝑧) 。

現在，證明者可以生成多項式 𝑃(𝑥) 滿足 𝑃(𝑧) = 𝑦 的證明：計算 [ 𝑄(𝑠) ]₁ 並將其發送給驗證者。

驗證者需要驗證 𝑒( [ 𝑄(𝑠) ]₁, [ 𝑠 - 𝑧]₂ ) = 𝑒( [ 𝑃(𝑠) ]₁- [𝑦]₁, [1]₂) 。

如何使用 KZG 證明向量中的多個值？

我們可以構建如下證明來證明向量中的多個值：

使用這種方法，無論同一向量中有多少數據點需要驗證，都只需要一個大小不變的證明。

現在，讓我們從 KZG 承諾算法的角度來看看未經優化的 Verkle Tree 方案。

使用 “如何使用 KZG 證明向量中的單個值 ”一節中的構造方法，驗證者可以爲每個多項式 𝑓ᵢ(𝑥) 構造原多項式和商多項式的承諾，從而得到總共 𝟐﹡𝑚 KZG 承諾。驗證者發送所有這些承諾作爲驗證證明。

然而，如前所述，這種方法需要生成多個證明，驗證者也需要進行多次驗證計算。我們需要找到一種方法來壓縮多個承諾證明。

合並證明

證明者將證據 [ 𝑞( 𝑠 )]₁ 發送給驗證者進行驗證。

該方案生成的證據包括一個承諾、兩個證明和一個值，數據大小保持不變。最終，在 Verkle 樹的證明合並優化之後，發送給驗證者的可驗證數據對象包括以下內容：

1. 固定大小的證據
2. 待驗證的葉子數據（鍵值對）
3. 從葉子到根節點路徑上所有節點的承諾值（假設樹的寬度爲 256，有 2³² 個節點，平均深度爲 4，僅需要 3 個承諾值）

請注意，𝑥ᵢ 和 𝑦ᵢ 不需要明確提供，它們都可以計算出來。

5.3.3 性能

關於 Verkle 樹的證明合並方案，生成證明的具體大小如下（行的單位是億）：

上述數據假設使用樹的寬度爲 256，採用 KZG 承諾方案（承諾大小爲 48 字節），並最大限度地提高樹的利用率。實際上，對於完全隨機的信息分布，樹的深度將增加約 60%，每個元素的大小將增加 30 字節。如果使用防彈證明方案，則承諾大小爲 32 字節。

5.4.證明者和驗證者計算負載

1. 證明生成： 證明者生成證明的成本與樹的寬度有關，但每個原子操作所需的計算成本相對較低，因此寬度在 256 到 1024 之間的 Verkle 樹在算法方面表現良好。
2. 證明驗證： Vitalik 表示，驗證算法非常快，即使有幾千個值需要驗證，通常也能在 100ms 內完成。
3. 更新 Verkle 樹時： 由於值或結構的變化，更新樹需要重新計算路徑上的所有中間承諾值。不過，Vitalik提到，由於多項式承諾算法的一些特性，可以設計一種方法，預先計算替代承諾值並存儲它們，從而減少更新時的計算時間成本，這實質上是用空間換時間。

6.結論

以下是 vitalik 博客的原話，我們在最後添加了一段作爲補充。

Verkle 樹是 Merkle 證明的強大升級版，它允許更小的證明規模。證明者不需要提供每一層的所有 “姊妹節點”，而只需提供一個證明，證明從每個葉節點到根節點的路徑上所有承諾之間的所有父子關係。與理想的哈希樹相比，這使得證明規模減少了 ~6-8 倍，與以太坊目前使用的六叉Patricia trees相比，則減少了 20-30 倍（！！）。

它們的實現需要更復雜的加密技術，但卻爲擴展性帶來了巨大的潛力。中期來看，SNARKs 可以進一步改善情況：我們可以將已經高效的 Verkle 證明驗證器 SNARK 化，將見證大小減少至接近零，或者在 SNARKs 顯著改進時（例如，通過 GKR、非常適合 SNARK 的哈希函數或 ASICs），重新切換回 SNARKed Merkle 證明。而在更遙遠的未來，量子計算的崛起將迫使我們轉向以哈希爲基礎的 STARKed Merkle 證明，因爲它會使 Verkle 樹所依賴的線性同態變換不再安全。但目前而言，它們給我們帶來了與這些更先進技術相同的擴展收益，而我們已經具備了實現它們所需的所有工具。

目前，許多以太坊客戶端已經提供了 Verkle 樹及其相關測試網絡的實現。社區仍在討論 Verkle 樹何時將在主網絡上啓用。很可能會在 2024 年或 2025 年通過硬分叉升級實現。有關以太坊上 Verkle 樹的詳細信息，請參閱 https://verkle.info/ 。

7. 參考文獻

[1]. BRASSARD G, CHAUM D, CRÉPEAU C. Minimum disclosure proofs of knowledge[J]. Journal of computer and system sciences, 1988, 37(2)： 156-189.

[2]. CATALANO D, FIORE D. 矢量承諾及其應用[C]//Public-KeyCryptography-PKC 2013： 第 16 屆國際公鑰密碼學實踐與理論會議，日本奈良，2013 年 2 月 26 日至 3 月 1 日。論文集 16. Springer, 2013： 55-72.

聲明：

1. 本文轉載自[ZAN]，著作權歸屬原作者[AntChain Open Labs and ZAN]，如對轉載有異議，請聯系Gate Learn團隊，團隊會根據相關流程盡速處理。
2. 免責聲明：本文所表達的觀點和意見僅代表作者個人觀點，不構成任何投資建議。
3. 文章其他語言版本由Gate Learn團隊翻譯， 在未提及Gate.io的情況下不得復制、傳播或抄襲經翻譯文章。