在 Scroll，我們正在開放構(gòu)建zkEVM，并希望將我們正在構(gòu)建的協(xié)議的所有方面保持公開透明。

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

背景

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

1. 用戶向 Scroll 的內(nèi)存池提交交易。

2. 排序器(sequencer)節(jié)點(diǎn)將一些交易打包到一個區(qū)塊中。

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

• 批次的數(shù)據(jù)（包括其所有交易數(shù)據(jù)）被發(fā)布或“提交”到以太坊 L1

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

• 該證明可以證明該批次中的所有交易均已正確執(zhí)行。

• 該證明提交給以太坊 L1 進(jìn)行驗(yàn)證。相應(yīng)的批次被認(rèn)為是“最終確認(rèn)的”。

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

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

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

由于批次由區(qū)塊組成，而區(qū)塊由交易組成，因此批次的行消耗配置文件由組成它的交易所決定。如果一個批次的行消耗超過最大行數(shù) m，則該批次將無法證明（即證明“溢出”）。當(dāng)一個批次無法證明時，它無法在 L1 上最終確認(rèn)，任何后續(xù)的批次也無法證明（取決于無法證明批次的結(jié)果狀態(tài)）。

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

要解決“證明溢出”問題需要解決以下問題：如何防止創(chuàng)建超出電路容量的批次？

長期解決方案

問題源于我們電路架構(gòu)的局限性：所有子電路都必須有一些預(yù)先確定的、固定數(shù)量的行。我們正在研究重新設(shè)計(jì)我們的架構(gòu)，以便可以獨(dú)立地動態(tài)調(diào)整子電路的大小——每個子電路的大小都可以根據(jù)批次證明的要求放大或縮小。例如，如果一個批次在 Keccak 電路中需要 2^20 行，但在求冪電路中只需要 2^14 行，則子電路可以獨(dú)立縮放。

這種類型的動態(tài)設(shè)計(jì)帶來了挑戰(zhàn)，我們正在努力解決這些問題。然而，與此同時，我們需要解決固定尺寸電路的問題。

當(dāng)前解決方案

1. 根據(jù)最壞情況下的操作碼設(shè)置區(qū)塊Gas 限制

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

• 優(yōu)點(diǎn)：簡單

• 缺點(diǎn)

• 非常低效

• 分析表明，最昂貴的操作碼 (SHA) 的證明行與 EVM Gas之間的比率約為 11 倍。

• 每個額外的 Keccak 字節(jié)占用約 2.2 行，同時消耗約 6/32 EVM gas。對于 m = 2^20（大約 100 萬行），我們可以容納大約 2^20 / 2.2 個 Keccak 字節(jié)。這對應(yīng)于 (2^20 / 2.2) * (6/32) ~= 89,000 gas 的最大區(qū)塊限制。太?。?！

2. Gas 重新定價 

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

• 優(yōu)點(diǎn)：

• 證明溢出問題在執(zhí)行層被處理為“Out of Gas”錯誤

• 缺點(diǎn)

• 可能會破壞依賴于正常 EVM Gas 定價的合約。

• 很難以編程方式將操作碼映射到行消耗。

• 這個映射應(yīng)該是可編程的，因?yàn)閦kEVM的電路庫會隨著時間的推移而改變，也因?yàn)槭止し治鋈菀壮鲥e，這里稍有錯誤就會導(dǎo)致溢出漏洞

• 需要保持 L2Geth Gas定價和 zkEVM 電路庫之間的同步 - 不同步將導(dǎo)致漏洞

3. 引入額外的“Proof Gas”計(jì)量

除了正常的 EVM Gas之外，我們還可以有一個單獨(dú)的概念 “Proof  Gas ”。Proof  Gas 將用于量化交易在我們的電路中消耗的空間。請注意，這種“Proof  Gas”應(yīng)該是多維的——因?yàn)椴煌牟僮鞔a在不同的電路中占據(jù)不同的行。

一旦引入“Proof  Gas”計(jì)量的概念，就會出現(xiàn)在哪個級別約束它的問題。

3a.在執(zhí)行層約束 Proof Gas

此解決方案與解決方案2類似，不同之處在于它保留了 EVM Gas 和Proof Gas 的概念。這將再次涉及將每個操作碼靜態(tài)映射到它在每個電路中占用的行數(shù)，然后修改 L2Geth 以添加這種 Proof Gas的概念。如果特定交易超過了 Proof Gas 限制，則交易將撤銷并出現(xiàn)一些自定義的“ out of proof gas ”的錯誤。這將確保沒有區(qū)塊可以超過行約束，因?yàn)閳?zhí)行層將在此之前停止交易。

• 優(yōu)點(diǎn)：

• 證明溢出問題在執(zhí)行層被處理為“out of proof gas”錯誤

• 缺點(diǎn)

• 難以生成從操作碼到行消耗的靜態(tài)映射

• 需要保持 L2Geth 和 zkEVM 電路庫之間的同步

• 需要對 L2Geth 和 zkEVM 電路庫中的邏輯進(jìn)行重大更改，以支持額外的 Proof Gas 概念

3b.在執(zhí)行層之外約束 Proof Gas

我們可以從 zkEVM 電路庫中公開 API 來報(bào)告給定執(zhí)行蹤跡所需的行數(shù)，而不是生成操作碼到電路行的靜態(tài)映射。L2Geth 可以生成區(qū)塊的執(zhí)行蹤跡，然后查詢電路行消耗 —— 如果超過最大行數(shù)，則不會創(chuàng)建區(qū)塊。

• 優(yōu)點(diǎn)：

• 無需以編程方式將操作碼映射到行消耗所需的復(fù)雜性。

• 缺點(diǎn)：

• 當(dāng)必須構(gòu)造一個區(qū)塊時，L2Geth 會增加一些計(jì)算開銷，因?yàn)樗枰M(jìn)行額外的計(jì)算來估計(jì)電路行消耗。

• 使強(qiáng)制包含（Forced Inclusion）變得復(fù)雜。

• 強(qiáng)制包含是一種機(jī)制，用戶可以直接通過 L1 提交 L2 交易。這些交易被“強(qiáng)制”包含在 L2 鏈中，作為一種抗審查機(jī)制。

• 我們無法將交易映射到它在 L1 上消耗的電路行數(shù)，因此無法判斷它是否可證明

結(jié)語：

似乎解決方案 3b 是最簡單且風(fēng)險最小，也是可行的解決方案。

伴隨這種方案的主要挑戰(zhàn)是如何處理強(qiáng)制交易，因?yàn)榭赡艽嬖谔蠖鵁o法放入電路中的強(qiáng)制交易。這里的一個想法是使用解決方案 1 中的想法來限制強(qiáng)制交易的 Gas 限制，這樣即使在最壞的情況下，強(qiáng)制交易也不會溢出電路。

從長遠(yuǎn)來看，我們的目標(biāo)是開發(fā)一個更靈活的證明系統(tǒng)，支持動態(tài)大小的子電路，從而完全避免這個問題。

熱點(diǎn)：rollup