BulletProofs 详解

ZK Bulletproofs 简介

Bulletproofs 是一种零知识内积论证，它使证明者能够说服验证者他们正确计算了内积。也就是说，证明者有两个向量 $\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$，而是接收到这些值的承诺。粗略地说，可以认为验证者接收到一个“哈希” $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 承诺”的特殊哈希，这是本教程第一章的主题。Pedersen 承诺是一种基于椭圆曲线的特殊“哈希”；Pedersen 承诺可以在不了解原始输入的情况下重建。

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

为了证明零知识，证明者通常需要展示他们知道一个满足电路约束的算术电路的赋值（证人）。然而，SNARKs，尤其是 Groth16，并不接受任意电路——电路必须采用特定的格式，即 Rank One Constraint System。然后，使用 Lagrange 插值和多项式除法将 R1CS 转换为 Quadratic Arithmetic Program (QAP)。

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

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

$$ \begin{bmatrix} l{11}, l{12}, l{13}\\ l{21}, l{22}, l{23}\\ l{31}, l{32}, l{33}\\ l{41}, l{42}, l{43}\\ \end{bmatrix} \begin{bmatrix} a_1\a_2\a3 \end{bmatrix}= \begin{matrix} \langle [l{11}, l{12}, l{13}],[a_1,a_2,a3]\rangle\\ \langle [l{21}, l{22}, l{23}],[a_1,a_2,a3]\rangle\\ \langle [l{31}, l{32}, l{33}],[a_1,a_2,a3]\rangle\\ \langle [l{41}, l{42}, l{43}],[a_1,a_2,a_3]\rangle\\ \end{matrix} $$

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

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

Bulletproofs 的缺点

与 ZK-SNARK 证明的大小是常数不同，Bulletproofs 的证明大小是乘法数量的对数。

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$ 的实际值。这被称为范围证明，因为我们在不知道实际值的情况下知道 $v$ 在范围 $[0,255]$ 内。

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

对于熟悉 NP 完全性的读者，子集和问题也可以直接通过内积论证建模。任何 NP 问题都可以归约为子集和实例，并且解决方案可以通过内积论证证明。在某些情况下，这种归约可能比算术电路更高效。

Bulletproofs 的实际应用

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

Bulletproofs 的线性运行时间使其不适合用于以太坊主网上的智能合约。然而，对于需要快速生成和验证小型问题（例如范围证明）的协议来说，Bulletproofs 很难被超越。

RareSkills ZK 书籍中的 Bulletproofs

我们对 Bulletproofs 的讲解基于原始的 Bulletproofs 论文。该论文组织得非常严谨，但由于针对专业密码学研究

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