绘素的Blog

关于 zk-SNARK 的学习笔记，主要关注 zk-SNARK 中的方程。

ZK-SNARK 代表 零知识简洁非交互式知识论证。

zk-SNARK 的三个属性

1. 完整性：每个具有有效见证的声明都有一个能够说服验证者的证明。

2. 健壮性：具有无效见证的声明没有能够说服验证者的证明。

3. 零知识：证明仅传达有关声明有效性的信息，而不涉及证明者的见证。

初步知识#

算术电路#

算术电路是计算多项式的模型。对于有限域 $F=\{0,\cdots,p-1\}$（素数 $p>2$），算术电路 $C:F^n\rightarrow F$ 是一个有向无环图（DAG），其中节点是加法和乘法门，边是电线。DAG 中每个节点有两个输入和输出。DAG 有一个最终输出。

在一个 $m$- 门，$n$- 线的算术电路中，见证 定义为 $s=(s_1,s_2,\cdots, s_n)$，其中 $s_i$ 是第 $i$ 条电线的值。

Rank-1 约束 (R1CS) 定义如下：对于某些常数 $\{u_{i,q},v_{i,q},w_{i,q}\}_{1\le i\le n,1\le q\le m}$，$\sum_{i=1}^ns_iu_{i,q}\cdot \sum_{i=1}^ns_iv_{i,q}=\sum_{i=1}^ns_iw_{i,q}$。例如，在图 1 中，$s_1\cdot s_2=s_4$ 是一个 R1CS，其中 $u_{1,1}=1,v_{2,1}=1,w_{4,1}=1$，其他 $=0$。

二次算术程序 (QAP)#

首先，我们定义目标点为 $r_1,r_2,\cdots,t_m\in F_p$。每个目标点对应于算术电路中的一个门。然后，我们定义消失函数 $t(x)=\Pi_{q=1}^m(x-r_q)$，使得 $t(x)=0$ 在目标点 $r_1,r_2,\cdots,t_m$。

一个二次算术程序是一个关于 $s=(s_1,s_2,\cdots, s_n)$ 的关系，使得 $\sum_{i=1}^ns_iu_{i}(x)\cdot \sum_{i=1}^ns_iv_{i}(x)-\sum_{i=1}^ns_iw_{i}(x)\equiv 0~(\bmod~t(x))$，其中 $u_i(x),v_i(x),w_i(x)$ 是度为 $m-1$ 的多项式，使得对于 $1\le i\le n,1\le q\le m$，$u_i(r_q)=u_{i,q}$，$v_i(r_q)=v_{i,q}$ 和 $w_i(r_q)=w_{i,q}$。

当 $x=r_q$ 时，这个方程是第 $q$ 个门的 R1CS。因此，检查这个方程等同于同时检查 $m$ 个 Rank-1 约束。

同态编码#

同态编码是一个单射同态 $E: F_p\rightarrow G$，使得给定 $E(x)$ 很难找到 $x$。

例如，给定一个素数阶 $p$ 的循环群 $G$，以 $g$ 为生成元，乘法为群运算，同态编码为 $E(a)=g^a$。它是同态的且是单射的。此外，由于离散对数问题的困难，给定 $E(x)$ 也很难找到 $x$。

配对函数，或双线性映射#

配对函数，也称为双线性映射，定义如下：

$G_1,G_2$ 和 $G_T$ 是素数阶 $p$ 的群，配对函数为 $e:G_1\times G_2\rightarrow G_T$，使得：

1. 如果 $g,h$ 分别是 $G_1$ 和 $G_2$ 的生成元，则 $e(g,h)\not= 1$ 是 $G_T$ 的生成元。

2. $e(g^a,h^b)=e(g,h)^{ab}$。

双线性映射具有几个属性，如下所示：

• $e(u,vw)=e(g^a,h^bh^c)=e(g,h)^{a(b+c)}=e(g^a,h^b)e(g^a,h^c)=e(u,v)e(u,w)$

• $e(vw,u)=e(v,u)e(w,u)$

• $e(u^x,v)=e(g,h)^{xab}=e(u,v^x)$

在 Pinocchio 实现中（zk-SNARK 的一种实现），使用了对称双线性映射，其中 $G:=G_1=G_2$。

zk-SNARK#

对于任何 NP 计算，证明者和验证者事先达成一致，他们可以为该计算构建一个算术电路，使得该电路的见证是原始计算的见证。算术电路可以简化为 QAP，使得验证 QAP 的见证等同于验证算术电路的见证。因此，验证 QAP 的见证等同于验证原始计算的见证。

从算术电路到 QAP 的一般简化#

对于一个具有 $m$ 个门和 $n$ 条线的算术电路，见证定义为 $s=(s_1,s_2,\cdots,s_n)\in R^n$。对于 $s$ 的 R1CS $(a_i,b_i,c_i)$ 定义为 $(s\cdot a_i)\times(s\cdot b_i)-s\cdot c_i=0$，其中 $1\le i\le m$ 且 $a_i,b_i,c_i\in R^n$。

一般简化包括三个步骤：

1. 将 $m$ 个约束向量堆叠以获得矩阵 $A,B,C\in R^{m\times n}$，其中

   • $A=\begin{pmatrix}a_1^T\\a_2^T\\\vdots\\a_m^T\end{pmatrix}B=\begin{pmatrix}b_1^T\\b_2^T\\\vdots\\b_m^T\end{pmatrix}C=\begin{pmatrix}c_1^T\\c_2^T\\\vdots\\c_m^T\end{pmatrix}$

2. 使用拉格朗日插值，找到 $3$ 组 $n$ 个多项式 $\{u_i\}_{i=1}^n,\{v_i\}_{i=1}^n,\{w_i\}_{i=1}^n$，使得

   • 对于所有 $i\in[n]$ 和 $x\in[m]$

   • $\begin{aligned}u_i(x)&=A[x][i]\\v_i(x)&=B[x][i]\\w_i(x)&=C[x][i]\end{aligned}$

3. 找到多项式 $h(x)$，使得

   • $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$

   • 其中 $t(x)=(x-1)(x-2)\cdots(x-n)$

因此，检查 $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$ 等同于检查算术电路中的 R1CS 关系。也就是说，见证可以满足每个节点中的所有 R1CS 关系。

Pinocchio 协议#

Pinocchio 协议是 zk-SNARK 的一种实现。

该协议建立在一个素数阶 $p$ 的群 $G$ 上，生成元为 $g$。定义同态编码为 $E:F_p\rightarrow G$，$E(x)=g^x$。定义椭圆曲线双线性映射为 $e:G\times G\rightarrow G_T$。证明者知道见证 $\{s_i\}_{i=1}^n$，他可以通过简化得到以下方程：$\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$。

主要思想如下：

1. $V$ 在随机点 $z\in F_p$ 测试 $P$ 的多项式。

2. $P$ 计算 $u(z)=\sum_{i=1}^{n}s_{i}u_{i}(z),v(z)=\sum_{i=1}^{n}s_{i}v_{i}(z),w(z)=\sum_{i=1}^{n}s_{i}w_{i}(z)$ 和 $h(z)$，并同态编码这些值并发送给 $V$。

3. $V$ 可以验证同态编码的值满足相同的方程，而不需要了解见证本身。

Pinocchio 协议由三个步骤组成：（1）可信第三方生成一个公共参考字符串（CRS）；（2）证明者生成证明；（3）验证者检查证明并决定接受或拒绝。

在 CRS 生成过程中，可信第三方随机选择 $\alpha, \beta_u,\beta_v,\beta_w,\gamma,z\in F_p^*$ 并发布 CRS。然后，可信第三方丢弃在生成过程中使用的所有采样群元素（有毒废物）。CRS 包含证明者的评估密钥和验证者的验证密钥。

评估密钥定义如下：

• $\{E(z^{i})\}_{i=0}^{n},\{E(\alpha z^{i})\}_{i=0}^{n}$

• $\{E(u_i(z)\}_{i=1}^n,\{E(\alpha u_i(z)\}_{i=1}^n,\{E(\beta_uu_i(z)\}_{i=1}^n$

• $\{E(v_{i}(z)\}_{i=1}^{n},\{E(\alpha v_{i}(z)\}_{i=1}^{n},\{E(\beta_{v}v_{i}(z)\}_{i=1}^{n}$

• $\{E(w_i(z)\}_{i=1}^n,\{E(\alpha w_i(z)\}_{i=1}^n,\{E(\beta_ww_i(z)\}_{i=1}^n$

验证密钥定义如下：

• $E(1),E(\alpha),E(t(z))$

• $E(\gamma),E(\beta_u\gamma),E(\beta_v\gamma),E(\beta_w\gamma)$

在证明生成过程中，由于证明者知道多项式 $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$，他将首先计算 $h(x)$。然后，证明者使用评估密钥生成证明，如下所示：

• $E(u(z)),E(\alpha u(z)),\mathrm{~其中~}u(z)=\sum_{i=1}^ns_iu_i(z)$

• $E(v(z)),E(\alpha v(z)),\mathrm{~其中~}v(z)=\sum_{i=1}^ns_iv_i(z)$

• $E(w(z)),E(\alpha w(z)),\text{ 其中 }w(z)=\sum_{i=1}^ns_iw_i(z)$

• $E(h(z)),E(\alpha h(z))$

• $E(\beta_uu(z)+\beta_vv(z)+\beta_ww(z))$

例如，

• $E(u(z))=E(\sum_{i=1}^ns_iu_i(z))=g^{\sum_{i=1}^ns_iu_i(z)}=\Pi_{i=1}^ng^{s_iu_i(z)}=\Pi_{i=1}^n(g^{u_i(z)})^{s_i}=\Pi_{i=1}^n(E(u_i(z))^{s_i})$

• $E(\alpha u(z))=E(\sum_{i=1}^ns_i\alpha u_i(z))=\Pi_{i=1}^n(E(\alpha u_i(z))^{s_i})$

• $E(h(z))$：$z^i$ 的线性组合，可以从 $E(z^i)$ 中计算。

• $E(\beta_uu(z)+\beta_vv(z)+\beta_ww(z))=E(\beta_uu(z))E(\beta_vv(z))E(\beta_ww(z))$

在证明验证过程中，验证者将进行三次验证。

首先，验证者检查项 $u(z), v(z), w(z), h(z)$ 是否作为 CRS 中项的线性组合构造，通过检查以下方程：

• $e(E(u(z)),E(\alpha u_{1}(z))) =e(E(\alpha u(z)),E(u_1(z)))$

• $e(E(v(z)),E(\alpha v_1(z))) =e(E(\alpha v(z)),E(v_1(z)))$

• $e(E(w(z)),E(\alpha w_{1}(z))) =e(E(\alpha w(z)),E(w_1(z)))$

• $e(E(h(z)),E(\alpha)) =e(E(\alpha h(z)),E(1))$

然后，验证者检查每个项 $u(z), v(z), w(z)$ 是否使用相同的线性系数 $\{s_i\}^n_{i=1}$，即检查 $u(z)=\sum_{i=1}^{n}s_{i}u_{i}(z),v(z)=\sum_{i=1}^{n}s_{i}v_{i}(z),w(z)=\sum_{i=1}^{n}s_{i}w_{i}(z)$。

• $e(E(\beta_uu(z)+\beta_vv(z)+\beta_ww(z)),E(\gamma))=e(E(u(z)),E(\beta_u\gamma))e(E(v(z)),E(\beta_v\gamma))e(E(w(z)),E(\beta_w\gamma))$

最后，验证者检查表征多项式可除性标准的关键条件，通过检查以下方程：

• $e(E(u(z)),E(v(z)))=e(E(w(z)),E(1))\cdot e(E(t(z)),E(h(z)))$

• 即 $e(E(u(z)),E(v(z)))/e(E(w(z)),E(1))= e(E(t(z)),E(h(z)))$

• 即检查 $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$

如果所有检查都通过，验证者将接受。

由于现在的过程不是零知识。如果 $V$ 提出自己的见证 $s^\prime=(s_1^\prime,s_2^\prime,\cdots,s_n^\prime)$，他们可以计算 $E(u^\prime(z)),E(v^\prime(z)),E(w^\prime(z)),E(h^\prime(z))$。如果这些值与 $E(u(z)),E(v(z)),E(w(z)),E(h(z))$ 不同，则验证者得出结论，证明者的见证不是 $s^\prime$。

通过向多项式 $u,v,w$ 添加随机偏移，可以实现零知识。随机偏移将是 $t(x)$ 的倍数，以便一切仍然在 $\bmod~t(x)$ 下相同。对于随机 $\delta_1,\delta_2,\delta_3\in F_p$，偏移多项式定义为

• $u_z(x)=u(x)+\delta_1 t(x)$

• $v_z(x)=v(x)+\delta_2t(x)$

• $w_z(x)=w(x)+\delta_3t(x)$

然后，$P$ 将在其证明中用偏移项替换未偏移项。例如，$E(u_z(x))=E(u(x)+\delta_1t(x))=E(u(x))E(\delta_1t(x))$。

Groth-16 协议#

Groth-16 协议是 zk-SNARK 的一种更简洁的实现。证明大小和验证者复杂度都显著低于 Pinocchio。

在 Groth-16 中，由于证明者知道多项式 $\left(\sum_{i=1}^ns_iu_i(x)\right)\cdot\left(\sum_{i=1}^ns_iv_i(x)\right)-\left(\sum_{i=1}^ns_iw_i(x)\right)=h(x)t(x)$，证明定义如下：

• $E(\alpha+u(z))$

• $E(\beta+v(z))$

• $E(\sum s_i\times(\beta u_i(z)+\alpha v_i(z)+w_i(z))+h(z)t(z))$

验证者将检查：$e(E(\alpha+u(z)), E(\beta+v(z)))=e(E(\sum s_i\times(\beta u_i(z)+\alpha v_i(z)+w_i(z))+h(z)t(z)), E(1))e(E(\alpha), E(\beta))$

参考文献#

A Review of zk-SNARKs

Zero Knowledge Proofs MOOC