把程序摊成一张表
卷 II 那台机器只会证一句话：「我知道某个数。」离「我跑对了一整段程序」还差得很远。跨过去的办法朴素得让人意外——把程序摊平成一张表，再把「每一步都没算错」翻译成一堆加法和乘法的等式。一道 9×9 数独摊出来是 1620 条约束，其中 648 条只是在说「每个格子里的数得在 1 到 9 之间」。第 22 章会告诉你，这 648 条里少写 8 条会发生什么。
先说清楚在哪个世界里做算术
这一卷的所有算术都在一个有限域里做。听起来吓人，其实你早就用过：就是「模一个素数」的算术。这本书用的素数是 65537。
加法： (a + b) mod 65537
乘法： (a × b) mod 65537
减法： 照常，负数就加回 65537
除法： 也有！ a / b 的意思是「乘上 b 的逆元」，
也就是那个满足 b × b⁻¹ = 1 的数。素数模下每个非零元素都有逆元。
于是加减乘除四则运算齐全，和有理数一样好用——
唯一的区别是这里只有 65537 个数，而且它们首尾相接。
为什么非要用它？三个理由，都很实在：
- 精确。没有浮点误差，没有溢出。
(a+b)+c和a+(b+c)严格相等——这在浮点数里可不成立（这本书的姊妹篇《抹零》整本都在讲那件事）。 - 有限。元素个数有限，所以「随机取一个」这件事有确定的概率意义，第 12 章要靠它算出错误概率。
- 能长多项式。下一章要把整张表变成一条曲线，那件事只在域上成立。
约束长什么样
先看最小的例子，来自这个领域最常被引用的一段教材：「我知道一个 x，使得 x³ + x + 5 = 35。」（答案是 3，但我们不打算说。）
把这个式子拆成每次只做一个乘法的形式：
中间变量 约束（左边 × 右边 = 结果） ──────────────────────────────────────────── sym1 = x · x x × x = sym1 y = sym1 · x sym1 × x = y sym2 = y + x y+x × 1 = sym2 out = sym2 + 5 sym2+5 × 1 = out 一共 4 条约束。
注意每一条的形状都是「一坨东西 × 一坨东西 = 一坨东西」，其中每一坨都只是变量的线性组合（加法和乘常数，不含变量相乘）。这个形状有个名字叫 R1CS（一阶约束系统），今天大部分证明系统的输入格式就是它。
把所有变量排成一行，就得到见证向量：
见证向量 w = [ 1, 3, 9, 27, 30, 35 ]
│ │ │ │ │ └─ out
│ │ │ │ └────── sym2 = y + x
│ │ │ └─────────── y = x³
│ │ └──────────────── sym1 = x²
│ └───────────────────── ⟦ x ⟧ ← 秘密就在这里
└────────────────────────── 常数 1（永远排第一位）
长度 6，其中第 1 位是常数，最后一位是公开的输出 35，
中间四个是证明者的秘密。
验证一份见证，就是把它代进那 4 条约束，看每一条是不是都成立。本机跑：
x³ + x + 5 = 35 的约束条数 4 见证向量长度（含常数 1） 6 见证向量 1 3 9 27 30 35 全部约束成立 True 把 x 偷偷改成 4，第几条约束先炸 第 1 条
最后那行是重点：作弊者改一个数，某一条约束立刻不成立。他要想瞒过去，就得把后面所有相关的中间变量一起改——而那正好是第 3 章说的「作弊只需要改一格」的场景。这一卷剩下的三章，就是要让这个「一格」变成「几万格」。
电路（circuit）里没有电。它是一张数据流图：输入从左边进来，经过一堆加法门和乘法门，结果从右边出去。之所以叫「电路」，纯粹是因为这个概念最早来自计算复杂性理论里的布尔电路。写电路 = 写一堆等式，不涉及任何硬件。
约束（constraint）也不是「限制」的意思，它就是一条等式。「满足约束」= 「这个等式成立」。「约束数」= 「有多少条等式要检查」，也就是这份证明有多贵。
见证（witness）在第 2 章出现过，现在它有了具体形状：它就是那张填满了所有中间变量的表。不是「答案」，是「答案 + 全部草稿」。
一道数独有多大
换一个所有人都熟悉的例子：「我知道这道数独的解。」陈述是那道题（哪些格子已经给了什么数），见证是完整的 81 格。
要写哪些约束？两类：
第一类：每个格子里的数必须在 1…9 之间
(v−1)(v−2)(v−3)(v−4)(v−5)(v−6)(v−7)(v−8)(v−9) = 0
这个乘积为零，当且仅当 v 是 1 到 9 里的某一个。
一次只能乘两个数，所以拆成 8 条约束。
81 格 × 8 = 648 条
第二类：每一行、每一列、每一宫里的 9 个数两两不等
「a ≠ b」怎么写成等式？用一个技巧：
引入一个新变量 inv，要求 (a − b) × inv = 1
如果 a = b，左边恒为 0，永远凑不出 1 —— 约束无法满足。
如果 a ≠ b，取 inv = (a−b)⁻¹ 即可。
9 行 + 9 列 + 9 宫 = 27 组，每组 C(9,2) = 36 对
27 × 36 = 972 条
数独电路：约束条数 1620 其中「每格 ∈ 1..9」 648 其中「两两不等」 27 组 × 36 对 = 972 见证向量长度 1702 真解通过全部约束 True 一道给了 30 个数的题：公开输入 / 秘密见证 30 / 51 把第一格 5 改成 6，第几条约束先炸 第 651 条（属于「两两不等」那一段）
注意那个「不等」的技巧：为了表达一个不等式，我们凭空造了一个新变量，并且要求证明者把它算出来。这是这个世界里的通用手法——凡是不能直接用加乘表达的东西，都要靠「让证明者提供一个辅助值，再用约束把它钉死」来实现。
见证向量长度 1702，比 81 大了二十倍——多出来的全是这类辅助变量。这就是「把程序摊成表」的真实成本：表比程序大得多。
什么东西便宜，什么东西贵
这是这一章最该带走的东西，因为它和你在 CPU 上的全部直觉相反：
| 操作 | 在 CPU 上 | 在电路里 | 为什么 |
|---|---|---|---|
域加法 a + b | 1 周期 | 0 条约束 | 线性组合是免费的，它被吸收进下一条约束的「一坨」里 |
域乘法 a × b | 3–5 周期 | 1 条约束 | R1CS 的基本单位就是它 |
判断相等 a == b | 1 周期 | 2–3 条 | 要引入辅助变量和逆元 |
比较大小 a < b | 1 周期 | 33 条 | 域里没有「大小」——元素首尾相接，没有顺序。只能把数拆成 32 个比特，每个比特要一条「它只能是 0 或 1」的约束 |
| 32 位异或 | 1 周期 | 96 条 | 同上，位运算必须先拆位 |
| 一次 SHA-256 | 约 1 微秒 | 33512 条 | 它全部由位运算和 32 位加法组成。第 17 章会把这个数亲手数出来 |
| 一次 MiMC 哈希 | 比 SHA-256 慢 | 182 条 | 专门设计成只用加法和立方——在 CPU 上更慢，在电路里便宜 184 倍 |
在电路里，「加乘」是空气，「位」是黄金。
所以这个领域出现了一整族在 CPU 上毫无意义、只为电路而生的算法：算术友好的哈希（MiMC、Poseidon、Rescue）、算术友好的加密、算术友好的随机数。它们在你的笔记本上跑得比 SHA-256 慢，但在证明系统里便宜两个数量级。
这也是一个更一般的现象的例子：「什么操作便宜」不是绝对的，它由你所在的计算模型决定。换了模型，整套算法审美就得重写一遍。
分支和循环去哪了
电路是一张固定的图，没有「跳转」这回事。所以：
| 你写的 | 电路里变成 | 代价 |
|---|---|---|
if c { A } else { B } | 两边都算，然后 out = c·A + (1−c)·B，并加一条 c·(c−1) = 0 保证 c 只能是 0 或 1 | 两个分支的代价相加，不是取大的那个 |
for i in 0..n，n 由数据决定 | 展开到最坏情况。循环次数必须在编译期确定 | 一个「最多循环一百万次」的循环，哪怕实际只跑 3 次，也要付一百万次的钱 |
arr[i]，i 是变量 | 要么全表扫一遍（n 条约束），要么用 Merkle 证明（第 13 章） | 随机访问内存在这里是奢侈品，而它在 CPU 上是免费的 |
这三行解释了为什么「把任意程序变成证明」这件事直到最近才变得实用，也解释了第 21 章那个 zkVM 要解决的问题究竟有多难。
一个能跑的 R1CS 检查器只要三十行。写一次，这个概念就再也不抽象了：
P = 65537
def dot(row, w): # 一「坨」= 变量的线性组合
return sum(k * w[i] for i, k in row.items()) % P
def check(A, B, C, w): # 逐条验：(A·w) × (B·w) == (C·w)
for i, (a, b, c) in enumerate(zip(A, B, C)):
if dot(a, w) * dot(b, w) % P != dot(c, w):
return i # 第几条先炸
return -1
# --- x³ + x + 5 = 35 ---
# 下标： 0=常数1 1=x 2=sym1 3=y 4=sym2 5=out
A = [{1: 1}, {2: 1}, {3: 1, 1: 1}, {4: 1, 0: 5}]
B = [{1: 1}, {1: 1}, {0: 1}, {0: 1}]
C = [{2: 1}, {3: 1}, {4: 1}, {5: 1}]
w = [1, 3, 9, 27, 30, 35]
print('约束条数', len(A), ' 见证长度', len(w))
print('真见证通过：', check(A, B, C, w) == -1)
bad = [1, 4, 9, 27, 30, 35] # 只把 x 改成 4，别的不动
print('把 x 改成 4，第 %d 条先炸' % (check(A, B, C, bad) + 1))
约束条数 4 见证长度 6 真见证通过： True 把 x 改成 4，第 1 条先炸
数独那 1620 条也可以照着搭，两个循环的事——你会发现写电路的体力活占了九成，这正是 Circom 这类语言存在的理由。下面给出「两两不等」那个技巧的最小验证：
a, b = 5, 7
inv = pow(a - b, -1, P) # (a−b) 的逆元
print('a≠b 时能凑出 1：', (a - b) * inv % P == 1)
a, b = 5, 5
try:
inv = pow(a - b, -1, P) # 0 没有逆元
except ValueError as e:
print('a==b 时无解：', e)
python3 -c "P=65537;print((5-7)*pow(5-7,-1,P)%P)"
在线跑：python.org/shell。想看工业级的写法，去 docs.circom.io——Circom 就是一门专门用来生成这些约束的语言。
- Circom / Noir / Halo2 / Cairo。这些语言的工作全都是「把你写的逻辑编译成约束」。它们的编译输出里有一个数字叫「约束数」，那就是你这份证明的价格标签。写这类代码时，程序员盯着的不是「运行时间」，是约束数——整套性能直觉都得换掉。
- 为什么以太坊上的 zk 应用最早都是「转账」和「投票」。因为它们的逻辑几乎全是加法和比较，约束数小。而「跑一个神经网络」「验一段任意代码」直到最近才变得可行——第 21 章会给出今天的数字。
- 「凭空造一个辅助变量再钉死它」是这个领域的万能手法。不等、除法、比较、开方、排序、哈希，全都用它。这个模式在别处也有名字：非确定性计算。它的思想是「结果比过程好验」——让证明者去猜答案，电路只负责检查。第 21 章的 zkVM 把这个手法用到了极致。
- 和数据库约束的对照。SQL 里的
CHECK、UNIQUE、外键，做的事情和这里一模一样：用一组等式/不等式，把「合法的数据」和「非法的数据」分开。数独那 972 条「两两不等」，本质上就是 27 个UNIQUE约束。差别只在于：数据库信任自己的存储引擎，而这里谁都不信任。
「电路就是程序的另一种写法，把代码翻译过去就行了，性能应该差不多。」
电路是一张展开到最坏情况的、没有控制流的数据流图。你的程序里那些「大部分时候会提前退出」「这个分支很少走」「这个数组很少访问」的优化，在这里一分钱都省不下来——电路必须为每一种可能性都付钱。
具体的坑：一个 if 的代价是两个分支之和（不是较大者）；一个上限一百万次的循环，跑 3 次也要付一百万次的钱；一次 arr[i] 可能比一百次算术还贵。
最反直觉的一条：算得快的算法在这里不一定便宜。SHA-256 在你的 CPU 上一微秒跑完，在电路里要 33512 条约束；MiMC 在 CPU 上慢得多，在电路里只要 182 条。判据是：在电路里，成本 = 乘法门的个数，和运行时间没有关系。把这句话换掉你脑子里的「时间复杂度」，这一卷剩下的内容才读得顺。
这一章的一句话
「我跑对了一段程序」被翻译成「我有一张表，它满足这几千条加乘等式」；于是要证的东西从一个结果变成了整个过程，而这个翻译的代价，是一套和 CPU 完全相反的成本直觉。
但现在我们回到了第 3 章那个死胡同：验证者要检查 1620 条约束，就得读整张表——那和重算一遍没区别。而如果他只抽查几条，作弊者改一格就能躲过去。
下一章解决它，而且解法出人意料地不含任何密码学。只要把这张表看成一条曲线，再把曲线画长 64 倍——改一格就会变成错 64513 格。同样戳三格，抓住的概率从 0.29% 变成 99.9996%。这是全书的招牌，而它成立的理由，是一条你在初中就学过的事实。