精读Groth16算法

Abstract

本文中要解决的问题是，基于配对的SNARG可以有多高效

本文的第一个贡献是基于配对（预处理）的算术电路可满足性SNARK，本文使用非对称配对来提高效率，证明仅包含3个群元素，验证包括3次配对运算和一次配对乘积方程

本文的方案是零知识，并且没有透露任何关于证明人用来证明的证人的信息

本文的第二个贡献是回答了Bitansky、Chiesa、Ishai、Ostrovsky和Paneth在TCC2013上提出的一个开放性问题，证明了2步线性交互证明不能有线性决策过程，因此Prover和Verifier使用通用非对称双线性群操作的SNARG不能由单个群元素组成，这给出了基于配对的SNARG的第一个下限

不过这个下界是否可达仍然是个问题，若不可达，则本文的方案为目前最优的

1 Introduction

本文构造了一个关于算术电路可满足性的NIZK论证，其中证明仅由3个群的元素组成，证明长度不仅很短，验证也很高效，只需要三次配对即可

本文的构造可以用任何类型的配对进行实例化，包括最有效的III型配对

论证具有完美完备性和完美零知识性，为了确保合理性，本文依赖于通用双线性群模型$[Sho97,Nec94]$中的安全性证明

采用非对称的配对可以获得最佳的效率，不过采用对称的配对可以提供额外的安全性：若密码分析可以在源群之间构造一个可有效计算的同构，也不一定会导致本文方案的失效

综上，本文可以使用任何类型的配对进行实例化，可以在效率和通用性之间进行权衡

表1给出了布尔电路的性能比较，表2给出了本文方案与算术电路的性能比较

size matter

以往的研究中，所有基于配对的SNARK都遵循这样一个范式：Prover使用一般的群运算计算群元素，Verifier利用配对乘积方程验证，Bitansky等人$[BCI+13]$通过定义线性交互证明（LIPs）将该范式形式化，一旦有了一个合适的两步LIP，就可以通过使用基于配对的密码学来在指数上验证方程，从而将LIP编译为SNARK

基于这个范式，本文有两种方式来提高效率，第一种方式是为算术电路设计了一个LIP，Prover只需要发送三个元素即可完成证明，第二种方式是对LIP更积极地编译，本文将LIP编译为了单个群元素来提高效率

此外，由于本文采用非对称的配对，效率比对称的更高

lower bounds

本文证明了基于配对的SNARG至少需要包含两个群元素，第一和第二源群各一个，仅包含一个群元素的SNARG不存在（无论其是否满足ZK）

本文给出的理论下界是两个群元素，理论上可以从两个源群$\mathbb G_1,\mathbb G_2$各取一个元素构造SNARG，但是这样的方案否存在仍然不知道

‍

2 Perliminaries

• $f(\lambda)\approx g(\lambda)$：对于给定的两个函数$f,g:N\rightarrow [0,1]$，$f\approx g$表示$|f(\lambda)-g(\lambda)|=\lambda^{-\omega(1) }$
• $y\larr A(x)$：表示算法$A$输入$x$，输出$y$（省略了随机性）
• $y\larr S$：从集合$S$中随机选择一个元素
• $(y;z)\leftarrow (A||\chi_A)$：表示$A$和$\chi_A$都以x和随机性作为输入，$A$输出为$y$，$\chi_A$输出为$z$
• $(p,G_1,G_2,G_T,e,g,h)$：本文采用的双线性配对，$g,h$分别为$G_1,G_2$中的生成元
• $[a]_1$：表示$g^a$，$h$同理

2.1 Non-interactive zero-knowledge argument of knowledge

记$\mathcal R$为一关系生成器，以安全参数$\lambda$作为输入，输出一个多项式时间可判定的二元关系$R$，对于陈述$\phi$和证据$w$，有二元组$(\phi,w)\in R$，记$\mathcal R_\lambda$为以安全参数$\lambda$为输入，所有可能的关系$R$的集合

此外，关系生成器还可能会有一些侧信息$z$，这些侧信息会作为敌手的输入

一个关于关系生成器$\mathcal R$的高效公开可验证的非交互的论证是一个四元组，包含四个概率多项式时间的算法

• $(\sigma,\tau)\leftarrow Setup(R)$：初始设置算法，算法产生一个关于关系$R$的CRS$\sigma$，以及一个模拟陷门$\tau$
• $\pi \leftarrow Prove(R,\sigma,\phi,w)$：证明算法，以CRS串$\sigma$和$(\phi,w)\in R$作为输入，输出一个论证串$\pi$
• $0/1\leftarrow Vfy(R,\sigma,\phi,\pi)$：验证算法，以CRS串$\sigma$，陈述$\phi$和论证串$\pi$作为输入，输出0表示拒绝，1表示接受
• $\pi\leftarrow Sim(R,\tau,\phi)$：模拟器以陷门$\tau$和陈述$\phi$作为输入，输出论证串$\pi$

2.2 Quadratic Arithmetic Programs

本节介绍本文的QAP

考虑一个由有限域$\mathbb F$上的加法和乘法门组成的算术电路，可以将一些输入/输出线指定为指定statement，其余导线定义witness

算术电路中主要关注一组由变量描述的多项式之间的关系，其中一些变量对应于statement，剩余的对应于witness

该关系由满足所有等式的statement和witness组成，其中$a_0=1,a_1,...,a_m\in \mathbb F$，形式如下

$$ \sum a_iu_{i,q}\cdot \sum a_iv_{i,q}=\sum a_iw_{i,q} $$

其中$u_{i,q},v_{i,q},w_{i,q}\in \mathbb F$用于指定第$q$个方程

上述方程中包含加法门和乘法门组成，可以将此类方程构造的算数约束系统推广到了算术电路，比如乘法门可以描述为$a_i\cdot a_j =a_k(u_i,=1v_j=1,w_k=1)$，并令其余常数设置为零

这里需要注意：方程的和中不处理加法门，比如说$a_i+a_j=a_k$，且$a_k$需要与$a_l$相乘，则直接记为$(a_j+a_j)\cdot a_l$，跳过对$a_k$的计算

根据$[GGPR13]$的方法，可以在假设$\mathbb F$足够大的情况下，将算术约束集重新表示为二次算术程序，也即对于给定$n$个方程，我们选择任意不同的$r_1,...,r_n\in \mathbb F$，定义$t(x)$如下

$$ t(x)=\prod_{q=1}^n(x-r_q) $$

此外定义三个阶为$n-1$的多项式，如下

$$ u_i(r_q)=u_{i,q},v_i(r_q)=v_{i,q},w_i(r_q)=w_{i,q} \ \forall i=0,...,m,q=1,...,n $$

此时当且仅当对于所有的点$r_1,...,r_n\in \mathbb F$，均有下列等式成立时

$$ \sum_{i=0}^ma_iu_i(r_q)\cdot \sum_{i=0}^ma_iv_i(r_q) =\sum_{i=0}^ma_iw_i(r_q) $$

称$a_0=1,a_1,...,a_m\in \mathbb F$满足这$n$个等式

因为$t(X)$是对于所有的点$\{r_1,...,r_n\}$，均满足$t(r_q)=0$，因此可以将上述等式变形如下

$$ \sum_{i=0}^ma_iu_i(X)\cdot \sum_{i=0}^ma_iv_i(X) \equiv \sum_{i=0}^ma_iw_i(X) \ mod \ t(X) $$

总的来说，定义$QAP$的关系$R$如下

$$ R=(\mathbb F,aux,\mathcal l,{u_i(X),v_i(X),w_i(X)}_{i=0}^m,t(X)) $$

其中

• $\mathbb F$：有限域
• $aux$：额外信息
• $u_i(X),v_i(X),w_i(X),t(X)\in \mathbb F[X]$，且这四个多项式的阶严格小于$n$

把这个$R$的定义展开，具体如下（其中$a_0=1$）

$$ R=\left\{(\phi,w) \bigg|\begin{aligned} &\phi=(a_1,...,a_l)\in \mathbb F^l \\ &w=(a_{l+1},...,a_m)\in F^{m-l}\\ &\sum_{i=0}^ma_iu_i(X)\cdot \sum_{i=0}^ma_iv_i(X) \equiv \sum_{i=0}^ma_iw_i(X) \ mod \ t(X) \end{aligned}\right\} $$

2.3 Linear non-interactive proofs

$[BCI+13]$提出了一个称为两步代数输入不经意线性交互时证明（2-Move Algebraic InputOblivious Linear Interactive Proofs），本文将这一概念与非交互式论证相结合，并重新命名为非交互式线性证明（Non-Interactive Linear Proofs，NILP）

这里注意一点：这个重新命名的意思是将$[BCI+13]$中的那个两步什么玩意改了个名字，本质上还是同一个东西，原文用了两种不同的叫法只是为了便于区分

还有一点需要注意，NILP有两个含义：一个是可以通过基于配对来将其转化为一个公开可验证的非交互式论证，也是本文的重点之一，另一个是$[BCI+13]$原文中提到的方案，可以利用一个Paillier算法的变体，将其转化为一个指定验证者的非交互式论证

NILP的定义与关系生成器$\mathcal R$有关，假定关系指定了有限域$\mathbb F$，算法如下

• $(\boldsymbol\sigma,\boldsymbol\tau)\leftarrow Setup(R)$：初始设置是一个概率多项式时间算法，返回两个向量$\boldsymbol\sigma \in \mathbb F^m,\boldsymbol\tau\in \mathbb F^n$，假设$\boldsymbol\sigma$的第一个符号总是1，因此$\boldsymbol\sigma$的仿射函数和线性函数没区别

• $\boldsymbol\pi\leftarrow Prov(R,\boldsymbol\sigma,\phi,w)$：Prover的操作分为两个阶段

  1. 运行算法$\Pi\leftarrow ProofMatrix(R,\phi,w)$，其中$ProofMatrix$为一个概率多项式时间的算法，生成一个矩阵$\Pi\in\mathbb F^{k\times m}$
  2. 计算证明串$\boldsymbol\pi=\Pi\boldsymbol\sigma$

• $0/1\leftarrow Vfy(R,\boldsymbol\sigma,\phi,\boldsymbol\pi)$：Verifier的操作也分为两个阶段

  1. 运行确定性多项式时间算法$\boldsymbol t\leftarrow Test(R,\phi$)，获得算术电路$\boldsymbol t:\mathbb F^{k+m}\rightarrow\mathbb F^\eta$，该电路对应于总阶数为$d$的多元多项式向量的求值
  2. Verifier当且仅当$\boldsymbol t(\boldsymbol\sigma,\boldsymbol\pi)=0$

上述算法过程中提到的所有的阶$d$和维度$\mu,m,n,k,\eta$均为常数或关于安全参数$\lambda$的多项式

2.4 Non-interactive arguments from linear non-interactive proofs

NILP很有用，因为它可以使用配对编译成可公开验证的非交互式论证，也可以使用配对加密的变体$[BCI+13]$编译成指定的Verifier的非交互式论证

如果需要在基于配对中构造方案，直观的方法是Verifier的阶数$d=2$的NILP可以“在离散对数中”执行，CRS中包含对域元素的编码，Prover此时需要将证明计算为CRS中群元素的线性组合，Verifier通过验证多个配对方程来检查论证，这么做相当于检查一个基于域元素编码的二次方程，具体来看一下怎么做

当采用III型配对时，在DLOG中执行NILP需要为每个元素指定应该在哪个群中进行操作，因此定义一个拆分的NILP，其中CRS可以拆分为两个部分$\boldsymbol\sigma=(\boldsymbol\sigma_1,\boldsymbol\sigma_2)$，Prover的证明串也可拆分为两个部分$\boldsymbol\pi=(\boldsymbol\pi_1,\boldsymbol\pi_2)$，证明的每个部分都是从CRS的对应部分计算得到的，最后验证时，我们希望Verifier验证的是一个二次方程，其中每个变量的阶数均为1

个人理解：大致意思就是可以将CRS拆分为两个部分，其中一部分是Prover Key，另一部分是Verifier Key

3 Constructions of non-interactive arguments

根据前面说的，将QAP构造成一个基于配对的非交互式零知识论证，证明过程仅由三个群元素构成

构造方法分为两步，首先是为QAP构造一个NILP，不难发现其也是一个可分割的NILP，采用前面提到的编译技术可以转换为基于配对的NIZK论证

3.1 Non-interactive linear proofs for quadratic arithmetic programs

还是之前的关系

$$ R=(\mathbb F,aux,\mathcal l,\{u_i(X),v_i(X),w_i(X)\}_{i=0}^m,t(X)) $$

该关系定义了一种语言的陈述$(a_1,...,a_l)\in \mathbb F^l$及其证据$(a_{l+1},...,a_m)\in F^{m-l}$，且对于$a_0=1$，有下式成立

$$ \sum_{i=0}^ma_iu_i(X)\cdot \sum_{i=0}^ma_iv_i(X) = \sum_{i=0}^ma_iw_i(X) +h(X)t(X) $$

其中$h(X)$的阶为$n-2$，$t(X)$的阶为$n$，具体的算法如下

• $(\boldsymbol\sigma,\boldsymbol\tau)\leftarrow Setup(R)$：初始设置算法，选择$\alpha,\beta,\gamma,\delta,x\leftarrow \mathbb F^*$，令$\boldsymbol\tau=(\alpha,\beta,\gamma,\delta,x)$，$\boldsymbol\sigma$如下

$$ \boldsymbol\sigma=(\alpha,\beta,\gamma,\delta,\{x^i\}_{i=0}^{n-1},\{\frac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\delta}\}_{i=0}^{l},\{\frac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\gamma}\}_{i=l+1}^{m},\{\frac{x^it(x)}{\delta}\}_{i=0}^{n-2}) $$

• $\boldsymbol\pi\leftarrow Prove(R,\boldsymbol\sigma,a_1,...,a_m)$：证明串生成算法，选择$r,s\leftarrow \mathbb F$，然后计算一个$3\times(m+2n+4)$的矩阵Pi，满足$\boldsymbol\pi=\Pi\boldsymbol\sigma=(A,B,C)$，其中

$$ \begin{aligned} &A=\alpha+\sum_{i=0}^ma_iu_i(x)+r\delta\\ &B=\beta+\sum_{i=0}^ma_iv_i(x)+s\delta\\ &C=\frac{1}{\delta}\sum_{i=l+1}^ma_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+h(x)t(x)+As+Br-rs\delta \end {aligned} $$

• $0/1\leftarrow Vft(R,\boldsymbol\sigma,a_1,...,a_l)$：验证算法，计算一个二次多元多项式$\boldsymbol t(\boldsymbol\sigma,\boldsymbol\pi)=0$，也即验证下列等式成立

$$ A\cdot B=\alpha\beta+\gamma \cdot \frac{1}{\gamma}\sum_{i=0}^la_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+C \delta $$

• $\boldsymbol\pi\leftarrow Sim(R,\boldsymbol\tau,a_1,...,a_l)$：模拟器算法，选择$A,B\leftarrow \mathbb F$，然后计算$C$如下

$$ C=\frac{AB-\alpha\beta-\sum_{i=0}^la_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]}{\delta} $$

然后模拟器返回$\boldsymbol\pi=(A,B,C)$

这里需要说明一下

• $\alpha$和$\beta$的目的是确保在计算$A,B,C$时采用统一的参数$a_0,...,a_m$
• $\alpha\cdot\beta$确保了A和B中包含了$\alpha$和$\beta$的非平凡的部分，也即乘积$A\cdot B$包含了对于$\alpha$和$\beta$的线性依赖（$C$中的$\sum_{i=l+1}^ma_i[\beta u_i(x)+\alpha v_i(x)]$），这种线性依赖只能由$C$通过参数$a_0,...,a_m$得到
• $\gamma$和$\delta$的作用是将左因子分别除以$\gamma$和$\delta$，使验证方程的后两个乘积独立于第一个乘积
• $r$和$s$的目的是引入随机性（也即盲因子），使得协议满足零知识性

这里构造的针对仿射策略证明者的NILP，具备完美完备性，完美零知识性和统计知识合理性

接下来证明一下，具体可以看原文

首先是完美完备性，这个不难验证（简单手算一下就行）

其次，完美零知识性来源于真实协议执行和模拟中均具有均匀随机选择的域元素$A$和$B$，这些元素在验证等式中唯一的确定了表达式$C$，因此真实协议执行和模拟执行具有完全相同的概率分布，因此完美零知识性也成立

然后是需要证明：对于任何成功概率不可忽略的仿射策略的证明者，都可以从其上抽取出证据

当使用仿射策略的证明者，对于已知的域元素$A_\alpha,A_\beta,A_\gamma,A_\delta,A_i$，以及阶分别为$n-1$和$n-2$的多项式$A(x)$与$A_h(x)$，有

$$ \begin{aligned}&A=A_\alpha\alpha+A_\beta\beta+A_\gamma\gamma+A_\delta\delta+A(x)+\frac{1}{\gamma}\sum_{i=0}^lA_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+\frac{1}{\delta}\sum_{i=l+1}^mA_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+\frac{1}{\delta}A_h(x)t(x)\end{aligned} $$

对应于矩阵$\Pi$的第一行

对于$B$和$C$，也有相同的格式

$$ \begin{aligned}&B=B_\alpha\alpha+B_\beta\beta+B_\gamma\gamma+B_\delta\delta+B(x)+\frac{1}{\gamma}\sum_{i=0}^lB_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+\frac{1}{\delta}\sum_{i=l+1}^mB_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+\frac{1}{\delta}B_h(x)t(x)\\ &C=C_\alpha\alpha+C_\beta\beta+C_\gamma\gamma+C_\delta\delta+C(x)+\frac{1}{\gamma}\sum_{i=0}^lC_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+\frac{1}{\delta}\sum_{i=l+1}^mC_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+\frac{1}{\delta}C_h(x)t(x)\end{aligned} $$

分别对应矩阵$\Pi$的第二行和第三行

现在将验证方程视为多元洛朗多项式的等式，根据Schwartz-Zippel引理，除非将$A,B,C$视为关于$(\alpha,\beta,\gamma,\delta,x)$的多项式，否则Prover成功的概率可忽略，接下来分析一下

回看一下之前的验证等式

$$ A\cdot B=\alpha\beta+\gamma \cdot \frac{1}{\gamma}\sum_{i=0}^la_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+C \delta $$

首先发现等式右侧不包含$\alpha^2$的项，而$A\cdot B$中产生$\alpha^2$的项来自于$A_\alpha B_\alpha\alpha^2$，因此有$A_\alpha B_\alpha\alpha^2=0$，也即$A_\alpha=0$或$B_\alpha=0$，不失一般性，可以假设$B_\alpha=0$

然后观察等式右侧不包含$\beta^2$的项，而$A\cdot B$中产生$\beta^2$的项来自于$A_\beta B_\beta\beta^2$，因此有$A_\beta B_\beta\beta^2=0$，也即$A_\beta =0$或$B_\beta =0$，不失一般性，可以假设$A_\beta =0$

然后观察$A\cdot B$中包含$\alpha\beta$的项有$A_\beta B_\alpha$和$A_\alpha B_\beta$，因为假设$B_\alpha=0$，而等式右侧$\alpha\beta$的因子为1，也即$A_\beta B_\alpha=0$与$A_\alpha B_\beta=1$，不失一般性，可以假设$A_\alpha=B_\beta=1$

此时A和B可以化简为如下

$$ \begin{aligned}&A=\alpha+A_\gamma\gamma+A_\delta\delta+A(x)+\frac{1}{\gamma}\sum_{i=0}^lA_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+\frac{1}{\delta}\sum_{i=l+1}^mA_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+\frac{1}{\delta}A_h(x)t(x)\\&B=\beta+B_\gamma\gamma+B_\delta\delta+B(x)+\frac{1}{\gamma}\sum_{i=0}^lB_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+\frac{1}{\delta}\sum_{i=l+1}^mB_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+\frac{1}{\delta}B_h(x)t(x)\\ \end{aligned} $$

继续观察验证等式的右侧，发现没有$\frac{1}{\delta^2}$的项，因此

$$ (\sum_{i=l+1}^mA_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+A_h(x)t(x))\cdot (\sum_{i=l+1}^mB_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)+B_h(x)t(x)])=0 $$

不失一般性，假设$\sum_{i=l+1}^mA_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+A_h(x)t(x)=0$

继续观察验证等式的右侧，发现没有$\frac{1}{\gamma^2}$的项，因此

$$ (\sum_{i=0}^lA_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)])\cdot (\sum_{i=0}^lB_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)])=0 $$

不失一般性，假设$\sum_{i=0}^lA_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]=0$

继续观察验证等式的右侧，发现没有$\frac{\alpha}{\gamma},\frac{\alpha}{\delta},\frac{\delta}{\gamma}$的项，因此

$$ \begin{aligned}&\sum_{i=0}^lB_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]=0\\&\sum_{i=l+1}^mB_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+B_h(x)t(x)=0\\ &\sum_{i=0}^lC_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)] \end{aligned} $$

验证等式的右侧，发现没有$\alpha\gamma$和$\beta\gamma$的项，因此

$$ A_\gamma=0,B_\gamma=0 $$

综上，最初的$A,B$化简为如下

$$ \begin{aligned} &A=\alpha+A_\delta\delta+A(x) \\&B=\beta+B_\delta\delta+B(x) \end{aligned} $$

化简后，观察验证方程组涉及$\alpha$和$\beta$的这两个项：$\alpha B(x)$和$\beta A(x)$，带入验证等式，得到

$$ \begin{aligned} &\alpha B(x)=\sum_{i=0}^ma_i\alpha v_i(x)+\sum_{i=l+1}^m C_i\alpha v_i(x) \\&\beta A(x)=\sum_{i=0}^ma_i\beta u_i(x)+\sum_{i=l+1}^m C_i\beta u_i(x) \end{aligned} $$

此时对于$i=l+1,...,m$，令$C_i=a_i$，从而有

$$ \begin{aligned} &A(x)=\sum_{i=0}^ma_iu_i(x)\\ &B(x)=\sum_{i=0}^ma_i v_i(x) \end{aligned} $$

将这个回代到验证等式中，则可以得到我们需要的等式

$$ \sum_{i=0}^ma_iu_i(x) \cdot \sum_{i=0}^ma_iv_i(x) = \sum_{i=0}^ma_iw_i(x) +C_h(x)t(x) $$

这意味着，若验证等式成立，则一定有上式成立，此时代表着对于$i=l+1,...,m$，一定有$C_i=a_i$，也就是说，利用证明串$\pi$和CRS串$\sigma$构成的线性关系若能提供正确的证明，则意味着其拥有关于陈述$(a_1,...,a_l)$的证据$(a_{l+1},...,a_m)$，证毕

2 Field Element NILPs

接下来思考一个问题，是否可以进一步减少NILP中Prover需要发送的元素，因为上述证明和验证过程中用到了三个元素$A,B,C$，$[DFGK14]$这篇论文给出了一个关于布尔电路可满足性的NILP解决方案，只需要两个域元素，如果将电路修改为只使用平方门的电路，也可以将算术电路的可满足性转变为只需要两个域元素的NILP

因为乘法门$a\cdot b=c$可以改写为$(a+b)^2-(a-b)^2=4c$，此时电路中不仅只包含平方门，还可以得到$\forall i,u_i=v_i$，若此时选择$r=s$，可以得到$B=A+\beta-\alpha$，因此Prover只需要发送A和C即可，B可以由Verifier自己计算出来并用于验证

不过因为电路中将乘法门改为了平方门，此外还需要一些额外的导线来实现平方差（减法），因此若希望减小NILP使用的元素，代价是电路的规模会急剧增大

3.2 NIZK argument for quadratic arithmetic programs

接下来将QAP转化为一个基于配对的NIZK

首先是关系生成器如下

$$ R=(p,\mathbb G_1,\mathbb G_2,\mathbb G_T,e,g,h,l,\{u_i(X),v_i(X),w_i(X)\}_{i=0}^m,t(X)) $$

其中$p$的长度$|p|=\lambda$

关系定义了一个域$\mathbb Z_p$与一个语言的陈述$(a_1,...,a_l)\in \mathbb Z_p$和证据$(a_{l+1},...,a_m)\in \mathbb Z^{m-l}_p$，$a_0=1$，满足

$$ \sum_{i=0}^ma_iu_i(X) \cdot \sum_{i=0}^ma_iv_i(X) = \sum_{i=0}^ma_iw_i(X) +h(X)t(X) $$

其中商多项式$h$的阶为$n-2$

之前提到了NILP的特点是其可以得到一个拆分的NILP，验证元素$A,B,C$在验证等式中只使用一次，因此可以很容易的将他们分配到双线性测试中不同的部分，因此通过将CRS分割成两部分，使得分别计算每个部分可以完成验证，从而得到了一个拆分的NILP

由此产生的拆分NILP也是disclosure-free的，因此可以利用2.5节中的方式，在通用的群模型中编译成NIZK论证

由于易于配对的椭圆曲线中，通常$\mathbb G_1$表示的元素比$\mathbb G_2$小，因此在$\mathbb G_1$中确定元素$A$和$C$，在$\mathbb G_2$中确定元素$B$以获得最高的效率，并得到下列的NIZK论证

• $(\boldsymbol\sigma,\boldsymbol\tau)\leftarrow Setup(R)$：初始设置算法，选择$\alpha,\beta,\gamma,\delta,x\leftarrow \mathbb Z^*_p$，令$\boldsymbol\tau=(\alpha,\beta,\gamma,\delta,x)$，$\boldsymbol\sigma=([\boldsymbol\sigma_1]_1,[\boldsymbol\sigma_2]_2)$如下（方括号为之前提到的群上操作的简写）

$$ \boldsymbol\sigma_1=(\alpha,\beta,\delta,\{x^i\}_{i=0}^{n-1},\{\frac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\gamma}\}_{i=0}^{l},\{\frac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\delta}\}_{i=l+1}^{m},\{\frac{x^it(x)}{\delta}\}_{i=0}^{n-2}),\boldsymbol\sigma_2=(\beta,\gamma,\delta,\{x^i\}_{i=0}^{n-1}) $$

• $\boldsymbol\pi\leftarrow Prove(R,\boldsymbol\sigma,a_1,...,a_m)$：证明串生成算法，选择$r,s\leftarrow \mathbb Z_p$，然后计算$\boldsymbol\pi=([A]_1,[C]_1,[B]_2)$，其中

$$ \begin{aligned} &A=\alpha+\sum_{i=0}^ma_iu_i(x)+r\delta\\ &B=\beta+\sum_{i=0}^ma_iv_i(x)+s\delta\\ &C=\frac{1}{\delta}\sum_{i=l+1}^ma_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]+h(x)t(x)+As+Br-rs\delta \end {aligned} $$

• $0/1\leftarrow Vft(R,\boldsymbol\sigma,a_1,...,a_l,\pi)$：验证算法，根据收到的$\pi$，验证$\pi=([A]_1,[C]_1,[B]_2)\in \mathbb G_1^2\times \mathbb G_2$，当且仅当下列等式成立时接受

$$ [A]_1\cdot [B]_2 =[\alpha]_1\cdot [\beta]_2 +\sum_{i=0}^la_i[\frac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\gamma}]_1\cdot [\gamma]_2+[C]_1\cdot [\delta]_2 $$

• $\boldsymbol\pi\leftarrow Sim(R,\boldsymbol\tau,a_1,...,a_l)$：模拟器算法，选择$A,B\leftarrow \mathbb Z_p$，然后计算$C$如下

$$ C=\frac{AB-\alpha\beta-\sum_{i=0}^la_i[\beta u_i(x)+\alpha v_i(x)+w_i(x)]}{\delta} $$

然后模拟器返回$\pi=([A]_1,[C]_1,[B]_2)$

和上述协议相关的定理如下

• Theorem 2：上述协议是一个非交互式的零知识论证，具有完全完备性和完全零知识，且仅对具有多项式次数的泛型双线性群操作的敌手时有统计知识合理性成立

证明可以看原文，和无泄漏的CRS证明类似

Symmetric Bilinear Groups

不难证明这个非交互式论证系统也可以适用于对称的双线性群，此时CRS包含的是$[\sigma_1]_1$和$[\sigma_2]_2$的并集，但生成证明和验证的过程和上述提到的方法一致

Efficiency

证明的大小包含两个$\mathbb G_1$中的元素和一个$\mathbb G_2$中的元素，而CRS包含关系$R$，$\mathbb Z_p$中的$n$个元素，$\mathbb G_1$中的$m+2n+3$个元素和$\mathbb G_2$中的$n+3$个元素

根据之前提到的验证过程，实际上Verifier不需要知道整个CRS的内容，只需要知道

$$ \sigma_V=(p,\mathbb G_1,\mathbb G_2,\mathbb G_T,e,[1]_1,\{[\frac{\beta u_i(x)+\alpha v_i(x)+w_i(x)}{\gamma}]_1\}^l_{i=0},[1]_2,[\gamma]_2,[\delta]_2,[\alpha\beta]_T) $$

此时Verifier需要的CRS只包含$\mathbb G_1$中的$l+2$个元素，$\mathbb G_2$中的$3$个元素和$\mathbb G_T$中的1个元素

而Verifier只需要计算$\mathbb G_1$上的$l$次指数，少量群乘法和三次配对（如果假设$[\alpha\beta]_T=[\alpha]_1\cdot[\beta]_2$已经在Verifier的CRS中预计算好了，那就只需要计算三次pairing）

Prover必须计算多项式$h(X)$，对于$q=1,...,n$，Prover可以计算下面三个

$$ \begin{aligned} &\sum^m_{i=0}a_iu_i(r_q)=\sum^m_{i=0}a_iu_{i,q}\\ &\sum^m_{i=0}a_iv_i(r_q)=\sum^m_{i=0}a_iv_{i,q}\\ &\sum^m_{i=0}a_iw_i(r_q)=\sum^m_{i=0}a_iw_{i,q} \end{aligned} $$

若算术电路中连接到乘法门的导线数量是恒定的，由于$n-1$阶多项式完全由这些点评估，因此关系是稀疏的，此时计算的代价是关于$n$的线性阶

但是如果$r_1,...,r_n$是素数根，则Prover可以利用FFT算法在$O(n\log n)$次操作在$\Z _p$上计算$h(X)$，此时Prover同样可以利用FFT计算$\sum^m_{i=0}a_iu_i(X),\sum^m_{i=0}a_iv_i(X)$的系数，计算这些系数分别需要$\mathbb G_1$上的$m+3n-l+3$次指数和$\mathbb G_2$上的$n+1$次指数运算

不难发现，$\mathbb G_1$上的指数运算会很多，当安全参数增大时，指数运算会变为主要的计算开销，但是实践中对于中等安全参数和较大的statement而言，引入FFT的乘法会导致更高的开销，此时采用一个包含预处理元素的超大CRS会比较有效，比如包含$[u_i(x)]_1,[v_i(x)]_1,[v_i(x)]_2,i=0,...,m$，此时$A$和$B$可以直接计算，Prover无需计算$\sum^m_{i=0}a_iu_i(X),\sum^m_{i=0}a_iv_i(X)$的系数，同时指数运算的开销也节省了

在布尔电路的情况下，$a_i\in \{0,1\}$，此时Prover利用预处理元素，在计算$A$和$B$时只需要分别完成$m$次群乘法即可，不过这样的话，表1中的CRS会变得贼大

4 Lower bounds for non-interactive arguments

上面的内容提到了非交互式论证的效率，本节中给出一个下限，表明基于配对的非交互式论证在证明中至少需要有两个群元素

具体而言，观察基于配对的论证，CRS中包含了一个双线性群和一些群元素，证明串则包含了由Prover利用常规群操作计算得到的一些群元素，Verifier检查证明串时需要采用常规双线性群操作

对于这种基于配对的论证系统，若语言中包含下列提到的决策困难问题，则证明需要$\mathbb G_1$和$\mathbb G_2$中的元素

考虑这样一个关系$R$，其中有两种抽样算法，$Yes$表示抽样关系中的statement和witness，$No$表示抽样那些不在语言$L_R$中的statement，此时关注一个statement是被$Yes$还是$No$抽样

• Definition 5：称一个关系生成器$\mathcal R$具有决定困难问题，则有两个多项式时间算法$Yes$和$No$，分别表示当选择$(R,z)\leftarrow\mathcal R(1^\lambda)$时，有$Yes(R)\rightarrow(\phi,w)\in R$和$No(R)\rightarrow \phi\notin R$，对于任意非均匀多项式时间的区分器$\mathcal A$，有

$$ Pr[(R,z)\leftarrow \mathcal R(1^\lambda);\phi_0\leftarrow No(R);(\phi_1,w_1)\leftarrow Yes(R);b\leftarrow\{0,1\}:\mathcal A(R,z,\phi_b)=b]\approx \frac{1}{2} $$

此时区分器区分这两个statement的概率约为$\frac{1}{2}$

若单向函数存在，则可以构造伪随机发生器，通过伪随机发生器可以生成一个伪随机串，此时该发生器的种子就是Yes算法的证据，而No算法则均匀选择一个随机串，且要求该串以极高的概率不是伪随机的

此时，若关系R是NP完备的，或知识表达得足以捕获为随机生成器，则其包含了一个决策困难问题

具体而言，当采用基于配对的论证时，必须假设离散对数问题是困难的，则此时存在一个具有决策困难问题的关系生成器

4.1 Linear interactive oofs cannot have linear decision rocedures

证明了Bitansky等人$[BCI+13]$NILPs不能包含一个度为1的Verifier，该结论即便在考虑获得输入$\boldsymbol \sigma_V$的指定Verifier的NILP（$\boldsymbol \sigma_V$对Prover不可见），且仅考虑弱化的合理性（而非知识合理性）时仍然成立

• Definition 6(Statistical soundness against affine prover strategies)：若一个LIP，对于任意敌手$\mathcal A$，有

$$ Pr[(R,z)\larr \mathcal R(1^\lambda);(\boldsymbol \sigma_P,\boldsymbol \sigma_V,\boldsymbol \tau)\larr Setup(R);(\phi,\Pi)\larr(R,z),\boldsymbol \pi=\Pi\boldsymbol \sigma_P\larr Test(R,\phi,\boldsymbol \sigma_V):\phi\notin L_R\wedge \boldsymbol t(\boldsymbol \pi)=0]\approx0 $$

则称该LIP在对抗放射策略的Prover时满足合理性

这里还有一个相关的定理

• Theorem 3：对于决定性困难问题，不存在Verifier度为1的NILP

定理的具体的证明可以看原文

定理3的证明也适用于拆分的NILP。也即如果限制合理性敌手生成两个拆分的矩阵$\Pi_1,\Pi_2$，这只能表示Prover和敌手可以生成证明矩阵的一个而外显子，而2.5接种，本文利用disclosure-free的拆分NILP构造了基于配对的SNARK，disclosure-free的属性确保了一般合理性的敌手无法在基于配对的构造中从CRS中得到任何其感兴趣的信息，此时敌手只能选择一个statement$\phi\notin L_R$和一个独立于CRS串$\boldsymbol \sigma$的证明矩阵$\Pi$并祈祷这个证明矩阵可以通过验证，但是由于单元素证明对应于第三类配对中的线性决策过程，因此可以得到下列推论

• Corollary 1：一个由disclosure-free的拆分NILP构建得到的基于第三类配对的SNARK的关系生成器，其证明串中至少包含两个元素，才可以证明非平凡的语言

4.2 Lower bound for the size of generic pairing-based non-interactive agruments

由于不要求CRS保密，因此第三类群上基于配对的非交互式论证必须在$\mathbb G_1,\mathbb G_2$中都包含元素，因为如果我们有一个只有单个$\mathbb G_1$或$\mathbb G_2$中的元素的单边论证，则验证方程会变为线性的，从而导致合理性不成立，为了做到通用性，本文展示了即便是CRS和证明串中包含了$\mathbb G_T$中，这一点也成立，从而我们可以得到一个结论：基于配对的非交互式论证的证明中至少包含两个群元素

现在考虑基于配对的论证系统$(Setup,Prove,Vfy)$，其中CRS和证明由采用普通群运算计算的群元素组成，Verifier采用普通双线性群运算来检查证明，通过创建一些配对乘积方程，并限制这些方程在都成立时Verifier才接受，所有已知的基于配对的SNARK都满足此限制，该限制排除了违反声称论证是“基于配对”的意图的可能性（最后这句话没理解）

比如说，若CRS和证明以群元素的比特幂表示，也即表示为$(G^0,G^1,...,G^1,G^0)$，此时我们可以想象一下，Prover可以读取CRS中的比特串，并使用这个比特串创建基于非配对的SNARK，并将其编码为发送给Verifier的比特串，之后Verifier会解码这个串并验证，显然这只是一种非常麻烦且不同类型的SNARK，并不能称为是基于配对的

总之，结论是基于配对的非交互式论证中，无论怎么做，证明串中都至少包含两个群元素

总结

回顾一下之前R1CS和QAP的那篇博客$[2]$，里面介绍了如何从算术电路构建R1CS，最后利用多项式插值法转化到QAP

那篇博客中提到了，利用拉式插值法，将验证矩阵转化为多项式，采用多项式的原因是验证多项式的相等比验证相同大小的向量要快得多

根据Schwartz–Zippel Lemma，在一个很大的域上随机选一个点，若两个多项式不相等，则这两个多项式在该点的取值相等的概率微乎其微，这也是所有SNARK方案中采用多项式来优化提速的最主要的原因

既然得到了QAP问题，Groth16的工作就是基于这个QAP构造zk-SNARK了，简单来说就是利用KoE假设和双线性配对

Koe假设有两个目的，一个是可以使我们采用域（或者说椭圆曲线域）上的点来表示多项式，另一个是强制Prover生成正确的$\alpha$对，也即确保Prover不会作弊（Koe假设可以看$[3]$和$[4]$）

但是这个$\alpha$应当是保密的，如何生成$\alpha$对是个问题，目前只有两种解法，一个是引入可信第三方，由第三方生成$\alpha$对（也即由第三方生成CRS串），另一个方法是引入MPC协议来模拟可信第三方，这两种方法暂不讨论，本文主要还是关注如何构建zk-SNARK

对于验证$\alpha$对，需要采用双线性配对，本文采用的是第三型配对，因为非对称的构造效率要比对称的要高得多

剩下的就是证明和验证了，不难看出CRS中有很多的点，$\boldsymbol \sigma_1$包含的是群$\mathbb G_1$中的点，$\boldsymbol \sigma_2$包含的是群$\mathbb G_2$中的点，这两个CRS隐含了许多的$\alpha$对，$\beta$对，$\gamma$对，$\delta$对，用于后续Prover生成证明和Verifier的验证

注意到证明的上号Prover没有显示构造$\alpha$对，$\beta$对，而是通过选择两个随机数$r,s$，并通过线性组合的方式构造（$[3]$中有介绍，一些$\alpha$对线性组合的结果仍然是$\alpha$对），随机数的目的是为了确保协议的零知识性

最后通过Groth设计的验证算法，这些复杂的$\alpha$对，$\beta$对，$\gamma$对，$\delta$对都可以消掉（具体可以看3.1节的证明过程），剩下的那个就是最原始需要验证的QAP

此外，这篇paper还给出了一个结论，采用配对的非交互式论证的证明串至少需要包含两个元素，少一个都不行，否则会破坏协议的合理性

本文的方案有三个群元素，群$\mathbb G_1$有两个，群$\mathbb G_2$一个，Groth也在原文中说明了，还不知道是否可以做到两个元素的证明串，但是在那之前，本文的方案就是最好的，不过许多加密货币和区块链系统都用上了Groth16的方案，也证明了他确实是高效的

当然也存在缺点，其一是CRS很长，具体的看表1和表2就知道了，不过和前人的工作比起来，也算优化了不少，其二是需要可信设置，也即常说的Trust Setup，这是一个比较关键的点，尤其是在区块链这种无信任的环境下，引入可信第三方是一个极其复杂的问题，要不然就只能走一个MPC协议，但是如何执行这个MPC协议又是另一个值得研究的问题了

不过也有其他的解决方案，比如STARK，其中的T就代表着Transparent，透明的意思，透明即代表无需可信第三方，可以在无信任的环境中执行协议，STARK也有自己的优缺点，这里不再展开

总的来说，Groth16算法最大的有点就是最短的证明串和最搞笑的Verifier验证开销，目前仍然是最广泛应用的zk-SNARK方案

后记

怎么说呢，上周看Groth10的时候顺便翻了一下自己Groth16的博客，感觉有很大的问题，因为原来自己看Groth16的时候也没看完全看懂

这段时间看了不少paper，感觉自己对zk-SNARK有了全新的理解，于是打算回来再看一i按这篇曾经似懂非懂的paper，然后重新整理思路写了这篇博客

总的来说收获不少，也确实是搞懂了从算术电路一步步构建，最终到达zk-SNARK的全流程了，懂确实是懂了，但是还是需要多看多巩固

看起来似乎很简单，但是整个流程其实还是比较复杂的，还是需要时间多学习

参考文献

$[1]$ Jens Groth:On the Size of Pairing-Based Non-interactive Arguments. EUROCRYPT (2) 2016: 305-326

$[2]$ R1CS and QAP - Snowolf's Island

$[3]$ 零知识证明（17）：系数知识测试 - Snowolf's Island

$[4]$ Hardness Assumption - Snowolf's Island