干货 | zkEVM:设计挑战与解决思路
感谢 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 中构建通用 dApp
-
一种是为不同 dApp 构建专用电路(“ASIC”)。 -
另一种是构建通用 “EVM” 电路用于执行智能合约。
“电路(circuit)” 指的是零知识证明中使用的程序表示。例如,如果你想要证明 hash(x) = y,你需要使用电路形式重新编写哈希函数。电路形式只支持非常有限的表示(即,R1CS 只支持加法和乘法)。因此,使用 circuit 语言编写程序难度很高 —— 你只能使用加法和乘法来构建所有程序逻辑(包括 if else、循环等等)。
add
的结果是正确的,你依然需要负担整个 EVM 电路的成本。如果你的执行追踪中有上千个操作,证明者就要负担 1000 倍的 EVM 电路成本3。
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 在当下有可能实现
-
多项式承诺(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 是如何运作和构建的?
开发者和用户的工作流程
zkEVM 的工作流程
-
Layer 1 靠的是重新执行智能合约。 -
Layer 2 靠的是 zkEVM 电路的有效性证明
add
操作码需要从堆栈中读取两个元素,将它们相加并将结果写入堆栈。
-
字节码从永久存储项中正确加载(你正在运行从某个地址加载的正确操作码) -
字节码中的操作码始终逐一执行(字节码按顺序执行,不会遗漏或跳过任何操作码) -
每个操作码均正确执行(每个操作码中的三个子操作都正确执行,R/W + 计算)
zkEVM 设计亮点
jump
这样的条件式操作码(与智能合约中的 loop、if else 语句相对应)可能会跳转到任何地方。在某个人使用特定输入运行该字节码之前,跳转目的地都是不确定的。这就是为什么我们需要验证实际的执行踪迹。执行踪迹可以被认为是 “展开的字节码”,包含按实际执行顺序排列的操作码(即,如果你跳转到另一个位置,踪迹中将包含该目标操作码和位置)。
-
我们可以将 R/W 和计算分成两个证明。一个证明会将所有操作码用到的元素都放到 “总线” 中。另一个证明会证明对 “总线” 上元素的计算是正确执行的。这会大幅降低每个部分的成本(即,你在生成计算证明时无需考虑整个 EVM 存储)。在更详细的规范中,前者被称为 “状态证明”,后者被称为 “EVM 证明”。另一个发现是,查找声明可以有效处理 “总线映射” 。 -
我们可以为每个操作码设计度数更高的定制化约束(即,我们可以将一个 EVM word 切分成多个数据块,以便更高效地处理)。我们可以选择是否根据需求通过一个选择符多项式来 “打开” 一个约束。这样可以避免每个操作都要消耗整个 EVM 电路的成本。
zkEVM 还能给我们带来什么?
结论
关于我们
注:
-
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 上可验证。
比推快讯
更多 >>- Coinbase 聘请前洛杉矶市长 Antonio Villaraigosa 担任政策顾问
- Coinbase因涉嫌欺骗投资者而面临新的集体诉讼
- 三家香港现货虚拟资产ETF上市首周资管规模已超20亿港元,是期货ETF的近两倍
- 某地址累计卖出677197枚FRIEND空投,获利约115万美元
- 某巨鲸从Compound累计借出1700万枚USDT
- Sui官方:Mysten Labs创始人不控制任何代币
- 巴菲特:现在没有足够有吸引力的投资标的,伯克希尔本季度末持有的现金或增至 2000 亿美元
- 巴菲特:伯克希尔的主要投资将永远在美国
- 巴菲特:美债或美元没有真正的替代品
- 动态模块化服务平台Crestal完成200万美元Pre-Seed融资,MH Ventures等参投
- Bitfinex 首席技术官否认勒索软件组织数据泄露的谣言
- Jack Dorsey向非营利组织OpenSats捐赠2100万美元
- 特斯拉网站新增狗狗币作为支付方式
- 孙宇晨地址向 Swell Network 存入 12 万枚 eETH,价值 3.76 亿美元
- BTC-e运营商Alexander Vinnik承认共谋洗钱罪
- 美财长耶伦:基本面仍然指向通胀放缓
- Q1 Coinbase 国际交易所永续期货名义合约交易量超 760 亿美元
- 风投Q1向加密和区块链公司投资 24.9 亿美元,环比增长 29%
- 马斯克:需要对我们的国家债务采取行动,否则美元将一文不值
- MakerDAO计划引入两种新代币NewStable和NewGovToken
- 盗走1,155枚WBTC的团伙已将代币全部售出,换成 22,960 ETH
- LayerZero建议女巫地址主动报告,截止日期是 5 月 17 日
- 链上数据API开发商Airstack完成400万美元种子轮融资,Red Beard Ventures领投
- 一巨鲸过去两天逢低买入1500枚BTC,价值约8825万美元
- SEC推迟对7RCC现货比特币和碳信用期货ETF做出决议
- 今日美国9只现货比特币ETF总计减持2350枚BTC,价值约 1.4亿美元
- LayerZero:将在两小时内将发布一项公告
- 盗走1155枚WBTC的地址正在将代币兑换成ETH
- 数据:约74%的BTC在过去6个月未发生移动