抽一个点就够
上一章比较的是两张表，可现实中验证者手里只有一张。他真正要检查的是「这张表满足那 1620 条约束吗」。这一章把那 1620 条压成一条等式，再把「检查一条等式」压成「在随机的一个点上代进去算一次」。而且我要先给你一个完全不含密码学、可以在自己机器上跑出来的例子：验一个 512×512 的矩阵乘法，不重算，快 58 倍，错判概率上界 3.55 × 10⁻¹⁵。
先看一个没有密码学的版本
Freivalds 在 1979 年提出的问题：有人给你三个大矩阵 A、B、C，声称 A × B = C。你怎么查？
老实的做法是把 A×B 重算一遍再比对，代价 n³ 次乘法。Freivalds 的做法是：
随机取一个向量 v。 检查 A × (B × v) == C × v ？ 左边：先算 B×v（n² 次乘法），再算 A×(那个结果)（又 n² 次）。 右边：C×v（n² 次）。 一共 3n² 次乘法，而不是 n³ 次。 如果 A×B == C，两边永远相等。 如果 A×B ≠ C，随机的 v 让两边碰巧相等的概率 ≤ 1/|F|。
本机跑 n = 512（在模 65537 的域上）：
老实重算一遍（268 百万次乘加） 5304.8 ms Freivalds 抽 3 次随机向量 91.98 ms 快了多少倍 58× 正确的 C 通过 true 改了一个格子的 C 通过 false Freivalds 抽 3 次的错判上界 3.55e-15
上面这个例子里没有哈希，没有椭圆曲线，没有任何「难解问题」。它是 1979 年的一个纯粹的算法技巧。而它已经做到了这本书第 1 章承诺的那件事：验证比重做便宜了 58 倍，代价是 3.55 × 10⁻¹⁵ 的错判概率。
而且这个倍数随规模增长：操作数之比是 n³ ÷ 9n² = n/9。n 越大，越划算。
所以「验证比执行便宜」不是密码学带来的。密码学后来加进去，是为了解决另外两件事：让证明者没法作弊（承诺，第 4 章），以及让秘密不必露出来（第 7 章）。这个先后关系，是这本书想扭正的一个常见误解。
那条支撑一切的不等式
Freivalds 和上一章的编码，靠的是同一句话的两个形态。这句话叫 Schwartz–Zippel 引理：
设 f 是一个不恒为零的多项式，次数为 d，域的大小是 |F|。从域里均匀随机取一个点 r，那么
Pr[ f(r) = 0 ] ≤ d / |F|
翻译成人话：一个不恒为零的多项式，在随机一点上碰巧取零的概率，不超过「次数 ÷ 域大小」。
推论（这才是我们要用的形态）：两个不同的、次数 ≤ d 的多项式，在随机一点上碰巧相等的概率 ≤ d / |F|。
它的证明就是上一章那句初中的话：d 次多项式最多 d 个根，所以 |F| 个候选点里最多 d 个会中招。
把这个上界代进真实参数：
| 场景 | 次数 d | 域大小 |F| | 错判概率上界 |
|---|---|---|---|
| 这本书的玩具域 | 1023 | 65537 | 1.5610% |
| 典型 STARK | 2²⁰ | 2⁶⁴ | 5.68 × 10⁻¹⁴ |
| 典型 SNARK（BN254） | 2²⁰ | 2²⁵⁶ | 9.06 × 10⁻⁷² |
| 对照：一次哈希碰撞 | — | 2¹²⁸ | 2.94 × 10⁻³⁹ |
域大到 2²⁵⁶ 的时候，一个点就够了——不需要抽三十几次。这就是第 5 章那张「代数路线 vs 抽查路线」表的技术原因：域越大，一次抽样买到的可靠性越多。而 STARK 用小域（为了算得快），所以要多抽几次。
把 1620 条压成 1 条
现在回到第 10 章那堆约束。做法分两步，都很直接。
第一步：把「一堆等式」变成「一条多项式等式」。
1620 条约束，第 i 条长这样： Aᵢ · Bᵢ = Cᵢ
把每一条的三边分别看成「在位置 i 上的取值」，插值成三条曲线：
A(x)、B(x)、C(x) （用上一章那个插值）
于是「全部 1620 条都成立」等价于：
A(x)·B(x) − C(x) = 0 在 x = 1, 2, …, 1620 的每一个位置上
一个多项式在这 1620 个位置上全为零，等价于它能被
Z(x) = (x−1)(x−2)…(x−1620) ← 叫「消失多项式」
整除。也就是说，存在某条曲线 H(x) 使得
A(x)·B(x) − C(x) = Z(x) · H(x) ← 一条等式，替代了 1620 条
第二步：用一个随机点检查这条等式。
验证者随机抽一个点 r，要求证明者报出
A(r), B(r), C(r), H(r)
然后自己算 Z(r)（他能算，因为 Z 是公开的），检查
A(r)·B(r) − C(r) == Z(r)·H(r) ？
如果证明者的表真的满足全部约束，等式恒成立。
如果他的表有任何一处不满足，那么 A·B − C − Z·H 就是一条
不恒为零的多项式，Schwartz–Zippel 说它在随机点上为零的概率 ≤ d/|F|。
1620 条约束，一个随机点，四个数。这就是「简洁」这个词落到实处的样子。
消失多项式（vanishing polynomial）听起来玄，它就是「在指定的那些点上取零的最简单的那条曲线」，也就是把这些点当根乘起来：Z(x) = ∏(x − 那些点)。
它在这里扮演的角色，和整数世界里的整除一模一样：「这个数能被 12 整除」等价于「它是 12 的倍数」。这里是「这条曲线在那 1620 个点上全为零」等价于「它是 Z 的倍数」。把「一堆条件」压成「一个整除关系」，这是这一整套技术最核心的代数动作。
顺带一提，如果那 1620 个点取成上一章那种「乘法子群」，Z(x) 会退化成极其简单的 x^1620 − 1，验证者算它只要一次快速幂。工业系统全都这么选点，纯粹为了让验证者这一步便宜。
随机化在这里到底干了什么
值得把这一章的动作抽象一层，因为它在别处会反复出现：
| 原来的问题 | 随机化之后 | 代价 |
|---|---|---|
| 「对所有 i，等式成立」（全称量词，要查 n 次） | 「在这一个随机点上，等式成立」（查 1 次） | d / |F| |
| 「这两个大对象完全相同」 | 「它们的一个随机指纹相同」 | 1 / |F| |
| 「A×B 确实等于 C」 | 「A×(B×v) 确实等于 C×v」 | 1 / |F| |
随机化把「全称量词」换成了「一次抽样」，代价是一个可以任意压低的错误概率。这是理论计算机科学在 1970–80 年代最重要的一次范式转变，它的顶点是 1992 年的 PCP 定理：任何数学证明都可以改写成一种形式，使得验证者只需随机读取其中的常数个比特。
这本书讲的全部东西，都是那个定理三十年后的工程化落地。
Freivalds 值得亲手跑，因为它是「验证比执行便宜」最短的一个例子，纯标准库：
import random, time
P, n = 65537, 200
A = [[random.randrange(P) for _ in range(n)] for _ in range(n)]
B = [[random.randrange(P) for _ in range(n)] for _ in range(n)]
t = time.perf_counter()
C = [[sum(A[i][k]*B[k][j] for k in range(n)) % P for j in range(n)]
for i in range(n)] # 老实重算 n³
t_mul = time.perf_counter() - t
def matvec(M, v):
return [sum(M[i][j]*v[j] for j in range(n)) % P for i in range(n)]
def freivalds(A, B, C, reps=3):
for _ in range(reps):
v = [random.randrange(P) for _ in range(n)] # 随机向量
if matvec(A, matvec(B, v)) != matvec(C, v):
return False
return True
t = time.perf_counter()
ok = freivalds(A, B, C)
t_fr = time.perf_counter() - t
bad = [row[:] for row in C]
bad[123][45] = (bad[123][45] + 1) % P # 改一个格子
print('老实重算 %.0f ms' % (t_mul * 1000))
print('Freivalds %.0f ms → 快 %.0f 倍' % (t_fr * 1000, t_mul / t_fr))
print('正确的 C 通过：', ok, ' 改了一格的 C 通过：', freivalds(A, B, bad))
print('错判上界 %.2e' % ((1 / P) ** 3))
老实重算 527 ms Freivalds 19 ms → 快 28 倍 正确的 C 通过： True 改了一格的 C 通过： False 错判上界 3.55e-15
纯 Python 在 n=200 跑出 28 倍；书里那个 58 倍是 n=512 的结果。把 n 翻倍，倍数就翻倍——因为比值是 n/9。这是这本书里唯一一个「越大越划算」在几行代码里就能看见的地方。
再验一下 Schwartz–Zippel 本身：造两条不同的 1023 次曲线，数一数它们在整个域里有多少个点重合。
# 接第 11 章那段 lde()：A 和 B 是两条曲线在 65536 个点上的值
same = sum(a == b for a, b in zip(A, B))
print('重合点 %d，上界 d = 1023，占比 %.4f%%' % (same, 100 * same / 65536))
# 重合点 1023，上界 d = 1023，占比 1.5610%
python3 fr.py # n=200 大约 0.6 秒
在线跑：python.org/shell（n 调小到 100 以内更快）。Freivalds 的原始论文是 1979 年的《Fast probabilistic algorithms》。
- 分布式计算的结果抽检。你把一个大矩阵乘法扔给一百台机器，怎么知道它们没偷懒？Freivalds 让你用 1% 的成本验完。这个思路在 MapReduce 时代就有实现，只是没人叫它「零知识」。
- 数据库比对。两个库的某张表是否一致？不必逐行比，各自算一个「随机加权和」（本质上是在一个随机点求值），比对一个数。这就是 Schwartz–Zippel 的第二行形态。rsync 的滚动校验、Git 的对象哈希、区块链的状态根，全是同一族。
- 集合相等性检查。「这两个乱序的集合是不是同一个」——把每个元素 a 变成因式
(x − a)乘起来，在随机点求值比对。这一招叫「置换检查」，是 PlonK 系统里最核心的组件之一（它用来保证「电路里同一根线在不同位置的取值一致」）。 - 反面：不要在没有随机性的地方用它。如果那个「随机点」是攻击者能预测或影响的，整套论证立刻归零——他会构造一条恰好在那个点上取零的曲线。这就是第 8、9 章那件事：随机点从哪来，是整个系统的命门。在非交互系统里，这个点由 Fiat–Shamir 生成；哈希输入漏一样，命门就开了。
「概率性的验证不够严谨。我要的是『一定对』，不是『99.9999% 对』。真要紧的事情不能靠抽样。」
这个直觉在日常里是对的，在这里错得很彻底，因为它没有和现实中的其他错误率作比较。
| 事件 | 概率 |
|---|---|
| 一次 Schwartz–Zippel 检查错判（2²⁵⁶ 的域） | 9 × 10⁻⁷² |
| 宇宙射线让你的内存翻一个比特（每 GB 每小时，典型估计） | 10⁻⁴ 量级 |
| 硬盘静默数据损坏 | 10⁻¹⁵ 量级 |
| 你的 CPU 有一个未被发现的浮点缺陷 | 历史上发生过（1994 年 Pentium FDIV） |
你所谓「一定对」的重算，跑在一台会被宇宙射线翻位、可能有硅缺陷、由几百万行没被证明过的编译器和操作系统支撑的机器上。它的实际错误率，比一次 2⁻²³⁵ 的抽样检查高出六十多个数量级。
正确的问法不是「是不是 100%」，而是「这个错误率和我系统里其他环节的错误率比，处在什么位置」。判据是：当一个概率低于「你的硬件出错」和「你的代码有 bug」时，它就不再是这个系统的短板——继续压它没有收益，该去看别的地方了。第 22 章会告诉你短板真正在哪。
这一章的一句话
随机化把「所有 i 都成立」换成了「这一个随机点上成立」，代价是一个可以压到任意小的错误概率；而这件事本身不需要密码学——密码学后来加进去，是为了防止证明者作弊和保护秘密，不是为了让验证变快。
但这里有一个漏洞，你可能已经看出来了：验证者凭什么相信证明者报出的 A(r)、B(r)、C(r)、H(r) 是真的？他完全可以随口编四个数，让等式凑上。
下一章补上最后这块。答案回到第 4 章：那四个数必须是从一个事先钉死的东西里「打开」出来的。一张 65536 格的表压成 32 字节的指纹，打开任意一格要 512 字节——而这三样东西（承诺、抽查、打开）凑齐之后，一台完整的简洁证明系统就成型了。