Fiat-Shamir 变换 — 交互→非交互

日期: 2026-11-28 方向: 零知识证明 / ZK理论 阶段: Phase 4 - ZK基础理论 (Day 209-222) 标签: #ZK #FiatShamir #ROM #NIZK

---

今日目标

---

一、为什么需要 Fiat-Shamir

1.1 交互式协议的痛

• 链上不能交互（每轮一笔交易，gas 爆炸）
• 离线签名场景需要"一次性"证明
• Snapshot 投票、空投证明等需要可发布的对象

目标：让 prover 自己生成 challenge，但不能"作弊选 challenge"。

1.2 Fiat-Shamir 启发式

把交互式公共币 Σ-协议转非交互式：

原：
    P → V :  a
    V → P :  c ←$ Z_q
    P → V :  z
非交互：
    P 自己计算: c = H(x ‖ a)        ← 用哈希代替 verifier 随机性
    P → V : (a, c, z)  或  (c, z)  (verifier 可重算 c)

哈希 $H$ 当作 random oracle（ROM 假设）：每次新输入返回独立均匀输出。

1.3 关键直觉

• Prover 必须先 commit $a$ 才能查 $H(x | a)$ → 不能"选"自己想要的 challenge
• $H$ 的 unpredictability 替代了 verifier 的真随机性
• 安全性从 interactive HVZK + soundness → NIZK + ZK + EUF-CMA（在 ROM 下）

---

二、ROM 下安全性证明

2.1 Random Oracle Model

ROM 假设：所有参与方（含 adversary）只能通过查询 $H$ 来得到值；reduction 可以"编程" $H$（programming RO）。

虽然 ROM 是启发式（实际哈希不是 RO；CGH 2004 反例），但：

1. ROM 证明仍提供强信心
2. 已知的 ROM-only 反例都是人造的
3. 从 ROM 到标准模型的提升是研究热点（CDH-secure FS for sigma 已知）

2.2 Schnorr signature 安全归约（Forking Lemma, Pointcheval-Stern 1996）

设 $\mathcal{A}$ 是 EUF-CMA forger，能在 $q_h$ 次 RO 查询、$q_s$ 次签名查询后伪造概率 $\epsilon$。

Forking Lemma：存在解 DL 算法 $\mathcal{B}$，期望时间 $O(q_h / \epsilon)$，成功概率 $\Omega(\epsilon^2 / q_h)$。

思路：

1. $\mathcal{B}$ 模拟整个签名预言机和 RO
2. $\mathcal{A}$ 输出 forgery $(m^, (a^, c^, z^))$，其中 $c^* = H(m^* | a^*)$
3. $\mathcal{B}$ rewind 到 $\mathcal{A}$ 查询 $H(m^* | a^)$ 那刻，重新返回另一个 $c^{\prime}$
4. 若 $\mathcal{A}$ 再次输出 forgery $(m^, (a^, c^{\prime}, z^{\prime}))$（同 $a^$，不同 $c$），则用 special soundness 抽 witness $w = (z^ - z^{\prime})(c^ - c^{*\prime})^{-1}$ → 解 DL

→ Schnorr signature 在 ROM 下基于 DL 困难性安全。

2.3 NIZK 性质

变换后的 Schnorr 是 NIZK：

• Soundness：ROM 假设下，从 forging proof 可抽 witness（同 forking lemma）
• ZK：模拟器 program $H$，先选 $c, z$ 算 $a$，再设定 $H(x | a) := c$；这与真实分布不可区分（assumes RO 不被 $\mathcal{A}$ 提前查询，概率 negl）

---

三、Schnorr Signature（FS-Schnorr）

3.1 算法

KeyGen：$w \leftarrow_$ \mathbb{Z}_q$，$h = g^w$

Sign(sk = w, msg = m)：

1. $r \leftarrow_$ \mathbb{Z}_q$
2. $a = g^r$
3. $c = H(m | a)$ 或 $H(h | m | a)$（BIP340 风格）
4. $z = r + c \cdot w \mod q$
5. 输出 $\sigma = (a, z)$ 或 $(c, z)$

Verify(pk = h, msg = m, sigma = (a, z))：

1. $c = H(m | a)$
2. accept iff $g^z \stackrel{?}{=} a \cdot h^c$

3.2 BIP340 (Bitcoin Taproot)

• 64 bytes signature: $(R_x, s)$，其中 $R$ x-only（节省 1 byte）
• $c = H(\text{tag} | R_x | P_x | m)$（域分离）
• 阶 $n$ 为 secp256k1 order

---

四、代码实现

"""
fs.py — Fiat-Shamir Schnorr signature + weak-FS attack demo
"""
import secrets
import hashlib

# Toy parameters (in production: secp256k1)
P = (1 << 256) - 189
Q = (P - 1) // 2  # 假设是素数
G = 5

def H(*args, length=32):
    h = hashlib.sha256()
    for a in args:
        if isinstance(a, int):
            h.update(a.to_bytes(64, "big"))
        else:
            h.update(a)
    return int.from_bytes(h.digest()[:length], "big") % Q

# ---------- 标准 FS-Schnorr ----------
def keygen():
    w = secrets.randbelow(Q - 1) + 1
    h = pow(G, w, P)
    return w, h

def sign(sk_w, pk_h, msg: bytes):
    r = secrets.randbelow(Q - 1) + 1
    a = pow(G, r, P)
    c = H(pk_h, msg, a)             # ← 关键: 包含 pk, msg, a
    z = (r + c * sk_w) % Q
    return (a, z)

def verify(pk_h, msg: bytes, sig):
    a, z = sig
    c = H(pk_h, msg, a)
    return pow(G, z, P) == (a * pow(pk_h, c, P)) % P

# ---------- 弱 FS: 漏掉 a, 漏掉 pk ----------
def sign_weak(sk_w, pk_h, msg: bytes):
    r = secrets.randbelow(Q - 1) + 1
    a = pow(G, r, P)
    c = H(msg)                       # ← 漏: 不含 a, pk
    z = (r + c * sk_w) % Q
    return (a, z)

def verify_weak(pk_h, msg: bytes, sig):
    a, z = sig
    c = H(msg)
    return pow(G, z, P) == (a * pow(pk_h, c, P)) % P

# ---------- 弱 FS 攻击: 任意伪造 ----------
def forge_weak(target_pk, msg: bytes):
    """
    攻击: 因为 c 不依赖 a, 攻击者先选 z, c, 反推 a
    """
    c = H(msg)
    z = secrets.randbelow(Q)
    pk_neg_c = pow(target_pk, (-c) % Q, P)
    a = (pow(G, z, P) * pk_neg_c) % P
    return (a, z)

# ---------- 测试 ----------
def test_correct_fs():
    sk, pk = keygen()
    msg = b"hello FS"
    sig = sign(sk, pk, msg)
    assert verify(pk, msg, sig)
    print(f"[OK] Standard FS-Schnorr verify on '{msg.decode()}'")

def test_weak_fs_attack():
    sk, pk = keygen()
    msg = b"transfer 100 ETH to attacker"
    forged = forge_weak(pk, msg)
    assert verify_weak(pk, msg, forged), "Weak FS should be forgeable!"
    print(f"[!] Weak FS forged signature accepted on '{msg.decode()}'")
    # 标准 FS 应该拒绝同样的伪造
    assert not verify(pk, msg, forged), "Standard FS should reject!"
    print(f"[OK] Standard FS rejects the same forged sig (因为 c 含 a)")

def benchmark():
    import time
    sk, pk = keygen()
    msg = b"x" * 32
    t = time.time()
    for _ in range(100):
        sig = sign(sk, pk, msg)
        assert verify(pk, msg, sig)
    print(f"[Bench] 100 sign+verify: {time.time()-t:.3f}s")

if __name__ == "__main__":
    test_correct_fs()
    test_weak_fs_attack()
    benchmark()

输出预期：

[OK] Standard FS-Schnorr verify on 'hello FS'
[!] Weak FS forged signature accepted on 'transfer 100 ETH to attacker'
[OK] Standard FS rejects the same forged sig (因为 c 含 a)
[Bench] 100 sign+verify: 0.x s

---

五、协议关键步骤图

交互式（原 Σ）

P                                          V
|--------- a ------------------------>|
|<-------- c (V's coin) -------------|
|--------- z ------------------------>|
                                     check g^z == a · h^c

Fiat-Shamir（非交互式）

P 自己:
   r ←$ Z_q
   a = g^r
   c = H(stmt ‖ a)
   z = r + c·w
P → 任何人: (a, z)   ← 一次性发布

Verifier 离线:
   c = H(stmt ‖ a)
   accept iff g^z == a·h^c

---

六、Strong vs Weak Fiat-Shamir

真实事故：

• Frozen Heart attack (2022): PlonK / Spartan / Bulletproofs 多个实现的 weak FS 漏洞，由 TrailOfBits 披露
• 漏 public input 导致 statement 替换
• 漏 commitment 导致 Schnorr 直接被 forge（如 forge_weak）

Lesson：FS 哈希必须 commit 到所有先前的 prover-to-verifier 消息和 statement。

---

七、历史与论文

---

八、应用对应

---

九、常见陷阱

1. Weak FS：哈希不含 statement → 攻击者替换 stmt 不影响 $c$
2. Public input 漏哈希：如 PlonK 公开输入未参与 challenge 派生
3. 域分离遗漏：不同 protocol 用同一 $H$ → cross-protocol attack
4. RO 假设的"自反"：在 RO 模型证安全的协议在 standard model 不一定安全（CGH 反例）
5. 嵌套 FS：递归证明里 inner FS 用了 mismatched challenge derivation → soundness 损失

---

十、关键速查

---

十一、面试题

Q1: Fiat-Shamir 在 Random Oracle Model 下安全的核心论证？

A1: Forking Lemma：若 forger 概率 $\epsilon$，则可通过 rewind 同一 RO 查询点（给不同回答），用 special soundness 抽 witness，期望时间 $O(q_h/\epsilon)$，成功概率 $\Omega(\epsilon^2 / q_h)$。这把 FS 安全性归约到底层 Σ-协议的 special soundness + 底层困难假设（如 DL）。

Q2: Weak FS 攻击的本质？举一个真实漏洞？

A2: 本质：哈希输入未 commit 到所有先前消息（如 statement、commitment）。攻击者可后选 $a$，让 challenge 偏移到攻击者可控点。Frozen Heart attack (2022) 中多个实现 PlonK/Spartan 漏掉某些 public input 进 challenge，导致可伪造证明。

Q3: ROM 反例（CGH 2004）说明什么？

A3: 存在协议在 ROM 下 secure，在任何具体哈希实例下不 secure。说明 ROM 是启发式而非定理。但已知反例都是"人造"的（专为反例构造），实际部署的 FS-NIZK 仍被广泛信任。研究方向是把 FS 提升到 standard model（CDH-based, lattice-based 已有进展）。

Q4: 为什么 Schnorr signature 不需要 message 进 commitment $a$？

A4: $a = g^r$ 与 message 无关；message 通过 challenge $c = H(m | a)$ 进入。这种 "message-independent commitment" 是 Σ-协议的标准结构。BIP340 的 challenge 还包含公钥避免 cross-key forgery。

Q5: 一个 NIZK 系统中，如何检查 FS 实现是否 robust？

A5: (1) 列出所有 prover 状态（statement、public input、所有 commitments、aux randomness）；(2) 检查每个 challenge 是否 commit 到当时可见的全部信息；(3) 检查域分离（每个 challenge 用独立 tag）；(4) 用 fuzzer 注入恶意 commitments，看是否被检测；(5) 对比 reference impl（如 plonky2）的 transcript 顺序。

---

十二、明日预告

Day 212 — 通用 ZK 的电路化：把任意 NP 关系编码为 R1CS，看 $x^2 + x = 12$ 如何变成约束系统，为 Day 213 QAP 做准备。