区块链原理 / 系统课时

用 Fiat-Shamir 消除交互轮次

用 Fiat-Shamir 消除交互轮次

交互式零知识证明通常要求验证者现场生成随机挑战,这使证明生成依赖双方通信。Fiat-Shamir 变换利用密码学哈希函数从证明上下文和承诺中生成挑战,让证明者独立生成证明、验证者事后重算挑战,从而减少通信轮次。本文通过 Schnorr 协议理解转换过程,并掌握上下文绑定、域分离和安全假设。

学习目标

  • 说明 Fiat-Shamir 变换如何将公开随机挑战替换为哈希挑战。
  • 使用一个可计算的 Schnorr 示例完成证明生成与验证。
  • 判断上下文绑定、域分离和随机预言机模型分别解决什么问题。

从交互式 Schnorr 协议理解问题

设 GG 是阶为素数 qq 的循环群,gg 是生成元。证明者持有秘密 xx,公开值为 y=gxy=g^x,目标是证明自己知道 xx,但不公开它。

经典 Schnorr 知识证明包含三个消息:

  1. 证明者随机选择 r∈Zqr\in\mathbb{Z}_q,发送承诺 R=grR=g^r。
  2. 验证者独立随机选择挑战 c∈Zqc\in\mathbb{Z}_q,发送给证明者。
  3. 证明者返回响应 s=(r+cx) mod qs=(r+cx)\bmod q,验证者检查 gs=R⋅ycg^s=R\cdot y^c。

验证等式成立,是因为 gr+cx=gr(gx)cg^{r+cx}=g^r(g^x)^c。但这一等式成立本身不等于知识证明成立;安全性还依赖挑战不可由证明者提前控制,以及离散对数等协议假设。

交互式 Schnorr 与 Fiat-Shamir 非交互式流程对比

这里的交互成本不是验证等式本身,而是必须等待验证者返回挑战。对于链上验证、异步证明提交和离线生成证明,这一往返通信并不方便。

用哈希替代验证者挑战

Fiat-Shamir 变换将验证者生成挑战的步骤,替换为双方能够独立计算的确定性规则:

c=H(encode⁡(context,y,R)) mod qc=H(\operatorname{encode}(\text{context},y,R))\bmod q

其中 HH 是密码学哈希函数,encode⁡\operatorname{encode} 表示无歧义的字节编码。实践中通常先将哈希输出解释为非负整数,再按协议规定映射到挑战空间;直接取模只是便于理解的方案,可能产生轻微分布偏差,严格要求均匀分布时可采用拒绝采样。

转换后的证明生成过程如下:

  1. 证明者选择随机数 rr,计算承诺 R=grR=g^r。
  2. 证明者对协议上下文、公开陈述 yy 和承诺 RR 计算哈希,得到挑战 cc。
  3. 证明者计算 s=(r+cx) mod qs=(r+cx)\bmod q,输出证明 π=(R,s)\pi=(R,s)。
  4. 验证者读取 π\pi,使用相同规则重新计算 cc,检查 gs=R⋅ycg^s=R\cdot y^c。

验证者不需要相信证明者声称的挑战值,也不必事先参与通信。只有公开输入、编码规则与哈希算法完全一致,双方才会得到相同挑战。

用小规模数字验证转换结果

为了手算,取素数模数 p=23p=23,群的阶 q=11q=11,生成元 g=2g=2。因为 211 mod 23=12^{11}\bmod23=1 且 2≠12\ne1,所以 gg 在模 23 乘法群中生成一个阶为 11 的子群。

设秘密 x=3x=3,公开值 y=23 mod 23=8y=2^3\bmod23=8。本次随机选择 r=4r=4,因此 R=24 mod 23=16R=2^4\bmod23=16。

以下 Python 3 示例将 SHA-256 挑战与验证过程放在同一程序中。编码使用固定宽度整数,并包含协议标识与公开值,避免简单拼接造成歧义。

python
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 计算得到的挑战与响应,第三行如下。

text
verified=True

这段程序适合验证协议计算关系,但不能用于真实资产或生产证明系统:23 是极小模数,秘密与随机数固定,挑战采用直接取模,且没有实现公开输入检查或规范化证明格式。真实 Schnorr 实现应使用经过审查的群、密码学安全随机数和规范的编码与挑战生成方法。

上下文绑定与域分离

如果挑战只计算 H(R)H(R),那么证明没有绑定它究竟证明哪个公开陈述,也没有绑定应用场景。不同协议可能对相同承诺生成相同挑战,给跨协议复用和上下文混淆留下空间。

实际系统应明确挑战绑定范围:

绑定内容 示例 防止的问题
协议域标识 schnorr-proof-v1 不同证明协议意外共享挑战空间
公开陈述 公钥 yy 挑战未关联当前证明目标
承诺消息 RR 挑战未关联本轮承诺
应用上下文 合约地址、链 ID、业务操作 不同使用场景中的证明被直接复用

表中最后一项是否必须包含,取决于业务安全目标。例如,同一证明要允许跨链验证,就不能随意把某条链的 ID 固定进协议;如果要求证明仅对特定合约有效,则应绑定相应的链和合约标识。

域分离通常通过唯一协议标签实现,但不能仅靠在可变长度字段之间添加短字符串。推荐采用定长编码或带长度前缀的编码,例如依次编码标签长度、标签、公开值长度、公开值和承诺,避免不同字段组合得到同一字节序列。

随机预言机模型与安全边界

Fiat-Shamir 的安全论证通常在随机预言机模型(Random Oracle Model,ROM)中进行。该模型把哈希函数抽象为一个对新输入返回独立随机结果、对重复输入返回一致结果的理想预言机。

这个假设让安全证明能够分析攻击者如何查询挑战,以及如何从成功伪造证明的攻击行为中构造对底层困难问题的攻击。但现实中的 SHA-256 是确定性算法,不是真正的随机预言机。因此,在 ROM 中证明安全,不等于对任意真实哈希函数都自动获得相同保证。

还需区分三个容易混淆的结论:

  • 非交互性:证明者不再等待验证者的在线随机消息,能够一次性提交证明。
  • 知识可靠性:是否能从成功证明中论证证明者知道秘密,需要原协议性质、挑战空间和 Fiat-Shamir 安全条件支持。
  • 零知识性:证明是否泄露秘密,需要单独分析模拟能力及相应的模型假设,不能仅凭挑战来自哈希就得出结论。

对于多轮证明协议,不能简单把每轮挑战全部计算成同一个哈希值。通常需要将此前产生的公开消息按确定顺序吸收到 transcript(协议记录)中,再派生下一轮挑战。实际工程还应检查挑战长度、字段编码、证明版本和协议所要求的随机预言机模型。

链上验证时怎样使用

链上验证器最适合承担确定性工作:读取公开输入和证明,重建挑战,然后检查证明关系。采用 Fiat-Shamir 后,证明者可以在链下完成随机取样与响应计算,合约无需在线发送挑战,也无需保存交互会话。

以一个应用级 Schnorr 知识证明为例,最小验收规则是:

  1. 合约固定群参数、挑战派生算法和编码格式,检查群元素及响应的合法范围。
  2. 证明者按协议生成 R,sR,s,将业务上下文以及需要的防重放字段纳入挑战。
  3. 验证器基于公开输入重算挑战,验证等式;任何绑定字段发生改变,都必须重新验证。
  4. 测试正确证明、被篡改的 RR、被篡改的 ss、错误公开值与错误上下文,确认只有合法证明通过。

在 SNARK 或其他复杂证明系统中,同样会用哈希 transcript 生成挑战,但具体轮次、代数关系及安全证明与 Schnorr 不同,不能直接照搬这套验证等式。

Fiat-Shamir 消除的是在线挑战交互,不是证明所需的代数运算或安全检查。只有将全部必要的公开消息和应用上下文准确绑定到哈希挑战,并满足所用证明协议的安全条件,非交互式证明才适合在链下生成、链上验证。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用 Fiat-Shamir 消除交互轮次

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通