區塊更新摘要：無需全域狀態樹的成員資格證明
作者： Cody Littley、Alejandro Ranchal-Pedrosa ( @alranpe )、Omar Garcia — Sei Labs
TL;DR： BUD 是一種成員資格證明方案，它隨著每個區塊的寫入量而不是總狀態大小而擴展，而無需在關鍵路徑上設定全域狀態 trie。
動機
成員資格證明（也稱為狀態證明，由eth_getProof提供）允許鏈下觀察者在無需信任第三方的情況下，以加密方式驗證鏈上值。標準方法是在整個狀態上建立一個 Merkle trie 樹，這樣，對根雜湊進行簽名並結合 Merkle 路徑，即可證明任何金鑰的包含或排除。
這種方法的成本會隨著狀態總量的增加而增加：每個區塊都必須更新一棵樹，而這棵樹的葉子節點跨越數百萬個帳戶和儲存槽位。對於高吞吐量的 EVM 等效鏈來說，這種開銷會成為難以承受的瓶頸，無論是在原始計算方面，還是在它所強制的資料庫佈局方面。即使是以太坊 L1 層，維護全域狀態樹也會帶來顯著的複雜性和 I/O 開銷。
我們提出了一種名為區塊更新摘要（BUD）的增量式認證資料結構，它將狀態承諾成本與總狀態大小解耦，而是根據每個區塊的更新量進行擴展。 BUD 可以與我們稱為SuperBUD 的分層摘要層以及按需存取交易相結合，從而滿足各種延遲、證明大小和成本需求。
二元狀態樹和Verkle樹的區別
以太坊 L1 路線圖已將二元狀態樹 (EIP-7864) 確定為長期狀態承諾機制，並計劃採用O(1 )複雜度的SNARK 驗證來驗證狀態證明。對於致力於在共識關鍵路徑上維護全域認證資料結構的鏈而言，這些提案明顯優於目前的 MPT。 BUD 則完全解決另一個問題，兩者互為補充，而非競爭關係。
BUD 解決了一個不同的架構問題：經過認證的資料結構是否應該存在於共識關鍵路徑上？
無論全域狀態樹的實作效率如何（MPT、二元樹、Verkle 樹），每個驗證者都需要在區塊執行期間維護和更新一個 trie 樹狀資料結構。此 trie 樹限制了資料庫佈局，每次寫入都會引入與樹深度成正比的 I/O 放大，並將執行吞吐量與狀態提交成本糾纏在一起。即使是完美的二元樹，其複雜度也僅為O(log n) O ( log n) 。 n )路徑施加O(w \cdot \log n) O ( w ⋅ log n )每個區塊進行w次狀態寫入的雜湊計算，且資料庫必須以 trie 友善的佈局儲存中間節點。
BUD 認為，對於高吞吐量的執行環境，將 trie 樹放在驗證器的關鍵路徑上是不合適的抽象層。相反，驗證器產生一個輕量級的區塊摘要（成本僅與寫入集成正比，與總狀態大小無關），而完整的證明基礎設施則委託給歸檔節點。狀態本身可以儲存在任何對原始執行速度最優的扁平鍵值儲存佈局中，不受 trie 樹式 I/O 的限制。
這是一種架構選擇，而非臨時解決方案。採用 BUD 的區塊鏈並非“等待遷移到更好的 trie 樹”，而是選擇完全不在關鍵路徑上維護全域 trie 樹。
需要注意的是，SNARK 驗證論證是對稱的：BUD Merkle 證明也可以用 SNARK 驗證，而且由於 BUD 樹更小（與The Block寫入集合成正比，而非與完整狀態成正比），電路也更簡單。如果最終目標是為跨鏈橋和輕客戶端提供 SNARK 驗證的狀態證明，那麼兩種方法都能達到目的；問題僅僅在於區塊生成過程中驗證者所承擔的成本。
核心思想
芽
芽（BUD）是一個小型默克爾樹，它基於單一區塊（或更一般地，任何連續的k個區塊視窗）產生的變化構建而成。每個葉子記錄：
- 關鍵在於，
- 它的新價值，
- 當前區塊編號，以及
- 密鑰上次修改時所在的區塊編號。
欄位 (4) 是關鍵的新增功能：它將每個鍵的修改鏈貫穿 BUD 序列中，以便同一鍵的兩個相鄰 BUD 條目可以證明其間沒有任何變更。為了支援這一點，鍵值儲存中的每個條目都攜帶 8 個額外的元數據，用於記錄其上次修改的The Block高度（外加 1 個位元組的序列化版本欄位）。
圖 1：BUD Merkle 樹的結構。每個葉子節點記錄（鍵、新值、當前區塊號、已修改的前一個區塊號）。 BUD 雜湊由權益大於 (n+f)/2 的驗證者簽署。
驗證者對 BUD 雜湊值進行簽名，並以常規方式聚合簽名（法定人數為> (n+f)/2 > ( n + f ) / 2 個權益，其中至多f個權益為對抗性權益）。然後，BUD 被串流到歸檔節點進行長期儲存和證明服務。
由於樹僅基於資料區塊中修改過的鍵構建，因此其構建成本與資料區塊的寫入集成正比，而非與全局狀態的大小成正比。一個修改了 10,000 個鍵的資料區塊，無論全域狀態的總條目數是否達到 1 億，都會建立一個包含 10,000 個葉子節點的樹。
超芽
單一 BUD 驗證鍵在其被修改的The Block中的值，但輕客戶端查詢d個區塊前最後寫入的鍵的當前值時，如果想排除該鍵，則需要檢查d個BUD。 SuperBUD 將此線性掃描壓縮為對數級掃描。
一個等級為 ℓₜ的SuperBUD跨越eℓ個區塊（其中e是一個可配置的基數；我們以e = 2為例） ，並且產生於eℓₜ的倍數的區塊高度處。在內部，SuperBUD 是一個 Merkle樹，它將跨越範圍內每個被觸及的鍵映射到該鍵被修改的最新區塊號。同一層級的兩個相鄰 SuperBUD 可以透過合併它們的鍵集，並且對於同時出現在兩個 SuperBUD 中的鍵，僅保留最近的區塊號，合併成下一級別的一個 SuperBUD。這種合併操作只需對兩個已排序的 Merkle 樹進行一次O(n )的協同遍歷即可完成。
對於給定的密鑰，SuperBUD 證明要么顯示 (a) 密鑰被修改的跨度內的最高區塊，要么顯示 (b) 密鑰在該跨度內根本沒有被修改。結合在已識別區塊上的 BUD 證明，即可獲得完整的成員資格證明。
圖 2：基於基數e = 2的區塊 B0–B11 上的 SuperBUD 層次結構。 1 級 SuperBUD 跨越 2 個區塊，2 級跨越 4 個區塊，3 級跨越 8 個區塊。同一級別的相鄰 SuperBUD 透過一次O( n )遍歷合併到下一級。
延遲和證明大小。如果上次修改發生在 d d 個區塊之前，則客戶端需要一個等級為\lceil \log_e d \rceil ⌈ log e 的SuperBUD。 d ⌉ 。最壞情況下，客戶端最多需要等待e^{\lceil \log_e d \rceil} e ⌈ log e d ⌉區塊用於等待該層級下一個對齊視窗關閉。因此，等待時間在最壞情況下是線性的，但這種層級結構帶來的好處是證明的緊湊性：摘要查找次數呈對數級，默克爾路徑數量為常數，而不是每個區塊的排除證明的線性鏈。
觸摸交易
SuperBUD 以延遲換取證明的緊湊性，且不產生鏈上成本；而觸碰交易則提供了相反的權衡：支付少量鏈上費用即可在當前區塊立即獲得 BUD 證明，無論密鑰有多麼陳舊。
觸碰交易不會修改鍵的值；它只會更新「最後修改」元數據，並在當前區塊的 BUD 中產生一筆記錄。這類似於 Unix shell 中的touch指令：刷新時間戳記而不改變內容。觸碰交易的定價是基於鏈上現有的資源計量機制（按狀態存取和元資料寫入單位計費），因此除了費用表已涵蓋的部分之外，不會引入新的拒絕服務攻擊面。
SuperBUD 和觸控交易共同涵蓋了整個延遲/成本設計空間：對成本敏感的用戶等待 SuperBUD；對延遲敏感的用戶進行觸摸。
證明策略
BUD 和 SuperBUD 可以組成幾種證明策略，每種策略都有不同的權衡取捨。
單次 BUD 驗證。如果查詢的區塊高度與修改點（或接點）重合，則一次 BUD 驗證即可。極其緊湊，但僅在修改點可用。
雙重 BUD 證明。對同一密鑰進行兩次連續的 BUD 證明，其中第二次證明的「上一個區塊已修改」欄位指向第一個證明，即可證明其間任意區塊的值。每個密鑰的修改鏈保證了不會遺漏任何中間變更。
BUD + SuperBUD。 BUD證明最後一次修改的數據，並結合 SuperBUD，SuperBUD 的跨度涵蓋該修改和目標區塊。 SuperBUD 證明在其跨度內不存在後續修改。這種方法緊湊且成本低廉，但對於最近修改過的條目會有中等延遲，而對於過時的條目則延遲較高。
圖 3：策略 BUD + SuperBUD。在區塊 B2 處使用 BUD 證明，結合跨越 A–C 的 SuperBUD，可以證明密鑰 K 在 SuperBUD 上限邊界之前的任何區塊的值，而無需進行接觸交易。
BUD + 多個 SuperBUD。為了在不進行接觸式交易的情況下降低延遲，可以將多個相鄰的 SuperBUD 連結起來以彌補延遲。這種方法雖然不太緊湊（證明大小會隨著時間推移而增加），但可以避免鏈上成本。
首次修改證明。如果 BUD 條目的「上一個區塊已修改」值為-1 - 1 ，則表示該金鑰在該區塊之前不存在（追溯到可設定的證明截止點）。這對於排除證明和最近創建的密鑰非常有用。
設計選擇和靈活性
建築採用模組化設計。我們重點介紹其主要的靈活性體現：
BUD粒度。我們預設採用1:1的粒度（每個區塊一個BUD），但也可以在前一個時間窗口內每隔k個區塊產生一個BUD。這樣可以分攤簽名開銷，但代價是證明的精準度略低。
SuperBUD的基礎層級和調度。層級結構的基礎層級e控制分支因子。當e = 2 時，層級跨度翻倍（2, 4, 8, 16, …），最大合併深度L決定最大證明年齡：系統支援最近e^ L區塊內任何區塊的證明。較大的e值會減少層級數量，但會增加最壞情況下的等待時間。如果鏈的最終性節奏使得某些邊界更自然，則可以將生產調度（與e^\ell e ℓ的倍數對齊）進行偏移或交錯。
最大證明期限和墓碑。刪除密鑰不得破壞其修改鏈。狀態不會刪除條目，而是寫入一個墓碑（值為 nil，保留「最後修改」元資料）。可配置的最大證明期限（例如，區塊的天數或月數）限制了墓碑的保留時間：一旦墓碑的年齡超過截止期限，就會被垃圾回收。在截止期限之前產生的證明將無限期地保持有效和可驗證；失效的是為非常古老的區塊產生新證明的能力。
排除證明。 SuperBUD本身無法證明排除性，因為它們不斷言密鑰的預先存在狀態。完整的排除證明需要一個 BUD 條目（可能透過對不存在的金鑰進行接觸交易創建，從而產生墓碑標記）。這是一種有意為之的設計權衡：證明一個從未存在且沒有墓碑標記的密鑰不存在的極端情況非常罕見，因此需要進行接觸交易是可以接受的。
與全域狀態樹的比較
| 方面 | 全域狀態特里樹（包括 Binary/Verkle） | 芽 + 超芽 |
|---|---|---|
| 建築師職位 | 在共識關鍵路徑上 | 卸載到歸檔基礎設施 |
| 每個區塊的承諾成本 | O(w \cdot \log n) O ( w ⋅ log n )哈希（ ww寫入， nn狀態條目） | O(w \cdot \log w) O ( w ⋅ log w ）哈希（ w w僅寫入） |
| 資料庫佈局 | 需要適合Trie的儲存方式 | 扁平鍵值存儲，每個條目額外包含 9 位元組元數據 |
| 為目前狀態產生證明 | 立即（來自 trie 樹的單一 Merkle 路徑） | 立即觸摸；否則請等待 SuperBUD |
| 校樣尺寸 | O(log n) O ( log n ） | O(log w) O ( log w )每個 BUD + O(\log s) O ( log s ）每 SuperBUD |
| SNARK友好性 | 可證明；電路複雜度為O(log n) O ( log n ）路徑 | 可證明；電路複雜度為O(log w) O ( log w ）路徑（較小） |
| 驗證器儲存負擔 | 完整trie樹（中間節點+葉節點） | 目前狀態 + 9 位元組元數據 |
| 誰來提供證據 | 驗證節點或全節點 | 歸檔節點（專用基礎設施） |
核心權衡：全域 trie 樹可以立即為任何最近區塊的任何鍵提供證明，但代價是執行層與 trie 樹的維護糾纏在一起。 BUD 僅在修改點（或透過 touch 按需）提供立即證明，但使執行層擺脫了任何 trie 樹形狀的約束。
目標和後續步驟
BUD 是一種永久性的架構方案，用於在共識關鍵路徑上維護全域狀態樹。它們並非等待採用更優 trie 樹的鏈的過渡機制，也不是疊加在現有 trie 樹之上的補充。相反，BUD 的設計初衷是為那些選擇完全不在驗證者關鍵路徑上維護全域認證資料結構的鏈而生，它們將證明基礎設施委託給歸檔節點，以換取不受限制的執行吞吐量。
主要目標用戶是高吞吐量的 EVM 等效 L1 快取和 Rollup 緩存，在這些快取中，狀態樹維護已成為或即將成為執行瓶頸。對於以太坊 L1 快取而言，由於二元樹遷移（EIP-7864）已在進行中，BUD 並非其天然的適用方案。但對於那些從零開始設計狀態承諾策略，或隨著狀態成長而重新考慮狀態承諾策略的鍊而言，BUD 提供了一種截然不同的擴展路徑。
我們正在準備一份資訊性環境影響評估報告（EIP），以規範該建設方案。我們歡迎就設計、參數選擇和潛在的應用路徑進行討論。
完整的 RFC 可供查閱；一旦 EIP 草案發布，我們將提供連結。
未解決的問題
我們歡迎就以下議題展開討論：
- 參數選擇：在實際應用中，對於高吞吐量鏈，基本 e和最大證明年齡的合適值是多少？ e = 2是正確的預設值，還是更大的分支因子更適合典型的金鑰年齡分佈？
- 排除證明的極端情況：要求透過接觸交易來證明從未存在過的密鑰不存在，這是一種有意為之的權衡。這在實踐中是否可以接受，還是需要不同的解決方案？
- 歸檔節點激勵機制： BUD 將證明服務完全委託給歸檔節點。什麼樣的激勵機制能夠確保歸檔節點在長期內維持可用性和誠信？
- 採用路徑：對於已經運行全域狀態 trie 的鏈來說，遷移到 BUD 的破壞性最小的路徑是什麼？
