深入探讨Bulletproofs：停留在范围内

我们之前已经了解了 Bulletproofs 内部乘积参数（IPA）的工作原理：它允许我们证明我们知道一个秘密向量而不泄露它。

这很棒，但我们实际上可以用它做什么？

→ 范围证明!

Bulletproofs 是现代范围证明的支柱：它们允许我们证明一个秘密值位于给定的范围内，而不泄露该值本身。

如果你没有读过之前的 IPA 文章，请不要担心，你可以将 IPA 视为一个黑盒，它证明了一个内部乘积关系，而不会暴露向量。不过……如果你想理解它，请阅读分解 Bulletproofs（第一部分）和揭示 Bulletproofs 的魔力（第二部分）。

这里有一个关于我们今天要讨论内容的快速概述😅

(此图来自优秀的 Dalek Bulletproofs 文档)

不！🥲 不要停在这里！我保证，在本文结束时，这张看起来很奇怪的图表会变得非常清晰。

一个激励性的例子

一个很好的用例是保密转账。

想象一下，你想给朋友寄钱，但你不希望其他人看到寄了多少钱。你仍然需要证明转账是有意义的：你没有发送负数或超过你的余额。

在许多保护隐私的系统中（例如，当余额由同态承诺表示时），这需要证明金额和结果余额都保持在有效范围内，防止溢出/下溢，而不泄露它们的实际数值。

例如：

• 你可以转移的最大金额是 100
• 允许的最大余额是 1000

你将生成两个范围证明：

1. 转账金额有效： $0 \leq \text{amount} \leq 100$

2. 结果余额有效： $0 \leq \text{balance} - \text{amount} \leq 1000$

如果两者都成立，则你的转账是正确的……而无需泄露实际数字。

这些类型的证明称为范围证明，而 Bulletproofs 是有效构建它们的一种方法。

也存在其他的构造（例如，参见2024SoK 论文），但 Bulletproofs 仍然是当今最实用的证明之一。Monero 著名地采用了它们，以在生产中实现保密交易。

我们试图证明什么？

我们想要证明一个秘密值 $v$ 位于范围 $[0,2^n)$ 内，而不泄露 $v$。

你可以将相同的逻辑应用于任何范围 $[a,b]$，但今天我将保持 2 的幂，这使得数学更简洁。

正如你可能猜到的那样，我们将重用我们的向量机制和我们之前构建的内部乘积参数（需要复习吗？请查看 分解 Bulletproofs（第一部分） 和 揭示 Bulletproofs 的魔力（第二部分）😁)。

符号

每当我使用 粗体 时，这意味着我正在谈论一个向量。

• $2^n = (2^0, 2^1, 2^2, ..., 2^{n-1})$

长度为 n 的向量，包含 2 的连续幂

• $0^n = (0, 0, ..., 0)$

n 个零的向量

• $1^n = (1, 1, ..., 1)$

n 个一的向量

• $y^n = (y^0, y^1, y^2, ..., y^{n-1})$

长度为 n 的向量，包含一个随机值 y 的连续幂

• $z1^n = (z, z, ..., z)$

向量 n 个元素，全部等于 z（$1^n$ 乘以 z）

将我们的秘密数字分解为位

Bulletproofs 范围证明中的关键技巧是位分解，将一个秘密数字分解为其各个位。

注意

这与在其他系统中使用的基本方法相同：你证明每一位是 0 或 1，并且它们的加权和重构了该值。例如，在 Circom 中，这是通过 Num2Bits gadget 完成的。

虽然较新的证明系统有时使用基于查找的范围检查来提高效率，但位分解仍然是大多数协议所依赖的基本构建块。

我们将秘密值 $v$ 表示为其位的总和。

令 $a_L$ 为 $v$ 的位向量。

例如，如果 $v = 123 = 0b1111011$：

$a_L = (1, 1, 1, 1, 0, 1, 1)$

然后：

$\langle a_L, 2^n \rangle = v$

该内积精确地表达了二进制数的工作方式：

$a{L0} \cdot 2^0 + a{L1} \cdot 2^1 + ... + a_{Ln-1} \cdot 2^{n-1} = v$

_(注意：这里我假设 $aL$ 是小端序)

以我们的例子（以 大端序 形式）：

$1 \cdot 2^6 + 1 \cdot 2^5 + 1 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 64 + 32 + 16 + 8 + 2 + 1 = 123$

我们的范围证明将围绕着说服验证者：

• 这个方程成立，并且
• 每个 $a_{Li}$ 确实是一个 位 (0 或 1)

这很重要，因为验证者只会看到 $a_L$ 的 承诺，而不是向量本身。因此，如果没有此检查，证明者可以将任意值隐藏在承诺中，并且仍然使方程平衡。

说服验证者我们的位是真实的 0 和 1

我们不能只是告诉验证者我们的位，这会泄露 $v$。

所以我们需要一种方法来证明 $a_L$ 的每个分量都是 0 或 1。

对于单个数字 $x$，成为一个位意味着：

$x \cdot (x - 1) = 0$

只有当 $x$ 是 0 或 1 时，该等式才成立。

对于向量，我们使用元素级（哈达玛）乘法 $\circ$:

$x \circ (x - 1^n) = 0^n$

所以我们定义一个新的向量：

$a_R = a_L - 1^n$

我们想要证明：

$a_L \circ a_R = 0^n$

这确保了 $a_L$ 的所有条目都是二进制的。

注意

你可能想知道为什么我们引入一个新的向量，而不是直接在等式中使用 $a_L - 1^n$。

原因主要是结构性的：我们需要在证明的不同部分引用 $a_L$ 和 $a_R$，有时在一起，有时分开。

通过将此表达式分配给它自己的变量，我们使后面的方程式更简洁，更容易使用，特别是当我们开始构建涉及每个向量的内部乘积和承诺，并且独立时。每个向量在证明中扮演不同的角色，并且显式地定义它们可以确保这些承诺与我们正在强制执行的约束保持一致。

你也可以将其视为一个电路，其中每个操作都会产生一个新的变量，并且我们约束每个关系。

用伪代码表示，如下所示：

def range_proof_circuit(params, priv, pub):
    bitlen = params
    com_v = pub
    a_L, a_R, ... = priv
    assert com(sum(a_L * power_of_2)) == com_v
    assert a_R == a_L - vec_1
    assert a_L * a_R == vec_0

一个巧妙的概率技巧

我们如何证明两个隐藏的向量相乘为零而不泄露它们？

我们从一个简单的直觉开始：假设你想证明一个秘密数字 $x$ 等于 0。

如果验证者给你一个随机值 $r$，你用

$x \cdot r = 0$

(我们假设你不能作弊，必须发送该乘积的实际结果)

那么除非你（真的）很幸运，否则这种情况成立的唯一方法是 $x = 0$。

我们将相同的想法应用于向量，但有一个细微的差别……

Schwartz–Zippel 用于内积

我们刚刚看到了随机挑战如何帮助检查单个值是否等于零。

在这里，我们实际上有几个方程（每个向量元素一个），我们希望它们同时成立：

$a_i \cdot b_i = 0 \forall i$

如果不是这种情况，这些项可能会相互抵消。

例如，对于长度为 3 的向量，你可能会有：

$a_0 \cdot b_0 = 6$ $a_1 \cdot b_1 = -4$ $a_2 \cdot b_2 = -2$

即使每一行都不为零，它们的总和（内积）也等于 0，这不是我们想要的。

为了避免这种情况，我们为每一行添加随机性。

这样，即使你试图作弊，你也无法预测如何使这些项抵消。

验证者发送一个长度为 $n$ 的随机向量 $r$，证明者现在必须展示：

$\langle a_L \circ a_R, r \rangle = 0$

为什么这有效？

因为 $r$ 中的随机系数充当每个项的独立缩放，因此任何潜在的抵消实际上都变得不可能。

如果此等式对于随机挑战 $r$ 成立，则元素级乘积本身很可能都为零。

形式上，这依赖于 Schwartz–Zippel 引理：我们将左侧视为多项式，并测试它是否在随机点处求值为零。如果是这样，则很可能整个多项式完全为零，并且被愚弄的概率最多为 $d/|F|$。

为了减少通信，验证者不发送整个向量 $r$，而只是发送一个随机值 $y$。

然后，证明者构造 $r = y^n = (1, y, y^2, ..., y^{n-1})$

$a_R$ 的格式正确

我们还有最后一个问题……我们还需要表明 $a_R$ 是如实定义的：

$a_R \stackrel{?}{=} a_L - 1^n$

简单！我们通过证明另一个内积等于零来做到这一点：

$\langle a_L - 1^n - a_R, y^n \rangle = 0$

同样，因为验证者随机选择 $y$，所以证明者无法伪造它。

总结：我们必须证明的一切

总而言之，证明者需要证明三个关系，每个关系都被简化为一个可以使用 IPA 验证的内积：

$\langle a_L, 2^n \rangle = v$ $\langle a_L - 1^n - a_R, y^n \rangle = 0$ $\langle a_L, a_R \circ y^n \rangle = 0$

请注意，我稍微重新排列了第三个等式。

它等同于我们之前的内容：

$\langle a_L \circ a_R, y^n \rangle = 0$

但是该等式的结构现在与 Bulletproofs 承诺稍后表示的方式更好地对齐。

这就是我们的完整设置！从这里开始，我们将继续进行将所有内容联系在一起的更重的代数运算。

组合内积

到目前为止，我们有三个独立的内积需要证明。

这需要处理很多事情。

理想情况下，我们希望将它们捆绑成一个可以使用单个 IPA 证明的内积。

为此，我们从验证者那里引入了另一个随机挑战：$z$。

然后，我们使用 $z$ 的幂对三个等式进行随机线性组合：

$z^2 \cdot \langle a_L, 2^n \rangle + z \cdot \langle a_L - 1^n - a_R, y^n \rangle + \langle a_L, a_R \circ y^n \rangle = z^2 \cdot v$

这样，证明者就无法独立地“调整”每个等式来作弊。一切都必须与组合保持一致。

我们现在想要重新排列这个等式，以便：

• 内积的左侧只是 $a_L$ 的函数
• 右侧仅取决于 $a_R$
• 结果仅取决于 $v$ 和验证者已知的常量

这种清晰的分离将使以后承诺每一侧都容易得多。

首先展开：

$z^2 \cdot \langle a_L, 2^n \rangle + z \cdot \langle a_L, y^n \rangle - z \cdot \langle a_R, y^n \rangle - z \cdot \langle 1^n, y^n \rangle + \langle a_L, a_R \circ y^n \rangle = z^2 \cdot v$

然后将 $-z \cdot \langle a_R, y^n \rangle$ 移到另一侧，并将 $z$ 移到内积中：

$z^2 \cdot \langle a_L, 2^n \rangle + z \cdot \langle a_L, y^n \rangle - z \cdot \langle 1^n, a_R \circ y^n \rangle + \langle a_L, a_R \circ y^n \rangle = z^2 \cdot v + z \cdot \langle 1^n, y^n \rangle$ $\langle a_L, z^2 \cdot 2^n \rangle + \langle a_L, z \cdot y^n \rangle + \langle -z1^n, a_R \circ y^n \rangle + \langle a_L, a_R \circ y^n \rangle = z^2 \cdot v + z \cdot \langle 1^n, y^n \rangle$

最后按 $a_L$ 和 $a_R \circ y^n$ 分组

$\langle a_L, z^2 \cdot 2^n + z \cdot y^n + a_R \circ y^n \rangle + \langle -z1^n, a_R \circ y^n \rangle = z^2 \cdot v + z \cdot \langle 1^n, y^n \rangle$

现在将相同的项添加到两侧：

$\langle -z1^n, z^2 \cdot 2^n + z \cdot y^n \rangle$

简化后，我们得到：

$\langle a_L, z^2 \cdot 2^n + z \cdot y^n + a_R \circ y^n \rangle + \langle -z1^n, z^2 \cdot 2^n + z \cdot y^n + a_R \circ y^n \rangle = z^2 \cdot v + z \cdot \langle 1^n, y^n \rangle - \langle z1^n, z^2 \cdot 2^n + z \cdot y^n \rangle$ $\langle a_L - z1^n, z^2 \cdot 2^n + z \cdot y^n + a_R \circ y^n \rangle = z^2 \cdot v + (z - z^2) \cdot \langle 1^n, y^n \rangle - z^3 \cdot \langle 1^n, 2^n \rangle$

右侧的每个项（$v$ 除外）验证者都知道，因此我们可以将它们分组为一个仅取决于随机挑战的已知值 $\delta(y, z)$：

$\delta(y, z) = (z - z^2) \cdot \langle 1^n, y^n \rangle - z^3 \cdot \langle 1^n, 2^n \rangle$

有了它，我们最终得到了我们将要使用的单个内积：

$\langle a_L - z1^n, y^n \circ (a_R + z1^n) + z^2 \cdot 2^n \rangle = z^2 \cdot v + \delta(y, z)$

我们现在已经将所有三个约束组合为一个紧凑的内积。

随机挑战 $z$ 将它们联系在一起，因此证明者无法有选择地满足一个约束而不满足其他约束。

此等式是我们将在下一步中使用的确切形式，当我们对向量进行盲化和承诺时。

SageMath 设置

在进一步之前，让我们添加一些代码。

从现在开始，我将使用简短的 SageMath 代码片段来说明证明的每个步骤。

我们将在一个微小的玩具字段上工作，以使计算保持简单（真正的系统使用大的 256 位字段）。

具体来说，我们将使用：

• 素数域 F929，
• 该字段上的椭圆曲线：$y^2 = x^3 + 5x + 15$，它具有素数阶 919

p = 929
Fp = GF(p)
E = EllipticCurve(Fp, [5, 15])
Fr = GF(E.gens()[0].order())

目标是检查 $v$ 是 8 位

$v \in [0, 2^8)$

我们定义向量：

• $1^n$
• $2^n$

然后将 $v$ 分解为位以形成 $a_L$ 和 $a_R$

n = 8  # 比特数
print(f"我们将证明 v 在 0 和 {pow(2, n)} 之间\n")

## (2^0, 2^1, 2^2, ..., 2^(n-1))
vec_2n = vector([Fr(2 ^ i) for i in range(n)])
## (1, 1, 1, ..., 1)
vec_1n = vector([Fr(1)] * n)

v = Fr(random.randint(0, pow(2, n)))
print("v =", v)

v_bin = bin(v)[2:].zfill(n)[::-1][:n]
print("v_bin = ", v_bin)

aL = vector([Fr(int(bit)) for bit in v_bin])
assert v == sum([aL[i] * 2 ^ i for i in range(n)])

assert v == inner_product(aL, vec_2n)

## 定义 aR
aR = aL - vec_1n
assert inner_product(aL, aR) == 0

print("aL = ", aL)
print("aR = ", aR)

这与我们之前的等式匹配：

$v = \langle a_L, 2^n \rangle$

核心证明（没有零知识）

如果我们在这里停下来，我们已经可以在我们组合的内积上运行内积参数 (IPA) 并获得有效的证明，就像在上一篇文章中一样😊。

但有一个问题：IPA 没有隐藏。它会泄露关于见证人的信息，可能泄露秘密值 $v$。

在真正的协议中，我们将使用盲化向量 $s_L, s_R$ 解决这个问题。

在到达那里之前，让我们简化一下，看看一个简化的版本，没有任何盲化，会如何工作。

我们从先前组合的关系开始，并命名内积的这两个方面：

$l = a_L - z1^n$ $r = y^n \circ (a_R + z1^n) + z^2 \cdot 2^n$

一个完全天真的协议会让证明者只发送 $(l, r)$ 并证明

$\langle l, r \rangle = z^2 \cdot v + \delta(y, z)$

但这既没有约束力也没有私密性。任何人都可以伪造满足等式的向量。

所以我们添加承诺。

承诺

在该协议开始时（在知道 $y, z$ 之前），证明者承诺比特向量和值 $v$：

$A = \langle a_L, G \rangle + \langle a_R, H \rangle + \alpha \cdot H$ $V = v \cdot G + \gamma \cdot H$

这里：

• $G$ 和 $H$ 是椭圆曲线生成器的向量（$a_L$ 的每位一个）
• $G, H$ 是单个生成器，用于标量承诺
• $\alpha, \gamma$ 是用于隐藏的随机标量（盲化因子）

## 定义生成器
G = E.random_point()
H = E.random_point()

Gs = [E.random_point() for _ in range(n)]
Hs = [E.random_point() for _ in range(n)]

## Commit to v
print("\n我们可以从一开始就承诺 v")
blinding_gamma = Fr.random_element()
V = v * G + blinding_gamma * H
print(f"v 承诺 (V): {V}\n")

blinding_alpha = Fr.random_element()
A = inner_product(aL, Gs) + inner_product(aR, Hs) + blinding_alpha * H
print("A = ", A)
print("\证明者将 A, V 发送给验证者")

然后验证者发送挑战 $y, z$

print("验证者发送随机挑战 y 和 z\n")
y = Fr.random_element()
vec_y_n = vector([y ^ i for i in range(n)])

z = Fr.random_element()
vec_z_1n = vector([z] * n)

所以我们现在可以定义我们的主要关系 $\langle l, r \rangle = z^2 \cdot v + \delta(y, z)$

l = aL - vec_z_1n
r = aR.pairwise_product(vec_y_n) + vec_y_n * z + z ^ 2 * vec_2n
main_inner_product = inner_product(l, r)

delta_y_z = (z - z ^ 2) * inner_product(vec_1n, vec_y_n) - z ^ 3 * inner_product(vec_1n, vec_2n)
t = z ^ 2 * v + delta_y_z

assert main_inner_product == t
print("组合内积 = z ^ 2 * v + delta_y_z.\n我们可以继续...\n")

重新缩放生成器：$H'$

先前的承诺是在协议开始时计算的，在收到验证者的任何挑战之前。

因此，一旦验证者发送挑战 $y, z$，我们就会面临一个微妙的问题：$r$ 包含 $y$ 的幂，但是 $A$ 是在知道 $y$ 之前创建的。

内积中 $a_R$ 的每个坐标都乘以 $y^i$，但是承诺 $A$ 是用普通的 $H$ 做的。我们需要协调这些。

诀窍是将 $y^i$ 因子吸收到基中。这就是我们定义新向量的原因：

$H' = \frac{1}{y^n} \circ H$

这种重新缩放确保了，对于任何向量 $u$：

$\langle y^n \circ u, H' \rangle = \sum_i (y^i \cdot u_i) \cdot (\frac{H_i}{y^i}) = \sum_i u_i \cdot H_i = \langle u, H \rangle$

换句话说，我们可以自由地将 $y^i$ 权重从向量侧“移动”到生成器侧，而不会更改承诺。

vec_y_n_inv = vec_y_n.apply_map(lambda x: 1/x)
H_y_minus1 = [vec_y_n_inv[i] * Hs[i] for i in range(n)]

构建点 P

有了这个，证明者构建一个单个椭圆曲线点：

$P = \langle l, G \rangle + \langle r, H' \rangle$

使用公共信息，验证者可以用先前的承诺 $A, V$ 表示 $P$：

$P \stackrel{?}{=} A - \langle z1^n, G \rangle + \langle z \cdot y^n + z^2 \cdot 2^n, H' \rangle - \alpha \cdot H$

让我明确地向你展示这个等式：

$P = A - \langle z1^n, G \rangle + \langle z \cdot y^n + z^2 \cdot 2^n, H' \rangle - \alpha \cdot H = \langle a_L, G \rangle + \langle a_R, H \rangle + \alpha \cdot H - \langle z1^n, G \rangle + \langle z \cdot y^n + z^2 \cdot 2^n, H' \rangle - \alpha \cdot H = \langle a_L, G \rangle - \langle z1^n, G \rangle + \langle a_R, H \rangle + \langle z \cdot y^n + z^2 \cdot 2^n, H' \rangle = \langle a_L - z1^n, G \rangle + \langle a_R \circ y^n, H' \rangle + \langle z \cdot y^n + z^2 \cdot 2^n, H' \rangle = \langle l, G \rangle + \langle a_R \circ y^n + z \cdot y^n + z^2 \cdot 2^n, H' \rangle = \langle l, G \rangle + \langle r, H' \rangle$

完美！$P$ 的两个表示匹配。

P = A - inner_product(vec_z_1n, Gs) + inner_product(z * vec_y_n + z ^ 2 * vec_2n, H_y_minus1) - blinding_alpha * H
assert P == inner_product(l, Gs) + inner_product(r, H_y_minus1)

内积参数

最后，验证者需要根据他拥有的值：$A, V$，挑战和公共参数来检查 $P$ 是否已正确构建。

为什么它有效？现在我们了解了 $H'$，这很容易：

IPA

最后，证明者使用基 $G, H', Q$ 运行 IPA 以证明：

$P + t \cdot Q = \langle l, G \rangle + \langle r, H' \rangle + t \cdot Q$

其中：

• $Q$ 是验证者选择的另一个椭圆曲线生成器
• $t = z^2 \cdot v + \delta(y, z)$

验证者：

1. 通过上面的公式从 $A, V, y, z$ 重构 $P$

2. 验证 $\langle l, r \rangle = t$ 的 IPA 证明

就是这样！一个完全可靠但非零知识的范围证明。

print("\n最后，我们运行 IPA：P + t * Q")
Q = E.random_point()

ipa_proof = ipa(l, r, Gs, H_y_minus1, t, Q, Fr)
P_full = P + t * Q
verify(Gs, H_y_minus1, P_full, ipa_proof[0], ipa_proof[1], ipa_proof[2], ipa_proof[3], ipa_proof[4], Q, n, Fr)
print("IPA 证明 ✅")

要检查 ipa() 函数的代码，请参阅此处：ipa.sage

对于简化协议的完整脚本：range-proof-simple.sage

真正的 Bulletproof 添加了缺失的盲化多项式以使其私密。但在结构上，这已经是协议的核心。

从现在开始，一切都与隐私有关……🙈

盲化以实现零知识：向量到多项式

到目前为止，我们已经将我们的三个内积组合成一个等式，并看到了该协议的非零知识版本。

为了使证明具有零知识性，我们需要隐藏这些向量，同时仍然说服验证者该关系成立。

诀窍有两方面：

• 引入盲化因子以掩盖 $a_L, a_R$
• 并从向量移动到多项式，因此我们可以将真实数据和盲化项组合在单个结构化等式中。

让我们看看证明者如何构建这些盲化多项式并使用 Pedersen 承诺来承诺它们，隐藏所有秘密，同时保持每个等式都可验证。

使用盲化项隐藏我们的向量

证明者引入两个新的随机向量：$s_L, s_R$。

它们充当噪声以掩盖真实向量：$a_L, a_R$。

使用它们，我们定义两个取决于变量 $X$ 的多项式向量：

$l(X) = (a_L + s_L \cdot X) - z1^n$ $r(X) = y^n \circ ((a_R + s_R \cdot X) + z1^n) + z^2 \cdot 2^n$

当 $x = 0$ 时，这些多项式显示了我们关心的原始表达式：

$l(0) = a_L - z1^n$ $r(0) = y^n \circ (a_R + z1^n) + z^2 \cdot 2^n$

现在看看当我们取它们的内积时会发生什么： $\langle l(0), r(0) \rangle = \langle a_L - z1^n, y^n \circ (a_R + z1^n) + z^2 \cdot 2^n \rangle = z^2 \cdot v + \delta(y, z)$

这是我们最终想要证明的核心公式。

通过将向量转换为多项式，证明者现在可以安全地在一个随机点（由验证者选择）揭示 $l(X), r(X)$，而不是揭示完整的秘密向量。

计算它们的内积

当我们计算两个多项式向量的内积时会发生什么？

如果我们有：$ax + b$ 和 $cx + d$，那么：

$\langle ax + b, cx + d \rangle = \langle a, c \rangle x^2 + (\langle a, d \rangle + \langle b, c \rangle) x + \langle b, d \rangle$

换句话说，结果是一个二次多项式。

在我们的例子中，我们称这个多项式为 $t(X)$：

$t(X) = \langle l(X), r(X) \rangle = t_0 + t_1 \cdot X + t_2 \cdot X^2$

常数项 $t_0$ 正是我们的目标内积：

$t_0 = \langle l(0), r(0) \rangle = \langle a_L - z1^n, y^n \circ (a_R + z1^n) + z^2 \cdot 2^n \rangle = z^2 \cdot v + \delta(y, z)$

注意

为了有效地计算剩余的系数 $t_1, t_2$，我们可以使用一个简单的 Karatsuba 技巧：

$t_2 = \langle s_L, s_R \rangle$ $t_1 = \langle l(0) + s_L, r(0) + s_R \rangle - t_0 - t_2$

这节省了一些冗余的工作：我们没有逐项展开所有内容，而是重用现有部分来推导出交叉项 $t_1$。

所以从现在开始，我们的目标是：

• 证明 $t_0$ 是正确的：它等于 $z^2 \cdot v + \delta(y, z)$
• 证明 $t(X)$ 是形式良好的：
  • $l(X)$ 和 $r(X)$ 被正确构造
  • $t(X) = \langle l(X), r(X) \rangle$

对所有内容进行承诺

在验证者可以检查任何内容之前，证明者必须承诺所有相关值。 以一种具有约束力的方式（他以后不能更改它们），但仍然是隐藏的（验证者什么也学不到）。

这些承诺是对椭圆曲线点做出的，并遵循严格的顺序。

我们已经在先前描述的“简化协议”中看到很多了，但是再次提醒一下也没有什么坏处。

步骤 1： 承诺秘密值 $v$

使用随机盲化因子 $\gamma$：

$V = v \cdot G + \gamma \cdot H$

其中 $G$ 和 $H$ 是固定的、独立的椭圆曲线生成器。

步骤 2： 承诺比特向量

现在，证明者承诺向量 $a_L$ 和 $a_R$，以及盲化向量 $s_L$ 和 $s_R$：

$A = \langle a_L, G \rangle + \langle a_R, H \rangle + \alpha \cdot H$ $S = \langle s_L, G \rangle + \langle s_R, H \rangle + \rho \cdot H$

其中：

• $G$ 和 $H$ 是椭圆曲线生成器的向量（$a_L$ 的每个比特一个）
• 并且 $\alpha, \rho$ 是盲化标量

blinding_alpha = Fr.random_element()

A = inner_product(aL, Gs) + inner_product(aR, Hs) + blinding_alpha * H
print("A = ", A)

## blinding terms for left and right polys
sL = vector([Fr.random_element() for i in range(n)])
sR = vector([Fr.random_element() for i in range(n)])

blinding_beta = Fr.random_element()
S = inner_product(sL, Gs) + inner_product(sR, Hs) + blinding_beta * H
print("S = ", S)
print("\nProver sends A, S, V to Verifier")

一旦 A 和 S 被承诺，验证者（或 Fiat-Shamir 启发式）就可以产生挑战 y 和 z。

然后将这些挑战用于定义 l(X),r(X) 和 t(X)。

R.<X> = Fr[]

lX = aL - vec_z_1n + sL * X
print("lX = ", lX)
rX = vec_y_n.pairwise_product(aR + vec_z_1n) + z ^ 2 * vec_2n + vec_y_n.pairwise_product(sR * X)
print("rX = ", rX)

tX = inner_product(lX, rX)
print(f"tX = {tX}\n")

步骤 3： 承诺 t(X)

最后，证明者承诺 t(X) 的系数：线性项和二次项 t1 和 t2，每个都带有自己的盲化因子 τ1,τ2：

$T1 = t1 \cdot G + \tau1 \cdot H$ $T2 = t2 \cdot G + \tau2 \cdot H$

这些承诺确保证明者以后不能调整 t(X) 以使公式神奇地起作用。

[t0, t1, t2] = tX.coefficients(sparse=False)

print("Notice that t0 is the inner product we're trying to prove\n")
assert t0 == main_inner_product

blinding_tau1 = Fr(123)
blinding_tau2 = Fr(456)
T1 = t1 * G + blinding_tau1 * H
T2 = t2 * G + blinding_tau2 * H
print("T1 = ", T1)
print("T2 = ", T2)

整合在一起：验证

一切都快准备好了！ 🤩

证明者已经承诺了所有正确的部分。 现在，验证者只需要检查所有内容是否一致。

最终挑战

验证者发送了最后一个随机挑战 x。

通过在此随机点评估多项式 l(x),r(x) 和 t(x)，我们可以检查所声明的关系是否以极大的概率成立（感谢 Schwartz–Zippel 引理）。

证明者计算：

$l = l(x)$ $r = r(x)$ $\hat{t} = \langle l, r \rangle$ $\tau_x = \tau_2 \cdot x^2 + \tau_1 \cdot x + z^2 \cdot \gamma$ $\mu = \alpha + \rho \cdot x$

这里：

• $\hat{t}$ 是 t(X) 在 x 处的求值，等于 l 和 r 的内积
• $\tau_x$ 组合了 t(x) 的所有盲化因子
• μ 组合了 A 和 S 的盲化因子

print("\nVerifier sends challenge x\n")
x = Fr.random_element()
print("x = ", x)

## evaluate left and right polys at u
lx = lX(x)
rx = rX(x)
tx = tX(x)
print("lx = ", lx)
print("rx = ", rx)
print("tx = ", tx)
assert tx == lx * rx

print("\nProver sends proof_blindings_mu and proof_blindings_tau to Verifier")
proof_blindings_mu = blinding_alpha + blinding_beta * x
proof_blindings_tau = z ^ 2 * blinding_gamma + blinding_tau1 * x + blinding_tau2 * x ^ 2

验证者检查 #1：多项式 t(x)

首先，验证者确保 $\hat{t}$ 与声明的多项式评估 t(x) 匹配。

从概念上讲，它检查：

$\hat{t} =? \langle l, r \rangle$

并且对 t(x) 的承诺与所有先前的承诺是一致的。

实际检查是：

$\hat{t} \cdot G + \tau_x \cdot H =? z^2 \cdot V + \delta(y,z) \cdot G + T1x + T2x^2$

为什么会这样？

$t(x) \cdot G = (t0 + t1x + t2x^2) \cdot G$ $t(x) \cdot G = (z^2 \cdot v + \delta(y,z)) \cdot G + t1x \cdot G + t2x^2 \cdot G$ $t(x) \cdot G = z^2 \cdot v \cdot G + \delta(y,z) \cdot G + x(T1 - \tau1 \cdot H) + x^2(T2 - \tau2 \cdot H)$ $t(x) \cdot G = z^2 \cdot v \cdot G + \delta(y,z) \cdot G + T1x - \tau1x \cdot H + T2x^2 - \tau2x^2 \cdot H$ $t(x) \cdot G + (\tau1x + \tau2x^2) \cdot H = z^2 \cdot (V - \gamma \cdot H) + \delta(y,z) \cdot G + T1x + T2x^2$ $t(x) \cdot G + (\tau1x + \tau2x^2) \cdot H = z^2 \cdot V - z^2 \cdot \gamma \cdot H + \delta(y,z) \cdot G + T1x + T2x^2$ $t(x) \cdot G + (\tau1x + \tau2x^2 + z^2 \cdot \gamma) \cdot H = z^2 \cdot V + \delta(y,z) \cdot G + T1x + T2x^2$ $t(x) \cdot G + \tau_x \cdot H = z^2 \cdot V + \delta(y,z) \cdot G + T1x + T2x^2$

check1_lhs = tx * G + proof_blindings_tau * H
check1_rhs = V * z ^ 2 + delta_y_z * G + T1 * x + T2 * x ^ 2
assert check1_lhs == check1_rhs
print("Check 1 ✅")

验证者检查 #2：向量 l 和 r

接下来，验证者检查所揭示的向量 l 和 r 与所有先前的承诺一致。

我们先前已经解释了 H' 是什么。 但是对于比较懒的人，再次提供：

$H' = \frac{1}{y^n} \circ H$

然后计算：

$P = A + x \cdot S - \langle z \cdot 1_n, G \rangle + \langle z \cdot y^n + z^2 \cdot 2_n, H' \rangle$

并检查：

$P =? \langle l, G \rangle + \langle r, H' \rangle + \mu \cdot H$

如果此等式成立，则表示证明者的 l(x) 和 r(x) 的构建正确。

P = - proof_blindings_mu * H + A + S*x + inner_product(-vec_z_1n, Gs) + inner_product(z * vec_y_n + z ^ 2 * vec_2n, H_y_minus1)
print("P = ", P)
assert P == inner_product(lx, Gs) + inner_product(rx, H_y_minus1)
print("Check 2 ✅")

内积论证：最后一步

但是等等…… 证明者不能只发送完整的向量 l 和 r，那样会泄露太多信息。

这正是内积论证再次发挥作用的地方！

为了做好准备，我们稍微重新排列上面的等式：

$P = A + x \cdot S - \langle z \cdot 1_n, G \rangle + \langle z \cdot y^n + z^2 \cdot 2_n, H' \rangle - \mu \cdot H = \langle l, G \rangle + \langle r, H' \rangle$

并将内积结果 $\hat{t}$ 放入其中：

$P + \hat{t} \cdot Q = \langle l, G \rangle + \langle r, H' \rangle + \langle l, r \rangle \cdot Q$

（其中 Q 是用于 IPA 证明的随机椭圆曲线点）。

这是 IPA 的输入：证明者产生一个简短的递归证明，证明 $\langle l, r \rangle = \hat{t}$。

如果你忘记了，可以在这里找到我们之前的文章：分解Bulletproofs（第一部分） 和 展开Bulletproofs的魔力（第二部分）。

Q = E.random_point()
print("Remember that tx = <lx,rx>")
ipa_proof = ipa(lx, rx, Gs, H_y_minus1, tx, Q, Fr)
P_full = P + tx * Q
verify(Gs, H_y_minus1, P_full, ipa_proof[0], ipa_proof[1], ipa_proof[2], ipa_proof[3], ipa_proof[4], Q, n, Fr)
print("IPA proof ✅")

最终证明的样子

完整的范围证明包括：

• A 和 S
• T1 和 T2
• $\hat{t}$ 及其盲化因子 $\tau_x$
• μ（A 和 S 的盲化）
• IPA 证明，其中包括：
• 来自每个折叠步骤的 L 和 R 向量
• 表示最终折叠向量 l 和 r 的两个标量

就是这样！ 我们已经从头开始构建了一个完整的范围证明！ 🧠

从一个简单的想法开始：证明一个隐藏值介于 0 和 $2^n$ 之间，我们结合了一系列强大的技巧：

• 比特分解将值表示为 0 和 1 的向量
• 随机挑战 (x,y,z) 将每个等式联系在一起并防止作弊
• 承诺隐藏数据，同时保持所有关系一致
• 盲化IPA的输入和输出，因为IPA协议不是零知识的
• 最后，内积论证可以高效且紧凑地验证所有内容

所有这些结合在一起，以便验证者可以确信：“证明者的秘密值位于正确的范围内”，而不会了解该值本身的任何信息。

这个基础为机密转移、私有余额和许多其他保护隐私的系统提供支持，例如我们在本文开头介绍的系统。

你可以在这里找到完整的 Sagemath 脚本：range-proof.sage

延伸阅读

• Bulletproofs 论文
• Dalek crate 文档

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

了解更多 →

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