Bulletproofs 是一种零知识内积证明（zero knowledge inner product argument），它使证明者（prover）能够向验证者（verifier）证明他们正确计算了内积。也就是说，证明者有两个向量 $\mathbf{a} = [a_1, a_2, \dots, a_n]$ 和 $\mathbf{b} = [b_1, b_2, \dots, b_n]$，并且他们计算了 $v = \langle\mathbf{a},\mathbf{b}\rangle=a_1b_1+a_2b_2 + \dots +a_nb_n$。证明者可以选择隐藏或公开这些向量或内积结果，但仍然能让验证者相信他们诚实地进行了计算。

验证者不会接收到向量 $\mathbf{a}$、$\mathbf{b}$ 和标量 $v$，而是接收这些值的承诺（commitments）。粗略地说，你可以将其理解为验证者接收到了一个“哈希值” $h$，其中 $h = \mathsf{hash}([a_1, a_2, \dots, a_n],[b_1, b_2, \dots, b_n],v)$，然后接收到一个证明（我们称之为 $\pi$），证明该哈希值确实包含两个向量及其内积。换言之，验证者接收到 $(h, \pi)$ 并确信证明者对被哈希的值正确执行了内积操作——但验证者无法得知哈希的任何“内容”。

在执行 Bulletproof 验证部分的过程中，验证者将重构该哈希值，从而确信证明者如其所言地计算了内积。

当然，在不知道输入的情况下重构传统的哈希值是不可能的，因此 Bulletproofs 使用了一种特殊类型的哈希，称为“Pedersen Commitment”，这也是本教程第一章的主题。Pedersen Commitments 是一种基于椭圆曲线的特殊“哈希”；可以在不知道原始输入的情况下对其进行重构。

一些工程师将 $a_1b_1+a_2b_2 + \dots +a_nb_n$ 这种组合向量的操作称为“点积”（dot product）。从技术上讲，点积指的是笛卡尔平面上向量的操作，而内积（inner product）指的是任意向量的操作。因此，我们将此操作称为内积。我们使用粗体字母（如 $\mathbf{a}$）来表示向量，使用小写字母（如 $v$）来表示有限域元素（大致相当于模算术中的“标量”），并使用尖括号 $\langle\mathbf{a},\mathbf{b}\rangle$ 来表示两个向量的内积，其结果始终为一个有限域元素。

通常，为了证明零知识，证明者必须证明他们知道一个满足算术电路约束的赋值（即 witness）。然而，SNARKs，尤其是 Groth16，并不接受任意电路——电路必须采用特定格式，即 Rank One Constraint system（R1CS）。随后，通过拉格朗日插值法和多项式除法，将 R1CS 转换为二次算术程序（Quadratic Arithmetic Program，简称 QAP）。

多项式插值和多项式除法带来的额外开销显著增加了证明者的工作量。

另一方面，Bulletproofs 允许我们直接为 R1CS 创建证明，而无需使用 QAP。请思考一下，左侧的矩阵运算与右侧的内积计算是等价的：

换句话说，将 $n \times m$ 矩阵乘以 $m$ 维向量等同于计算 $n$ 个内积。因此，如果我们能直接证明内积计算正确，就不需要创建 Quadratic Arithmetic Program 的额外步骤。

此外，Bulletproofs 不使用配对（仅使用基本的椭圆曲线加法），也不需要可信设置（trusted setup）。

Bulletproofs 的缺点

证明的大小与乘法次数成对数关系，这与具有恒定大小的 ZK-SNARK 证明不同。

Bulletproofs 的主要缺点是验证者的运行时间与电路大小成线性关系。这是因为原本应由可信设置完成的工作现在必须由验证者来完成。

无算术电路的 ZK

内积的一个主要优势是它们可以“直接”对某些问题进行建模——也就是说——它们不需要算术电路。

例如，要证明一个数字 $v$ 小于 $2^n$，可以通过证明 $v$ 具有二进制表示 $\mathbf{b}$，并且 $\mathbf{b}$ 与向量 $[1,2,4,8,...,2^{n-1}]$ 的内积为 $v$ 来实现。这直接暗示了 $v < 2^n$。比如，如果 2 的幂向量是 $[1,2,4,8,16,32,64,128]$，那么我们就知道 $v$ 必须小于 256，这与 uint8 不能保存大于 255 的值的道理相同。但由于 $\mathbf{b}$ 是隐藏的，我们并不知道 $v$ 的实际值。这被称为范围证明（range proof），因为我们在不知道实际值的情况下，知道 $v$ 处于 $[0,255]$ 范围内。

如果我们转而为范围证明创建算术电路，这将引入大量的计算开销。

对于熟悉 NP 完全性（NP-Completeness）的读者来说，子集和问题（Subset Sum problem）也可以直接使用内积证明进行建模。NP 中的任何问题都可以归约（reduced）为子集和实例，并且可以使用内积证明来证明其解。在某些情况下，这种归约可能比算术电路更高效。

实践中的 Bulletproofs

隐私区块链 Monero 使用上述的范围证明来确保交易输入中不出现负值（即有限域中的溢出）。ZCash 使用 Bulletproofs 作为使用 PLONKish 电路的 SNARK 多项式承诺的替代方案。

Bulletproofs 的线性运行时间使其不适合在 Ethereum 主网上的智能合约中使用。然而，对于需要快速生成证明和验证小型问题（如范围证明）的协议来说，Bulletproofs 难有匹敌者。

RareSkills ZK 手册中的 Bulletproofs 篇

我们对 Bulletproofs 的解析基于原始的 Bulletproofs 论文。该论文结构严谨，但内容极其硬核，因为它面向的是专业的密码学研究人员，并假设读者具备相当深厚的背景知识。我们的 Bulletproof 系列教程在很大程度上是将该论文“翻译”成资深 web3 开发者能够理解的版本。对于论文中隐式假设读者已经掌握的先决知识，我们撰写了完整的教程。

像往常一样，我们致力于提供该算法直观的心智模型，而不仅仅是照本宣科地复述算法步骤。在合适的地方，我们引入了数学动画以提高解释的效率。我们不惜一切代价避免过度简化，以便您对算法的每一步实现了什么都有充分的直觉认知。

如何阅读本文

我们假设读者已经阅读并理解了我们 ZK Book 的前九章内容。不要求熟悉 Groth16 或其他 ZK 算法。

我们附带了“填空式” Python 编码练习，以便您可以学以致用。

对于具备适当先决知识的读者，只要稍微保持自律，每天抽出不超过三个小时的时间，两周内从零开始编写 Bulletproofs 算法的代码是完全可能的。 本文对 Bulletproofs 的处理提供了一个框架，指导您在不需要过度“手把手”教学的情况下如何实现这一目标。

从某种意义上说，Bulletproofs 比 SNARKs“更简单”，因此它们是建立对 ZK 领域理解信心的绝佳方式。

目录

第 2 章介绍了 Pedersen Commitment，这是 Bulletproofs 的基础构建模块。第 3-5 章展示了如何实现具有零知识但非简洁（证明大小为 $\mathcal{O}(n)$，其中 $n$ 是向量的大小）的内积证明。第 6-7 章展示了如何在没有 ZK 的情况下证明对内积的知识，但证明大小与 $n$ 成对数关系。第 8 章展示了核心的 Bulletproofs 算法。第 9 章和第 10 章是第 11 章的先决条件，在第 11 章中我们将展示如何在不使用算术电路的情况下构建范围证明。

1. Bulletproofs 简介（本章）
2. Pedersen Commitments Pedersen Commitments 就是我们在本文开头所称的“哈希”。然而，由于它们具有加法同态性（additively homomorphic），因此它们比传统哈希函数更具可组合性。也就是说，我们可以将 2 承诺给 $A$，将 5 承诺给 $B$，并向 $A + B$“揭示” 7。
3. Polynomial Commitments via Pedersen Commitments 通过创建多项式系数的 Pedersen commitments，我们可以证明我们 1）承诺了一个多项式，并且 2）在不泄露原始多项式的情况下正确地对其进行了求值。
4. Zero Knowledge Multiplication 我们可以通过 1）提交承诺，2）对其求值，以及 3）检查前两个求值结果相乘是否等于第三个结果，来验证两个多项式是否正确相乘。通过拥有一种（在零知识情况下）将多项式相乘的方案，我们同时也能免费获得标量乘法能力。
5. Inner Product Arguments 既然我们已经有了进行乘法零知识证明的机制，只需稍作修改即可支持内积的零知识证明。具体来说，我们将标量系数多项式更改为“向量多项式”，并为系数执行向量承诺而不是标量承诺。我们还定义了“向量多项式内积”操作，使我们能够完成内积证明。虽然具备零知识属性，但这个证明还不够简洁。
6. Succinct Inner Product Arguments 通常，为了证明您正确计算了两个长度为 $n$ 的向量的内积，您需要发送 $2n$ 个元素（即这两个向量）。本章展示了一个仅发送 $n$ 个元素的巧妙技巧。
7. Logarithmic-Sized Proofs of Knowledge for Inner Products 本章递归地使用第 6 章中描述的算法来证明我们正确计算了两个大小为 $n$ 的向量的内积，且证明数据大小仅为 $\mathcal{O}(n)$。
8. Bulletproof ZKP: the algorithm end-to-end 我们将第 5 章中的零知识内积证明与第 7 章中的简洁内积相结合，生成完整的 Bulletproof。到这一步，您已经掌握了足够的知识，可以通过组合之前的练习来自己编写该算法的代码。
9. Inner Product Algebra 本章介绍并证明了用于将内积相加的各种代数恒等式，这在学习 Bulletproof 范围证明时非常有用。
10. Random Linear Combinations 我们可以使用随机线性组合技巧为多个内积创建一个证明，而不是为两个（或更多）内积创建两个（或更多）证明。
11. Range Proofs 范围证明用于证明承诺的值位于特定范围内。Bulletproofs 可以直接完成这项任务，而无需将问题算术化。Bulletproofs 范围证明了可以将一个数字编码为 2 的幂向量 $[1,2,4,...,2^{n-1}]$ 与二进制向量的内积，但不会揭示哪些位是 1 或 0。

我们建议您在阅读时复刻（fork）这个 Bulletproofs ZK 仓库并进行练习，以便您可以立即实践所学知识。

致谢

由 Henry de Valence、Cathie Yun 和 Oleg Andreev 编写的出色的 Rust Bulletproofs crate 文档在论文不够清晰的地方提供了有用的指导，有时我们使用了他们的符号表示，在某些情况下，这些符号比原始论文中的符号更直观。读者可能会发现该资源作为理解 Bulletproofs 的替代视角非常有用。