作者: Ye Zhang@Scroll
感谢 Vitalik Buterin、Barry Whitehat、Chih-Cheng Liang、Kobi Gurkan 和 Georgios Konstantopoulos 的审阅和真知灼见。
太长不看
我们相信 zk-Rollup 会成为 “香饽饽” —— 其成本优势和极高的安全性使得一众 Layer 2 可扩展性方案相形见绌。然而，现有的 zk-Rollup 实现都是针对特定应用的，因此我们很难在某个 zk-Rollup 内构建具有可组合性的通用 dApp，把现有的应用迁移过来也无从谈起。我们引入了 zkEVM 用来为通用的 EVM 验证生成零知识证明。这样一来，我们就可以构建出完全兼容 EVM 的 zk-Rollup，以便现有以太坊应用轻松迁移到这个 zk-Rollup 上。
在本文中，我们明确指出了 zkEVM 在设计上面临哪些挑战以及为何 zkEVM 在当下有可能实现。我们还给出了更加具体、直观的认知，并概述了如何从头开始构建 zkEVM。
背景
zk-Rollup 是公认的最佳以太坊可扩展性方案。它不仅在安全性上媲美以太坊 Layer 1，而且在交易敲定速度上是 Layer 2 解决方案的翘楚（点击此处，查看详细的对比分析（原文、译本））。
从中长期来看，随着 ZK-SNARK 技术不断发展，zk-rollup 将在所有应用场景中力拔头筹。—— Vitalik Buterin
zk-Rollup 的基础原理是将大量交易打包到一个 Rollup 区块内，并在链下为该区块生成一个简洁证明。随后，Layer 1 上的智能合约只需验证该证明即可直接应用新的状态，无需重新执行这些交易。这样就可以节约一个数量级的 gas 费，因为证明的验证成本远低于重新执行的计算成本。另一个好处是可以通过数据压缩来节省存储空间（即，仅在链上存储最少量的数据用于验证）。
虽然 zk-Rollup 安全且高效，但是其应用依然局限于付款和互换（swap）。通用 dApp 构建起来很难，主要有以下两个原因：
第一，如果你想在某个 zk-Rollup 内开发 dApp，你需要使用一种特殊的语言（即，R1CS）来编写你的所有智能合约的逻辑。这种语言有着复杂的语法，而且要求使用者精通零知识证明。
第二，现有的 zk-Rollup 实现不支持可组合性1。因此，在 Layer 2 上，不同的 zk-Rollup 应用之间无法交互，严重破坏了 DeFi 应用的可组合性。
简而言之，zk-Rollup 目前对开发者并不友好，而且功能有限。这是我们想要解决的最大问题。我们想要通过直接支持原生 EVM 验证来提供最好的开发者体验，并在 Layer 2 上支持可组合性，让现有以太坊应用可以原封不动地迁移到 zk-Rollup 上。
在 zk-Rollup 中构建通用 dApp
我们可以通过以下两种方法在 zk-Rollup 内构建通用 dApp：
一种是为不同 dApp 构建专用电路（“ASIC”）。
另一种是构建通用 “EVM” 电路用于执行智能合约。
“电路（circuit）” 指的是零知识证明中使用的程序表示。例如，如果你想要证明 hash(x) = y，你需要使用电路形式重新编写哈希函数。电路形式只支持非常有限的表示（即，R1CS 只支持加法和乘法）。因此，使用 circuit 语言编写程序难度很高 —— 你只能使用加法和乘法来构建所有程序逻辑（包括 if else、循环等等）。
第一种方法要求开发者为不同 dApp 设计专用 “ASIC” 电路。这是最传统的使用零知识证明的方式。自定义的电路设计有助于降低各个 dApp 的成本。但是，这也带来了可组合性问题，因为电路是 “静态的”，而且对电路设计知识的高度依赖导致开发者体验很糟糕2。
第二种方法不需要任何特殊的设计，也不要求开发者具备极强的专业知识。这种基于机器的证明背后的深层概念是，任何程序终将运行在 CPU 上。因此，我们只需要构建一个通用 CPU 电路来验证低级 CPU 操作。然后，我们可以使用这个 CPU 电路来验证任何程序执行。就本文的应用场景而言，程序指的就是智能合约，CPU 就是 EVM。然而，由于成本过高，这个方法在过去几年里没有得到普遍采用。例如，即使你只想证明某一个操作中 add 的结果是正确的，你依然需要负担整个 EVM 电路的成本。如果你的执行追踪中有上千个操作，证明者就要负担 1000 倍的 EVM 电路成本3。
最近，有很多研究致力于利用这两种方法来优化零知识证明，包括（i）提议新的零知识证明友好型原语 Poseidon 哈希（Poseidon 哈希在电路中的效率是 SHA256 的 100 倍）；（ii）持续提高通用可验证虚拟机的效率，就像 TinyRAM 那样；（iii）越来越多的通用优化技巧，如 Plookup，以及运行速度更快的密码学库。
在我们之前的文章中，我们提议为每个 dApp 设计 “ASIC” 电路，并让它们通过密码学承诺进行通信。然而，根据社区的反馈，我们改变了研究重点，将聚焦于使用第二种方式构建通用 EVM 电路（所谓的 “zkEVM”）。zkEVM 将带来与 Layer 1 完全相同的开发体验。我们不会把设计复杂性留给开发者，而是利用自定义 EVM 电路设计取而代之，解决效率问题。
zkEVM 的设计挑战
zkEVM 构建起来很难。尽管多年来这种直觉都很清晰，但是至今还没有人成功构建出原生 EVM 电路。不同于 TinyRAM，zkEVM 在设计和实现上更具挑战性，具体原因如下：
第一，EVM 对椭圆曲线的支持有限。目前，EVM 只支持 BN254 配对。由于不直接支持循环椭圆曲线，EVM 很难实现证明递归。在这种设置下，我们也很难使用其它专用协议。验证算法必须是 EVM 友好型的。
第二，EVM 的 word 大小是 256 位。EVM 基于 256 位整数运行（就像大多数基于 32～64 位整数运行的普通虚拟机那样），零知识证明则 “天然” 基于素域运行。在电路中进行 “错配域算术” 需要范围证明，进而给每个 EVM 操作增加大约 100 个约束。这会将 EVM 电路大小增加两个数量级。
第三，EVM 有许多特殊的操作码。不同于传统虚拟机，EVM 有很多特殊的操作码，如 CALL ，以及与执行环境和 gas 相关的错误类型。这会给电路设计带来新的挑战。
第四，EVM 是基于堆栈的虚拟机。SyncVM（zksync）和 Cario（starkware）架构在基于寄存器的模型中定义自己的 IR/AIR。它们构建了一个专门的编译器来将智能合约代码编译成一个新的零知识证明友好型 IR。该方法是语言兼容的，而非原生 EVM 兼容的。无论是证明基于堆栈的模型，还是直接支持原生工具链，都会变得更加困难。
第五，以太坊存储布局带来了高昂的成本。以太坊存储布局高度依赖 Keccak 和一个巨型 MPT4。二者都不是零知识证明友好型的，而且会产生高昂的证明成本。例如，Keccak 哈希的电路大小是 Poseidon 哈希的 1000 倍。但是，如果你将 Keccak 哈希替换成另一种哈希，就会给现有的以太坊基础设施带来一些兼容问题。
第六，基于机器的证明带来了高昂的成本。即使你可以妥善处理上述所有问题，你依然需要找到一种有效的方法来将它们组合起来得到一个完整的 EVM 电路。正如我在上一节中提到的，即使像 add 这样简单的操作码也有可能需要你负担整个 EVM 电路的成本。
为何 zkEVM 在当下有可能实现
得益于研究者取得的重大进展，过去两年里越来越多效率问题得到了解决，zkEVM 的证明成本终于不再是障碍！最主要的技术进展体现在以下几个方面：
多项式承诺（polynomial commitment）的使用。过去几年来，大多数简洁零知识证明协议都使用 R1CS，PCP 查询被编码到了特定于应用的受信任起步设置（trusted setup）中。这往往会增加电路的大小，导致很多自定义优化都无法实现，因为每个约束的度必须是 2（双线性配对（bilinear pairing）只允许进行一次指数乘法计算）。有了多项式承诺方案，你可以通过通用设置（universal setup）乃至透明设置（transparent setup）将你的约束提高到任何阶，大幅提高了后端选择的灵活性。
查找表参数和自定义小工具的出现。另一个重要优化是查找表的使用。这个优化首次提议于 Arya，然后在 Plookup 中得到实现。对于零知识证明不友好型原语（即，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 上，已部署智能合约的字节码都存储在以太坊 storage（存储项）内。交易将在点对点网络中传播。对于每一笔交易，每个全节点需要加载对应的字节码并在 EVM 上执行以获得相同的状态（交易将作为输入数据）。
在 Layer 2 上，字节码同样存储在存储项内，用户的操作方式也相同。交易将在链下发送至一个中心化的 zkEVM 节点。然后，zkEVM 不单执行字节码，还将生成一个简洁证明来表明交易达成后状态已正确更新。最后，Layer 1 合约将验证该证明并更新状态，不再重新执行交易。
我们来深入了解一下执行过程，看看 zkEVM 最终需要证明的是什么。在原生执行中，EVM 将加载字节码并从头开始逐个执行字节码中的操作码。每个操作码都可以被看作是在执行以下三个步骤：(i) 从堆栈（stack）、memory 或存储项中读取元素；(ii) 基于这些元素执行计算；(iii) 将结果写入堆栈、memory 或存储项5。例如，add 操作码需要从堆栈中读取两个元素，将它们相加并将结果写入堆栈。
因此，显而易见的是，zkEVM 的证明需要包含以下几个方面（与执行流程对应）：
- 字节码从永久存储项中正确加载（你正在运行从某个地址加载的正确操作码）
- 字节码中的操作码始终逐一执行（字节码按顺序执行，不会遗漏或跳过任何操作码）
- 每个操作码均正确执行（每个操作码中的三个子操作都正确执行，R/W + 计算）
zkEVM 设计亮点
在为 zkEVM 设计架构时，我们需要分别采取措施满足上述三个方面的需求。
1. 我们需要为某个密码学累加器设计一个电路。
这是为了起到 “可验证存储器” 的作用，我们需要通过某种技术来证明读取过程是准确无误的。密码学累加器可以更高效地实现这一点 6。我们以默克尔树为例。已部署的字节码会被存储为默克尔树上的叶节点。然后，验证者可以使用简洁证明来验证该字节码是否正确加载自某个地址（即，验证电路中的默克尔路径）。针对以太坊存储，我们需要这个电路同时兼容默克尔-帕特里夏树和 Keccak 哈希函数。
2. 我们需要设计一个电路将字节码与实际的执行追踪关联起来。
将字节码转移到静态电路中会带来一个问题：像 jump 这样的条件式操作码（与智能合约中的 loop、if else 语句相对应）可能会跳转到任何地方。在某个人使用特定输入运行该字节码之前，跳转目的地都是不确定的。这就是为什么我们需要验证实际的执行踪迹。执行踪迹可以被认为是 “展开的字节码”，包含按实际执行顺序排列的操作码（即，如果你跳转到另一个位置，踪迹中将包含该目标操作码和位置）。
证明者将直接提供执行踪迹作为电路的见证数据。我们需要证明该执行追踪确实是特定的字节码使用特定的输入 “展开” 的。我们的想法是强制让程序计数器的值保持一致。针对目的地不确定的问题，解决思路是让证明者提供一切数据。然后，你可以使用查找参数高效地检查一致性（即，证明带有准确全局计数器的操作码包含在 “总线” 中）。
3. 我们需要为每个操作码设计电路（证明每个操作码中的读、写和计算都是正确的）。
这是最重要的部分 —— 证明执行追踪中的每个操作码都是正确且一致的。如果你直接将所有东西都放在一起，会产生高昂的成本。此处重要的优化思路是：
我们可以将 R/W 和计算分成两个证明。一个证明会将所有操作码用到的元素都放到 “总线” 中。另一个证明会证明对 “总线” 上元素的计算是正确执行的。这会大幅降低每个部分的成本（即，你在生成计算证明时无需考虑整个 EVM 存储）。在更详细的规范中，前者被称为 “状态证明”，后者被称为 “EVM 证明”。另一个发现是，查找声明可以有效处理 “总线映射” 。
我们可以为每个操作码设计度数更高的定制化约束（即，我们可以将一个 EVM word 切分成多个数据块，以便更高效地处理）。我们可以选择是否根据需求通过一个选择符多项式来 “打开” 一个约束。这样可以避免每个操作都要消耗整个 EVM 电路的成本。
这个架构最初由以太坊基金会提出，依然处于早期阶段，正在积极开发中。我们正在与以太坊基金会进行密切合作，旨在找到最佳方式实现该 EVM 电路。迄今为止，我们已经定义了 EVM 电路最重要的特点，并（使用 Halo2 库中的 UltraPlonk 语法）实现了一些操作码（点击此处查看）。更详细的内容将在后续文章中介绍。我们推荐感兴趣的读者阅读这篇文档。开发流程将是透明化的。这将是集整个社区之力的完全开源的设计。希望会有更多人加入进来，贡献出一份力量。
zkEVM 还能给我们带来什么？
zkEVM 远不仅仅是 Layer 2 扩容。我们可以将它理解为通过 Layer 1 有效性证明扩展以太坊 Layer 1 的直接方式。这意味着不需要任何特殊的 Layer 2 就可以扩展现有的 Layer 1。
例如，你可以将 zkEVM 当作全节点来使用。该证明可以用来直接证明现有状态之间的转换。无需将任何东西迁移到 Layer 2 上，你可以直接证明所有 Layer 1 交易！更宽泛地来说，你可以使用 zkEVM 为整个以太坊生成简洁证明，就像 Mina 那样。唯一需要增加的东西是证明递归（即，将区块的验证电路嵌入 zkEVM）7。
结论
zkEVM 可以为开发者和用户提供相同的体验，而且可以在不牺牲安全性的前提下将成本降低几个数量级。目前已经有人提议了一种架构，可以通过模块化方式构建 zkEVM。这个架构利用零知识证明的最新突破降低成本（包括自定义约束、查找参数、证明递归和硬件加速）。我们期待看到更多人为 zkEVM 社区贡献力量，与我们一起进行头脑风暴！
关于我们
Scroll Tech 是新成立的科技公司。我们的目标是利用强大的证明网络构建一个兼容 EVM 的 zk-Rollup（点击此处，查看简介）。我们团队目前专注于开发。我们正在积极招募开发者，有志者请联系 hr@scroll.tech 。如果你对本文的技术内容有任何问题，请通过 yezhang@scroll.tech 或私信联系我。
注：
Starkware 于 2021 年 9 月 1 日的公告中声明已实现可组合性（点击此处，查看公告）。
电路是固定且静态的。例如，在将一个程序实现为电路时，你无法使用可变上限循环。上限必须固定为最大值。电路无法处理动态逻辑。
为便于读者理解，我们在这里详细说明 EVM 电路的成本。正如前文所言，电路是固定且静态的。因此，EVM 电路需要包含所有可能的逻辑（这个体量是仅包含 add 的电路的 10000 倍）。这就意味着，即使你只想证明 add，你依然需要负担该 EVM 电路中可能包含的所有逻辑的成本。也就是说，成本被放大了 10000 倍。在执行追踪中，你需要证明一连串操作码，而且每个操作码都会带来高昂的成本。
EVM 本身并没有与默克尔-帕特里夏树（MPT）紧密绑定。目前，MPT 仅用于存储以太坊状态。要换一个很容易（有人提议使用 Verkle 树替换掉 MPT）。
这是经过高度简化的抽象概念。从技术上来说，“EVM 状态” 的名单更长，包括程序计数器、gas 余量、调用栈（以上所有加上堆栈中每次调用的地址和静态）、一组日志和交易范围变量（热存储槽、退款、自毁）。我们可以另外引入针对不同调用环境的标识符来直接支持可组合性。
由于存储量很大，我们使用累加器进行存储。内存和堆栈可以使用可编辑的 Plookup（我们可以通过这种方式有效地实现 “RAM”）。
将一个完整的递归证明添加进 zkEVM 电路并非易事。实现递归的最好方式还是使用循环椭圆曲线（即，Pasta 曲线）。我们需要引入某种 “包装（wrapping）” 过程让递归在以太坊 Layer 1 上可验证。
原文链接:
https://hackmd.io/@yezhang/S1_KMMbGt
