风险提示:请理性看待区块链,树立正确的货币观念和投资理念,不要盲目跟风投资,本站内容不构成投资建议,请谨慎对待。 免责声明:本站所发布文章仅代表个人观点,与highland-crypto官方立场无关

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

本文介绍 zkEVM 的设计挑战以及可行性,并提出了从零开始构建 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 上可验证。

原创文章,作者:ChainCatcher 链捕手,如若转载,请注明出处:https://highland-crypto.com/2861/

发表回复

您的电子邮箱地址不会被公开。