区块链原理 / 系统课时

把电路等式转换为 R1CS 约束

把电路等式转换为 R1CS 约束

业务规则进入零知识证明系统前,通常需要转换为可验证的代数约束。本篇以包含乘法和加法的电路为例,逐步构造 R1CS 的三个线性组合,计算见证向量并检查约束是否成立,同时识别不能直接写成单条 R1CS 的表达式。

学习目标

  • 理解 R1CS 的标准形式以及左、右、输出线性组合的职责。
  • 将包含乘法、加法和常数的等式拆解为合法约束。
  • 使用具体见证值验证约束,并识别常见转换错误。

R1CS 为什么只允许两个线性组合相乘

R1CS 是 Rank-1 Constraint System,即秩一约束系统。每条约束采用如下形式:

(mathbfacdotmathbfz)(mathbfbcdotmathbfz)=mathbfccdotmathbfz(\\mathbf{a}\\cdot\\mathbf{z})(\\mathbf{b}\\cdot\\mathbf{z})=\\mathbf{c}\\cdot\\mathbf{z}

其中,mathbfz\\mathbf{z} 是见证向量,通常把常数 11 放在第一个位置;mathbfa\\mathbf{a}、mathbfb\\mathbf{b}、mathbfc\\mathbf{c} 是系数向量。三个点积分别称为左线性组合、右线性组合和输出线性组合。

例如采用变量顺序:

mathbfz=[1,x,y,t,o]\\mathbf{z}=[1,x,y,t,o]

表达式 2x+3y+52x+3y+5 可以写为:

[5,2,3,0,0]cdotmathbfz[5,2,3,0,0]\\cdot\\mathbf{z}

系数中的 55 乘以见证首位的常数 11,因此不需要另外创建常数变量。

一条 R1CS 可以表示 (x+2)y=o(x+2)y=o,但不能直接把 xy+yt=oxy+yt=o 当作单条标准约束,因为左侧含两个独立的乘积项。虽然两个线性组合相乘可以展开成多个乘积项,但不能任意表示所有二次表达式。

从电路等式拆出合法约束

考虑业务规则:输入 xx、yy,先计算乘积,再加上 xx,最终得到输出 oo。

xy+x=oxy+x=o

引入中间变量 t=xyt=xy,拆成两条约束:

  1. 乘法门:xcdoty=tx\\cdot y=t。
  2. 加法门:(t+x)cdot1=o(t+x)\\cdot1=o。

乘法加法电路与R1CS约束映射

固定见证顺序为 [1,x,y,t,o][1,x,y,t,o],对应系数如下:

约束 左向量 mathbfa\\mathbf{a} 右向量 mathbfb\\mathbf{b} 输出向量 mathbfc\\mathbf{c}
xy=txy=t [0,1,0,0,0][0,1,0,0,0] [0,0,1,0,0][0,0,1,0,0] [0,0,0,1,0][0,0,0,1,0]
t+x=ot+x=o [0,1,0,1,0][0,1,0,1,0] [1,0,0,0,0][1,0,0,0,0] [0,0,0,0,1][0,0,0,0,1]

第二条约束把加法放在左线性组合中,右线性组合取常数 11。因此,加法不需要额外制造两个变量相乘。

实际系统通常在有限域 mathbbFp\\mathbb{F}_p 内执行运算,所有等式都按模 pp 理解。这里用小整数方便手算;真实证明系统的有限域模数由证明方案及底层曲线等参数决定。

代入见证值逐条验证

选择 x=3x=3、y=4y=4,根据电路计算:

t=3times4=12,qquado=12+3=15t=3\\times4=12,\\qquad o=12+3=15

完整见证为:

mathbfz=[1,3,4,12,15]\\mathbf{z}=[1,3,4,12,15]

第一条约束计算结果为 3times4=123\\times4=12,第二条为 (12+3)times1=15(12+3)\\times1=15,两条均成立。

下面使用 Python 3 标准库实现同样的校验。示例采用模数 9797 展示有限域运算;该模数仅用于教学,不是生产证明系统的参数。

python
P = 97
z = [1, 3, 4, 12, 15]

constraints = [
    ([0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0]),
    ([0, 1, 0, 1, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 1]),
]


def linear(coefficients, witness):
    # 系数与见证按同一变量顺序排列
    return sum(a * v for a, v in zip(coefficients, witness)) % P


for index, (a, b, c) in enumerate(constraints, start=1):
    # 两侧乘积与输出都在有限域内比较
    left = linear(a, z) * linear(b, z) % P
    right = linear(c, z)
    print(f"约束{index}: {left} == {right}, 成立={left == right}")

预期输出:

text
约束1: 12 == 12, 成立=True
约束2: 15 == 15, 成立=True

如果把见证中的 tt 错填为 1111,第一条约束会得到 12ne1112\\ne11;若 oo 仍为 1515,第二条也会失败。校验必须覆盖所有约束,而不是只检查最终输出。

识别不能直接表示的表达式

R1CS 的限制并不是只能出现一次乘法,而是每条约束必须能分解成两个线性组合的乘积等于一个线性组合。

原始表达式 能否直接表示为一条约束 正确处理
x+y=ox+y=o 能 (x+y)cdot1=o(x+y)\\cdot1=o
(x+2)y=o(x+2)y=o 能 左组合 x+2x+2,右组合 yy
xy+1=oxy+1=o 能 xcdoty=o−1x\\cdot y=o-1
xy+xt=oxy+xt=o 能 x(y+t)=ox(y+t)=o
xy+tu=oxy+tu=o 一般不能 引入 v=xyv=xy,再约束 tu=o−vtu=o-v
xyz=oxyz=o 一般不能 引入 v=xyv=xy,再约束 vz=ovz=o

其中 xy+tu=oxy+tu=o 在互不相关的变量下通常无法直接分解成一条秩一约束,而 xy+xt=oxy+xt=o 可以提取公共因子 xx。判断前先尝试代数因式分解,避免产生不必要的中间变量。

还要注意,R1CS 约束成立不代表自动验证了整数范围。例如 xx 在有限域中的值为 9696,模 9797 时相当于 −1-1。如果业务要求 0lex<160\\le x<16,需要另外增加范围约束;仅凭乘加等式不能保证这一条件。

从业务规则转换时的验收检查

把一个电路交给证明系统前,可以按以下顺序检查:

  1. 固定见证向量顺序,确认所有系数向量长度相同且索引一致。
  2. 对每条约束分别检查左、右、输出三项是否都是线性组合。
  3. 为不能直接表示的乘法链或独立乘积引入中间变量,并确保中间变量受到约束。
  4. 选择至少一组合法输入,计算完整见证并验证每条等式。
  5. 故意修改一个中间值或输出值,确认相关约束能够发现错误。
  6. 对范围、布尔值和大小比较等业务条件另行检查是否已经编码。

例如要求布尔变量 bb 只能取 00 或 11,可以添加 b(b−1)=0b(b-1)=0。在任意域中,这条约束都会把 bb 限制为两个合法值,但不会自动限制其他变量。

最终得到的 R1CS 是一组代数条件,而不是原始计算步骤的执行程序。证明者提供的见证必须同时满足全部约束;因此,判断转换正确性时应同时检查合法见证能通过,以及违反业务规则的见证不能绕过约束。

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

目录与阅读设置

阅读设置

17

记录一个想法

把电路等式转换为 R1CS 约束

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

登录哪都通