1. 引言

前序博客有：

• SNARK Design
• Rollup项目的SNARK景观

SNARK方案由 Polynomial IOP ➕多项式承诺方案 组成。

当前的Polynomial IOP主要分为三大类：

• 1）基于interactive proofs（IPs）的Polynomial IOP：如Hyrax、vSQL、Libra、Virgo等。【$P$无需做FFT运算】
• 2）基于multi-prover interactive proofs（MIPs）的Polynomial IOP：如Spartan、Brakedown、Xiphos等。【$P$无需做FFT运算】
• 3）基于constant-round的Polynomial IOP：如Marlin、PlonK、StarkWare的SNARKs等。【$P$需要做FFT运算】

以上方案都是通过增加$P$开销，来减少proof长度以及降低$V$开销。
以上1）2）类，只要其结合的多项式承诺方案也不需要FFT，则$P$无需做FFT运算。

当前的多项式承诺方案主要分为四大类：

• 1）基于pairing的多项式承诺方案（既不transparent，也不post-quantum）
  • 如KZG10、PST13、ZGKPP18等。
  • 独特属性有：具有constant sized evaluation proofs。
• 2）基于discrete logarithm的多项式承诺方案（transparent，但不post-quantum）
  • 如BCCGP16、Bulletproofs、Hyrax、Dory等。【其中Dory即需要discret-log hardness，还需要pairing。】
• 3）基于IOPs+hashing（transparent 且 post-quantum）
  • 如Ligero、FRI、Brakedown等。
• 4）基于Groups of unknown order的多项式承诺方案（若使用class groups具有transparent属性，但不是post-quantum的）
  • 如DARK、Dew等。
  • 由于使用class groups，$P$非常慢。

本文将：

• 1）从“Multi-prover Interactive Proofs”（即基于MIP）的Polynomial IOP 分类中选择一个示例
• 2）从“IOPs+hashing”的多项式承诺方案 分类中选择一个示例
• 3）将以上1）2）2个示例组合，展示SNARK的工作原理
• 4）将以上1）2）2个示例组合，所构成的SNARK具有novel efficiency：
  • 4.1）从文献来看，具有最快的$P$（concretely and asymptotically）；
  • 4.2）可基于任意（足够大）的域（即具有field agnosticism（域不可知）属性）；
  • 4.3）首个实现见Brakedown [GLSTW21]：
    • 详细见 Alexander Golovnev、Jonathan Lee、Srinath Setty、Justin Thaler和Riad S. Wahby等人2021年论文 Brakedown: Linear-time and post-quantum SNARKs for R1CS）
    • 开源代码见：https://github.com/conroi/lcpc（Rust）
  • 4.4）缺点在于：proof相当大——近期已对其进行了改进，可参看Tiancheng Xie等人2022年论文Orion: Zero Knowledge Proof with Linear Prover Time。【Orion改进了proof size，但是牺牲了field agnosticism（域不可知）属性。】
    

2. Polynomial IOP示例

本文的Polynomial IOP示例运行在Arithmetic Circuit Satisfiability上下文中。
所谓Arithmetic Circuit Satisfiability，是指：

• 已知某 arithmetic circuit $C$ over $\mathbb{F}$ of size $S$且输出为$y$，判断是否存在某$w$，使得$C(w)=y$。

以w={a1,a2,a3,a4}，y=a12+a22+a32+a42w=\{a_1,a_2,a_3,a_4\}， y=a_1^2+a_2^2+a_3^2+a_4^2w={a1​,a2​,a3​,a4​}，y=a12​+a22​+a32​+a42​为例：

arithmetic circuit $C$ 的 transcript $T$ 是指：

• 对电路中每个gate的赋值

若电路中各个gate的赋值对应有效的witness $w$，则称$T$为correct transcript。

可将transcript看成是 domain为{0,1}log⁡S\{0,1\}^{\log S}{0,1}logS的function，为$C$中的每个gate赋予 a $(\log S)-$bit gate label，看将$T$看成是将gate labels映射为$F$的函数：【逐层赋值】

所谓Polynomial IOP是指：

• 1）$P$的第一个message为某具有$(\log S)$个变量的多项式$h$，$P$声称该多变量多项式$h$可extend a correct transcript $T$，即意味着：
  h(x)=T(x),∀x∈{0,1}log⁡Sh(x)=T(x),\forall x\in\{0,1\}^{\log S}h(x)=T(x),∀x∈{0,1}logS
  仍以上图为例，相应的多变量多项式$h$为：【可基于Boolean domain，借助multilinear Lagrange interpolation来获得多变量多项式】
  
  该多变量多项式$h$满足：$h(0,0,0,0)=3,h(0,0,0,1)=2,h(0,0,1,0)=0,h(0,0,1,1)=0$等等。
  注意，$h$不仅适于x∈{0,1}log⁡Sx\in\{0,1\}^{\log S}x∈{0,1}logS的情况，还适于所有$x\in {\mathbb{F}}^{\log S}$的情况：如，$h(2,2,2,2)=-19$。
  也就是说，transcript仅基于bit vectors域，而多变量多项式$h$的定义域更大。
• 2）$V$需要检查$P$声称的h(x)=T(x),∀x∈{0,1}log⁡Sh(x)=T(x),\forall x\in\{0,1\}^{\log S}h(x)=T(x),∀x∈{0,1}logS成立，但是，$V$仅能learn a few evaluations of $h$。
  为何$V$仅凭少量evaluations of $h$，就可信服$P$的声称呢？原因在于：
  • 2.1）将$h$看成是对transcript $T$的distance-amplified encoding。
  • 2.2）$T$的domain为{0,1}log⁡S\{0,1\}^{\log S}{0,1}logS，$h$的domain为${\mathbb{F}}^{\log S}$，要比$T$的大得多。可称$h$为$T$的extension polynomial。
    
  • 2.3）根据Schwartz-Zippel：若2个transcript $T和T^{\prime }$哪怕仅有一个gate value值不同，二者相应的extension polynomial $h和h^{\prime }$在${\mathbb{F}}^{\log S}$内几乎所有的evaluation值都不相同（准确来说，不相同的概率为$1-\log (S)/|\mathbb{F}|$）。
  • 2.4）这种encoding的distance-amplifying特性，使得，哪怕整个transcript中仅有一个“inconsistency”，$V$也可以发现。

Two-step plan of attack：

• 1）已知任意的$(\log S)$个变量的多项式$h$，找到相应的具有$(3\log S)$个变量的多项式$g_h$，使得：

  • $h$ extends a correct transcript $T$，当且仅当，对于任意的∀(a,b,c)∈{0,1}3log⁡S\forall(a,b,c)\in\{0,1\}^{3\log S}∀(a,b,c)∈{0,1}3logS，有$g_h(a,b,c)=0$。【即$g_h$ vanish over the Boolean hypercube，等价为，$P$的原始声称——即“ $h$ extends a correct transcript $T$”。】
  • 此外，为evaluate $g_h(r)$ at any input $r$，足以通过evaluate $h$ at only 3 inputs来实现。

  为简化描述，以仅有乘法门的电路为例，可仅关注下述等式右侧的第二项，其输入为3个gate labels $a,b,c$，其中$\widetilde{mult}(a,b,c)$表示的是gates之间的wiring关系，也称为wiring polynomial。
  

• 2）为检查 gh(a,b,c)=0,∀(a,b,c)∈{0,1}3log⁡Sg_h(a,b,c)=0,\forall(a,b,c)\in\{0,1\}^{3\log S}gh​(a,b,c)=0,∀(a,b,c)∈{0,1}3logS，设计了一个interactive proof：

  • 其中$V$仅需要evaluate $g_h(r)$ at one point $r$。