区块链原理 / 系统课时
用 Fiat-Shamir 消除交互轮次
用 Fiat-Shamir 消除交互轮次
交互式零知识证明通常要求验证者现场生成随机挑战,这使证明生成依赖双方通信。Fiat-Shamir 变换利用密码学哈希函数从证明上下文和承诺中生成挑战,让证明者独立生成证明、验证者事后重算挑战,从而减少通信轮次。本文通过 Schnorr 协议理解转换过程,并掌握上下文绑定、域分离和安全假设。
学习目标
- 说明 Fiat-Shamir 变换如何将公开随机挑战替换为哈希挑战。
- 使用一个可计算的 Schnorr 示例完成证明生成与验证。
- 判断上下文绑定、域分离和随机预言机模型分别解决什么问题。
从交互式 Schnorr 协议理解问题
设 是阶为素数 的循环群, 是生成元。证明者持有秘密 ,公开值为 ,目标是证明自己知道 ,但不公开它。
经典 Schnorr 知识证明包含三个消息:
- 证明者随机选择 ,发送承诺 。
- 验证者独立随机选择挑战 ,发送给证明者。
- 证明者返回响应 ,验证者检查 。
验证等式成立,是因为 。但这一等式成立本身不等于知识证明成立;安全性还依赖挑战不可由证明者提前控制,以及离散对数等协议假设。

这里的交互成本不是验证等式本身,而是必须等待验证者返回挑战。对于链上验证、异步证明提交和离线生成证明,这一往返通信并不方便。
用哈希替代验证者挑战
Fiat-Shamir 变换将验证者生成挑战的步骤,替换为双方能够独立计算的确定性规则:
其中 是密码学哈希函数, 表示无歧义的字节编码。实践中通常先将哈希输出解释为非负整数,再按协议规定映射到挑战空间;直接取模只是便于理解的方案,可能产生轻微分布偏差,严格要求均匀分布时可采用拒绝采样。
转换后的证明生成过程如下:
- 证明者选择随机数 ,计算承诺 。
- 证明者对协议上下文、公开陈述 和承诺 计算哈希,得到挑战 。
- 证明者计算 ,输出证明 。
- 验证者读取 ,使用相同规则重新计算 ,检查 。
验证者不需要相信证明者声称的挑战值,也不必事先参与通信。只有公开输入、编码规则与哈希算法完全一致,双方才会得到相同挑战。
用小规模数字验证转换结果
为了手算,取素数模数 ,群的阶 ,生成元 。因为 且 ,所以 在模 23 乘法群中生成一个阶为 11 的子群。
设秘密 ,公开值 。本次随机选择 ,因此 。
以下 Python 3 示例将 SHA-256 挑战与验证过程放在同一程序中。编码使用固定宽度整数,并包含协议标识与公开值,避免简单拼接造成歧义。
import hashlib
p, q, g = 23, 11, 2
x, r = 3, 4
y = pow(g, x, p)
R = pow(g, r, p)
# 教学示例:协议域、公开陈述和承诺全部参与挑战生成。
def challenge(public_y: int, commitment: int) -> int:
message = (b"schnorr-fs-demo-v1"
+ public_y.to_bytes(2, "big")
+ commitment.to_bytes(2, "big"))
digest = hashlib.sha256(message).digest()
return int.from_bytes(digest, "big") % q
c = challenge(y, R)
s = (r + c * x) % q
# 验证者独立重算挑战,而不接收证明者提供的 c。
verified = (pow(g, s, p) ==
(R * pow(y, challenge(y, R), p)) % p)
print(f"public_y={y}, commitment={R}")
print(f"challenge={c}, response={s}")
print(f"verified={verified}")预期结果:第一行固定为 public_y=8, commitment=16,第二行给出由实际 SHA-256 计算得到的挑战与响应,第三行如下。
verified=True这段程序适合验证协议计算关系,但不能用于真实资产或生产证明系统:23 是极小模数,秘密与随机数固定,挑战采用直接取模,且没有实现公开输入检查或规范化证明格式。真实 Schnorr 实现应使用经过审查的群、密码学安全随机数和规范的编码与挑战生成方法。
上下文绑定与域分离
如果挑战只计算 ,那么证明没有绑定它究竟证明哪个公开陈述,也没有绑定应用场景。不同协议可能对相同承诺生成相同挑战,给跨协议复用和上下文混淆留下空间。
实际系统应明确挑战绑定范围:
| 绑定内容 | 示例 | 防止的问题 |
|---|---|---|
| 协议域标识 | schnorr-proof-v1 |
不同证明协议意外共享挑战空间 |
| 公开陈述 | 公钥 | 挑战未关联当前证明目标 |
| 承诺消息 | 挑战未关联本轮承诺 | |
| 应用上下文 | 合约地址、链 ID、业务操作 | 不同使用场景中的证明被直接复用 |
表中最后一项是否必须包含,取决于业务安全目标。例如,同一证明要允许跨链验证,就不能随意把某条链的 ID 固定进协议;如果要求证明仅对特定合约有效,则应绑定相应的链和合约标识。
域分离通常通过唯一协议标签实现,但不能仅靠在可变长度字段之间添加短字符串。推荐采用定长编码或带长度前缀的编码,例如依次编码标签长度、标签、公开值长度、公开值和承诺,避免不同字段组合得到同一字节序列。
随机预言机模型与安全边界
Fiat-Shamir 的安全论证通常在随机预言机模型(Random Oracle Model,ROM)中进行。该模型把哈希函数抽象为一个对新输入返回独立随机结果、对重复输入返回一致结果的理想预言机。
这个假设让安全证明能够分析攻击者如何查询挑战,以及如何从成功伪造证明的攻击行为中构造对底层困难问题的攻击。但现实中的 SHA-256 是确定性算法,不是真正的随机预言机。因此,在 ROM 中证明安全,不等于对任意真实哈希函数都自动获得相同保证。
还需区分三个容易混淆的结论:
- 非交互性:证明者不再等待验证者的在线随机消息,能够一次性提交证明。
- 知识可靠性:是否能从成功证明中论证证明者知道秘密,需要原协议性质、挑战空间和 Fiat-Shamir 安全条件支持。
- 零知识性:证明是否泄露秘密,需要单独分析模拟能力及相应的模型假设,不能仅凭挑战来自哈希就得出结论。
对于多轮证明协议,不能简单把每轮挑战全部计算成同一个哈希值。通常需要将此前产生的公开消息按确定顺序吸收到 transcript(协议记录)中,再派生下一轮挑战。实际工程还应检查挑战长度、字段编码、证明版本和协议所要求的随机预言机模型。
链上验证时怎样使用
链上验证器最适合承担确定性工作:读取公开输入和证明,重建挑战,然后检查证明关系。采用 Fiat-Shamir 后,证明者可以在链下完成随机取样与响应计算,合约无需在线发送挑战,也无需保存交互会话。
以一个应用级 Schnorr 知识证明为例,最小验收规则是:
- 合约固定群参数、挑战派生算法和编码格式,检查群元素及响应的合法范围。
- 证明者按协议生成 ,将业务上下文以及需要的防重放字段纳入挑战。
- 验证器基于公开输入重算挑战,验证等式;任何绑定字段发生改变,都必须重新验证。
- 测试正确证明、被篡改的 、被篡改的 、错误公开值与错误上下文,确认只有合法证明通过。
在 SNARK 或其他复杂证明系统中,同样会用哈希 transcript 生成挑战,但具体轮次、代数关系及安全证明与 Schnorr 不同,不能直接照搬这套验证等式。
Fiat-Shamir 消除的是在线挑战交互,不是证明所需的代数运算或安全检查。只有将全部必要的公开消息和应用上下文准确绑定到哈希挑战,并满足所用证明协议的安全条件,非交互式证明才适合在链下生成、链上验证。