Bulletproofs ZKP 允许证明者通过对数大小的证明来证明其知道某个内积。Bulletproofs 不需要可信设置（trusted setup）。

在前面的章节中，我们展示了如何在不泄露向量或内积的情况下证明对内积的知识，尽管其证明大小为 $\mathcal{O}(n)$，其中 $n$ 是向量的长度。我们还展示了如何使用对数大小的数据来证明对内积的知识，但不具备零知识属性。

在本章中，我们将这些算法结合起来，以展示 Bulletproof ZK 算法。

（本文是 ZK Bulletproofs 系列的一部分。）

问题陈述

证明者和验证者就长度为 $n$ 的两个椭圆曲线基向量 $\mathbf{G}$ 和 $\mathbf{H}$，以及椭圆曲线点 $Q$ 和 $B$ 达成一致。所有这些点之间的离散对数关系都是未知的。

证明者拥有向量 $\mathbf{a}$ 和 $\mathbf{b}$，其内积为 $v$。证明者将 $\mathbf{a}$ 和 $\mathbf{b}$ 承诺为 $A$，即 $A =\langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle + \alpha B$，其中 $\alpha$ 是盲化项（blinding term）。证明者承诺 $V = \langle\mathbf{a},\mathbf{b}\rangle Q + \gamma B$。

证明者将 $(A, V)$ 发送给验证者，旨在证明 $A$ 是对 $\mathbf{a}$ 和 $\mathbf{b}$ 的承诺，且 $V$ 是对它们内积的承诺。验证者不会获知具体的向量或内积。

证明的大小必须为 $\mathcal{O}(\log n)$。

Bulletproof ZK 算法

证明者生成随机标量 $\set{\alpha, \beta,\gamma,\tau_1,\tau_2}$ 和随机向量 $\set{\mathbf{s}_L,\mathbf{s}_R}$ 并计算承诺：

证明者准备（但不发送）向量多项式：

$A$ 是对向量多项式常数项的承诺，$S$ 是对一次项的承诺，$V$ 是对内积的承诺。

证明者为 $t(x)$ 的系数创建承诺，如下所示：

请注意，$V$ 是对 $t(x)$ 常数项系数的承诺，而 $T_1$ 和 $T_2$ 分别是对 $t(x)$ 一次项和二次项系数的承诺。

证明者将 $(A, S, V, T_1, T_2)$ 发送给验证者。

验证者回复随机值 $u$。

然后证明者在 $u$ 处对多项式求值，并创建它们被正确求值的证明：

在之前的方法中，证明者传输 $(\mathbf{l}_u, \mathbf{r}_u, t_u, \pi_{lr}, \pi_t)$ 以便验证者可以检查：

但由于向量 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 的存在，其大小将是线性的。为了解决这个问题，证明者将 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 承诺为：

并发送 $(C, t_u, \pi_{lr}, \pi_t)$。

我们可以将前两个验证者的检查重新排列如下：

观察发现，如果我们设 $P = A + Su -\pi_{lr}B$，那么这与证明 $P$ 是对基于基向量 $\mathbf{G}$ 和 $\mathbf{H}$ 的两个向量 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 的承诺，且 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 的内积为 $t_u$ 的问题陈述是相同的。因此，我们可以复用打开为 $P$ 的承诺的对数大小的知识证明。

对于这个证明，我们不需要保密性，因为在前一个算法中 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 本来就是公开的。

现在验证者已经拥有所有必要的数据，证明者参与交互式证明，以证明 $C$ 持有对 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 的承诺，并且它们的内积为 $t_u$：

该子程序将在无需发送 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 的情况下，证明 $t_u\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle$ 和 $C\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H} \rangle$。而且它仅发送对数大小的数据。注意，上一章的递归算法使用的是承诺 $P = \langle \mathbf{a}, \mathbf{G} \rangle + \langle \mathbf{b}, \mathbf{H} \rangle + \langle\mathbf{a},\mathbf{b}\rangle Q$，因此验证者需要自己添加“$Q$ 部分”。现在验证者可以确信：

最后，验证者检查：

回想一下，$A$ 和 $S$ 分别是对向量多项式 $\mathbf{l}(x)$ 和 $\mathbf{r}(x)$ 的常数项和一次项的承诺。第一个检查确保承诺为 $C$ 的向量是这些多项式在 $u$ 处的求值。

第二个检查是为了在已知系数承诺 $V$、$T_1$ 和 $T_2$ 的情况下，确保 $t(u)$ 被正确求值。

通过 Fiat Shamir 变换实现非交互性

在实践中，此算法通过 Fiat Shamir Transform 实现非交互性。证明者无需向验证者索取随机数，而是通过连接到目前为止传输的所有数据并对其进行哈希处理来生成随机数。然后，验证者对数据重新进行哈希处理，以确保证明者正确生成了随机数。

至关重要的是，哈希必须包含之前所有的传输数据，否则该实现将出现 frozen heart vulnerability。

下一步

在实践中，具有实际意义的问题通常由多个内积组成。例如，一个秩一约束系统（Rank 1 Constraint System，R1CS）：

实际上是 $3n$ 个内积（例如，将 $\mathbf{a}$ 乘以 $L$ 的 $n$ 行，对于 $R$ 和 $O$ 也是如此）和一个 Hadamard 乘积（Hadamard product）。因此，掌握一些将多个内积合并为单一内积的数学技巧将会非常方便，这样我们就无需发送 $3n$ 个 Bulletproofs。我们将会在接下来关于随机线性组合（random linear combinations）的章节中学习如何实现这一点。

此外，一些有用的问题可以直接编码为内积，尤其是范围证明（range proof）或子集求和问题（subset sum problem）。在这些情况下，我们可以跳过将问题编码为算术电路的步骤，直接将其编码为内积。为了增加内积表示的灵活性，并为理解随机线性组合打下基础，我们将在下一章学习一些内积代数。

练习： 结合之前的练习来证明 $A =\langle\mathbf{a},\mathbf{G}\rangle + \langle\mathbf{b},\mathbf{H}\rangle + \alpha B$，其中 $\mathbf{a}$ 和 $\mathbf{b}$ 是长度为 4 的向量。你的证明应该是既简洁又具备零知识属性的。为了简单起见，请创建一个交互式证明。练习请参考 此仓库。