Zero Knowledge Proof 解密 QAP

2019-04-03 本文已影响0人末座少年

本文的内容来自于V神的博客文章，再加上一些自己的理解。验证代码在https://github.com/ethereum/research/blob/master/zksnark/

零知识的证明逻辑需要花很多篇幅仔细介绍，涉及到QAP，KCA，Groth16，同态隐藏，双线性映射等。这篇文章主要介绍quadratic arithmetic program（QAP）。

ZK-snark不能直接拿来应用，我们必须把原始数据转换成适合ZK-snark处理的方式。以如下的3次方等式为例：

x**3 + x + 5 == 35 (答案是 3)

编程Python程序如下：

def qeval(x):

y = x**3

return x + y + 5

扁平化展开

上面的2元3次方程可以展开为：【1】

sym_1 = x * x

y = sym_1 * x

sym_2 = y + x

~out = sym_2 + 5

R1CS转换

rank-1 constraint system (R1CS) 是一个（a.b.c)的3个向量，R1CS的解答是一个向量S,满足s . a * s . b - s . c = 0, 此处 . 代表相应位置的乘法,然后再将乘法的结果相加，随后，对b 和s ，以及 c 和 s做同样的操作。

S.a=（1×5 +3×0 +35×0 + 9×0 + 27 ×0 + 30 ×1） =35

S.b=（1×1 + 3×0 +35×0+9×0+27×0+30×0）=1

S.c=（1×0 +3×0 + 35×1 + 9×0+27×0+30×0）=35

显然上面的S向量（1，3，35，9，27，30）就是上述二元3次方程的一个解

为了规范化，我们加了一个哑元'~one'，以及中间变量'sym_1', 'sym_2'，向量变成下面这样：

'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'

第一个门：

a = [0, 1, 0, 0, 0, 0]

b = [0, 1, 0, 0, 0, 0]

c = [0, 0, 0, 1, 0, 0]

上面的（a，b，c）矢量组表示下面的语句：s.a*s.b-s.c=0

sym_1 = x * x

同理：

a = [0, 0, 0, 1, 0, 0]

b = [0, 1, 0, 0, 0, 0]

c = [0, 0, 0, 0, 1, 0]

代表：

sym_1 * x = y

上面的语句来自【1】

sym_1 = x * x

y = sym_1 * x

sym_2 = y + x

~out = sym_2 + 5

上面语句的完整的R1CS如下:【2】

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编成QAP

拉格朗日插值

学过数值分析的应该很容易理解，对于一列坐标：(x0,y0),(x1,y1)...(xi,yi),可以通过拉格朗日插值，找到一个多项式，它通过这个坐标序列里的每一个点。具体的方法是：

对于（x0,y0), 我们找到一个多项式，在x1,x2....xi处，y1,y2,..yi均为零。这样的多项式很容易找，比如，下面就是一个例子：

y= (x-x1)(x-x2)...(x-xi)

举个例子，比如有3个点：(1, 3), (2, 2) 和(3, 4)。

- 首先我们找到通过(1, 3), (2, 0)和 (3, 0)的多项式。

- 其次我们找到通过(1, 0), (2, 2)和 (3, 0)的多项式。

- 再次我们找到通过(1, 0), (2, 0)和 (3, 4)的多项式。

- 最后，我们把上面得到的多项式加起来就是通过这三个点的多项式

我们用拉格朗日插值来变换上面的【2】

程序如下

#Assumes vec[0] = p(1), vec[1] = p(2), etc, tries to find p,

#expresses result as [deg 0 coeff, deg 1 coeff...]

def lagrange_interp(vec):

    o=[]

    for i in range (len(vec)):

        o=add_polys(o, mk_singleton(i+1, vec[i],len(vec)))

    for i in range(len(vec)):

        assert abs(eval_poly(o, i+1)-vec[i]<10**-10), (o, eval_poly(o, i+1), i+1)

    return o

def transpose(matrix):

    return list(map(list,zip(*matrix)))

#A, B, C = matrices of m vectors of length n, where for each

#0 <= i < m, we want to satisfy A[i] * B[i] - C[i] = 0

def r1cs_to_qap(A,B,C):

    A, B, C=transpose(A), transpose(B), transpose(C)

    new_A=[lagrange_interp(a) for a in A]

    new_B=[lagrange_interp(b) for b in B]

    new_C=[lagrange_interp(c) for c in C]

    Z=[1]

    for i in range(1,len(A[0])+1):

        Z=multiply_polys(Z, [-i,1])

    return(new_A, new_B, new_C, Z)

結果如下

A 多项式

[-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 多项式

[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 多项式

[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]