导语
在前一篇中我们介绍了零知识证明核心工具的椭圆曲线和同态隐藏。本文我们将继续介绍零知识证明核心工具中的多项式规约过程。
核心数学工具
多项式规约过程
上一小节，我们通过同态隐藏，得到了一个非交互的多项式盲验证协议，算是解决了零知识证明中最核心的问题。接下来，我们在阿维·威格森的NP问题可零知识证明化理论和NP问题可相互规约理论[6]的指导下，再通过一些列数学工具，来解决普通程序转化为多项式的问题。
1、计算电路
我们以这样一段程序为例：
function calc(w, a, b)if w thenreturn a × belsereturn a + bend ifend function
首先我们把该程序翻译成函数表达式：
思考一下，其实我们可以用这种方法表达任何形式的有限程序。
执行calc(1, 3, 2)和对f (1, 3, 2)求值都可以得到6。如果执行calc(0, 3, 2)和f(0,3,2)能够得到 5。
对于我们的证明系统，需要我们证明的是,对于表达式f(w,a,b)，输入为 (1, 4, 2) 时输出为 8，换句话说，Alice要证明她知道(w,a,b)的值，使得多项式：
w(a · b)+(1-w)(a+b) = v, w ∈ {0,1}
我们把该函数展开一下：
w(a · b-a-b) + a + b= v
这样我们就可以把所有的复杂计算拍平成计算电路：
2、门电路求解
接下来，我们要往多项式上靠了，具体思想是这样的：
为了证明单个计算的正确性，我们就必须首先确保所提供的操作数的输出（结果）的正确性。对于每一个门电路，类似得我们也可以将其表示为一个运算多项式
l(x) operator r(x) = o(x)
在一些选定的取值a处的运算:
•l(x) — 表示（运算结果为）左操作数
•r(x) — 表示（运算结果为）右操作数
•o(x) — 表示运算结果（输出）
因而在计算过程中如果操作数和结果都可以用多项式的形式正确地表示出来，那么l(a) operator r(a) = o(a)就能够成立。也就是说假如输出多项式o(x)所代表的值是由运算符在操作数多项式l(x)和r(x)上进行乘法运算得出的正确结果，那么我们把输出多项式o(x)放到等式的左边就能够得到：
l(a) operator r(a) – o(a) = 0
那么只要多项式是有效的，运算多项式就一定有一个根a。因此，根据前面的基础这个多项式里面一定包含因式(x-a) ，这就是我们要使用证明的目标多项式，即t(x) = x – a。
例如，我们来看一个运算：3×2=6
可以用一个简单的多项式表示它：l(x) = 3x, r(x) = 2x, o(x) = 6x，取a=1进行计算，即l(1) = 3；r(1) = 2；o(1) = 6。
然后我们可以得到p(x) = l(x) × r(x) – o(x)的图像：
l(x) × r(x) = o(x)
3x × 2x =6x
6x² -6x =0
p(x) = 6x² -6x
现在，我们已经把一个乘法门计算，转化成了对p(x)系数的求解。如果我们就这样一个一个门电路求解过去也是可以的，但是这样做显然效率不高。
所以，为了能够高效的对复杂的算数电路求解，和上面的曲线叠加思路一致，每一个门电路其实是互不干扰的一条曲线，如果我们把所有的门电路叠加到一起，形成一条新的曲线，这条曲线在每一个门电路求解处，仍然是互不干扰的。
这样，我们就可以构造出一条曲线，通过对这条曲线的多项式系数的求解，一次完成所有门电路的计算。为了构造这样一条曲线，我们引入了R1CS。
3、R1CS
我们把每一个门电路表示为等价的向量点积形式，这个过程成为R1CS（rank-1 constraint system）。
对每个门电路，我们定义一组向量
和
一个解向量(全部输入的向量)，使得
每一个向量都包含了所有门电路的输入输出维度，
为了让加法门也能用同样的方式表达，我们增加一个虚拟的变量one，向量变成
对应到第一个门:
（s向量的解代表了我们知道所有满足门电路约束条件的输入、输出和中间过程，也就等价于我们知道calc函数的所有逻辑以及输入和对应的输出）
把s，a，b和c代入s . a * s . b – s . c = 0，得到
其中⋅表示向量内积，∗表示算数乘法。即这个向量表达跟第一个门是完全等价的，那么此时能够使等式成立的s向量，就是这个门电路的解。
同理我们可以计算第二个门，第三个门……
我们最终要找的s向量，是可以满足所有R1CS的解。
好了，到这里，我们把一个计算式拍平成为门电路，接着又通过R1CS把门电路“编码”成向量的表达方式。
接下来是最重要的一步，把向量表达式表示为多项式，然后一次找到满足所有约束的s向量。这个过程称为QAP（Quadratic Arithmetic Programs）。
4、QAP
QAP的第一步，是把我们上以一节得到的
向量组中的每一个维度都表示成一个多项式的结果：
针对门 1/门 2/门 3/门 4/门 5/门 6，我们可以分别令x=1，x=2，x=3，x=4，x=5，x=6。对于不同门相同向量维度取其R1CS的值。比如说：门 1 的
的第三个维度取值是1，那么
门 2 的的第三个维度取值也是1，那么么
门 3 的第三个维度取值是0，那么
依次类推，我们可以得到
这个函数在x=1，x=2，x=3，x=4，x=5，x=6处的6个点。
知道一条曲线上的多个点，如何确定这条曲线？这就要用到我们大学高数里的知识——拉格朗日插值法了。小伙伴可以通过这个工具(https://zh.planetcalc.com/8692/)来插值出一个多项式。
第二步，在我们获得了
的这些多项式后，代入
向量，得到多项式：
而前述的过程表明，在x=1，x=2，x=3，x=4，x=5，x=6时，
所以可以得出一个确定可整除的多项式
第三步，我们可以根据多项式除法，得到h(x)。
至此，我们把一个分支条件的普通计算程序，转化成了一个多项式系数验证问题，接下来，我们就可以通过3.2节介绍的同态隐藏算法来构造通用零知识证明的非交互协议了。
纵观整个多项式规约过程，包含了两点数学思想：1、约束求解，2、超维，从中我们可以略微的窥探到数学家们脑子里的思维武器是怎么配合使用的。
与上篇文章一样， 本篇文章强度依然很大，能坚持学习到这里已经非常不错了。 本篇主要介绍了零知识证明核心数学工具的最后一个——多项式规约过程。下一篇文章我们开始介绍零知识证明协议——匹诺曹协议和Groth16。
本文参考文献
[6] Hartmanis J. Computers and intractability: a guide to the theory of np-completeness (michael r. garey and david s. johnson)[J]. Siam Review, 1982, 24(1): 90.
原文始发于微信公众号（Numen Cyber Labs）：Numen | 零知识证明引论Part 3
