这个知识点已经是很久之前看的了，现在补一篇blog。还有就是这一篇文章并不算零知识证明的科普，如果是入门的话，可以参考，但如果对零知识证明一无所知，建议先看看网上其它文章了解一下。
当时也是含泪看完V神的blog 
概述
首先，zk-SNARKs不能直接应用于任何计算问题；相反，你必须将问题转换成正确的“形式”，以便问题能够发挥作用。而这种形式称为“二次算术程序”(quadratic arithmetic program，QAP)，但将函数代码转化为这种形式是很困难的。在转换过程中，还可以运行另一个进程，因此，如果有输入，可以创建相应的解决方案，也就是QAP的witness。在此之后，为这个witness创建一个真正的零知识证明以及也是一个非常复杂的过程，除此之外，还需要一个单独的过程来验证别人传给你的证明。
假设：证明你知道方程：$x^3+x+5=35$，这个答案是3，将其写成代码形式：
def qeval(x):
y = x**3
return x + y + 5Flattening
在这个过程中，可以将可能包含任意复杂语句和表达式的原始代码转换为具有两种形式的语句序列：$x=y$($y$可以使变量或者数字)和$x=y \ (op) \ z$($op$是$+，-，*，/$，$y$和$z$可以是变量、数字或子表达式)。也可以将其看做电路中的逻辑门，最后的结果如下：
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)$，以及R1CS的解$s$，并且满足方程$s.a*s.b-s.c=0$这里的$.$代表点积。也就是将两个向量$s\ and\ a$对应位置上的两个值相乘，最后再求和得到的值即为两向量的点积$s.a$，也称之为内积。
例如，下面就是一个R1CS：
现在，结合Flattening的四个逻辑门，每一个逻辑门都有一个约束(实际上，在不同场景下面临的约束可能更多)，接下来将一步步将其转化为R1CS。
首先，提供以下变量映射：
'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'
这里的$x,\ y,\ sym_{-}1,\ sym_{-}2,\ ~out$均与Flattening中的对应，而$~one$则代表着常量1的作用，下面就可以将每一个门都转化成向量形式。
第一个门：
a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]
结合变量映射，可以发现它完全就是 sym_1 = x * x 的另一种表示。
在检查它是否满足方程，因为点乘的缘故，也很容易检查3 * 3 - 9 = 0，也是满足的。
同样的方式，接下来转化剩余三个门。
第二个门：
a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]
这里检查的是y = sym_1 * x。
第三个门：
a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 0, 0, 0, 1]
这里检查的是sym_2 = y + x。
第四个门：
a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]
这里检查的是~out = sym_2 + 5。图1中取的一组$a, b, c$便是与第四个门一样(但它们并没有任何必然关系)。
我们的例子中共有四个约束，witness则是对所有变量的赋值，包括输入、输出以及中间变量：
[1, 3, 35, 9, 27, 30]
将完整的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 to QAP
接下来这一步将把R1CS转化为QAP，即将三个4组长度为6的向量转化为6组度(即多项式的最高次数)为3的多项式。每一个多项式在$x$处的评估代表着一个约束。也就是说，可以在$x=1$处评估多项式，得到第一组向量；在$x=2$处评估多项式，得到第二组向量，以此类推。
接下来通过拉格朗日插值来变换R1CS。
以$a$向量为例，一共4条R1CS，也就是说需要在$x\ =\ 1,\ 2,\ 3,\ 4$处评估多项式得到相同的R1CS。取出四个向量的第一个元素，组成(1,0), (2,0), (3,0), (4,5)四个点，通过这四个点进行拉格朗日插值可以得出多项式：$0.83x^3\ -\ 5x^2\ +\ 9.1x\ -\ 5$，
由此，可以得到A多项式的第一个系数向量(所有的系数按升序排列)：
[-5.0, 9.166, -5.0, 0.833]
同样的方法，转化所有R1CS，可以得到如下结果：
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$进行评估，将得到以下结果：
A results at x=1
0
1
0
0
0
0
B results at x=1
0
1
0
0
0
0
C results at x=1
0
0
0
1
0
0
可以发现，这与三个逻辑门的R1CS完全一致。
Checking the QAP
为什么我们要进行这么多如此复杂的变换呢？
如果仔细的话能够发现，现在可以通过对多项式进行点积检查来同时检查所有约束，而不是单独检查 R1CS 中的约束。
此时，再进行点积检查是一系列的多项式加法和乘法，其结果也将是一个多项式。如果生成的多项式在每一个$x$($x\ =\ 1,\ 2,\ 3,\ 4$)的评估下均为0，则检查通过。如果出现了任何一个非零值，则代表逻辑门的输入和输出是不一致的。
实际上，在大部分情况下，也就是在“与逻辑门相对应的点” 以外的点，多项式的值并不是0。所以，并不需要计算每一个对应点的$t\ =\ (A\ ·\ s)\ *\ (B\ ·\ s)\ -\ (C\ ·\ s)$的值，只需要增加一个检查多项式$Z(x)\ =\ (x\ -\ 1)(x\ -\ 2)(x\ -\ 3)(x\ -\ 4)$，当$t\ /\ Z(x)$没有余数，即其可以整除，则验证通过。
通过此方法可以很大程度上减少开销。
换一种方式来解释，我们要检查$t$在逻辑门对应点出的值为0，也就是说$t$在$x\ =\ 1,\ 2,\ 3,\ 4$处有零点，现在问题就转化为代数问题了，要证明$t$在$x\ =\ 1,\ 2,\ 3,\ 4$处有零点，也就是要证明存在一个多项式$H(x)$，使得$t\ =\ H(x)\ *\ Z(x)$，也就是说$t$可以被$Z(x)$整除。
现在，我们对多项式进行点积检查，首先，中间多项式：
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]
由此，可以得出$t$：
t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]
现在，$Z(x)$：
Z = [24, -50, 35, -10, 1]
将上面的结果除$Z(x)$：
H = t / Z = [-3.666, 17.055, -3.444]
并没有任何余数，也就是说检查通过，这样我们就有了QAP的解。
到这一步ZK-SNARK的基本步骤已经结束了，整个过程是非常严密的，如果我们尝试伪造 R1CS 解决方案中的任何变量，最终得到一个
未能通过其中一项检查的多项式$t$。
参考资料
https://vitalik.ca/general/2016/12/10/qap.html
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649