Scroll 研究：zkEVM 的设计挑战和解决方案

来源：Scroll Tech  

编译：饼干，链捕手

概述

zk-Rollup 是一种非常便宜且安全的以太坊二层扩展解决方案。然而，现有的 zk-Rollup 只限于特定应用程序使用，这使得开发人员在 zk-Rollup 中构建通用的可组合 DApp 和迁移现有应用程序变得困难。我们通过引入 zkEVM 生成 zk 证明用于 EVM 验证来构建完全兼容 EVM 的 zk-Rollup，任何以太坊应用程序都可以轻松迁移到该 zk-Rollup。

本文介绍 zkEVM 的设计挑战以及可行性，并提出了从零开始构建 zkEVM 的详细方案。

背景

zk-Rollup是公认的以太坊最佳扩容解决方案。不仅具有以太坊 Layer 1 的安全性，并且与所有其他 Layer 2 解决方案相比，交易速度最快。

从中长期来看，随着 ZK-SNARK 技术的改进，ZK rollups 将在所有用例中胜出。— Vitalik Buterin

zk-Rollup 的基本理念是将大量交易聚合到一个 Rollup 块中，并为链下的块生成简洁的证明。然后 Layer 1 上的智能合约只需要验证zk-Rollup的证明并直接更新状态，无需重新执行那些交易。证明验证状态比重新执行计算的 gas 费用便宜很多，另外数据压缩（即只保留最少的链上数据进行验证）利于降低 gas 费用，这样的交易流程节省一个数量级的 gas 费用。

尽管 zk-Rollup 安全高效，但很难构建通用 DApp，其应用仍仅限于支付和互换（swap），主要是以下两个原因：

首先，在 zk-Rollup 中开发 DApp 需要使用特殊的编程语言（即 R1CS ）来编写智能合约的逻辑。该编程语言的语法复杂，而且要求开发者精通零知识证明。

其次，当前的 zk-Rollup 不支持可组合性[1]。这意味着多个的 zk-Rollup 应用程序不能在 Layer 2 内相互交互，极大地降低了 DeFi 应用程序的可组合性。

简而言之，目前 zk-Rollup 对开发人员不友好并且功能有限。 我们希望解决这些问题，通过直接支持原生 EVM 验证，为开发人员提供快速开发体验，支持 Layer 2 内应用程序的可组合性，以便现有的以太坊应用程序可以轻松迁移到 zk-Rollup 上。

在 zk-Rollup 中构建通用 DApp

在 zk-Rollup 中有两种构建通用 DApp 的方法。

• 为不同的 DApp 构建专用电路（“ASIC”）
• 为智能合约执行构建一个通用的“EVM”编码

“ 电路（circuit）”是指零知识证明中使用的程序表示方法。例如，如果要证明 hash(x) = y，则需要使用 ASIC 电路重新编写散列函数。电路只支持非常有限的计算表达式（例如 R1CS 只支持加法（add）和乘法（mul））。因此，开发人员使用电路语言编写程序的过程非常困难，必须使用 add 和 mul 构建所有程序逻辑（包括 if else、循环等）。

第一种方法要求开发人员为不同的 DApp 设计专门的“ASIC”电路，这需要使用零知识证明最原始的方式。通过设计定制电路减少每个 DApp 的成本。然而，由于电路是“静态的”，不能为应用提供可组合性，并且需要专业的电路设计知识，因此开发体验很糟糕[2]。

第二种方法不需要任何特殊的设计或电路专业知识。这种基于机器证明的高级思想让任何程序可以在 CPU 上运行，因此开发者只需要构建一个通用的 CPU 电路来验证底层步骤。然后使用这个 CPU 电路来验证程序的执行。在此场景中，程序指的是智能合约，CPU 则是 EVM。但是，由于成本过高，过去几年并没有普遍采用这种方法。例如，即使开发者只想增加一个验证步骤，就需要承担整个 EVM 电路的成本。如果执行跟踪中有数千个步骤，那么 EVM 电路成本将是 1000 倍。[3]

最近，有很多研究在按照这两种方法优化 zk 证明，包括：

（i）提议新的零知识证明友好型语言 Poseidon hash ，其在电路中的效率是 SHA256 的 100 倍

（ii）通用可验证虚拟机，如TinyRAM

（iii）) 越来越多的通用优化技巧，如 Plookup，以及运行速度更快的密码学库。

我们之前建议为每个 DApp 设计“ASIC”电路，通过验证密码进行通信。但是，根据社区的反馈，我们改变了优先级，将重点关注在第二种方法，优先构建通用 EVM 电路（所谓的“zkEVM”）。zkEVM 将支持与 Layer 1 完全相同的开发体验。我们不会将底层设计的复杂性留给开发人员，而是通过定制的 EVM 电路设计来解决效率问题。

zkEVM 的设计挑战

zkEVM 很难构建，与 TinyRAM 不同，zkEVM 的设计和实现更具挑战性，原因如下：

首先，EVM 对椭圆曲线的支持有限。目前，EVM 仅支持 BN254 配对，不直接支持循环椭圆曲线，因此很难进行递归证明。其他专用协议在此限制下也很难使用，除非是 EVM 兼容的验证算法。

其次，EVM 字长为 256 位。EVM 在 256 位整数上运行（大多数常规 VM 在 32-64 位整数上运行），而 zk 证明在素数字段上工作。在电路内部进行“不匹配场算术”需要范围证明，这将在每个 EVM 步骤中增加大概 100 个约束，导致 EVM 电路尺寸扩大两个数量级。

第三，EVM 有很多特殊的操作码。EVM 与传统 VM 不同的是有许多特殊的操作码，例如CALL，还有执行上下文和 gas 相关的错误类型。这将给电路设计带来新的挑战。

第四，EVM 是基于堆栈的虚拟机。SyncVM ( zksync ) 和 Cario (starkware) 架构在基于寄存器的模型，并定义了特定的 IR/AIR。需要专门的编译器将智能合约代码编译成新的 zk 友好的 IR。这种方法是语言兼容而不是原生 EVM 兼容，基于堆栈的模型和直接支持原生工具链更难实现。

第五，以太坊存储布局的成本太大。以太坊存储布局高度依赖 Keccak 和 MPT [4]，它们都不是 zk 友好类型，并且会产生高昂的成本。例如，Keccak 哈希的电路大小是 Poseidon hash 的 1000 倍。但是，如果将 Keccak 替换为另一个哈希，则会对现有的以太坊基础设施造成一些兼容性问题。

第六，基于机器的证明有高昂的成本。即使能够妥善处理上述所有问题，仍然需要找到一种有效的方法将它们组合在一起以获得完整的 EVM 电路。正如我在上一节中提到的，简单的操作码add可能会导致整个 EVM 电路的成本。

为什么 zkEVM 有可能实现？

感谢研究人员在这方面取得的巨大进步，近两年来解决的效率问题越来越多，证明了 zkEVM 的可行性！主要的技术进步来自以下几个方面：

多项式承诺（polynomial commitment）的使用。在过去的几年里，大多数零知识证明协议都在使用 R1CS，PCP 查询被编码到了特定于应用的受信任起步设置（trusted setup）中。。这种情况通常会使电路会超出负载，并且无法进行自定义优化，因为每个约束的程度需要为 2（双线性配对（bilinear pairing）仅允许指数中的一次乘法）。开发者使用多项式承诺方案可以通过通用设置（universal setup）或者透明设置（transparent setup）将约束提升到任何程度，大幅提高后端的选择的灵活性。

数据表查询参数和自定义小工具。优化数据表查询参数首先由 Arya 中提出，然后在 Plookup 中进行优化。这可以为 zk 不友好的编程语句（例如 AND、XOR 等）省略很多按位运算。定制小工具可以让开发者高效地进行高度约束。 TurboPlonk 和 UltraPlonk 定义了优雅的语法，以便开发者更轻松地使用查询数据表和自定义小工具。这对于减少 EVM 电路的成本非常有帮助。

递归证明的可行性越来越高。在过去递归证明依赖于特殊的循环椭圆曲线（即基于 MNT 曲线的构造），需要大量的成本。目前更多的技术在不牺牲效率的前提下改变这种依赖情况。例如，Halo可以配对友好椭圆曲线，并使用特殊的内积参数来分摊递归成本。Aztec 表明可以直接对现有协议进行聚合证明（查询数据表可以减少非本地字段操作的成本，从而降低验证电路的成本）。这种方法可以极大地提高电路负载量的可扩展性。

硬件加速更加高效。我们制造了 GPU 和 ASIC/FPGA 加速器，并且关于 ASIC 证明者的论文已经被最大的计算机会议（ISCA）接受。GPU 证明器比Filecoin 的实现快大约 5 到 10 倍。这将大幅提高证明器的计算效率。

zkEVM 是如何工作的，如何建造它呢？

开发人员和用户的工作流程

开发人员可以使用任何与 EVM 兼容的语言来运行智能合约，并将编译后的字节码部署在 Scroll 上。然后，用户可以发送交易与智能合约进行交互。用户和开发者的体验将与 Layer 1 完全相同。但是，gas 费用显着降低，并且在 Scroll 上的交易订单即时预先确认（提款只需几分钟即可完成）。

zkEVM 的工作流程

即使 Layer 1 和 Layer 2 表面上的工作流程没有太多差别，但二者的底层处理过程完全不同：Layer 1 依赖于智能合约的重新执行；Layer 2 依赖于 zkEVM 电路的有效性证明。

让我们更详细地解释 Layer 1 和 Layer 2 交易的情况有何不同。

在 Layer 1 ，智能合约的字节码存储在以太坊存储中，交易将在 P2P 网络中广播。对于每个事务，每个全节点都需要加载相应的字节码并在 EVM 上执行以达到相同的状态（事务将作为输入数据）。

Layer 2 的智能合约字节码也以相同的方式进行操作，但后续步骤是交易将在链下发送到一个集中的 zkEVM 节点。然后，zkEVM 执行字节码并生成一个简洁的证明，以证明在应用交易后状态已正确更新。最后，Layer 1 合约将验证证明并更新状态，而无需重新执行交易。

让我们深入了解一下执行过程，看看 zkEVM 最终需要证明什么。在原生执行中，EVM 首先加载字节码，然后从头开始逐个执行字节码中的操作码，对每个操作码执行以下三个子步骤：

（i）从堆栈、内存或存储中读取元素

（ii）对这些元素执行一些计算

（iii）将结果写回堆栈、内存或存储。[5]例如，add操作码需要从堆栈中读取两个元素，将它们相加并将结果写回堆栈。

所以 zkEVM 的证明需要包含与执行过程相对应的以下几个方面：

• 字节码从存储中正确加载 （以便虚拟机正确地运行从给定地址加载的操作码）
• 字节码中的操作码逐个执行 （字节码按顺序执行，不会丢失或跳过任何操作码）
• 每个操作码都正确执行 （每个操作码中的三个子步骤都正确执行读写和计算）

zkEVM 设计亮点

在设计 zkEVM 的架构时，我们需要处理/解决上述三个问题。

第一，为密码验证器设计一个电路。这部分就像一个“可验证的存储”，我们通过使用密码验证器这种技术手段来保证验证结果的正确性。[6] 以默克尔树为例，部署的字节码将作为叶节点存储在 Merkle 树中。然后验证者可以使用简洁的证明来验证从给定地址加载的字节码（即验证电路中的默克尔路径）。对于以太坊存储，则需要电路兼容 Merkle Patricia Trie 和 Keccak 哈希函数。

第二，设计一个电路来将字节码与真实的执行产生关联。将字节码转移到静态电路中会带来一个问题：像 jump 这样的条件式操作码（与智能合约中的 loop、if else 语句相对应）可能会跳转到任何地方。在某个人使用特定输入运行该字节码之前，跳转目的地都是不确定的。这就是为什么我们需要验证实际的执行踪迹。执行踪迹可以被认为是 “展开的字节码”，包含按实际执行顺序排列的操作码（即，如果你跳转到另一个位置，踪迹中将包含该目标操作码和位置）。

证明者将直接提供执行踪迹作为电路的见证数据。我们需要证明该执行追踪是通过特定字节码使用特定的输入 “展开” 的工作，目的是强制让程序计数器的值保持一致。针对目的地不确定的问题，解决思路是让证明者提供一切数据。然后通过查找参数高效地检查一致性（即，证明带有准确全局计数器的操作码包含在 “总线” 中）。

第三，为每个操作码设计电路（证明每个操作码中的读写和计算都是正确的）。这是最重要的部分，证明执行跟踪中的每个操作码都是正确且一致的。如果将所有东西直接放在一起，将会带来高昂的成本。这里的优化方案是：

1）我们将读写和计算分成两个证明。一个证明会将所有操作码用到的元素都放到 “总线” 中，另一个证明会证明对 “总线” 上元素的计算是正确执行的。这会大幅降低每个部分的成本（生成计算证明时无需考虑整个 EVM 存储）。前者被称为 “状态证明”，后者被称为 “EVM 证明”。另一个发现是，查找声明可以有效处理 “总线映射” 。

2）我们可以为每个操作码设计度数更高的定制化约束（即，我们可以将一个 EVM word 切分成多个数据块，以便更高效地处理）。我们可以选择是否根据需求通过一个选择符多项式来 “打开” 一个约束。这样可以避免每个操作都要消耗整个 EVM 电路的成本。

这个架构最初由以太坊基金会提出，依然处于早期阶段，正在积极开发中。我们正在与以太坊基金会进行密切合作，旨在找到最佳方式实现该 EVM 电路。迄今为止，我们已经定义了 EVM 电路最重要的特点，并（使用 Halo2 库中的 UltraPlonk 语法）实现了一些操作码。更详细的内容将在后续文章中介绍。我们推荐感兴趣的读者阅读这篇文档。开发流程将是透明化的。这将是集整个社区之力的完全开源的设计。希望会有更多人加入进来，贡献出一份力量。

zkEVM 还能带来什么？

zkEVM 远不仅仅是 Layer 2 扩容。我们可以将它理解为通过 Layer 1 有效性证明扩展以太坊 Layer 1 的直接方式。这意味着不需要任何特殊的 Layer 2 就可以扩展现有的 Layer 1。

例如开发者可以将 zkEVM 当作全节点来使用，该证明可以用来直接证明现有状态之间的转换。所有 Layer 1 交易无需将任何东西迁移到 Layer 2 上，你可以直接证明！更宽泛地来说，你可以使用 zkEVM 为整个以太坊生成简洁证明，就像 Mina 那样。唯一需要增加的东西是证明递归（将区块的验证电路嵌入 zkEVM）[7]。

结论

zkEVM 可以为开发者和用户提供相同的体验。在不牺牲安全性的情况下，它的价格要便宜几个数量级。已经提出了以模块化方式构建它的架构。它利用最近在零知识证明方面的突破来减少成本（包括自定义约束、查找参数、证明递归和硬件加速）。我们期待看到更多的人加入 zkEVM 社区，与我们一起集思广益！

备注：

[1]: Starkware 于 2021 年 9 月 1 日的公告中声明已实现可组合性。

[2]: 电路是固定且静态的。例如，在将一个程序实现为电路时，你无法使用可变上限循环。上限必须固定为最大值。电路无法处理动态逻辑。

[3]: 为便于读者理解，我们在这里详细说明 EVM 电路的成本。正如前文所言，电路是固定且静态的。因此，EVM 电路需要包含所有可能的逻辑（这个体量是仅包含 add 的电路的 10000 倍）。这就意味着，即使你只想证明 add，你依然需要负担该 EVM 电路中可能包含的所有逻辑的成本。也就是说，成本被放大了 10000 倍。在执行追踪中，你需要证明一连串操作码，而且每个操作码都会带来高昂的成本。

[4]: EVM 本身并没有与默克尔-帕特里夏树（MPT）紧密绑定。目前，MPT 仅用于存储以太坊状态。要换一个很容易（有人提议使用 Verkle 树替换掉 MPT）。

[5]: 这是经过高度简化的抽象概念。从技术上来说，“EVM 状态” 的名单更长，包括程序计数器、gas 余量、调用栈（以上所有加上堆栈中每次调用的地址和静态）、一组日志和交易范围变量（热存储槽、退款、自毁）。我们可以另外引入针对不同调用环境的标识符来直接支持可组合性。
[6]: 由于存储量很大，我们使用累加器进行存储。内存和堆栈可以使用可编辑的 Plookup（我们可以通过这种方式有效地实现 “RAM”）。

[7]: 将一个完整的递归证明添加进 zkEVM 电路并非易事。实现递归的最好方式还是使用循环椭圆曲线（即，Pasta 曲线）。我们需要引入某种 “包装（wrapping）” 过程让递归在以太坊 Layer 1 上可验证。