区块链原理 / 系统课时

为整数添加范围检查约束

为整数添加范围检查约束

在零知识证明电路中,一个字段元素并不天然代表普通意义上的非负整数。如果只用加减乘法表达金额、年龄或库存判断,可能因为有限域中的模回绕而接受不符合业务规则的值。本课用位分解、布尔约束和重组等式,为整数建立可验证的范围边界,并实现一个可运行的检查示例。

学习目标

  • 理解有限域整数与普通整数的区别,识别模回绕风险。
  • 使用位分解、布尔约束和重组约束证明整数属于指定范围。
  • 用 Circom 实现并验证范围检查,处理非零下界与区间端点。

为什么字段元素不能直接当作整数

零知识证明中的算术电路通常在素数有限域 Fp\mathbb{F}_p 上运行。整数运算实际按模 pp 计算,因此 pp 与 00 表示同一个域元素,p+1p+1 与 11 也表示同一个域元素。

以一个模数为 1717 的教学示例说明:业务要求余额不少于支出。若余额为 33、支出为 55,直接计算差值,会得到:

3−5≡15(mod17)3-5\equiv15\pmod{17}

如果开发者把这个差值当作普通非负整数,错误地认为余额足够,就可能放过不合法交易。实际上,有限域本身没有与普通整数一致的大小顺序,不能仅凭字段元素表示非负差值就证明余额不少于支出。

业务计算 普通整数结果 模 17 的域元素
3 - 5 -2 15
8 - 5 3 3
16 + 3 19 2

正确做法是先明确操作数的整数解释和允许范围,再证明差值或比较结果满足相应的有界整数约束。例如,证明 0≤b≤a≤150\leq b\leq a\leq15 时,可以分别约束 aa、bb 和 a−ba-b 为 4 位无符号整数。在模数 17 的示例中,a=3a=3、b=5b=5 会产生域元素 15;虽然 15 本身属于 4 位范围,但还需要利用 aa、bb 的范围以及防止回绕的适当模数界限,不能机械照搬到任意参数。

位分解、布尔约束与重组

要证明字段元素 xx 属于 [0,2n−1][0,2^n-1],可以把它分解成 nn 个二进制位 b0,b1,…,bn−1b_0,b_1,\ldots,b_{n-1},并添加两类约束。

首先,每个位都必须是布尔值:

bi(bi−1)=0b_i(b_i-1)=0

在域中,这个等式迫使 bib_i 只能是 00 或 11。其次,必须证明这些位确实重组成原始输入:

x=∑i=0n−1bi2ix=\sum_{i=0}^{n-1}b_i2^i

两个条件缺一不可。只检查位是 0 或 1,却不约束它们与输入 xx 的关系,证明者仍能为任意 xx 提供一组无关的合法位。

位分解与整数重组约束示意

例如 x=13x=13,4 位表示为 11011101,对应从低到高的位值 1,0,1,11,0,1,1,重组结果为 1+0+4+8=131+0+4+8=13。因为 4 个布尔位的加权和最大为 15,所以在 24<p2^4<p 时,重组等式能够唯一地限定输入的常规整数值在 0 到 15 之间。

这个条件非常关键:若 2n>p2^n>p,不同的位组合可能在域中重组成同一个元素。即使每个位都是布尔值,也不能直接宣称重组后的整数表示唯一。

使用 Circom 实现 8 位范围检查

下面使用 Circom 2.x 编译器与 circomlib 的 Num2Bits 模板。Num2Bits(n) 会将输入约束为 nn 个布尔位,并添加加权重组等式;因此它不只是计算二进制表示,而是在电路里真正建立约束。

先创建一个已安装 circomlib 的 Circom 2.x 项目。以下示例假定编译器命令 circom 已可用,且项目根目录存在 node_modules/circomlib。将代码保存为 range.circom:

text
// 片段说明:本节实际采用完整 Circom 电路,文件名为 range.circom。
javascript
pragma circom 2.1.0;

include "node_modules/circomlib/circuits/bitify.circom";

template Range8() {
    signal input value;
    signal output accepted;

    // Num2Bits 为输入添加 8 个布尔位约束及重组约束。
    component bits = Num2Bits(8);
    bits.in <== value;

    // 常量输出便于演示;能否通过由范围约束决定。
    accepted <== 1;
}

component main = Range8();

安装编译依赖后,运行以下命令编译电路并生成约束信息:

bash
circom range.circom --r1cs --sym --wasm -o .

预期结果:编译成功后,当前目录生成 range.r1cs、range.sym 和 range_js 等输出。具体编译日志因 Circom 版本而异。使用下列输入生成见证,能够进一步检验约束。

将合法输入保存为 valid.json:

json
{"value":255}

将非法输入保存为 invalid.json:

json
{"value":256}

执行见证生成命令:

bash
node range_js/generate_witness.js range_js/range.wasm valid.json valid.wtns
node range_js/generate_witness.js range_js/range.wasm invalid.json invalid.wtns

预期结果:第一条命令成功并生成 valid.wtns,第二条命令因无法满足 8 位分解约束而失败,通常会报告断言或约束检查错误;具体错误文本取决于运行版本。

需要区分:见证生成失败是本地验证现象,正式安全性仍取决于生成的证明能否通过验证器。约束必须存在于 R1CS 中,不能只依赖见证生成器中的 JavaScript 检查。

从零开始推广到任意业务区间

实际业务经常需要区间 [L,U][L,U],而非固定的 [0,2n−1][0,2^n-1]。若上下界是编译期常量,可以先计算偏移量 y=x−Ly=x-L,再约束 yy 的范围。

例如订单数量必须在 10 到 25 之间,令 y=x−10y=x-10,并要求 yy 属于 4 位无符号范围。因为 25−10=1525-10=15,有:

0≤y≤150\leq y\leq15

对应的 Circom 完整模板如下,适用于前面相同的项目环境:

javascript
pragma circom 2.1.0;

include "node_modules/circomlib/circuits/bitify.circom";

template QuantityRange() {
    signal input quantity;
    signal shifted;

    // 固定下界为 10,转换为 0 到 15 的范围。
    shifted <== quantity - 10;

    // 约束偏移结果确实由 4 个布尔位构成。
    component bits = Num2Bits(4);
    bits.in <== shifted;
}

component main = QuantityRange();

该模板在常规整数含义下允许 10 到 25,但这里还必须排除域回绕带来的伪造值。对于 BN254 标量域等大模数环境,单独对不受约束的 quantity 做减法后再检查 4 位,可能接受字段元素 p+10p+10 的模等价表示;字段元素本身没有唯一的任意整数输入解释。因此,对来自其他计算环节的 quantity,还应验证上游整数语义,或对原值额外添加足够严格的范围约束,确保输入遵守预定业务编码。

用边界测试检查结果:

quantity shifted 预期
9 -1(域内回绕) 拒绝
10 0 接受
25 15 接受
26 16 拒绝

若需要检查 10 到 20,直接使用 4 位分解会错误地接受 21 到 25。此时除了对 x−10x-10 限定为 4 位,还要证明 20−x20-x 为非负的有界整数,或者使用经过审计的安全比较模板来完成上界约束。

选择位宽并检查边界安全

位宽应由业务最大值推导,而不是习惯性使用 8、32 或 64。例如允许最大值为 1000,则 10 位覆盖 0 到 1023,足以容纳该值;但仍需额外检查不超过 1000,否则 1001 到 1023 也会通过。

业务值范围 最小覆盖位宽 是否需要额外上界检查
0~255 8 位 否
0~1000 10 位 是,检查 ≤1000
10~25 偏移后 4 位 否,需保证输入整数语义
1~100 偏移后 7 位 是,检查偏移 ≤99

在大整数电路中,需要同时确认三个问题:位分解最大值是否小于域模数、加减乘的中间值是否会产生意外回绕,以及比较模板对输入位宽有哪些前置要求。不能只看输入值在界面上显示为正数,就认为电路已经证明它非负。

最终验收时,至少测试最小值、最大值、上下界外各一个值,并检查生成的约束和证明验证行为。若某一业务值可能由多个域元素运算得到,应在进入比较前建立统一的整数表示和范围约束,避免用有限域等式代替整数大小关系。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

为整数添加范围检查约束

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通