抽查为什么平时不管用
这本书叫《抽查》，而这一章要证明抽查是没用的。一份一千零二十四步的计算记录，作弊者只改了一格——你随手戳三格抓住他的概率是 0.29%；你要抽到 99% 的把握，得戳 4714 格，比整份记录还长 4.6 倍。朴素的抽查不但抓不到人，还比老老实实重算一遍更贵。这本书剩下的四分之三，都是在修这个「没用」。
一份真的计算记录
先造一个具体的东西，后面十几章都会用它。规则简单到可以口算：
从一个数开始，反复做同一个动作：
加上一个固定的常数，然后立方。
x₀ = 12345
x₁ = (x₀ + c₀)³
x₂ = (x₁ + c₁)³
……一共 1024 步。
为了不让数越滚越大，所有算术都在「模 65537」下做
（也就是算完除以 65537 取余数）。
这个东西有个名字叫 MiMC，是一种专门为了「在证明系统里便宜」而设计的哈希函数，第 17 章会解释它为什么长这样。现在你只要把它当成一段普普通通的、有 1024 步的计算。跑出来的前八格是：
格号 0 1 2 3 4 5 6 7 … 1023
值 12345 26688 46524 58581 11769 24101 24183 19394 … 61995
└─输入 输出─┘
这 1024 个数就是这本书里的「计算记录」——把一段计算的每一步中间状态都写下来的那张表。证明者声称：「我从 12345 出发，按规则跑了 1024 步，得到 61995。」他要证的就是这句话。
这张表在文献里叫 trace（执行轨迹）。中文常见的翻译是「踪迹」「轨迹」，都容易让人以为是日志之类的东西。它其实就是草稿纸：你做一道长算术题时写在纸上的每一行中间结果。
整本书要做的事，用一句话说就是：让别人相信你的草稿纸是对的，而不必让他看这张纸，也不必让他重算一遍。这句话值得记住，因为后面所有的技术，都可以放回这句话里检查它在解决哪一半。
作弊者只需要改一格
现在假设证明者撒谎。他想让最后那个输出变成别的数——比如把一笔转账的金额改掉，或者让一道本来无解的题「有解」。他要付出的最小代价是什么？
答案是：改一格。他把第 700 格的数悄悄加 1，然后从那里往后重新算下去。得到的整张表在逻辑上是自洽的（每一步都符合规则），只有第 700 格那里断了一下。
好，现在轮到你了。你是验证者，不想读完 1024 个数（那就等于重算了）。你决定随机戳几格看看。
| 你戳几格 | 抓住他的概率 | |
|---|---|---|
| 1 格 | 0.0977% | 基本等于没戳 |
| 3 格 | 0.2927% | 一千次里抓到三次 |
| 10 格 | 0.9723% | |
| 100 格 | 9.3083% | 已经读了十分之一的表，抓住的概率还不到一成 |
| 1000 格 | 62.3576% | 几乎把整张表读完了，还有三分之一漏网 |
把要求提到「99% 的把握」，需要戳多少格？
要 99% 把握 → 4714 格 （整份记录只有 1024 格，是它的 4.60 倍） 要 2⁻⁴⁰ 把握 → 28378 格 （27.7 倍）
你没看错。因为是随机戳、允许重复，要 99% 的把握必须戳 4714 次——而整张表只有 1024 格。与其这样，不如从头到尾读一遍，1024 次，还是 100% 的把握。
这就是抽查在原始形式下的处境：它不但不省事，它比老老实实重做还贵。
旋钮在谁手里
把上面那件事写成算式，就能看清问题出在哪。设作弊者污染了整张表的比例是 δ（错误的扩散率），你戳 k 次：
抓住的概率 = 1 − (1 − δ)^k k 是你的旋钮：你想戳几次就戳几次，只是每次都要花钱。 δ 是他的旋钮：他想污染多少就污染多少，而他当然会选最小的那个。
作弊者会把 δ 压到 1/1024。于是你的 k 必须涨到几千，才能把乘积拉起来。这是一场你注定输的军备竞赛，因为对方的旋钮比你的便宜得多。
反过来看就很清楚了——如果作弊者被迫大改，抽查立刻变得极其好用：
| 他改了多少格 | 扩散率 δ | 你只戳 3 格，抓住的概率 |
|---|---|---|
| 1 格 | 0.10% | 0.2927% |
| 10 格 | 0.98% | 2.9012% |
| 100 格 | 9.77% | 26.5290% |
| 512 格（一半） | 50.00% | 87.5000% |
同样戳三格，抓住的概率从 0.29% 跳到 87.5%。差别完全不在你身上，全在他改了多少。
既然赢不了这场军备竞赛，那就把对方的旋钮拿走。
办法是：不要直接抽查那张原始的表，而是先把它改写成另一种形式，这种形式有一个性质——原表里任何一处哪怕只改一个数，改写后的版本都会有 98% 以上的位置对不上。
这样 δ 就不再由作弊者决定，而是由编码方式决定，被钉在 0.98 附近。他想小改也小改不了：一改就是一大片。于是 k = 3 就够了。
第 11 章会把这件事做出来，用的是一个高中生就能验证的事实。那一章是这本书的招牌。
顺便说，这也解释了为什么现实中的抽样审计还能抓到人：财务造假通常是成片的。一家公司要虚增十个亿的收入，做不到只改一张凭证——它得伪造一整条业务链：合同、发票、出入库单、银行流水、物流记录。δ 天然就很大，所以抽 30 张就有相当高的命中率。
而计算作弊不是这样。改一个数字就够了，剩下的部分让计算机重新算一遍，天衣无缝。这就是为什么审计业的经验不能直接搬到这里来。
这一章的每个数字都能用一行算术复核。先看那张「戳几格」的表：
import math
n = 1024 # 记录长度
for k in [1, 3, 10, 100, 1000]:
p = 1 - (1 - 1/n) ** k
print('戳 %5d 格：抓住 %.4f%%' % (k, 100 * p))
for target in [0.99, 2 ** -40]:
need = math.ceil(math.log(1 - target) / math.log(1 - 1/n))
print('要 %.10g 的把握，得戳 %d 格（记录只有 %d 格）' % (target, need, n))
# 反过来：他改得越多越好抓
for bad in [1, 10, 100, 512]:
print('他改 %3d 格，你戳 3 格抓住 %.4f%%'
% (bad, 100 * (1 - (1 - bad/n) ** 3)))
戳 1 格：抓住 0.0977% 戳 3 格：抓住 0.2927% 戳 10 格：抓住 0.9723% 戳 100 格：抓住 9.3083% 戳 1000 格：抓住 62.3576% 要 0.99 的把握，得戳 4714 格（记录只有 1024 格） 要 9.094947018e-13 的把握，得戳 28378 格（记录只有 1024 格） 他改 1 格，你戳 3 格抓住 0.2927% 他改 10 格，你戳 3 格抓住 2.9012% 他改 100 格，你戳 3 格抓住 26.5290% 他改 512 格，你戳 3 格抓住 87.5000%
再把那张计算记录本身跑出来。这段代码复现的就是书里那张表，后面十几章都会用到它，值得留一份：
import hashlib
P = 65537
h = hashlib.sha256(b'spotcheck-mimc').digest()
C = [] # 1024 个轮常数，从 SHA-256 里取
for i in range(1024):
if i % 16 == 0:
h = hashlib.sha256(h).digest()
C.append(int.from_bytes(h[(i % 16) * 2:(i % 16) * 2 + 2], 'big') % P)
x, trace = 12345, []
for i in range(1024):
trace.append(x)
x = pow(x + C[i], 3, P) # 加常数，立方，模 65537
print(trace[:8], '...', trace[-1])
# [12345, 26688, 46524, 58581, 11769, 24101, 24183, 19394] ... 61995
python3 -c "n=1024;print(*['%d 格 %.4f%%'%(k,100*(1-(1-1/n)**k)) for k in (1,3,10,100,1000)],sep='\n')"
在线跑：python.org/shell，纯标准库。上面那张表的前八格和最后一格，和书里印的逐个相同——这本书里每一张记录你都能自己跑出来。
- 体育兴奋剂检测。抽检的威慑力完全建立在「运动员不知道什么时候会被抽到」上。而一旦作弊方式变成「只在某几天用、其余时间干净」，δ 就被压到极小，抽检立刻失效。反兴奋剂机构的应对不是提高抽检频率（k），而是引入生物护照——记录长期指标，让任何一次用药都在整条曲线上留下痕迹。这正是「把小改动放大成大改动」的现实版。
- 校验和与纠错码。你每天都在用「让一处错误染到很多位置」这件事：一个 CRC32 让任何一个比特翻转都改变整个校验值；RAID、二维码、光盘上的里德–所罗门码更进一步，能在几百个字节被毁掉的情况下把原始数据算回来。第 11 章要用的那套编码，和二维码用的是同一个东西。这不是巧合——它们要的性质一模一样：任何小扰动都要产生大差异。
- 代码评审。一个 3000 行的 PR，评审者读 100 行，抓住 bug 的概率非常接近这一章那张表。这也是为什么「小 PR」不只是礼貌问题：它把 δ 抬高了——在一个 50 行的改动里，任何问题都占了很大比例。
- 数据库审计日志。一条被篡改的记录，在普通日志里只影响一行；而在 Merkle 化的日志里（第 13 章），它会让之后的每一个哈希都对不上。同一个思想：让局部的谎言产生全局的痕迹。
「多抽几次就行了。抽 3 次不够就抽 30 次，抽 30 次不够就抽 300 次——总能把概率堆上去。」
这个直觉在数学上不算错，但它把成本算反了。上面那张表里，戳 1000 格才有 62% 的把握，而整张表只有 1024 格——你已经付出了「重算一遍」的代价，却只拿到了「三分之二的把握」。抽查此时不是一个更便宜的方案，是一个更贵、更差的方案。
更要命的是，这里的成本关系是反过来的：记录越长（n 越大），要达到同样把握需要的抽查次数就越多（大约正比于 n）。抽查的开销随被检查的东西线性增长，这恰好是「简洁」的反面。
正确的方向不是加大 k，而是动 δ。第 11 章会把 δ 从 0.001 推到 0.98，然后 k = 3 就够了；工业系统用 k = 34 把作弊概率压到 2⁻¹⁰², 而且这个 k 不随记录长度增长。判据是：看到「抽样检查」四个字，先问 δ 是谁在定。如果是被查的人在定，这个检查大概率是摆设。
这一章的一句话
抽查能不能抓到人，取决于一个作弊者说了算的旋钮——错误的扩散率；而这个领域全部的技术含量，就是把这个旋钮从他手里抢过来，办法是先把要检查的东西改写成「改一处就会错一大片」的形式。
不过在改写之前，还有一件更基础的事必须先办：他得先把话钉死。如果他可以在看到你要戳哪一格之后再决定那一格填什么，那么无论你戳多少格、无论 δ 是多少，他都是满分。下一章有一个一千轮的实测：先看题再答的作弊者，1000 比 0 全过。以及一个具体的坑——承诺不加盐时，把它反推回去只要 28.2 微秒。