1. 主页
  2. 文档
  3. zk-SNARKS验证教程
  4. 从计算到多项式

从计算到多项式

本文主要专注于将欲证明和验证的语句转换成多项式,而这还要从 Lund,Fortnow,Karlnoff以及 Nisan 在多项式上的突破说起。

在2013年,Gennaro ,Gentry,Parno 以及Raykova 在将计算式转换成多项式方面取得了极其重大的突破,他们在这方面的工作称为 二次算数程序,即 QAP .自此以后 ,QAP 成为 zk-SNARK 的构建基石,特别是在 Zcash 中的应用。

假设 Alice 想向 Bob 证明她知道域$\mathbb{F}_p$ 上的 c1,c2,c3,c4,并且满足等式(c1+c2)*(c3+c4)=7 。

需要做的第一步是将其转换为运算电路。

运算电路由包含诸如加法和乘法等算数运算的门组成,各个门之间用导线相连接,底部为输入,顶部为输出。

值得注意的是:

  1. 当同一根导线连接不同的门时,同样把它看成是一根导线,而不是两根。
  2. 乘法门通常有两个输入导线,一般把它们成为左导线和右导线。
  3. 从加法门到乘法门或加法门的导线是不标记的,因为加法门的输入是直接进入乘法门的,因此在本例中w1和w3 都是 g2 的右输入。

对被标记导线的赋值是电路的合法赋值,每个乘法门的输出值是其对应输入的产出。

对于本文中的运算电路而言,其合法的赋值形式为:
$c_4=c_1*c2,c_5=c_4*(c_1+c_3)$

而 Alice 要证明的是她知道 $(c_1,…,c_5)的一个合法赋值$,使得 $c_5=7$ ,接下来要做的工作是使用 QAP 将语句转换成多项式。

首先将每个乘法门与域 $\mathbb{F}_p$ 上的一个元素联系起来:

在本例中,$g_1$ 与 $\mathbb{F}_p$ 上的 1 相关联,$g_2$与$\mathbb{F}_p$ 上的2相关联,此时把 {1,2}称为目标点。
现在需要定义左导线多项式 $L_1,L_2,…,L_5$,右导线多项式 $R_1,R_2,….,R_5$ 以及输出导线多项式 $O_1,O_2,…,O_5$

之所以会如此定义多项式,是其在目标点的多项式值通常为 0 ,除了乘法门上的目标点。

$W_1,W_2,W_4$ 分别对应 g1 的左,右,输出导线;

定义 $L_1=R_2=O_4=2-X$, 因为 2-X 在之前给出的$g_1$点 1 上的值是 1,而在$g_2$的点 2上的值是 0 。

既然 $w_1$ 和 $w_3$ 都是 $g_2$ 的右输入,那么可给出相似的定义式:
$L_4=R_1=R_3=O_5=X-1$ ,因为 X-1 在 $g_2$ 的目标点 2 上的值是 1 ,在其他目标点上是 0 ,最后把多项式剩余的部分都设置为零式。

给出定值$(c_1,….,c_5)$,并把它作为左,右,输出多项式的系数,即
$L:=\sum_{i=1}^5c_i*L_i,R:=\sum_{i=1}^5c_i*R_i,O:=\sum_{i=1}^5c_i*O_i$

基于此,定义多项式:$P:=L*R-O$

给出以上所有定义之后,核心点是:$(c_1,…,c_5)$对电路来说是合法赋值当且仅当多项式 P 在所有的目标点上为零。

以本例作为测试,假设我们在给定的 $c_1,…,c_5$ 上定义 L,R,O,P ,以下要做的是在目标点 1 上评估所有的多项式。

在所有的 $L_i$ 中,只有$L_1$ 在目标点 1 上是非零的,可得 $L(1)=c_1*L_1(1)=c_1$ ,同样可得 $R_1=c_2$,$O(1)=c_4$,所以 $P(1)=c_1*c_2-c_4$ ,同理可得 $P(2)=c_4*(c_1+c_3)-c_5$

换句话说,当且仅当$(c_1,…c_5)$是合法赋值时, P 在目标点上取 0 。

现在,基于下述代数定理:对于多项式 P 和域$\mathbb{F}_p$ 上的点 a, 可得 P(a)=0 当且仅当多项式 X-a 整除 P,即 P = (X-a)* H,其中 H 是某多项式。

给出目标多项式定义式:T(X):=(X-1)*(X-2),若T整除 P 当且仅当 $(c_1,…,c_5)$是合法赋值.

现在给出下述 QAP 定义:
d 阶大小为 m 的二次算数程序 Q,由多项式 $L_1,..,L_m,R_1….,R_m,O_1,….,O_m$以及 d 阶目标多项式 T 构建而成。

如果 $(c_1,c_2….,c_m)$满足 Q 式,那么定义:
$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 想要证明她知道一个满足 QAP 的赋值 $(c_1,c_2,…c_5)$,其中 $c_5=7$

总结一下,本文主要讲述的是如何使用QAP将语句“Alice 知道满足等式 $(c_1*c_2)*(c_1+c_3)=7$替换成相等的多项式”
下篇文章要阐述的是对 QAP 合理赋值的证明。

我们要如何帮助您?