SpaceStation09 / my-notes

Mozilla Public License 2.0
0 stars 0 forks source link

零知识证明:R1CS 与 QAP #3

Open SpaceStation09 opened 1 day ago

SpaceStation09 commented 1 day ago

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


这其中就包含了这篇博客要讲的两个重要流程,R1CS 和 QAP:

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

SpaceStation09 commented 1 day ago

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 commented 1 day ago

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_1sym_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: image

SpaceStation09 commented 1 day ago

R1CS to QAP

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

我们依然以向量组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 commented 15 hours ago

Checking QAP

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


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

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:

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

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

SpaceStation09 commented 15 hours ago

结语

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