ZK rollups 中的“证明溢出”问题探究

2023.05.08

在 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”计量的概念，就会出现在哪个级别约束它的问题。