区块链原理 / 系统课时

将等式转换为多项式约束

将等式转换为多项式约束

零知识证明不能直接依赖程序中的赋值语句和条件判断来验证计算。我们需要把计算过程改写为一组多项式等式,使证明系统能够检查变量之间的关系。本篇使用一个具体算例,从普通算术表达式出发,完成变量拆分、约束构造和结果验证。

学习目标

  • 将加法、乘法和常量运算转换为多项式等式。
  • 使用中间变量拆分复杂表达式,理解约束与见证的关系。
  • 判断一组变量赋值是否满足约束,并识别有限域中的运算边界。

从普通等式开始

考虑一个需要证明的计算关系:已知公开结果 y=35y=35,证明者知道一个秘密数 xx,满足:

y=x2+3x+5y=x^2+3x+5

验证者希望确认结果确实由某个秘密 xx 计算得到,但不希望直接取得 xx。这里先研究如何表达计算关系,不讨论如何隐藏见证或生成密码学证明。

将所有项移到等号左边,可以得到多项式约束:

x2+3x+5−y=0x^2+3x+5-y=0

代入 x=4x=4、y=33y=33,等式成立;若要求 y=35y=35,这组赋值就不满足约束。在整数范围内,x=5x=5 时结果为 4545,也不是 3535。因此,构造约束与找到满足约束的见证是两件不同的事。

在证明系统中,通常固定一个有限域 Fp\mathbb{F}_p,所有加减乘法都在模 pp 意义下计算。为了方便观察,下面先使用普通整数解释,再用一个小素数域验证。

把计算拆成基础关系

许多算术电路和 R1CS 约束系统以乘法关系为基本单位,常见形式为:

A⋅B=CA\cdot B=C

其中 AA、BB、CC 可以是变量与常量的线性组合。加法不需要独立的乘法门,可以写成某个因子为 11 的等式。

例如,计算 y=x2+3x+5y=x^2+3x+5,可以引入两个中间变量:

t=x⋅xt=x\cdot x
u=t+3xu=t+3x
y=u+5y=u+5

对应的三个基础约束是:

x⋅x=tx\cdot x=t
(t+3x)⋅1=u(t+3x)\cdot1=u
(u+5)⋅1=y(u+5)\cdot1=y

第一条负责乘法,后两条负责线性关系。这里的 tt 和 uu 并非随意增加的未知数,它们必须与 xx、yy 一起满足全部约束。

算术表达式拆分为乘法与加法约束的电路结构

这种拆分方式使每条约束只描述一次局部计算。实际系统可以将这些局部关系组合为更大的约束集合,而不必让单个约束承载整个表达式。

用具体数值检查见证

为了得到能够满足约束的例子,把公开结果改为 y=33y=33,选择秘密输入 x=4x=4。

逐项计算可得:

变量 计算方式 结果
xx 秘密输入 44
tt 4×44\times4 1616
uu 16+3×416+3\times4 2828
yy 28+528+5 3333

将这四个值组成赋值集合 w=(x,t,u,y)=(4,16,28,33)w=(x,t,u,y)=(4,16,28,33),它就是这组约束的一个满足赋值。在相关证明系统中,见证通常指证明者提供的满足约束的变量赋值;具体哪些变量公开、哪些变量私有,由电路接口和证明协议决定。

下面使用 Python 3 标准库验证约束,不依赖第三方包。示例选择素数 p=97p=97,用于演示有限域运算,并不具备密码学安全性。

python
P = 97


def verify(x, t, u, y):
    # 每个约束都在有限域 F_97 内检查
    constraints = [
        (x * x - t) % P,
        (t + 3 * x - u) % P,
        (u + 5 - y) % P,
    ]
    return all(value == 0 for value in constraints)


if __name__ == "__main__":
    print("正确见证:", verify(4, 16, 28, 33))
    print("错误中间值:", verify(4, 15, 28, 33))
    print("错误公开结果:", verify(4, 16, 28, 35))

预期输出:

text
正确见证: True
错误中间值: False
错误公开结果: False

第一组所有约束的余数均为零。第二组中 4×4−15=14\times4-15=1,乘法约束失败;第三组中 28+5−35=−228+5-35=-2,最终输出约束失败。

注意,这段代码只是普通的约束检查器,并不是零知识证明协议。它会直接接收秘密变量,不能实现零知识性质;真正的证明系统需要额外的证明生成与验证机制。

从多项式约束连接到 R1CS

R1CS 是 Rank-1 Constraint System,即秩一约束系统。它把每条约束统一写成两个线性组合相乘等于第三个线性组合:

(a⋅z)(b⋅z)=c⋅z(\mathbf{a}\cdot\mathbf{z})(\mathbf{b}\cdot\mathbf{z})=\mathbf{c}\cdot\mathbf{z}

其中 z\mathbf{z} 是包含常量 11 和所有变量的向量。对本例选定顺序:

z=(1,x,t,u,y)\mathbf{z}=(1,x,t,u,y)

每个线性组合都由系数向量指定,三条约束可表示为:

约束 a\mathbf{a} b\mathbf{b} c\mathbf{c}
x⋅x=tx\cdot x=t (0,1,0,0,0)(0,1,0,0,0) (0,1,0,0,0)(0,1,0,0,0) (0,0,1,0,0)(0,0,1,0,0)
(t+3x)⋅1=u(t+3x)\cdot1=u (0,3,1,0,0)(0,3,1,0,0) (1,0,0,0,0)(1,0,0,0,0) (0,0,0,1,0)(0,0,0,1,0)
(u+5)⋅1=y(u+5)\cdot1=y (5,0,0,1,0)(5,0,0,1,0) (1,0,0,0,0)(1,0,0,0,0) (0,0,0,0,1)(0,0,0,0,1)

例如,第二行左侧第一个线性组合得到 3x+t3x+t,第二个得到 11,右侧得到 uu,因此它恰好表达 t+3x=ut+3x=u。

这里有三个容易混淆的地方。

  • 多项式约束是数学等式,算术电路是组织计算依赖关系的一种方式,R1CS 则是一种具体的约束表示格式。
  • 一条复杂多项式等式不一定对应一条 R1CS 约束;为了满足线性组合相乘的形式,可能需要引入多个中间变量。
  • 约束满足只说明赋值在指定有限域内合法,不会自动保证秘密性、知识可靠性或零知识性。

有限域带来的边界

在普通整数中,x2+3x+5=33x^2+3x+5=33 的解之一是 x=4x=4。但当所有计算都在 F97\mathbb{F}_{97} 中进行时,验证的是:

x2+3x+5−y≡0(mod97)x^2+3x+5-y\equiv0\pmod{97}

这意味着数值相差 9797 的整数代表同一个域元素。例如,整数 130130 与域元素 3333 在 F97\mathbb{F}_{97} 中等价,因为 130 mod 97=33130\bmod97=33。

如果业务要求的是普通整数的大小比较、非负数或固定范围,单纯的多项式等式不够。例如要限定 0≤x<160\le x<16,需要额外的范围约束,而不能只假设域元素会按整数规则解释。

实际建模时,先列出全部基础运算,再为需要的中间结果命名,最后逐条检查每个乘法关系以及公开输入与输出是否受到约束。任何没有被约束正确连接的中间变量,都可能使证明者构造出不符合原始计算意图的赋值。

掌握这一过程后,便可以把更长的算术表达式逐步转换为 R1CS 所需的线性组合与乘法约束。

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

目录与阅读设置

阅读设置

17

记录一个想法

将等式转换为多项式约束

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

登录哪都通