为何 zkEVM 在当下有可能实现?一文了解 zkEVM 的设计挑战与工作流程_COSM:MOS

作者:?Ye

感谢VitalikButerin、BarryWhitehat、Chih-ChengLiang、KobiGurkan和GeorgiosKonstantopoulos的审阅和真知灼见。

太长不看

我们相信zk-Rollup会成为“香饽饽”——其成本优势和极高的安全性使得一众Layer2可扩展性方案相形见绌。然而,现有的zk-Rollup实现都是针对特定应用的,因此我们很难在某个zk-Rollup内构建具有可组合性的通用dApp,把现有的应用迁移过来也无从谈起。我们引入了zkEVM用来为通用的EVM验证生成零知识证明。这样一来,我们就可以构建出完全兼容EVM的zk-Rollup,以便现有以太坊应用轻松迁移到这个zk-Rollup上。

在本文中,我们明确指出了zkEVM在设计上面临哪些挑战以及为何zkEVM在当下有可能实现。我们还给出了更加具体、直观的认知,并概述了如何从头开始构建zkEVM。

背景

zk-Rollup?是公认的最佳以太坊可扩展性方案。它不仅在安全性上媲美以太坊Layer1,而且在交易敲定速度上是Layer2解决方案的翘楚)。

从中长期来看,随着ZK-SNARK技术不断发展,zk-rollup将在所有应用场景中力拔头筹。——VitalikButerin

zk-Rollup的基础原理是将大量交易打包到一个Rollup区块内,并在链下为该区块生成一个简洁证明。随后,Layer1上的智能合约只需验证该证明即可直接应用新的状态,无需重新执行这些交易。这样就可以节约一个数量级的gas费,因为证明的验证成本远低于重新执行的计算成本。另一个好处是可以通过数据压缩来节省存储空间。

虽然zk-Rollup安全且高效,但是其应用依然局限于付款和互换。通用dApp构建起来很难,主要有以下两个原因:

第一,如果你想在某个zk-Rollup内开发dApp,你需要使用一种特殊的语言来编写你的所有智能合约的逻辑。这种语言有着复杂的语法,而且要求使用者精通零知识证明。

美SEC专员:不明白为何比特币现货ETF申请决定需要花费这么长时间:1月5日消息,在周二发布的一份通知中,SEC指出,“指定一个较长的期限来发布批准或不批准该ETF的指令是合适的”。消息传出后,比特币的价格并未受到影响,仍在4.7万美元以下的盘整区间内徘徊。

虽然加密货币爱好者已经习惯了比特币现货ETF申请被拒绝和延迟,但SEC专员Hester Peirce也想知道为什么要花这么长时间。在接受行业媒体采访时,Peirce表示:“我不敢相信我们还在谈论这件事,就好像我们在等待一件事发生一样……甚至在最近,我们还否决了一系列的此类ETF申请,而那些声明仍在使用我认为在现下已经过时的论证方法。”(Cointelegraph)

此前消息,美国SEC已将有关NYDIG比特币ETF的决定推迟至3月16日。[2022/1/5 8:27:29]

第二,现有的zk-Rollup实现不支持可组合性1。因此,在Layer2上,不同的zk-Rollup应用之间无法交互,严重破坏了DeFi应用的可组合性。

简而言之,zk-Rollup目前对开发者并不友好,而且功能有限。这是我们想要解决的最大问题。我们想要通过直接支持原生EVM验证来提供最好的开发者体验,并在Layer2上支持可组合性,让现有以太坊应用可以原封不动地迁移到zk-Rollup上。

在zk-Rollup中构建通用dApp

我们可以通过以下两种方法在zk-Rollup内构建通用dApp:

一种是为不同dApp构建专用电路。

另一种是构建通用“EVM”电路用于执行智能合约。

“电路”指的是零知识证明中使用的程序表示。例如,如果你想要证明hash(x)=y,你需要使用电路形式重新编写哈希函数。电路形式只支持非常有限的表示。因此,使用circuit语言编写程序难度很高——你只能使用加法和乘法来构建所有程序逻辑。

第一种方法要求开发者为不同dApp设计专用“ASIC”电路。这是最传统的使用零知识证明的方式。自定义的电路设计有助于降低各个dApp的成本。但是,这也带来了可组合性问题,因为电路是“静态的”,而且对电路设计知识的高度依赖导致开发者体验很糟糕2。

以太坊开发者Tim Beiko解释为何柏林升级没有纳入EIP-2537:以太坊开发者Tim Beiko解释为何柏林升级没有纳入EIP-2537表示,其在柏林升级需要更多测试,团队总体都同意,但是当我们讨论将它包含在伦敦升级时,有人提出了一个我们应该使用的新库,并可能修改gas成本,这需要更多的测试,因为它没有削减gas。此外,它从一个非常好的拥有(预存款合约启动以验证存款)变成了“我们在分片之前需要这个”,因此紧迫性大大降低。[2021/6/8 23:21:36]

第二种方法不需要任何特殊的设计,也不要求开发者具备极强的专业知识。这种基于机器的证明背后的深层概念是,任何程序终将运行在CPU上。因此,我们只需要构建一个通用CPU电路来验证低级CPU操作。然后,我们可以使用这个CPU电路来验证任何程序执行。就本文的应用场景而言,程序指的就是智能合约,CPU就是EVM。然而,由于成本过高,这个方法在过去几年里没有得到普遍采用。例如,即使你只想证明某一个操作中?add?的结果是正确的,你依然需要负担整个EVM电路的成本。如果你的执行追踪中有上千个操作,证明者就要负担1000倍的EVM电路成本3。

最近,有很多研究致力于利用这两种方法来优化零知识证明,包括提议新的零知识证明友好型原语?Poseidon哈希;持续提高通用可验证虚拟机的效率,就像?TinyRAM?那样;越来越多的通用优化技巧,如Plookup,以及运行速度更快的密码学库。

在我们之前的文章中,我们提议为每个dApp设计“ASIC”电路,并让它们通过密码学承诺进行通信。然而,根据社区的反馈,我们改变了研究重点,将聚焦于使用第二种方式构建通用EVM电路。zkEVM将带来与Layer1完全相同的开发体验。我们不会把设计复杂性留给开发者,而是利用自定义EVM电路设计取而代之,解决效率问题。

zkEVM的设计挑战

zkEVM构建起来很难。尽管多年来这种直觉都很清晰,但是至今还没有人成功构建出原生EVM电路。不同于TinyRAM,zkEVM在设计和实现上更具挑战性,具体原因如下:

法院要求SEC出具有关为何批准BTC和ETH为非证券的文件:数据研究员Leonidas Hadjiloizou 发推文说,法院已同意Ripple的申请,要求SEC出具有关为何批准比特币和以太坊为非证券的文件,另外还包括美国SEC关于XRP地位的内部通信以及有关另外十名托管人的文件。同时,美国地方法院法官Sarah Netburn裁定,Ripple Labs和SEC在4月6日下午2:00通过电话会议讨论相关细节。(U.today)[2021/3/25 19:18:12]

第一,EVM对椭圆曲线的支持有限。目前,EVM只支持BN254配对。由于不直接支持循环椭圆曲线,EVM很难实现证明递归。在这种设置下,我们也很难使用其它专用协议。验证算法必须是EVM友好型的。

第二,EVM的word大小是256位。EVM基于256位整数运行,零知识证明则“天然”基于素域运行。在电路中进行“错配域算术”需要范围证明,进而给每个EVM操作增加大约100个约束。这会将EVM电路大小增加两个数量级。

第三,EVM有许多特殊的操作码。不同于传统虚拟机,EVM有很多特殊的操作码,如?CALL?,以及与执行环境和gas相关的错误类型。这会给电路设计带来新的挑战。

第四,EVM是基于堆栈的虚拟机。SyncVM和?Cario架构在基于寄存器的模型中定义自己的IR/AIR。它们构建了一个专门的编译器来将智能合约代码编译成一个新的零知识证明友好型IR。该方法是语言兼容的,而非原生EVM兼容的。无论是证明基于堆栈的模型,还是直接支持原生工具链,都会变得更加困难。

第五,以太坊存储布局带来了高昂的成本。以太坊存储布局高度依赖?Keccak?和一个巨型?MPT4。二者都不是零知识证明友好型的,而且会产生高昂的证明成本。例如,Keccak哈希的电路大小是Poseidon哈希的1000倍。但是,如果你将Keccak哈希替换成另一种哈希,就会给现有的以太坊基础设施带来一些兼容问题。

第六,基于机器的证明带来了高昂的成本。即使你可以妥善处理上述所有问题,你依然需要找到一种有效的方法来将它们组合起来得到一个完整的EVM电路。正如我在上一节中提到的,即使像?add?这样简单的操作码也有可能需要你负担整个EVM电路的成本。

声音 | Samson Mow:很难理解为何质疑Liquid网络不是真正的侧链:据Bitcoinist消息,Blockstream首席战略官Samson Mow近日表示,很难理解为何会有人质疑Liquid网络并不是真正的侧链。Liquid网络与两种数字货币锚定,并且其数据可在其他链上被验证。[2018/10/13]

为何zkEVM在当下有可能实现

得益于研究者取得的重大进展,过去两年里越来越多效率问题得到了解决,zkEVM的证明成本终于不再是障碍!最主要的技术进展体现在以下几个方面:

多项式承诺的使用。过去几年来,大多数简洁零知识证明协议都使用R1CS,PCP查询被编码到了特定于应用的受信任起步设置中。这往往会增加电路的大小,导致很多自定义优化都无法实现,因为每个约束的度必须是2只允许进行一次指数乘法计算)。有了多项式承诺方案,你可以通过通用设置乃至透明设置将你的约束提高到任何阶,大幅提高了后端选择的灵活性。

查找表参数和自定义小工具的出现。另一个重要优化是查找表的使用。这个优化首次提议于Arya,然后在?Plookup?中得到实现。对于零知识证明不友好型原语来说,查找表可以省很多事。自定义小工具可以高效实现高阶的约束。TurboPlonk?和?UltraPlonk?定义了优雅的程序语法,降低了使用查找表和定义自定义小工具的难度。这对于降低EVM电路的成本帮助很大。

递归证明的可行性越来越高。过去,递归证明会带来很高的成本,因为它依赖特殊的配对友好型循环椭圆曲线。这会产生很高的计算成本。然而,越来越多技术能够在不牺牲效率的情况下使得递归证明成为可能。例如,Halo?无需配对友好型曲线,还可以使用特殊的内积参数来摊销递归成本。Aztec证明了可以直接聚合现有协议的证明。同样的电路规模现在能够实现更多的功能。

硬件加速正在提高证明效率。据我们了解,我们已经为证明程序打造了最快的GPU和ASIC/FPGA加速器。我们关于ASIC证明程序的论文已于今年被顶级计算机学术会议ISCA接受了。我们的GPU证明器比?Filecoin的实现快了大约5至10倍,可大幅提高证明器的计算效率。

美国“韭菜”跑步进场 美国70岁买家不知比特币为何物:据报道,美国70岁的比特币投资者Rita Scott在孙子的帮助下卖掉了她的比特币,短短几周赚了45%的收益率。在这之前,她根本不知道什么是比特币,还以为是硬币。而在美国,有很多人甚至想刷信用卡来买比特币。[2017/11/30]

zkEVM是如何运作和构建的?

除了强烈的直觉和技术改进,我们还得想明白我们需要证明的是什么,并构思好一个更加具体的架构。更多的技术细节和对比分析会留到之后的文章中进行介绍。在本文中,我们会介绍整个工作流程和一些核心概念。

开发者和用户的工作流程

开发者可以使用EVM兼容语言实现智能合约并在Scroll上部署编译好的字节码。之后,用户可以发送交易来与已经部署好的智能合约进行交互。用户和开发者将获得与在Layer1上相同的体验。但是,gas费会显著降低,交易将在Scroll上即时得到预先确认。

zkEVM的工作流程

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

Layer1靠的是重新执行智能合约。Layer2靠的是zkEVM电路的有效性证明

我们来详细解释下Layer1和Layer2上的交易有何不同。

在Layer1上,已部署智能合约的字节码都存储在以太坊storage内。交易将在点对点网络中传播。对于每一笔交易,每个全节点需要加载对应的字节码并在EVM上执行以获得相同的状态。

在Layer2上,字节码同样存储在存储项内,用户的操作方式也相同。交易将在链下发送至一个中心化的zkEVM节点。然后,zkEVM不单执行字节码,还将生成一个简洁证明来表明交易达成后状态已正确更新。最后,Layer1合约将验证该证明并更新状态,不再重新执行交易。

我们来深入了解一下执行过程,看看zkEVM最终需要证明的是什么。在原生执行中,EVM将加载字节码并从头开始逐个执行字节码中的操作码。每个操作码都可以被看作是在执行以下三个步骤:(i)从堆栈、memory或存储项中读取元素;(ii)基于这些元素执行计算;(iii)将结果写入堆栈、memory或存储项5。例如,add?操作码需要从堆栈中读取两个元素,将它们相加并将结果写入堆栈。

因此,显而易见的是,zkEVM的证明需要包含以下几个方面:

字节码从永久存储项中正确加载字节码中的操作码始终逐一执行每个操作码均正确执行

zkEVM设计亮点

在为zkEVM设计架构时,我们需要分别采取措施满足上述三个方面的需求。

1.我们需要为某个密码学累加器设计一个电路。

这是为了起到“可验证存储器”的作用,我们需要通过某种技术来证明读取过程是准确无误的。密码学累加器可以更高效地实现这一点?6。我们以默克尔树为例。已部署的字节码会被存储为默克尔树上的叶节点。然后,验证者可以使用简洁证明来验证该字节码是否正确加载自某个地址。针对以太坊存储,我们需要这个电路同时兼容默克尔-帕特里夏树和Keccak哈希函数。

2.我们需要设计一个电路将字节码与实际的执行追踪关联起来。

将字节码转移到静态电路中会带来一个问题:像?jump?这样的条件式操作码可能会跳转到任何地方。在某个人使用特定输入运行该字节码之前,跳转目的地都是不确定的。这就是为什么我们需要验证实际的执行踪迹。执行踪迹可以被认为是“展开的字节码”,包含按实际执行顺序排列的操作码。

证明者将直接提供执行踪迹作为电路的见证数据。我们需要证明该执行追踪确实是特定的字节码使用特定的输入“展开”的。我们的想法是强制让程序计数器的值保持一致。针对目的地不确定的问题,解决思路是让证明者提供一切数据。然后,你可以使用查找参数高效地检查一致性。

3.我们需要为每个操作码设计电路。

这是最重要的部分——证明执行追踪中的每个操作码都是正确且一致的。如果你直接将所有东西都放在一起,会产生高昂的成本。此处重要的优化思路是:

我们可以将R/W和计算分成两个证明。一个证明会将所有操作码用到的元素都放到“总线”中。另一个证明会证明对“总线”上元素的计算是正确执行的。这会大幅降低每个部分的成本。在更详细的规范中,前者被称为“状态证明”,后者被称为“EVM证明”。另一个发现是,查找声明可以有效处理“总线映射”。

我们可以为每个操作码设计度数更高的定制化约束。我们可以选择是否根据需求通过一个选择符多项式来“打开”一个约束。这样可以避免每个操作都要消耗整个EVM电路的成本。

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

zkEVM还能给我们带来什么?

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

例如,你可以将zkEVM当作全节点来使用。该证明可以用来直接证明现有状态之间的转换。无需将任何东西迁移到Layer2上,你可以直接证明所有Layer1交易!更宽泛地来说,你可以使用zkEVM为整个以太坊生成简洁证明,就像Mina那样。唯一需要增加的东西是证明递归7。

结论

zkEVM可以为开发者和用户提供相同的体验,而且可以在不牺牲安全性的前提下将成本降低几个数量级。目前已经有人提议了一种架构,可以通过模块化方式构建zkEVM。这个架构利用零知识证明的最新突破降低成本。我们期待看到更多人为zkEVM社区贡献力量,与我们一起进行头脑风暴!

关于我们

ScrollTech是新成立的科技公司。我们的目标是利用强大的证明网络构建一个兼容EVM的zk-Rollup。我们团队目前专注于开发。我们正在积极招募开发者,有志者请联系。如果你对本文的技术内容有任何问题,请通过或私信联系我。

注:

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

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

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

EVM本身并没有与默克尔-帕特里夏树紧密绑定。目前,MPT仅用于存储以太坊状态。要换一个很容易。

这是经过高度简化的抽象概念。从技术上来说,“EVM状态”的名单更长,包括程序计数器、gas余量、调用栈、一组日志和交易范围变量。我们可以另外引入针对不同调用环境的标识符来直接支持可组合性。

由于存储量很大,我们使用累加器进行存储。内存和堆栈可以使用可编辑的Plookup。

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

原文链接:

https://hackmd.io/@yezhang/S1_KMMbGt

郑重声明: 本文版权归原作者所有, 转载文章仅为传播更多信息之目的, 如作者信息标记有误, 请第一时间联系我们修改或删除, 多谢。

金智博客

[0:15ms0-4:673ms