在内积证明（inner product arguments）的语境下，范围证明是指证明标量 $v$ 已经被承诺为 $V$，并且对于某个非负整数 $n$，$v$ 小于 $2^n$。

本文将展示 Bulletproofs 论文是如何构建这种证明的。其高层理念是，如果我们能证明向量 $\mathbf{a}_L$ 仅由 1 和 0 组成，并且 $\mathbf{a}_L$ 是 $v$ 的二进制表示，那么 $v$ 必然小于 $2^n$。这就好比说一个能装进 8 位无符号整数的数字必然小于 256。

使用 Bulletproofs 进行范围证明的优势在于，可以直接构建范围证明，而无需使用算术电路。

Monero 使用了 Bulletproofs 范围证明（即本文介绍的算法）来确保交易金额之和不为负数（在有限域中，负数是指大于 $p/2$ 的元素，因为它们是小于或等于 $p/2$ 的元素的加法逆元，其中 $p$ 是域的阶）。

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

符号说明

$\mathbf{0}^n$ 是一个全零的 $n$ 维向量。

$\mathbf{1}^n$ 是一个全 1 的 $n$ 维向量。

$\mathbf{2}^n$ 是一个 $n$ 维向量 $[1,2,4,8,...,2^{n-1}]$。

$\mathbf{y}^n$ 是一个 $n$ 维向量 $[1, y, y^2, y^3, ..., y^{n-1}]$。

$\mathbf{y}^{-n}$ 是一个 $n$ 维向量 $[1, y^{-1}, y^{-2}, ..., y^{-(n-1)}]$。

注意 $\mathbf{y}^n\circ\mathbf{y}^{-n}=\mathbf{1}^n$。

范围证明概述

要证明 $V$ 是对一个值小于 $2^n$ 的标量的承诺，需要证明以下几点：

1. $\mathbf{a}_L$ 是二进制的（只包含值 $0$ 和 $1$）。
2. 内积 $\langle \mathbf{a}_L,\mathbf{2}^n\rangle=v$。

第二点很容易证明，我们进行常规的内积证明，然后揭示 $\mathbf{2}^n$ 是承诺中的向量之一——或者让验证者自己构建 $\mathbf{2}^n$ 的承诺。然而，在没有算术电路的情况下证明 $\mathbf{a}_L$ 是二进制的，需要用到一些代数技巧。

四个实用的技巧

Bulletproofs 论文隐式地使用了四个代数技巧，在直接查看范围证明算法之前，最好先显式地讲解它们。

1. 证明 $\mathbf{a}_L$ 是二进制的

声明 $\mathbf{a}_L$ 是二进制的等价于以下两个断言：

• $\mathbf{a}_R = \mathbf{a}_L-\mathbf{1}^n$
• $\mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}^n$

例如，如果 $\mathbf{a}_L = [1,0,0,1]$，那么 $\mathbf{a}_R=[0,-1,-1,0]$。

在这种情况下，$\mathbf{a}_L \circ\mathbf{a}_R=\mathbf{0}^n$，因为

现在考虑 $\mathbf{a}_L$ 不是二进制的情况，例如 $[2, 1, 0, 0]$。$\mathbf{a}_R$ 将是 $[1,0,-1,-1]$，$\mathbf{a}_L$ 和 $\mathbf{a}_R$ 的 Hadamard 乘积（Hadamard product）将是 $[2,0,0,0] \neq \mathbf{0}^n$。

更一般地说，如果 $\mathbf{a}_L$ 有一个非二进制的元素，该元素减去 $1$ 后，在 $\mathbf{a}_R$ 中对应的结果元素将是非零的。当计算 Hadamard 乘积时，在那个特定的索引处，$\mathbf{a}_L$ 和 $\mathbf{a}_R$ 都将是非零的，其乘积也是非零的，这意味着 $\mathbf{a}_L \circ \mathbf{a}_R \neq \mathbf{0}^n$。

然而，如果 $\mathbf{a}_L$ 中某个特定元素为 $1$，那么 $\mathbf{a}_R$ 在该索引处将为 $0$，因此在该索引处的 Hadamard 乘积也将为零。

最后，如果 $\mathbf{a}_L$ 中某个特定元素为 $0$，那么 $\mathbf{a}_R$ 在该索引处将为 $-1$，它们在该索引处的逐元素乘积仍然为零。

因此，如果 $\mathbf{a}_L$ 是二进制的并且 $\mathbf{a}_R$ 按 $\mathbf{a}_R = \mathbf{a}_L-\mathbf{1}$ 计算，那么 $\mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}^n$。

2. 证明一个向量为全零

假设我们希望证明 Pedersen 承诺 $A$ 包含一个全零向量。我们创建 Pedersen 承诺 $A = \langle\mathbf{a},\mathbf{G}\rangle + \alpha B$，并希望向验证者证明 $\mathbf{a}=\mathbf{0}^n$。

看起来仅仅发送盲化因子 $\alpha$ 就足够了，但为了让我们的方案更具可组合性，我们不希望泄露盲化因子，因为这可能会影响我们创建的其他承诺。

相反，证明者将 $A$ 发送给验证者，验证者回复一个充满随机值的向量 $\mathbf{r}$。现在证明者必须证明

请注意，这是一个概率测试。在 $\mathbf{a}\neq\mathbf{0}^n$ 的情况下，$\langle\mathbf{a},\mathbf{r}\rangle=0$ 是有可能的，但概率可以忽略不计；同时证明者不可能伪造这样的 $\mathbf{a}$，因为他们无法预先知道 $\mathbf{r}$ 会是什么。

然而，传输 $\mathbf{r}$ 需要 $\mathcal{O}(n)$ 的通信开销，因此验证者改为只发送单个随机元素 $y$，而证明者计算 $\mathbf{y}^n$ 并将 $\mathbf{y}^n$ 用作随机向量。

然后，证明者证明 $\langle\mathbf{a},\mathbf{y}^n\rangle=0$。

3. 证明内积具有 $\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle$ 的形式，其中 $y$ 由验证者选择，且证明者计算 $\mathbf{y}^n$

我们还没有机制来证明 $\mathbf{a}_L\circ\mathbf{a}_R=\mathbf{0}^n$，因为这是一个 Hadamard 乘积，而不是内积。然而，声明向量 $\mathbf{a}_L\circ\mathbf{a}_R$ 恒等于 $\mathbf{0}^n$ 就相当于声明 $\langle\mathbf{a}_L\circ\mathbf{a}_R,\mathbf{y}^n\rangle=0$。根据内积规则，我们可以将 $\mathbf{a}_R$ 移到内积的另一侧，现在我们得到 $\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle=0$。

验证者将收到对 $\mathbf{a}_L$ 和 $\mathbf{a}_R$ 的承诺，而不是对 $\mathbf{a}_R\circ\mathbf{y}^n$ 的承诺。这就需要验证者自行构建对 $\mathbf{a}_R\circ\mathbf{y}^n$ 的承诺，以确信证明者在内积中使用了 $\mathbf{a}_R\circ\mathbf{y}^n$ 作为第二个向量。

我们所依赖的关键技巧是，证明者使用基向量 $\mathbf{G}$ 和 $\mathbf{H}$ 来对其向量进行承诺，而验证者使用 $\mathbf{G}$ 和 $\mathbf{H}\circ\mathbf{y}^{-n}$。

当证明者发送求值结果 $\mathbf{r}_u$ 时，证明者必须确保 $\mathbf{y}^n$ 项会与验证者基向量 $\mathbf{y}^{-n}\circ\mathbf{H}$ 中的 $\mathbf{y}^{-n}$ 相抵消。

具体来说，证明者构建承诺

并将 $(A, S)$ 发送给验证者。由于在本例中 $V$ 为零，所以不需要对 $V$ 进行承诺并发送。

证明者的多项式将是

关键在于，证明者将 $\mathbf{s}_R$ 与 $\mathbf{y}^n$ 进行了 Hadamard 相乘。在以前，$\mathbf{r}(x)$ 被计算为 $\mathbf{r}(x)=\mathbf{a}_R\circ\mathbf{y}^n + \mathbf{s}_Rx$（没有 $\mathbf{y}^n\circ\mathbf{s}_R$）。这将在稍后允许当验证者计算承诺 $\langle\mathbf{r}_u,\mathbf{y}^{-n}\circ\mathbf{H}\rangle$ 时，抵消掉所有的 $\mathbf{y}^n$ 项。在底层逻辑上，$\mathbf{r}_u$ 是 $(\mathbf{a}_R+\mathbf{s}_Ru)\circ\mathbf{y}^n$，因此当验证者计算 $\langle(\mathbf{a}_R+\mathbf{s}_Ru)\circ\mathbf{y}^n,\mathbf{y}^{-n}\circ\mathbf{H}\rangle$ 时，$\mathbf{y}^n$ 将被抵消，即：

然而，证明者现在还不能计算 $\mathbf{l}(x)$ 或 $\mathbf{r}(x)$，因为验证者还没有发送 $y$。因此，在收到 $(A, S)$ 后，验证者发送 $y$，证明者计算 $\mathbf{y}^n$ 并计算多项式 $t(x)$：

其中

证明者将系数 $t_1$ 和 $t_2$ 承诺为

并将 $(T_1, T_2)$ 发送给验证者。验证者用 $u$ 回应，证明者对向量多项式 $\mathbf{l}(x)$ 和 $\mathbf{r}(x)$ 进行求值：

注意，$\pi_t$ 只包含 $t_1$ 和 $t_2$ 的盲化因子。在之前的实现中，$\pi_t$ 被计算为 $\gamma + \tau_1u+\tau_2u^2$，其中 $\gamma$ 是 $V$ 的盲化因子，它也是多项式 $t(x)$ 的常数项系数。

这里没有盲化因子 $\gamma$，因为没有对 $V$ 的承诺，也就是说 $v$ 不是秘密的——它是 $0$。证明者发送 $(\mathbf{l}_u, \mathbf{r}_u, t_u, \pi_{lr}, \pi_t)$，验证者检查：

第一个关键区别是，由于之前讨论的原因，对 $\mathbf{r}_u$ 的承诺是相对于基向量 $\mathbf{y}^{-n}\circ\mathbf{H}$ 而不是 $\mathbf{H}$ 进行的。

其次，$t_uG\stackrel{?}{=} T_1 u + T_2 u^2 - \pi_t B$ 没有常数承诺。通常情况下，等式为 $t_uG\stackrel{?}{=} \boxed{V}+T_1 u + T_2 u^2 - \pi_t B$，但在本例中 $V$ 是对 $0$ 的承诺。

一般来说，如果 $V$ 包含验证者已知的值，验证者可以自行构建对 $V$ 的承诺，正如我们在下一节中所展示的。

4. 在涉及加法公开常数的情况下证明内积

正如上一节所暗示的，如果验证者知道底层向量，验证者就可以重构承诺。

例如，假设我们要证明

$\langle\mathbf{a}_L + \mathbf{j},\mathbf{a}_R\circ\mathbf{y}^n + \mathbf{k}\rangle=vz$

其中 $\mathbf{j}$ 和 $\mathbf{k}$ 是验证者已知的向量，$z$ 是验证者事先已知的标量。与 $\mathbf{y}^n$ 不同，这些向量和标量在证明开始之前就是已知的。请注意，在本例中 $\mathbf{k}$ 没有被 $\mathbf{y}^n$ 进行 Hadamard 乘法。

证明者仍然像往常一样只对秘密值 $\mathbf{a}_L$、$\mathbf{a}_R$ 和 $v$ 做出承诺：

像往常一样，多项式 $\mathbf{l}(x)$ 和 $\mathbf{r}(x)$ 的常数项是原始内积中的向量，线性项是 $\mathbf{s}_L$ 和 $\mathbf{s}_R$。在从验证者那里收到 $y$ 后，证明者计算 $\mathbf{y}^n$ 并构造（但不求值）$\mathbf{l}(x)$ 和 $\mathbf{r}(x)$：

请注意，$\mathbf{k}$ 没有与 $\mathbf{y}^n$ 进行 Hadamard 相乘，但线性项 $\mathbf{s}_R$ 仍然进行了相乘。我们稍后将展示验证者如何处理这一点。

目前，我们将 $t(x)$ 计算为

其中

注意 $t(x)$ 中的常数项是 $vz$ 而不是 $v$。承诺被计算为

并发送给验证者，然后验证者发送随机值 $u$。

证明者计算：

注意 $\pi_t$ 中的常数项是 $\gamma z$。证明者发送 $(\mathbf{l}_u,\mathbf{r}_u,t_u,\pi_{lr},\pi_t)$。最后，验证者计算：

$\mathbf{l}_u$ 和 $\mathbf{r}_u$ 分别包含 $\mathbf{j}$ 和 $\mathbf{k}$，但 $A$ 和 $S$ 并不包含。因此，验证者计算对这些向量的承诺，并将它们加到承诺 $A$ 和 $S$ 中。对于 $\mathbf{k}$，基向量 $\mathbf{y}^{-n}\circ\mathbf{H}$ 会导致 $\mathbf{k}$ 变成 $\mathbf{k}\circ\mathbf{y}^{-n}$，因此必须相对于 $\mathbf{y}^{-n}\circ\mathbf{H}$ 来计算承诺。最后，盲化因子 $\pi_t$ 包含 $vz$，但 $V$ 并不包含 $z$。因此，证明者必须将 $V$ 乘以 $z$。

通过计算 $\langle\mathbf{j},\mathbf{G}\rangle$、$\langle\mathbf{k},\mathbf{y}^n\circ\mathbf{H}\rangle$ 和 $Vz$，验证者可以确信内积计算中确实包含了这些项。

范围证明

为了证明 $V$ 是一个小于 $2^n$ 的值，我们需要证明三件事：

• 内积 $\langle \mathbf{a}_L,\mathbf{2}^n\rangle = V$，即 $\mathbf{a}_L$ 是 $v$ 的二进制表示
• $\mathbf{a}_R=\mathbf{a}_L-\mathbf{1}$
• $\mathbf{a}_L \circ \mathbf{a}_R = \mathbf{0}$

最后两个声明并不直接采用内积的形式。然而，我们可以稍微修改它们以实现这一目标。我们实际上要表达的是，向量

• $\mathbf{a}_R - \mathbf{a}_L+\mathbf{1}$
• $\mathbf{a}_L\circ\mathbf{a}_R$

都是 $\mathbf{0}^n$。我们可以使用上一节中的技巧来证明它们为零。也就是说，证明者需要确立

和

其中 $\mathbf{y}^n$ 是从验证者发送的 $y$ 值派生出的随机向量。

原始的 Bulletproofs 论文对第一个声明进行了如下微调，以便我们可以使用上一节中的第三个技巧：

因此，证明者需要建立三个内积：

1. $\langle \mathbf{a}_L,\mathbf{2}^n\rangle = v$
2. $\langle\mathbf{a}_L,\mathbf{a}_R\circ\mathbf{y}^n\rangle=\mathbf{0}^n$
3. $\langle\mathbf{a}_L -\mathbf{1}^n- \mathbf{a}_R,\mathbf{y}^n\rangle=\mathbf{0}^n$

将三个内积合并为一个

使用由验证者提供的随机数 $z$ 进行随机线性组合，可以将这三个内积合并为一个内积。

通过一些非常繁琐的内积代数运算，我们可以如下合并所有的内积。我们将在附录中展示推导过程。

下面方框中的项包含验证者已知的值，因此我们将构建验证算法来显式检查这些值。也就是说，由验证者（而不是证明者）计算对框内各项值的承诺：

为了节省篇幅，Bulletproofs 论文将项 $(z - z^2) \cdot \langle \mathbf{1}^n, y^n \rangle - z^3 \langle \mathbf{1}^n, 2^n \rangle$ 称为 $\delta(y,z)$，所以该内积可以写为

注意 $\delta(y,z)$ 是一个验证者可以计算的值。

范围证明算法

证明者选择 $v$ 及其二进制表示 $\mathbf{a}_L$，并计算 $\mathbf{a}_R = \mathbf{a}_L - \mathbf{1}$。

证明者然后随机选择盲化因子 $\alpha$，并使用基向量 $\mathbf{G}$ 和 $\mathbf{H}$ 计算对 $\mathbf{a}_L$ 和 $\mathbf{a}_R$ 的组合承诺为

证明者随后选择即将创建的向量多项式 $\mathbf{l}(x)$ 和 $\mathbf{r}(x)$ 的线性项作为 $\mathbf{s}_L$ 和 $\mathbf{s}_R$，并对它们进行承诺

证明者将内积承诺为 $V$，它是关于未知离散对数的基点 $G$（与 $\mathbf{G}$ 无关）进行的承诺：

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

验证者回复随机值 $(y, z)$，证明者将使用它们将三个内积合并为一个。

内积的左半部分 $\mathbf{a}_L-z\cdot\mathbf{1}$ 将作为 $\mathbf{l}(x)$ 的常数项，而 $\mathbf{y}^n \circ\mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n$ 将作为 $\mathbf{r}(x)$ 的常数项。

因此，我们将 $\mathbf{l}(x)$ 构造为

并将 $\mathbf{r}(x)$ 构造为

注意，出于上面前置条件部分第 3 点所讨论的原因，我们将 $\mathbf{s}_Rx$ 与 $\mathbf{y}^n$ 进行了逐元素相乘。

证明者现在可以构造 $t(x) = \langle\mathbf{l}(x),\mathbf{r}(x)\rangle$，其常数项系数 $t_0$、线性项系数 $t_1$ 和二次项系数 $t_2$ 计算如下：

其中 $t(x) = t_0 + t_1x + t_2x^2$

证明者发送对 $t_1$ 和 $t_2$ 的承诺如下

不需要对 $t_0$ 进行承诺——请注意，它正是我们试图证明的内积，因此验证者已经拥有了它的承诺，即 $V$。

验证者发送随机数 $u$，证明者计算

注意，$\pi_t$ 的常数项乘以了 $z^2$，以反映原始内积的 $z^2\cdot v$ 项。

验证者随后计算新的基向量 $\mathbf{H}_{\mathbf{y}^{-1}}=\mathbf{y}^{-n}\circ\mathbf{H}$ 并运行以下检查：

$t_u \stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{r}_u \rangle$

$A + Su + \boxed{\langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle} + \boxed{\langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle}\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H}_{y^{-1}} \rangle + \pi_{lr} B$

$t_uG+\pi_tB=V\boxed{z^2}+\boxed{\delta(y,z)}\cdot G+T_1u+T_2u^2$

回顾一下，证明者并没有对用于内积左右两侧的完整向量进行承诺，而只承诺了 $\mathbf{a}_L$ 和 $\mathbf{b}_L$。其余的向量是对验证者已知的加法公开向量，因此验证者通过构造对常数项的承诺，并将它们加到由证明者提供的秘密向量的承诺上，从而重构了对向量的承诺。

作为提醒，以下是原始内积，验证者已知的值已加框标出：

建议读者验证：在原始内积中加框的项（验证者已知的值）已经在上述的一组等式检查中，由验证者在框内各项里进行了重构。

通过复制证明者的部分计算，验证者可以断言证明者确实如其所称的那样执行了计算。

验证算法的正确性

我们现在展示，如果证明者是诚实的，那么最终的验证检查是完全正确的。

下面我们将展示精确的代数运算，但从直觉上看，验证者是在“重构”内积的左向量 $\mathbf{a_L} - z \cdot \mathbf{1}^n$、内积的右向量 $\mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n$ 以及输出结果 $z^2v+\delta(y,z)$。

验证者并没有被给出对 $\mathbf{a_L} - z \cdot \mathbf{1}^n$ 和 $\mathbf{y}^n \circ \mathbf{a_R} + \mathbf{y}^n\cdot z + z^2 \cdot 2^n$ 的承诺，而只有对 $\mathbf{a}_L$ 和 $\mathbf{a}_R$ 的承诺。同样，验证者并没有被给出对输出 $z^2v + \delta(y,z)$ 的承诺，而只给出了对 $v$ 的承诺。

加法项以及被 $\mathbf{y}^n$ 逐元素相乘的项必须由验证者进行重构。

$t_u = \mathbf{t}(u)$ 的正确性

对于 $t_u\stackrel{?}=\langle\mathbf{l}_u,\mathbf{r}_u\rangle$ 检查，根据定义这是成立的，因为这正是证明者计算 $t_u$ 的方式。

关于 $A$ 和 $S$ 承诺的 $\mathbf{l}(x)$ 和 $\mathbf{r}(x)$ 的正确性

对于
$A + Su + \langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle\stackrel{?}{=} \langle \mathbf{l}_u, \mathbf{G} \rangle + \langle \mathbf{r}_u, \mathbf{H}_{y^{-1}} \rangle + \pi_{lr} B$

我们做以下替换：

$\underbrace{\langle\mathbf{a}_L,\mathbf{G}\rangle+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B}_A + \underbrace{(\langle\mathbf{s}_L,\mathbf{G}\rangle+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B)}_Su + \langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle\stackrel{?}{=} \langle \underbrace{\mathbf{a}_L-z\cdot\mathbf{1}+\mathbf{s}_Lu}_{\mathbf{l}_u}, \mathbf{G} \rangle + \langle \underbrace{\mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_Rx}_{\mathbf{r}_u}, \mathbf{H}_{y^{-1}} \rangle + \underbrace{(\alpha+\beta u)}_{\pi_{lr}} B$

所有 $\mathbf{G}$ 项按如下方式抵消：

$\cancel{\langle\mathbf{a}_L,\mathbf{G}\rangle}+\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B + (\cancel{\langle\mathbf{s}_L,\mathbf{G}\rangle}+\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B)u + \cancel{\langle -z\cdot\mathbf{1}^n,\mathbf{G}\rangle} + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \cancel{\langle \mathbf{a}_L-z\cdot\mathbf{1}+\mathbf{s}_L u, \mathbf{G} \rangle} + \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R x, \mathbf{H}_{y^{-1}} \rangle + (\alpha+\beta u) B$

$\langle\mathbf{a}_R,\mathbf{H}\rangle+\alpha B + (\langle\mathbf{s}_R,\mathbf{H}\rangle+\beta B)u + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R x, \mathbf{H}_{y^{-1}} \rangle + (\alpha+\beta u) B$

与 $B$ 相关的盲化因子按如下方式抵消：

$\langle\mathbf{a}_R,\mathbf{H}\rangle+\cancel{\alpha B} + (\langle\mathbf{s}_R,\mathbf{H}\rangle+\cancel{\beta B)u} + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R x, \mathbf{H}_{y^{-1}} \rangle + \cancel{(\alpha+\beta u) B}$

$\langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{y}^n\circ(\mathbf{a}_R+z\cdot\mathbf{1})+z^2\mathbf{2}^n+\mathbf{y}^n\circ\mathbf{s}_R u, \mathbf{H}_{y^{-1}} \rangle$

$\mathbf{H}_{y^{-1}}$ 与 $\mathbf{y}^n$ 项抵消：

$\langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n+z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{a}_R+z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle\mathbf{s}_R u, \mathbf{H} \rangle$

拆分内积：

$\langle\mathbf{a}_R,\mathbf{H}\rangle + (\langle\mathbf{s}_R,\mathbf{H}\rangle u) + \langle z\cdot\mathbf{y}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle z^2\cdot\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle \stackrel{?}{=} \langle \mathbf{a}_R,\mathbf{H}\rangle+\langle z\cdot\mathbf{1},\mathbf{H}\rangle+\langle z^2\mathbf{2}^n,\mathbf{H}_{\mathbf{y}^{-1}}\rangle+\langle\mathbf{s}_R u, \mathbf{H} \rangle$

抵消等式两侧都出现的项：

将 $\mathbf{y}^n$ 移到另一侧：

$t(u)$ 求值的正确性

要看出

是正确的，我们可以如下代入各项：

其中 $\mathbf{l}_u$、$\mathbf{r}_u$、$t_1$、$t_2$ 为：

然而，这样的代数运算将极其混乱。相反，我们观察到 $z^2v+\delta(y,z)G$ 是向量多项式内积 $\langle\mathbf{l}(x),\mathbf{r}(x)\rangle$ 的常数项。为了抵消 $V$ 中 $\gamma B$ 的盲化因子，请注意 $\pi_t$ 包含了 $z^2\gamma$，因此这将与 $Vz^2 = (vG + \gamma B)z^2$ 中的 gamma 项相抵消。

因为 Pedersen 承诺是加法同态的，验证者可以简单地计算 $\delta(y,z)G$ 并将其加到 $Vz^2$ 上，从而计算出多项式 $t(x)$ 常数项的承诺。

对数级大小的范围证明

我们可以通过发送一个对 $\mathbf{l}_u$ 和 $\mathbf{r}_u$ 的承诺 $C$，并使用对数级大小的证明来证明所承诺的向量具有内积 $t_u$，从而减少数据传输的大小，然后验证

以及

是相对于基向量 $\mathbf{G}$ 和 $\mathbf{H}_{\mathbf{y}^{-1}}$ 成立的。

将范围证明算法应用于子集和问题

子集和问题提出这样的问题：“给定一组数字，是否存在一个子集（可能包括整个集合）的总和为 $k$？”例如，如果 $k = 16$ 且集合为 $\set{3,5,7,11}$，答案是“是”，因为 $5 + 11 = 16$。但是，如果 $k=13$，则答案为“否”。

子集和问题是一个 NP-Complete（NP完全）问题，这意味着，类似于布尔电路或算术电路，它可以表示NP中的任何问题。也就是说，NP中的任何问题都可以重写（技术术语为“归约（reduced）”）为一个子集和问题实例。

通过将 $\mathbf{2}^n$ 替换为 $[3,5,7,11]$，我们可以证明自己知道子集和问题的解，而无需泄露答案。具体来说，如果 $k=16$，证明者会知道 $\mathbf{a}_L= [0,1,0,1]$。一般来说，$\mathbf{a}_L$ 中的 1 表示我们把该元素包含在子集中，0 则表示不包含在子集中。

因此，Bulletproofs 能够为 NP 中的任何问题证明对任何见证（witness）的知识。

附录：将三个内积合并为一个的推导

从三个内积开始

我们将展示如何使用之前学过的内积代数来推导最终结果

1. 中间项可以被拆分为独立的内积：