08 把裁判换成一台哈希

◻ 本章先赊三条

第一条。随机性并不需要来自「一个诚实的人」。它只需要满足两条：证明者事先不可预测，且所有人事后都能复算。哈希函数正好同时具备。 第二条。你每天在用的数字签名，就是这样一份非交互零知识证明。这不是类比，是同一份东西的两个名字。 第三条。这一招不是白拿的。它换掉了上一章那条「不可转移性」，还引进了一个没法在标准假设下证明的模型——而第 9 章会展示这个模型被误用时的后果。

那个挑战到底需要什么

回头看第 5 章那三步。Victor 抛出的那个 c，为什么必须由他来抛？

不是因为他人品好，而是因为要保证两件事：

(1) 证明者在交出 R 的那一刻，不知道 c 会是什么。
        —— 否则他就能倒推 R，通过率 100%（第 4、7 章）。

(2) 验证者能确认这个 c 不是证明者自己挑的。
        —— 否则证明者当然会挑一个对自己有利的。

「一个诚实的人现场抛骰子」只是满足这两条的一种方式。还有别的方式吗？

有。找一个函数，它把已经被钉死的那些东西映射成一个数，并且这个函数的输出看起来完全随机、事先无法预测。哈希函数正好就是这个东西。

◆ Fiat–Shamir 变换

原来：  c ← 验证者随机抛出

现在：  c ← H( 陈述 ‖ 承诺 ‖ 上下文 )
        也就是 c = H(P ‖ R ‖ 消息)

为什么这满足条件 (1)？因为 R 是哈希的输入。证明者想让 c 变成他想要的值，就得改 R；而一改 R，c 立刻又变了。他被自己咬住了尾巴——这正是哈希函数「不可预测」的含义。

为什么满足条件 (2)？因为验证者拿到 (R, s) 之后自己算一遍 H 就知道 c 是多少。没有讨价还价的余地。

三步变成了这样：

证明者（一个人在家）
    1. 随机取 k，算 R = k·G
    2. 自己算 c = H(P ‖ R ‖ 消息)
    3. 算 s = k + c·x
    输出：证明 = (R, s)          ← 两个数，没有 c，因为 c 谁都能自己算

验证者（任何人，任何时候）
    1. 自己算 c = H(P ‖ R ‖ 消息)
    2. 检查 s·G == R + c·P

来回次数：0

于是它就是签名

把上面那段协议里的「消息」当成你要签的那份文件，看看得到了什么：

零知识的说法	签名的说法
陈述：P = x·G	公钥
见证：⟦ x ⟧	私钥
证明 (R, s)	签名，64 字节
挑战 c = H(P ‖ R ‖ 消息)	把消息绑进证明的那一步
「我知道 P 的离散对数，而且我看过这条消息」	「这份文件是我签的」

数字签名就是一份非交互零知识知识证明。这不是一个类比——Schnorr 签名（比特币 2021 年 Taproot 升级引入的 BIP-340）的定义，就是把第 5 章那个协议做一次 Fiat–Shamir 变换，一个字都不多。

这件事值得停下来想一想。你这辈子已经生成过成千上万份零知识证明了：每一次 git push、每一次 HTTPS 握手、每一次刷卡、每一次手机解锁。这个领域最难懂的名词，早就装在你每天用的东西里。

一个 Schnorr 签名 = R 的 x 坐标 ‖ s = 32 + 32 = 64 字节
交互式要几个来回 / 非交互要几个        3 步 2 个来回 / 0 个

✎ 术语正名

这一招要「安全」，需要一个叫随机预言机模型（Random Oracle Model, ROM）的假设：假装那个哈希函数是一个真正的随机函数——它对每一个新输入都独立均匀地吐出一个随机值，除了查询它没有别的办法知道输出。

问题是：SHA-256 不是随机预言机。它是一段确定的、几百行的代码，任何人都能读。存在一些人造的协议，它们在随机预言机模型下可证明安全，而把预言机换成任何具体的哈希函数之后都不安全（Canetti–Goldreich–Halevi 1998）。

所以工业界的处境是：这个模型在理论上被证明不严谨，在实践中三十多年没出过因它本身而起的事故。大家一边用一边知道自己在赌什么——这是密码学里很典型的一种状态，值得记住它的形状。

付出的三样东西

这一招看起来是白拿的，其实付了三笔账：

付出	说明
多了一个假设	随机预言机模型。它比「离散对数难解」这种假设弱得多，也脏得多。
可否认性没了	上一章那份「谁都能伪造、所以不能当证据」的记录，现在变成了全世界都能验、而且只有你能造的文件。这正是签名需要的性质，但它意味着你再也不能否认。同一个变换，在合同场景是优点，在聊天场景是灾难。
「塞什么进哈希」变成了安全边界	交互式协议里，挑战是外面来的，证明者碰不到。现在挑战是他自己算的，哈希的输入列表就成了唯一的防线。少放一样东西，整条防线就断。下一章整章讲这件事。

第二行有一个具体的现实后果值得单独说：为什么 Signal 不用普通签名认证消息。如果它用了，那么你的每一条消息都带着一份「全世界可验证、且只有你能生成」的证据——截图可以造假，但签名不能。Signal 选择用一种双方都能伪造的认证方式，就是为了保住上一章那个「可否认」。这是一次明确的、把安全性换成可否认性的设计决策。

⌨ 自己跑一遍

把交互式的三步舞变成非交互，只需要动一行。下面是完整的、可运行的对照：

import hashlib, random

p, q, g = 2039, 1019, pow(3, 2, 2039)
x = random.randrange(1, q)                 # ⟦ 私钥 ⟧
P = pow(g, x, p)

def H(*parts):                             # 把一堆东西哈希成一个挑战
    s = '|'.join(str(v) for v in parts).encode()
    return int.from_bytes(hashlib.sha256(s).digest(), 'big') % q

# ---------- 非交互证明（证明者一个人做完） ----------
def prove(msg):
    k = random.randrange(1, q)
    R = pow(g, k, p)
    c = H(P, R, msg)                       # ← 这一行代替了「验证者抛骰子」
    s = (k + c * x) % q
    return (R, s)                          # 证明只有两个数

# ---------- 验证（任何人，任何时候） ----------
def verify(msg, proof):
    R, s = proof
    c = H(P, R, msg)                       # 自己把挑战算一遍
    return pow(g, s, p) == R * pow(P, c, p) % p

pf = prove('转账 100 元给 Bob')
print('证明 =', pf)
print('验证通过：', verify('转账 100 元给 Bob', pf))
print('换一条消息再验：', verify('转账 10000 元给 Mallory', pf))   # False

证明 = (517, 431)        # 两个数就是全部证明；每次跑都不同
验证通过： True
换一条消息再验： False

最后那行是重点：消息进了哈希，所以证明和这条消息绑死了。换任何一个字，c 就变了，等式立刻不成立。这就是「签名绑定消息」的全部机制。

现在做一个实验，它会直接引出下一章：把 H(P, R, msg) 改成 H(R)，再跑一遍。你会发现两次验证仍然全部通过——包括那条你没签过的转账消息。只是删掉了哈希里的两个参数，这份签名就不再绑定任何东西了。

python3 -c " import hashlib H=lambda *a: int.from_bytes(hashlib.sha256('|'.join(map(str,a)).encode()).digest(),'big')%1019 print(H(7,1583,'hi'), H(7,1583,'ho'))"

在线跑：python.org/shell。上面那行显示：输入改一个字符，挑战就完全变了。

▸ 在现实里

比特币的 BIP-340（2021 年 Taproot）。它的规范里，挑战定义为 H(R.x ‖ P.x ‖ 消息)——三样东西全部塞进去，一样不少。这不是偶然，是三十年踩坑的结果。
以太坊上的每一个 zk-rollup。要把证明放上链，它必须是非交互的：证明者在链下生成，合约在链上验，中间不可能有来回问答。没有 Fiat–Shamir，就没有 rollup。
工作量证明也是同一个结构的亲戚。矿工要找一个 nonce 使 H(区块头 ‖ nonce) 足够小。这里哈希扮演的同样是「谁都无法预测、谁都能复算的裁判」。「用哈希代替一个可信第三方」是这三十年里被反复使用的同一个动作。
可验证随机函数（VRF）。Algorand、Cardano 这类链用它来抽签决定谁出块：每个节点用自己的私钥算一个「随机数 + 证明」，别人能验但事先谁也预测不了。这就是把 Fiat–Shamir 反过来用——那里要的不是「证明」，就是那个随机数本身。
反面：抽奖、游戏爆率、AB 分流。只要「随机数由一方生成、另一方无法核对」，这一方就有作弊空间。把随机数改成 H(公开的种子 ‖ 用户 ID)，任何人都能事后复算——这是把这一章那招搬到日常工程里最直接的用法，成本几乎为零。

✗ 这个直觉是错的

「既然挑战是证明者自己算出来的，那他多试几次不就行了？一直换 k，直到算出一个他喜欢的 c 为止。」

他确实可以一直试——这叫重放攻击（grinding），而且它是一个真实的攻击手段，不是理论担忧。但它的成本是这样的：他每试一次，只能得到一个均匀随机的 c。如果他需要撞上某个特定的 c，期望要试 2²⁵⁶ 次。

危险的情况是挑战空间小的时候。假设某个系统的挑战只有 2²⁰ 种可能，那么试一百万次就能撞上想要的那个——在一台笔记本上是几秒钟的事。所以非交互协议的挑战必须足够宽，而这正是「抽查路线」要付的一笔额外的账：第 11 章那种一轮只买 3 比特的协议，要抽三四十次才够，而且必须防止证明者靠重试来挑一组对自己有利的抽查位置。

判据是：看到一个非交互证明系统，问「证明者重试一次的成本是多少、他需要重试多少次才能得到想要的挑战」。这两个数的比值就是它的实际安全裕度，而它常常比宣称的比特数低。真实系统会因此刻意提高抽查次数——多花的那几 KB 证明大小，买的就是这个裕度。

✓ 结账

第一条「随机性不必来自诚实的人」——付清了：它只需要「证明者不可预测 + 所有人可复算」，哈希两条都满足。来回次数 2 → 0。 第二条「签名就是证明」——付清了：一张对照表逐行对上，Schnorr 签名 64 字节就是第 5 章那个协议做一次 Fiat–Shamir。 第三条「不是白拿的」——付了两笔：多了随机预言机假设，丢了可否认性。第三笔账在下一章：哈希的输入列表成了唯一的防线。

这一章的一句话

那个必须在场抛骰子的裁判，可以被一台「谁都能复算、谁都无法预测」的哈希函数整个替换掉；代价是多了一个不干净的假设、丢了可否认性，以及从此以后「往哈希里塞了什么」就是这个系统的全部安全边界。

下一章我们把那条边界踩断。做法是删掉哈希输入里的一个参数——就一个，而且是那个看起来最无关紧要的。然后我拿 Alice 一份完全合法的证明，当场改出一份针对另一个公钥的合法证明，而我并不知道那个公钥的私钥。本机实测：弱版验证器 100% 接受，强版验证器当场拒绝。这个漏洞在 2022 年有一个正式的名字，它同时命中了好几个主流零知识库。