理解Groth16，一些细节上的说明

V神曾经写过一篇非常好的介绍R1CS与QAP问题的文章。但是，对于不熟悉密码学的，或者说如何使用密码学的思想来解决问题的票友们来说，文章中的一些逻辑上的跨度还是大了一些。尤其是在R1CS转换成多项式的地方，初次接触的人可能会一脸懵逼，不明白为什么要这么做。下面我就从我的理解来谈一谈，从R1CS到QAP这一过程。

在Groth16的流程中，我们首先需要把计算问题拍平成电路的形式。在这一步骤中，我们会将原始的计算问题，解构成电路的形式(Circuit)。这个电路和原始的计算问题是等价。电路由若干的有输入有输出的算数电路门(Gate)组成。通常情况下，这些电路门都是由两个输入变量，一个输出变量组成。然后我们基于每一个电路门，来构造R1CS约束。

$$ a * b = c $$

这里我们直接使用V神的博客中的例子。下面的三个矩阵是就是原问题对应的电路的R1CS的约束矩阵。

A [0, 1, 0, 0, 0, 0] [0, 0, 0, 1, 0, 0] [0, 1, 0, 0, 1, 0] [5, 0, 0, 0, 0, 1]

B [0, 1, 0, 0, 0, 0] [0, 1, 0, 0, 0, 0] [1, 0, 0, 0, 0, 0] [1, 0, 0, 0, 0, 0]

C [0, 0, 0, 1, 0, 0] [0, 0, 0, 0, 1, 0] [0, 0, 0, 0, 0, 1] [0, 0, 1, 0, 0, 0]

这三个矩阵都包含了四个行向量，代表了原始的计算被拍平成了在R1CS约束下的四个电路门。到了这一步，我们的原问题”我们知道原始计算的一个解“就转化成了，“我们知道一个解向量，使得它在每个电路约束下都成立”。我们用$S$来表示解向量，本例中$S$的值如下所示。

1 3 35 9 27 30

此时，如果我们想证明我们知道原始计算的一个解，那么就需要证明A，B，C矩阵中的每个行向量与解向量$S$的内积之后的值是符合R1CS约束的($A_i,B_i,C_i$表示矩阵中的行向量)：

$$ (A_iS) (B_iS) - C_iS = 0 $$

在接下来的一步，我们需要将R1CS的约束转换成一个QAP问题。我觉得原文中没有提到的一点时，我们为什么要这么做的？这样的转换目的是什么？V神的原文只描述了这一步骤的目标是把向量的内积计算转化为多项式的形式，以及如何进行拉普拉斯插值求多项式。所以第一次读到这里的时候，我感觉一头雾水。

这一过程是理解包括Groth16在内的所有ZK-Proof System的重点。这里阐述一下我的理解。这样做的原因是，如果只使用R1CS的约束矩阵来验证，我们只能一个电路门，一个电路门的，使用列向量与解向量的内积来验证是否满足R1CS的约束。这样在方式在大规模电路下（几十万，上百万的电路门）显然是十分低效的。

那么接下来的自然思考方向就变成了，存不存在一种办法，可以让我们通过一次/个计算来验证所有约束的正确性？

我们如果仔细观察上面的计算过程，可以发现解向量中 $S$中的 $S1$元素一定与约束矩阵中$A{11}$，$A{21}$，$A{31}$，$A_{41}$这四个元素相乘。因此，我们假设存在这样一个多项式 $A_1(x)$，它经过$(1,0), (2,0), (3,0), (4,5)$这四个点。这个多项式 $A_1(x)$的数学意义是：当x的值为1时，多项式的值为0，当$x=2$时，多项式的值为0，当$x=3$时，多项式的值为0，当$x=4$时，多项式的值为5。这样，我们通过引入额外的参数x，使得可以使用一个的多项式$A1(x)$来描述[$A{11}$，$A{21}$，$A{31}$，$A_{41}$]这四个值。

根据原文中提到的拉普拉斯插值法，我们可以求出关于[$A{11}$，$A{21}$，$A{31}$，$A{41}$]的多项式为：

$$ A_1(x) = 0.833x^3 -5.0x^2 +9.166*x -5.0 $$

我们验证一下就可以发现，当x取1时，$A1(x)$的值为0，等于原R1CS约束矩阵中的$A{11}$的值。同样的，我们可以构造出其他列向量的多项式$A_i(x),B_i(x),C_i(x)$。

那么这样，我们就可以使用这几个多项式来描述，向量内积是否满足R1CS约束的过程。我们将解向量$S$带入，原等式的左边可以写成下面的形式:

$$ ((1 A_1(x))+(3 A_2(x))+(35 A_3(x)) + (9 A_4(x)) +(27 A_5(x))+(30 A_6(x))) \ （(1 B_1(x)+(3 B_2(x))+(35 B_3(x)) + (9 B_4(x)) +(27 B_5(x))+(30 B_6(x))) \ - （(1 C_1(x)+(3 C_2(x))+(35 C_3(x)) + (9 C_4(x)) +(27 C_5(x))+(30 * C_6(x))) $$

当x取1时，上面的多项式就等于验证第一个门电路是否满足R1CS约束；当x取2时，上面的多项式就等于验证第二个门电路是否满足R1CS约束。以此类推。现在我们已经将实际的值转换成了多项式，根据x的取值的不同，来描述不同的R1CS约束。

那么，更进一步的来说，因为上面的式子中都是多项式，我们可以把等式左边展开成一个更简洁的多项式 $p(x)$:

$$ p(x) = (-5.166x^3+38.5x^2-73.333x+43)(0.666x^3-5.0x^2+10.333x-3.0)-(2.833x^3-24.5x^2+10.333x-41.0)\ = -3.440556x^6+51.471x^5-294.720056x^4+805.7885x^3-1063.749889x^2+592.652x-88 $$

同时我们需要让等式右边的值等于0。因此，我们就可以先构造一个多项式$t(x)=(x-1)(x-2)(x-3)(x-4)$。显然$t(x)$在x的取值为[1，2，3，4]值情况下都等于0。在本例中，显然$t(x)$是不等于$t(x)$（多项式的阶不同），所以我们引入另一个多项式$h(x)$，使得$p(x)=t(x)h(x)$。

这一步的操作中蕴含了一个数学引理: Schwartz–Zippel lemma。感兴趣的读者可以深入了解一下这个引理。

这样我们就实现了用一个多项式来描述所有的R1CS的约束了。我们可以设置x值取1，2，3，4，来验证对应的电路的R1CS约束是不是合法。在实际问题上，x的取值远不止范围1，2，3，4四个值。

现在的关于Prover是否知道原问题的解的证明转换成了，Prover是否知道一个基于原电路R1CS约束正确插值形成的多项式$p(x)$，使得$p(x)=t(x)h(x)$在x的域上都成立。

那么，顺着这个逻辑继续思考，Prover如何向其他人证明，他/她知道这个多项式$P(x)$的存在的呢？

最简单的方法就是，Prover直接把$p(x)$这个多项式发给Verifier。但是在现实中，多项式$p(x)$的degree可能非常的高，传输$p(x)$成本很大，不符合简洁证明的要求。那么，另一个简单的想法可以是这样的。在公式$p(x)=t(x)h(x)$中，$t(x)$是公开的多项式，那么作为知道$p(x)$的Prover，我们可以快速的计算出$h(x)=\frac{p(x)}{t(x)}$。那么，我们只要提供某个$x=r$对应的$h(r)$,$p(r)$的值给验证者。那么显然，验证者通过计算$t(r)*h(r)$的值，与Prover提供的$p(r)$的值进行比较验证。那么作为Prover，我们不需要公开$p(x)$的细节，就可以向Verifier证明我们知道多项式$p(x)$。

那么想象一下，Alice对Bob说，我知道一个计算的解。那么Bob可以要求Alice计算$x=r$时，$h(r)$和$t(r)$的值，并且验证$h(r)*z(r)$是否与$t(r)$的值是否相等来判断Alice说的是否正确。同时，在这个过程我们完美的隐藏掉了原来解向量$S$的存在。

通过，上面的过程，我们就完成了一个简单的零知识问题的转换。但是这个模型并不足够安全，比如Alice可以伪造合法的$h(r)$和$t(r)$的值，使得$t(r)=z(r)h(r)$成立。具体的来说，比如不管Bob请求任意r下的$h(r)$值，Alice总是返回$h(r),t(r) == 0$。用稍微正式的语言来描述这个现象就是：Alice知道了$r$的具体值之后，可以计算出另一组值$t(r')$,$h(r')$，使得$t(r')=z(r)h(r')$成立。因此在这种情况下，等式的左右两边仍然是相同的，但是不符合我们的目标。

因此，顺着这个逻辑思考，接下来的需要解决的问题就变成了，如何保证Prover不会伪造$h(r)$,$p(r)$的值呢？

这一步就是文章中从QAP到PCP(Probabilistic Checkable Proofs)这一步. 目前这部分主要是通过KCA(Knowledge of Coefficient Test and Assumption)来实现的。Groth16中，我们需要对多项式(电路)建立Common Reference String(CRS)，来保证non-interactive。这也就是我们常常听到的Trusted Setup。Trusted Setup带了不少负面效果。一旦Trusted Setup时的信息发生了泄漏，整个的Proof System的安全性保证也就不存在了。同时在Groth16中，我们需要对每个多项式都进行Trusted Setup的。换句话说，我们需要对每个计算电路都要进行一次的Trusted Setup，这对于图灵完备的通用计算来说成本是非常高的。这也是为什么目前只有ZCash可以良好的运行ZK-SNARKs，而很少见到在General-Purpose Blockchain中使用ZK-SNARKs相关技术的原因之一。

为了解决这方面的问题，研究人员提出了BulletProofs。BulletProofs将Groth16中的多项式证明的部分升级成了基于Inner production-base Polynomial Commitment Scheme。在BulletProofs中，多项式的验证不再需要Trusted Setup，但是需要更大的Proof Size。

另一方面，研究人员提出了Plonk协议，这是另一种证明体系。在Plonk中的电路约束不再是R1CS的形式，并且引入了KZG(KATE Commitment)作为Polynomial Commitment Scheme。在Plonk体系中，只需要一次的Trusted Setup，就可以给多个多项式进行验证。目前，基于zk-rollup技术的Layer-2解决方案ZKSync就是基于Plonk协议开发的。

关于Plonk，PCS的技术在本篇中不做详解。感兴趣的读者可以搜索相关的关键词进行学习。

Thanks to Zhang Ye, Peng Jingshu for review.

References

1. Bulletproofs: Short Proofs for Confidential Transactions and More, [link]
2. Schwartz–Zippel lemma, [link]
3. Quadratic Arithmetic Programs: from Zero to Hero, [link]
4. Kate Commitments: A Primer, [link]
5. Constant-Size Commitments to Polynomials and Their Applications, [link]
6. Understanding PLONK, [link]