ZKP proof聚合技术

ZKP proof聚合技术

引用

CSDN

1.

https://blog.csdn.net/mutourend/article/details/140190747

零知识证明（ZKP）中的SNARKs（简洁的非交互式知识论证）和STARKs（可扩展的透明知识论证）因其在去中心化私有计算和区块链扩容等领域的应用而备受关注。然而，证明大型程序或计算是非常昂贵的，因为运行其本身会引入开销。为了解决这个问题，可以将大型计算切分为多个更小的计算，但这样会导致proof size和verification time的线性增加。为了解决这个问题，可以使用proof聚合技术，将所有proof打包，然后仅做一次验证。本文将重点讨论几种可用的proof聚合技术，及其在prover time、verification time和proof size方面的权衡。

1. 引言

SNARKs (succinct, non-interactive arguments of knowledge) 和 STARKs (scalable, transparent arguments of knowledge)，因其在去中心化私有计算和区块链扩容等领域的应用，而备受关注。

• 支持一方（Prover），向另一方（Verifier），证明某计算的正确性
• Verifier验证proof，要比重新执行该计算，快得多。
• proof size，要比证明该计算所需的信息量，小得多。
  如：
• 可在不提供整个Sudoku游戏结果的情况下，证明知道该游戏的解。
• 为证明某虚拟机执行的正确性，Verifier无需知道该虚拟机在每个cycle的寄存器值，仅需query寄存器在某些时刻的值即可。

证明大型程序或计算是非常昂贵的，因为运行其本身会引入开销。在某些情况下，可将大型计算切分为多个更小的计算，如，”证明某区块内的交易，可转为，分别证明每笔交易“，但这样有2个缺陷：

• 1）proof size 会随切分的计算份数线性增加
• 2）verification time 会随切分的计算份数线性增加
  这2个缺陷会影响可扩展性，因需要更多的时间来验证整个计算，且会增加所需内存。
  可将所有proof打包，然后仅做一次验证。具体有多种可用技术：
• 最佳技术取决于所用的proof system类型，以及实际需求。
  本文重点讨论几种可用技术，及其在prover time、verification time和proof size方面的权衡。

2. proof聚合技术

proof聚合技术支持同时证明多个statements，降低，因引入多个statements check，所导致的proof size和verification time的扩大。

2.1 Proof recursion

SNARKs/STARKs支持以时间和内存高效的方式来检查任意NP statement的有效性。验证某statement所需的信息量，要远小于，检查该statement所需的witness size。如

• 在STARKs中，Verifier无需知道program的整个execution trace，仅需要做随机query。
• 在Plonk中，Verifier知道trace polynomials在随机点的evaluations，要远小于该trace内的3 n 3n3n个值。

递归的工作原理为：

• Prover，证明，其验证了，具有public inputu uu的某计算的proofπ \piπ。

其中：

• 1）Prover：根据public input、witness、待证明program，来生成proofπ \piπ，以证明该计算的有效性。
• 2）Prover：将proofπ \piπ和原始program电路作为witness，再根据public input、proofπ \piπ的验证电路（即Verifier检查该statement所需做的操作），来获得新的proofπ ′ \pi'π′——证明该Prover知道，该proofπ \piπ满足指定input下的验证电路。
• 3）Verifier：检查proofπ ′ \pi'π′，π ′ \pi'π′可展示：
• 3.1）Prover所做的验证是有效的，从而意味着第一次计算的正确性。

对于STARKs场景，若验证操作的trace，短于，原始program的trace，则proof size和verification time都会减少——因为二者都取决于trace lengthn nn。

实际也可以使用2种不同的Prover。如：

• 1）证明第一个program使用STARKs Prover，其证明速度快，但proof size大。
• 2）第二个使用Groth16/Plonk Prover，其具有更小的proof size。
• 因为第二种情况下，无需处理任意计算，因此可为针对STARK proof verification的优化电路。
• 最终，具有可快速验证的small proof。

也可使用相同的结构，并证明多个proof的验证：

但这样存在的问题在于：

• 尽管proof size会减小，但public input会线性增加。

可通过，将所有public input的hash/commitment作为witness的一部分，来解决该问题。在验证时：

• 需检查witness中public input的哈希值，对应于public input的hash/commitment。

借助proof recursion，可构建树结构，以增加并行度，来更高效的处理：

proof recursion已被用于多个项目中来降低proof size并让验证更便宜，如：

• Starknet：见StarkWare团队2022年8月11日博客Recursive STARKs: The very first recursive proofs of general computation, now live on Ethereum Mainnet
• Polygon zkEVM：见Polygon Labs团队2023年1月13日博客The Go Fast Machine: Adding Recursion to Polygon zkEVM
• zkSync：见Matter Labs团队2020年8月1日博客zkSync v1.1 “Reddit Edition”: Recursion (up to 3,000 TPS!), Subscriptions, and More

即便proof recursion有很多优势，但其给Prover增加了负担。
在类似STARKs的证明系统中，Prover需要计算大量非常昂贵的运算——哈希运算。幸好：

• 有algebraic哈希函数，其证明开销比Keccak等普通哈希函数要更低。
• 有STIR: Reed–Solomon Proximity Testing with Fewer Queries等协议，可降低生成proofs所需的哈希次数。

对于基于椭圆曲线的SNARKs中，其proof包含椭圆曲线内的元素——其坐标是基于域F p \mathbb{F}_pFp 的，scalar以F r \mathbb{F}_rFr 表示。SNARKs中做递归证明的问题在于：

• 为计算基于曲线的运算，不得不做基于F p \mathbb{F}_pFp 的运算。
• 电路中的scalars位于F r \mathbb{F}_rFr ，从而导致non-native域运算。如：
• https://github.com/yi-sun/circom-pairing/blob/master/circuits/bn254/groth16.circom中有验证Groth16 proofs的电路，需要的约束数约为2000万个。
• 下文会提到，采用cycles of curves，有助于避免non-native域运算导致的field emulation。

2.2 Cycles of curves

由上可知，椭圆曲线E EE的坐标位于F p \mathbb{F}_pFp 域，而scalar域为F r \mathbb{F}_rFr ，在做递归证明时，会存在non-native域运算问题。
若能找到基于F r \mathbb{F}_rFr 域的曲线E ′ E'E′，且其scalar域为F p \mathbb{F}_pFp ，则可使用E ′ E'E′来检查基于E EE的proofs。
具有这些特征的曲线对称为cycle of curves。
幸运的是，某些形如y 2 = x 3 + b y^2=x^3+by2=x3+b的曲线可满足该条件。

• Pallas和Vesta曲线（又名Pasta曲线对）构成了该cycle，已用于Mina的Pickles和Halo2中。

其中，在LambdaClass团队2024年2月5日博客Mina to Ethereum ZK bridge中，有详细介绍Mina的Pickles证明系统。
Pickles使用2个accumulators，每个曲线对应一个accumulator，并将某些检查推迟到下一个step。这样，可避免昂贵的雁阵个，并高效传递递归可验证计算。

2.3 Folding and accumulation schemes

full recursion的缺陷之一在于：

• 需证明整个验证，那非常昂贵。
  如在递归STARKs中，必须计算所有哈希并验证所有代数运算来获取新的proof。
  Folding schemes提供了一种完全验证的替代方案，其将多个实例结合并累加。
• Nova介绍了一种针对R1CS的folding scheme方案。其核心思想为，若有针对R1CS的2个解( u 1 , w 1 ) (u_1,w_1)(u1 ,w1 )和( u 2 , w 2 ) (u_2,w_2)(u2 ,w2 )，将二者结合为针对某committed relaxed-R1CS的单个claim( u , w ) (u,w)(u,w)。所谓relaxed-R1CS，是指更通用的R1CS。然后为该unified claim生成proof，相当于证明所有实例的有效性。

2.4 SNARKPack

某些证明系统的proofs可通过其它方式来聚合，如针对Groth16的SNARKPack。
Groth16 proof中包含3个元素：

• Π = ( π 1 , π 2 , π 3 ) \Pi=(\pi_1,\pi_2,\pi_3)Π=(π1 ,π2 ,π3 )，其中π 1 , π 3 \pi_1,\pi_3π1 ,π3 属于曲线的groupG 1 G_1G1 ，π 2 \pi_2π2 属于groupG 2 G_2G2 。
  Groth16 proof验证会检查如下pairing等式：
• e ( π 1 , π 2 ) = Y e ( π 3 , D ) e(\pi_1,\pi_2)=Y e(\pi_3,D)e(π1 ,π2 )=Ye(π3 ,D)
  其中：
• Y YY：取决于public input和Groth16 trusted setup中的参数。
• D DD：为Groth16 trusted setup中的部分参数。
  若有多个Groth16 proofsΠ k = ( π 1 k , π 2 k , π 3 k ) \Pi_k=(\pi_{1k},\pi_{2k},\pi_{3k})Πk =(π1k ,π2k ,π3k )，对于这些不同的checkse ( π 1 k , π 2 k ) = Y k e ( π 3 k , D ) e(\pi_{1k},\pi_{2k})=Y_k e(\pi_{3k},D)e(π1k ,π2k )=Yk e(π3k ,D)，可使用随机值r k r_krk 来组合为：
• ∏ e ( π 1 k , π 2 k ) r k = ∏ Y k r k e ( π 3 k , D ) r k \prod e(\pi_{1k},\pi_{2k})^{r_k}=\prod Y_k^{r_k} e(\pi_{3k},D)^{r_k}∏e(π1k ,π2k )rk =∏Ykrk e(π3k ,D)rk
  可将其重写为：
• Z A B = Y ′ e ( Z C , D ) Z_{AB}=Y'e(Z_C,D)ZAB =Y′e(ZC ,D)
  其中：
• Z A B = ∏ e ( π 1 k , π 2 k ) r k Z_{AB}=\prod e(\pi_{1k},\pi_{2k})^{r_k}ZAB =∏e(π1k ,π2k )rk
• Y ′ = ∏ Y k r k Y'=\prod Y_k^{r_k}Y′=∏Ykrk
• Z C = ∏ π 3 k r k Z_C=\prod \pi_{3k}^{r_k}ZC =∏π3krk
  Verifier需检查Z A B , Z C Z_{AB},Z_CZAB ,ZC 与所提供的proofsπ k \pi_kπk 一致。
• 可通过一次target inner pairing product，和，一次multiexponentiation inner product来实现。
• 其优势在于：所组合的proof size，与其实际所聚合的proof个数无关。

2.5 Continuations

Continuations为一种机制，来将复杂的计算，切分为更小的segments，这些segments可独立计算和证明。从而：

• 借助并行化，可有更快的证明速度
• 降低Prover的内存开销
• 缺点为：除非以rollup形式来实现，否则proof size会blowup。
• 但可借助独立proofs的优势，使用folding scheme来组合所有claims到同一验证电路，或使用递归证明。
• 可将所有segments包裹仅单个proof——即最终的proof可为具有constant proof size的SNARK。

3. 总结

过去10年来，看到了新证明系统和技术的发展，以内存和时间高效的方式来证明计算的有效性。
但需要将大型计算切分为独立的、更小的计算，如为证明某区块内交易，可分别证明每笔交易。其缺点在于proof size和verification time的blowup，从而会影响可扩展性，或，增加开销。
幸运的是，有多种技术来聚合证明，因此验证单个proof，即意味着验证了所有其它proofs的有效性。而递归证明可提供高效并行方式来聚合证明，其包含了昂贵的操作——如field emulation和哈希函数。
accumulation或folding schemes则提供了不同于完全验证的另一种方式，将某些checks推迟，直到验证的最后一步。

上图摘自：LambdaClass团队2024年5月3日博客Aligned Layer: First Aligned Testnet in EigenLayer。

参考资料

[1] LambdaClass团队2024年3月25日博客Proof aggregation techniques
[2] LambdaClass团队2024年5月3日博客Aligned Layer: First Aligned Testnet in EigenLayer