证明聚合方案：SnarkPack 和 aPlonk

导言

zk-SNARKs 是一种强大的密码学原语，它允许一方（称为证明者）向第二方（称为验证者）证明他知道一个给定的秘密，而不泄露任何关于该秘密的信息。这方面的应用包括，例如，在去中心化的私有计算中，我们可以将一个昂贵的计算委托给一个不受信任的服务器，并收到证明计算正确性的密码学证明，而不泄露敏感信息。我们还可以利用 zk-SNARKs 来解决影响大多数去中心化账本的隐私和可扩展性问题。在那里，每个节点必须独立地执行计算以检查其有效性。这意味着能力较弱的设备可能会成为瓶颈，尤其是在计算成本很高时，从而影响可扩展性。但是，我们可以让节点验证一个简短的证明来表明计算是正确的，而不是让每个节点重新执行每个计算。在那种情况下，我们可以减轻整个系统的负担。

zk-SNARKs 的主要问题之一是证明的生成时间。通常，证明生成涉及将计算转换为一些 NP 完全问题，我们可以在其中证明计算的正确性。其中包括算术电路可满足性或二次约束系统（秩 1 约束系统，R1CS）。然后，我们必须执行一些昂贵的计算，例如多标量乘法（MSM）和椭圆曲线配对以检查解。已经采用了多种策略来降低计算成本，例如证明组合、批处理、递归、处理数量增加的较小证明以及利用多项式承诺方案的优势。

在之前的文章中，我们介绍了增量可验证计算（IVC）和 folding 方案，这些方案为我们提供了在实践中实现 IVC 的方法。我们介绍了 Nova 的基础知识以及 folding 方案的工作原理。现在，我们将注意力转向证明聚合方案：SNARKPack 和 aPlonK。这些方案使我们能够减少证明的总大小和相关的验证时间：对于 $n$ 个证明，聚合证明的大小和验证时间将为 $O(n)$，这是一个显着的减少，尤其是在大量证明的情况下。SNARKPack 构建在 Groth16 SNARK 之上，而 aPlonk 则与 Plonk 证明系统一起使用。两者都是使用最广泛的 SNARK，并使用可信设置，这是涉及多方计算的设置仪式的结果。

SNARKPack

在 Groth16 方案中，证明 $\pi$ 由三个 椭圆曲线 群元素组成，即 $A, B, C$。$A$ 和 $B$ 都属于群 $G_1$，而 $C$ 属于群 $G_2$。这两个群具有相同的 阶（元素数量），即 $p$，并且是扩展域上椭圆曲线的 $p$ 阶挠群之一。我们可以通过从每个群中取一个元素并在第三个群 $G_t$ 上输出一个元素来定义双线性映射（或配对运算）：$e:G_1 \times G_2 \rightarrow G_t$。该操作必须满足属性 $e(g^a, h^b) = e(g, h)^{ab}$ 才是双线性的。在之前的等式中，$a, b$ 是数字，$g, h$ 分别是群 $G_1$ 和 $G_2$ 的生成元（我们说群的一个元素 $g$ 是一个生成元，如果群中的任何元素都可以通过重复添加它来获得）。我们在 Groth16 中通过配对运算执行证明验证，

$e(A, C) = Y e(B, D)$

其中 $D$ 是 $G_2$ 的一个元素，$Y$ 是 $G_t$ 的一个元素。聚合 $n$ 个 Groth16 证明背后的主要思想是，我们可以通过使用随机线性组合（在某种程度上存在很小的误差）来同时验证所有这些证明。这样，我们只需要执行一次配对操作，而不是 $n$ 次，

$\prod e(A_k, C_k)^{r_k} = \prod Y_k^{r_k} \prod e(B_k r_k, D)$

其中 $r$ 是随机采样的数字，$\prod$ 意味着我们取所有可能的配对的乘积。

定义以下术语以简化表示法：

$Z_{AC} = \prod e(A_k, C_k)^{r_k}$

$Y_{prod} = \prod Y_k$

$Z_B = \prod e(B_k r_k, D)$

$Z{AC} = Y{prod} Z_B$

在检查完最后一个等式成立后，我们剩下的任务是验证对于一些初始的 committed 向量 $A = (A_1, A_2, ... A_n)$、$B = (B_1, B_2, ..., B_n)$ 和 $C = (C_1, C_2, ..., Cn)$，$Z{AC}, Z_B$ 与这些规范一致。我们使用两个内部配对参数来检查这一点：

1. 目标内部配对乘积 (TIPP) 表明 $Z_{AC} = \prod e(A_k, C_k)^{r_k}$。
2. 多指数内部配对乘积 (MIPP) 表明 $Z_B = \prod e(B_k r_k, D)$。

我们需要具有同态和折叠性质的有效承诺方案来构建这些内部配对的乘积。我们说如果给定两个元素 $a, b$，承诺方案满足 $cm(a + b) = cm(a) + cm(b)$，则该承诺是加法同态的。例如，Pedersen 和 Kate-Zaverucha-Goldberg 承诺具有此属性。为了实现对数证明大小，SNARKPack 的作者使用了与 bulletproofs 相同的策略，该策略基于内部积参数。这些承诺在密钥空间中也是同态的：给定两个密钥 $k_1, k_2$ 并且对于任何消息 $m$，我们有 $cm(m, k_1 + k_2) = cm(m, k_1) + cm(m, k_2)$。

该协议使用了两个大型设置仪式的可信设置：Filecoin 和 Zcash。在 Groth16 中，结构化参考字符串（SRS），它是仪式的成果，由隐藏在群 $G_1, G_2$ 内部的随机元素 $\tau$ 的幂组成。给定生成元 $g, h$，SRS 由 $g, g^\tau, g^{\tau^2}, ... g^{\tau^d} = g, g_1, g_2, ...$ 和 $h, h^\tau, h^{\tau^2}, ..., h^{\tau^d} = h, h_1, h_2, ...$ 给出。这些将允许我们承诺多项式并验证关于它们的声明。

我们现在可以使用两个 SRS 创建配对群承诺。为了简化表示法，我们将调用

1. $w1 = (g, g{11}, h_{12}, ...)$ 和 $v1 = (h, h{11}, h_{12}, ...)$ 是仪式 1 的 SRS。
2. $w2 = (g, g{21}, h_{22}, ...)$ 和 $v2 = (h, h{21}, h_{22}, ...)$ 是仪式 2 的 SRS。

这些承诺有两个版本：单群和双群。前者以 $k_s = (v_1, v_2)$ 作为承诺密钥，而后者使用 $k_d = (v_1, w_1, v_2, w_2)$。

单群承诺接受向量 $A$ 和密钥 $k_s$ 并输出两个群元素：

$cmS(A, k_s) = (t_A, u_A)$

其中

$t_A = e(A_1, h) \times e(A2, h{11}) \times e(A3, h{12}) \times .... = A \cdot v_1$

$t_A = e(A_1, h) \times e(A2, h{21}) \times e(A3, h{22}) \times .... = A \cdot v_2$

双重承诺接受由 $G_1$ 和 $G_2$ 中的元素组成的向量 $A$ 和 $C$ 以及 $k_d$ 并输出两个元素：

$cmd(A, C) = (t{AC}, u{AC})$

其中

$t_{AC} = (A \cdot v_1)(C \cdot w_1) = (\prod e(Ak, h{1, k-1})(\prod e(g_{1, k-1}, C_k))$

$u_{AC} = (A \cdot v_2)(C \cdot w_2) = (\prod e(Ak, h{2, k-1})(\prod e(g_{2, k-1}, C_k))$

我们将结合 TIPP 使用双重承诺来表明 $Z_{AC} = \prod e(A, C)^{r_k}$，而 MIPP 将与单承诺一起使用，以查看 $Z_B = \prod e(B_k r_k, D)$。有两个关系需要检查：

R_{MIPP} = (t_B, u_B, r, Z_B, B, rv): Z_B = B_k r_k \land (u_B, t_B) = cms(B) \land (rv)_i = r^{i-1}

R_{TIPP} = (t_{AC}, u_{AC}, r, Z_{AC}, A, C, rv): Z_{AC} = \prod e(A_k, C_k)^{r_k} \land

(u_{AC}, t_{AC}) = cmd(A, C) \land (rv)_i = r^{i-1}

简而言之，在每个关系中，我们检查该值是否正确以及承诺是否有效。

有关证明和验证算法的确切详细信息，我们请读者参考来源。

在所示的案例研究中，聚合方案在大小和时间上都优于批量验证，略高于 100 个证明。

aPlonk

aPlonk 以 SNARKPack 的思想为基础，使用不同的证明系统 (Plonk) 并引入多项式承诺以在多项式的数量上实现亚线性大小。关键思想是通过执行承诺的随机线性组合并检查它来验证多个证明。表示法略有不同，因为 aPlonk 的作者在使用群时使用加法表示法，而 SNARKPack 的作者使用乘法表示法。如果 $cm(p_k)$ 是对多项式 $p_k$ 的承诺（如果我们使用 KZG 承诺，则它是椭圆曲线元素），那么我们可以通过执行以下操作来验证所有这些多项式

$\sum r_k cm(p_k) = \beta$

并检查 $\beta$ 在点 $z$ 处是否打开（评估）为

$v = \sum r_k v_k$

其中 $v_k$ 是 $p_k(z)$ 的值。如果我们使用乘法表示法，则前面的等式将读为

$\prod (cm(p_k))^{r_k} = \beta$

为了实现亚线性大小，证明者将承诺多项式的承诺，即 $\beta = cm(cm(p_1), cm(p_2)...)$。

由于我们正在使用 $r$ 的幂计算线性组合，因此自然会使用多项式承诺方案，例如 KZG 或内部积参数 (IPA)。

Plonk 的约束系统具有以下表达式

$q{Li} x{ai} + q{Ri} x{bi} + q{Oi} x{Ci} + q{Mi} x{ai} x{bi} + q{Ci} = 0$

并且可以扩展为包括更高阶的项或自定义门。对于每个 $q_k$，我们可以通过让每个多项式在 $n$ 个单位本原根 $\omegai$ 处评估为其对应的 $q{ki}$ 来定义一个单变量多项式 $q_L(x), q_R(x), q_O(x), q_M(x), q_C(x)$（我们说 $\omega_i$) 是单位的 $n$ 次本原根，如果 $\omega_n^i = 1$ 且 $\omega_k^i \neq 1$ 如果 $k < n$。此外，证明者必须证明索引 $a_i, b_i, c_i$ 之间的关系通过置换相关联。这些置换也用多项式表示。因此，我们必须承诺总共 8 个多项式。

一个关键的构建块是多项式承诺方案。这包括 5 个高效的算法，setup、commit-polynomial、commit-evaluation、open、check；主要区别在于添加了 commit-evaluation 算法。多项式承诺建立在两个多项式承诺方案之上：KZG 和 IPA。

一个重要的优化是所有多项式都在相同的随机挑战 $r$ 处进行评估，该挑战由 Fiat-Shamir 启发式给出。因此，证明者必须从所有证明的部分脚本中获取 $r$，这要求每个语句的证明协调运行。即使这阻止了增量可验证计算 (IVC) 的构建，因为在这种情况下，证明是一个接一个地生成的，但该构建对于有效性 rollup 效果很好。

总结

证明聚合方案是减少许多 zk-SNARK 的大小和验证时间的另一种方法。特别是，对于 $n$ 个证明，我们可以获得 $O(log(n))$ 阶的证明大小和验证时间。对于略多于 100 个证明，证明聚合优于批处理技术，并且当我们添加超过 1000 个证明时，它具有明显的优势。实现这些属性的主要构建块是同态多项式承诺（例如 KZG）、两个可信设置以及我们可以通过使用某个数字 $r$ 的幂作为系数来采用随机线性组合来验证许多证明的事实。

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