区块链原理 / 系统课时
用模运算解释有限域中的数值
用模运算解释有限域中的数值
零知识证明中的算术电路通常不直接使用普通整数,而是在有限域中完成运算。一个看似简单的加法,可能因为模回绕得到意想不到的结果。本篇使用素数 17 构造有限域,实际计算加减乘、逆元和除法,并说明为什么业务范围约束不能只依赖域内等式。
学习目标
- 理解有限域元素与普通整数的区别,能够计算模 17 的加减乘。
- 掌握乘法逆元与模除法,识别没有逆元的情况。
- 解释模回绕对零知识电路中余额、年龄和范围判断的影响。
有限域中的数为什么会回绕
选择素数 ,得到素数域 。它恰好包含 17 个元素,通常选用整数 0 到 16 作为标准代表元。
任意整数 都可以按模 17 映射为一个域元素:
例如,20 和 3 在普通整数中不相等,但它们表示同一个模 17 的域元素,因为 。同样, 对应域元素 16。
| 普通整数 | 模 17 的标准代表元 |
|---|---|
| 3 | 3 |
| 17 | 0 |
| 20 | 3 |
| 34 | 0 |
| -1 | 16 |
| -18 | 16 |
这里的回绕并不是整数溢出异常,而是有限域运算本身的规则。域元素始终存在,但通常不存在与普通整数相同的大小顺序。例如,16 加 1 得到 0,并不能据此认为普通整数 16 加 1 等于 0。
加减乘如何计算
对于 ,先按整数计算,再取模 17 的标准代表元。下面把三种基础运算放在一起:
| 运算 | 整数计算 | 域内结果 |
|---|---|---|
| 20 | 3 | |
| -5 | 12 | |
| 42 | 8 | |
| 17 | 0 |
减法出现负数时,可以加上 17,直到结果位于 0 到 16。例如,,对应域元素 12。也可以把减法理解为加上加法逆元:8 的加法逆元是 9,因为 。
下面使用 Python 3 验证。Python 的 `%` 在模数为正整数时会返回非负余数,适合表示这些标准代表元。
P = 17
def field(value: int) -> int:
# 归一化为 0 到 P-1 的标准代表元
return value % P
print('15 + 5 =', field(15 + 5))
print('3 - 8 =', field(3 - 8))
print('7 * 6 =', field(7 * 6))
print('16 + 1 =', field(16 + 1))预期输出:
15 + 5 = 3
3 - 8 = 12
7 * 6 = 8
16 + 1 = 0注意,域内的等号表达的是模意义下的相等。比如 在 中成立,却不是普通整数等式。代码中的 `field` 只演示归一化,并不是生产级零知识证明库。
乘法逆元与模除法
普通整数除法中, 通常表示分数或小数;有限域里需要先找到 5 的乘法逆元。如果元素 的逆元为 ,则满足:
由于 17 是素数,域内每个非零元素都有且仅有一个乘法逆元。比如 5 的逆元为 7,因为 ,而 。
所以,域内除法定义为乘以逆元:
再看 :2 的逆元是 9,因为 。因此,域内的 ,它不是普通实数中的 0.5。
Python 3.8 及以上版本支持使用 `pow(a, -1, p)` 计算模逆元:
P = 17
# 分母必须在有限域中非零
inverse_5 = pow(5, -1, P)
quotient = (10 * inverse_5) % P
inverse_2 = pow(2, -1, P)
print('inv(5) =', inverse_5)
print('10 / 5 =', quotient)
print('inv(2) =', inverse_2)
print('1 / 2 =', inverse_2)预期输出:
inv(5) = 7
10 / 5 = 2
inv(2) = 9
1 / 2 = 9零没有乘法逆元。因为无论乘以哪个域元素,结果都为零,不可能等于一。执行 `pow(0, -1, 17)` 会抛出 `ValueError`,因此电路中的除法或逆元约束必须处理分母为零的情况。
模回绕怎样影响业务范围判断
假设一个零知识电路要验证账户扣款:原余额 15、扣款 5、剩余余额 10。在普通整数中,必须满足原余额不少于扣款额,而且剩余余额非负。
如果电路只验证域内等式:
那么攻击者可以提交 `balance=3`、`amount=5`、`remaining=15`。因为 ,模 17 后恰好为 3,等式仍然成立。这不能证明普通整数意义下余额充足。
| 检查项 | 正常扣款 | 有问题的输入 |
|---|---|---|
| 原余额 | 15 | 3 |
| 扣款金额 | 5 | 5 |
| 声称的剩余余额 | 10 | 15 |
| 域内等式 | 成立 | 成立 |
| 普通整数扣款规则 | 满足 | 不满足 |
问题的根源是域等式不能单独表达无符号整数的范围和大小关系。实际设计中需要配合范围约束,使所有值都符合业务语义。
以教学用的模 17 电路为例,如果要求余额和扣款金额都在 0 到 7 之间,且剩余余额也在 0 到 7 之间,那么 `balance = amount + remaining` 的右侧最多为 14,不会跨越模数 17。再通过该等式和范围限制,就能够排除上述回绕伪造。
在实际零知识电路中,常采用位分解、范围检查门或查找表约束。例如要证明 ,可以把 表示为 8 个布尔位的加权和,并约束每一位只能为 0 或 1,同时保证对应的整数表示不会发生模回绕。对于比较或减法,还必须结合输入边界证明没有意外回绕。
怎样检查电路里的整数语义
把有限域数值用于金额、计数器、年龄或数组下标时,可以按以下顺序检查:
- 确定证明系统实际使用的域模数 ,不要把链上整数位宽与证明电路域大小混为一谈。
- 列出每个输入的合法整数范围,例如 `amount` 为 0 到 255,`balance` 为 0 到 65535。
- 计算表达式在普通整数中的最大值和最小值,检查是否可能达到或跨越 。
- 为需要大小关系的数值增加有效的范围证明,并对加减法中的进位、借位和中间结果施加必要约束。
- 构造越界用例进行测试,确认非法见证不能满足约束。
例如在 中,下面的测试可以直接证明域内等式不足以验证业务扣款规则:
P = 17
balance, amount, remaining = 3, 5, 15
# 模等式成立,不代表普通整数余额足够
field_valid = (balance - amount - remaining) % P == 0
business_valid = balance >= amount and remaining == balance - amount
print('field_valid =', field_valid)
print('business_valid =', business_valid)预期输出:
field_valid = True
business_valid = False在真正的零知识证明中,验证者只会检查电路编码的约束是否满足,不能自动理解开发者原本想表达的整数业务规则。有限域提供加减乘除的代数基础;整数范围、大小比较和防止回绕,则需要由电路设计者明确编码为额外约束。