Groth16 详解

Groth16算法使得证明者可以在可信设置中利用椭圆曲线点计算二次算术程序，并由验证者快速检查。它使用来自可信设置的辅助椭圆曲线点来防止伪造证明。

前提条件

本文是RareSkills Book of Zero Knowledge Proofs中的一章。假设你已熟悉之前的章节。

表示法

我们将属于$\mathbb{G}_1$椭圆曲线群的一个椭圆曲线点表示为$[x]_1$，属于$\mathbb{G}_2$椭圆曲线群的椭圆曲线点表示为$[x]_2$。$[x]_1$和$[x]_2$之间的一个 pairing 表示为 $[x]_1\bullet[x]2$，并在 $\mathbb{G}{12}$ 中生成一个元素。粗体字母变量如$\mathbf{a}$表示向量，粗体大写字母如$\mathbf{L}$表示矩阵，字段元素（有时非正式地称为“标量”）是小写字母，如$d$。所有算术运算都发生在一个有限域中，特征等于椭圆曲线群的阶。

给定一个算术电路 (ZK Circuit)，我们将其转换为秩 1约束系统(R1CS) $\mathbf{L}\mathbf{a}\circ \mathbf{R}\mathbf{a} = \mathbf{O}\mathbf{a}$，其中矩阵的维度为$n$行和$m$列，见证向量为$\mathbf{a}$。然后，我们可以通过将矩阵的列插值为在$x$值$[1,2,…,n]$上的$y$值，从R1CS转换为二次算术程序(QAP)。由于$\mathbf{L}$，$\mathbf{R}$，和$\mathbf{O}$有$m$列，我们将得到三组$m$个多项式：

$$ \begin{array}{} u_1(x),…,u_m(x) & m \text{ 个在 } m \text{ 列的 } \mathbf{L} \text{ 上插值的多项式}\ v_1(x),…,v_m(x)& m \text{ 个在 } m \text{ 列的 } \mathbf{R} \text{ 上插值的多项式}\ w_1(x),…,w_m(x)& m \text{ 个在 } m \text{ 列的 } \mathbf{O} \text{ 上插值的多项式}\ \end{array} $$

从这个多项式中，我们可以构造一个二次算术程序(QAP)：

$$ \sum_{i=1}^m a_iui(x)\sum{i=1}^m a_ivi(x) = \sum{i=1}^m a_iw_i(x) + h(x)t(x) $$

其中 $$ t(x) = (x – 1)(x – 2)\dots(x – n) $$

$$ h(x) = \frac{\sum_{i=1}^m a_iui(x)\sum{i=1}^m a_ivi(x) – \sum{i=1}^m a_iw_i(x)}{t(x)} $$

如果一个第三方通过tau挤压仪创建结构化参考字符串(srs)，那么证明者可以在隐藏点$\tau$上计算和项 （$\sum a_if_i(x)$项）在QAP中。假设结构化参考字符串的计算如下：

$$ \begin{align} [\Omega{n-1}, \Omega{n-2},\dots,\Omega_2,\Omega_1,G_1] &= [\tau^nG_1,\tau^{n-1}G_1,\dots,\tau G_1,G_1] && \text{对于 } G1 \\ [\Theta{n-1}, \Theta_{n-2},\dots,\Theta_2,\Theta_2,G_2] &= [\tau^nG_2,\tau^{n-1}G_2,\dots,\tau G_2,G_2] && \text{对于 } G2\\ [\Upsilon{n-2},\Upsilon_{n-3},\dots,\Upsilon_1,\Upsilon_0]&=[\tau^{n-2}t(\tau)G_1,\tau^{n-3}t(\tau)G_1,\dots,\tau t(\tau)G_1,t(\tau)G_1] && \text{对于 }h(\tau)t(\tau)\\ \end{align} $$

我们将$f(\tau)$称为在结构化参考字符串$[\tau^dG_1,…,\tau^2G_1,\tau G_1,G_1]$上评估的多项式，通过内积获取：

$$ f(\tau) = \sum_{i=1}^d f_i\Omega_i=\langle[fd, f{d-1},…,f_1,f_0],[\Omegad,\Omega{d-1},…,G_1]\rangle $$

或者对于 $\mathbb{G}_2$的srs：

$$ f(\tau) = \sum_{i=1}^d f_i\Theta_i=\langle[fd, f{d-1},…,f_1,f_0],[\Thetad,\Theta{d-1},…,G_1]\rangle $$

$f(\tau)$是上述表达式的简写，生成一个椭圆曲线点。这并不意味着证明者知道$\tau$。

证明者可以通过计算来评估其QAP在可信设置：

$$ \begin{align} [A]1 &= \sum{i=1}^m a_iu_i(\tau)\ [B]2 &= \sum{i=1}^m a_iv_i(\tau)\ [C]1 &= \sum{i=1}^m a_iw_i(\tau) + h(\tau)t(\tau) \end{align} $$

此计算的详细信息在我们的教程在椭圆曲线上进行二次算术程序中讨论。

如果QAP是平衡的，则以下等式成立：

$$ [A]_1\bullet[B]_2 \stackrel{?}= [C]_1\bullet G_2 $$

动机

仅仅提供$([A]_1, [B]_2, [C]_1)$并不能令人信服地证明证明者知道$\mathbf{a}$使得QAP是平衡的。

证明者可以随意虚构值$a$，$b$，$c$使得$ab = c$，计算

$$ \begin{align} [A]_1 &= aG_1\ [B]_2 &= bG_2\ [C]_1 &= cG_1 \end{align} $$

并将这些作为椭圆曲线点$[A]_1$，$[B]_2$，$[C]_1$呈现给验证者。

因此，验证者无法得知$([A]_1, [B]_2, [C]_1)$是否是满足的QAP的结果。

我们需要迫使证明者诚实，而不会引入太多的计算开销。第一个能做到这一点的算法是“Pinocchio: Nearly Practical Verifiable Computation”。这个算法足够可用，使得ZCash能基于其第一个版本的区块链。

然而，Groth16能够在更少的步骤中完成同样的事情，并且该算法至今仍被广泛使用，因为自其之后没有其他算法能够为验证步骤提供如此高效的算法（尽管其他算法已消除了可信设置或显著减少了证明者的计算量）。

2024更新： 一篇题为“Polymath: Groth16 is not the limit”的论文在《密码学》中发布，展示了一种算法，其所需的验证者步骤少于Groth16。然而，目前尚无已知的该算法的实现。

防止伪造第 1 部分：引入 $\alpha$ 和 $\beta$

一个“不可解决”的验证公式

假设我们将验证公式更新为以下内容：

$$[A]_1 \bullet [B]2 \stackrel{?}= [D]{12} + [C]_1\bullet G_2$$

注意我们为方便起见使用了$G{12}$群的加法符号。_

这里，$[D]{12}$是来自$G{12}$的一个元素，并且有一个未知的离散对数。

我们现在展示，验证者在不知道$[D]_{12}$的离散对数的情况下，不可能提供方程$([A]_1, [B]_2, [C]_1)$的解。

攻击 1：伪造A和B并推导出C

假设证明者随机选择$a’$和$b’$生成$[A]{1}$和$[B]{2}$，并试图推导出一个与验证者公式兼容的值$[C’]$。

$$[A]_1 \bullet [B]2 \stackrel{?}= [D]{12} + [C]_1\bullet G_2$$

知道$[A]{1}$和$[B]{2}$的离散对数，恶意证明者尝试通过以下方式解出$[C’]$：

$$ \begin{align} \underbrace{[A]_1\bullet [B]2 – [D]{12}}{\chi{12}}=[C’]_1\bullet G2\ [\chi]{12}=[C’]_1\bullet G_2 \end{align} $$

最后一行要求证明者解决$\chi_{12}$的离散对数，因此他们不能计算出$[C’]_1$的有效离散对数。

攻击 2：伪造C并推导出A和B

这里证明者选择一个随机点$c’$并计算$[C’]_1$。因为他们知道$c’$，他们可以尝试发现$A’$和$B’$的兼容组合，使得

$$ \begin{align} [A]_1 \bullet [B]2 &\stackrel{?}= \underbrace{[D]{12} + [C]_1\bullet G2}{[\zeta]_{12}}\ [A]_1 \bullet [B]2 &\stackrel{?}=[\zeta]{12} \end{align} $$

这要求证明者在给定$[\zeta]{12}$的情况下想出一个$[A]{1}$和$[B]{2}$以生成$[\zeta]{12}$。

与离散对数问题类似，我们依赖未经证明的加密假设，即该计算（将$\mathbb{G}_{12}$中的一个元素分解成$\mathbb{G}_1$和$\mathbb{G}2$元素）是不可行的。在这种情况下，我们无法将$[\zeta]{12}$分解为$[A]{1}$和$[B]{2}$的假设称为双线性Diffie-Hellman假设。感兴趣的读者可以参见关于决策Diffie-Hellman假设 的相关讨论。

（未经证明并不意味着不可靠。如果你能找到证明或反驳该假设的方法，将会赢得名声和财富！在实践中，目前没有已知的方法将$[\zeta]{12}$分解为$[A]{1}$和$[B]_{2}$，并且相信这是计算上不可行的。）

$\alpha$和$\beta$的用法

实际上，Groth16不使用项$[D]_{12}$。相反，可信设置生成两个随机标量$\alpha$和$\beta$，并发布计算出的椭圆曲线点$([\alpha]_1,[\beta]_2)$：

$$ \begin{align} [α]_1 &= α G_1 \ [β]_2 &= β G_2 \end{align} $$

我们之前所称的$[D]_{12}$实际上就是$[\alpha]_1 \bullet [\beta]_2$。

重新推导证明和验证公式

为了使验证公式 $[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1\bullet[\beta]_2 + [C]_1\bullet G_2$“可解”，我们需要修改我们的QAP公式，以包含$\alpha$和$\beta$。

$$ \sum_{i=1}^m a_iui(x)\sum{i=1}^m a_ivi(x) = \sum{i=1}^m a_iw_i(x) + h(x)t(x) $$

现在考虑我们如果将项$\theta$和$\eta$引入到方程的左侧会发生什么：

$$(\boxed{\theta}+\sum_{i=1}^m a_iui(x))(\boxed{\eta} +\sum{i=1}^m a_iv_i(x)) =$$

$$=\boxed{\theta\eta} + \boxed{\theta}\sum_{i=1}^m a_ivi(x) + \boxed{\eta}\sum{i=1}^m a_iui(x) + \sum{i=1}^m a_iui(x)\sum{i=1}^m a_iv_i(x)$$

我们可以使用原始QAP定义来替换右侧的最后项： $$=\theta\eta + \theta\sum_{i=1}^m a_ivi(x) + \eta\sum{i=1}^m a_iui(x) + \boxed{\sum{i=1}^m a_iui(x)\sum{i=1}^m a_iv_i(x)}$$

$$=\theta\eta + \theta\sum_{i=1}^m a_ivi(x) + \eta\sum{i=1}^m a_iui(x) + \boxed{\sum{i=1}^m a_iw_i(x) + h(x)t(x)}$$

现在我们可以引入一个“扩展”QAP，其定义如下：

$$(\theta+\sum_{i=1}^m ui(x))(\eta +\sum{i=1}^m vi(x)) =\theta\eta + \theta\sum{i=1}^m a_ivi(x) + \eta\sum{i=1}^m a_iui(x) + \sum{i=1}^m a_iw_i(x) + h(x)t(x)$$

作为我们正在进行的概述，如果我们用$[\alpha]_1$替换$\theta$，用$[\beta]_2$替换$\eta$，我们得到早期的更新验证公式：

$$[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [C]_1\bullet G_2$$

其中

$$ \underbrace{([\alpha]1+\sum{i=1}^m a_iui(\tau))}{[A]_1}\underbrace{([\beta]2 +\sum{i=1}^m a_ivi(\tau))}{[B]_2} =[\alpha]_1\bullet[\beta]2 + (\underbrace{\alpha\sum{i=1}^m a_ivi(\tau) + \beta\sum{i=1}^m a_iui(\tau) + \sum{i=1}^m a_iwi(\tau) + h(\tau)t(\tau)}{[C]_1}) \bullet G_2$$

证明者可以在不知$\tau$，$\alpha$，或$\beta$的情况下计算$[A]_1$和$[B]_2$。Given the structured reference string (powers of $\tau$) and the elliptic curve points $([\alpha]_1,[\beta]_2)$, the prover computes $[A]_1$ and $[B]_2$ as

$$ \begin{align} [A]_1 &= [\alpha]1 + \sum{i=1}^m a_iu_i(\tau)\ [B]_2 &= [\beta]2 + \sum{i=1}^m a_iv_i(\tau)\ \end{align} $$

这里$a_iu_i(\tau)$并不意味着证明者知道$\tau$。证明者使用结构化参考字符串$[\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1]$来计算$u_i(\tau)$，其中$i=1,2,\dots,m$以及$G_2$的srs用于$[B]_2$。

然而，目前不可能在不知道$\alpha$和$\beta$的情况下计算$[C]_1$。证明者不能将$[\alpha]_1$与$\sum a_iu_i(\tau)$以及$[\beta]_2$与$\sum a_ivi(\tau)$配对，因为那会生成一个$\mathbb{G}{12}$点，而证明者需要一个$\mathbb{G}_1$点来计算$[C]_1$。

相反，可信设置需要预先计算用于扩展QAP中有问题的$C$项的$m$个多项式。

$$\alpha\sum_{i=1}^m a_ivi(\tau) + \beta\sum{i=1}^m a_iui(\tau) + \sum{i=1}^m a_iw_i(\tau)$$

通过一些代数运算，我们将和项组合为一个单一的和：

$$=\sum_{i=1}^m (\alpha a_iv_i(\tau)+\beta a_iu_i(\tau) + a_iw_i(\tau))$$

并将$a_i$提取出来：

$$=\sum_{i=1}^m a_i\boxed{(\alpha v_i(\tau)+\beta u_i(\tau) + w_i(\tau))}$$

可信设置可以从上面框起来的项创建$m$个在$\tau$上评估的多项式，证明者可以用它来计算该和。确切的细节将在下一部分中显示。

目前算法的总结

可信设置步骤

具体来说，可信设置计算如下： $$ \begin{align} \alpha,\beta,\tau &\leftarrow \text{随机标量}\ [\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1] &\leftarrow \text{srs for } \mathbb{G}_1\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \text{srs for } \mathbb{G}_2\ [\tau^{n-2}t(\tau),\tau^{n-3}t(\tau),\dots,\tau t(\tau),t(\tau)] &\leftarrow \text{srs for }h(\tau)t(\tau)\ [\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,\text{srs}{G1},\text{srs}{G_2},[\Psi_1]_1,[\Psi_2]_1,\dots,[\Psi_m]_1)$$

证明者步骤

证明者计算

$$ \begin{align} [A]_1 &= [\alpha]1 + \sum{i=1}^m a_iu_i(\tau)\ [B]_2 &= [\beta]2 + \sum{i=1}^m a_iv_i(\tau)\ [C]1 &= \sum{i=1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\ \end{align} $$

注意我们将“有问题”的多项式

$$=\sum_{i=1}^m a_i\boxed{(\alpha v_i(\tau)+\beta u_i(\tau) + w_i(\tau))}$$

（包含$\alpha$和$\beta$的那个）替换为了

$$\sum_{i=1}^m a_i[\Psi_i]_1$$

验证者步骤

验证者计算：

$$[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [C]_1\bullet G_2$$

支持公共输入

至今，验证者公式不支持公共输入，即使得部分见证公开。

根据惯例，见证的公共部分是向量$\mathbf{a}$的前$\ell$个元素。为了使这些元素公开，证明者只需公开它们：

$$[a_1, a2, \dots, a\ell]$$

验证者需要测试这些值是否实际上被使用，验证者必须执行证明者原本在计算的一部分。

具体而言，证明者计算：

$$ \begin{align} [A]_1 &= [\alpha]1 + \sum{i=1}^m a_iu_i(\tau)\ [B]_2 &= [\beta]2 + \sum{i=1}^m a_iv_i(\tau)\ [C]1 &= \sum{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\ \end{align} $$

注意只有$[C]_1$的计算被更改——证明者仅使用从$\ell + 1$到$m$的$a_i$和$\Psi_i$项。

验证者计算和的前$\ell$项：

$$[X]1=\sum{i=1}^\ell a_i\Psi_i$$

验证公式为：

$$[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet G_2 + [C]_1\bullet G_2$$

第 2 部分：使用 $\gamma$ 或 $\delta$ 将公共输入与私有输入分开

通过滥用 $\Psi_i$ 来伪造证明，$i\leq\ell$

上述方程的假设是证明者只利用$\Psi_{\ell+1}$到$\Psi_m$来计算$[C]_1$，但没有任何东西阻止不诚实的证明者利用$\Psi1$到$\Psi{\ell}$来计算$[C]_1$，导致伪造的证明。

例如，这里是我们当前的验证方程：

$$[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]2 + \sum{i=1}^\ell a_i\Psi_i + [C]_1\bullet G_2$$

如果我们在内部展开$C$项，则得到如下结果：

$$[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]2 + \sum{i=1}^\ell a_i\Psii + \underbrace{(\sum{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau))}_C \bullet G_2$$

假设例如且不失一般性，$\mathbf{a} = [1,2,3,4,5]$ 并且 $\ell=3$。在那种情况下，见证的公共部分是$[1,2,3]$，私有部分是$[4,5]$。

最终方程如下：

$$[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + (1\Psi_1+2\Psi_2+3\Psi_3)\bullet G_2 + \underbrace{(4\Psi_4 + 5\Psi_5 + h(\tau)t(\tau))}_C \bullet G_2$$

然而，没有什么能阻止证明者创建一个有效的公共见证部分，例如$[1,2,0]$，并将零化的公共部分移动到私有部分的计算中，如下所示：

$$[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + (1\Psi_1+2\Psi_2+\boxed{0\Psi_3})\bullet G_2 + \underbrace{(\boxed{3\Psi_3}+4\Psi_4 + 5\Psi_5 + h(\tau)t(\tau))}_C \bullet G_2$$

上述方程是有效的，但见证并不一定满足原始约束。

因此，我们需要防止证明者在计算$[C]_1$时使用$\Psi1$到$\Psi{\ell}$。

引入 $\gamma$ 和/或 $\delta$

为避免上述问题，可信设置引入了一个新的标量：$\gamma$ 或 $\delta$，强制 $\Psi_{\ell+1}$到$\Psim$与 $\Psi{1}$到 $\Psi_{\ell}$分开。为此，可信设置将（乘以模逆）私有项（构成$[C]_1$）通过$\delta$和/或公共项（构成$[X]_1$，验证者计算和的总和）通过$\gamma$进行划分。

因为$h(\tau)t(\tau)$项包含在$[C]_1$中，这些干扰项也需要通过$\delta$划分。如果$\delta$和$\gamma$其中一个具有未知的离散对数，则前面描述的伪造以及其他可能的方法将会被避免。这种方法被Zcash的基于Sapling的可信设置中使用，其中$\gamma$被简单地留在$G_2$中，而$\delta$仍从$G_2$更新到稍后的可信设置阶段的随机值。

$$ \begin{align} \alpha,\beta,\tau,\gamma,\delta &\leftarrow \text{随机标量}\ [\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1] &\leftarrow \text{srs for } \mathbb{G}_1\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \text{srs for } \mathbb{G}_2\ [\frac{\tau^{n-2}t(\tau)}{\delta},\frac{\tau^{n-3}t(\tau)}{\delta},\dots,\frac{\tau t(\tau)}{\delta}, \frac{t(\tau)}{\delta}] &\leftarrow \text{srs for }h(\tau)t(\tau)\ \ &\text{ 见证的公共部分} \ [\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}G1\ &\vdots\ [\Psi\ell]_1 &= \frac{\alpha v_m(\tau) + \beta u_m(\tau) + w_m(\tau)}{\gamma}G1\ \ &\text{ 见证的私有部分}\ [\Psi{\ell+1}]1 &= \frac{\alpha v{\ell+1}(\tau) + \beta u{\ell+1}(\tau) + w{\ell+1}(\tau)}{\delta}G1\ [\Psi{\ell+2}]1 &= \frac{\alpha v{\ell+2}(\tau) + \beta u{\ell+2}(\tau) + w{\ell+2}(\tau)}{\delta}G1\ &\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,\text{srs}{G1},\text{srs}{G_2},[\Psi_1]_1,[\Psi_2]_1,\dots,[\Psi_m]_1)$$

证明者步骤与以前相同：

$$ \begin{align} [A]_1 &= [\alpha]1 + \sum{i=1}^m a_iu_i(\tau)\ [B]_2 &= [\beta]2 + \sum{i=1}^m a_iv_i(\tau)\ [C]1 &= \sum{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\ \end{align} $$

而验证者步骤现在还包括通过$[\gamma]_2$和/或$[\delta]_2$的配对，以抵消分母：

$$[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2$$

或者
$$[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [G]_2 + [C]_1\bullet [\delta]_2$$

第 3 部分：强制真正的零知识：r 和 s

我们的方案尚未真正实现零知识。如果攻击者能够猜测我们的见证向量（如果有效输入只有一个小范围，例如特权地址的秘密投票），他们可以通过将其构建的证明与原始证明进行比较，从而验证他们的猜测。

作为一个简单的例子，假设我们的声明是$x_1$和$x_2$必须为$0$或$1$。相应的算术电路将是

$$ \begin{align} x_1 (x_1 – 1) = 0\ x_2 (x_2 – 1) = 0 \end{align} $$

攻击者只需要猜测四种组合，就可以找出见证是什么。也就是说，他们猜测一个见证，生成证明，并查看他们的答案是否与原始证明匹配。

为了防止猜测，证明者需要“加盐”其证明，验证方程需要修改以容纳盐。

证明者从随机字段元素$r$和$s$中进行采样，并将它们添加到$A$和$B$中，以使得见证不可猜测——攻击者将不得不同时猜测见证和盐$r$和$s$：

$$ \begin{align} [A]_1 &= [\alpha]1 + \sum{i=1}^m a_iu_i(\tau) + r[\delta]_1\ [B]_2 &= [\beta]2 + \sum{i=1}^m a_iv_i(\tau) + s[\delta]_2\ [B]_1 &= [\beta]1 + \sum{i=1}^m a_iv_i(\tau) + s[\delta]_1\ [C]1 &= \sum{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau) + As+Br-rs[\delta]_1\ \end{align} $$

为了推导最终的验证公式，让我们暂时忽略我们不知道希腊字母项的离散对数，并计算验证方程的左侧$AB$：

$$\underbrace{(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)}A \underbrace{(\beta + \sum{i=1}^m a_iv_i(x) + s\delta)}_B$$

展开这些项我们得到：

$$ \alpha\beta+\alpha\sum_{i=1}^m a_ivi(x)+\alpha s\delta + \beta\sum{i=1}^m a_iui(x) + \sum{i=1}^m a_iui(x)\sum{i=1}^m a_ivi(x)+\sum{i=1}^m a_iui(x) s\delta + r\delta\beta + r\delta\sum{i=1}^m a_iv_i(x) + r\delta s\delta $$

我们可以选择出$C$的原始项

$$ \alpha\beta+\boxed{\alpha\sum_{i=1}^m a_ivi(x)}+\alpha s\delta + \boxed{\beta\sum{i=1}^m a_iui(x)} + \boxed{\sum{i=1}^m a_iui(x)\sum{i=1}^m a_ivi(x)}+\sum{i=1}^m a_iui(x) s\delta + r\delta\beta + r\delta\sum{i=1}^m a_iv_i(x) + r\delta s\delta $$

并将它们在左侧组合，右侧留新的项：

$$ \alpha\beta + \boxed{\alpha\sum_{i=1}^m a_ivi(x) + \beta\sum{i=1}^m a_iui(x) + \sum{i=1}^m a_iui(x)\sum{i=1}^m a_ivi(x)}+ \underline{\alpha s\delta + \sum{i=1}^m a_iui(x) s\delta + r\delta\beta + r\delta\sum{i=1}^m a_iv_i(x) + r\delta s\delta} $$

我们进一步重新排列下面的项，以$As\delta$和$Br\delta$的形式重写它们。同时我们还将$r\delta s\delta$分割为$rs\delta^2 + rs\delta^2 – rs\delta^2 $：

$$ =\alpha s\delta + \sum_{i=1}^m a_iui(x) s\delta + rs\delta^2 + r\delta\beta + r\delta\sum{i=1}^m a_iv_i(x) + rs\delta^2 – rs\delta^2 $$

将$s$和$r$的项组合：

$$ =(\alpha s\delta + \sum_{i=1}^m a_iui(x) s\delta + rs\delta^2) + (r\delta\beta + r\delta\sum{i=1}^m a_iv_i(x) + rs\delta^2) – rs\delta^2 $$

提取出$s\delta$和$r\delta$：

$$ =\underbrace{(\alpha+ \sum_{i=1}^m a_iui(x) + r\delta)s\delta}{As\delta} + \underbrace{(\beta + \sum_{i=1}^m a_ivi(x) + s\delta)r\delta}{Br\delta} – rs\delta^2 $$替换 $A$ 和 $B$：$$ =As\delta + Bs\delta – rs\delta $$

所以我们的最终方程是

$$(\alpha + \sum_{i=1}^m a_iui(x) + r\delta)(\beta + \sum{i=1}^m a_ivi(x) + s\delta)=\alpha\beta+\sum{i=1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x) + As\delta + Bs\delta – rs\delta$$

我们现在将其划分为公共部分和私有部分：

$$(\alpha + \sum_{i=1}^m a_iui(x) + r\delta)(\beta + \sum{i=1}^m a_ivi(x) + s\delta)=\alpha\beta+\underbrace{\sum{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+wi(x))}\text{公共} + \underbrace{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+wi(x)) + h(x)t(x) + As\delta + Bs\delta – rs\delta}\text{私有}$$

我们希望公共部分和私有部分分别由 $\gamma$ 和 $\delta$ 分隔：

$$(\alpha + \sum_{i=1}^m a_iui(x) + r\delta)(\beta + \sum{i=1}^m a_ivi(x) + s\delta)=\alpha\beta+\gamma\frac{\sum{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+wi(x))}{\gamma} + \delta\frac{\sum{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x) + As\delta + Bs\delta – rs\delta}{\delta}$$

$\delta$ 在某些项中被消去：

$$(\alpha + \sum_{i=1}^m a_iui(x) + r\delta)(\beta + \sum{i=1}^m a_ivi(x) + s\delta)=\alpha\beta+\gamma\frac{\sum{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+wi(x))}{\gamma} + \delta\frac{\sum{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x)}{\delta} + As + Bs – rs\delta$$

我们现在将此方程分为验证者部分和证明者部分。框选的项是验证者部分，下划线的项是证明者提供的项：

$$\underbrace{(\alpha + \sum_{i=1}^m a_iui(x) + r\delta)}{[A]1}\underbrace{(\beta + \sum{i=1}^m a_ivi(x) + s\delta)}{[B]2}=\boxed{\alpha\beta}+\boxed{\gamma}\boxed{\frac{\sum{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+wi(x))}{\gamma}} + \boxed{\delta}\underbrace{\frac{\sum{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+wi(x)) + h(x)t(x)}{\delta} + As + Bs – rs\delta}{[C]_1}$$

Groth16 证明算法

我们现在准备展示 Groth16 算法的全过程。

受信任的设置

$$\begin{align} \alpha,\beta,\tau,\gamma,\delta &\leftarrow \text{随机标量}\\ [\tau^{n-1}G_1,\tau^{n-2}G_1,\dots,\tau G_1,G_1] &\leftarrow \text{srs for } \mathbb{G}_1\\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \text{srs for } \mathbb{G}_2\\ [\frac{\tau^{n-2}t(\tau)}{\delta},\frac{\tau^{n-3}t(\tau)}{\delta},\dots,\frac{\tau t(\tau)}{\delta}, \frac{t(\tau)}{\delta}] &\leftarrow \text{srs for }h(\tau)t(\tau)\\ \\ &\text{见证的公共部分}\\ [\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}G1\\ &\vdots\\ [\Psi\ell]_1 &= \frac{\alpha v_m(\tau) + \beta u_m(\tau) + w_m(\tau)}{\gamma}G1\\ \\ &\text{见证的私有部分}\\ [\Psi{\ell+1}]1 &= \frac{\alpha v{\ell+1}(\tau) + \beta u{\ell+1}(\tau) + w{\ell+1}(\tau)}{\delta}G1\\ [\Psi{\ell+2}]1 &= \frac{\alpha v{\ell+2}(\tau) + \beta u{\ell+2}(\tau) + w{\ell+2}(\tau)}{\delta}G1\\ &\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,\text{srs}{G1},\text{srs}{G_2},[\Psi_1]_1,[\Psi_2]_1,\dots,[\Psi_m]_1)$$

证明者步骤

证明者有一个见证 $\mathbf{a}$ 并生成随机标量 $r$ 和 $s$。 $$\begin{align} [A]_1 &= [\alpha]1 + \sum{i=1}^m a_iu_i(\tau)+r[\delta]_1\\ [B]_1 &= [\beta]1 + \sum{i=1}^m a_iv_i(\tau)+s[\delta]_1\\ [B]_2 &= [\beta]2 + \sum{i=1}^m a_iv_i(\tau)+s[\delta]_2\\ [C]1 &= \sum{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)+[A]_1s+[B]_2r-rs[\delta]_1\\ \end{align}$$

证明者发布 $([A]_1, [B]_2, [C]_1, [a_1,…,a\ell])$。

验证者步骤

验证者检查

$$ \begin{align} [X]1&=\sum{i=1}^\ell a_i\Psi_i\\ [A]_1\bullet[B]_2 &\stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2 \end{align} $$

在 Solidity 中验证 Groth16

此时，你有足够的知识来理解 Solidity 中的证明验证代码。这里是 Tornado Cash 的证明验证代码。鼓励读者仔细阅读源代码。如果读者对 Solidity 汇编编程感到熟悉，那么理解该源代码将不会困难，因为变量名与本文中使用的一致。

在 Solana 上也有 Groth16 的库支持。

需要注意的安全问题

Groth16 是可变的

Groth16 证明是可变的。给定一个有效证明

$([A]_1, [B]_2, [C]_1)$，攻击者可以计算 $[A]_1$ 和 $[B]_2$ 的点相反数并呈现新的证明为 $([A’]_1, [B’]_2, [C]_1)$，其中 $[A’]_1 = \mathsf{neg}([A]_1)$ 和 $[B’]_2 = \mathsf{neg}([B]_2)$。

要看到 $[A]_1\bullet[B]_2 = [A’]_1\bullet[B’]_2$，考虑以下代码：

from py_ecc.bn128 import G1, G2, multiply, neg, eq, pairing

## 任意选择
x = 10
y = 100
A = multiply(G1, x)
B = multiply(G2, y)

A_p = neg(A)
B_p = neg(B)

assert eq(pairing(B, A), pairing(B_p, A_p))

直观上，攻击者将 $A$ 和 $B$ 乘以 $-1$，并且 $(-1)\times(-1)$ 在配对运算中相互抵消。

因此，如果验证公式接受 $$[A]_1\bullet[B]_2 \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2$$

那么它也会接受

$$\mathsf{neg}([A]_1)\bullet\mathsf{neg}([B]_2) \stackrel{?}= [\alpha]_1 \bullet [\beta]_2 + [X]_1\bullet [\gamma]_2 + [C]_1\bullet [\delta]_2$$

针对这种攻击的防御将在以下部分中描述。

你可以在这篇 文章 中看到此攻击的概念证明。

证明者可以为相同的见证创建无限数量的证明

这并不算是一个“安全问题”——这是实现零知识所必需的。然而，应用程序需要一种机制来跟踪已经被证明的事实，而不能依赖于证明的唯一性来实现这一点。

通过 RareSkills 学习更多

我们能够免费发布这样的材料，依赖于我们的学生的持续支持。考虑报名参加我们的 零知识训练营、Web3 训练营，或在 RareTalent 找工作。

首次发布于 2023 年 8 月 31 日

• 原文链接： rareskills.io/post/groth...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～