Recursive SNARKs总览

1. 引言

Recursive SNARKs又名Incrementally Verifiable Computation（IVC）、Proof Carrying Data（PCD）或 inductive SNARKs。 上图摘自 zkStudyClub: Halo Infinite with Ben Fisch (Stanford)。

下图摘自 微软团队2021年论文 《Nova: Recursive Zero-Knowledge Arguments from Folding Schemes》，其中：

• [BCTV14]：为Ben-Sasson等人2014年论文《Scalable zero knowledge via cycles of elliptic curves》
• [Gro16]：为Groth 2016年论文《On the size of pairing-based non-interactive arguments》。可参看博客：
  • Groth16 学习笔记
  • ZCash bellman版本 Groth16代码解析。
• [Set20]：为微软团队Setty 2019年论文《Spartan: Efficient and general-purpose zkSNARKs without trusted setup》。可参看博客：
  • Spartan: zkSNARKS without trusted setup学习笔记
  • Spartan: zkSNARKS without trusted setup 源代码解析
  • Spartan中 Vitalik R1CS例子 SNARK证明基本思路
• [COS20]：Chiesa等人2019年论文 《Fractal: Postquantum and transparent recursive proofs from holography》
• [BGH19]：Bowe等人2019年论文《Halo: Recursive proof composition without a trusted setup》。可参看博客：
  • Halo: Recursive Proof Composition without a Trusted Setup 学习笔记
  • Halo代码解析
• [BCL+20]：B¨unz等人2020年论文《Proof-carrying data without succinct arguments》。可参看博客：
  • proof-carrying data from accumulation schemes学习笔记

Mina团队在其 pickles库 中实现了inductive proof systems。

2. 何为Recursive SNARKs？ 2.1 何为SNARK？

2.2 何为SNARK of a SNARK proof？

2.3 何为SNARK of multiple SNARK proofs？

注意， C ′ C' C′仅依赖 V V V和 S V S_V SV​（而不是 C 1 , C 2 C_1,C_2 C1​,C2​）。 可将 V V V以circuit表示为：【 w ′ = π ′ w'=\pi' w′=π′，独立于 w 1 , w 2 w_1,w_2 w1​,w2​。且有 ∣ C ′ ∣ = 2 ∗ ∣ V ∣ < ∣ 2 ∗ C ∣ |C'|=2*|V|