Groth16 证明系统概览

介绍

在过去的十年里，SNARKs（简洁的、非交互的知识论证）和 STARKs（可扩展的、透明的知识论证）由于它们在可验证的私有计算和区块链的可扩展性方面的应用而备受关注。

Groth 在 2016 年介绍了这个 证明系统，并在 ZCash 中看到了早期的应用。该协议依赖于 pairing-friendly elliptic curves（配对友好的椭圆曲线），例如 BN254、BLS12-381 和 BLS12-377（稍后会详细介绍）。它的证明大小是最小的（仅由三个椭圆曲线元素组成），并且验证速度最快。主要的缺点是它需要每个程序都进行 trusted setup（可信设置）。换句话说，每当我们想证明一个新程序（或更改原始程序）时，都需要重新生成所有参数。

在这篇文章中，我们将描述 Groth16 的主要成分以及它的工作原理。正如路线图中所述，我们正在 Lambdaworks 库 中实现该协议。它也用作正在进行的 Sparkling Water Bootcamp 中的一个项目。

算术化

为了证明给定程序的执行，我们必须将其转换为 SNARK（简洁的、非交互的知识论证）友好的形式。其中一种形式是 arithmetic circuit satisfiability（算术电路可满足性），在这种形式中，可以证明对有效电路赋值的了解。第一步，称为 arithmetization（算术化），是将程序转换为算术电路或等效形式。

R1CS

算术电路可以等效地表示为（二次）rank one constraint systems (R1CS)（秩一约束系统），它是以下形式的方程组：

$(Az) \times (Bz) = Cz$

其中 $A, B, C$ 是大小为 $m+1$ 行、$n+1$ 列的矩阵，$z$ 是大小为 $n+1$ 的（列）向量，而 $\times$ 表示结果向量的按分量乘积。

我们可以选择将此紧凑形式视为

$(\sumk a{0k}z_k)(\sumk b{0k}z_k) - (\sumk c{0k}z_k) = 0$

$(\sumk a{1k}z_k)(\sumk b{1k}z_k) - (\sumk c{1k}z_k) = 0$

$(\sumk a{2k}z_k)(\sumk b{2k}z_k) - (\sumk c{2k}z_k) = 0$

$\vdots$

$(\sumk a{mk}z_k)(\sumk b{mk}z_k) - (\sumk c{mk}z_k) = 0$

通过使用多项式，我们可以更紧凑地表达这些方程，并更简洁地证明 R1CS 系统的解。为此，我们将介绍 quadratic arithmetic programs, QAP（二次算术程序）。

二次算术程序

我们可以将 $A$ 矩阵的每一列解释为某些多项式在某些合适的域上的求值。这是许多 SNARK 中常见的做法，我们尝试将向量编码为多项式；例如，请参阅我们关于 STARKs 的文章。我们从有限域中采样 $D_0 = x_0, x_1, ..., x_n$，并将多项式 $A_i(x)$ 定义为最多 $n$ 次的多项式，使得 $A_i(xk) = a{ki}$。

出于性能原因，选择插值域 $D_0$ 作为单位的 n 次根是很方便的，因为我们可以使用快速傅里叶变换进行插值。类似地，我们可以将 $B$ 和 $C$ 的列解释为多项式 $B_k(x)$ 和 $C_k(x)$。利用这些多项式，我们可以用多项式形式表示 R1CS 系统，

$P(x) = (\sum_k A_k(x)z_k)(\sum_k B_k(x)z_k) - (\sum_k C_k(x)z_k)$

我们可以看到，如果我们有一个有效的 R1CS 解，则多项式 $P(x)$ 在 $D_0$ 上求值为 $0$（因为我们要求多项式插值矩阵列的值）。因此，我们可以将条件表示为

$P(x) = 0$ 对于 $x \in D_0$

现在，我们引入集合 $D_0$ 上的 vanishing polynomial（消失多项式），$Z_D(x) = \prod_k (x - x_k)$

因此，如果多项式 $P(x)$ 在 $D_0$ 上求值为 $0$，则它可以被 $Z_D(x)$ 整除。这可以写成存在某个多项式 $h(x)$ 使得

$P(x) = h(x)Z_D(x)$

多项式 $h(x)$ 的次数是 $P$ 的次数减去 $Z_D$ 的次数。一个诚实的证明者应该能够找到结果商，并用它来表明他正确地执行了该程序。

将 QAP 转换为零知识证明

如果我们要将其转换为零知识证明，我们需要对上述问题进行一些转换。有关此过程的更详细说明，请参见此处。我们必须确保证明者不能作弊，并且验证者无法了解有关私有输入或 witness（证据）的任何信息。一个关键成分是 polynomial commitment scheme (PCS)（多项式承诺方案）：我们可以使证明者承诺给定的多项式，以便他以后无法更改它。一种这样的承诺方案是 KZG commitment（KZG 承诺），在其中我们使用 pairing-friendly elliptic curves（配对友好的椭圆曲线）将证明者绑定到多项式。该方案的安全性取决于曲线上离散对数问题的难度。配对可以被认为是一种允许椭圆曲线中点之间一次性乘法的运算。在我们的例子中，我们将在 type3 III pairings( III 型配对), $\dagger: G_1 \times G_2 \rightarrow G_t$ 上工作，它具有以下优良性质（双线性）：

$(ag_1) \dagger (bg_2) = (ab)(g_1 \dagger g_2)$

要使用 KZG 承诺来承诺一个多项式，我们需要采样一个随机标量 $\tau$（它被认为是 toxic waste（有毒垃圾），应该被遗忘，否则我们可以伪造证明）并生成椭圆曲线中的以下点序列，其生成器为 $g_1$,

$P_0 = g_1$,

$P_1 = \tau g_1$

$P_2 = \tau^2 g_1$

$\vdots$

$P_n = \tau^n g_1$

然后，给定一个多项式 $p(x) = a_0 + a_1x + a_2x^2 + ... + a_nx^n$ 我们计算承诺为

$cm(p) = a_0P_0 + a_1P_1 + ... + a_nP_n$

这与 $cm(p) = p(\tau)g_1$ 相同，也就是说，将 $p(x)$ 的求值隐藏在椭圆曲线内。由于离散对数问题很难，我们无法使用我们对 $g_1$ 和 $cm(p)$ 的了解来获得 $p(\tau)$。

要检查多项式 $p(x)$ 在 $z$ 处求值为 $v$，我们可以使用以下事实

$p(x) - v = (x - z)q(x)$

其中 $q(x)$ 是 $p(x)$ 除以 $x - z$ 的商多项式。证明者可以使用相同的技巧承诺 $q(x)$ 来生成此类求值的证明。但是，验证者仍然需要一些附加信息（包含在 verifying key（验证密钥）中），$g_2$（组 $G_2$ 的生成器）和 $\tau g_2$（记住，没有人必须知道 $\tau$）。然后，使用配对，验证者可以使用椭圆曲线中的点来检查求值，

$(cm(p) - vg_1 \dagger g_2) = a = p(\tau)(g_1 \dagger g_2)$

$cm(q) \dagger (\tau g_2 - zg_2) = b = q(\tau)(\tau - z)(g_1 \dagger g_2)$

如果 $a$ 和 $b$ 相同，并且由于 $\tau$ 是一个具有高概率的随机点，我们假设 $p(z) = v$ （这取决于 Schwartz-Zippel 引理）。

记住，我们想证明验证者知道一些 $w$ 和一个 $m-1$ 次多项式 $h(x)$，这样，如果 $z = (1, x, w)$, 则以下条件成立

$(\sum_k A_k(x)z_k)(\sum_k B_k(x)z_k) = (\sum_k C_k(x)z_k) + h(x)Z_D(x)$

如果我们首先强制证明者承诺多项式 $A_k(x)$ 和 $B_k(x)$，然后生成商多项式，我们必须确保他不能伪造 $C_k(x)$ 来满足先前的条件。为此，我们将引入随机位移（$\alpha$ 和 $\beta$）到求值：

$cm(\sum A_iz_i) = \sum (A_i(\tau)z_i)g_1 + \alpha g_1$

$cm(\sum B_iz_i) = \sum (B_i(\tau)z_i)g_2 + \beta g_2$

$B_i(x)$ 使用组 $G_2$ 进行承诺，以便我们可以通过配对计算左侧的乘积，

$(cm(\sum A_iz_i)) \dagger (cm(\sum B_iz_i)) = (\sum A_i(\tau)z_i)(\sum B_i(\tau)z_i)(g_1 \dagger g_2)$

因为我们引入了这些位移，所以我们需要相应地修改 $C_k$ 项，

$(\alpha + \sum_k A_k(x)z_k)(\beta + \sum_k B_k(x)z_k) = \alpha\beta + (\sum_k (C_k(x) + \beta A_k(x) + \alpha B_k(x))z_k) + h(x)Z_D(x)$

由于证明者无法知道 $\alpha$ 和 $\beta$，我们需要将它们隐藏起来作为 trusted setup（可信设置）的一部分提供，如 $\alpha g_1$ 和 $\beta g_2$，这样我们就可以计算

$(\alpha g_1) \dagger (\beta g_2) = \alpha\beta(g_1 \dagger g_2)$

这样我们就可以将此结果与移位的 $A_i$ 和 $B_i$ 之间的配对进行比较。

另外，由于证明者没有 $\alpha$ 和 $\beta$，因此需要向他提供 $C_k(x) + \beta A_k(x) + \alpha B_k(x)$ 形式的所有元素。但是，当我们想要计算这些项和 $z$ 之间的乘积时，我们必须记住 $z$ 包含 public input（公共输入）和 witness（证据）。验证者无法了解有关 witness（证据）的任何信息（因此，涉及 witness（证据）的求值应由证明者提供）。我们引入两个附加变量 $\gamma$ 和 $\delta$，以在 public input（公共输入）和 witness（证据）之间分割变量 $z$。前 $k$ 项对应于 public input（公共输入），这些项编码为

$Kv_i = \gamma^{-1}(C_i(\tau) + \beta A_i(\tau) + \alpha B_i(\tau))g_1$

对于 $i = 0, 1, 2, ..., k$。对于 witness（证据），我们有

$Kp_i = \delta^{-1}(C_i(\tau) + \beta A_i(\tau) + \alpha B_i(\tau))g_1$

使用这些新参数，我们得到

$(\alpha + \sum_j A_j(x)z_j)(\beta + \sum_j B_j(x)z_j) = \alpha\beta + \gamma(\sum_i^k \gamma^{-1}(C_i(x) + \beta A_i(x) + \alpha B_i(x))xi) + \delta(\sum{j=k+1}^n \delta^{-1}(C_i(x) + \beta A_i(x) + \alpha B_i(x))x_i) + h(x)Z_D(x)$

我们可以将最后两个项合并为一个（因为它们包含验证者不得学习的所有信息）

$D = (\sum_{j=k+1}^n \delta^{-1}(C_i(x) + \beta A_i(x) + \alpha B_i(x))x_i) + h(x)Z_D(x)\delta^{-1}$

由于我们想借助一个配对来计算乘积 $h(x)Z_D(x)$，我们可以计算以下组元素，

$Z_0 = \delta^{-1}Z_D(\tau)$

$Z_1 = \delta^{-1}\tau Z_D(\tau)$

$Z_2 = \delta^{-1}\tau^2 Z_D(\tau)$

$\vdots$

$Z_{m-1} = \delta^{-1}\tau^{m-1}Z_D(\tau)$

通过这些更改，QAP 的右侧是 3 个项的总和：

1. 一个常数（与随机位移有关）。

2. 涉及 public input（公共输入）的项。

3. 一个包含秘密项（只有证明者知道）的项。

设置

Groth16 需要采样五个随机域元素来生成 proving key（证明密钥）和 verifying key（验证密钥），即 $t, \alpha, \beta, \gamma, \delta$。这些都是 toxic waste（有毒垃圾），一旦密钥生成后，就应该丢弃并完全遗忘。

我们将使用 pairing-friendly elliptic curve（配对友好的椭圆曲线）（带有 III 型配对），其子组 $G_1$ 和 $G_2$ 具有素数阶 $r$。我们将分别调用生成器 $g_1$ 和 $g_2$。为了使符号更易于使用，我们将编写

$[x]_1 = xg_1$

$[x]_2 = xg_2$

表示 $G_1$ 和 $G_2$ 中的点，其中 $xg$ 表示 $x$ 和组的生成器的标量积（即，将椭圆曲线组运算应用于生成器 x 次）。我们将遵循 DIZK 给出的符号。首先，我们计算以下向量，

$Kv_i(t) = \gamma^{-1}(\beta A_i(t) + \alpha B_i(t) + C_i(t))$

对于 $i = 0, 1, 2, ... k$,

$Kp_i(t) = \delta^{-1}(\beta A_i(t) + \alpha B_i(t) + C_i(t))$

对于 $i = k+1, 1, 2, ... n$ 和

$Z_k(t) = t^kZ_D(t)\delta^{-1}$

对于 $k = 0, 1, 2, ... m-1$。

proving key（证明密钥）由以下元素组成：

1. $[\alpha]_1$
2. $[\beta]_1$
3. $[\beta]_2$
4. $[\delta]_1$
5. $[\delta]_2$
6. $[A_0(t)]_1, [A_1(t)]_1, ..., [A_n(t)]_1$
7. $[B_0(t)]_1, [B_1(t)]_1, ..., [B_n(t)]_1$
8. $[B_0(t)]_2, [B_1(t)]_2, ..., [B_n(t)]_2$
9. $[Kp{k+1}(t)], [Kp{k+2}(t)], ..., [Kp_n(t)]$
10. $[Z_0(t)], [Z1(t)], ..., [Z{m-1}(t)]$

verifying key（验证密钥）短得多，除外，验证密钥还会包含一个配对的值，因为该值是常数：

1. $[\alpha]_1 \dagger [\beta]_2$
2. $[\gamma]_2$
3. $[\delta]_2$
4. $[Kv_0(t)]_1, [Kv_1(t)]_1, ..., [Kv_k(t)]_1$

证明生成

证明者收到 proving key（证明密钥），并且知道表示程序和 public input（公共输入）的多项式，并且他想证明他具有满足该程序的 witness（证据）。首先，证明者需要计算商多项式 $h(x)$，或者更准确地说，是计算它的系数。证明者必须计算

$h(x) = \frac{\sum A_k(x)z_k \sum B_k(x)z_k - \sum C_k(x)z_k}{Z_D(X)}$

评估此商的最佳方法是选择一个域 $D_{ev}$，其大小至少是商多项式的次数加 1，并且不包含来自 $D0$（插值域）的元素，并在 $D{ev}$ 的所有元素上评估分子和分母。由于我们至少具有与多项式 $h(x)$ 的次数加 1 一样多的多项式 $h(x)$ 的评估，因此我们可以通过插值来重构 $h(x)$。在实践中，最快的方法是使用快速傅里叶变换进行评估和插值。证明者现在拥有一个系数向量 $h_0, h_1, h_2, ..., h_m$。

为了确保 proof（证明）是零知识的，证明者对两个随机标量 $r$ 和 $s$ 进行采样。

证明者可以通过执行以下计算来计算 proof（证明）的三个元素，$\pi = ([\pi_1]_1, [\pi_2]_2, [\pi_3]_1)$，

$[\pi_1]_1 = [\alpha]_1 + \sum z_k[A_k(t)]_1 + r[\delta]_1$

$[\pi_2]_2 = [\beta]_2 + \sum z_k[B_k(t)]_2 + s[\delta]_2$

$[\pi_2]_1 = [\beta]_1 + \sum z_k[B_k(t)]_1 + s[\delta]_1$

$[h(t)z(t)]_1 = \sum h_i[Z_i(t)]_1$

$[\pi_3]_1 = \sum w_i[Kp_i]_1 + [h(t)z(t)]_1 + s[\pi_1]_1 + r[\pi_2]_1 - rs[\delta]_1$

验证

验证者拥有 verifying key（验证密钥）和 public input（公共输入），并将 proof（证明）解析为 $[\pi_1]_1, [\pi_2]_2, [\pi_3]_1$ 并计算以下内容：

$[\pi_1]_1 \dagger [\pi_2]_2 = P_1$

$[\pi_3]_1 \dagger [\delta]_2 + [\alpha]_1 \dagger [\beta]_2 + (\sum x_i[Kv_i]_1) \dagger [\gamma]_2 = P_2$

如果 $P_1$ 和 $P_2$ 一致，则 proof（证明）有效。这相当于检查修改后的 QAP。

结论

在这篇文章中，我们介绍了 Groth16 协议，该协议提供了一个框架来证明计算的正确性，而无需透露敏感信息。它具有简洁的 proof（证明）和优雅的验证，但对于我们要证明的每个程序都需要 trusted setup（可信设置）。我们看到了将程序转换为 arithmetic circuits（算术电路）或其等效的 R1CS 的步骤，然后可以将其编译为 quadratic arithmetic program（二次算术程序）。我们解释了该协议如何转换基本方程，以确保证明者无法作弊，并且验证者不会了解有关 private data（私有数据）的任何信息。在即将发布的文章中，我们将介绍如何从头开始编码 Groth16。

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