05 一次问答的解剖

◻ 本章先赊三条

第一条。这台机器只需要那个「单向函数」满足一条额外性质——可加。整个三步舞就是这一条性质的直接后果，不需要任何别的魔法。 第二条。一轮问答能买到多少可靠性，只取决于挑战有多少种可能。山洞是 2 种，这台机器是 2²⁵⁶ 种。 第三条。「重复很多轮把概率压下去」这个做法，在现实里往往贵得离谱：一个 1000 条边的图三染色证明，要压到 2⁻⁴⁰ 得跑 27713 轮。

先要一样东西：正着好算，倒着算不动

整章只需要一个数学零件，而且它只需要满足两条性质。第一条你早就见过：

有一个起点 G，和一个「走 x 步」的动作，记作 x·G。

  正着算：给你 x，算出 x·G          → 很快（毫秒级，哪怕 x 是 256 比特）
  倒着算：给你 x·G，反推出 x        → 目前没人会（这叫「离散对数问题」）

这跟哈希不一样的地方在第二条性质，而这一条才是三步舞成立的原因：

可加：(a + b)·G = a·G + b·G

  也就是说：「走 a 步再走 b 步」和「一次走 a+b 步」到的是同一个地方。
  哈希函数完全没有这条性质——H(a+b) 和 H(a)、H(b) 毫无关系。

满足这两条的东西现实中有很多。比特币和以太坊用的那个叫 secp256k1，是一条椭圆曲线；曲线上的点可以「相加」，「走 x 步」就是把起点自己加 x 次。这一章完全不需要你懂椭圆曲线——你只要接受上面那两行字。（想看它长什么样，第 16 章有一张对照表。）

✎ 术语正名

私钥就是那个 x，一个 256 比特的随机数。公钥就是 x·G。「私钥不能从公钥推出来」这句话，说的正是上面那个「倒着算不动」。

所以「我持有这个钱包的私钥」这句话，翻译成这本书的语言就是：「我知道一个 x，使得公开的那个点 P 等于 x·G」。这是一句标准的陈述加见证：P 是公开的陈述，x 是秘密的见证。

三步

Peggy 想让 Victor 相信「我知道 P 对应的那个 x」，但不告诉他 x。

第一步（押注 · 承诺）
    Peggy 随机取一个数 k（用完即弃），算出 R = k·G，把 R 发给 Victor。
    ——注意这就是第 4 章的「先钉死」：她把 k 锁住了，事后改不了。

第二步（出题 · 挑战）
    Victor 随机取一个数 c，发回去。
    ——他不知道 k，也不知道 x。他只是在扔骰子。

第三步（作答 · 响应）
    Peggy 算 s = k + c·x，把 s 发给 Victor。

验证
    Victor 检查：s·G  ==  R + c·P ？

为什么诚实的 Peggy 一定能过？把 s 展开，用那条「可加」：

s·G = (k + c·x)·G
    = k·G + (c·x)·G          ← 可加
    = R + c·(x·G)
    = R + c·P                ← 因为 P 就是 x·G

严格相等。完备性成立。

跑在真曲线上是这样（这是本机实跑的一次，数值截了前 32 位十六进制）：

公钥 P 的 x 坐标      6117aefb470d623b3b11a1820c6b72a9…
第一步  R = k·G       7cd11c7c0638f7f4da8fe1f4006ca946…
第二步  挑战 c         0x3fb2c1
第三步  s = k + c·x    0c3f2b893711c86ed9164d447e0e3dbc…
验证    s·G == R + c·P   ✓ 通过

而那个 ⟦ x ⟧ 从头到尾没有出现在这三行里的任何一行。

骗子为什么过不去

假设 Mallory 不知道 x，她想蒙混过关。她的处境是这样的：

如果她能预知 c，那太容易了：随便挑一个 s，令 R = s·G − c·P，验证等式自动成立。这正是第 4 章那个「先看题再答」的作弊者，通过率 100%。
但她必须先交 R。交完之后 c 才出现。这时她被卡住了：要让等式成立，她得算出一个 s 满足 s·G = R + c·P——而从一个点反推出「走了多少步」，正是那个倒着算不动的问题。

那她能不能赌？能。她可以赌 c 恰好是某个她事先准备好的值。赌中的概率 = 1 / 挑战的可能取值数。

而在 secp256k1 上，c 的取值有大约 2²⁵⁶ 种。

◆ 一轮买多少比特

把「挑战空间的大小」记作 N，那么一轮问答把作弊概率压到 1/N，也就是买到 log₂N 比特的可靠性。

协议	一轮的挑战有几种	一轮买到	压到 2⁻⁴⁰ 要几轮
山洞（左／右）	2	1 比特	40
三色问题（挑一条边）	3	1.58 比特	26
图三染色，1000 条边	1000	0.0014 比特 ✗	27713
Schnorr（secp256k1）	2²⁵⁶	256 比特	1

第三行是个陷阱，值得看清楚：图三染色是经典教科书里的零知识例子，它每轮只挑一条边来检查，作弊者只要染错一条边，被抽到的概率就是 1/|E|。边越多，一轮买到的可靠性越少——1000 条边的图要跑 27713 轮才安全。

而这正是第 3 章那个「扩散率」问题换了张脸：作弊者只染错一条边（δ = 1/1000），你就得抽两万七千次。

为什么这台机器这么便宜

Schnorr 之所以能一轮解决，是因为它不是靠抽查。它靠的是代数：那条「可加」性质让验证等式要么严格成立，要么严格不成立，没有中间地带。作弊者不是「被抽中才露馅」，而是「除非蒙对那 2²⁵⁶ 分之一，否则根本算不出 s」。

这就带出了这本书两条并行的技术路线，值得现在就摆清楚：

	代数路线	抽查路线
典型代表	Schnorr、Groth16、KZG	STARK、FRI、Merkle 树
可靠性来自	某个数学问题很难（离散对数、配对）	随机抽查 + 编码的扩散率
一轮的效率	极高（一轮 256 比特）	低（一轮 3 比特，要抽几十次）
依赖	椭圆曲线 → 量子计算机能打破	只依赖哈希 → 目前认为抗量子
这本书里	卷 II（第 5–9 章）	卷 III（第 10–13 章）

两条路线在第 16 章会合。现实中的系统往往两条都用：用抽查路线处理「一大段计算」，再用代数路线把最后那点东西压到 128 字节。

⌨ 自己跑一遍

三步舞不需要椭圆曲线也能跑。下面用最朴素的「模指数」版本（同一条可加性，只是写成乘法），三十行纯 Python，零依赖：

import random

# 一个「正着好算、倒着算不动」的场景：模 p 的乘法群，阶为 q
p = 2 * 1019 + 1          # 2039，素数
q = 1019                  # 子群的阶，也是素数
g = pow(3, 2, p)          # 一个阶为 q 的生成元

x = random.randrange(1, q)          # ⟦ 私钥 ⟧
P = pow(g, x, p)                    # 公钥（陈述）

# --- 三步舞 ---
k = random.randrange(1, q)          # 第一步：押注
R = pow(g, k, p)
c = random.randrange(0, q)          # 第二步：出题
s = (k + c * x) % q                 # 第三步：作答

lhs = pow(g, s, p)                  # 验证：g^s == R · P^c
rhs = (R * pow(P, c, p)) % p
print('诚实证明者通过：', lhs == rhs)

# --- 骗子：先交 R，再收到随机的 c ---
wins = 0
for _ in range(10000):
    guess_c = random.randrange(0, q)        # 她赌挑战会是这个
    fake_s = random.randrange(0, q)
    R2 = (pow(g, fake_s, p) * pow(P, -guess_c, p)) % p   # 倒推出 R
    real_c = random.randrange(0, q)         # 但真正的挑战是现场抛的
    if (pow(g, fake_s, p) == (R2 * pow(P, real_c, p)) % p):
        wins += 1
print('骗子 10000 次通过 %d 次，理论值 %.1f 次' % (wins, 10000 / q))

诚实证明者通过： True
骗子 10000 次通过 7 次，理论值 9.8 次      # 这一行每次跑都不一样，在 10 上下浮动

把 q 换成一个大素数（比如 secp256k1 的阶），骗子那一行就永远是 0——因为 1/2²⁵⁶ 在宇宙寿命里都不会撞上一次。这就是「一轮买 256 比特」的全部含义。

python3 -c " import random p,q=2039,1019; g=pow(3,2,p); x=random.randrange(1,q); P=pow(g,x,p) k=random.randrange(1,q); R=pow(g,k,p); c=random.randrange(0,q); s=(k+c*x)%q print(pow(g,s,p)==R*pow(P,c,p)%p)"

在线跑：python.org/shell。要跑真曲线版本，装 pip install ecdsa 或直接用 Node 的 crypto.createECDH('secp256k1')。

▸ 在现实里

比特币的每一笔交易。2021 年的 Taproot 升级把 Schnorr 签名（BIP-340）正式带进了比特币。你花掉一个 UTXO 时附的那 64 字节，就是这一章这台机器的非交互版本（第 8 章会讲怎么去掉那个来回）。
你手机上的 SSH 登录。ssh-ed25519 用的 Ed25519 是同一个三步舞的一个变体。你每次 git push，都在向服务器证明「我知道那把私钥」，而私钥从未离开你的电脑。
WiFi 的 WPA3 握手。它换掉了 WPA2 那个能被离线爆破的四次握手，改用一种「双方各自证明自己知道密码、但不发送密码」的协议（Dragonfly）。同一个思想：把「发送秘密」换成「证明持有秘密」。
反面教材：绝大多数网站的密码登录。你把明文密码发给服务器，服务器哈希一遍对比。这在本章的框架里是最原始的做法——你把见证本身交出去了。第 7 章会说明为什么它连零知识的边都沾不上，以及为什么改进它比听起来难。

✗ 这个直觉是错的

「零知识证明要重复很多轮，所以慢。上一章那个山洞跑四十轮，现实里的系统肯定跑成千上万轮吧。」

「重复很多轮」不是零知识的固有属性，是挑战空间太小的症状。山洞只有左右两个方向可问，所以每轮只买 1 比特；把挑战换成一个 256 比特的随机数，一轮就够了。

反过来，这也解释了一个更值得警惕的现象：教科书里那些「优雅」的零知识例子（三染色、哈密顿回路），在工程上全都是灾难。图三染色每轮只检查一条边，1000 条边的图要跑 27713 轮——而每一轮都要重新承诺一遍整个图的染色。这些例子存在的意义是证明「任何 NP 问题都有零知识证明」这个定理，不是拿来用的。

判据是：看到一个证明协议，先问「一轮的挑战有多少种可能」。这个数的对数，就是一轮的产出；产出太低的协议，无论多优雅都用不了。第 11 章会给出抽查路线上的答案——那里一轮只买 3 比特左右，所以要抽三四十次，但这个次数不随被证的计算变长，于是仍然是简洁的。

✓ 结账

第一条「只需要可加这一条性质」——付清了：完备性那三行推导里，唯一用到的就是 (a+b)·G = a·G + b·G。 第二条「一轮买多少取决于挑战有多少种」——付清了：山洞 1 比特，Schnorr 256 比特，因为挑战空间是 2 和 2²⁵⁶。 第三条「重复很多轮往往贵得离谱」——付清了：1000 条边的图三染色要 27713 轮。教科书例子和工程可用之间隔着这个数。

这一章的一句话

最小的证明机器只有三步——押注、出题、作答——它成立的全部理由是那个单向函数「可加」；而一轮问答能买到多少可靠性，只取决于题目有多少种可能，这个数决定了一个协议是能用还是只能上教科书。

下一章问一个看起来很哲学的问题：Peggy 通过了验证，凭什么说她「知道」 x？也许她只是运气好，也许她有别的办法算出 s。答案是一个非常具体、非常暴力的东西：如果她能对两个不同的挑战都答对，我就能当场把她的私钥算出来。本机实测，一行除法，和真私钥逐位相同——而索尼 PlayStation 3 的签名系统就是死在这上面。