本文的内容来自于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]
A.s：
1 1*（-5）+3×8 + 35*0 + 9*(-6)+ 27 *4 + 30*(-1)=43
2 1*（9.166）+3×(-11.333) + 35*0 + 9*(9.5)+ 27 *(-7) + 30*(1.833)=-73.333
3 ...
4 ...
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]
附录
定义
对某个多项式函数，已知有给定的k+ 1个取值点：
其中
对应着自变量的位置，而
对应着函数在这个位置的取值。
假设任意两个不同的xj都互不相同，那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为：
其中每个
为拉格朗日基本多项式（或称插值基函数），其表达式为：
拉格朗日基本多项式的特点是在
上取值为1，在其它的点
上取值为0。
证明
对于给定的k+1个点：
，拉格朗日插值法的思路是找到一个在一点
取值为1，而在其他点取值都是0的多项式
。这样，多项式
在点
取值为
，而在其他点取值都是0。而多项式
就可以满足
在其它点取值为0的多项式容易找到，例如：
它在点
取值为：
。由于已经假定
两两互不相同，因此上面的取值不等于0。于是，将多项式除以这个取值，就得到一个满足“在
取值为1，而在其他点取值都是0的多项式”：
这就是拉格朗日基本多项式。
https://www.cnblogs.com/ECJTUACM-873284962/p/6833391.html
https://blog.csdn.net/qq_35505348/article/details/81560451
