Circom 实战 2 — Range Proof / Bit Decomposition

日期: 2026-12-12 方向: ZK工程 / 电路开发 阶段: Phase 4 - ZK电路开发实战 (Day 223-243) 标签: #ZK #Circom #range-proof #bit-decomposition #Bulletproofs

---

今日目标

---

背景与定位

为什么 range proof 是 ZK 的难点？/ Why range proof is the hard part of ZK?

• 在普通 EVM 里，require(x < 2^32) 是一行代码。但在 R1CS 里，field 没有「比较」概念。
• bn128 的 scalar field $p \approx 2^{254}$。在域里，$2^{32}$ 和 $2^{200}$ 都是合法元素，没有「大小」语义。
• 唯一的方法：证明 x 可以被 $N$ 个 bit 二进制表示，即 $x = \sum_{i=0}^{N-1} b_i \cdot 2^i$ 且每个 $b_i \in {0,1}$。

应用场景：

• Bulletproofs / ZCash：证明转账金额 ∈ [0, 2^64]，避免 overflow 攻击。
• 年龄证明：证明 18 ≤ age ≤ 120。
• DEX 隐私：证明 0 ≤ slippage ≤ maxSlippage。
• zkEVM：所有 256-bit operations 都需要 range check 子电路。

约束成本：

• N-bit range proof = N + 1 约束（N 个 boolean + 1 个 sum）
• 32-bit: 33 约束（极便宜）
• 256-bit: 257 约束（zkEVM 中 dominant cost）

---

完整代码实现

range.circom

pragma circom 2.1.6;

/*
 * Num2Bits(n): decompose `in` into n bits.
 *   constraints:
 *     - each out[i] in {0,1}
 *     - sum_{i} out[i] * 2^i === in
 */
template Num2Bits(n) {
    signal input in;
    signal output out[n];

    var lc = 0;
    var pow2 = 1;

    for (var i = 0; i < n; i++) {
        out[i] <-- (in >> i) & 1;          // unsafe assignment (witness only)
        out[i] * (out[i] - 1) === 0;       // boolean constraint (CRITICAL)
        lc += out[i] * pow2;
        pow2 = pow2 + pow2;
    }

    lc === in;                             // sum constraint
}

/*
 * RangeProofN: prove 0 <= in < 2^N
 */
template RangeProofN(N) {
    signal input in;

    component n2b = Num2Bits(N);
    n2b.in <== in;
    // No need to expose bits; just constraining decomposition is enough.
}

/*
 * RangeProofMinMax(N): prove min <= in <= max
 *   trick: prove in - min ∈ [0, 2^N]  AND  max - in ∈ [0, 2^N]
 *   This works as long as max - min < 2^N (no field wrap).
 */
template RangeProofMinMax(N) {
    signal input in;
    signal input min;
    signal input max;

    // in - min ≥ 0
    component low = RangeProofN(N);
    low.in <== in - min;

    // max - in ≥ 0
    component high = RangeProofN(N);
    high.in <== max - in;
}

// Test: prove 0 <= x < 2^32
component main {public []} = RangeProofN(32);

test input

// input_valid.json
{ "in": "4294967295" }    // 2^32 - 1 ✓

// input_invalid.json
{ "in": "4294967296" }    // 2^32 ✗ (should fail witness gen)

调试运行

# 1. compile
circom range.circom --r1cs --wasm --sym -o build/

# 2. info
snarkjs r1cs info build/range.r1cs
# # of Constraints: 33   ← N=32: 32 boolean + 1 sum

# 3. valid case — succeed
node build/range_js/generate_witness.js \
     build/range_js/range.wasm input_valid.json build/witness.wtns
# OK

# 4. invalid case — should fail
node build/range_js/generate_witness.js \
     build/range_js/range.wasm input_invalid.json build/witness_bad.wtns
# Error: Assert Failed. Error in template Num2Bits_0 line: 14

---

关键 gotcha：负数与 field wrap

gotcha 1: 负数怎么处理？

在 bn128 域里，-1 等价于 p - 1，是个非常大的数。如果你写：

RangeProofMinMax(32) — prove min=10, max=100, in=5

in - min = 5 - 10 = -5 = p - 5，这是个 254-bit 的数，不可能用 32 bit 表示。所以 Num2Bits(32) 会失败。这正是我们想要的！下界检查通过失败保护。

gotcha 2: max - min < 2^N 的约束

RangeProofMinMax(N) 隐含要求 max - min < 2^N。否则即使 in > max，max - in 仍可能在 [0, 2^N] 内（field wrap），让恶意 prover 通过。

修复方法：要么 (a) 编译期保证 max - min < 2^N；要么 (b) 加上额外的 range check on max - min。

gotcha 3: Num2Bits 的 N 上限

如果 N > 254，bit 表示无法唯一（field 不够大），可能多个 bits 组合 hash 到同一 field 元素。Circom 标准 lib 在 N ≥ 254 时会显式失败。

---

真实漏洞案例 / Real-world Bug

Underconstrained Bit Decomposition：

2022 年 Aleo 在 ZK 编译器测试中发现：早期版本 Num2Bits 忘记加 out[i] * (out[i] - 1) === 0，导致 prover 可以用非 0/1 bit（如 out[0] = 2, out[1] = -1）满足 sum 但绕过 range。

• 修复 PR：iden3/circomlib commit 91dc8b5
• 影响范围：所有依赖 circomlib < v0.5.0 的项目

类似漏洞在 Aztec ECNoir audit (2023) 和 0xPARC Reclaim Protocol audit 中也出现过。

---

性能基准 / Benchmarks

注意：Groth16 verify gas 与 N 无关（只受 public input 数影响）。Bulletproofs 则相反（gas 随 N 线性增长）。

---

进阶：Range Proof 的多种方案

Halo2 用 lookup argument，对 32-bit range 只要 1 行（不是 32 行）。这是为什么 zkEVM 越来越往 PLONKish 靠拢。

---

关键速查

// 所有 ZK 项目的 import 起点
include "circomlib/circuits/bitify.circom";   // Num2Bits, Bits2Num
include "circomlib/circuits/comparators.circom"; // LessThan, GreaterEqThan
include "circomlib/circuits/poseidon.circom";

// LessThan 内部用 Num2Bits 实现
component lt = LessThan(32);  // 第二参数是 bit width
lt.in[0] <== a;
lt.in[1] <== b;
// lt.out == 1 if a < b else 0

---

生产经验

• zkSync Era 的 range check 优化：用 lookup table（PLONKish）把 16-bit range 压成 1 个 lookup 而非 16 个 boolean。整个 zkEVM 的 range check 占 ~30% 总约束。
• Aztec Noir 提供 as u32 自动插入 range check，开发者无感知（但要意识到约束成本）。
• 不要写 signal x; x <-- in / 2：除法在域里不是「整除」，可能让 prover 任意填值。要用 Num2Bits + 选 bit。

---

面试题

1. Q: 在 ZK 电路中如何证明 0 ≤ x < 2^32？为什么不能直接用 <？ A: R1CS 的有限域没有大小关系。把 x 分解成 32 个 bit $b_0..b_{31}$，约束每个 $b_i \in {0,1}$ 且 $\sum b_i 2^i = x$。

2. Q: Underconstrained 漏洞是什么？举一个 range proof 的例子。 A: 电路只约束部分关系，prover 可以填非预期值。例：忘加 b_i (b_i - 1) === 0，prover 可以填 b_0 = 2, b_1 = -1，sum 仍可能等于 x，但绕过 range。

3. Q: 为什么 Halo2 / PLONKish 用 lookup argument 比 bit decomposition 更高效？ A: bit decomp 是 N 个约束；lookup 把 0..2^N-1 表查找压到 1 行 + log 级证明开销。当 N 大时 lookup 渐近更优。但需要 PLONKish IOP 支持，Groth16 不支持原生 lookup。

---

明日预告

Day 226 — Circom + snarkjs 端到端流程。把 Day 223-225 的电路串起来，跑一个完整的 setup → prove → verify → on-chain verify 流水线，写 Solidity verifier 部署到本地 hardhat。