區塊更新摘要：無需全局狀態樹的成員證明方案

作者： Cody Littley, Alejandro Ranchal-Pedrosa (@alranpe), Omar Garcia — Sei Labs

內容提要： BUDs 是一種成員證明方案，其擴展性取決於每個區塊的寫入量而非總狀態大小，且不需要在關鍵路徑上維護全域狀態樹（Global State Trie）。

---

動機

成員證明（即狀態證明，如 eth_getProof 所提供的）允許鏈下觀察者在不信任第三方的情況下，以加密方式驗證鏈上數值。標準做法是在整個狀態上構建一個 Merkle 樹，這樣對根哈希的簽名配合 Merkle 路徑，即可證明任何鍵（Key）的包含或排除。

這種方法的成本隨總狀態大小而增加：每個區塊都必須更新一棵葉子節點涵蓋數百萬個帳戶和存儲插槽的樹。對於高吞吐量的 EVM 等效鏈來說，無論是在原始計算還是其強制要求的數據庫佈局上，這種開銷都成為了難以承受的瓶頸。即使是以太坊 L1，維護全域狀態樹也帶來了顯著的複雜性和 I/O 成本。

我們提出了 區塊更新摘要（Block Update Digests, BUDs），這是一種增量認證數據結構，它將狀態承諾成本與總狀態大小解耦，轉而使其隨每個區塊的更新量擴展。BUDs 與我們稱為 SuperBUDs 的分層摘要層以及按需進行的 觸碰交易（Touch Transactions） 相結合，涵蓋了延遲、證明大小和成本要求的全方位需求。

---

與二元狀態樹和 Verkle 樹的區別

以太坊 L1 路線圖已收斂於將二元狀態樹（EIP-7864）作為長期狀態承諾機制，並朝著狀態證明的 O(1) SNARK 驗證方向發展。對於致力於在共識關鍵路徑上維護全域認證數據結構的鏈來說，這些提案代表了對當前 MPT 的明顯改進。而 BUDs 探討的是一個完全不同的問題，兩者是互補而非競爭關係。

BUDs 處理的是一個不同的架構問題：認證數據結構是否應該存在於共識關鍵路徑上？

全域狀態樹無論實現得如何高效（MPT、二元樹、Verkle 樹），都要求每個驗證者在區塊執行期間維護和更新一個樹狀數據結構。這棵樹限制了數據庫佈局，在每次寫入時引入與樹深度成正比的 I/O 放大，並將執行吞吐量與狀態承諾成本糾纏在一起。即使是具有 O(\log n) 路徑的完美二元樹，對於 w 次狀態寫入，每個區塊仍需進行 O(w \cdot \log n) 次哈希計算，且數據庫必須以對樹友好的佈局存儲中間節點。

BUDs 的立場是，對於高吞吐量的執行環境，樹結構並非放置在驗證者關鍵路徑上的正確抽象。相反，驗證者只需生成一個輕量級的每區塊摘要（成本僅與寫入集大小成正比，與總狀態大小無關），而完整的證明基礎設施則委託給存檔節點。狀態本身可以存儲在任何為了原始執行速度而優化的扁平鍵值對（Key-Value）存儲佈局中，不受樹狀 I/O 限制。

這是一個架構選擇，而非臨時過渡方案。採用 BUDs 的鏈並非在「等待遷移到更好的樹結構」；它們是選擇根本不在關鍵路徑上維護全域樹。

值得注意的是，SNARK 驗證的論點是對稱的：BUD Merkle 證明同樣可以進行 SNARK 驗證，且電路更簡單，因為 BUD 樹更小（與區塊寫入集而非全狀態成正比）。如果最終目標是為跨鏈橋和輕客戶端提供經 SNARK 驗證的狀態證明，兩種方法都能達成；問題純粹在於區塊生產期間強加給驗證者的成本。

---

核心思想

BUDs

BUD 是一棵針對單個區塊（或更廣義地說，任何連續的 k 個區塊窗口）產生的變更而構建的小型 Merkle 樹。每個葉子節點記錄：

• 鍵（Key），

• 它的新值（New Value），

• 當前區塊號，以及

• 該鍵上次被修改時的前一個區塊號。

第 (4) 個字段是關鍵的補充：它在 BUD 序列中串聯起每個鍵的修改鏈，使得同一個鍵的兩個相鄰 BUD 條目可以證明中間沒有發生任何變化。為了支持這一點，鍵值存儲中的每個條目都帶有 8 字節的額外元數據，記錄其最後一次修改的區塊高度（外加 1 字節的序列化版本字段）。

圖 1：BUD Merkle 樹的結構。每個葉子節點記錄（鍵、新值、當前區塊號、前次修改區塊號）。BUD 哈希由質押量 > (n+f)/2 的驗證者簽名。

驗證者對 BUD 哈希進行簽名，並以常規方式聚合簽名（質押量 > (n+f)/2 的法定人數，其中最多 f 為敵對節點）。隨後 BUDs 被流式傳輸到存檔節點進行長期存儲和證明服務。

由於樹僅針對區塊中觸碰到的鍵構建，其構建成本與區塊的寫入集大小成正比，而非全域狀態大小。一個修改了 10,000 個鍵的區塊，無論總狀態是否包含 1 億個條目，都只構建一棵擁有 10,000 個葉子的樹。

---

SuperBUDs

單個 BUD 證明了鍵在被修改時的區塊值，但如果輕客戶端查詢一個在 d 個區塊前最後一次寫入的鍵的當前值，理論上需要檢查 d 個 BUD 以證明其間未被修改。SuperBUDs 將這種線性掃描壓縮為對數掃描。

一個 \ell 級 SuperBUD 涵蓋 e^\ell 個區塊（e 為可配置的基數；我們以 e = 2 為具體實例），並在 e^\ell 倍數的區塊高度生成。在內部，SuperBUD 是一個 Merkle 字典，將其跨度內觸碰到的每個鍵映射到其最後一次修改的區塊號。兩個同級別的相鄰 SuperBUD 可以合併為下一級別的單個 SuperBUD，方法是取其鍵集的聯集，對於在兩者中都出現的鍵，僅保留較新的區塊號。這種合併是對兩個已排序字典進行的一次 O(n) 協調遍歷。

給定鍵的 SuperBUD 證明可以顯示 (a) 該跨度內該鍵被修改的最高區塊號，或 (b) 該鍵在該跨度內完全未被修改。結合所識別區塊處的 BUD 證明，即可獲得完整的成員證明。

圖 2：區塊 B0–B11 上基數 e=2 的 SuperBUD 層級結構。1 級 SuperBUD 涵蓋 2 個區塊，2 級涵蓋 4 個，3 級涵蓋 8 個。同級別的相鄰 SuperBUD 通過單次 O(n) 遍歷合併到下一級。

延遲與證明大小。 如果最後一次修改是在 d 個區塊前，客戶端需要一個 \lceil \log_e d \rceil 級別的 SuperBUD。在最壞情況下，客戶端需等待最多 e^{\lceil \log_e d \rceil} 個區塊，直到該級別的下一個對齊窗口關閉。因此，等待時間在最壞情況下與陳舊度（Staleness）成線性關係，但層級結構換取的是證明緊湊性：只需對數次的摘要查找和常數個 Merkle 路徑，而非線性的每區塊排除證明鏈。

---

觸碰交易（Touch Transactions）

SuperBUDs 是在不增加鏈上成本的情況下以延遲換取證明緊湊性，而觸碰交易則提供相反的權衡：支付少量的鏈上費用，即可在當前區塊立即獲得 BUD 證明，無論該鍵有多陳舊。

觸碰交易不修改鍵的值；它僅更新「最後修改」元數據，並在當前區塊的 BUD 中產生一個條目。這類似於 Unix shell 中的 touch 命令：刷新時間戳而不改變內容。觸碰交易根據鏈現有的資源計量（按狀態訪問和元數據寫入單位）定價，因此除了費率表已考慮的因素外，不會引入新的 DoS 攻擊面。

SuperBUDs 和觸碰交易共同涵蓋了完整的延遲/成本設計空間：對成本敏感的用戶等待 SuperBUDs；對延遲敏感的用戶使用觸碰交易。

---

證明策略

BUDs 和 SuperBUDs 可以組合成多種證明策略，每種策略都有不同的權衡。

單一 BUD 證明。 如果查詢的區塊高度恰好發生了修改（或觸碰），則一個 BUD 證明就足夠了。極其緊湊，但僅在修改點可用。

雙重 BUD 證明。 同一個鍵的兩個連續 BUD 證明，其中第二個的「前次修改區塊」字段指向第一個，即可證明兩者之間任何區塊的值。每鍵修改鏈保證了沒有遺漏中間的任何變更。

BUD + SuperBUD。 最後一次修改處的 BUD 證明，結合一個涵蓋該修改點和目標區塊的 SuperBUD。SuperBUD 證明在其跨度內不存在更晚的修改。緊湊且廉價，但對於最近修改的條目有中等延遲，對於陳舊條目延遲較高。

圖 3：BUD + SuperBUD 策略。區塊 B2 的 BUD 證明結合涵蓋 A–C 的 SuperBUD，證明了鍵 K 在直到 SuperBUD 上邊界為止的任何區塊的值，無需觸碰交易。

BUD + 多個 SuperBUDs。 為了在不使用觸碰交易的情況下降低延遲，可以串聯多個相鄰的 SuperBUDs 來填補間隙。緊湊性較低（證明大小隨陳舊度增長），但避免了鏈上成本。

首次修改證明。 如果一個 BUD 條目的「前次修改區塊」等於 -1，則證明該鍵在該區塊之前不存在（追溯到可配置的證明截止點）。這對於排除證明和最近創建的鍵非常有用。

---

設計選擇與靈活性

該結構採用模組化設計。我們強調主要的靈活性維度：

BUD 粒度。 我們預設展示 1:1 的情況（每個區塊一個 BUD），但 BUD 也可以每 k 個區塊針對前面的窗口生成一次。這攤銷了簽名開銷，代價是證明粒度略粗。

SuperBUD 基數與時程。 層級結構的基數 e 控制分叉因子。當 e = 2 時，級別跨度翻倍（2, 4, 8, 16, …），最大合併深度 L 決定了最大證明時效：系統支持過去 e^L 個區塊內任何區塊的證明。較大的 e 減少了層級數量，但增加了最壞情況下的等待時間。生成時程（對齊 e^\ell 的倍數）可以根據鏈的最終性節奏進行偏移或交錯，使邊界更自然。

最大證明時效與墓碑（Tombstones）。 刪除鍵絕不能破壞其修改鏈。狀態不會移除條目，而是寫入一個墓碑（值為 nil，保留「最後修改」元數據）。可配置的最大證明時效（例如以天或月計的區塊數）限制了墓碑保留的時間：一旦墓碑超過截止點，就會被垃圾回收。在截止點之前生成的證明無限期有效且可驗證；過期的是為極舊區塊生成新證明的能力。

排除證明。 單靠 SuperBUDs 無法證明排除，因為它們不對鍵的預先存在狀態做任何斷言。完整的排除證明需要一個 BUD 條目（可能通過對不存在的鍵進行觸碰交易產生，這會生成一個墓碑）。這是一個刻意的設計權衡：證明一個從未存在且沒有墓碑的鍵不存在，這種邊緣案例足夠小眾，要求使用觸碰交易是可以接受的。

---

與全域狀態樹的比較

維度	全域狀態樹 (含 Binary/Verkle)	BUDs + SuperBUDs
架構位置	在共識關鍵路徑上	卸載至存檔基礎設施
每區塊承諾成本	O(w \cdot \log n) 哈希 (w 次寫入, n 個條目)	O(w \cdot \log w) 哈希 (僅 w 次寫入)
數據庫佈局	需要對樹友好的存儲	扁平鍵值存儲，每條目額外 9 字節元數據
當前狀態證明生成	立即（樹中的單個 Merkle 路徑）	觸碰則立即；否則等待 SuperBUD
證明大小	O(\log n)	每個 BUD O(\log w) + 每個 SuperBUD O(\log s)
SNARK 友好性	可證明；電路覆蓋 O(\log n) 路徑	可證明；電路覆蓋 O(\log w) 路徑 (更小)
驗證者存儲負擔	完整樹（中間節點 + 葉子節點）	僅當前狀態 + 9 字節元數據
誰提供證明服務	驗證者或全節點	存檔節點（專門的基礎設施）

核心權衡：全域樹為任何最近區塊的任何鍵提供即時證明，代價是將執行與樹維護糾纏在一起。BUDs 僅在修改點（或通過觸碰按需）提供即時證明，但使執行層擺脫了任何樹狀結構的束縛。

---

目標與後續步驟

BUDs 是在共識關鍵路徑上維護全域狀態樹的一種永久性架構替代方案。它們不是為等待採用更好樹結構的鏈提供的過渡機制，也不是分層在現有樹結構之上的補充。相反，BUDs 是為那些選擇完全不在驗證者關鍵路徑上維護全域認證數據結構，並將證明基礎設施委託給存檔節點以換取不受限執行吞吐量的鏈而設計的。

主要受眾是高吞吐量的 EVM 等效 L1 和 Rollup，在這些環境中，狀態樹維護已經或正在成為執行瓶頸。對於已經在進行二元樹遷移（EIP-7864）的以太坊 L1 來說，BUDs 並非自然的選擇。對於從頭設計狀態承諾策略，或隨著狀態增長而重新考慮策略的鏈，BUDs 提供了一條根本不同的擴展路徑。

我們正在準備一份資訊型 EIP 以正式化此結構。我們歡迎對設計、參數選擇和潛在採用路徑的討論。

完整的 RFC 已可供審閱；我們將在 EIP 草案發布後提供鏈接。

---

開放性問題

我們歡迎對以下內容進行討論：

• 參數選擇： 在實踐中，對於高吞吐量鏈，基數 e 和最大證明時效的合適值是多少？e=2 是正確的預設值嗎，還是更大的分叉因子更適合典型的鍵齡分佈？

• 排除證明的邊緣案例： 要求觸碰交易來證明從未存在的鍵不存在是一個刻意的權衡。這在實踐中是否可以接受，還是需要不同的解決方案？

• 存檔節點激勵： BUDs 將證明服務完全委託給存檔節點。什麼樣的激勵結構能確保存檔節點在長期的時間跨度內保持可用且誠實？

• 採用路徑： 對於已經在運行全域狀態樹的鏈，向 BUDs 遷移的最微創路徑是什麼？

        1 則貼文 - 1 位參與者
  
        [閱讀完整主題](https://ethresear.ch/t/block-update-digests-membership-proofs-without-a-global-state-tree/24509)