Layer2扩容关键技术：递归零知识证明剖析

作者： ZKSwap 小白

在 Layer2 扩容赛道上， ZkRollup 方案以完美的数据可用性以及与 Layer1 同等级的安全性，备受青睐；以单个 Block 为处理单元，用零知识证明算法来保证此区块引起的世界状态变化的有效性，大幅降低了每笔交易的上链成本，同时也增长了系统的吞吐效率。然而，在实际的落地过程中，研究者们发现，简单的 ZkRollup 方案带来的扩容效果，并不能满足真实的场景需求；这和很多因素有关，电路参数的限制，零知识证明算法的效率等等；研究者们做了很多努力，比如对零知识证明算法进行加速，配备超高配置机器，优化电路规模等，虽带来了一定的性能提升，但仍难以满足需求。

研究者们当然希望，链上一次处理的交易越多越好。朝着这个目标出发，研究者们首先发现了聚合证明（ Aggregation proof ）技术，该技术已经被 ZKSwap 推出的 ZKSpeed 扩容方案采用。在前面的文章中，已经解释了聚合证明（ Aggregation proof ）的原理和思想，简单来说就是把多个区块的证明聚合成一个证明，使得链上一次就可以完成多个区块的验证，大大的降低了交易的平均成本，其原理如下图所示：

该方案虽然有优势，可实现多个区块的证明的一次验证，但也有其一定的局限性：

1. 一次聚合的区块是有上限的，受限于电路参数的限制；

2. 聚合的区块越多，电路就越大，直到其规模的上限；这种电路生成的证明时间要更长，证明密钥和验证密钥也会占用更大的存储空间；

3. 目前可支持的最大聚合粒度是 20 个区块，也就是凑齐 20 个区块后，才会开始聚合处理。如果生成证明的效率比较低，这会导致这些区块被确认的时间拉长，尤其是最早生成的那些区块；

受限于证明计算（ Proof computation ）和 CRS 生成复杂度的限制，上述的零知识证明算法是不可扩展的。因此，研究者们也在努力寻找一个可扩展的零知识证明算法，即 Scalable zk-SNARKs 。

Scalable zk-SNARKs 可拓展的 zk-SNARKs

在论文《 Scalable Zero Knowledge via Cycles of Elliptic Curves 》中， Eli Ben-Sasson 等给出了 Scalable zk-SNARKs 的定义：

1. Key generation is cheap ：即， Key 生成的时间和计算复杂度没有关系（如果是 Scalable zk-S T ARKs ，可能不需要 ）；

2. Proof generation is carried out incrementally ：即，证明生成过程既包含了当前执行步骤的正确性又包含了在此之前所有计算的正确性，这种 zk-SNARKs 是 incrementally computable ；

为了方便大家理解，用一张图来表示上述思想：

上图表示意思是：证明着证明一个递归计算过程，即：初始状态为 S ₀ ，经过 t 次函数 F 迭代计算后的结果为 S _t （像极了区块链里区块更新的过程）。

第一个计算方式， Monolithic option ：证明方 P 把 t 次计算过程全部写成电路，然后一次性证明，正如我们前面所列举的一样，存在相同的局限性，很高的时间复杂度和空间复杂度；

第二个计算方式， Recursive option ：递归计算，其过程如下：

1. 首先对于初始状态 S0=>S1 ，证明方 P 对于 S ₁ = F(S ₀ ) 计算过程生成一个证明 π ₁ ；

2. 对于 S ₁ =>S ₂ 的转换，由图中可以得知，证明方 P 证明了两部分： {S ₂ = F(S ₁ ), V(S ₁ , π ₁ ) = 1} ，前半部分保证了当前计算的有效性，后半部分保证了上一步计算过程的有效性；由于在 zk-SNARKs 里，证明生成的时间比原始计算要快一些，因此，对于验证过程进行证明是合理的；

由此可以看出， Recursive option 满足 Scalable zk-SNARKs 了基本要求：

1. Key 的生成和循环次数没有关系，取决于单次 F 的复杂度，如果是 general zk-SNARKs ，只取决于安全参数；

2. 证明满足 incrementally computable ，每个证明都包含了在此之前所有计算的有效性；

3. 证明的大小固定，和迭递归次数 t 没有关系；

由上可知， Scalable zk-SNARKs 采用了 Recursive 思想，即当前的 Prove 过程包含上一步的验证过程电路，具体如下图所示：

可以看到， P ₂ 证明电路里，包含了上一步 P ₁ 的验证过程电路。需要注意的是， P ₁ 对应的 V 在域 F _q 上， P ₂ 的证明过程在 F _r 上，如何在 F _r 上表示 V 的算术电路，是一个值得探讨的过程；由于 C _v 可以看作是 P 的一个子电路，因此， q 需要满足 q = #E(F _r ) 或者 q 整除 #E(F _r ) ，即 q 整除 r ^k - 1 ，因此：

尝试 1. 理想的情况下，如果 r = q ，那么在 F _r 上，能完美表示 F _q 上的 V 的算术电路，但是根据上述原理， r != q 恒成立；

尝试 2. 对于 q != r ，因为需要在 F _r 上去模拟 F _q 上的计算，会导致计算复杂度的提高 log(r) 倍；

尝试 3. 采用 椭圆曲线循环（ cycle of elliptic curves ） ，可以完美实现 Recursive 过程；

具体的，选取两个大素数， r 和 q 。满足 r = #E(F _q ) 和 q = #E(F _r ) ，即，当前群的域等于另外一个群的阶，反之亦然。因此，域 F _q 上的证明方 P 可以完美的在 F _q 上实现 F _r 上的验证电路，域 F _r 上的证明方 P 也可以在 F _r 上实现 F _q 上的验证电路；因此不会出现尝试 2 里面的缺陷。

下面表格列举常用的 cycle of elliptic curves （ https://eprint.iacr.org/2014/595.pdf ）

写在最后

通过采用 递归证明组合密码技术 (R ecursive Proof Composition) ， zk-SNARKS 变成了 Scalable zk-SNARKs ，实现了更高效、简洁的零知识证明算法，并能真实的落地应用。即将发布主网的 Mina 就采用了这种技术实现了简洁的区块链，即固定大小的链，保持在 22KB 左右；同时，其他的技术团队包括 Matter Labs 、 starkWare 等也在计划采用 Scalable zk-SNARKs 技术来实现 Layer2 更高的扩容。 ZKSwap 团队在 Layer2 赛道上持续发力，在 Scalable zk-SNARKs 上亦有所突破，相信不久就会应用于新的版本上。