ZK 定义 — 完备性、可靠性、零知识

日期: 2026-11-26 方向: 零知识证明 / ZK理论 阶段: Phase 4 - ZK基础理论 (Day 209-222) 标签: #ZK #SNARK #定义 #模拟器 #GMW

---

今日目标

---

一、为什么需要零知识？

1.1 直觉问题

考虑场景：Alice 想向 Bob 证明她知道某个秘密 $w$（例如某哈希的原像、某 Merkle 树的成员、某 ECDSA 私钥），但不想泄露 $w$ 本身。

朴素方案的失败：

• 直接发送 $w$：泄露
• 发送 $H(w)$：Bob 无法验证 $w$ 的"知识"（除非 $H$ 可被预先承诺）
• 加密后发送：Bob 仍可解密

ZK 的革命性：存在协议使得 Bob 在结束时只学到一个比特——即 "Alice 知道 $w$"——而对 $w$ 自身一无所知。

1.2 真实应用对应

---

二、形式化定义（GMR 1985 / GMW 1991）

2.1 交互式证明系统 (Interactive Proof System, IP)

设 $L \subseteq {0,1}^*$ 是一个语言（NP 语言或更广），$x$ 是输入。

定义：交互式证明系统 $(P, V)$ 由两个图灵机组成：

• Prover $P$：计算无界（或多项式时间，取决于场景）
• Verifier $V$：概率多项式时间（PPT）

二者通过若干轮消息交互，最终 $V$ 输出 ${0, 1}$（接受/拒绝）。记交互产生的 transcript 为 $\langle P, V \rangle(x)$，记 $V$ 的最终输出为 $\text{out}_V \langle P, V \rangle(x)$。

2.2 三大性质

(1) 完备性 (Completeness)：诚实证明者能让诚实验证者接受。

$$ \forall x \in L,\quad \Pr[\text{out}_V \langle P, V \rangle(x) = 1] \geq 1 - \text{negl}(|x|) $$

通常要求 $\Pr = 1$（perfect completeness）。

(2) 可靠性 (Soundness)：作弊证明者无法让验证者接受错误陈述。

$$ \forall x \notin L,\ \forall P^* \text{(任意策略)},\quad \Pr[\text{out}_V \langle P^*, V \rangle(x) = 1] \leq \text{negl}(|x|) $$

这里 $P^*$ 可以是计算无界的（统计可靠）或仅 PPT（计算可靠，对应 SNARK 的 "argument"）。

(3) 零知识 (Zero-Knowledge)：验证者从协议中学不到 "$x \in L$" 之外的信息。

形式化用 模拟器范式 (simulation paradigm)：

存在 PPT 模拟器 $S$，对任意 PPT 验证者 $V^*$，

$$ {S^{V^}(x)}{x \in L} \stackrel{c}{\approx} {\text{view}{V^}\langle P, V^*\rangle(x)}_{x \in L} $$

其中 $\text{view}_{V^}$ 是 $V^$ 在真实交互中看到的所有内容（自身随机币 + 收到的消息）。

零知识强度（由强到弱）：

• Perfect ZK：两个分布完全相同
• Statistical ZK：统计距离 negl
• Computational ZK：计算上不可区分（实际系统通常是这种）

2.3 知识证明 (Proof of Knowledge, PoK)

可靠性只保证 "$x \in L$"，但不保证证明者知道 witness $w$。PoK 加强为：

存在 PPT 抽取器 (extractor) $E$，对任意 $P^$，若 $\Pr[\text{out}_V\langle P^, V\rangle(x) = 1] \geq \epsilon$，则

$$ \Pr[E^{P^*}(x) \text{ 输出有效 witness } w] \geq \text{poly}(\epsilon, 1/|x|) $$

抽取器可访问 $P^*$ 作为黑盒（rewind oracle），通过倒带提取 $w$。

---

三、模拟器构造直觉

3.1 为什么模拟器证明 ZK？

核心论证：如果 $V^*$ 能在真实交互中"学到 $w$"，那么模拟器（无 $w$）就能伪造一份等同的视图，矛盾。

模拟器的"超能力"：可以倒带 (rewind) $V^*$，可以选择性看到 challenge 后再决定 commitment（在交互式 ZK 中）。这使得它能在不知道 $w$ 的情况下生成"长得对的" transcript。

3.2 三种模拟策略

---

四、Honest-Verifier ZK vs Full ZK

4.1 HVZK

仅要求 challenge 是诚实分布（均匀随机）时存在模拟器。Schnorr 直接是 HVZK。

4.2 升级为 Full ZK

• Fiat-Shamir：challenge = $H(\text{transcript})$，强制"诚实分布"
• Coin-flipping protocol：双方共同生成 challenge

---

五、代码 — Language Membership 简化模拟

"""
zk_intro.py
模拟一个微型 IP/ZK 协议: 证明 "x 是二次剩余 (QR mod n)"
不进行真实密码运算, 仅演示完备性/可靠性/ZK 三个性质的统计验证。
"""
import random
from math import gcd

def is_qr(x, n):
    """穷举判断 x 是否是 QR mod n (仅用于小 n 教学)"""
    return any((r * r) % n == x % n for r in range(1, n))

def find_witness(x, n):
    for r in range(1, n):
        if (r * r) % n == x % n:
            return r
    return None

# 简化 Σ-协议: 证明知道 r s.t. r^2 = x mod n
def prover_round1(x, n, w):
    s = random.randrange(1, n)
    while gcd(s, n) != 1:
        s = random.randrange(1, n)
    a = (s * s) % n
    return s, a  # 私有 s, 公开 a

def verifier_challenge():
    return random.randint(0, 1)

def prover_round3(s, w, c, n):
    if c == 0:
        return s
    else:
        return (s * w) % n

def verifier_check(x, n, a, c, z):
    if c == 0:
        return (z * z) % n == a
    else:
        return (z * z) % n == (a * x) % n

# 模拟器 (无 w 仍能生成有效 transcript)
def simulator(x, n):
    c = random.randint(0, 1)
    z = random.randrange(1, n)
    while gcd(z, n) != 1:
        z = random.randrange(1, n)
    if c == 0:
        a = (z * z) % n
    else:
        # need a s.t. z^2 = a*x mod n => a = z^2 * x^{-1}
        x_inv = pow(x, -1, n)
        a = (z * z * x_inv) % n
    return (a, c, z)

if __name__ == "__main__":
    n = 77  # 7 * 11
    w = 5
    x = (w * w) % n  # x = 25
    print(f"x={x}, w={w}, n={n}")

    # 完备性
    accept = 0
    for _ in range(1000):
        s, a = prover_round1(x, n, w)
        c = verifier_challenge()
        z = prover_round3(s, w, c, n)
        if verifier_check(x, n, a, c, z):
            accept += 1
    print(f"Completeness (should be 1000/1000): {accept}/1000")

    # 可靠性: 作弊 prover (不知道 w) 通过率应 ~50% (单轮)
    accept = 0
    for _ in range(1000):
        s, a = prover_round1(x, n, 1)  # 用错误 w=1 (其实 1^2=1 != 25)
        c = verifier_challenge()
        z = prover_round3(s, 1, c, n)  # 用错误 w
        if verifier_check(x, n, a, c, z):
            accept += 1
    print(f"Soundness (cheating, ~500/1000 single-round): {accept}/1000")
    # 注: k 轮重复后作弊概率为 2^{-k}

    # 零知识: 模拟器分布
    sim_transcripts = [simulator(x, n) for _ in range(5)]
    print("Simulator transcripts:", sim_transcripts[:3])

---

六、协议关键步骤图

Prover (knows w)                       Verifier
       |                                  |
       |--------- commitment a --------->|
       |                                  |
       |<-------- challenge c ------------|
       |                                  |
       |--------- response z ------------>|
       |                                  |
                                       check(a, c, z, x)
                                       output 0/1

Special soundness：从两个有效 transcripts $(a, c_1, z_1), (a, c_2, z_2)$（$c_1 \neq c_2$）可抽取 witness $w$。这是 PoK 的核心。

---

七、历史与论文

经典 quote (Goldreich)：

"ZK is a paradigm in which one party convinces another of an assertion while revealing nothing beyond the assertion's validity."

---

八、应用对应

---

九、常见陷阱

1. 混淆 IP 和 ZK：IP 只要求完备+可靠；ZK 多一个 "verifier 学不到东西"
2. HVZK ≠ ZK：HVZK 仅对诚实 verifier，恶意 verifier 可能学到额外信息
3. Soundness vs Knowledge soundness：前者只保证 $x \in L$，后者保证 prover 真"知道"
4. Computational vs Statistical ZK：实际系统几乎都是 computational（依赖密码假设）
5. CRS 信任假设：Groth16 等需要可信 setup，setup 失败则 soundness/ZK 都可能崩

---

十、关键速查

---

十一、面试题

Q1: 完备性、可靠性、零知识三个性质的形式化定义？为什么 ZK 用模拟器范式？

A1: Completeness: $x\in L$ 时诚实 prover 让诚实 verifier 以接近 1 概率接受；Soundness: $x\notin L$ 时任何 cheating prover 的接受概率 negl；ZK: 存在 PPT 模拟器 $S$ 输出与真实 view 不可区分的分布。模拟器范式因为它反证：若 $V^*$ 学到了 $w$，则 $S$（无 $w$）也能伪造，矛盾。

Q2: Proof vs Argument 的区别？SNARK 是哪种？

A2: Proof 抵御计算无界 prover；Argument 仅抵御 PPT prover。SNARK = Succinct Non-interactive Argument of Knowledge，因为 succinct（proof 大小 < witness 大小）只能通过密码假设实现，因此只对计算受限对手安全。

Q3: Statistical ZK 和 Computational ZK 实际差别？

A3: Statistical: 即使无限计算的 verifier 也学不到额外信息；Computational: 仅对 PPT verifier 不可区分。前者更强但通常需要更弱的语言（如 graph isomorphism）；后者依赖密码假设但能覆盖所有 NP。

Q4: HVZK 在实际系统中够用吗？

A4: 仅当能保证 challenge 真随机时够用（例如 Fiat-Shamir 后 challenge 由随机预言机产生）。原始 Σ-协议是 HVZK，恶意 verifier 可能选 biased challenge 学到信息——所以实践中要么用 FS，要么加 OR-proof / commitment 升级到 Full ZK。

Q5: PoK extractor 与 soundness extractor 的区别？

A5: Soundness 只需证 "$x \in L$"，extractor 不必给出具体 witness；PoK 要求 extractor 真正输出 witness $w$ 满足 $R(x, w) = 1$。SNARK 都需要 knowledge soundness（不然没法做 zk-rollup 的合法性证明）。

---

十二、明日预告

Day 210 — Schnorr Σ-协议：实现完整 3 轮 ID protocol，用 special soundness 证 PoK，rewinding simulator 证 HVZK。这是所有现代 NIZK 的基本构件。