在内部训练营中使用lambdaworks实现BabySNARK

介绍

两周前，我们启动了一个内部训练营，旨在帮助新工程师快速融入我们的团队。我们希望提供密码学的基本构建块，并介绍使用 lambdaworks 的零知识证明（ZKP）。零知识证明是一种强大的技术，可以以许多不同的方式塑造未来。有关该主题的介绍和一些历史，请参阅我们之前的博客文章。现代证明系统使用多种技巧和优化来提高性能。然而，这使得学习过程复杂化，因为我们必须将主要逻辑（算术化、插值、施加约束、对多项式进行承诺）与改进分开，其中一些改进难以掌握。我们专注于一个更直接的构造，遵循 BabySNARK。在第一周，我们介绍了有限域的基础知识、群的概念、椭圆曲线、哈希函数、签名、公钥加密和对称密钥加密方案。如果你不熟悉某些主题，我们建议你阅读我们的数学生存工具包。

这篇博客文章将解释证明系统的工作原理及其使用 lambdaworks 的实现（你可以在此处查看正在进行的工作）。我们希望这将有助于新人们进入 ZKP 这个奇妙的领域。

工作原理

程序作为多项式之间的关系

BabySNARK 基于 2014 年提出的这个 NIZK。它使用 square span programs，这与 quadratic arithmetic programs (用于 Pinocchio) 类似，但更简单。电路的表示使用矩阵 $U$ (属于 $F^{m \times n}$) 和向量 $z = (1, u, w)^t$ (包含实例 $u$ 和 witness $w$)，

$(U.z) \circ (U.z) = 1$

我们可以使用这些类型的约束来表达任何布尔电路。让我们以一种不同的形式重写方程，这将便于以后使用：

$(\sumj u{ij} z_j)^2 = 1$

这对于每个 $i = 0, 1, 2, ...$ 都应该是有效的。我们可以使用多项式来编码这些方程。假设 $m = 2^k$，对于某个 $k$，并且我们正在处理一个包含大小为 $2^k$ 的子群 $D_i$ 的 nice field $F$。我们可以将 $\omega$ 作为单位的 $m$ 次本原根（$\omega$ 生成整个子群），并找到满足以下条件的多项式 $U_j(x)$

$Uj(\omega^i) = u{ij}$

通过这样做，我们将方程编码为多项式上的关系。因此，我们可以等效地替换该问题，

$(\sum_j U_j(x) z_j)^2 - 1 = p(x)$

如果我们在 $\omega^i$ 处评估多项式，那么我们得到 $Uj(\omega^i) = u{ij}$，并且 $p(\omega^i)$ 在每个 $\omega^i$ 处评估为 $0$。一个定理说，如果 $\omega^i$ 是多项式 $p(x)$ 的根/零点，那么 $x - \omega^i$ 除以 $p(x)$。换句话说，存在一些 $q(x)$ 使得 $p(x) = (x - \omega^i) q(x)$。

如果多项式有多个零点，那么它必须能被每个 $x - \omega^i$ 整除。让我们将 $Z(x)$ 定义为 $D_i$ 上的 vanishing polynomial

$Z(x) = \prod_j (x - \omega^j) = x^m - 1$

我们在最后一个等式中使用了 $\omega$ 是单位的本原 $m$ 次根（这个技巧也用在 STARKs 中）。因此，如果所有约束都成立，我们有一个多项式 $q(x)$ 满足这个等式

$p(x) = Z(x) q(x)$

证明由方程组描述的计算有效的一种方法是提供 $p(x)$ 和 $q(x)$，并让验证者自己检查等式。问题是我们必须传递两个多项式的所有系数（它们与计算一样长），并让他计算右手边，并断言它是否等于左手边的多项式。此外，我们还会泄露关于 witness 的信息！我们如何将其变成简洁的东西，并且不泄露信息？

多项式承诺方案

多项式承诺方案由四个算法给出：setup、commit、open 和 evaluate。承诺允许我们使用短数据将自己绑定到给定的多项式，并在以后能够证明关于该多项式的事情。承诺方案必须满足以下两个属性：

1. 隐藏性：承诺不会泄露关于承诺多项式的任何信息。
2. 绑定性：给定对 $p(x)$ 的承诺 $cm(p)$，找到另一个 $q(x)$ 使得 $cm(p) = cm(q)$ 是不可行的。

构建 PCS 的一种方法是使用 pairing-friendly 椭圆曲线，例如 BN254 或 BLS12-381。我们将在这里使用 type-3 pairings，它们是具有以下属性的函数 $e: G_1 \times G_2 \rightarrow G_t$：

1. 双线性：$e(ag_1, bg_2) = e(g_1, g_2)^{ab}$。
2. 非退化：如果 $e(P, Q) = 1$，那么 $P = O$ 或 $Q = O$。

KZG 承诺方案 在此设置下工作，这是我们将使用的工具。 pairings 为什么有用？因为它们为我们提供了一种将隐藏在椭圆曲线群中的事物相乘的方法。

我们选择一个随机的 $s$（prover 和 verifier 都不知道），并且我们生成椭圆曲线中的以下点

${P_0, P_1, ..., P_n} = {g_1, sg_1, ..., s^n g_n}$

这些点包含隐藏在椭圆曲线群中的 $s$ 的幂。给定任何 $P_k$，由于椭圆曲线上离散对数问题的难度，恢复 $s$ 在计算上是棘手的。

我们通过计算以下公式来对多项式进行承诺

$p(s)g_1 = \sum a_k (s^k g_1) = \sum a_k P_k$

其中 $g_1$ 是椭圆曲线的素数阶 $r$ 的群/子群的生成器。我们也可以使用 $G_2$ 中的元素进行承诺，其中 $g_2$ 是子群生成器。

使用 pairings，我们可以通过计算两个 pairings 并检查它们的相等性来证明多项式 $p(x)$ 和商 $q(x)$ 之间的关系：

$e(p(s)g_1, g_2) = e(g_1, g_2)^{p(s)}$

$e(q(s)g_1, s^m g_2 - g_2) = e(g_1, g_2)^{q(s)(s^m - 1)}$

由于 $s$ 是随机选择的，如果 $p(s) = q(s)Z(s)$，那么以压倒性的概率，我们有 $p(x) = q(x)Z(x)$。

使用这种构造，我们不需要向 verifier 提供多项式的系数，只需要提供它们的承诺。这解决了部分问题，但不是全部。

协议的直觉

我们想要证明的程序/电路由矩阵 $U$ 定义。当我们为电路定义一个特定的实例/公共输入 $u$ 时，如果 $u$ 是有效的，我们应该能够找到一些 $w$ 来求解方程组。为了使证明简洁，我们应该发送比完整 witness 少得多的信息（此外，如果我们想要零知识，则应该对 witness 保密）。

我们有问题的多项式 $p(x)$、vanishing polynomial $Z(x)$ 和商 $q(x)$。最后，我们想证明

$p(x) = Z(x) q(x)$

如果计算有效。 $Z(x)$ 是 prover 和 verifier 都知道的，我们甚至可以承诺 $Z(x)$ 作为公共信息的一部分。我们可以将此检查简化为一个点 $x = s$，并使用 pairings 验证它。但是，仅此检查是不够的，因为 prover 可以提供任何多项式 $p(x)$。如果我们回顾一下我们如何构建 $p(x)$，

$(\sum_j U_j(x) z_j)^2 - 1 = p(x)$

求和中的某些项可以由 verifier 计算（因为这些是公共的）。但是，verifier 不知道 witness 的项，我们不想让他完全访问该数据。解决方案是 prover 提供求和，仅包括 witness 的值，

$Vw(x) = \sum{j \in w} w_j U_j(x)$

此外，我们可以使用我们之前拥有的承诺方案 $V_w(s)g_1$ 和 $V_w(s)g_2$ 来提供对 $V_w(x)$ 的承诺（我们将展示为什么我们很快需要两者）。然后，verifier 可以计算

$Vu(x) = \sum{k \in u} u_j U_j(x)$

并获得 $V_u(s)g_1$ 和 $V_u(s)g_2$。verifier 可以以等效的方式计算涉及 $e(p(s)g_1, g_2)$ 的 pairing，

$e(V_u(s)g_1 + V_w(s)g_1, V_u(s)g_2 + V_w(s)g_2) e(g_1, g_2)^{-1} = e(p(s)g_1, g_2)$

这看起来很奇怪，但如果我们取所有标量到指数，我们有 $(V_u(s) + V_w(s))(V_u(s) + V_w(s)) - 1$，并且 verifier 可以获得电路的多项式。所以，我们得到了第一个检查，

$e(V_u(s)g_1 + V_w(s)g_1, V_u(s)g_2 + V_w(s)g_2) e(g_1, g_2)^{-1} = e(q(s)g_1, Z(s)g_2)$

但是，我们有一个问题。我们如何知道 prover 在两个承诺中使用了相同的 $V_w(x)$？幸运的是，我们可以通过另一个 pairing 检查来解决这个问题，

$e(V_w(s)g_1, g_2) = e(g_1, V_w(s)g_2)$

我们得到了另一个检查。最后，我们如何知道 verifier 正确计算了 $V_w(x)$，而不是做一些随机线性组合，它会与公共输入抵消并产生一些好的结果？

我们可以强制 prover 提供相同的线性组合，但所有点都按某个常数 $\beta$ 移动，双方都不知道。我们定义

$B_w(x) = \sum \beta w_j U_j(x) = \beta V_w(x)$

我们可以使用 pairings 对这种关系进行一次最终检查，

$e(B_w(s)g_1, \gamma g_2) = e(\gamma \beta g_1, V_w(s)g_2)$

其中 $\gamma$ 也是双方都不知道的。这使得 prover 不可能为 $V_w(x)$ 构建虚假多项式。我们可以看到，如果不存在此条件，我们可以创建任何 $V_w(x) = CZ(x) - V_u(x) + 1$，这将通过我们选择的任何 $C$ 的所有其他检查。事实上，

$V_w(x) + V_u(x) = CZ(x) + 1$

但是 $p(x) = (V_w(x) + V_u(x))^2 - 1$，所以

$p(x) = C^2 Z(x) Z(x) + CZ(x) = Z(x) (C^2 Z(x) + C)$

我们发现 $q(x) = (C^2 Z(x) + C)$，即使我们不知道 witness。

证明 $\pi$ 将包括：

1. 使用 $g_1$ 对 $V_w(x)$ 的承诺。
2. 使用 $g_2$ 对 $V_w(x)$ 的承诺。
3. 使用 $g_1$ 对 余数 多项式 $q(x)$ 的承诺。
4. 使用 $g_1$ 对 $B_w(x)$ 的承诺

验证涉及六个 pairings（pairing $e(g_1, g_2)^{-1}$ 可以预先计算，因为它是一个常数），以检查我们提到的三个条件。

为了计算承诺，我们需要参数 $s, \beta, \gamma$ 对双方都未知（因此，它们是有毒废物）。我们需要生成一个参考字符串，这将取决于电路（那是因为我们需要提供 $\beta U_j(s)g_1$）。有了这一切，我们可以进入实现。

实现

设置

Prover 和 verifier 同意一个 pairing-friendly 的椭圆曲线和群 $G_1$ 和 $G_2$ 的生成器，分别表示为 $g_1$ 和 $g_2$。在我们的例子中，我们选择 BLS12-381。证明密钥包括以下内容：

1. ${s^k g_1}$ 对于 $k = 0, 1, 2, ... m$
2. ${U_j(s)g_1}$ 对于 $j = l, l+1, ... m$（$l$ 是公共输入的数量）。
3. ${U_j(s)g_2}$ 对于 $j = l, l+1, ... m$
4. ${\beta U_j(s)g_1}$ 对于 $j = l, l+1, ... m$

验证密钥包括以下内容：

1. ${U_j(s)g_1}$ 对于 $j = 0, 1, ... l-1$
2. ${U_j(s)g_2}$ 对于 $j = 0, 1, ... l-1$
3. $[Z'] = (s^m - 1)g_2$（对 vanishing polynomial 的承诺）
4. $e(g_1, g_2)^{-1}$
5. $\beta \gamma g_1$
6. $\gamma g_2$

证明

prover 的步骤如下：

1. 使用证明密钥计算 $[V_w] = V_w(s)g_1$，$[V'_w] = V_w(s)g_2$ 和 $[B_w] = B_w(s)g_1$。
2. 从 zerofier $Z(x)$、witness 和实例向量以及描述电路 $U_j(x)$ 的多项式计算多项式 商 多项式 $q(x)$。
3. 使用证明密钥计算 $[q] = q(s)g_1$。
4. 生成证明 $\pi = ([q], [V_w], [V'_w], [B_w])$

验证

verifier 具有以下步骤：

1. 将证明 $\pi$ 解析为 $[q], [V_w], [V'_w], [B_w]$。
2. 检查 $e([V_w], g_2) = e(g_1, [V'_w])$
3. 检查 $e([B_w], \gamma g_2) = e(\beta \gamma g_1, [V'_w])$
4. 使用验证密钥计算 $[V_u] = V_u(s)g_1$ 和 $[V'_u] = V_u(s)g_2$。
5. 检查 $e([V_u] + [V_w], [V'_u] + [V'_w]) e(g_1, g_2)^{-1} = e([q], [Z'])$

如果所有检查都通过，则证明有效。

优化

1. 插值使用快速傅立叶变换 (FFT) 完成。这是可能的，因为 BLS12-381 的标量域有 $2^{32}$ 作为其因子之一。
2. 商 的计算以评估形式完成，使用 FFT。我们需要在 $\mu \omega^k$ 处评估多项式，其中 $\mu$ 是偏移量（我们希望在 cosets 上进行评估，因为如果我们直接在 $D_i$ 上进行评估，我们会得到 0/0）。
3. vanishing polynomial 的评估很简单：$Z(\mu \omega^k) = (\mu \omega^k)^m - 1 = \mu^m - 1$，因为 $\omega$ 的阶数为 $m$。
4. 使用 Pippenger 算法计算 multiscalar multiplication。

将 SNARK 转换为 zk-SNARK。

上面的协议不是零知识的，因为可以从随机的 $V(x)$ 中区分出 $V_w(x)$。为了使其成为零知识，prover 必须采样一个随机值 $\delta$，并对多项式进行以下更改：

1. 多项式 $p(x) = (\sum_k z_j U_j(x) + \delta Z(x))^2 - 1$。请注意，添加 $Z(x)$ 不会更改主要条件，即当且仅当 $p(x)$ 可被 $Z(x)$ 整除时，约束才得到满足。
2. 计算 $[V_w] = (V_w(s) + \delta Z(s))g_1$，$[V'_w] = (V_w(s) + \delta Z(s))g_2$ 和 $[B_w] = (B_w(s) + \beta \delta Z(s))g_1$。

verifier 的步骤保持不变。

总结

这篇文章介绍了基于 square span problems 实现一个简单的 SNARK。我们给出了协议如何工作的直觉，以及为什么我们需要不同的检查来确保安全。我们希望这将使新手能够学习 ZKP 的一些基本概念和工作流程。

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