3.2 Fiat-Shamir：把对话折叠成一条记录

3.2 Fiat-Shamir：把对话折叠成一条记录

本节摘要：Fiat-Shamir 变换用"对承诺做哈希"替代"验证者现场抛骰子"，把多轮交互证明塌缩成单条可任意转交的记录——今天的 Schnorr 签名、多数 SNARK 的非交互化都踩在这块基石上。本节讲清它的机理、随机预言机模型的论证角色，以及三类把变换做坏的真实实现错误。承接 3.1，通往 3.3 的 SNARK 家族。

把验证者的骰子换成哈希

3.1 节把交互式协议的死穴定位在"验证者必须在场"。1986 年，Fiat 与 Shamir 给出一个轻描淡写却改变行业的替代方案：既然挑战的唯一要求是不可预知且不可操纵，那能不能让一个谁都无法左右的函数来充当骰子？哈希函数恰好合适——证明者发出承诺 R 后，自己算 challenge = H(R)，然后照原协议应答。验证者收到三元组 (R, s) 后，重算 H(R) 便知挑战是否被尊重，全程无需证明者在线，记录还能装进信封转交任何人复验。

流程的塌缩过程值得画出来对照：

图：交互协议到非交互记录的折叠

折叠为什么没把可靠性一起折断？关键在顺序。原协议里作弊者的困境是：不知道 x，就得在看到 c 之前先定下 R，然后祈祷 c 落进自己能应付的小集合。折叠之后，c 不再来自验证者的骰子，而是 H(R) 的输出——作弊者若想操控 c，只能反复换 R 去碰哈希输出，这正是 2.1 节讲过的"哈希当骰子"：输出伪随机，猜中目标值只能靠海量试错。理论表述叫随机预言机模型：把哈希理想化为一台真随机函数，再论证变换在该模型下安全。真实哈希当然不是真随机函数，但这套论证方式在四十年的实战检验下依然是可靠的第一道防线。

折叠的直接产物：Schnorr 签名

把折叠后的 Schnorr 三元组加上一段消息 m（进入哈希输入），就得到 Schnorr 签名——折叠最成功的商业落地。下面是完整可跑的玩具实现，签名与验签一目了然：

# Schnorr 签名玩具实现：Fiat-Shamir 折叠的直接产物
import hashlib, secrets
p, g, q = 101, 2, 100                # 玩具参数（真实参数为素数阶群，见 2.1 提醒）

def h_int(*parts: bytes) -> int:     # 确定性骰子：所有材料拼一起哈希
    return int.from_bytes(hashlib.sha256(b"|".join(parts)).digest(), "big") % q

x = 37
y = pow(g, x, p)                     # 公钥

def sign(msg: bytes):
    r = secrets.randbelow(q)         # 随机盲化量，绝对不能复用（1.3 的教训）
    R = pow(g, r, p).to_bytes(8, "big")
    c = h_int(R, msg)                # 挑战由哈希现场生成，验证者不需要在场
    s = (r + c * x) % q
    return R, s

def verify(msg: bytes, R: bytes, s: int) -> bool:
    c = h_int(R, msg)                # 重算同一颗骰子
    lhs = pow(g, s, p)
    rhs = pow(int.from_bytes(R, "big"), 1, p) * pow(y, c, p) % p
    return lhs == rhs

msg_ok = "同意报销单据2026-0091".encode("utf-8")     # 消息按字节参与哈希
msg_bad = "同意报销单据2026-0092".encode("utf-8")    # 只改了末位数字的对照消息
sig = sign(msg_ok)
print("验签通过:", verify(msg_ok, *sig))                       # True
print("篡改消息后:", verify(msg_bad, *sig))                    # False
# 想伪造签名？需要找 R 使哈希落进自己能应付的挑战集合，
# 唯一途径是海量枚举 R——成本被难题假设钉死
​

注意消息进入了哈希输入：这正是签名"绑定内容"的机制。篡改一个数字，重算出的挑战立刻对不上应答，验签当场拒绝。

变换做坏的三种方式

Fiat-Shamir 的公式简单到令人大意，实现事故却年年出现。第一类：上下文缺失。哈希输入里漏掉协议名、参数、消息或承诺表，攻击者就能把一份记录搬到另一个语境里重复播放（重放攻击）。修复原则只有一句：哈希进"从协议开始到现在的一切公开材料"，少一项就是漏洞。第二类：可操纵输入。若承诺空间里存在大量取值都能导向"好挑战"（比如某些协议允许证明者塞进可选字段），作弊者可以离线海选这些字段直到挑战落进能应付的子集，这类攻击俗称 grinding。修复办法是把自由度封死：可选字段一并入哈希，或干脆删除可选性。第三类：弱哈希与短输出。挑战空间不够大，作弊者枚举得起——挑战宽度直接决定安全档位，按 128 位安全等级配置输出长度是底线。

三条修法归纳成一个审查动作：拿到任何非交互证明，先找哈希输入清单，逐项问"这一项可被证明者操纵吗？这一项在不同语境下会重复吗？"两问过不了，方案再漂亮也不能收。

过渡：证明小了，仪式来了

折叠解决了"在场"问题，SNARK 家族紧接着解决"尺寸"问题，但那要付出一次性的信任成本。下一节把四张面孔摆上同一张桌子对账。

事故复盘式三问

**问：有没有真实系统因为上下文缺失出过事？**事故模式在多篇公开的密码学实现分析报告里反复出现：跨协议重放（同一签名在两条业务线之间互认）、跨参数重放（换群不换哈希输入）、跨版本重放（升级后旧证明仍可通过）。这些缺陷的共同点是——协议数学本身没错，错在实现把哈希输入裁短了。复盘规程：每次协议升级，把新旧版本的哈希输入清单逐项 diff，多一项少一项都要给出安全理由。

**问：把哈希换成更贵的函数更安全吗？**方向错了。安全来自输入的完备与不可操纵，不来自哈希本身的强度冗余——输入不全，换再贵的哈希也挡不住重放；输入完备，标准哈希就够。把预算花在输入清单审查与测试覆盖上，回报率远高于换函数。

**问：怎么测试 Fiat-Shamir 实现的好坏？**三类用例值得写进持续集成：重放类（同一证明在不同上下文参数下必须被拒）；操纵类（枚举全部可选字段构造"好挑战"，验证存活率与理论一致）；回归类（任何依赖项变更后，历史证明与新证明的挑战分布抽样比对）。三类齐备，Fiat-Shamir 这层才算有护栏。

补充：多轮协议的折叠与域分离

3.2 的例子折叠的是一轮挑战，多轮协议的处理方式值得补一句：每一拍挑战都单独哈希生成，输入包含"从协议开始到该拍为止的全部公开消息序列"——相当于把对话全程逐帧打包进骰子。配套纪律是域分离（domain separation）：不同用途、不同协议、不同版本的哈希调用，在输入里掺入互不相同的标签常量，确保同一输入永远不可能被两个不同语境解释。域分离是防重放的最后一段保险丝，成本为零，漏掉的事故却反复出现——把它写进代码评审清单的第一行。多轮折叠的另一个实用推论：轮数不减少安全性，但折叠后的记录长度与验证成本随轮数线性增长，工程上通常把多轮协议一次性折叠、而非逐轮折叠。

本节要点回顾

• 折叠的本质：把挑战生成从验证者的骰子委托给哈希函数，交互随之消失而不可预知性保留；
• 随机预言机模型是论证的租界：理想化假设换来干净证明，需以实现纪律偿还；
• Schnorr 签名 = 折叠后的三拍，消息必须进哈希，盲化量绝不能复用；
• 三大实现事故源：上下文缺失、可操纵输入、挑战宽度不足——审查从哈希输入清单开始。