剖析Bulletproofs：无需配对，无需可信设置

Bulletproofs 协议 允许你仅基于离散对数假设生成这些零知识证明，而无需可信设置。这实际上意味着不需要配对（比如 KZG/Groth16），而是比仅使用哈希函数（比如 STARKs）更复杂的方案。该协议已用于 门罗币中的范围证明，作为 Kimchi（Mina 协议的核心）等证明系统中的多项式承诺方案，以及 Zcash 的 Halo 2 中。因此，它非常通用，并且在现实世界中得到了很好的部署。

我认为，介绍 Bulletproofs 协议最简单的方法是解释它只是以可验证的方式计算 内积 的协议：

$\langle \vec{a}, \vec{b} \rangle = c$

如果你不知道什么是内积，请想象以下示例：

$\langle (a_1 a_2 a_3 a_4), (b_1 b_2 b_3 b_4) \rangle = a_1 b_1 + a_2 b_2 + a_3 b_3 + a_4 b_4$

使用 Bulletproofs 可以更快地验证 $\langle \vec{a}, \vec{b} \rangle = c$ 的证明，而不是自己计算内积。但更重要的是，Bulletproofs 甚至允许你隐藏一个或两个输入，或者隐藏输出，以获得有趣的 ZK 协议。

此外，如果计算内积本身听起来不是很吸引人，你可以想象它被用于执行实际有用的事情，比如证明一个值在给定的范围内（范围证明），甚至证明一个 电路 被正确执行了（当在通用零知识证明系统中使用时）。但这超出了本文解释的范围 :)

好了，介绍够多了，让我们开始吧。Bulletproofs 及其变体总是通过将所有内容隐藏在承诺中来“压缩”证明，这样你就可以用一个单独的点来表示每个输入/输出：

• $A = \langle \vec{a}, \vec{G} \rangle$
• $B = \langle \vec{b}, \vec{H} \rangle$
• $C = \langle \vec{a}, \vec{b} \rangle Q$

在这里你可以看到每个点 A、B、C 都是一个 非隐藏的 Pedersen 承诺，具有独立的基 $\vec{G}, \vec{H}, Q$（所以上面的计算是多标量乘法）。为了强调这一点，让我重复一遍：单个点代替长向量可以使证明更短！

因为我们喜欢例子，所以让我给你 $\vec{a}$ 的承诺：

$\langle (a_1 a_2 a_3 a_4), (G_1 G_2 G_3 G_4) \rangle = a_1 G_1 + a_2 G_2 + a_3 G_3 + a_4 G_4$

不同的协议（比如我在第一篇文章中讨论的 halo 协议），自从 bootleproof（在 bulletproofs 之前的论文）以来，以不同的方式聚合承诺。在上面的解释中，我没有聚合任何东西，但你可以想象，你可以通过对输入/输出进行单个承诺 $P = A + B + C$ 使事情变得更小。

此时，证明者可以只显示两个输入 $\vec{a}, \vec{b}$，验证者可以检查它们是否是 A、B 的有效打开，以及 $c = \langle \vec{a}, \vec{b} \rangle$ 是否是 C 的有效打开。如果我们把所有承诺聚合到单个承诺 P 中，那么你将检查聚合的打开是否有效。

但正如我之前所说，这不是很有效（你必须作为验证者来执行内积），而且也不是很紧凑（你必须发送长向量 $\vec{a}$ 和 $\vec{b}$）。

我知道它也不是零知识的，但我们将只解释没有隐藏的 Bulletproofs/IPA，对于隐藏部分，我们将像通常在 ZKP 方案的粗略解释中那样忽略它。

话虽如此，证明者最终会以明文形式发送两个输入向量，但在这样做之前，他们会减少它们。更准确地说，证明者和验证者将一起执行这个过程来减少问题陈述 $\langle \vec{a}, \vec{b} \rangle = c$ 到一个更小的 $\langle \vec{a'}, \vec{b'} \rangle = c'$，其中向量 $\vec{a'}$ 和 $\vec{b'}$ 都只有一个条目。

如果原始向量的大小为 $2^n$，那么 Bulletproofs 将执行 $n$ 次减少以获得最终的陈述（因为每次减少都会将向量的大小减半），然后将发送这些“减少的”输入向量 $a', b'$。此时，验证者将产生 $c' = \langle a', b' \rangle$ 并检查它们是否是减少的承诺 $A', B'$ 和 $C'$ 的有效打开。

如果你一直关注到现在，你应该期望我们接下来需要回答以下两个问题：

1. 如何从 A,B,C 减少到 $A', B', C'$？

2. 如何验证它？

为了减少 内容，我们执行 几乎 与我们在每个“折叠”协议中喜欢做的相同的基本操作：我们将向量分成两半，并生成两半的随机线性组合。除了这里我们还必须使用倒数 $x^{-1}$。

注意
需要 $x$ 的倒数是因为我们正在处理一个更难的代数结构，即 Pedersen 承诺，[正如这篇文章中指出的](https://www.cryptologie.net/posts/a-note-on-the-elliptic-curve-pairing-checks-in-zero-knowledge-proofs/)，它基本上是你所承诺的内容（隐藏在指数中）的随机线性组合。这使得在不产生错误结果的情况下对其条目执行任何线性组合变得困难，因为存在随机性。幸运的是，使用 $x^{-1}$ 将很好地允许我们“消除”烦人的项，这一点很快就会变得显而易见。

以下是我们如何折叠输入：

• $\vec{a'} = x^{-1} (a_1 a_2) + x (a_3 a_4)$
• $\vec{b'} = x (b_1 b_2) + x^{-1} (b_3 b_4)$

然后你得到两个大小减半的新向量 $\vec{a'}, \vec{b'}$。到目前为止，这并没有多大意义，所以让我们看看它们的内积是什么样的：

$\langle \vec{a'}, \vec{b'} \rangle = \langle (x^{-1} a_1 + x a_3 \quad x^{-1} a_2 + x a_4), (x b_1 + x^{-1} b_3 \quad x b_2 + x^{-1} b_4) \rangle = (a_1 b_1 + a_2 b_2 + a_3 b_3 + a_4 b_4) + x^{-2} (a_1 b_3 + a_2 b_4) + x^2 (a_3 b_1 + a_4 b_2) = \langle \vec{a}, \vec{b} \rangle + x^{-2} (L) + x^2 (R)$

对于一些与所选的挑战 $x$ 无关的交叉项 $L$ 和 $R$（因此，当我们使用 Fiat-Shamir 转换此协议时，证明者需要在抽取 $x$ 之前生成 $L$ 和 $R$）。

哇，你注意到了吗？新的内积取决于旧的内积。这意味着作为验证者，你可以通过计算以下内容以可验证的方式生成减少的内积结果

$\langle \vec{a'}, \vec{b'} \rangle = \langle \vec{a}, \vec{b} \rangle + \text{stuff}$

如果你有一个承诺 $C = \langle \vec{a}, \vec{b} \rangle Q$，那么你可以生成一个减少的承诺 $C' = C + \text{stuff}$，其中“stuff”主要由证明者提供，并且不会干扰 $C$，因为挑战会转移/随机化垃圾（它看起来像 $x^{-2} [L] + x^2 [R]$，其中 $[L]$ 和 $[R]$ 是对 $L$ 和 $R$ 的承诺）。

因此，我们解决了如何以可验证的方式减少内积结果的问题。但是输入呢？今天你很幸运，因为你可以对 a 和 b 的承诺使用相同的技巧！因此，基本上，你得到 $[\vec{a'}] = \text{reduce}([\vec{a}], x, \text{stuff})$（对于 $\vec{b}$ 来说，类似）。

我们可以通过一个快速的例子来复习一下，但这和我们上面所做的非常相似，只是需要减少生成器 $\vec{G}$ 和 $\vec{H}$。

让我们从减少生成器开始，让我们只展示如何使用 $\vec{G}$ 来做到这一点：

$\vec{G'} = x (G_1 G_2) + x^{-1} (G_3 G_4)$

现在让我们看看我们减少的第一个输入 $\vec{a'}$ 的 Pedersen 承诺是什么样的：

$A' = \langle \vec{a'}, \vec{G'} \rangle = (x^{-1} a_1 + x a_3)(x G_1 + x^{-1} G_3) + (x^{-1} a_2 + x a_4)(x G_2 + x^{-1} G_4) = A + x^{-2} (a_1 G_3 + a_2 G_4) + x^2 (a_3 G_1 + a_4 G_2) = A + x^{-2} L_a + x^2 R_a$

换句话说，$\langle \vec{a'}, \vec{G'} \rangle = \langle \vec{a}, \vec{G} \rangle + \text{stuff}$（对于第二个输入也类似）。

请注意，在 Bulletproofs 协议中，我们处理的是单个承诺 $P = A + B + C$，因此我们会将该陈述减少为 $P' = P + \text{stuff}$，其中 stuff 包含所有单独承诺的聚合 $L$ 和 $R$。

因此，简单回顾一下，这就是你在此协议的第一轮中主要做的事情：

1. 我们从 $P = \langle \vec{a}, \vec{G} \rangle + \langle \vec{b}, \vec{H} \rangle + \langle \vec{a}, \vec{b} \rangle Q$ 开始

2. 证明者生成点 $L$ 和 $R$

3. 验证者抽取一个挑战 $x$

4. 他们都生成 $P' = P + x^{-2} L + x^2 R$

此时，证明者可以选择释放 $\vec{a'}$ 和 $\vec{b'}$，验证者可以通过将其与预期的打开 $\langle \vec{a'}, \vec{G'} \rangle + \langle \vec{b'}, \vec{H'} \rangle + \langle \vec{a'}, \vec{b'} \rangle Q$ 进行比较来检查这是否是 $P'$ 的有效打开。

Bulletproofs 并没有就此止步，而是注意到减少的陈述看起来像你可以给 Bulletproofs 的另一个陈述。因此，在完整的协议中，证明者和验证者多次减少原始陈述，直到他们获得大小为 1 的减少的输入。当然，在实践中，你可以更早停止。

警告
请注意，我们计算了 $\langle \vec{a'}, \vec{b'} \rangle Q$，这很重要，因为你要确保内积结果确实是 $\langle \vec{a'}, \vec{b'} \rangle$，而不是一些任意值。以减少的形式检查这一点可以高概率地告诉你，这在原始陈述 P 中也是正确的。

最后一个细节是，在实际实现中，减少不是由验证者逐个检查的，而是将所有减少检查聚合为单个检查。这意味着验证者基于在协议的许多轮/减少期间看到的挑战，知道如何直接计算最终减少的生成器、输入和交叉项。

通过一个简单的例子，你可以很快看到这一点：两轮生成器折叠。下图显示了最终会出现在每个减少的元素（在这种情况下，是构成向量 $\vec{G}$ 的生成器）前面的挑战的最终乘积，可以看作是挑战的二叉树所采取的路径：

在下一部分中，我们将看到如何在 sagemath playground 中将这些东西连接起来！

zkSecurity 为密码系统提供审计、研究和开发服务，包括零知识证明、MPC、FHE 和共识协议。

了解更多 →

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