干货 | zkEVM:设计挑战与解决思路
发布时间:2021-10-15
摘要: 感谢您对Vitalik Buterin、Barry Whitehat、Chih-Cheng Liang、Kobi Gurkan、Georgios Konstantopoulos的阅读和洞察。 太长不看 zk-Rollup相信会成为“盛宴”——。 由于其成本优势和极高的安全性,第2层的可

感谢您对Vitalik Buterin、Barry Whitehat、Chih-Cheng Liang、Kobi Gurkan、Georgios Konstantopoulos的阅读和洞察。

太长不看

zk-Rollup相信会成为“盛宴”——。 由于其成本优势和极高的安全性,第2层的可扩展性计划很差。 但是,由于现有的zk-Rollup的实现都是以特定的APP为对象的,所以在某个zk-Rollup内构建可组合的通用dApp很困难,即使迁移现有的APP应用也变得不值一提。 我们导入了zkEVM,为通用的EVM验证生成了知识零证明。 这样,您就可以构建与EVM完全兼容的zk-Rollup,以便现有的以太网APP应用程序可以轻松地迁移到此zk-Rollup。

本文清楚地说明了zkEVM在设计上面临哪些挑战,以及为什么zkEVM目前能够实现。 我们还展示了更加具体直观的认知,就从一开始就构筑zkEVM的方法进行了概述。

背景

zk-Rollup是公认的最好的以太坊扩展性方案。 在安全性方面不仅可以与以太坊第一层媲美,在交易决策速度方面也是第二层解决方案的优势。 (点击此处进行详细的比较分析(原文、翻译) )。

从中长期来看,随着ZK-SNARK技术的发展,zk-rollup将在所有应用场景中拔得头筹。 —— Vitalik Buterinzk-Rollup的基本原理是将大量事务打包为一个Rollup块,并在链下生成该块的简要证明。 然后,第1层智能合约只需验证证书,即可直接应用新状态,而无需重新执行这些交易。 这样可以节省一位数的gas费用,因为经证明的验证成本远远低于重新运行的计算成本。 另一个好处是通过数据压缩可以节省存储容量。 这意味着存储在链中的数据量将被最小化以用于验证。

虽然zk-Rollup安全高效,但其应用仍然局限于支付和交换(swap )。 通用dApp的构建困难主要有以下两个原因。

第一,如果要在某个zk-Rollup内开发dApp,则必须使用特殊语言(R1CS )来创建所有智能合约的逻辑。 该语言具有复杂的语法,要求使用者熟悉零知识证明。 第二,现有的zk-Rollup实现不支持组合可能性1。 因此,在Layer 2中,不同的ZK-roll up APP应用之间不能进行相互作用,从而严重损害了defi APP应用的组合性。 简单地说,zk-Rollup现在对开发者不友好,功能有限。 这是我们想解决的最大问题。 我们希望通过直接支持本机EVM身份验证提供最佳的开发者体验,并在第2层支持可组合性,以确保现有的以太网APP应用程序能够直接迁移到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有许多特殊的操作码,如呼叫、运行环境和与gas相关的错误类型。 这给电路设计带来新的挑战。 第四,EVM是基于堆栈的虚拟机。 同步虚拟机(ZK同步)和电信星际(cario stark ware )体系结构在基于寄存器的模型中定义了自己的IR/AIR。 构建了专用编译器,用于将智能合约代码编译成新的零知识证明友好IR。 此方法与本机EVM不兼容,而是与语言兼容。 证明基于堆栈的模型,或者直接支持本机工具链,都变得更加困难。 第五,以太坊的存储布局带来了高昂的成本。 以太坊的存储布局在很大程度上依赖于Keccak和巨大的MPT4。 两者都不是零知识的证明友好型,会产生很高的证明成本。 例如,Keccak散列的电路大小是Poseidon散列的1000倍。 但是,将Keccak散列替换为其他散列会导致现有以太网基础架构出现兼容性问题。 第六,机器证明带来了高昂的成本。 即使能够妥善处理上述所有问题,也需要找到将它们组合得到完整的EVM电路的有效方法。 如上节所述,像add这样简单的操作码也可能需要承担整个EVM电路的成本。

为何 zkEVM 在当下有可能实现

多亏了研究者的巨大进展,在过去的两年中解决了越来越多的效率问题,zkEVM的证明成本终于不再是障碍! 最主要的技术进展体现在以下方面。

使用多项式承诺(polynomial commitment )。 近年来,大多数简单的零知识证明协议都使用R1CS,PCP查询被编码为特定于APP的可信启动设置(trusted setup )。 这往往会增加电路的大小,导致许多定制优化无法实现。 因为每个约束的度必须是2。 (双线性配对(bilinear pairing )只允许进行一次指数乘法计算。 如果有多项式约定方案,可以通过通用设置或透明设置将约束提高到任何级别,从而大大提高了后端选择的灵活性。 查找表的参数和自定义小工具的出现。 另一个重要的优化是使用查找表。 这个优化首次在Arya上提出,之后在Plookup上实现。 对于知识零证明的不友好原语,也就是AND和XOR等比特运算来说,查找表可以省去很多麻烦。 自定义小工具可以有效地实现高级约束。 TurboPlonk和UltraPlonk定义了优雅的程序语法,减少了使用查找表和定义自定义小工具的困难。 这将大大有助于降低EVM电路的成本。 递归证明的可行性越来越高。 过去,递归证明依赖于特殊的配对友好循环椭圆曲线,即基于MNT曲线的结构,因此成本很高。 这个产生很高的计算成本。 但是,越来越多的技术使递归证明成为可能,而不牺牲效率。 例如,Halo不需要友好曲线配对,也可以使用特殊的内积参数来摊销递归成本。 Aztec证明了可以直接聚合现有的协议。 查找表降低了非本地域运算的成本,减小了验证电路的大小。 同样的电路规模可以实现更多的功能了。 硬件加速提高了证明效率。 据我们了解,为了证明程序,我们构建了最快的GPU和ASIC/FPGA加速器。 我们关于ASIC证明计划的论文今年被顶级计算机学术会议ISCA接受了。 我们的GPU证明器比Filecoin的实现快约5到10倍,可以大大提高证明器的计算效率。

zkEVM 是如何运作和构建的?

不仅要有很强的直觉和技术的改善,还必须理解需要证明的事情,构思更具体的框架。 更多的技术细节和比较分析将留在后面的文章中介绍。 本文介绍了整个工作流和几个主要概念。

开发者和用户的工作流程

开发人员可以使用EVM兼容语言实现智能合约,并将编译的字节码部署到Scroll。 然后,用户可以发送交易,与已部署的智能合约进行交互。 用户和开发者将获得与第1层相同的体验。 但是,gas费用将明显下降,交易将在Scroll中即时得到事先确认(取现将在几分钟内决定)

zkEVM 的工作流程

即使外部工作流是固定的,第1层和第2层的基本处理过程也完全不同。

第1层依赖于智能合约的再次运行。 第2层依赖于zkEVM电路的有效性,下面详细说明第1层和第2层的交易有什么不同。

在第1层中,所有已部署的智能合约字节码都存储在以太网存储器中。 交易通过点对点网络传播。 对于每个事务,每个完整节点都必须加载相应的字节码,并在EVM上运行以获得相同的状态。 事务用作输入数据。

在第2层中,字节码也存储在内存条目中,用户的操作方法也相同。 交易被发送到链下集中的zkEVM节点。 然后,zkEVM不仅会执行字节码,还会生成一个简要的证书,表明交易成功后状态已正确更新。 最后,第1层合同将验证证书并更新状态,从而不再重新执行交易。

让我们仔细看看运行过程,看看zkEVM最终需要证明的东西。 在本机运行中,EVM加载字节码,并从头开始运行字节码中的操作码。 每个操作码可以被认为是执行三个步骤: (I )从堆栈(stack )、memory或存储中读取元素。 (ii )基于这些元素执行计算(iii )将结果写入堆栈、内存或存储项目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不仅仅是第2层的扩展。 这可以理解为证明了通过第1层的有效性扩展以太层1的直接方式。 这意味着不需要特殊的第2层就可以扩展现有的第1层。

例如,可以将zkEVM用作完整节点。 这个证明可以用来直接证明现有状态之间的转移。 没有必要迁移到第2层,可以直接证明所有的第1层交易! 更广泛地说,可以使用zkEVM生成整个以太坊的简明证书。 就像Mina一样。 需要添加的只是证明递归。 也就是说,在zkevm(7中嵌入块的验证电路。

结论

zkEVM为开发者和用户提供了同样的体验,可以在不牺牲安全性的情况下降低几个数量级的成本。 现在,提出了可以通过模块方式构筑zkEVM的架构。 该体系结构利用知识零证明方面的最新突破,降低定制约束、查找参数、递归证明、硬件加速等成本。 我期待着更多的人为zkEVM社区效力,和我们一起头脑风暴!

注:

Starkware在2021年9月1日的公告中宣布实现了组合可能性(点击此处查看公告)。 电路是固定的和静态的。 例如,作为电路实施程序时,不能使用可变上限环。 上限必须固定在最大值。 电路不能处理动态逻辑。 为了便于读者理解,这里详细说明一下EVM电路的成本。 综上所述,电路是固定的、静态的。 因此,EVM电路必须包含所有可能的逻辑。 该电位器是只包含add的电路的10000倍。 也就是说,即使只想证明add,也必须承担该EVM电路中可能包含的所有逻辑的成本。 也就是说,成本扩大了10000倍。 要执行跟踪,需要证明一系列的操作码,每个操作码都要花很高的成本。 EVM本身与默克尔帕特丽夏(MPT )没有密切联系。 目前,MPT只用于保存以太坊的状态。 改变很容易。 (有人提议用Verkle树代替MPT。 这是一个高度简化的抽象概念。 从技术上说,“EVM状态”列表是程序计数器、gas剩余量、调用栈(上述所有加栈中每次调用的地址和静态)、日志和事务范围变量的集合)热存储可以单独部署用于不同调用环境的标识符,以直接支持可组合性。 因为存储量很大,所以使用累加器保存。 内存和堆栈可以使用可编辑的Plookup。 用这种方法可以有效地实现“RAM”。 向zkEVM电路添加完整的递归证明并不容易。 实现递归的最佳方法还是使用循环椭圆曲线,即Pasta曲线。 需要实施某种“包装”流程,以便可以在以太坊Layer 1中递归验证。 (完) )。

(文章中有很多超链接,请点击左下方的“阅读原文”“从EthFans网站获取”)

原文链接:

359海克MD.io/@ yezhang/S1 _ KMM BGT

作者: Ye Zhang@Scroll

标签: