Zero-knowledge proofs(零知识证明)

注：本文是跟着 CryptoHack 的 Zero Knowledge Proofs 分类学习时整理的知识点，主线就是 Σ-协议（Sigma Protocol） 这一条，从交互式证明一路讲到 Fiat-Shamir 非交互化、OR 复合，题目本身不在这展开。

零知识证明

零知识证明（ZKP）：让证明者 P 向验证者 V 证明”某个陈述为真”，但除了”它为真”之外，不泄露任何额外信息。

ZKP 同时满足三个性质：

• 完备性（Completeness）：陈述为真、P 真知道，诚实的 V 一定接受
• 可靠性（Soundness）：陈述为假、P 不知道，能骗过 V 的概率可忽略
• 零知识性（Zero-Knowledge）：V 验证完，除了”陈述为真”，啥也没多学到

应用方向：身份验证系统、可验证计算（外包算力的结果正确性）、隐私保护区块链。

在cryptohack中，提到了一个很好的例子来解释这个概念：

你需要向那位无法区分颜色的朋友Victor证明：两个形状完全相同的球——一个红色，一个绿色——其实是不同的。但你不能告诉他哪个是红色，哪个是绿色。你需要用一种特定的证明方法来让他相信这一点。你把球拿给他看，由于他无法区分颜色，所以他来测试你。Victor把球藏起来，然后拿出其中一个球，可能会交换它的位置，也可能不交换。你需要判断他是否换了球的位置。重复这个过程足够多次后——比如 50 次——由于你能通过观察颜色来判断是否发生了交换，Victor就会相信这两个球确实是不同的，但他仍然不知道哪个是红色，哪个是绿色。这种证明方式不会透露任何额外信息，因此属于“零知识证明”的典型例子。

整个过程 Victor 没有学到任何”哪个是红哪个是绿”的信息——这就是零知识。

proof of knowledge

陈述（statement）与见证（witness）

ZKP 里的”知识”被形式化成关系 R，以离散对数关系 $R_{dlog}$ 为例：

• 陈述 statement：公开信息 $(p, q, g, y)$——$p, q$ 为素数，$g$ 生成 $\mathbb{F}_p^*$ 的 $q$ 阶子群，$y$ 是子群中的元素
• 见证 witness：满足关系的秘密 $w$，即 $g^w = y \bmod p$（$y$ 关于 $g$ 的离散对数）
• 合起来记作 $((p,q,g,y), w) \in R_{dlog}$

注意：“证明知道 witness” ≠ “证明 statement 为真”。statement 是公开的，谁都知道它为真；ZKP 证明的是”我脑子里有那个满足关系的 $w$”。这类证明叫 proof of knowledge（知识证明）。

Schnorr 协议与 Σ-协议

Schnorr 给出了证明”我知道 $y$ 的离散对数”的交互协议。P、V 之间来回三条消息，消息流程画出来像希腊字母 Σ，所以这类协议统称 Σ-协议。

参数：公开 $y = g^w \bmod p$，秘密为 $w$。

流程（三消息形式）：

P（证明者）                                V（验证者）
                                          持有公开参数 (p,q,g,y)
随机选 r
a = g^r mod p         —— a ——→
                      ←—— e ———           随机 t-bit 挑战 e
z = r + e·w mod q     —— z ——→
                                          验证 g^z = a·y^e mod p
                                          通过 → ⊤  否则 → ⊥

注：$z$ 要模 $q$，因为 $z$ 出现在验证等式的**指数**上，指数世界是模群的阶 $q$ 的（$g^q = 1$），底数那边才模 $p$。

验证为什么成立（这就是完备性）：

$g^z = g^{r + e \cdot w} = g^r \cdot (g^w)^e = a \cdot y^e \bmod p$

一个协议要配叫 Σ-协议，除了长这个形状，还得满足三个性质：

• 完备性 Completeness（上面已经验证了）
• 特殊可靠性 Special Soundness
• 特殊诚实验证者零知识 SHVZK

特殊可靠性 Special Soundness

P、V 之间的一组消息 $(a, e, z)$ 称为一个转录（transcript）。

简单理解就是：拿到同一承诺 $a$、不同挑战 $e \neq e’$ 的两个”被接受的转录” $(a,e,z)$、$(a,e’,z’)$，就能高效算出一个有效 witness。

推导很直接，两份转录里 $r$ 是同一个：

$z = r + e \cdot w \bmod q$
$z’ = r + e’ \cdot w \bmod q$

两式相减消掉 $r$：
$w = (z - z’)(e - e’)^{-1} \bmod q$

# 已知同一 a 下两组被接受的 (e, z)，直接提取 w
from Crypto.Util.number import inverse

def extract_w(e1, z1, e2, z2, q):
    return (z1 - z2) * inverse(e1 - e2, q) % q

注：Soundness vs Special Soundness。普通可靠性说：不知道 $w$ 的 P 骗过 V 的概率不超过 $1/2^t$（挑战空间大小分之一）。特殊可靠性是更强的性质：它直接蕴含普通可靠性（不知道 $w$ 就答不了两个不同的 $e$，单轮成功全凭运气），还额外送一个 witness 提取器——后面 Fiat-Shamir 的安全证明、攻击者的”爆私钥”，全靠它。

再补一个”证明知识”的角度：承诺 $a$ 发出后，能对一个 $e$ 给出合法 $z$，可能只是运气（$1/2^t$）；能对两个不同 $e$ 都给出合法 $z$，就等价于本地能产出两份接受转录，等价于能算出 $w$。所以”能以不可忽略概率说服 V” ⇒ “$w$（或算出它的材料）就在 P 脑子里”——这就是”证明知识”的形式化含义（Bellare–Goldreich ‘92 的 extractor 定义）。

特殊诚实验证者零知识 SHVZK

SHVZK（Special Honest Verifier Zero-Knowledge）：只要 V 按协议老老实实出随机挑战，它从转录里学不到任何关于 $w$ 的东西。

证明思路是模拟器（Simulator）：不掌握 $w$ 的一方也能造出与真实转录分布一致的”假转录”——把协议倒着走一遍：

1、先随机选 $z$、$e$
2、倒着算承诺 $a = g^z \cdot y^{-e} \bmod p$
3、输出 $(a, e, z)$

这个假转录照样满足验证等式 $g^z = a \cdot y^e$，且与真实转录不可区分。连”作弊者”都能批量造出以假乱真的转录，说明转录本身就不携带关于 $w$ 的信息。

为什么 V 学不到东西（三条观察的推理链）：
1、V 本地跑模拟器就能造出任意多份接受转录 → 单纯”拿到一份转录”不构成任何计算 $w$ 的优势
2、诚实 V 的 $e$ 是均匀随机、且与 $a$ 无关的——“先看 $a$ 再选 $e$”实际上影响不了任何东西，这个 $e$ 甚至可以由 P 来随机生成
3、所以走完整套协议（先见 $a$、再见 $e$、再见 $z$）相比”只在最后看一眼完整转录”，没多学到任何东西；结合 ①，除了”P 知道 $w$”这个事实，V 一无所获

注：模拟器在这里开了挂——它被允许在看到挑战之后才选 $a$（现实里 P 必须先承诺 $a$ 再收到 $e$，这个顺序正是安全性的全部支柱）。”给模拟器超能力”是证零知识的标准手法：超能力只消耗在生成过程内部，不进入 V 的视角，所以不造成”模拟世界 vs 真实世界”的信息差。其他协议的超能力还有可编程随机预言机、带陷门的公共参考字符串（CRS）等。

注：带 “Special” 是因为模拟器依赖一个前提——“V 的挑战是均匀随机、且与 $a$ 无关”（这就是”诚实验证者”）。V 一旦不老实（故意挑特定的 $e$），这个性质就没了。这也是后面 Fiat-Shamir 里”挑战如何生成”成为核心安全问题的伏笔。

Fiat-Shamir 启发式：交互 → 非交互（签名）

交互协议只能在线用。把它变成签名的标准操作是 Fiat-Shamir 变换：

$e = H(a \parallel m)$

把”V 随机出挑战”替换成”对承诺和消息一起做哈希”，挑战由 P 自己算出来，不再需要交互。产出的 $(a, z)$ 就是对消息 $m$ 的 Schnorr 签名，安全性在随机预言机模型（ROM）下归约。

为什么哈希能顶替”V 的随机挑战”？关键是顺序：只要 $e$ 在 $a$ 定下来之后才被”随机地”确定，这个随机数由谁产生无所谓。P 固然可以本地狂换 $a$ 来”抽签”想要的 $e$（grinding），但由特殊可靠性，不知道 $w$ 的 P 对一个给定 $a$ 最多只能答对一个特定 $e$——每次抽中概率 $1/2^t$，多项式时间内伪造成功的概率可忽略。

注（CTF 高频考点）：哈希喂了什么非常讲究。原则上要把所有公开参数和全部首条消息都哈进去。FS 类题的经典漏洞就是”没把全部输入哈希进去”——轻则 $e = H(m)$ 不含 $a$（等于先知道 $e$ 再造 $a$，任何人都能伪造，前面”先选 $e$ 再造 $a$”推论说的就是这事），重则没哈某些公开输入，P 可以在算出 $e$ 之后篡改初始数据伪造证明。做题先检查哈希吃了什么。

关键点：此时协议里的随机数 $r$ 摇身一变成了签名 nonce——它一旦复用或可预测，上面特殊可靠性那个提取公式就会被攻击者拿过来反着用：

• 交互协议里：只有 V 能借”同 $a$ 双挑战”提取 $w$（这叫安全性）
• 签名里：任何人都能借”同一 nonce 的两份签名”提取私钥（这叫爆库）

同样的故事在 ECDSA 上也成立（两份签名 $r$ 相同 = nonce 复用，$k = (h_1 - h_2)(s_1 - s_2)^{-1} \bmod n$，再回代 $d = (s_1 k - h_1) r^{-1} \bmod n$），签名题里见烂了，根源都是这一条。

再补两块理论，是”为什么能这么证”的底气：

提取器与 rewinding：交互版协议里，特殊可靠性给的提取器 E 是这么干的——收 $a$、发随机 $e$、收 $z$；把 P rewind 回刚发完 $a$ 的状态；再发一个随机 $e’$、收 $z’$——两份同 $a$ 异 $e$ 的转录到手，套提取公式出 $w$。rewinding 是知识证明的标准证明技术（也是上一类题目里”验证者重放挑战就爆 witness”的原理）。

随机预言机（RO）与可编程 RO：非交互化后 $e = H(a)$ 对同一个 $a$ 永远是同一个值，上面的 rewind 没法做了。于是把哈希建模成随机预言机——首次收到某输入时返回均匀随机值并记录，重复询问返回同一值。在可编程 RO 模型里，提取器能观察 P 对 RO 的查询并控制其输出：让 $H(a)$ 第一次吐 $e$，把 P 连同 RO 一起 rewind，让它第二次吐 $e’$——等于在非交互世界里复刻了 rewinding。这就是”Σ-协议三性质免费换 NIZK 安全性”的机器细节。

FS 的意外之喜：变换把 V 的所有输入都从协议里拿掉了——V 再没有任何”作恶的抓手”。所以哪怕原来只证了 SHVZK（只防诚实 V），套上 FS 后对恶意验证者也零知识了。

恶意验证者：SHVZK 的 “Honest” 是软肋

SHVZK 的保证只覆盖”V 按协议出均匀随机挑战”。V 若故意挑选特殊的 $e$，事情可能崩。

典型受害者：Girault 身份识别协议——一个跑在模合数 $N$（而非素数）上的 DLOG 型 Σ-协议。协议三件套齐全，但面对恶意 V 精心构造的挑战值，P 的诚实应答会把秘密直接泄露出去。

对抗不可信 V 的两条修复路线：
1、做非交互（Fiat-Shamir）：V 的输入被完全移除，想作恶都没有接口——最省事
2、通用变换 SHVZK → 恶意安全 ZK：文献里有标准做法，一般多加一轮交互（防止 V 依据 P 的消息挑选 $e$）

注：交互式 Σ-协议要拿去对抗不可信的 V，两条路必须选一条，裸奔不行。

OR 证明（CDS 构造）

Σ-协议是乐高：文献里一堆复合构造能把简单 Σ-协议拼成复杂功能，最基础的一块是 OR-proof（Cramer–Damgård–Schoenmakers, CRYPTO’94）：证明”我知道 $x_0$ 的 witness 或 $x_1$ 的 witness 之一“，且不泄露是哪个。环签名思想就是从这来的。

流程（P 只掌握 $w_b$）：

1、不知道的那侧（$1-b$）：自己随机挑 $e_{1-b}$，跑 SHVZK 模拟器直接造一份接受转录——模拟器第一次从”证明技巧”变成”协议零件”
2、知道的那侧（$b$）：诚实算承诺 $a_b = g^r$
3、P 发 $(a_0, a_1)$，V 回随机挑战 $s$
4、P 设 $e_b = s \oplus e_{1-b}$，用 $w_b$ 诚实算 $z_b$，发两份完整转录
5、V 验证 $e_0 \oplus e_1 = s$，且两份转录各自通过验证

灵魂是 XOR 拆分：V 的一个挑战 $s$ 被拆成两份，P 自由决定一份（假侧开局就选好），另一份被 $s$ 锁死（真侧必须真刀真枪地答）。分布上 $e_b = s \oplus e_{1-b}$ 依旧均匀，真侧看起来和正常交互无异。

三性质全部继承（所以 $\Sigma_{OR}$ 本身还是 Σ-协议，能继续复合、继续套 FS）：

• 完备性：构造直接保证
• 零知识：两份转录各自的分布都正确，整体分布对 $b = 0/1$ 对称，V 看不出哪侧是真的——这正是”不泄露是哪个”
• 特殊可靠性：固定承诺，V 发两个不同挑战 $s \neq s’$ 且都被骗过 ⇒ $(e_0 \oplus e_0’) \oplus (e_1 \oplus e_1’) \neq 0$ ⇒ 至少一侧出现同 $a$ 异 $e$ 的两份转录 ⇒ 套提取公式，抽出某一侧的 witness

一句话直觉：一半真话、一半模拟，XOR 把两半缝成一句完整回答——V 只能验”缝合后”的整体，而要缝得上，P 至少得有一半是真的。

小结

• 三性质：完备性、可靠性、零知识性
• Σ-协议：承诺 $a$ → 随机挑战 $e$ → 应答 $z$，三件套验收合格
• 特殊可靠性：同 $a$ 异 $e$ 两转录 → 可提取 $w$（蕴含普通可靠性，$w = (z-z’)(e-e’)^{-1}$）
• SHVZK：模拟器 $S(x, e)$ 造同分布转录 → 转录不含 $w$ 的信息
• Fiat-Shamir：$e = H(\text{全部公开输入} \parallel a)$，交互 → 非交互 NIZK，顺带对恶意 V 也安全
• FS 漏洞点：哈希没吃全输入 = 可伪造；nonce 复用 = 爆私钥
• 恶意 V：SHVZK 只防诚实 V，对抗恶意 V 要靠 FS 非交互化或通用变换（Girault 之戒）
• OR 证明：模拟一侧 + 诚实一侧，XOR 缝合，不泄露掌握的是哪个 witness

刷这类题的固定思路：看到”证明你知道 $g^w = y$”，老老实实实现 P 侧（$r$ 每次随机）；看到”服务给你转录”，盯特殊可靠性那条减法公式凑两组同承诺数据；看到”给你 $s$ 让你凭空造转录”，两侧全跑模拟器；看到 FS 签名，先检查哈希吃了什么、nonce 有没有复用。