零知识证明：R1CS 与 QAP

[SpaceStation09]

zk-SNARKs 是一种比较难掌握的技术，我们需要将大量的部件组合在一起，才能使整个系统正常工作，因此，想要深入学习这项技术，我决定将各项部件拆解，分别学习并理解它。zk-SNARKs 不能直接应用于任何计算问题，我们需要将计算问题一步步的转化为正确的“形式”，以便问题可以在zk-SNARKs的体系中顺利运行，其流程如下图：

这其中就包含了这篇博客要讲的两个重要流程，R1CS 和 QAP： - R1CS 的全称是 Rank-1 Con­straint Sys­tem，一阶约束系统，其本质是一个方程组。 - QAP 全称 Qua­dratic Arith­metic Problem， 二次算术问题。QAP 转换不仅可以将函数的代码转换为 QAP，还可以在转换的同时构建一个对应于代码输入的解（又称为 QAP 的 Wit­ness），之后再基于这个 wit­ness 构建一个实际的零知识证明系统。

后文将以Vitalik的文章Quadratic Arithmetic Programs: from Zero to Hero 为参照，详细展开解释R1CS和QAP转换的流程。

[SpaceStation09]

QAP问题

假设，Prover 希望想Verifier 证明其知道方程： $x^3+x+5=35$ 的解 (Prover知道x = 3 是方程的解，因此 witness 为 x = 3），接下来，我们可以看看如何进行 QAP 转换。
首先，我们将该方程用一种特殊的程序设计语言描述：

def qeval(x):
    y=x**3
    return y+x+5

需要注意的是，这个特殊的程序设计语言仅支持最基本的算术运算（加减乘除）和常数次幂的运算（i.e. 只能计算 x^7 ，但不可以计算x^y），此外，该语言还对计算步骤和逻辑有限制，也即不允许出现循环，不支持模运算和比较运（<,>,geq,leq,==,!=），因为在有限循环群算法中没有直接进行模运算或比较的有效方法，如果确实存在的话，则意味着破解椭圆曲线的速度比二进制搜索和中国剩余定理还要快得多。

[SpaceStation09]

Flattening

第一步，我们需要将以上的代码拍平，转化为两种一次的表达式：

1. x = y
2. x = y (op) z ( op can be +, -, *, /)

那么经过拍平后，我们的结果如下：

sym_1 = x x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 +5

这时，可以将上述的每一行理解为一个数学电路中的逻辑门（如下图），与上一part中的代码相比，我们引入了sym_1 和 sym_2两个中间变量（signal），输出标记为~out。

R1CS

第二步需要将flattening的结果转化为一阶约束系统 R1CS，一个R1CS是由三个向量构成的向量组(a, b, c), 我们可以把R1CS的解向量，记为s，则s满足： $(s·a) * (s·b) - s·c = 0$ 其中 · 表示向量内积，*表示乘法。
我们可以将flattening后的每一行语句转化为一个R1CS的向量组：

1. 将所有用到的变量用s来表示：s = [~one, x, ~out, sym_1, y, sym_2] 其中，~one是一个伪变量，其代表常数1。
2. a, b, c实际为系数变量, 参考下图，了解a, b, c的取值是如何得到的：

同理，我们可以得到：
第2行, sym_1 * x - y = 0：

a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]

第3行, (y + x) * 1 - sym_2= 0：

a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 0, 0, 0, 1]

第4行, (sym_2 + 5) * 1 - (~out) = 0：

a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]

此时之前，我们说witness为 x = 3，现在我们转化为了 s = [1, 3, 35, 9, 27, 30], 这个向量s是使得以上四个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]

[验证]
我们有向量s = [1, 3, 35, 9, 27, 30]， 然后我们取一组约束，以最后一个约束(sym_2 + 5) * 1 - (~out) = 0为例， 此时:

a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]

代入 $(s·a) * (s·b) - (s·c) = 0$ , 我们不难验证， 向量s满足这个R1CS：

[SpaceStation09]

R1CS to QAP

接下来，我们需要将R1CS转化成 QAP的形式，什么是QAP形式呢？实际上，QAP实现了与R1CS完全相同的逻辑，只不过使用的是多项式而不是向量内积的形式。我们的具体做法是这样的：

• 压缩矩阵：现在：每个向量组中：4个长度为6的向量 => 6 个 degree 为3的多项式 (6个长度为4的向量）
  其意义是：在A,B,C 中，每个x坐标处的多项式，代表一个约束（向量）
  当 x = 1时，我们求出的多项式，应该就是第一行的向量，
  当 x = 2时，我们求出的多项式，应该就是第二行的向量，以此类推。

我们依然以向量组A 为例， 首先，我们需要求出四个约束（row）所对应的每个a向量的第一个值的多项式。此时，我们就像当于拥有了四个点：x = 1时（第一行），a向量的第一个值为0，得到点(1,0)；x = 2时（第二行），a向量的第一个值为0，得到点(2,0)，以此类推，我们有四个点(1,0) (2,0) (3,0) (4,5)。我们想要求得一个有关向量a的第一个值的多项式，其能同时满足4个约束，i.e. 该多项式的图像，经过这四个点，那么我们可以使用 拉格朗日插值法，求得该多项式。 可以使用在线工具Cubic Polynomial Generator进行计算。我们计算可得，对于，a向量第一个值相关的多项式为：

$$y_1 = -5 + 9.166x -5x^2 + 0.833x^3$$

将多项式按x的degree升序排列，得到系数向量[-5, 9.166, -5, 0.833]。
以此类推，继续计算所有的多项式，得到：

A polynomials
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]

B polynomials
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]

C polynomials
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]

[验证]
将x=1代入这些系数构成的多项式，我们可以恢复出，3个R1CS中，第一个约束（行）的三个向量:
a = [0, 1, 0, 0, 0, 0], b = [0, 1, 0, 0, 0, 0], c = [0, 0, 0, 1, 0, 0]。

Q： 既然有了R1CS， 为什么我们还要将其转化为QAP呢？
A：我们可以通过对多项式进行内积的检查，从而能同时检查A的所有约束， 而不是单独检查R1CS的约束。

[SpaceStation09]

Checking QAP

正如上一部份的末尾所说，我们做R1CS to QAP的原因是：有了QAP这个形式，我们可以通过在多项式上做内积的检查，来同时检查所有的约束，而不是单独检查R1CS中的每一条约束。具体来说，是这样做的：

根据上一部分中的计算，我们可以得到：

A · s = [43.0, -73.333, 38.5, -5.166]
B · s = [-3.0, 10.333, -5.0, 0.666]
C · s = [-41.0, 71.666, -24.5, 2.833]

在此，我们挑选一个作为例子，简单计算一下， 以B为例：
$$B · s = [ 3.0 * 1 + (-2) * 3, -5.166 *1 +5.166 *3, 2.5 *1 + (-2.5) *3, (-0.333)*1 + 0.333 * 3] = [-3, 10.333, -5, 0.666]$$

此时我们得到的A · s, B · s, C · s，实际上是多项式中的系数，即，

$$A(x) = -5.166 x^3 + 38.5 x^2 -73.333x +43$$

$$B(x) = 0.666 x^3 -5 x^2 +10.333x -3$$

$$C(x) = 2.833 x^3 -24.5 x^2 +71.666 x -41$$

我们希望 $t = (A · s)* (B · s) - C · s = 0 $在x=1, x=2,x=3,x=4时均成立（满足约束），如果均成立，则证明，我们知道一个witness，可以满足上述的所有约束。

为了节省验证的计算成本，我们再对这个statement进行一点变形：我们首先给一个多项式 $z=(x-1)*(x-2)*(x-3)*(x-4)$ 这个多项式是什么呢？在x=1, x=2, x=3, x=4时，值均为0的最小多项式。在线性代数中，我们有一个定理，如果我们的多项式t也在x=1, x=2, x=3, x=4时，值为0，那么 t一定能被这个最小多项式z整除。现在，statement的形式变了，变成了： `t/z 是否有余数。

接下来我们开始验证这个新的statement：

• 我们先将z化简为: $z=24-50x+35x^2-10x^3 + x^4$ => z = [24, -50, 35, -10, 1]
• 计算得到 $t=-88 + 592.666 x - 1063.777 x^2+ 805.833 x^3 -294.777x^4 + 51.5 x^5 - 3.444 x^6$ (此处因为一些小数点的精确问题，导致我自己计算的结果 与 vitalik原文的结果不太一样，但比较接近，此处暂时采用原文的值）=> t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]
• 计算得到 $t/z = -3.666 + 17.055 x -3.444 x^2$ ，没有余数。（ 此处也比较奇怪，我用在线工具计算，并没有得到整除的结果，怀疑也是因为小数点运算的问题。不过查询后，发现在本例子的计算中，无需在意此情况，因为zk-SNARKs 的有限域是整数。不用担心因为小数点运算带来的无法整除的情况。）

到此，我们已经完成证明，我们有了QAP的证明答案。

[Counter Example]
假设，我们想要造假，我们并没有一个正确的witness s 向量，我们将s的某一个element 改掉，那么我们得到的多项式t 就不会被 z整除。那么 QAP也无法得证。

[SpaceStation09]

结语

实际上，在上面的计算中，我也发现了，因为各种小数点运算的精度问题，导致很多误差的产生，所以，后面会在以上的流程中，出现更多的优化操作。我们实际使用中的zk - SNARKs 也会在有限域上做算术运算，这样结果就是整数了，避免了误差问题。

[SpaceStation09]

Reference

1. Quadratic Arithmetic Programs: from Zero to Hero
2. 零知识证明（13）：R1CS与QAP