上节中介绍了Alice如何利用QAP将证明转化为一种多项式描述的验证方法，本节中介绍Alice如何向Bob展示一个简短的证明，证明其拥有一个合法的QAP，利用到了Parno, Howell, Gentry and Raykova在2013年提出的匹诺曹协议
这里可以结合R1CS和QAP的文章$[2]$来看
根据上一节提到的内容，如果Alice知道一个合法的QAP的赋值，则意味着存在一个多项式H，满足$P=H\cdot T$，换句话说，对于任意的$s\in F_p$，都有$P(s)=H(s)\cdot T(s)$，如果Alice不知道一组合法的赋值，则会导致得到的P不会被T整除，这意味着对于任意阶数至多为$d-2$的多项式$H$而言，$P$与$L,R,O,H$都是不同的多项式（这里$P$至多为$2(d-1)$阶，$L,R,O$至多为$d-1$阶，$H$至多为$d-2$阶）
接下来就可以用之前提到的Schwartz-Zippel引理$[3]$，根据Schwartz-Zippel引理，两个阶数至多为$2d$的不同的多项式至多在$2d$个点$s\in F_p$上相等，因此若选择的$p$很大，远大于$2d$，则对于随机选择的点$s\in F_p$，使得等式$P(s)=H(s)\cdot T(s)$成立的概率是极小的
因此，将之前几节的内容简单整理一下，拟定一个简单的协议来检查Alice是否有一个合法的赋值
- Alice选择四个阶至多为$d$的多项式$L,R,O,H$
- Bob选择一个随机的点$s\in_R F_p$，计算$E(T(s))$
- 根据之前提到的方案，Alice将这四个多项式在点$s$处的盲评估发送给Bob，也即Alice向Bob发送$E(L(s)),E(R(s)),E(O(s)),E(H(s))$
- Bob检查等式$E[L(s)\cdot R(s)-O(s)]=E[T(s)\cdot H(s)]$在点$s$处是否成立，若成立则接受Alice，否则拒绝Alice
若Alice没有合法的赋值，则其最终使用的多项式会导致方程无法全等，于是在多数随机选择的点$s$处均不成立，综上，若Alice不知道合法的赋值，则协议可以确保Bob以极高的概率拒绝
根据第2-4节介绍的内容，Alice可以也必须在不知道s的情况下选择他的多项式，从而上述协议可以完成
确保Alice根据赋值选择多项式
首先需要明确一个点，如果Alice不知道一个合法的赋值，仅代表着她不能找到一个多项式$P$，使得$P$是由$L,R,O$生成的，而并不代表她不能找到任意阶至多为$d$的多项式$L,R,O,H$，满足$L\cdot R - O =T\cdot H$
换句话说，Alice只是不知道由赋值$(c_1,...,c_m)$生成的多项式$L,R,O$，但不意味着她没有能力找到其他的多项式来满足方程$L\cdot R - O =T\cdot H$，因为在第四节中，我们只确保了Alice生成了阶数正确的多项式$L,R,O$，但并没有确保这些多项式是由赋值$(c_1,...,c_m)$生成的，接下来看如何解决这个问题
令一个新的多项式如下
$$ F=L+X^{d+1}\cdot R + X^{2(d+1)} \cdot O $$
这里将$R$乘$X^{d+1}$和$O$乘$X^{2(d+1)}$的目的是让$L,R,O$的系数在F中不会混淆，从而得到了$F$中$1,X,...,X^d$的项对应的系数刚好是$L$中的系数，$X^{d+1},...,X^{2d+1}$的项的系数是$R$的系数，最后$X^{2(d+1)},...,X^{3d+2}$的项的系数是$O$的系数
接下来利用类似的方法来把QAP定义中的多项式合并起来，对于每个$i\in\{1,2,...,m\}$，定义多项式$F_i$，其前$d+1$个系数来自$L_i$，中间$d+1$个系数来自$R_i$，最后$d+1$个系数来自$O_i$，也即定义
$$ F_i=L_i+X^{d+1}\cdot R_i + X^{2(d+1)} \cdot O_i $$
当对两个F_i求和时，$L_i$,$R_i$,$O_i$也会对应的求和，也即有
$$ F_1+F_2=(L_1+L_2)+X^{d+1}\cdot (R_1+R_2) + X^{2(d+1)} \cdot (O_1+O_2) $$
更一般地，对于赋值$(c_1,...,c_m)$，假设有$F=\sum^m_{i=1}c_i\cdot F_i$，对于同样的赋值$(c_1,...,c_m)$，和之前一样，有$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$
因此，若$F$是$F_i$的一个线性组合，则意味着$L,R,O$实际上是由赋值$(c_1,...,c_m)$生成的，此时问题就转化为了Bob要求Alice证明$F$是$F_i$的线性组合
这里可以用之前提到的可验证的求值协议完成，比如Bob随机选择一个$\beta \in F^*_p$，然后计算同态隐藏$E[\beta \cdot F_1(s)],E[\beta \cdot F_2(s)],...,E[\beta \cdot F_m(s)]$并发送给Alice，利用之前提到的d-KCA，Alice需要返回$E[\beta \cdot F(s)]$，若Bob验证通过，则表明Alice知道如何将$F$表示为$F_i$的线性组合
加入零知识-隐藏赋值
在zk-SNARKs中，Alice不希望Bob知道他的赋值，也即Alice需要隐藏她的赋值的所有信息，但是$E[L(s)],E[R(s)],E[O(s)],E[H(s)]$实际上还是会提供一些关于复制的信息
比如，给定另一组合法的赋值$(c_1',...,c_m')$，Bob可以计算出对应的$L',R',O',H'$及其隐藏值$E[L'(s)],E[R'(s)],E[O'(s)],E[H'(s)]$，如果这些值和这些跟Alice的隐藏值不一样，则其可以推断赋值$(c_1',...,c_m')$不是Alice的赋值
为了避免出现这种情况，Alice需要为每个多项式增加一个随机$T$偏移来达到隐藏她的赋值的目的，也即随机选择$\delta_1,\delta_2,\delta_3\in F^*_p$，并定义$L_z=L+\delta_1\cdot T,R_z=R+\delta_2 \cdot T,,O_z=O+\delta_3 \cdot T$，然后根据之前提到的$L\cdot R - O =T\cdot H$，计算$L_z\cdot R_z-O_z$
$$ \begin{aligned} L_z\cdot R_z-O_z&=(L+\delta_1\cdot T)\cdot (R+\delta_2\cdot T) - O-\delta_3\cdot T\\ &=L\cdot R - O +L \cdot \delta _2 \cdot T+R \cdot \delta_1 \cdot T +\delta_1\cdot\delta_2 \cdot T^2 -\delta_3 \cdot T\\ &=T \cdot (H +L \cdot \delta_2+R \cdot\delta_1 +\delta_1 \cdot \delta_2 \cdot T -\delta_3) \end{aligned} $$
不难发现，T也是可以整除$L_z\cdot R_z-O_z$的，此时令$H_z=H +L \cdot \delta_2+R \cdot\delta_1 +\delta_1 \cdot \delta_2 \cdot T -\delta_3$，从而有$L_z\cdot R_z-O_z=T \cdot H_z$，从而Alice利用多项式$L_z,R_z,O_z,H_z$也可以使得Bob接受，但是Bob不会推断出Alice的赋值，因为除了在那个特定的点s外，其余的s均有$T(s)\neq 0$，因此不会泄露关于分配的信息（因为$T(s)\neq 0$，$\delta_1,\delta_2,\delta_3$是随机的，因此$L_z,R_z,O_z$在Bob看来也是一个随机的值，从而不会泄露关于$L(s),R(s),O(s)$的信息）
小结
目前为止，匹诺曹协议的框架已经介绍完毕了，Alice可以在不需要泄露赋值的情况下使得Bob相信她拥有一个使得QAP合法的赋值
不过为了完全实现zk-SNARKs，还需要解决两个问题
- Bob需要一个支持加法和乘法的同态隐藏，因为验证过程中需要利用$E[H(s)]$和$E[T(s)]$计算$E[H(s)\cdot T(s)]$，但是之前的内容介绍的同态隐藏仅支持加法或线性组合
- 最后的目标需要实现的是Alice仅发送消息的非交互式证明，也即目前为止zk-SNARKs中的N还没有实现，此外这个证明是可以公开验证的，意思是看到Alice消息的任何一个参与方都可以完成验证，而不仅仅是Bob
下一节处理这个两个问题
本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正
参考文章
$[1]$Explaining SNARKs Part VI: The Pinocchio Protocol - electriccoin-blog
$[2]$零知识证明（13）：R1CS与QAP - Snowolf
$[3]$Schwartz–Zippel lemma - Wikipedia