零知识证明 - Coda SNARK挑战（Stage2）

SNARK挑战的第二阶段（Stage2）挑战的主要内容是：Groth16算法的证明生成和验证性能的优化。第二阶段的挑战又分成两部分内容：Groth16算法的证明生成（65000美金）以及Groth16算法的验证（10000美金）。

SNARK挑战使用的零知识证明算法是：BG18。BG18是Groth16算法的一种变种算法，由Zcash的团队在2018年发表。

https://eprint.iacr.org/2018/187.pdf

BG18的证明的生成，比Groth16算法增加了z变量。

BG18的验证，比Groth16算法增加了一个验证：

        ![](https://img.learnblockchain.cn/2020/03/01_/355299853.png)

01 BG18算法的验证

https://codaprotocol.github.io/snark-challenge/verifier.html

挑战的主要内容：优化JS或者WebAssembly，提高BG18算法的验证性能。这部分不需要GPU优化。不详细介绍。主要介绍一下，证明生成的挑战内容。

02 BG18算法的证明生成

https://codaprotocol.github.io/snark-challenge/problem-07-groth16-prover-challenges.html

BG18算法的证明生成逻辑涉及到以下相关的计算：

G1/G2椭圆曲线的点加和多点加法求和以及快速FFT（快速傅立叶变换）。

在$\Bbb F MNT4753$或者 $\Bbb F MNT6753$上，给定如下的参数：

• d （uint64)

  可以理解成门电路多项式的最高项的阶，也可以理解成门的个数

• m （uint64）

  m+1可以理解成整个电路向量的大小

• A （G1， m+1）

  G1椭圆曲线上m+1个点

• B1（G1，m+1）

  G1椭圆曲线上m+1个点

• B2（G2，m+1）

  G2椭圆曲线上m+1个点

• L（G1，m+1）

  G1椭圆曲线上m+1个点，可以理解成witness的部分

• T（G1，d）

  G1椭圆曲线上d个点

在挑战描述的符号下，BG18算法满足的QAP表示为：$\sum^m_{i=0}\omegaA_i(x)\sum^m_{i=0}\omegai*B(x)-\sum^m{i=0}\omega_iL(x)=H(x)T(x)$。如果电路给定，$A_i(x),B_i(x),L_i(x)$也就确定。注意$A_i(x),B_i(x),L_i(x)$是多项式，A/B1/B2/L是椭圆曲线上的点。对一个确定x，再给定G1/G2椭圆曲线的基点，对应椭圆曲线上的点也可以确定，这也是为什么直接给出A/B1/B2/L的原因（在证明生成中，L只需要计算witness的部分，所以只需要提供m+1个点就足够）。因为门电路的个数是d，也就是$T(x)=(x-t_1)(x-t_2)...(x-td)$，表示成多项式 $T(x)=x^d+T{d_1}*x^{d-1}+...$。给出的T参数，就是多项式每一项的在椭圆曲线上的点。

以上的信息，可以理解成电路的相关信息。再提供以下的输入信息：

• w（F，m+1）

  statement+witness信息

• ca，cb，cc（F，d+1）

  在给定x的情况下，$Ai(x)$的值给定。并且已知w的情况下$\sum^m{i=0}\omegaAi(x),\sum^m{i=0}\omega_iB(x),\sum^m_{i=0}\omega_i*L(x)$都可知。ca，cb，cc是$\omega^0,\omega^1,...,\omega^d$对应的各个多项式的值。

• r（F）

  r满足$\sigma^{r-1}=1$，每个$\sigma$值在每个域已经给定。在给定$\sigma,\gamma$的情况下，$\omega=\sigma^{(r-1)/(d+1)}$，也就是$\omega^{d+1}=1$。

计算BG18的证明信息：A（G1），B（G2），C（G1）。计算公式如下：

注意以上的计算公式，并不是完整的BG18或者Groth16的计算公式，但是，绝大部分的计算量已经体现。

在以上的计算中，只有$H[i]$未知。$T(x)=(x-1)(x-\omega^1)(x-\omega^2)...(x-\omega^d)=x^{d+1}-1$。

挑战的说明，给出了利用傅立叶变换和反变换的方式计算$H[i]$的过程。

1. ca，cb，cc是$\omega^0,\omega^1,...,\omega^d$对应的各个多项式的值。通过反傅立叶变换，可以获取$fA(x)=\sum^m{i=0}\omega_iA_i(x),fB(x)=\sum^m{i=0}\omega_iB_i(x),fC(x)=\sum^m{i=0}\omega_i*L_i(x)$多项式对应的系数。

2. 在已知系数的情况下，并对每个系数进行偏移（每个系数乘以$\sigma^i$），通过傅立叶变换，可以计算出$\sigma ,\sigma\omega^1,\sigma\omega^2,...,\sigma\omega^d$对应的多项式的值。

3. 因为 所以从第2步的结果，可以求解出$f_H(x)$的$\sigma ,\sigma\omega^1,\sigma\omega^2,...,\sigma\omega^d$对应的多项式的值。

4. 通过傅立叶逆变换，可以求的$f_H(x)$的系数的表示形式。每个系数除以$\sigma$，就能求得$f_H(x)$的系数的最终结果。

总的来说，需要三次傅立叶变换和4次傅立叶逆变换获取H多项式的系数。整个证明生成，还需要G1椭圆曲线上的4次多点加法求和计算和G2椭圆曲线上的一次多点加法求和计算。

总结：

Stage2的挑战是对BG18（Groth16）算法的性能优化。计算量涉及点加和多点加法求和以及快速FFT（快速傅立叶变换）。