Groth16 详解

Last updated on Mar 16, 2026

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电路），我们将其转换为秩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) & 对 \mathbf{L} 的 m 列进行插值得到的 m 个多项式\\ v_1(x),...,v_m(x)& 对 \mathbf{R} 的 m 列进行插值得到的 m 个多项式\\ w_1(x),...,w_m(x)& 对 \mathbf{O} 的 m 列进行插值得到的 m 个多项式\\ \end{array}

由此，我们可以构造一个二次算术程序 (QAP)：

\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(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_iu_i(x)\sum_{i=1}^m a_iv_i(x) - \sum_{i=1}^m a_iw_i(x)}{t(x)}

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

\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] && G_1 \text{ 的 srs} \\ [\Theta_{n-1}, \Theta_{n-2},\dots,\Theta_2,\Theta_1,G_2] &= [\tau^nG_2,\tau^{n-1}G_2,\dots,\tau G_2,G_2] && G_2 \text{ 的 srs}\\ [\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] && h(\tau)t(\tau) \text{ 的 srs}\\ \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[f_d, f_{d-1},...,f_1,f_0],[\Omega_d,\Omega_{d-1},...,G_1]\rangle

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

f(\tau) = \sum_{i=1}^d f_i\Theta_i=\langle[f_d, f_{d-1},...,f_1,f_0],[\Theta_d,\Theta_{d-1},...,G_2]\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*}

此计算的详细信息在我们的教程 Quadratic Arithmetic Programs over Elliptic Curves 中有讨论。

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

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

动机

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

证明者可以简单地编造出满足 $ab = c$ 的值 $a$ 、 $b$ 、 $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]₁$ 和 $[B]₂$ ，并试图推导出一个与验证者公式兼容的值 $[C']$ 。

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

知道 $[A]₁$ 和 $[B]₂$ 的离散对数后，恶意的证明者试图通过以下计算求解 $[C']$

\begin{align*}\underbrace{[A]_1\bullet [B]_2 - [D]_{12}}_{\chi_{12}}=[C']_1\bullet G_2\\ [\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 G_2}_{[\zeta]_{12}}\\ [A]_1 \bullet [B]_2 &\stackrel{?}=[\zeta]_{12} \end{align*}

这要求证明者在给定 $[\zeta]_{12}$ 的情况下，想出一对 $[A]₁$ 和 $[B]₂$ ，它们配对后能产生 $[\zeta]_{12}$ 。

与离散对数问题类似，我们依赖于未经证实的密码学假设：这种计算（将 $\mathbb{G}_{12}$ 中的元素分解为一个 $\mathbb{G}_1$ 和一个 $\mathbb{G}_2$ 元素）是不可行的。在这种情况下，我们无法将 $[\zeta]_{12}$ 分解为 $[A]₁$ 和 $[B]₂$ 的假设被称为双线性 Diffie-Hellman 假设。感兴趣的读者可以参阅关于判定性 Diffie-Hellman 假设 (Decisional Diffie-Hellman Assumption) 的相关讨论。

（未经证实并不意味着不可靠。如果你能找到证明或反驳这个假设的方法，名誉和财富都在等着你！在实践中，没有已知的方法可以将 $[\zeta]_{12}$ 分解为 $[A]₁$ 和 $[B]₂$ ，并且人们相信在计算上这是不可行的。）

$\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_iu_i(x)\sum_{i=1}^m a_iv_i(x) = \sum_{i=1}^m a_iw_i(x) + h(x)t(x)

现在考虑如果我们在等式左侧引入项 $\theta$ 和 $\eta$ 会发生什么：

\left(\boxed{\theta}+\sum_{i=1}^m a_iu_i(x)\right)\left(\boxed{\eta} +\sum_{i=1}^m a_iv_i(x)\right) =

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

我们可以使用原始的 QAP 定义来替换最右侧的项：

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

=\theta\eta + \theta\sum_{i=1}^m a_iv_i(x) + \eta\sum_{i=1}^m a_iu_i(x) + \boxed{\sum_{i=1}^m a_iw_i(x) + h(x)t(x)}

现在我们可以引入一个具有以下定义的“扩展版” QAP：

\left(\theta+\sum_{i=1}^m a_iu_i(x)\right)\left(\eta +\sum_{i=1}^m a_iv_i(x)\right) =\theta\eta + \theta\sum_{i=1}^m a_iv_i(x) + \eta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iw_i(x) + h(x)t(x)

为了让大家提前窥见我们接下来的目标，如果我们将 $\theta$ 替换为 $[\alpha]_1$ ，将 $\eta$ 替换为 $[\beta]_2$ ，我们就能得到前面更新后的验证公式：

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

其中

\underbrace{\left([\alpha]_1+\sum_{i=1}^m a_iu_i(\tau)\right)}_{[A]_1}\underbrace{\left([\beta]_2 +\sum_{i=1}^m a_iv_i(\tau)\right)}_{[B]_2} =[\alpha]_1\bullet[\beta]_2 + \underbrace{\left(\alpha\sum_{i=1}^m a_iv_i(\tau) + \beta\sum_{i=1}^m a_iu_i(\tau) + \sum_{i=1}^m a_iw_i(\tau) + h(\tau)t(\tau)\right)}_{[C]_1} \bullet G_2

证明者可以在不知道 $\tau$ 、 $\alpha$ 或 $\beta$ 的情况下计算 $[A]_1$ 和 $[B]_2$ 。给定结构化参考字符串（ $\tau$ 的幂）以及椭圆曲线点 $([α]_1,[β]_2)$ ，证明者按如下方式计算 $[A]_1$ 和 $[B]_2$

\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]$ 为 $i=1,2,\dots,m$ 计算 $u_i(\tau)$ ，并使用 $G_2$ srs 计算 $[B]_2$ 。

但是，目前在不知道 $\alpha$ 和 $\beta$ 的情况下是不可能计算出 $[C]_1$ 的。证明者无法将 $[\alpha]_1$ 与 $\sum a_iu_i(\tau)$ 配对，也无法将 $[\beta]_2$ 与 $\sum a_iv_i(\tau)$ 配对，因为那将创建一个 $\mathbb{G}_{12}$ 点，而证明者为求 $[C]_1$ 需要的是一个 $\mathbb{G}_1$ 点。

相反，可信设置需要为扩展 QAP 中存在问题的 $C$ 项预计算出 $m$ 个多项式。

\alpha\sum_{i=1}^m a_iv_i(\tau) + \beta\sum_{i=1}^m a_iu_i(\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 \mathbb{G}_1 \text{ 的 srs}\\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \mathbb{G}_2 \text{ 的 srs}\\ [\tau^{n-2}t(\tau)G_1,\tau^{n-3}t(\tau)G_1,\dots,\tau t(\tau)G_1,t(\tau)G_1] &\leftarrow h(\tau)t(\tau) \text{ 的 srs}\\ [\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,G_1 \text{ 的 srs},G_2 \text{ 的 srs},h(\tau)t(\tau) \text{ 的 srs},[\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, a_2, \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$ 将公开输入和私有输入分开

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

上述等式中的假设是，证明者只使用 $\Psi_{\ell+1}$ 到 $\Psi_m$ 来计算 $[C]_1$ ，但没有任何机制能阻止不诚实的证明者使用 $\Psi_1$ 到 $\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\Psi_i + \underbrace{\left(\sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\right)}_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 G2 + \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 G2 + \underbrace{(\boxed{3\Psi_3}+4\Psi_4 + 5\Psi_5 + h(\tau)t(\tau))}_C \bullet G_2

上面的等式是有效的，但见证却不一定满足原始约束。

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

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

为了避免上述问题，可信设置引入了一个新的标量： $\gamma$ 或 $\delta$ ，以强行将 $\Psi_{\ell+1}$ 到 $\Psi_m$ 与 $\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 \mathbb{G}_1 \text{ 的 srs}\\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \mathbb{G}_2 \text{ 的 srs}\\ \left[\frac{\tau^{n-2}t(\tau)}{\delta}G_1,\frac{\tau^{n-3}t(\tau)}{\delta}G_1,\dots,\frac{\tau t(\tau)}{\delta}G_1, \frac{t(\tau)}{\delta}G_1\right] &\leftarrow h(\tau)t(\tau) \text{ 的 srs}\\ \\ &\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}G_1\\ &\vdots\\ [\Psi_\ell]_1 &= \frac{\alpha v_\ell(\tau) + \beta u_\ell(\tau) + w_\ell(\tau)}{\gamma}G_1\\ \\ &\text{见证的私有部分}\\ [\Psi_{\ell+1}]_1 &= \frac{\alpha v_{\ell+1}(\tau) + \beta u_{\ell+1}(\tau) + w_{\ell+1}(\tau)}{\delta}G_1\\ [\Psi_{\ell+2}]_1 &= \frac{\alpha v_{\ell+2}(\tau) + \beta u_{\ell+2}(\tau) + w_{\ell+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,G_1 \text{ 的 srs},G_2 \text{ 的 srs},h(\tau)t(\tau) \text{ 的 srs},[\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

第 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*}

攻击者只需要猜测四种组合就能弄清楚见证是什么。也就是说，他们猜测一个见证，生成一个证明，然后看他们的答案是否与原证明匹配。

为了防止被猜测，证明者需要对其证明“加盐” (salt)，同时需要修改验证公式以适应加盐后的证明。

证明者抽取两个随机域元素 $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{\left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)}_A \underbrace{\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)}_B

将各项展开后我们得到：

\alpha\beta+\alpha\sum_{i=1}^m a_iv_i(x)+\alpha s\delta + \beta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)+\sum_{i=1}^m a_iu_i(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_iv_i(x)}+\alpha s\delta + \boxed{\beta\sum_{i=1}^m a_iu_i(x)} + \boxed{\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)}+\sum_{i=1}^m a_iu_i(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_iv_i(x) + \beta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)}+ \underline{\alpha s\delta + \sum_{i=1}^m a_iu_i(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_iu_i(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$ 相关的项组合在一起：

=\left(\alpha s\delta + \sum_{i=1}^m a_iu_i(x) s\delta + rs\delta^2\right) + \left(r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + rs\delta^2\right) - rs\delta^2

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

=\underbrace{\left(\alpha+ \sum_{i=1}^m a_iu_i(x) + r\delta\right)s\delta}_{As\delta} + \underbrace{\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)r\delta}_{Br\delta} - rs\delta^2

代入 $A$ 和 $B$ ：

=As\delta + Br\delta - rs\delta^2

因此我们的最终等式为

\left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)=\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 + Br\delta - rs\delta^2

我们现在将其分成公开和私有部分：

\left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)=\alpha\beta+\underbrace{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}_\text{公开部分} + \underbrace{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x) + As\delta + Br\delta - rs\delta^2}_\text{私有部分}

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

(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta)=\alpha\beta+\gamma\frac{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(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\delta + Br\delta - rs\delta^2

其中一部分项中的 $\delta$ 可以被提取出来：

(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta)=\alpha\beta+\gamma\frac{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}{\gamma} + \delta\left(\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 + Br - rs\delta\right)

我们现在将此等式拆分为验证者和证明者两部分。带方框的项是验证者计算的部分，带下括号的项是证明者提供的部分：

\underbrace{(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)}_{[A]_1}\underbrace{(\beta + \sum_{i=1}^m a_iv_i(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)+w_i(x))}{\gamma}} + \boxed{\delta}\underbrace{\left(\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 + Br - rs\delta\right)}_{[C]_1}

Groth16 证明算法

我们现在准备端到端地展示 Groth16 算法。可信设置和验证步骤与我们之前结合了 $\gamma$ 和 $\delta$ 的示例保持不变。只有证明者的计算为了包含 $r$ 和 $s$ 而发生了改变。

可信设置

\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 \mathbb{G}_1 \text{ 的 srs}\\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \mathbb{G}_2 \text{ 的 srs}\\ \left[\frac{\tau^{n-2}t(\tau)}{\delta}G_1,\frac{\tau^{n-3}t(\tau)}{\delta}G_1,\dots,\frac{\tau t(\tau)}{\delta}G_1, \frac{t(\tau)}{\delta}G_1\right] &\leftarrow h(\tau)t(\tau) \text{ 的 srs}\\ \\ &\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}G_1\\ &\vdots\\ [\Psi_\ell]_1 &= \frac{\alpha v_\ell(\tau) + \beta u_\ell(\tau) + w_\ell(\tau)}{\gamma}G_1\\ \\ &\text{见证的私有部分}\\ [\Psi_{\ell+1}]_1 &= \frac{\alpha v_{\ell+1}(\tau) + \beta u_{\ell+1}(\tau) + w_{\ell+1}(\tau)}{\delta}G_1\\ [\Psi_{\ell+2}]_1 &= \frac{\alpha v_{\ell+2}(\tau) + \beta u_{\ell+2}(\tau) + w_{\ell+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,G_1 \text{ 的 srs},G_2 \text{ 的 srs},h(\tau)t(\tau) \text{ 的 srs},[\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]_1r-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 具有延展性 (Malleable)

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

# chosen arbitrarily
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 了解更多

我们免费发布此类材料的能力依赖于我们学生的持续支持。请考虑注册我们的 Zero Knowledge Bootcamp、Web3 Bootcamps 或在 RareTalent 上寻找一份工作。

最初发布于 2023 年 8 月 31 日

Last updated on Mar 16, 2026

先决条件

本文是 RareSkills Book of Zero Knowledge Proofs 中的一章。假定您已熟悉前面的章节。

符号说明

\begin{array}{} u_1(x),...,u_m(x) & 对 \mathbf{L} 的 m 列进行插值得到的 m 个多项式\\ v_1(x),...,v_m(x)& 对 \mathbf{R} 的 m 列进行插值得到的 m 个多项式\\ w_1(x),...,w_m(x)& 对 \mathbf{O} 的 m 列进行插值得到的 m 个多项式\\ \end{array}

由此，我们可以构造一个二次算术程序 (QAP)：

\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(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_iu_i(x)\sum_{i=1}^m a_iv_i(x) - \sum_{i=1}^m a_iw_i(x)}{t(x)}

\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] && G_1 \text{ 的 srs} \\ [\Theta_{n-1}, \Theta_{n-2},\dots,\Theta_2,\Theta_1,G_2] &= [\tau^nG_2,\tau^{n-1}G_2,\dots,\tau G_2,G_2] && G_2 \text{ 的 srs}\\ [\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] && h(\tau)t(\tau) \text{ 的 srs}\\ \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[f_d, f_{d-1},...,f_1,f_0],[\Omega_d,\Omega_{d-1},...,G_1]\rangle

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

f(\tau) = \sum_{i=1}^d f_i\Theta_i=\langle[f_d, f_{d-1},...,f_1,f_0],[\Theta_d,\Theta_{d-1},...,G_2]\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*}

此计算的详细信息在我们的教程 Quadratic Arithmetic Programs over Elliptic Curves 中有讨论。

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

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

动机

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

证明者可以简单地编造出满足 $ab = c$ 的值 $a$ 、 $b$ 、 $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 计算得出的。

防止伪造第 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]₁$ 和 $[B]₂$ ，并试图推导出一个与验证者公式兼容的值 $[C']$ 。

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

知道 $[A]₁$ 和 $[B]₂$ 的离散对数后，恶意的证明者试图通过以下计算求解 $[C']$

\begin{align*}\underbrace{[A]_1\bullet [B]_2 - [D]_{12}}_{\chi_{12}}=[C']_1\bullet G_2\\ [\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 G_2}_{[\zeta]_{12}}\\ [A]_1 \bullet [B]_2 &\stackrel{?}=[\zeta]_{12} \end{align*}

这要求证明者在给定 $[\zeta]_{12}$ 的情况下，想出一对 $[A]₁$ 和 $[B]₂$ ，它们配对后能产生 $[\zeta]_{12}$ 。

$\alpha$ 和 $\beta$ 的使用方式

\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_iu_i(x)\sum_{i=1}^m a_iv_i(x) = \sum_{i=1}^m a_iw_i(x) + h(x)t(x)

现在考虑如果我们在等式左侧引入项 $\theta$ 和 $\eta$ 会发生什么：

\left(\boxed{\theta}+\sum_{i=1}^m a_iu_i(x)\right)\left(\boxed{\eta} +\sum_{i=1}^m a_iv_i(x)\right) =

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

我们可以使用原始的 QAP 定义来替换最右侧的项：

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

=\theta\eta + \theta\sum_{i=1}^m a_iv_i(x) + \eta\sum_{i=1}^m a_iu_i(x) + \boxed{\sum_{i=1}^m a_iw_i(x) + h(x)t(x)}

现在我们可以引入一个具有以下定义的“扩展版” QAP：

\left(\theta+\sum_{i=1}^m a_iu_i(x)\right)\left(\eta +\sum_{i=1}^m a_iv_i(x)\right) =\theta\eta + \theta\sum_{i=1}^m a_iv_i(x) + \eta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iw_i(x) + h(x)t(x)

为了让大家提前窥见我们接下来的目标，如果我们将 $\theta$ 替换为 $[\alpha]_1$ ，将 $\eta$ 替换为 $[\beta]_2$ ，我们就能得到前面更新后的验证公式：

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

其中

\underbrace{\left([\alpha]_1+\sum_{i=1}^m a_iu_i(\tau)\right)}_{[A]_1}\underbrace{\left([\beta]_2 +\sum_{i=1}^m a_iv_i(\tau)\right)}_{[B]_2} =[\alpha]_1\bullet[\beta]_2 + \underbrace{\left(\alpha\sum_{i=1}^m a_iv_i(\tau) + \beta\sum_{i=1}^m a_iu_i(\tau) + \sum_{i=1}^m a_iw_i(\tau) + h(\tau)t(\tau)\right)}_{[C]_1} \bullet G_2

\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*}

相反，可信设置需要为扩展 QAP 中存在问题的 $C$ 项预计算出 $m$ 个多项式。

\alpha\sum_{i=1}^m a_iv_i(\tau) + \beta\sum_{i=1}^m a_iu_i(\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 \mathbb{G}_1 \text{ 的 srs}\\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \mathbb{G}_2 \text{ 的 srs}\\ [\tau^{n-2}t(\tau)G_1,\tau^{n-3}t(\tau)G_1,\dots,\tau t(\tau)G_1,t(\tau)G_1] &\leftarrow h(\tau)t(\tau) \text{ 的 srs}\\ [\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,G_1 \text{ 的 srs},G_2 \text{ 的 srs},h(\tau)t(\tau) \text{ 的 srs},[\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, a_2, \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$ 将公开输入和私有输入分开

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

例如，这是我们当前的验证等式：

[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\Psi_i + \underbrace{\left(\sum_{i=\ell+1}^m a_i[\Psi_i]_1 + h(\tau)t(\tau)\right)}_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 G2 + \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 G2 + \underbrace{(\boxed{3\Psi_3}+4\Psi_4 + 5\Psi_5 + h(\tau)t(\tau))}_C \bullet G_2

上面的等式是有效的，但见证却不一定满足原始约束。

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

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

\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 \mathbb{G}_1 \text{ 的 srs}\\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \mathbb{G}_2 \text{ 的 srs}\\ \left[\frac{\tau^{n-2}t(\tau)}{\delta}G_1,\frac{\tau^{n-3}t(\tau)}{\delta}G_1,\dots,\frac{\tau t(\tau)}{\delta}G_1, \frac{t(\tau)}{\delta}G_1\right] &\leftarrow h(\tau)t(\tau) \text{ 的 srs}\\ \\ &\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}G_1\\ &\vdots\\ [\Psi_\ell]_1 &= \frac{\alpha v_\ell(\tau) + \beta u_\ell(\tau) + w_\ell(\tau)}{\gamma}G_1\\ \\ &\text{见证的私有部分}\\ [\Psi_{\ell+1}]_1 &= \frac{\alpha v_{\ell+1}(\tau) + \beta u_{\ell+1}(\tau) + w_{\ell+1}(\tau)}{\delta}G_1\\ [\Psi_{\ell+2}]_1 &= \frac{\alpha v_{\ell+2}(\tau) + \beta u_{\ell+2}(\tau) + w_{\ell+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,G_1 \text{ 的 srs},G_2 \text{ 的 srs},h(\tau)t(\tau) \text{ 的 srs},[\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

第 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*}

攻击者只需要猜测四种组合就能弄清楚见证是什么。也就是说，他们猜测一个见证，生成一个证明，然后看他们的答案是否与原证明匹配。

为了防止被猜测，证明者需要对其证明“加盐” (salt)，同时需要修改验证公式以适应加盐后的证明。

证明者抽取两个随机域元素 $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{\left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)}_A \underbrace{\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)}_B

将各项展开后我们得到：

\alpha\beta+\alpha\sum_{i=1}^m a_iv_i(x)+\alpha s\delta + \beta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)+\sum_{i=1}^m a_iu_i(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_iv_i(x)}+\alpha s\delta + \boxed{\beta\sum_{i=1}^m a_iu_i(x)} + \boxed{\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)}+\sum_{i=1}^m a_iu_i(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_iv_i(x) + \beta\sum_{i=1}^m a_iu_i(x) + \sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x)}+ \underline{\alpha s\delta + \sum_{i=1}^m a_iu_i(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_iu_i(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$ 相关的项组合在一起：

=\left(\alpha s\delta + \sum_{i=1}^m a_iu_i(x) s\delta + rs\delta^2\right) + \left(r\delta\beta + r\delta\sum_{i=1}^m a_iv_i(x) + rs\delta^2\right) - rs\delta^2

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

=\underbrace{\left(\alpha+ \sum_{i=1}^m a_iu_i(x) + r\delta\right)s\delta}_{As\delta} + \underbrace{\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)r\delta}_{Br\delta} - rs\delta^2

代入 $A$ 和 $B$ ：

=As\delta + Br\delta - rs\delta^2

因此我们的最终等式为

\left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)=\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 + Br\delta - rs\delta^2

我们现在将其分成公开和私有部分：

\left(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta\right)\left(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta\right)=\alpha\beta+\underbrace{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}_\text{公开部分} + \underbrace{\sum_{i=\ell+1}^m a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x)) + h(x)t(x) + As\delta + Br\delta - rs\delta^2}_\text{私有部分}

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

(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta)=\alpha\beta+\gamma\frac{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(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\delta + Br\delta - rs\delta^2

其中一部分项中的 $\delta$ 可以被提取出来：

(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)(\beta + \sum_{i=1}^m a_iv_i(x) + s\delta)=\alpha\beta+\gamma\frac{\sum_{i=1}^\ell a_i(\alpha v_i(x) + \beta u_i(x)+w_i(x))}{\gamma} + \delta\left(\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 + Br - rs\delta\right)

我们现在将此等式拆分为验证者和证明者两部分。带方框的项是验证者计算的部分，带下括号的项是证明者提供的部分：

\underbrace{(\alpha + \sum_{i=1}^m a_iu_i(x) + r\delta)}_{[A]_1}\underbrace{(\beta + \sum_{i=1}^m a_iv_i(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)+w_i(x))}{\gamma}} + \boxed{\delta}\underbrace{\left(\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 + Br - rs\delta\right)}_{[C]_1}

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 \mathbb{G}_1 \text{ 的 srs}\\ [\tau^{n-1}G_2,\tau^{n-2}G_2,\dots,\tau G_2,G_2] &\leftarrow \mathbb{G}_2 \text{ 的 srs}\\ \left[\frac{\tau^{n-2}t(\tau)}{\delta}G_1,\frac{\tau^{n-3}t(\tau)}{\delta}G_1,\dots,\frac{\tau t(\tau)}{\delta}G_1, \frac{t(\tau)}{\delta}G_1\right] &\leftarrow h(\tau)t(\tau) \text{ 的 srs}\\ \\ &\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}G_1\\ &\vdots\\ [\Psi_\ell]_1 &= \frac{\alpha v_\ell(\tau) + \beta u_\ell(\tau) + w_\ell(\tau)}{\gamma}G_1\\ \\ &\text{见证的私有部分}\\ [\Psi_{\ell+1}]_1 &= \frac{\alpha v_{\ell+1}(\tau) + \beta u_{\ell+1}(\tau) + w_{\ell+1}(\tau)}{\delta}G_1\\ [\Psi_{\ell+2}]_1 &= \frac{\alpha v_{\ell+2}(\tau) + \beta u_{\ell+2}(\tau) + w_{\ell+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,G_1 \text{ 的 srs},G_2 \text{ 的 srs},h(\tau)t(\tau) \text{ 的 srs},[\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]_1r-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

此外也有库支持 Solana 上的 Groth16。

需要注意的安全问题

Groth16 具有延展性 (Malleable)

Groth16 证明是具有延展性的。给定一个有效的证明

要理解为什么 $[A]_1\bullet[B]_2 = [A']_1\bullet[B']_2$ ，请考虑以下代码：

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

# chosen arbitrarily
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 了解更多

我们免费发布此类材料的能力依赖于我们学生的持续支持。请考虑注册我们的 Zero Knowledge Bootcamp、Web3 Bootcamps 或在 RareTalent 上寻找一份工作。

最初发布于 2023 年 8 月 31 日

先决条件

符号说明

动机

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

一个“无法求解”的验证公式

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

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

α\alpha 和 β\beta 的使用方式

重新推导证明和验证公式

迄今为止的算法总结

可信设置步骤

证明者步骤

验证者步骤

支持公开输入

第 2 部分：通过 γ\gamma 或 δ\delta 将公开输入和私有输入分开

通过滥用 i≤ℓi\leq\ell 的 Ψi\Psi_i 伪造证明

引入 γ\gamma 和/或 δ\delta

第 3 部分：实现真正的零知识：r 和 s

Groth16 证明算法

可信设置

证明者步骤

验证者步骤

在 Solidity 中验证 Groth16

需要注意的安全问题

Groth16 具有延展性 (Malleable)

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

通过 RareSkills 了解更多

Groth16 详解

先决条件

符号说明

动机

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

一个“无法求解”的验证公式

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

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

α\alpha 和 β\beta 的使用方式

重新推导证明和验证公式

迄今为止的算法总结

可信设置步骤

证明者步骤

验证者步骤

支持公开输入

第 2 部分：通过 γ\gamma 或 δ\delta 将公开输入和私有输入分开

通过滥用 i≤ℓi\leq\ell 的 Ψi\Psi_i 伪造证明

引入 γ\gamma 和/或 δ\delta

第 3 部分：实现真正的零知识：r 和 s

Groth16 证明算法

可信设置

证明者步骤

验证者步骤

在 Solidity 中验证 Groth16

需要注意的安全问题

Groth16 具有延展性 (Malleable)

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

通过 RareSkills 了解更多

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

$\alpha$ 和 $\beta$ 的使用方式

第 2 部分：通过 $\gamma$ 或 $\delta$ 将公开输入和私有输入分开

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

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

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

$\alpha$ 和 $\beta$ 的使用方式

第 2 部分：通过 $\gamma$ 或 $\delta$ 将公开输入和私有输入分开

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

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