之前的文章主要围绕处理和验证多项式的协议展开，接下来介绍一个将想要证明和验证的语句编译成多项式的协议，这个方式最早由Lund, Fortnow, Karloff and Nisan提出$[LFN92]$
之前介绍了一种处理和验证多项式的协议，接下来介绍一个将想要证明和验证的语句编译成多项式的协议，这个方式最早由Lund, Fortnow, Karloff and Nisan提出$[LFN92]$
2013年由Gennaro, Gentry, Parno and Raykova定义了另一种转换方式，称为QAP（Quadratic Arithmetic Program），QAP已成为现代zk-SNARKs的基础，Zcash中也有使用
算术电路
举个例子，比如Alice希望向Bob证明$c_1,c_2,c_3\in F_p$，且满足$(c_1\cdot c_2)\cdot(c_1+c_3)=7$，首先需要将$c_1,c_2,c_3$转换为算术电路，如下
最下面代表电路的输入，最上面代表电路的输出，这里有一些需要注意的点
- 对于连接的多条导线，仍然将其考虑为一条（如$c_1$有两条线连接到了乘法门和加法门，将其统一考虑为一条导线$w_1$）
- 将乘法门视为有两个输入的门，以左输入和右输入来区分
- 仅标记乘法门（如图中的$g_1$和$g_2$），不标记加法门及其输出，将加法门的输出直接作为乘法门的输入（如图中直接将$w_1$和$w_3$作为$g_2$乘法门的右输入）
此外，称电路的合法赋值为将值赋值给对应的导线，上图中导线$w_4$的值为$c_4=c_1\cdot c_2$，$w_5$的值为$c_5=c_4\cdot (c_1+c_3)$
根据之前提到的Alice希望向Bob证明$c_1,c_2,c_3\in F_p$，且满足$(c_1\cdot c_2)\cdot(c_1+c_3)=7$，此时转化为了Alice要向Bob证明一组赋值$(c_1,c_2,c_3,c_4,c_5)$，满足$c_5=7$，下一步是使用QAP将此语句转换为关于多项式的语句
归约至QAP
接下来需要做的，首先是将每个乘法门与域元素关联起来，比如$g_1$关联至$1\in F_p$，$g_2$关联至$2\in F_p$，则此时称点$\{1,2\}$为目标点
然后定义三组多项式
- 左导线多项式$L_1,...,L_5$
- 右导线多项式$R_1,...,R_5$
- 输出导线多项式$O_1,...,O_5$
这么定义的想法是：除非目标点对应的乘法门涉及了多项式，否则多项式在该目标点上通常为0
根据上面那个图举个例子，例如对于乘法门$g_1$及其相关联的左右输入导线和输出导线，定义$L_1=R_2=O_4=2-X$，此时这个多项式在$X=1$处的值为1，而在$X=2$处的值为0，也即在$g_1$处的值为1，而在$g_2$处的值为0
同理可以对乘法门$g_2$及其相关联的左右输入导线和输出导线，定义$L_4=R_1=R_3=O_5=X-1$，此时在$g_1$处的值为0，而在$g_2$处的值为1
然后对于上述三组多项式中剩余的多项式均定义为零多项式$0$
然后对于一组给定的值$(c_1,...,c_5)$，利用这一组值作为系数来定义左和、右和、输出和三个多项式
- $L=\sum^5_{i=1}c_i\cdot L_i$
- $R=\sum^5_{i=1}c_i\cdot R_i$
- $O=\sum^5_{i=1}c_i\cdot O_i$
然后定义多项式$P=L\cdot R -O$
重点来了，当且仅当$P$在所有目标点上消失（vanish）时，称$(c_1,...,c_5)$是一组有效的赋值（消失的意思是能被某个多项式整除）
不理解没关系，结合图来讲会清楚一些
有了$L,R,O,P$的定义，接下来用$(c_1,...,c_5)$给这四组多项式赋值
根据上面这个电路图，在点1时，$L$中所有多项式除了$L_1$外都是零，因此有$L(1)=c_1\cdot L_1=c_1$，同理有$R(1)=c_2,O(1)=c_4$，然后根据$P=L\cdot R -O$，有$P(1)=L(1) \cdot R(1)-O(1)=c_1\cdot c_2-c_4$
同理可得，$L(2)=c_4,R(2)=c_1+c_3,O(2)=c_5,P(2)=c_4\cdot(c_1+c_3)-c_5$
然后利用一个代数知识：对于多项式$P$和域上一个点$a\in F_p$，$P(a)=0$当且仅当多项式$X-a$可以整除P，也即$P=(X-a)\cdot H$，其中$H$也是一个多项式
根据上面的，定义目标多项式为$T(X)=(X-1)(X-2)$，当且仅当$T$可以整除$P$时，称$(c_1,...,c_5)$是一组有效的赋值，也就是前面提到的$P$在所有目标点上消失
总结一下，定义QAP如下
- QAP：一个QAP $Q$，其阶为$d$，大小为$m$，包含三组多项式$L_1,...,L_m,R_1,...,R_m,O_1,...,O_m$和阶为$d$的目标多项式$T$
定义左和、右和、输出和三个多项式
- $L=\sum^m_{i=1}c_i\cdot L_i$
- $R=\sum^m_{i=1}c_i\cdot R_i$
- $O=\sum^m_{i=1}c_i\cdot O_i$
然后定义多项式$P=L\cdot R -O$
- 称赋值$(c_1,...,c_m)$满足Q当且仅当多项式$T$可以整除多项式$P$
根据上面所说的，之前Alice需要向Bob证明其知道$c_1,c_2,c_3\in F_p$，且满足$(c_1\cdot c_2)\cdot(c_1+c_3)=7$，利用QAP就转化为了Alice需要证明她知道一组赋值$(c_1,c_2,c_3,c_4,c_5)$，满足$c_5=7$
以上面那个图为例子，看看QAP如何计算的
不妨设$c_1=1,c_2=1,c_3=6$，此时满足$(c_1\cdot c_2)\cdot(c_1+c_3)=7$，且有$c_5=7$，根据图中的电路，可以得到$c_4=c_1\cdot c_2$，因此这组赋值为$(c_1,c_2,c_3,c_4,c_5)=(1,1,6,1,7)$
根据前面的内容，我们有$L_1=R_2=O_4=2-X$，$L_4=R_1=R_3=O_5=X-1$，其余的和多项式为零，然后定义多项式$P=L\cdot R -O$
因此有
$$ \begin{aligned} &L=c_1(2-X)+c_4(X-1)\\ &R=c_1(X-1)+c_2(2-X)+c_3(X-1)\\ &O=c_4(2-X)+c_5(X-1) \end{aligned} $$
因此多项式$P$如下
$$ \begin{aligned}P&=L\cdot R -O=[c_1(2-X)+c_4(X-1)][c_1(X-1)+c_2(2-X)+c_3(X-1)]-c_4(2-X)-c_5(X-1)\\&=c_1(c_1+c_3)(2-X)(X-1)+c_4(c_1+c_3)(X-1)^2+c_1c_2(2-X)^2+c_2c_4(X-1)(2-X)-c_4(2-X)-c_5(X-1)\end{aligned} $$
令目标多项式为$T(X)=(X-1)(X-2)$，然后将$(c_1,c_2,c_3,c_4,c_5)=(1,1,6,1,7)$带入，得到
$$ \begin{aligned} P&=1*(1+6)(2-X)(X-1)+1*(1+6)(X-1)^2+1*1*(2-X)^2+1*1(X-1)(2-X)-1*(2-X)-7*(X-1)\\ &=7(2-X)(X-1)+7(X-1)^2+(2-X)^2-(2-X)-7(X-1)\\ &=7(2-X)(X-1)+7(X-1)(X-2)+(2-X)(1-X)\\ &=-2(X-1)(X-2) \end{aligned} $$
显然有$P=T\cdot H$成立，此时$H=-2$（是一个零次多项式）
小结
本节主要介绍了一种将要证明与验证的语句转化成多项式验证的方式，再结合上前几节介绍的内容，我们可以在同态隐藏的方式下，将一个语句以多项式的方式进行验证
至此，zk-SNARKs已经介绍过半，接下来还差简短和零知识没有介绍，也即zk-SNARKs中的zk和S，在接下来的两篇文章中逐一介绍
本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正
参考文章
$[1]$Explaining SNARKs Part V: From Computations to Polynomials - electriccoin-blog