1. 主页
  2. 文档
  3. zk-SNARKS验证教程
  4. 可验证的多项式盲估实现

可验证的多项式盲估实现

本文旨在基于前面两篇文章以构建可验证的多项式盲估协议,下一篇文章则是阐述如何将该协议应用于 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 中发挥作用。

我们要如何帮助您?