Scroll:如何解決ZK Rollups中的“證明溢出”問題?

在Scroll,我們正在開放構建zkEVM,並希望將我們正在構建的協議的所有方面保持公開透明。

這篇文章中描述了我們稱之為“證明溢出”的問題— 一個由於ZK rollups 中執行和證明生成分離而引起的問題。

背景

Scroll 的rollup 流程大致可以理解為:

1. 用戶向Scroll 的內存池提交交易。

2. 排序器(sequencer)節點將一些交易打包到一個區塊中。

3. 批處理程序(bather)將一些區塊打包成一個批次(batch)。

    • 批次的數據(包括其所有交易數據)被發布或“提交”到以太坊L1

4. 證明者獲取批次並生成證明。

    • 該證明可以證明該批次中的所有交易均已正確執行。
    • 該證明提交給以太坊L1 進行驗證。相應的批次被認為是“最終確認的”。

我們在Alpha 測試網中遇到的一個問題是無法證明某些批次。願意是它們“太大”而無法放入我們的zkEVM 電路中。

人們可以認為zkEVM 電路由許多子電路組成,比如n 個子電路,它們通過查找表互連。每個子電路用於約束特定的操作——例如,Keccak 電路計算Keccak 哈希,求冪電路計算求冪。我們的zkEVM 電路設計中當前限制是每個子電路必須具有相同的行數,比如m 行。

根據每個子電路中消耗的行數,每個所傳入的交易都具有唯一的配置文件。例如,可能有一個交易需要許多Keccak 操作,因此在Keccak 電路中佔用許多行,而在求冪電路中不佔用任何行。相反,可能有一個交易在Keccak 電路中佔用很少的行,而在求冪電路中佔用很多行。

由於批次由區塊組成,而區塊由交易組成,因此批次的行消耗配置文件由組成它的交易所決定。如果一個批次的行消耗超過最大行數m,則該批次將無法證明(即證明“溢出”)。當一個批次無法證明時,它無法在L1 上最終確認,任何後續的批次也無法證明(取決於無法證明批次的結果狀態)。

值得注意的是,即使只包含單個交易的批次也可能會溢出電路。

要解決“證明溢出”問題需要解決以下問題:如何防止創建超出電路容量的批次?

長期解決方案

問題源於我們電路架構的局限性:所有子電路都必須有一些預先確定的、固定數量的行。我們正在研究重新設計我們的架構,以便可以獨立地動態調整子電路的大小——每個子電路的大小都可以根據批次證明的要求放大或縮小。例如,如果一個批次在Keccak 電路中需要2^20 行,但在求冪電路中只需要2^14 行,則子電路可以獨立縮放。

這種類型的動態設計帶來了挑戰,我們正在努力解決這些問題。然而,與此同時,我們需要解決固定尺寸電路的問題。

當前解決方案

1. 根據最壞情況下的操作碼設置區塊Gas 限制❌

這裡的想法是根據最壞情況下(就電路行消耗而言最昂貴)的操作碼來設置區塊的Gas 限制。換句話說,設置區塊Gas 限制,即使它被最昂貴的操作碼填滿,該區塊仍然可以適配我們的電路。這保證了任何區塊都無法填滿電路。

  • 優點:簡單
  • 缺點
    • 非常低效
      • 分析表明,最昂貴的操作碼(SHA) 的證明行與EVM Gas之間的比率約為11 倍。
      • 每個額外的Keccak 字節佔用約2.2 行,同時消耗約6/32 EVM gas。對於m = 2^20(大約100 萬行),我們可以容納大約2^20 / 2.2 個Keccak 字節。這對應於(2^20 / 2.2) * (6/32) ~= 89,000 gas 的最大區塊限制。太小! !

2. Gas 重新定價⚠️

我們可以修改操作碼到Gas的映射表來反映證明成本,而不是執行成本。這將涉及從每個操作碼與它在所有子電路中佔用的最大行數的靜態映射,然後修改我們的Geth 分支(“L2Geth”)以使用這個新的Gas 定價。

  • 優點:
    • 證明溢出問題在執行層被處理為“Out of Gas”錯誤
  • 缺點
    • 可能會破壞依賴於正常EVM Gas 定價的合約。
    • 很難以編程方式將操作碼映射到行消耗。
      • 這個映射應該是可編程的,因為zkEVM的電路庫會隨著時間的推移而改變,也因為手工分析容易出錯,這裡稍有錯誤就會導致溢出漏洞
    • 需要保持L2Geth Gas定價和zkEVM 電路庫之間的同步- 不同步將導致漏洞

3. 引入額外的“Proof Gas”計量

除了正常的EVM Gas之外,我們還可以有一個單獨的概念“Proof Gas ”。 Proof Gas 將用於量化交易在我們的電路中消耗的空間。請注意,這種“Proof Gas”應該是多維的——因為不同的操作碼在不同的電路中佔據不同的行。

一旦引入“Proof Gas”計量的概念,就會出現在哪個級別約束它的問題。

3a.在執行層約束Proof Gas

此解決方案與解決方案2類似,不同之處在於它保留了EVM Gas 和Proof Gas 的概念。這將再次涉及將每個操作碼靜態映射到它在每個電路中佔用的行數,然後修改L2Geth 以添加這種Proof Gas的概念。如果特定交易超過了Proof Gas 限制,則交易將撤銷並出現一些自定義的“ out of proof gas ”的錯誤。這將確保沒有區塊可以超過行約束,因為執行層將在此之前停止交易。

  • 優點:
    • 證明溢出問題在執行層被處理為“out of proof gas”錯誤
  • 缺點
    • 難以生成從操作碼到行消耗的靜態映射
    • 需要保持L2Geth 和zkEVM 電路庫之間的同步
    • 需要對L2Geth 和zkEVM 電路庫中的邏輯進行重大更改,以支持額外的Proof Gas 概念

3b.在執行層之外約束Proof Gas

我們可以從zkEVM 電路庫中公開API 來報告給定執行踪跡所需的行數,而不是生成操作碼到電路行的靜態映射。 L2Geth 可以生成區塊的執行踪跡,然後查詢電路行消耗—— 如果超過最大行數,則不會創建區塊。

  • 優點:
    • 無需以編程方式將操作碼映射到行消耗所需的複雜性。
  • 缺點:
    • 當必須構造一個區塊時,L2Geth 會增加一些計算開銷,因為它需要進行額外的計算來估計電路行消耗。
    • 使強制包含(Forced Inclusion)變得複雜。
      • 強制包含是一種機制,用戶可以直接通過L1 提交L2 交易。這些交易被“強制”包含在L2 鏈中,作為一種抗審查機制。
      • 我們無法將交易映射到它在L1 上消耗的電路行數,因此無法判斷它是否可證明

結語

似乎解決方案3b 是最簡單且風險最小,也是可行的解決方案。

伴隨這種方案的主要挑戰是如何處理強制交易,因為可能存在太大而無法放入電路中的強制交易。這裡的一個想法是使用解決方案1 中的想法來限制強制交易的Gas 限制,這樣即使在最壞的情況下,強制交易也不會溢出電路。

從長遠來看,我們的目標是開發一個更靈活的證明系統,支持動態大小的子電路,從而完全避免這個問題。

Total
0
Shares
Related Posts