V神对QAP深入浅出的分析二

本文翻译自V神的Medium文章：二次计算方程：从0到1，详细讲解了QAP，并给出了一个程序实现，本文是下半部分，介绍了把计算转化为R1CS的过程。zcash官方博客对QAP这部分讲解的比较粗糙，V神的这篇文章是个很好的补充。友情提示：本文偏技术化，适合对技术非常感兴趣的同学阅读。
(本文授权BH好文好报群摘编、转载以及相关转授权推文行为)

上半部分介绍了如何把一个计算程序转化为R1CS，下面来看从R1CS转化成QAP形式。

R1CS到QAP

下一步就是把R1CS转化为QAP形式了，他们的底层逻辑是一样的，只是QAP用的多项式形式而不是向量点乘。我们这么做，我们把上面的三组(每组四个向量，每个向量长度为6)向量形式转化为六组(每组3个3次的多项式)多项式的形式，这些多项式在每个x坐标的结果代表一种约束。也就是说，如果我们计算多项式在x=1的结果，那么我们就得到我们的第一组向量，如果我们计算多项式在x=2的结果，我们就得到第二组向量，以此类推。

我们可以通过拉格朗日差值来完成这种转换。拉格朗日差值算法可以解决这类问题：如果你有一组点(类似(x,y)这种坐标点), 那么做在这些点位置进行拉格朗日差值，将会得到一个经过这些点的多项式。我们把这个问题拆解开来看：对于每个x坐标，我们可以创建一个多项式，使得它满足当前x对应的y坐标是目标y，而其他位置对应的y是0；然后我们把这些多项式相加就得到我们想要的多项式了。

我们来举个例子，假设我们想得到一个多项式经过(1, 3), (2, 2)和(3, 4)。我们从构造一个经过(1, 3),(2, 0)和(3, 0)的多项式开始。很明显，构造一个粘着x=1位置并且其他位置是0的多项式，可以这么做：

(x - 2) *( x - 3)

就像这样：

1_wsBN9VA71EXm2L4EV-hwcw.png

现在我们只需要把把它扩大一下，使得它在x=1的高度是正确的:

（x-2） * (x-3) * 3/( (1-2) * (1-3) )

于是，我们得到
1.5 * x^2 + 7.5*x + 9

1_8agIwBEX5YJ1HyZ4K5r5Gw.png

然后我们在对另外两个点也做相似的操作，只是我们需要分别调整"粘着"x=2和x=3。最后我们把三个多项式相加，得到：
1.5*x^2 + 5.5*x + 7

1_kAn6O2BcDOsMgSwRPvRfZA.png

这正是我们想要的坐标位置(满足了经过(1, 3), (2, 2)和(3, 4))。上面描述的算法时间复杂度是O(n^3)，因为共有n个点，每个点需要O(n^2)的时间；如果我们再稍微优化一下，可以缩减至O(n^2)，如果再深入思考下，使用快速傅立叶变换，那么还可以更快——这对于实际应用中的zk-SNARKs来说，是一个非常关键的优化策略，实际应用中经常有数千个门。

现在，我们使用拉格朗日差值算法来变换R1CS。我们首先从取出每个a向量的第一个元素，然后对他们做拉格朗日差值得到一个多样式(使得这个多项式在i的位置的值即是第i个a向量的第一个元素值)，对于b和c向量的第一个元素也做这种操作，然后对第二个元素也做这些操作，然后是第三个元素，依次到第六个元素。为了方便，我把答案提供出来：

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]

系数是按照阶次依次上升排列的，所以上面的第一个多项式实际上是:
0.833 * x^3 - 5*x^2 + 9.166*x - 5
这组多项式(还有一个Z多项式，下面会解释)构成了这种特殊QAP的参数。注意，到目前为止上面所有的工作，对于每个你要用zk-SNARKs去验证的函数来说，只需要执行依次；一旦QAP的参数生成出来，后面就可以重复利用了。

我们计算一下所有这些多项式在x=1位置的值。比较简单，只需要把多项式的各个参数相加就可以了(因为对于任意k来说，1^k = 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

你瞧，我们刚好得到了和第一个门完全一致的三个向量。

检验一下这个QAP

干嘛要做这种"疯狂的"转化？答案是，我们不再需要一个个去检验R1CS的每个约束了，我们现在可以一次性检查完所有的约束，只需要像下面一样做点乘就可以了：

1_QD2EfVsbNguEXrjKJwNVMg.png

因为做点乘仅仅是对多项式做一些列的加法和乘法，结果也是一个多项式。结果多项式在每个x坐标上的值代表一个逻辑门，如果它等于0，就代表所有的检查都通过了；如果结果多项式哪怕在一个x坐标上不等于0， 就代表对应的逻辑门是不一致的。

注意这个结果多项式本身不一定是0，实际上，大部分情况下都不是；它可能在“与逻辑门相对应的点”以外的点等于其他值，只要它在与逻辑门相对应的点上等于0就可以了。为了检查正确性，我们不需要真正的对于每个逻辑门对应的点上计算多项式
t = A·s * B·s - C·s
我们用另外一个多项式Z除t，如果能整除，也就是说t/Z没有余数，就代表通过验证了。

Z是这样定义的(x-1)*(x-2)*(x-3)...——这是个非常简单的多项式，它在逻辑门对应的点上等于0。这是一个简单的代码事实，任何一个多项式，如果在这些点上的值等于0，那么它一定包含这么一个最小的因式。如此就简单了。

现在，我们对上面的多项式来做下上面的点乘，对个检查。首先，这些临时的多项式：

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]

然后，计算A·s * B·s - C·s：

t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

我们最小的多项式Z = (x - 1) * (x - 2) * (x - 3) * (x - 4)

Z = [24, -50, 35, -10, 1]

如果我们用上面的结果除以Z，得到：

h = t / Z = [-3.666, 17.055, -3.444]

没有余数。

所以我们就有了QAP的解。如果我们尝试让某个R1CS的解中的变量值搞错，比如，把最后一个值30改成31，那么我们得到的t多项式将无法通过其中一项检查(在这个例子中，x=3的结果将会是-1，而不是0),从而t不会是Z的倍数，也就是说，t/Z将会得到余数[-5.0， 8.833， -4.5， 0.666]

注意，上面的例子是简化后的。在实际应用中，进行加减乘除运算的不会是常规的数字，而是有限域内的元素——那是一种奇特的、完备的运算方式，所以所有我们知道的代数规律还都可以应用，只不过结果值还是有限集合里的元素，当固定了大小n之后，里面的元素通常都是在0到n-1之间的数字。例如，如果n = 13 ,那么1/2=7(另外，27=1),35 = 2，类似这种。使用有限域运算，我们无需担心小数去整运算产生的误差，而且可以让整个系统可以和双曲线一起良好工作，这对于zk-SARK机制的其他的部分以及zk-SNARK的安全都是很必要的。

早赞声明：为方便早赞、避免乱赞，“BH好文好报群”为点赞者、写作者牵线搭桥，实行“先审后赞、定时发表”的规则，也让作品脱颖而出、速登热门！加群微信：we01230123（天平）。