zkEVM 的设计存在什么挑战?目前有哪些技术解决方案?

原文:zkEVM(HackMD)

作者:Ye Zhang  

编译:EthereumCN

感谢 Vitalik Buterin、Barry Whitehat、Chih-Cheng Liang、Kobi Gurkan 和 Georgios Konstantopoulos 的审阅和评论

摘要

我们相信 zk-Rollup 迟早成为 L2 赛道的佼佼者 — 这是一个非常便宜且安全的一流 L2 扩容解决方案。然而,现存的 zk-Rollup 都是应用专用型的,这让开发者难以在 zkRollup 中构建通用的可组合的 DApp 并迁移现有的应用程序。我们引入了 zkEVM,它可以为通用的 EVM (以太坊虚拟机,Ethereum Virtual Machine) 验证零知识证明 (zk proofs)。这允许我们构建一个完全兼容 EVM 的 zk-Rollup,任何现有的以太坊应用程序都可以轻松地迁移过去。

在本文中,我们指出了 zkEVM 的设计挑战何在以及为什么现在这个方案可行。我们还给出了更加具体和直观的描述、并概述了如何从头开始构建 zkEVM。

背景

zk-Rollup  被视为以太坊最好的扩容解决方案。它的安全性可以与以太坊一层网络的安全性媲美,并且与其他 L2 解决方案相比,它最终确定时间最短。具体对比分析请看:https://vitalik.ca/general/2021/01/05/rollup.html

中长期来看,随着 ZK-SNARK 技术完善,ZK rollups 将在所有用例中脱颖而出。 —— Vitalik Buterin

zk-Rollup 的基本概念就是将大量的交易聚合进一个 Rollup 区块中并为链下区块生成一个简洁证明。然后 L1 上的智能合约仅需要验证该证明即可直接应用已更新的状态,而无需重新执行那些交易。这可以节省一大笔 gas 费,因为验证证明比重新执行计算要便宜得多了。还省了一笔费用的地方就是将数据压缩了 (即,只在链上保留最少的数据量用于验证)

虽然 zk-Rollup 安全且高效,它的应用程序仍局限于支付和代币转换。由于下列两个原因,很难去构建通用型的 DApps:

  • 首先,如果你想要在一个 zk-Rollup 中开发 DApps,你需要使用一种特殊的语言 (如 R1CS) 来编写你所有的智能合约逻辑。不仅所需要的语言的语法复杂,而且这样做还需要在零知识证明方面具有极强的专业知识。
  • 第二,目前的 zk-Rollup 不支持可组合性 [1]。这意味着 L2 中的 zk-Rollup 应用程序不能互相交互。这种特性极大地破坏了 DeFi 应用的可组合性。

简而言之,zk-Rollup 对开发者不友好,目前功能有限。

这是我们想要解决的最大问题。我们希望通过直接支持原生 EVM 验证,以便在 L2 中提供最好的开发体验和支持 L2 可组合性。这样现有的以太坊应用程序就可以简单地迁移到 zk-Rollup 上了。

在 zk-Rollup 中构建通用型 DApp

在 zk-Rollup 中构建通用 DApp 有两种方式:

  • 为不同的 DApp 构建专用集成电路 (application-specific circuit, ASIC)。
  • 为智能合约执行构建一个通用的 "EVM" 电路

“circuit”  指的是在零知识证明中使用的程序表现形式。比如,如果你想要证明 hash(x) = y,你需要使用电路形式重写哈希函数。这种电路形式只支持非常有限的表达式 (例如,R1CS 只支持加和乘)。因此,使用电路语言编写程序是非常困难的 —— 你必须使用加法和乘法来构建所有的程序逻辑 (包括 if else、loop 等等)。

第一种方法要求开发者为不同的 DApp 设计专门的 "ASIC" 电路。这是使用零知识证明最传统的方法。通过自定义电路设计,每个 DApp 的开销将会更小。然而,这种方法带来了可组合性的问题,因为电路是 "静态的",而且由于需要强大的电路设计专业知识,开发体验会十分不友好 [2]。

第二种方法不需要任何特殊的设计或开发者的专业知识。这种基于机器的证明背后的逻辑为:任何程序最终都会在 CPU 上运行,所以我们只需要构建一个通用 CPU 电路来验证低级的 CPU 操作。然后我们可以使用这个 CPU 电路来验证任何程序执行。在我们的场景中,程序是智能合约,而 CPU 是 EVM。然而,由于其巨大开销,在过去几年里这个方法并未被广泛应用。比如,尽管你只想要在一个步骤中证明 add  的结果是正确的,你仍然需要承担整个 EVM 电路的开销。如果在执行追踪中有数千个步骤,那么证明者的 EVM 电路开销将提高 1000 倍。[3]

最近,有很多研究按照下面这两种方法来优化 zk 证明,包括 (i) 提议新的 zk 友好的原语,即 Poseidon hash  可以在电路中实现比 SHA256 高 100 倍的效率,(ii) 目前正提高通用可验证 VM 的效率,如 TinyRAM,以及 (iii) 越来越多的通用优化技巧,如 Plookup,甚至速度更快的密码学库。

在我们的上一篇文章中,我们提议为每个 DApp 设计 “ASIC” 并让他们通过加密承诺实现通信。然而,根据社区的反馈,我们调了一下我们工作的优先级,即优先选择第二种方法。我们将专注于构建一个通用的 EVM 电路 (也就是所谓的 “zkEVM”)。在 zkEVM 上开发和在 L1 上开发的体验将相差无几。我们不会把设计复杂性留给开发者处理,而是通过自定义的 EVM 电路设计来负责并解决效率问题。

zkEVM 的设计挑战**

zkEVM 难以构建。尽管多年来我们一直很清楚这个问题,但没有人成功构建过原生 EVM 电路。与 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 哈希大 1000 倍。然而,如果将 Keccak 替换为另一个哈希,则会对现有的以太坊基础架构造成一些兼容性问题。
  • 第六,基于机器的证明具有巨大的开销。即使你可以正确地处理上述所有问题,你仍然需要找到一个有效的方法将它们组合在一起以获得完整的 EVM 电路。即使是像 add  这样简单的操作码也可能导致整个 EVM 电路开销的产生。

为什么现在又行得通了?

多亏了研究人员在这一领域取得的巨大进展,近两年解决了越来越多的效率问题,zkEVM 的证明成本最终是可以解决的!最大的技术改进来自以下几个方面:

  • 多项式承诺的使用。在过去几年里,大多数简洁的零知识证明协议都坚持在应用专用型的可信设置中使用带有 PCP 查询编码的 R1CS。由于每个约束的程度需要为 2 (双线性配对 ) 只允许指数相乘一次),所以电路的大小通常会增大,这导致你无法进行许多自定义优化。借助多项式承诺机制,你可以通过通用设置甚至透明设置将约束解除到任何程度。这为后端的选择提供了极大的灵活性。
  • 查找表参数和自定义小工具的外观。另一个强大的优化为查找表的使用。这种优化首先在 Arya  中提出,然后在 Plookup  中得到优化。这可以为 zk 不友好的原语 (即 AND、XOR 等按位运算) 节省很多开销。自定义小工具可以让你高效地进行高阶约束。TurboPlonk  和 UltraPlonk  的程序语法十分优雅,以便更轻松地使用查找表和自定义小工具。这对于减少 EVM 电路的开销非常有帮助。
  • 递归证明越来越可行。过去,递归证明会带来巨大开销,因为它依赖于特殊的配对友好型的循环椭圆曲线 (即基于 MNT 曲线的构造)。这引入了巨大的计算开销。然而,更多技术的出现正在使这成为可能,并且同时不牺牲效率。例如,Halo  可以避免对于配对友好型曲线的需要,并使用特殊的内积参数分摊递归成本。在 Aztec 中,你可以直接对现有协议进行证明聚合 (查找表可以减少非本地域运算的开销,从而可以使验证电路变得更小)。它可以大大提高支持的电路大小的规模。
  • 硬件加速使证明更高效。基于最大程度的理解,我们已经为证明者制作了最快的 GPU 和 ASIC/FPGA 加速器。我们的论文描述了 ASIC 证明器已经被今年最大的计算机会议 (ISCA) 接受。GPU 证明者比 Fliecoin 的实现快 5 到 10 倍。这可以大大地提高证明者的计算效率。

那么,它是如何运作的,以及如何构建它?

除了强大的直觉和技术改善之外,我们还需要更清楚地了解我们需要证明什么并找出更具体的架构。我们将在后续的文章中介绍更多技术细节和对比。而在下文,我们描述了整个工作流程和一些关键想法。

开发者和用户的工作流

对于开发者,他们可以使用任何与 EVM 兼容的语言实现智能合约,并将编译后的字节码部署到 Scroll 上。然后,用户可以发送交易,与部署的智能合约进行交互。用户和开发者的体验将与 Layer1 完全相同。但是,gas 费用显著降低,并且交易在 Scroll 上即时预先确认 (提款只需花几分钟即可完成敲定)。

zkEVM 的工作流

即使外部的工作流保持不变,Layer1 和 Layer2 的底层处理过程也完全不同:

  • Layer1 依赖于智能合约的重新执行。
  • Layer2 依赖于 zkEVM 电路的有效性证明。

下面给出了更加详细的解释,说明 L1 和 L2 上的交易有何不同。

在 L1 中,已部署的智能合约的字节码保存在以太坊的存储库中。交易将通过点对点 (P2P) 网络进行广播。对于每笔交易,每个全节点都需要加载相应的字节码并在 EVM 上执行它以使得状态一致 (交易将用作输入数据)。

在 L2 中,字节码也保存在存储库中,并且用户将以同样的方式进行操作。首先,交易会被发送至链下的一个中心化 zkEVM 节点中。然后,zkEVM 将生成一个简洁的证明 (证明在交易进行后已正确更新状态),而不是简单地执行字节码。最后,L1 上的合约将验证这些证明并更新状态,而无需重新执行交易。

接下来让我们深入了解一下执行过程,看看 zkEVM 最终需要证明什么。在本地执行中,EVM 会加载字节码并从头开始逐个执行字节码中的操作码。每个操作码都可以被认为是在执行以下三个子步骤:(i) 从堆栈、内存或存储中读取元素;(ii) 对这些元素执行一些计算;(iii) 将结果写回到堆栈、内存或存储库中。[5] 比如, add  操作码需要从堆栈中读取两个元素,将它们相加并将结果写回堆栈中。

因此,结论很显然,zkEVM 的证明需要包含与执行过程相对应的以下方面:

  • 字节码从永久存储中正确加载 (你正在运行从某个地址中加载出的正确操作码)
  • 字节码中的操作码是一个接一个执行的 (字节码按顺序执行,不会遗漏或跳过任何操作码)
  • 每个操作码都正确执行 (每个操作码中的三个子步骤都正确执行,R/W + 计算)

zkEVM 的设计亮点

在设计 zkEVM 的架构时,我们需要考虑如何逐一处理/解决上述三个方面的问题。

  1. 我们需要为一些加密累加器设计一个电路。它就像一个 “可验证的存储库”,我们需要一些技术来证明我们正在正确读取数据。可以使用加密累积器来有效地实现这一目标。[6] 让我们以默克尔树为例。已部署的字节码将作为默克尔树的一片叶子存储在上面。然后,验证者可以通过一个简洁的证明来验证该字节码是从一个给定的地址中正确加载的 (即,验证电路中的默克尔路径)。对于以太坊存储,我们需要电路与 Merkle Patricia Trie 和 Keccak 哈希函数兼容。
  2. 我们需要设计一个电路来将字节码与实际的执行追踪连接起来。将字节码移动到一个静态电路中存在的一个问题就是条件操作码,如 jump (对应于智能合约中的 "loop" 和 "if else" 语句)。它可以跳转 (jump) 到任何地方。在使用特定输入运行字节码之前,目标是不确定的。这就是为什么我们需要验证实际的执行追踪。执行追踪可以被认为是” 展开的字节码 “,它将包含实际执行顺序中的操作码序列 (即,如果你跳转到另一个位置,那么轨迹将包含目标操作码和目标位置)。证明者将直接提供执行追踪作为电路的见证。我们需要证明这份提供的执行追踪确实是从具有特定输入的字节码中” 展开 “的。其思想是强制程序计数器的值保持一致。为了处理不确定的目的地,则需要让证明者提供一切。然后你可以使用查找参数有效地检查一致性 (即,证明具有适当全局计数器的操作码包含在” 总线 “中)。
  3. 我们需要为每个操作码设计电路 (证明每个操作码中的读、写和计算都是正确的)。这是最重要的部分 — 证明执行追踪中每个操作码都是正确且一致的。如果你直接把所有东西都放在一起,将会带来一大笔开销。这里最重要的优化思想是:
    • 我们可以将 R/W 和计算分离成两个证明。一个是将所有操作码所需的元素提取到 ” 总线 “ 中。另一个将证明对来自 ” 总线 “ 的元素执行的计算是正确的。这可以极大地减少每一部分的开销 (即,你不需要在计算证明中考虑整个 EVM 存储)。在更加详细的规范中,第一个称为 ” 状态证明 “,第二个称为 ”EVM 证明 “。另一个观察是,” 总线映射 “ 可以由查找参数有效地处理。
    • 我们可以为每个操作码设计更高程度的自定义约束 (即,可以通过将 EVM 字分成几个块来有效求解)。我们可以根据需要通过选择多项式来决定是否 ” 开放 “ 一个约束。这样可以避免在每个步骤中产生整个 EVM 电路的开销。

这种架构首先由以太坊基金会提出,并且仍处于早期研发阶段中。我们正与基金会密切合作,以找到实现 EVM 电路的最佳解决方案。到目前为止,我们已经定义了其最重要的特征,一些操作码已经实现 (使用 Halo2 存储库中的 UltraPlonk 语法)。更多细节将在后续文章中介绍。我们建议有兴趣的读者阅读此文档。开发过程将是透明的。这将是社区共同努力以及完全开源的设计成果。希望更多的人能够加入并为此做出贡献。

zkEVM 还能带来些什么?

zkEVM 不仅仅是 L2 扩容那么简单。我们可以这样理解它,这是一个通过 L1 有效性证明来扩容以太坊 L1 的直接方式。这意味着,你可以不需要任何特殊 L2 的情况下扩容现存的 L1。

比如,你可以将 zkEVM 用作一个全节点。这个证明可以用来直接证明现有状态之间的转换 —— 不需要将任何东西移植到 L2 中,你可以直接证明所有的 L1 交易!更广泛地说,你可以使用 zkEVM 为整个以太坊生成一个简洁的证明,比如 Mina。唯一需要添加的是证明递归 (即,将区块的验证电路嵌入到 zkEVM 中)[7]。

结论

对于开发者和用户来说,在 zkEVM 上的开发和使用体验与在一层上的没什么区别。并且在不牺牲安全性的前提下,zkEVM 的交易费便宜了一个数量级。已经有人提出了一种架构,即以模块化的方式来构建 zkEVM。而且,zkEVM 利用了最近在零知识证明方面的突破来减少开销 (包括自定义约束、查找参数、证明递归和硬件加速)。我们期待看到更多的人加入 zkEVM 社区,为其开发做出努力!


脚注

[1] Starkware 在几天前宣称其实现了可组合性 (参考文章)

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

[3] 为了更清楚地说明这一点,我们在这里详细阐述了 EVM 电路的成本。正如我们前面所描述的,电路是固定的和静态的。因此,EVM 电路需要包含所有可能的逻辑 (比单纯的 add  操作码要大 10,000 倍)。这意味着即便你只是想证明 add,你仍然需要承担 EVM 电路中所有可能逻辑的开销。这将使成本增加 10,000 倍。在执行追踪中,你需要验证一系列操作码,而每个操作码都产生很大的开销。

[4] EVM 本身没有与 Merkle Patricia tree 紧密绑定。MPT 就是目前以太坊状态的存储方式。要换成另一个并不难 (如,目前有人提议使用 Verkle trees  替换 MPT)。

[5] 这是一个高度简化的抽象概念。从技术上讲,”EVM 状态 “ 的列表更长,包括 PC、剩余 gas、调用堆栈 (以上所有加上堆栈中每次调用的地址和静态)、一组日志和交易范围的变量 (热存储槽、退款、自毁)。我们可以针对不同的调用环境添加标识符来直接支持可组合性。

[6] 由于存储量很大,我们使用累加器进行存储。对于内存和堆栈,可以使用可编辑的 Plookup ("RAM" 可以通过这种方式有效实现)。

[7] 向 zkEVM 电路添加一个完整的递归证明是很重要的。进行递归的最佳方法仍然是使用循环椭圆曲线 (即 Pasta 曲线)。需要一些 ” 封装“ 过程以使其在以太坊 L1 上可验证。

ECN 的翻译工作旨在为中国以太坊社区传递优质资讯和学习资源,文章版权归原作者所有,转载须注明原文出处。

免责声明:作为区块链信息平台,本站所发布文章仅代表作者及嘉宾个人观点,与 Web3Caff 立场无关。本文内容仅用于信息分享,均不构成任何投资建议及要约,并请您遵守所在国家或地区的相关法律法规。