区块链原理 / 系统课时

用模运算解释有限域中的数值

用模运算解释有限域中的数值

零知识证明中的算术电路通常不直接使用普通整数,而是在有限域中完成运算。一个看似简单的加法,可能因为模回绕得到意想不到的结果。本篇使用素数 17 构造有限域,实际计算加减乘、逆元和除法,并说明为什么业务范围约束不能只依赖域内等式。

学习目标

  • 理解有限域元素与普通整数的区别,能够计算模 17 的加减乘。
  • 掌握乘法逆元与模除法,识别没有逆元的情况。
  • 解释模回绕对零知识电路中余额、年龄和范围判断的影响。

有限域中的数为什么会回绕

选择素数 p=17p=17,得到素数域 mathbbF_17\\mathbb{F}\_{17}。它恰好包含 17 个元素,通常选用整数 0 到 16 作为标准代表元。

任意整数 aa 都可以按模 17 映射为一个域元素:

abmod17=r,quad0ler<17a\\bmod 17=r,\\quad 0\\le r<17

例如,20 和 3 在普通整数中不相等,但它们表示同一个模 17 的域元素,因为 20bmod17=320\\bmod17=3。同样,−1-1 对应域元素 16。

普通整数 模 17 的标准代表元
3 3
17 0
20 3
34 0
-1 16
-18 16

这里的回绕并不是整数溢出异常,而是有限域运算本身的规则。域元素始终存在,但通常不存在与普通整数相同的大小顺序。例如,16 加 1 得到 0,并不能据此认为普通整数 16 加 1 等于 0。

加减乘如何计算

对于 a,binmathbbF_17a,b\\in\\mathbb{F}\_{17},先按整数计算,再取模 17 的标准代表元。下面把三种基础运算放在一起:

运算 整数计算 域内结果
15+515+5 20 3
3−83-8 -5 12
7times67\\times6 42 8
16+116+1 17 0

减法出现负数时,可以加上 17,直到结果位于 0 到 16。例如,3−8=−53-8=-5,对应域元素 12。也可以把减法理解为加上加法逆元:8 的加法逆元是 9,因为 8+9equiv0pmod178+9\\equiv0\\pmod{17}。

下面使用 Python 3 验证。Python 的 `%` 在模数为正整数时会返回非负余数,适合表示这些标准代表元。

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))

预期输出:

text
15 + 5 = 3
3 - 8 = 12
7 * 6 = 8
16 + 1 = 0

注意,域内的等号表达的是模意义下的相等。比如 15+5=315+5=3 在 mathbbF_17\\mathbb{F}\_{17} 中成立,却不是普通整数等式。代码中的 `field` 只演示归一化,并不是生产级零知识证明库。

乘法逆元与模除法

普通整数除法中,1/51/5 通常表示分数或小数;有限域里需要先找到 5 的乘法逆元。如果元素 aa 的逆元为 a−1a^{-1},则满足:

atimesa−1equiv1pmod17a\\times a^{-1}\\equiv1\\pmod{17}

由于 17 是素数,域内每个非零元素都有且仅有一个乘法逆元。比如 5 的逆元为 7,因为 5times7=355\\times7=35,而 35bmod17=135\\bmod17=1。

所以,域内除法定义为乘以逆元:

10/5=10times7bmod17=210/5=10\\times7\\bmod17=2

再看 1/21/2:2 的逆元是 9,因为 2times9bmod17=12\\times9\\bmod17=1。因此,域内的 1/2=91/2=9,它不是普通实数中的 0.5。

Python 3.8 及以上版本支持使用 `pow(a, -1, p)` 计算模逆元:

python
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)

预期输出:

text
inv(5) = 7
10 / 5 = 2
inv(2) = 9
1 / 2 = 9

零没有乘法逆元。因为无论乘以哪个域元素,结果都为零,不可能等于一。执行 `pow(0, -1, 17)` 会抛出 `ValueError`,因此电路中的除法或逆元约束必须处理分母为零的情况。

模回绕怎样影响业务范围判断

假设一个零知识电路要验证账户扣款:原余额 15、扣款 5、剩余余额 10。在普通整数中,必须满足原余额不少于扣款额,而且剩余余额非负。

如果电路只验证域内等式:

balance=amount+remainingpmod17balance=amount+remaining\\pmod{17}

那么攻击者可以提交 `balance=3`、`amount=5`、`remaining=15`。因为 5+15=205+15=20,模 17 后恰好为 3,等式仍然成立。这不能证明普通整数意义下余额充足。

检查项 正常扣款 有问题的输入
原余额 15 3
扣款金额 5 5
声称的剩余余额 10 15
域内等式 成立 成立
普通整数扣款规则 满足 不满足

问题的根源是域等式不能单独表达无符号整数的范围和大小关系。实际设计中需要配合范围约束,使所有值都符合业务语义。

以教学用的模 17 电路为例,如果要求余额和扣款金额都在 0 到 7 之间,且剩余余额也在 0 到 7 之间,那么 `balance = amount + remaining` 的右侧最多为 14,不会跨越模数 17。再通过该等式和范围限制,就能够排除上述回绕伪造。

在实际零知识电路中,常采用位分解、范围检查门或查找表约束。例如要证明 0lex<2560\\le x<256,可以把 xx 表示为 8 个布尔位的加权和,并约束每一位只能为 0 或 1,同时保证对应的整数表示不会发生模回绕。对于比较或减法,还必须结合输入边界证明没有意外回绕。

怎样检查电路里的整数语义

把有限域数值用于金额、计数器、年龄或数组下标时,可以按以下顺序检查:

  1. 确定证明系统实际使用的域模数 pp,不要把链上整数位宽与证明电路域大小混为一谈。
  2. 列出每个输入的合法整数范围,例如 `amount` 为 0 到 255,`balance` 为 0 到 65535。
  3. 计算表达式在普通整数中的最大值和最小值,检查是否可能达到或跨越 pp。
  4. 为需要大小关系的数值增加有效的范围证明,并对加减法中的进位、借位和中间结果施加必要约束。
  5. 构造越界用例进行测试,确认非法见证不能满足约束。

例如在 mathbbF_17\\mathbb{F}\_{17} 中,下面的测试可以直接证明域内等式不足以验证业务扣款规则:

python
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)

预期输出:

text
field_valid = True
business_valid = False

在真正的零知识证明中,验证者只会检查电路编码的约束是否满足,不能自动理解开发者原本想表达的整数业务规则。有限域提供加减乘除的代数基础;整数范围、大小比较和防止回绕,则需要由电路设计者明确编码为额外约束。

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

目录与阅读设置

阅读设置

17

记录一个想法

用模运算解释有限域中的数值

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

登录哪都通