本文由Kurt Pan听译

Part1简介

两个零知识库Plonky2和Starky，代表了构建更高性能SNARKs/STARKs的新方法。Plonky2 是一个结合了Plonk和FRI的库，Starky 专注于运行基于AIR的STARKs，且支持对其的递归验证。该方法可以总结为，使用小域，然后使用递归FRI。

相比于基于椭圆曲线的证明系统，FRI允许使用更小的域，可以使用这个非常有趣的素数阶 Goldilocks域。这可以让我们利用结构和CPU的工作方式来加速域算术。

通过调整blow up因子，FRI能提供如下权衡：一个极端可以有快速的证明者但是证明非常大，另一个极端可以有更小的证明但是证明者很慢。迄今为止使用FRI的协议都选择了某个中间的折中点，例如如果你想在以太坊上验证一些东西，那么blow up因子要足够大，使得证明大小小到可以在以太坊上验证；但也不能太大，不然证明时间会太长。

通过Plonky2，使用递归，我们可以避开上述权衡。我们有一个要证明的复杂的论断，可以选择一个非常低的blow up因子，所以证明时间会非常快，但证明大小太大。我们可以将其封装进一个更小的递归证明中，于是就同时可以拥有快速的证明和依然很小的证明。根据不同应用，可以在使用Plonk和AIR算术化之间来回选择。

例如，编译Solidity或Yul来验证以太坊交易的虚拟机System Zero可以使用AIR，因为虚拟机的路由模型决定了每一步只需要访问上一步和下一步，就可以没有Plonk中的可以路由很多门到任意门的代价。Plonky2展示了这种非常有用的灵活性。

结果就是我们可以拥有非常快的，类似于STARK一样的无可信设置的完全透明的零知识证明系统。

Plonky2 拥有最好的递归性能。在Macbook Pro上生成递归证明需要170ms,且在未来几个月有希望再降低。比BN-254/Plonk+KZG快100倍。

在做Polygon Zero项目之前我们在做Mir协议，使用ZEXE风格的一级递归以及递归聚合。其中非常恼人的一点是，当你对基于椭圆曲线的方案使用递归时，通常来说要么要承受使用单个曲线，拥有电路中昂贵的非原生乘法的代价；要么就要使用曲线cycle, 时时要记录你在哪条曲线上。这很恼人，因为我们想在内部证明中进行某些计算，然后在使用同样的Merkle树和状态和accumulator时嵌入某些计算到外部证明中,但是它们的标量域都是不同的，所以我们做不到这点。而在Plonky2中，对于所以东西都是使用一个域。和Halo不同，我们是完全验证每个证明， 每个递归步骤都代表对正在验证的任何证明的完整验证。所以无需担心拥有accumulators或延迟计算或者对accumulators的组合。

Plonky2原生以太坊兼容。EVM验证者虽然还没完成，但迁移过来验证一些Keccak哈希还是比较容易的，估计出验证需要消耗1百万gas。我们现在也和Hermez合作一个项目来使用Goldilocks域来极大的降低验证gas。

当你使用FRI时一个明显的权衡在于证明大小比基于椭圆曲线的方案要大非常多。很多人非常关注证明大小，比如一个区块中可以放多少个证明这些问题，但其实在超过某个点比如100tps之后，性能瓶颈还是受限于验证时间。使用递归，可以把协议架构使得不会受限于证明大小，于是可以把证明路由到某个特定的可以聚合的节点。当前优化模式下证明大小为45kb，我们在进行进一步的证明压缩工作。

另一个缺点是小域方面的。对于更大的域，可以直接在证明系统中使用的标量域上定义椭圆曲线，但Goldilocks域太小了，以至于不能直接定义椭圆曲线。这是很不好的，因为要支持对于椭圆曲线签名和Pedersen哈希的验证。但我们最近在ePrint上提交了两篇论文，论证了我们可以在Goldilocks域的扩域上安全地定义曲线。于是就依然可以在Plonky2和Starky中高效的验证椭圆曲线算术。

我们对于Plonky2和这条技术路线很激动，因为我们将零知识证明视为一种计算平台，而在技术史上，不管是PC,手机还是游戏机，一种计算平台的计算性能一旦提升10倍，全新应用的设计空间将会获得爆炸式增长。而Plonky2代表了以太坊上递归性能对于通用论断相对其他证明系统的100倍提升。我们对于如此巨大的速度提升非常激动，这并非由于硬件加速，是软件的，关于CPU的，是一种对用零知识证明或密码学来构造东西的人来说非常有前景的技术路径。

Part2技术细节

快速回顾一下证明递归。一个证明系统包括，证明者生成证明，验证者 验证它。证明递归的想法是把这个验证算法也写到电路里面。于是就可以得到一个证明是正确的的证明。这可以应用到超过一个证明上，得到一个证明很多小证明都是正确的证明。在汇总场景中，当你有很多交易证明时，你可以使用递归证明来压缩它们，递归证明证明了所有的这些交易都是正确的，可以压缩为一个证明，可以发布到L1上。

虽然听起来简单，但是实践中的递归证明非常难。通常原因是大多数SNARKs证明系统都基于椭圆曲线。一个椭圆曲线包括两个域，标量域和基域。椭圆曲线上的证明系统中实际的证明是在标量域上的，但是证明是包含和元素的混合。如果你想在你的证明系统中验证这个证明，那么你要在中进行算术运算，但是证明系统是在上工作的，所以不得不进行非原生算术运算以在中模拟，虽然通常非常昂贵，但这是达到递归的第一种路径。

为了更高效，人们提出使用椭圆曲线的cycles, 一对椭圆曲线和，其标量域和基域互为对方的基域与标量域。思想是如果有一个上的证明，在上进行验证。因为的标量域是，可以对证明的元素进行原生算术来验证。反之如果有上的证明就在上验证，这就是为什么称为cycle。这是一个很好的解决方案，但是依然有一些问题。第一个问题是依然需要进行一些非原生算术，如上所述证明包含和中元素的混合，到中我们关心中的元素，但是在大多数证明系统中元素仍然会在中进行约束检查，在上会非常昂贵。要么在上进行昂贵的非原生的模拟，要么使用一些技巧，即将这种非原生计算延迟到回到曲线的时候再进行计算，但是这意味着你需要在每个时间点对不同的计算保持记录。Cycle的另外一个问题是对于配对友好曲线并没有合理的cycle，所以例如Groth16或原始Plonk证明系统是基于配对的，如果你想对这些方案使用cycle这种方法，你就不得不对配对友好曲线进行非常大的cycles,这些曲线会有非常大的域，使用起来非常的低效。有理论结果表明对于合理且高效的配对友好曲线不存在任何的cycle。所以因为你不能使用配对友好曲线，你就得使用基于IPA（内积证明）的系统，这是从bulletproofs开始的系列工作，一种做无可信设置的多项式承诺的方法，依然是在椭圆曲线上且使用离散对数，这是可行的，但依旧有些问题，因为bulletproofs的验证其实是非常难且非常昂贵的。所以如果你想递归地进行完全的验证，电路会变得太大。Halo是第一个想到使用accumulation方案的，并非在电路中真正实现完整的验证者，而是只实现一个accumulation检验，接着追踪记录这个accumulator。如果想要完成递归，依然需要检验这些accumulator。所以在任意时间点，并非真正的在计算递归证明，而是对于检验的证明，但是依然需要证明accumulator. 这是可行的，也是在Plonky 1中的做法，一个Plonk带上一个基于Halo的IPA多项式承诺。所有这些椭圆曲线方案的另一个问题是通常来说它们都很慢，因为它们都运行在大域上。Plonky 1的证明时间还行，但在某个时间我们发现可以做到更好，这就是为什么我们引入了Plonky 2。

Plonky2非常类似，但不是使用椭圆曲线或bulletproof，而是使用基于FRI的多项式承诺，依然使用Plonk算术化。

Plonky2 = PLONK + 基于FRI的多项式承诺

FRI是大多数STARKs的底层协议，是一个基于哈希的协议，不涉及任何椭圆曲线，FRI中的唯一密码学组分就是哈希。哈希由于以下原因很方便，第一因为通常来说哈希计算很快，第二因为它们只在一个域上定义，所以一个哈希的输入是一系列域元素而输出是同一个域上的一系列域元素。在椭圆曲线中我们必须去处理两个域，但是FRI只有一个域，这简化了很多事情。

FRI的另一个好处是我们可以使用小域，可以利用CPU很善于处理64比特数的事实，所以我们定义了被称为Goldilocks域的64比特域（也用在Miden和其他项目里），非常高效的运作，使得证明非常快。

另一个特性是完全递归，和accumulation方案不同，在任意时间点都有完全的对之前的链或树的递归证明，所以不需要检验任何 accumulator，任何延迟计算。工程上很简单，就是将完整的验证者在电路中实现。

使用Custom门，这被称为Turbo-PLONK算术化，即带Custom门的PLONK。这非常有用，因为在我们写递归电路时，有一些非常昂贵的操作，我们可以通过写Custom门把这些计算抽象掉，这是我们证明高效的原因之一。

另一个原因是我们在PLONK trace中使用了大量的列数。在原始PLONK论文中只用了3个列，大多数项目使用大约10列，我们使用140列。这允许我们只用trace的一行来进行哈希运算。由于哈希是我们在FRI中主要进行的操作，确保哈希尽可能高效是很重要的。

此外还有很多使得递归更高效的技巧。其中包括我们截断了所有的Merkle树，所以当验证Merkle路径时，不是直到根，而是会截断路径并在根下面停止，这使得证明更小，验证更高效。

所有的这些工程优化让我们可以达到如下结果，在个门中进行递归，时间170ms（Mackbook Pro上）。据我们所了解是迄今为止最高效的递归证明系统。

Part3Plonky 2 代码库

github.com/mir-protocol/plonky2

Plonky2代码库可以在Github上找到，完全由Rust编写。我们试图不使用依赖，所以Plonky2本身包含所有的密码学部分，包括所有域操作，Fiat-Shamir,IOP等等。当前包括7个sub-crates。

• plonky2: 主crate，证明系统逻辑，Plonk，Fiat-Shamir
• field: 域操作，Goldilocks域，和域操作相关的所有优化
• starky：给出可以被Plonky2验证的STARKs的定义
• system-zero：starky的一个系统实现，Polygon Zero的基于STARK的VM。可以模拟EVM以进行汇总。
• 其他包括Gadgets的crates，置换gadget，插入gadget 等

本文首发于：https://mp.weixin.qq.com/s/qSWFLQPQJvWHclAvlEXEaQ