Σ-协议 — Schnorr Identification

日期: 2026-11-27 方向: 零知识证明 / ZK理论 阶段: Phase 4 - ZK基础理论 (Day 209-222) 标签: #ZK #Sigma #Schnorr #PoK #ID-protocol

---

今日目标

---

一、Σ-协议形式化

1.1 定义

Σ-协议是一类特殊的 3 轮公共币交互式证明系统，证明 $w$ 满足关系 $R(x, w) = 1$：

Round 1: P → V :  a   (commitment)
Round 2: V → P :  c   (challenge, 均匀随机 ∈ C)
Round 3: P → V :  z   (response)
        V :  Verify(x, a, c, z) ∈ {0, 1}

要求三个性质：

(Σ.1) 完备性：诚实 P 让 V 以概率 1 接受。

(Σ.2) Special Soundness：从两个有效 transcripts $(a, c_1, z_1), (a, c_2, z_2)$（$c_1 \neq c_2$，同一个 $a$），存在 PPT 抽取器输出 witness $w$。

(Σ.3) Special HVZK：存在 PPT 模拟器 $S(x, c) \to (a, z)$ 使 $(a, c, z)$ 与诚实 transcript 同分布（在诚实 challenge $c$ 下）。

注：Special soundness ⇒ knowledge soundness（标准结果）；Special HVZK ⇒ HVZK。

1.2 重复缩短可靠性

单轮 challenge 空间 $|C|$ 有限时，作弊概率 $1/|C|$。重复 $k$ 轮（独立 challenge）后作弊概率 $1/|C|^k$。

实践中 $|C| \geq 2^{128}$（直接用 256-bit challenge），无需重复。

---

二、Schnorr ID 协议（1989）

2.1 设置

公开参数：

• 群 $G$，阶为大素数 $q$，生成元 $g$（如 secp256k1 group）
• 哈希函数 $H$（在 Fiat-Shamir 化时用）

密钥：

• 私钥 $w \in \mathbb{Z}_q$
• 公钥 $h = g^w \in G$

陈述：$\exists w$ s.t. $h = g^w$（即知道 $h$ 的离散对数）。 关系：$R(h, w) = 1 \iff g^w = h$。

2.2 协议

P: r ←$ Z_q       (随机 nonce)
P: a = g^r        (commitment)
P → V: a

V: c ←$ Z_q       (challenge)
V → P: c

P: z = r + c·w mod q  (response)
P → V: z

V: accept iff g^z == a · h^c

2.3 完备性证明

$$ g^z = g^{r + cw} = g^r \cdot (g^w)^c = a \cdot h^c \checkmark $$

2.4 Special Soundness 证明

设两个 accepting transcripts $(a, c_1, z_1)$ 和 $(a, c_2, z_2)$，$c_1 \neq c_2$：

$$ g^{z_1} = a \cdot h^{c_1}, \quad g^{z_2} = a \cdot h^{c_2} $$

相除：

$$ g^{z_1 - z_2} = h^{c_1 - c_2} $$

由 $h = g^w$，得：

$$ z_1 - z_2 \equiv w(c_1 - c_2) \pmod{q} $$

由于 $c_1 \neq c_2$ 且 $q$ 是素数，$c_1 - c_2$ 可逆，于是：

$$ \boxed{w = (z_1 - z_2)(c_1 - c_2)^{-1} \mod q} $$

抽取器算法明确：rewind P，给两次不同 challenge，取两个 $z$，按上式计算 $w$。

2.5 HVZK 模拟器

模拟器 $S(h, c)$：

1. 选 $z \leftarrow_$ \mathbb{Z}_q$
2. 计算 $a = g^z \cdot h^{-c}$
3. 输出 $(a, c, z)$

分布等同性证明：在真实协议中，$r$ 均匀，所以 $a = g^r$ 均匀；在模拟中，$z$ 均匀，所以 $a = g^z h^{-c}$ 也均匀。给定 $(a, c)$，真实协议的 $z$ 由 $z = r + cw$ 决定（$r$ 唯一对应 $a$），所以条件分布也一致。

→ Perfect HVZK。

---

三、为什么 Schnorr 这么"工整"？

3.1 关键代数结构

Schnorr 利用了离散对数群的线性同态：

• $g^{r_1 + r_2} = g^{r_1} \cdot g^{r_2}$
• $(g^r)^c = g^{rc}$

这使得 response $z = r + cw$ 是 $r, w$ 的线性组合，在 verifier 端用幂运算能反查。

3.2 与一般 NP 关系的差距

Schnorr 只能证 DL 关系。一般 NP 关系需要：

• 把电路编码为 R1CS/QAP（Day 212-213）
• 用密码学承诺（KZG/IPA/FRI）证多项式关系
• 或用 GMW 通用编译器（昂贵）

但 Schnorr 是构件——所有 SNARK 内部都用类似 "linear sigma" 的思想。

---

四、代码实现

"""
sigma.py — Schnorr ID Protocol (full implementation)
依赖: Python 3.10+
"""
import secrets
import hashlib

# 简化群: Z_p* 子群, 阶 q | p-1
# 实战可换 secp256k1; 这里用教学参数
P = 0xfffffffffffffffffffffffffffffffeffffffffffffffff  # ~192 bit (toy)
# 取小一点便于演示
P = (1 << 256) - 189  # 256-bit prime (toy)
Q = (P - 1) // 2  # 假设 (P-1)/2 也是素数 (实际要严格选)
G = 5  # 假设是阶 Q 的生成元 (教学)

def mod_inv(a, m):
    return pow(a, -1, m)

class SchnorrProver:
    def __init__(self, w):
        self.w = w % Q
        self.h = pow(G, self.w, P)  # 公钥
        self.r = None

    def commit(self):
        self.r = secrets.randbelow(Q)
        a = pow(G, self.r, P)
        return a

    def respond(self, c):
        z = (self.r + c * self.w) % Q
        return z

class SchnorrVerifier:
    def __init__(self, h):
        self.h = h
        self.a = None

    def challenge(self):
        self.c = secrets.randbelow(Q)
        return self.c

    def verify(self, a, c, z):
        lhs = pow(G, z, P)
        rhs = (a * pow(self.h, c, P)) % P
        return lhs == rhs

def simulator(h, c):
    """HVZK simulator: 在不知 w 的情况下伪造 (a, c, z)"""
    z = secrets.randbelow(Q)
    h_neg_c = pow(h, (-c) % Q, P)
    a = (pow(G, z, P) * h_neg_c) % P
    return a, c, z

def extractor(a, c1, z1, c2, z2):
    """Special soundness extractor: 从两个 transcript 抽 w"""
    assert c1 != c2
    dz = (z1 - z2) % Q
    dc_inv = mod_inv((c1 - c2) % Q, Q)
    w = (dz * dc_inv) % Q
    return w

# ============ 测试 ============
def test_completeness(n=1000):
    w = secrets.randbelow(Q)
    P_obj = SchnorrProver(w)
    V_obj = SchnorrVerifier(P_obj.h)
    accept = 0
    for _ in range(n):
        a = P_obj.commit()
        c = V_obj.challenge()
        z = P_obj.respond(c)
        if V_obj.verify(a, c, z):
            accept += 1
    print(f"[Completeness] {accept}/{n} accepted (expect {n}/{n})")
    assert accept == n

def test_simulator(n=5):
    w = secrets.randbelow(Q)
    h = pow(G, w, P)
    print(f"[Simulator] generated {n} transcripts without knowing w:")
    for _ in range(n):
        c = secrets.randbelow(Q)
        a, c, z = simulator(h, c)
        # 验证 (无 w)
        lhs = pow(G, z, P)
        rhs = (a * pow(h, c, P)) % P
        assert lhs == rhs
        print(f"  a={hex(a)[:20]}... c={hex(c)[:10]}... z={hex(z)[:10]}... [valid]")

def test_extractor():
    w = secrets.randbelow(Q)
    P_obj = SchnorrProver(w)
    h = P_obj.h
    a = P_obj.commit()
    c1 = secrets.randbelow(Q)
    z1 = P_obj.respond(c1)
    # rewind: 重置 r, 但 a 必须相同 (用同一个 r)
    # 注: 真实抽取需要 rewind oracle
    P_obj.r = None  # 模拟; 实际中 extractor 控制 P 的随机带
    P_obj.r = pow(G, 1, 1)  # 错误用法仅示意
    # 简化: 直接构造两个 transcripts (同 a, 同 r)
    r = secrets.randbelow(Q)
    a = pow(G, r, P)
    c1, c2 = secrets.randbelow(Q), secrets.randbelow(Q)
    while c1 == c2:
        c2 = secrets.randbelow(Q)
    z1 = (r + c1 * w) % Q
    z2 = (r + c2 * w) % Q
    w_extracted = extractor(a, c1, z1, c2, z2)
    print(f"[Extractor] true w  = {w}")
    print(f"[Extractor] got  w  = {w_extracted}")
    assert w_extracted == w

if __name__ == "__main__":
    test_completeness()
    test_simulator()
    test_extractor()
    print("All Schnorr tests passed.")

---

五、协议关键步骤图

        Prover (knows w, h=g^w)            Verifier (knows h)
                  |                              |
   r ←$ Z_q       |                              |
   a = g^r        |--------- a -----------> |
                  |                              |
                  |                              |   c ←$ Z_q
                  |<-------- c -------------|
                  |                              |
   z = r+cw mod q |                              |
                  |--------- z -----------> |
                                             check g^z =? a·h^c
                                             output 1/0

---

六、Σ-协议的扩展

OR 关键技巧（CDS 1994）：模拟器替换"真"分支之一，保持总分布不变。

---

七、历史与论文

Schnorr 协议 2008 年才解禁（专利到期），现在是 Bitcoin Taproot、EdDSA 等的基础。

---

八、应用对应

---

九、常见陷阱

1. Nonce 重用 = 私钥泄露：$z_1 - z_2 = (c_1 - c_2)w \Rightarrow w$ 可解，与 Sony PS3 ECDSA 泄露 root key 同理
2. Challenge 必须均匀：HVZK 假设之一；Fiat-Shamir 要哈希所有 transcript（含 $a$）
3. 群阶必须素数：否则可能落入小子群，DL 易解
4. 不要省略 $a$ 输入哈希：Fiat-Shamir 时若 $c = H(x)$ 不含 $a$，则攻击者可后选 $a$
5. 模拟器假设 $c$ 已知：HVZK 不防恶意 verifier，需要 FS 或 commitment 升级

---

十、关键速查

---

十一、面试题

Q1: Schnorr 协议中 nonce $r$ 重用为什么泄露私钥？

A1: 两个签名共享 $r$ 时 $a$ 相同，但 $c_1 \neq c_2$（消息不同 → 哈希不同），由 $z_i = r + c_i w$ 可解 $w = (z_1 - z_2)(c_1 - c_2)^{-1}$。这是 special soundness 抽取器的"双刃剑"。

Q2: 为什么 Schnorr 是 special HVZK 而不是 full ZK？

A2: 模拟器需要先知 $c$ 才能选 $z$ 反推 $a$；恶意 verifier 可能不按均匀分布给 $c$（如根据 $a$ 选）。Fiat-Shamir 后 $c = H(\text{stmt}|a)$ 在 ROM 下相当于均匀，升级为 NIZK。

Q3: special soundness 与 knowledge soundness 的关系？

A3: Special soundness 是充分条件（适用于 3 轮 Σ-protocol）：从 2 个 accepting transcripts 能多项式时间抽 witness。Knowledge soundness 是定义（PoK），允许任意 extractor 设计（含 rewinding、code access）。Special soundness ⇒ knowledge soundness via standard rewinding lemma（Bellare-Goldreich）。

Q4: 如何用 Schnorr 构造 Ring Signature？

A4: OR-Schnorr (CDS): 对真分支正常运行，对 fake 分支用模拟器（先选 $c, z$ 反推 $a$）。Total challenge $C = c_1 + c_2 + ... + c_n$ 由 verifier 提供，prover 调整真分支 $c_{\text{real}} = C - \sum_{i \neq \text{real}} c_i$。

Q5: Schnorr ID vs Schnorr signature 区别？

A5: ID 是交互的（V 给 challenge），signature 是非交互的（$c = H(\text{msg}|a)$，Fiat-Shamir）。ID 用于"我是谁"；signature 绑定消息，用于"我同意此消息"。

---

十二、明日预告

Day 211 — Fiat-Shamir 变换：交互式 → 非交互式，random oracle model 下安全性证明，把 Schnorr ID 转成 Schnorr signature。