Bulletproofs 范围证明：无可信设置的高效区间验证

这就是范围证明的核心价值——在不泄露具体数值的前提下，证明 $v \in [0, 2^n)$。

前置知识回顾

在深入 Bulletproofs 之前，需要明确两个基础概念：

1. Pedersen 承诺（已有覆盖）

Pedersen 承诺 $C = g^m \cdot h^r \mod p$ 具有两个关键性质：

• 绑定性：给定 $C$，不存在不同的 $(m, r)$ 对产生相同的 $C$
• 隐藏性：给定 $C$，无法推导出 $m$（离散对数困难）

2. 范围证明的基本思路

最直接的方法是将 $v$ 表示为二进制向量 $\vec{v} = (v_0, v_1, ..., v_{n-1})$，其中 $v_i \in \{0, 1\}$，则：

$$v = \sum_{i=0}^{n-1} v_i \cdot 2^i$$

验证 $v \in [0, 2^n)$ 等价于验证每个 $v_i$ 都是 0 或 1，即：

$$v_i \cdot (v_i - 1) = 0, \quad \forall i \in \{0, ..., n-1\}$$

这是 $n$ 个二次约束，但直接证明效率极低。Bulletproofs 的创新在于将这些约束压缩为单个内积方程。

技术原理：从线性约束到内积论证

1. 内积论证（Inner Product Argument）

内积论证是 Bulletproofs 的核心组件，最早由 Bootle 等人于 2016 年提出。

问题定义：给定承诺 $A, B$，证明者声称存在向量 $\vec{a}, \vec{b} \in \mathbb{F}_p^n$ 使得：

$$\langle \vec{a}, \vec{b} \rangle = \sum_{i=0}^{n-1} a_i \cdot b_i = c$$

其中 $c$ 是公开标量，且 $A = \text{Com}(\vec{a}), B = \text{Com}(\vec{b})$。

递归压缩：

内积论证的关键思想是通过递归将维度减半：

• 证明者将向量分为两半：$\vec{a} = (\vec{a}_L, \vec{a}_R)$，$\vec{b} = (\vec{b}_L, \vec{b}_R)$
• 计算：

• 发送 $c_L$ 给验证者
• 验证者随机选取挑战 $x$，计算新承诺并递归

2. 范围证明的构造

步骤一：将范围约束转化为内积形式

设 $v$ 是待证明的值，其二进制表示为 $\vec{v} = (v_0, ..., v_{n-1})$，$\vec{1}$ 是全 1 向量，$\vec{2} = (2^0, 2^1, ..., 2^{n-1})$。

我们需要证明：

• $v = \langle \vec{v}, \vec{2} \rangle$（值正确分解）
• $v_i \in \{0, 1\}$（每位是二进制）

步骤二：引入辅助承诺

证明者生成以下承诺：

• $V_1 = \text{Pedersen}(v, r_1)$
• $V_2 = \text{Pedersen}(v^2, r_2)$（用于验证 $v = v^2$ 在二进制约束下成立）

通过多项式插值，将 $n$ 个二次约束 $v_i(v_i-1)=0$ 压缩为单个内积方程：

$$\langle \vec{l}, \vec{r} \rangle = 0$$

其中 $\vec{l}, \vec{r} \in \mathbb{F}_p^n$ 是由 $\vec{v}$ 派生的向量，包含所有约束信息。

步骤四：应用内积论证

对 $\langle \vec{l}, \vec{r} \rangle = 0$ 应用内积论证协议，得到大小为 $2\log_2 n$ 的压缩承诺。

3. Bulletproofs 的证明尺寸

传统范围证明方案的尺寸通常与 $n$ 线性相关，而 Bulletproofs 的优势在于：

• 证明大小约 4KB
• 验证时间约 30ms
• 无需任何可信设置 ceremony

数学推导：完整构造流程

1. 参数设置

• 椭圆曲线群 $\mathbb{G}$，生成元 $g, h$
• 素数阶 $p$，满足 DLP 困难
• 范围位数 $n$（如 64 位）

2. 承诺阶段

证明者选择随机 $v, r_v$，计算： $$V_1 = g^v \cdot h^{r_v}$$

以及二次承诺： $$V_2 = g^{v^2} \cdot h^{r_{v^2}}$$

3. 内积论证阶段

构造向量： $$\vec{a}_L = \vec{v} - \vec{2}^{-n} \cdot \langle \vec{v}, \vec{2} \rangle \cdot \vec{1}$$ $$\vec{a}_R = \vec{v} \circ (\vec{v} - \vec{1})$$

其中 $\circ$ 表示逐元素乘法（Hadamard product）。

关键性质：$\langle \vec{a}_L, \vec{a}_R \rangle = 0$ 当且仅当 $v \in [0, 2^n)$ 且 $v_i \in \{0,1\}$。

4. 优化：单轮内积

Bulletproofs 的另一创新是将原本需要两轮内积论证的步骤合并为一轮，通过将 $\vec{l}$ 和 $\vec{r}$ 合并为一个内积：

$$\langle \vec{l}, \vec{r} \rangle = 0$$

其中 $\vec{l}$ 包含所有线性约束，$\vec{r}$ 包含二次约束的展开。

5. 最终证明

最终证明包含：

• $V_1, V_2$：承诺
• $\vec{L}, \vec{R}$：$\log_2 n$ 对压缩承诺
• $s$：标量响应
• $t$：辅助标量

与 SNARK / STARK 的对比

• SNARK 证明最小但需要可信设置，不适合隐私货币等需要信任最小化的场景
• STARK 无需可信设置但证明较大，验证成本也较高
• Bulletproofs 在两者之间取得平衡：证明小、无需可信设置、实现相对简单

国密视角下的应用

1. 国密标准体系中的位置

目前国密标准中尚无专门针对 Bulletproofs 的标准，但以下标准为其应用提供了基础：

2. 潜在应用场景

场景一：政务数据共享

在跨部门数据共享中，某部门需要证明某个数值属性（如收入、年龄）落在特定范围内，但不希望暴露具体值。Bulletproofs 可提供这种隐私保护。

场景二：金融风控

银行间清算需要验证交易金额的有效性，但不希望暴露客户的具体交易细节。基于 Bulletproofs 的范围证明可以在保护隐私的同时满足合规要求。

场景三：电子投票

投票系统中需要证明选票编码值在有效范围内（如 0 或 1），但不泄露投票选择。

3. 与 SM2 的集成

Bulletproofs 可以在 SM2 椭圆曲线上实现：

• 使用 SM2 曲线参数（$p, a, b, G, n$）替代 BLS12-381 等西方曲线
• SM3 哈希用于 Fiat-Shamir 变换
• SM2 签名用于证明者的身份认证

4. 工程实现建议

推荐实现路径：
1. 使用现有开源库（如 Rust 的 bulletproofs crate）
2. 底群替换为 SM2 曲线参数
3. 哈希函数替换为 SM3
4. 遵循 GM/T 0054 的安全要求设计系统架构

已知局限与挑战

1. 生成成本较高

虽然验证速度快，但 Bulletproofs 的证明生成需要 $O(n)$ 时间，对于大规模电路仍不够高效。

2. 与 SNARK 的混合方案

学术界正在研究将 Bulletproofs 与 SNARK 结合的方案（如 Halo 2），发挥两者优势：

• 使用 SNARK 处理通用计算
• 使用 Bulletproofs 处理范围证明

3. 国密适配的挑战

将 Bulletproofs 适配到国密体系时需要注意：

• SM2 曲线的安全性参数选择
• SM3 的抗碰撞性对方案安全性的影响
• 密钥生成和管理的合规要求

总结

Bulletproofs 是隐私密码学领域的重要突破，其核心价值在于：

• 无需可信设置：消除了 SNARK 的潜在信任假设
• 证明尺寸小：$O(\log n)$ 的规模使其适合实际部署
• 后量子安全：基于离散对数问题，对量子计算免疫
• 简洁性：相比 STARK，实现复杂度更低

相关实践