在前一篇文章中我展示了 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$ 的线性组合形式。

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

Leave a Reply

Your email address will not be published.