零知识证明（一）Groth16

零知识证明（一）Groth16

如果不熟悉R1CS和QAP，请参考零知识证明（零）前置知识。

1.1 可信设置

可信设置解决的是对QAP多项式随机求值的问题，求值的这个点不能公开，否则证明者就可以针对这个点生成伪证明，因此需要生成一个秘密的求值点。

可信设置（Trusted Setup）简单来讲就是计算多项式在一个秘密点的值。如\(f(x)=3x^3+2x^2+5x+10\)，可以通过内积来计算，即 \[ f(x)=[3,2,5,10]\cdot[x^3,x^2,x,1] \] 如何保证求值的点是秘密的，可以利用椭圆曲线的离散对数难题。选择一个\(\tau\)，计算结构化参考字符串（SRS, Structure Reference String）： \[ [\Omega_3,\Omega_2,\Omega_1,G_1]=[\tau^3G_1,\tau^2G_1,\tau G_1,G_1] \] 这样删除掉\(\tau\)后，就没人知道算的到底是哪个点的取值。计算取值的例子如下： \[ f(\tau)=[3,2,5,10]\cdot[\Omega_3,\Omega_2,\Omega_1,G_1]=3\Omega_3+2\Omega_2+5\Omega_1+10G_1 \]

这里\(f(\tau)\)表示对\(\tau\)生成的SRS进行求值，实际上\(\tau\)已经被删除了。

如何验证生成的SRS是正确的？生成SRS的同时还要给出\(\Theta=\tau G_2\)。

• 证明生成\(\Theta\)使用的\(\tau\)和上面的一样：验证\(e(G_1,\Theta)=e(\Omega_1,G_2)\)。
• 证明SRS生成正确：验证\(e(\Omega_i,\Theta)=e(\Omega_{i+1},G_2)\)。

如何保证\(\tau\)真的被删了？可以多方生成SRS，只要一方真的删掉了就无法还原。以两方为例：Alice选择\(\tau\)生成\(([\tau^nG_1,\cdots\tau G_1,G_1],\tau G_2)\)，Bob选择\(\gamma\)在Alice生成的基础上生成\(([(\tau\gamma)^nG_1,\cdots,(\tau\gamma)G_1,G_1],(\tau\gamma)G_2)\)，只要\(\tau\)和\(\gamma\)有一个删掉了就无法还原。

辨析CRS与SRS：

• CRS（Common Reference String），公共参考字符串：任意公开、预生成的一些随机参数。
• SRS（Structured Reference String），结构化参考字符串：具有某种代数结构的参考字符串，属于CRS的一种。

1.2 用SRS计算QAP

QAP得到的等式为\(u(x)v(x)=w(x)+h(x)t(x)\)​，各多项式的次数如下：

• \(u(x),v(x),w(x)\)：次数（至多）为\(n-1\)，因为是对矩阵的列进行插值的，每列有\(n\)个元素。
• \(t(x)\)：次数为\(n\)，由其定义易知。
• \(h(x)\)：次数（至多）为\(2(n-1)-n=n-2\)。

可信设置生成的SRS为： \[ \begin{align} [\Omega_{n-1},\cdots,\Omega_1,G_1]&=[\tau^{n-1}G_1,\cdots,\tau G_1,G_1],\Omega_i\in\mathbb G_1\\ [\Theta_{n-1},\cdots,\Theta_1,G_2]&=[\tau^{n-1}G_2,\cdots,\tau G_2,G_2],\Theta_i\in\mathbb G_2 \end{align} \] 求值时，\(u(x)\)和\(w(x)\)与\([\Omega_{n-1},\cdots,\Omega_1,G_1]\)做内积，\(v(x)\)与\([\Theta_{n-1},\cdots,\Theta_1,G_2]\)做内积。

如何求值\(h(x)t(x)\)？有如下考虑：

• 我们希望等式右边\(w(x)+h(x)t(x)\)都是\(\mathbb G_1\)的元素（考虑到最终pairing的次数），因此不能对\(h(x)\)和\(t(x)\)分别用不同的SRS求值。
• 目前的SRS是用来求值\(u(x),v(x),w(x)\)的，长度只有\(n\)，而求值多项式乘积\(h(x)t(x)\)需要长度为\(2n-1\)的SRS。
• \(t(x)\)是已知的；而\(h(x)\)是由证明者计算的，可信设置时未知。

因此采用的方法是预先计算\(t(x)\)，将\(\tau\)代入\(t(x)\)得到\(t(\tau)\)，这样\(t(\tau)\)就是常数了。所以\(h(x)t(x)=h(x)t(\tau)\)，现在只需对\(h(x)\)生成如下SRS： \[ [\Upsilon_{n-2}, \Upsilon_{n-3}, \ldots, \Upsilon_1, \Upsilon_0] = [\tau^{n-2} t(\tau) G_1, \tau^{n-3} t(\tau) G_1, \ldots, \tau t(\tau) G_1, t(\tau) G_1] \] 计算\(h(x)t(x)\)如下： \[ h(\tau)t(\tau)=[h_{n-1},\cdots,h_1,h_0]\cdot[\Upsilon_{n-2},\cdots,\Upsilon_1,\Upsilon_0] \]

为什么这样算是对的？ \[ \begin{align} h(\tau)t(\tau)&=[h_{n-2},\cdots,h_1,h_0]\cdot[\Upsilon_{n-2},\cdots,\Upsilon_1,\Upsilon_0]\\ &=[h_{n-2},\cdots,h_1,h_0]\cdot[\tau^{n-2} t(\tau) G_1, \tau^{n-3} t(\tau) G_1, \ldots, \tau t(\tau) G_1, t(\tau) G_1]\\ &=([h_{n-2},\cdots,h_1,h_0]\cdot[\tau^{n-2}G_1,\tau^{n-3} G_1,\ldots,\tau G_1,G_1])t(\tau)\\ &=h(\tau)t(\tau) \end{align} \] 上面的\(t(\tau)\)是直接将\(\tau\)的值代入\(t(x)\)，因为是可信设置时计算的。而\(h(\tau)\)表示将\(\tau\)生成的SRS代入\(h(x)\)。

到目前为止的Groth16

• 可信设置 \[ \begin{align} \text{random scalars}&\to\tau\\ SRS_{G_1}&\to[\tau^{n-1} G_1, \tau^{n-2} G_1, \cdots, \tau G_1, G_1]\\ SRS_{G_2}&\to[\tau^{n-1} G_2, \tau^{n-2} G_2, \cdots, \tau G_2, G_2]\\ SRS_{h(\tau)t(\tau)}&\to[\tau^{n-2} t(\tau) G_1, \tau^{n-3} t(\tau) G_1, \ldots, \tau t(\tau) G_1, t(\tau) G_1] \end{align} \]

• 证明者 \[ \begin{align} [A]_1&=u(\tau)\\ [B]_2&=v(\tau)\\ [C]_1&=w(\tau)+h(\tau)t(\tau) \end{align} \]

• 验证者 \[ e([A]_1,[B]_2)=e([C]_1,G_2) \]

1.3 引入\(\alpha\)和\(\beta\)：保证证明者根据QAP计算出了正确的ABC

在可信设置时生成\(\alpha\)和\(\beta\)，公开其对应的点： \[ \begin{align} [\alpha]_1&=\alpha G_1\\ [\beta]_2&=\beta G_2 \end{align} \] 将QAP等式\(u(x)v(x)=w(x)+h(x)t(x)\)修改为： \[ (\theta+u(x))(\eta+v(x))=\theta\eta+\theta v(x)+\eta u(x)+w(x)+h(x)t(x) \] 将\([\alpha]_1,[\beta]_2\)分别代入\(\theta,\eta\)，则需要验证的式子变为如下： \[ ([\alpha]_1+u(\tau))\cdot([\beta]_2+v(\tau))=[\alpha]_1\cdot[\beta]_2+(\alpha v(\tau)+\beta u(\tau)+w(\tau)+h(\tau)t(\tau))\cdot G_2 \]

令 \[ \begin{align} [A]_1&=[\alpha]_1+u(\tau)\\ [B]_2&=[\beta]_2+v(\tau)\\ [C]_1&=\alpha v(\tau)+\beta u(\tau)+w(\tau)+h(\tau)t(\tau) \end{align} \] 上式简化为 \[ [A]_1\cdot[B]_2=[\alpha]_1\cdot[\beta]_2+[C]_1\cdot G_2 \] 上式没有将\([\alpha]_1v(\tau)\)和\([\beta]_2u(\tau)\)也单独拿出来pairing，因为这样会导致验证时pairing的计算次数过多，所以是把后面的部分都合并为一个点\([C]_1\)，一起与\(G_2\)进行pairing。这样的话\(\alpha u(\tau)+\beta v(\tau)+w(\tau)+h(\tau)t(\tau)\)中就需要原始的\(\alpha\)和\(\beta\)，而这两个值只有在可信设置中才能直接使用，因此需要在可信设置时预计算部分值。

把\(u(\tau),v(\tau),w(\tau)\)都展开： \[ \begin{align} u(\tau)&=\sum_{i=1}^ma_iu_i(\tau)\\ v(\tau)&=\sum_{i=1}^ma_iv_i(\tau)\\ w(\tau)&=\sum_{i=1}^ma_iw_i(\tau) \end{align} \] 其中\(u_i(\tau),v_i(\tau),w_i(\tau)\)在给定了电路后是知道的，但\(a_i\)只有证明者才知道，所以只能在可信设置时计算： \[ \sum_{i=1}^m\alpha v_i(\tau)+\beta u_i(\tau)+w_i(\tau) \] 因此现在要得到\([C]_1\)只需与witness做内积即可，即\(\sum_{i=1}^ma_i(\alpha v_i(\tau)+\beta u_i(\tau)+w_i(\tau))\)。从这里可以看出可信设置与电路有关，每个电路都需要单独进行可信设置。

至此，通过引入\(\alpha\)和\(\beta\)解决了证明者无法伪造\([A]_1,[B]_2,[C]_1\)的问题。为什么呢？看这个式子\([A]_1\cdot[B]_2=[\alpha]_1\cdot[\beta]_2+[C]_1\cdot G_2\)，将左右展开可得： \[ \begin{align} 左边&=([\alpha]_1+u(\tau))\cdot([\beta]_2+v(\tau))\\ &=[\alpha]_1\cdot[\beta]_2+[\alpha]_1\cdot v(\tau)+u(\tau)\cdot[\beta]_2+u(\tau)\cdot v(\tau)\\ 右边&=[\alpha]_1\cdot[\beta]_2+(\alpha v(\tau)+\beta u(\tau)+w(\tau)+h(\tau)t(\tau))\cdot G_2 \end{align} \] 消去\([\alpha]_1\cdot[\beta]_2\)后，证明者给出的\(u(\tau),v(\tau),w(\tau),h(\tau)t(\tau)\)应满足下面两点才能通过验证：

• \([\alpha]_1\cdot v(\tau)+u(\tau)\cdot[\beta]_2\)等于\((\alpha v(\tau)+\beta u(\tau))\cdot G_2\)，注意\(\alpha v(\tau)+\beta u(\tau)\)是可信设置时生成的，证明者不知道\(\alpha\)和\(\beta\)的值，所以左边如果不用正确的\(u(\tau)\)和\(v(\tau)\)是满足不了等式的。这保证了\(u(\tau),v(\tau)\)是从QAP中得出的。
• \(u(\tau)\cdot v(\tau)\)等于\(w(\tau)+h(\tau)t(\tau)\)，这保证了QAP等式的成立。

总结就是：证明者只有用从QAP中正确计算得到的值来计算点值，才能匹配上可信设置时生成的值（因为生成这个值的时候用了正确的QAP），这样才能满足验证条件。

到目前为止的Groth16

• 可信设置

  \[\begin{align} \text{random scalars}&\to\alpha,\beta,\tau\\ SRS_{G_1}&\to[\tau^{n-1} G_1, \tau^{n-2} G_1, \cdots, \tau G_1, G_1]\\ SRS_{G_2}&\to[\tau^{n-1} G_2, \tau^{n-2} G_2, \cdots, \tau G_2, G_2]\\ SRS_{h(\tau)t(\tau)}&\to[\tau^{n-2} t(\tau)G_1, \tau^{n-3} t(\tau)G_1, \cdots, \tau t(\tau)G_1, t(\tau)G_1]\\ [\Psi_1]_1&=(\alpha v_1(\tau) + \beta u_1(\tau) + w_1(\tau)) G_1 \\ [\Psi_2]_1&=(\alpha v_2(\tau) + \beta u_2(\tau) + w_2(\tau)) G_1 \\ &\vdots\\ [\Psi_m]_1&=(\alpha v_m(\tau) + \beta u_m(\tau) + w_m(\tau)) G_1 \end{align}\]

  公开：

  \[ ([\alpha]_1,[\beta]_2,SRS_{G_1},SRS_{G_2},SRS_{h(\tau)t(\tau)}, [\Psi_1]_1,[\Psi_2]_1,\cdots,[\Psi_m]_1) \]

• 证明者 \[ \begin{align} [A]_1&=[\alpha]_1+\sum_{i=1}^ma_iu_i(\tau)\\ [B]_2&=[\beta]_2+\sum_{i=1}^ma_iv_i(\tau)\\ [C]_1&=\sum_{i=1}^ma_i[\Psi_i]_1+h(\tau)t(\tau) \end{align} \]

• 验证者 \[ [A]_1\cdot[B]_2=[\alpha]_1\cdot[\beta]_2+[C]_1\cdot G_2 \]

1.4 引入\(\gamma\)和\(\delta\)：支持公开输入

到目前为止的witness的元素都是私有的，但实际上需要公开一些元素（比如你知道哈希函数\(H(x)=y\)的输入\(x\)，这里\(y\)就是要公开的元素）。公开的通常是witness的前\(l\)个元素，即\([a_1,\cdots,a_l]\)。

对于证明者来说，\([A]_1,[B]_2\)的计算不变，\([C]_1\)变为： \[ [C]_1=\sum_{i=l+1}^ma_i[\Psi_i]_1+h(\tau)t(\tau) \] 验证者计算 \[ [X]_1=\sum_{i=1}^la_i[\Psi_i]_1 \] 验证的公式变为 \[ [A]_1\cdot[B]_2=[\alpha]_1\cdot[\beta]_2+[X]_1\cdot G_2+[C]_1\cdot G_2 \] 需要说明的是Groth16需要保证证明者只能用私有输入计算\([C]_1\)，而不能使用\([X]_1\)中的公开输入。举个例子，设\(\text{witness}=[1,2,3,4,5]\)，\(l=3\)，也就是前三个是公开输入，最右边两项本来应该是： \[ (1\Psi_1+2\Psi_2+3\Psi_3)\cdot G2+(4\Psi_4+5\Psi_5 + h(\tau)t(\tau))\cdot G_2 \] 但如果计算\([C]_1\)时用了公开输入\(\Psi_3\)，为了能满足验证等式，只能将上式改为： \[ (1\Psi_1+2\Psi_2+0\Psi_3)\cdot G2+(3\Psi_3+4\Psi_4+5\Psi_5 + h(\tau)t(\tau))\cdot G_2 \] 这样公开输入就从\([1,2,3]\)变为了\([1,2,0]\)，这就改变了原来想要证明的输入，而如果验证者不检查证明者提供的\(a_1,a_2,\cdots,a_l\)的话就会被证明者骗过去，因此协议强制证明者不能用公开输入计算\([C]_1\)。

为了解决上述问题，引入了\(\gamma\)和\(\delta\)。在可信设置时，计算\([C]_1\)相关（私有输入相关）的值时都要除以\(\delta\)，而计算\([X]_1\)相关（公开输入相关）的值时都要除以\(\gamma\)。在验证时将除掉的\(\gamma\)和\(\delta\)乘回去即可，即与\([\gamma]_2\)和\([\delta]_2\)进行pairing，见下。

到目前为止的Groth16

• 可信设置

  \[\begin{align} \text{random scalars}&\to\alpha,\beta,\tau,\gamma,\delta\\ SRS_{G_1}&\to[\tau^{n-1} G_1, \tau^{n-2} G_1, \cdots, \tau G_1, G_1]\\ SRS_{G_2}&\to[\tau^{n-1} G_2, \tau^{n-2} G_2, \cdots, \tau G_2, G_2]\\ SRS_{h(\tau)t(\tau)}&\to[\frac{\tau^{n-2}t(\tau)}{\delta}G_1,\frac{\tau^{n-3}t(\tau)}{\delta}G_1,\cdots,\frac{\tau t(\tau)}{\delta}G_1, \frac{t(\tau)}{\delta}G_1]\\ [\Psi_1]_1&=\frac{\alpha v_1(\tau) + \beta u_1(\tau) + w_1(\tau)}{\gamma}G_1 \\ [\Psi_2]_1&=\frac{\alpha v_2(\tau) + \beta u_2(\tau) + w_2(\tau)}{\gamma}G_1 \\ &\vdots\\ [\Psi_l]_1&=\frac{\alpha v_l(\tau) + \beta u_l(\tau) + w_l(\tau)}{\gamma}G_1\\ [\Psi_{l+1}]_1&=\frac{\alpha v_{l+1}(\tau) + \beta u_{l+1}(\tau) + w_{l+1}(\tau)}{\delta}G_1 \\ [\Psi_{l+2}]_1&=\frac{\alpha v_{l+2}(\tau) + \beta u_{l+2}(\tau) + w_{l+2}(\tau)}{\delta}G_1 \\ &\vdots\\ [\Psi_m]_1&=\frac{\alpha v_m(\tau) + \beta u_m(\tau) + w_m(\tau)}{\delta}G_1 \end{align}\]

  公开：

  \[ ([\alpha]_1,[\beta]_2,[\gamma]_2,[\delta]_2,SRS_{G_1},SRS_{G_2},SRS_{h(\tau)t(\tau)},[\Psi_1]_1,[\Psi_2]_1,\cdots,[\Psi_m]_1) \]

• 证明者 \[ \begin{align} [A]_1&=[\alpha]_1+\sum_{i=1}^ma_iu_i(\tau)\\ [B]_2&=[\beta]_2+\sum_{i=1}^ma_iv_i(\tau)\\ [C]_1&=\sum_{i=l+1}^ma_i[\Psi_i]_1+h(\tau)t(\tau) \end{align} \]

• 验证者

  \[ \begin{align} &[X]_1=\sum_{i=1}^la_i[\Psi_i]_1\\ [A]_1\cdot[B]_2=[&\alpha]_1\cdot[\beta]_2+[X]_1\cdot[\gamma]_2+[C]_1\cdot[\delta]_2 \end{align} \]

1.5 引入\(r\)和\(s\)：实现真正的零知识

如果输入的可能性很少，比如只有几个人投票，那么攻击者可以遍历所有的情况，按照证明者同样的算法为每种情况生成证明，然后与证明者生成的证明进行比较，从而就能得出witness。

解决方法是在证明中加盐（Salt），证明者计算时生成两个随机数\(r\)和\(s\)，把它们加入\([A]_1,[B]_2,[C]_1\)的计算中： \[ \begin{align} [A]_1&=[\alpha]_1+\sum_{i=1}^ma_iu_i(\tau)+r[\delta]_1\\ [B]_2&=[\beta]_2+\sum_{i=1}^ma_iv_i(\tau)+s[\delta]_2\\ [B]_1&=[\beta]_1+\sum_{i=1}^ma_iv_i(\tau)+s[\delta]_1\\ [C]_1&=\sum_{i=l+1}^ma_i[\Psi_i]_1+h(\tau)t(\tau)+[A]_1s+[B]_1r-rs[\delta]_1 \end{align} \] 为什么\([C]_1\)后面多了三项，来推一下： \[ \begin{align} [A]_1\cdot[B]_2&=([\alpha]_1+\sum_{i=1}^ma_iu_i(\tau)+r[\delta]_1)\cdot([\beta]_2+\sum_{i=1}^ma_iv_i(\tau)+s[\delta]_2)\\ &=[\alpha]_1\cdot[\beta]_2+[\alpha]_1\cdot\sum_{i=1}^ma_iv_i(\tau)+\sum_{i=1}^ma_iu_i(\tau)\cdot[\beta]_2+\sum_{i=1}^ma_iu_i(\tau)\cdot\sum_{i=1}^ma_iv_i(\tau)+\ \\ &\ \quad[\alpha]_1\cdot s[\delta]_2+\sum_{i=1}^ma_iu_i(\tau)\cdot s[\delta]_2+r[\delta]_1\cdot[\beta]_2+r[\delta]_1\cdot\sum_{i=1}^ma_iv_i(\tau)+r[\delta]_1\cdot s[\delta]_2\\ \end{align} \] 看第二个等号后面的式子：第一行对应原来的（上一节）验证公式的右边；第二行是新增的，可以稍微变换一下： \[ \begin{align} 第二行&=[\alpha]_1\cdot s[\delta]_2+\sum_{i=1}^ma_iu_i(\tau)\cdot s[\delta]_2\textcolor{blue}{+r[\delta]_1\cdot s[\delta]_2}+\ \\ &\ \quad r[\delta]_1\cdot[\beta]_2+r[\delta]_1\cdot\sum_{i=1}^ma_iv_i(\tau)+r[\delta]_1\cdot s[\delta]_2\textcolor{blue}{-r[\delta]_1\cdot s[\delta]_2}\\ &=([\alpha]_1+\sum_{i=1}^ma_iu_i(\tau)+r[\delta]_1)\cdot s[\delta]_2+\ \\ &\ \quad r[\delta]_1\cdot([\beta]_2+\sum_{i=1}^ma_iv_i(\tau)+s[\delta]_2)-r[\delta]_1\cdot s[\delta]_2\\ &=[A]_1\cdot s[\delta]_2+r[\delta]_1\cdot[B]_2-r[\delta]_1\cdot s[\delta]_2 \end{align} \] 其中\(r[\delta]_1\cdot[B]_2\)和\(r[B]_1\cdot[\delta]_2\)是相等的，提出公因式\([\delta]_2\)，就变成\([C]_1\)中的\([A]_1s+[B]_1r-rs[\delta]_1\)了。因此要验证的公式为： \[ \underbrace{([\alpha]_1+\sum_{i=1}^ma_iu_i(\tau)+r[\delta]_1)}_{[A]_1}\cdot \underbrace{([\beta]_2+\sum_{i=1}^ma_iv_i(\tau)+s[\delta]_2)}_{[B]_2}= [\alpha]_1\cdot[\beta]_2+ \underbrace{\sum_{i=1}^la_i[\Psi_i]_1}_{[X]_1}\cdot[\gamma]_2+ \underbrace{(\sum_{i=l+1}^ma_i[\Psi_i]_1+h(\tau)t(\tau)+[A]_1s+[B]_1r-rs[\delta]_1)}_{[C]_1}\cdot[\delta]_2 \] 其中 \[ \begin{align} \sum_{i=1}^la_i[\Psi_i]_1&=\sum_{i=1}^la_i\cdot\frac{\alpha u_1(\tau) + \beta v_1(\tau) + w_1(\tau)}{\gamma}G_1\\ \sum_{i=l+1}^ma_i[\Psi_i]_1&=\sum_{i=l+1}^ma_i\cdot\frac{\alpha u_1(\tau) + \beta v_1(\tau) + w_1(\tau)}{\delta}G_1\\ h(\tau)t(\tau)&=\sum_{i=0}^{n-2}h_i\cdot\frac{\tau^it(\tau)}{\delta}G_1 \end{align} \] 可见分母的\(\gamma\)和\(\delta\)在pairing时正好被\([\gamma]_2\)和\([\delta]_2\)消掉了。

1.6 最终的Groth16

• 可信设置

  \[\begin{align} \text{random scalars}&\to\alpha,\beta,\tau,\gamma,\delta\\ SRS_{G_1}&\to[\tau^{n-1} G_1, \tau^{n-2} G_1, \cdots, \tau G_1, G_1]\\ SRS_{G_2}&\to[\tau^{n-1} G_2, \tau^{n-2} G_2, \cdots, \tau G_2, G_2]\\ SRS_{h(\tau)t(\tau)}&\to[\frac{\tau^{n-2}t(\tau)}{\delta}G_1,\frac{\tau^{n-3}t(\tau)}{\delta}G_1,\cdots,\frac{\tau t(\tau)}{\delta}G_1, \frac{t(\tau)}{\delta}G_1]\\ [\Psi_1]_1&=\frac{\alpha v_1(\tau) + \beta u_1(\tau) + w_1(\tau)}{\gamma}G_1 \\ [\Psi_2]_1&=\frac{\alpha v_2(\tau) + \beta u_2(\tau) + w_2(\tau)}{\gamma}G_1 \\ &\vdots\\ [\Psi_l]_1&=\frac{\alpha v_l(\tau) + \beta u_l(\tau) + w_l(\tau)}{\gamma}G_1\\ [\Psi_{l+1}]_1&=\frac{\alpha v_{l+1}(\tau) + \beta u_{l+1}(\tau) + w_{l+1}(\tau)}{\delta}G_1 \\ [\Psi_{l+2}]_1&=\frac{\alpha v_{l+2}(\tau) + \beta u_{l+2}(\tau) + w_{l+2}(\tau)}{\delta}G_1 \\ &\vdots\\ [\Psi_m]_1&=\frac{\alpha v_m(\tau) + \beta u_m(\tau) + w_m(\tau)}{\delta}G_1 \end{align}\]

  公开：

  \[ ([\alpha]_1,[\beta]_1,[\beta]_2,[\gamma]_2,[\delta]_1,[\delta]_2,SRS_{G_1},SRS_{G_2},SRS_{h(\tau)t(\tau)},[\Psi_1]_1,[\Psi_2]_1,\cdots, [\Psi_m]_1) \]

• 证明者 \[ \begin{align} [A]_1&=[\alpha]_1+\sum_{i=1}^ma_iu_i(\tau)+r[\delta]_1\\ [B]_2&=[\beta]_2+\sum_{i=1}^ma_iv_i(\tau)+s[\delta]_2\\ [B]_1&=[\beta]_1+\sum_{i=1}^ma_iv_i(\tau)+s[\delta]_1\\ [C]_1&=\sum_{i=l+1}^ma_i[\Psi_i]_1+h(\tau)t(\tau)+[A]_1s+[B]_1r-rs[\delta]_1 \end{align} \] 公开： \[ ([A]_1,[B]_2,[C]_1,[a_1,\cdots,a_l]) \]

• 验证者 \[ \begin{align} &[X]_1=\sum_{i=1}^la_i[\Psi_i]_1\\ [A]_1\cdot[B]_2=[&\alpha]_1\cdot[\beta]_2+[X]_1\cdot[\gamma]_2+[C]_1\cdot[\delta]_2 \end{align} \]

与原文比较，只有个别符号不一样。

1.7 Python实现

请使用Linux环境或WSL运行如下代码，并确保安装了SageMath。

import random
from sage.all import GF, vector, Matrix, PolynomialRing, prod
from py_ecc.bn128 import curve_order, G1, G2, multiply, add, neg, pairing


################################## 参数 ##################################
r = curve_order     # 使用BN254(i.e. BN128)曲线，r是椭圆曲线群的阶，也是有限域的模数
n = 5               # 约束个数
m = 8               # witness长度
l = 3               # 公开的witness长度
F = GF(r)           # 有限域
R_poly = PolynomialRing(F, 'X')     # 多项式环
X = R_poly.gen()                       # 多项式的自变量符号

print(f"n = {n}, m = {m}")

################################## 约束 ##################################
# z1 = 2x^3 + xy - 4
# z2 = xy^3 - 3x

x = F(2)                        # 2
y = F(-1)                       # -1
v1 = x * x                      # 4
v2 = y * y                      # 1
v3 = x * y                      # -2
z1 = 2 * x * v1 + v3 - F(4)     # 10
z2 = v2 * v3 - 3 * x            # -8

witness = vector(F, [1, z1, z2, x, y, v1, v2, v3])
print("witness: ", witness)

################################## R1CS ##################################
class R1CS:
    def __init__(self):
        # Lw * Rw = Ow
        self.L = Matrix(F, [
            [0, 0, 0, 1, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0],
            [0, 0, 0, 1, 0, 0, 0, 0],
            [0, 0, 0, 2, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 1, 0]
        ])
        self.R = Matrix(F, [
            [0, 0, 0, 1, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0],
            [0, 0, 0, 0, 0, 1, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 1]
        ])
        self.O = Matrix(F, [
            [0, 0, 0, 0, 0, 1, 0, 0],
            [0, 0, 0, 0, 0, 0, 1, 0],
            [0, 0, 0, 0, 0, 0, 0, 1],
            [4, 1, 0, 0, 0, 0, 0, -1],
            [0, 0, 1, 3, 0, 0, 0, 0],
        ])
        self.check_r1cs()

    def check_r1cs(self):
        # 检查R1CS是否正确
        Lw = self.L * witness
        Rw = self.R * witness
        Ow = self.O * witness
        Lw_times_Rw = vector(F, [Lw[i] * Rw[i] for i in range(len(Lw))])
        assert Lw_times_Rw == Ow
        print("R1CS检查通过")

################################## QAP ##################################
r1cs = R1CS()

class QAP:
    """
    u_i(x), v_i(x), w_i(x)：公开的
    u(x), v(x), w(x), h(x)：仅证明者持有
    t(x)：公开的
    满足：u(x)v(x) = w(x) + h(x)t(x)
    """
    def __init__(self, r1cs):
        self.u_i = [self.interpolate_column(r1cs.L.column(j)) for j in range(m)]
        self.v_i = [self.interpolate_column(r1cs.R.column(j)) for j in range(m)]
        self.w_i = [self.interpolate_column(r1cs.O.column(j)) for j in range(m)]
        # poly = u_i[6]
        # print(poly)
        # print(poly(F(5)))

        self.u = sum(witness[j] * self.u_i[j] for j in range(m))
        self.v = sum(witness[j] * self.v_i[j] for j in range(m))
        self.w = sum(witness[j] * self.w_i[j] for j in range(m))
        self.t = prod([X - i for i in range(1, n + 1)])
        assert (self.u * self.v - self.w) % self.t == 0
        self.h = (self.u * self.v - self.w) // self.t

        self.check_qap()

    @staticmethod
    def interpolate_column(col):
        # 用点 (1, col[0]), ..., (n, col[n-1]) 插值
        points = [(i + 1, col[i]) for i in range(n)]
        return R_poly.lagrange_polynomial(points)

    def check_qap(self):
        assert self.u * self.v == self.w + self.h * self.t
        print("QAP检查通过")

################################## Trust Setup ##################################
qap = QAP(r1cs)

class CRS:
    def __init__(self, qap):
        # 生成完毕后销毁
        self.__alpha = F(random.randint(0, r - 1))
        self.__beta  = F(random.randint(0, r - 1))
        self.__gamma = F(random.randint(0, r - 1))
        self.__delta = F(random.randint(0, r - 1))
        self.__tau   = F(random.randint(0, r - 1))

        # 公开以下内容
        self.alpha_1 = multiply(G1, int(self.__alpha))
        self.beta_1 = multiply(G1, int(self.__beta))
        self.beta_2 = multiply(G2, int(self.__beta))
        self.gamma_2 = multiply(G2, int(self.__gamma))
        self.delta_1 = multiply(G1, int(self.__delta))
        self.delta_2 = multiply(G2, int(self.__delta))

        self.SRS_1 = [multiply(G1, int(self.__tau ** i)) for i in range(n)]
        self.SRS_2 = [multiply(G2, int(self.__tau ** i)) for i in range(n)]
        self.SRS_ht = [multiply(G1, int(self.__tau ** i * qap.t(self.__tau) / self.__delta)) for i in range(n - 1)]

        self.psi = []
        for i in range(m):
            numerator = self.__alpha * qap.v_i[i](self.__tau) + self.__beta * qap.u_i[i](self.__tau) + qap.w_i[i](self.__tau)
            self.psi.append(multiply(G1, int(numerator / (self.__gamma if i < l else self.__delta))))
        print("CRS生成完成")

################################## Prover ##################################
crs = CRS(qap)

class Prover:
    def __init__(self, crs):
        # salt
        self.__r = F(random.randint(0, r - 1))
        self.__s = F(random.randint(0, r - 1))

        # points
        self.A_1 = add(crs.alpha_1, multiply(crs.delta_1, int(self.__r)))
        self.B_2 = add(crs.beta_2, multiply(crs.delta_2, int(self.__s)))
        self.__B_1 = add(crs.beta_1, multiply(crs.delta_1, int(self.__s)))
        u_coe = qap.u.coefficients(sparse=False)
        v_coe = qap.v.coefficients(sparse=False)
        h_coe = qap.h.coefficients(sparse=False)
        for i in range(n):
            self.A_1 = add(self.A_1, multiply(crs.SRS_1[i], int(u_coe[i])))
            self.B_2 = add(self.B_2, multiply(crs.SRS_2[i], int(v_coe[i])))
            self.__B_1 = add(self.__B_1, multiply(crs.SRS_1[i], int(v_coe[i])))

        self.C_1 = add(multiply(self.A_1, int(self.__s)), multiply(self.__B_1, int(self.__r)))
        self.C_1 = add(self.C_1, multiply(neg(crs.delta_1), int(self.__r * self.__s)))
        for i in range(l, m):
            self.C_1 = add(self.C_1, multiply(crs.psi[i], int(witness[i])))
        for i in range(n - 1):
            self.C_1 = add(self.C_1, multiply(crs.SRS_ht[i], int(h_coe[i])))
        print("证明生成完成")

################################## Verifier ##################################
class Verifier:
    def __init__(self, crs):
        self.X_1 = multiply(crs.psi[0], int(witness[0]))
        for i in range(1, l):
            self.X_1 = add(self.X_1, multiply(crs.psi[i], int(witness[i])))

    def verify(self, crs, A_1, B_2, C_1):
        print("开始验证……")
        left = pairing(B_2, A_1)
        print(f"[A]₁·[B]₂ = {left}")
        right_1 = pairing(crs.beta_2, crs.alpha_1)
        print(f"[α]₁·[β]₂ = {right_1}")
        right_2 = pairing(crs.gamma_2, self.X_1)
        print(f"[X]₁·[γ]₂ = {right_2}")
        right_3 = pairing(crs.delta_2, C_1)
        print(f"[C]₁·[δ]₂ = {right_3}")
        right = right_1 * right_2 * right_3
        assert all(x == y for x, y in zip(left.coeffs, right.coeffs)), "验证失败"
        print("验证成功")


if __name__ == '__main__':
    prover = Prover(crs)
    verifier = Verifier(crs)
    verifier.verify(crs, prover.A_1, prover.B_2, prover.C_1)