实现可验证的多项式盲估(进阶)

本文旨在基于前面两篇文章以构建可验证的多项式盲估协议，下一篇文章则是阐述如何将该协议应用于 SNARKs 中。

同之前的文章一样，假设 Alice 拥有 d 阶多项式   P , Bob 随机选择域 $\mathbb{F}_p$ 上的点 s，我们要做的是构建一个 Bob 可以获知 E(P(s)) 的协议，即多项式 P 在 s 处的同态隐藏，其满足两个性质：
1.盲视性：Alice 无法获知 s (同样 Bob 无法获知 P)
2.可验证性：对于 d 阶多项式，Alice 如果发送不是 E(P(s)) 的值， Bob 有极高的概率不接受这个值。

这就是可验证的多项式盲估，为了实现可验证性，需要对之前的 KCA 进行拓展。

基于盲视性和可验证性，Alice 可在不知道 s 的情况下决定她要使用的多项式 P ,而在完整全面的证明中则更微妙，Alice 在选择决定多项式 P 之前是可获知一些关于 s 的信息，如 $s,....,s^d$ 的同态隐藏。

**KCA 拓展**
在先前的文章中 KCA 是如此定义的：如果 Bob 向 Alice 发送 $\alpha$ 对（a,b=$\alpha$*a),然后 Alice 基于此生成另一个 $\alpha$ 对(a',b'),以此获知Alice知道满足等式 a'=c*a 中的 c. 
换句话说，Alice 知道a'与a 之间的关联。

现在假设Bob 向Alice 发送一些$\alpha$对 (其中$\alpha$是相同的)；同样地，在接收到这些$\alpha$对之后，Alice 以此生成更多的 $\alpha$ 对 (a',b')

如先前文章中所述，Alice 所做的是取其中的一个$\alpha$ 对，暂时设为($a_i,b_i$),然后乘以域$\mathbb{F}_p^*$ 中的元素c。
如果($a_i,b_i$)的确是$\alpha$ 对，那么(c*$a_i$,c*$b_i$)也会属于$\alpha$对。

这时会产生这样一个想法：
既然 Alice 收到多个 $\alpha$ 对，那么是否存在多种方法以生成新的 $\alpha$ 对？
比如同时使用多个 $\alpha$ 对生成一个新的$\alpha$ 对？

答案是肯定的:
Alice 可以选择域 $\mathbb{F}_p$ 上的两个值c1,c2 ,并基于 (a',b')=($c_1*a_1+c_2*a_2,c_1*b_1+c_2*b_2$，证明它同属于$\alpha$ 对是显而易见的：
b'=$c_1*b_1+c_2*b_2=c_1\alpha*a_1+c_2\alpha*a_2=\alpha(c_1*a_1+c_2*a_2)=\alpha*a'$

在更一般的情况下，Alice 可以对给定的d个$\alpha$ 对进行线性组合，以此得出定义式(a',b')=$\sum_{i=1}^dc_ia_i,\sum_{i=1}^dc_ib_i$

如果Alice使用这种方法生成$\alpha$对，那么她会获知 a'与 $a_1,...,a_d$ 之间的线性关系，即满足等式 a'=$\sum_{i=1}^dc_i*a_i$ 的 $c_1,....,c_d$

d-KCA: 假设 Bob 从域 $\mathbb{F}_p^*$和域$\mathbb{F}_p$ 中分别选取$\alpha$和 s,
并向 Alice 发送$\alpha$对$(g,\alpha*g),(s*g,$\alpha$s*g),...,(s^d*g,\alpha s^d*g)$ ，然后 Alice 输出$\alpha$对(a',b'),那么她知道满足等式 $\sum_{i=0}^dc_is^i*g=a'$的 $c_0,c_1...c_d$ 的概率是忽略不计的。

值得注意的是，在 d-KCA 中，Bob 并不是任意发送 $\alpha$对的集合 ，而是基于一定的多项式结构，这对下面的协议构建非常有帮助。

**可验证多项式盲估协议**
假设对于上述的 G 中生成器 g, 同态隐藏HH 的映射表达式为 E(x)=x*g 。

1.Bob 从域$\mathbb{F}_p^*$中随机选择$\alpha$ ,并将$g,s*g...s^d*g$以及$\alpha *g,\alpha s*g,...,\alpha s^d*g$的同态隐藏发送给 Alice 。

2.Alice 基于等式 $a=P(s)*g$ 以及 $b=\alpha P(s)*g$ 来计算 (a,b),并将其发送给 Bob

3.Bob 检查(a,b) 是否满足等式 $b=\alpha *a$,当且仅当等式成立时，Bob 才会接收(a,b)

值得注意的是，首先给定的系数 P,P(s)*g 是 $g,s*g,...s^d*g$ 的线性组合，$\alpha P(s)*g$是 $\alpha *g,\alpha s*g...,\alpha s^d *g$ 的线性组合。

其次，基于 d-KCA,如果Alice 发送满足等式 $b=\alpha *a$ 的 (a,b),那么几乎可以确认 Alice 知道域$\mathbb{F}_p$ 上的 $c_0,...,c_d$, 使其满足 $a=\sum_{i=0}^dc_is^i*g$。

换句话说，如果Alice 不知道多项式P,那么 Bob 接受 (a,b)的概率是忽略不计的 。

总结一下，我们使用 d-KCA 构建了可验证的多项式盲估协议，在下一片文章中，将阐述可验证的多项式盲估如何在 SNARK 中发挥作用。