在前一篇文章中我展示了 Alice 向 Bob 证明的语句如何转换成等价的多项式形式，即二次运算程序(QAP)

本篇文章呈现的是 Alice 如何向 Bob 展示满足 QAP 的赋值，这会用到 Parno ,Howell，Gentry 和 Raykova 等人奠定的 Pinocchio 协议，先来回顾一下先前文章中对 QAP 的定义：

d 阶二次运算程序 Q 包含的多项式有
$L_1,....,L_m,R_1...R_m,O_1,....,O_m$ 以及目标 d 阶多项式 T ;
满足程序 Q 的赋值 $(c_1,...,c_m)$ 定义如下：
$L:= \sum_{i=1}^mc_i*L_i$
$R:= \sum_{i=1}^mc_i*R_i$
$O:= \sum_{i=1}^mc_i*O_i$
$P:=L*R-O$
可得目标多项式 T 整除 P

在前面的文章中提到，Alice 向 Bob 证明她拥有附带额外约束的满足 QAP 的赋值，例如 $c_m=7$ 。
这意味着基于上述定义的 $L,R,O,P$ ,存在多项式 $H$ 使得 $P=H*T$ ,更细化来说，对任何 $s\in\mathbb{F}_p$ ,都有$P(s)=H(s)*T(s)$

现在假设 Alice 没有满足条件的赋值，但她仍然可以通过某些不符合条件的 ${c_1,...,c_m}$ 来构建 $L,R,O,P$ ,以此可保证目标多项式 T 无法整除 P .
也就是说对于任何 d 阶多项式 H , P 和 H*T 是不同的多项式，而 P 和 H * T 的阶数最多为 2d 。

基于 Schwartz-Zippel 引理可知，两个最高阶数为 2d 的不同多项式在 $s\in\mathbb{F}_p$ 中最多有 2d 个相同点 。
因此，如果 p 比 2d 大，那么在域$\mathbb{F}_p$中随机选择 s ，使得 P(s)=H(s)*T(s) 的概率将会非常小。

下述为测试 Alice 是否拥有满足条件赋值的流程：

1. Alice 选择阶数最大为 d 的多项式 L,R,O,H
2. Bob 在域 $\mathbb{F}_p$ 中随机选择点 s，并计算 E(T(s))
3. Alice 向 Bob 发送各个多项式在 s 点的对应值，即E(L(s)),E(R(s)),E(O(s)),E(H(s)) .
4. Bob 检查 Alice 所发送的内容是否满足以下等式，即：$E(L(s)*R(s)-O(s))=E(T(s)*H(s))$

显而易见的是，如果 Alice 没有满足条件的赋值，那么上述等式不会成立，Bob 在这种情况下会有极高的概率拒绝。

最关键的一点在于， Alice 必须在不知道 s 的情况下选择多项式，但这个问题已经在之前的”可验证盲估协议“中得到过解决方案。

基于上述内容，将其转换成 Zk-SNARK 需要解决四个问题，本篇文章先处理其中的一个，另外三个在接下来的文章中会进行阐述。

确保 Alice 根据赋值选择多项式

1）如果 Alice 没有满足条件的赋值，这并不意味着她无法找到满足 L*R-O=T*H 的 d 阶多项式 L,R,O,H ，只是说 Alice 无法从赋值中得到 L,R 和 O ，之前的协议只是确保 Alice 使用了阶数允许范围内的多项式。

现在把多项式 L,R,O 整合到一个多项式 F 中:
$F=L+X^{d+1}*R+X^{2(d+1)}*O$
之所以给 R 和 O 乘以 $X^{d+1}$ 和 $X^{2(d+1)}$是为了不让它们在 F 中被混淆。
准确地说，F 中的 $1,X,...,X^d$ 是 L 的参数，接下来的 $X^{d+1},....,X^{2d+1} 是 R 的参数$ ，最后 d+1 个是 O 的参数。

现在用相同的方式对 QAP 定义中的多项式进行整合：
对每一个 $i\in{1,...,m}$ ,多项式 $F_i$ 的前 d+1 个系数是 $L_i$ 的系数，接下来是 $R_i$ 和 $O_i$ 的系数。
简单来说，针对每一个 $i\in{1,...,m}$，都可以如此定义多项式：
$F_i=L_i+X^{d+1}*R_i+X^{2(d+1)}*O_i$

那么，$F_1+F_2=(L_1+L_2)+X^{d+1}*(R_1+R_2)+X^{2(d+1)}*(O_1+O_2)$

在更一般的情况下，可得 $F=\sum_{i=1}^mc_i*F_i$,
以及 $L=\sum_{i=1}^mc_i*L_i,R=\sum_{i=1}^mc_i*R_i,O=\sum_{i=1}^mc_i*O_i$
换句话说，如果 F 是 $F_i$ 们的线性组合,那么 L,R,O 则是基于赋值生成。

Bob 向 Alice 请求证明 F 是$F_i$ 的线性组合的方式与可验证评估协议相似：
Bob 在域$\mathbb{F}_p^*$中随机选择 $\beta$ 并向 Alice 发送 $E(\beta*F_1(s),....,E(\beta*F_m(s)))$,然后 Bob 要求 Alice 向其发送元素 $E(\beta*F(s))$。
如果 Alice 成功向 Bob 返回该元素，基于先前文章中的“知识系数测试扩展版本“可知，Alice 知道如何将 F 写成 $F_i$ 的线性组合形式。

下篇文章阐述另外三个问题～