Schnorr 签名与 Σ 协议：最简单的零知识证明

一句话版本

Schnorr 协议让你证明"我知道 $x$ ，使得 $y = g^x$ "，却不透露 $x$ 本身。流程只有三步：承诺、挑战、回应。用哈希代替验证者出挑战（Fiat–Shamir 变换），这个证明就变成了签名。比特币 Taproot 升级用的正是 Schnorr 签名，它的线性结构让多人签名可以合并成一个。

全文分三层：

通俗理解：三步对话，为什么既可信又不泄露
实际用处：比特币 Taproot、MuSig2、Ed25519
数学原理：协议、可靠性（提取器）、零知识（模拟器）、Fiat–Shamir，附手算例子

第一层：通俗理解

1.1 证明你知道密码，但不说出密码

你想向门卫证明自己知道公司保险柜的密码，又不想把密码告诉他。Schnorr 协议给出的办法是一段三步对话：

为什么可信：证明者必须在看到挑战之前就定下 $R$ 。如果他不知道 $x$ ，就只能碰运气猜挑战，而挑战空间极大，几乎不可能猜中。
为什么不泄露：回应 $s = k + cx$ 里， $x$ 被一个随机数 $k$ "盖住"了， $s$ 看上去就是一个均匀随机数。

1.2 从对话到签名

对话需要验证者在线出题。Fiat 和 Shamir 的想法是：让哈希函数来出题，令 $c = \mathrm{Hash}(R, \text{消息})$ 。哈希的输出无法预测，效果和诚实的验证者一样。这样证明者可以一个人生成 $(R, s)$ ，任何人事后都能检查，这就是数字签名。

第二层：实际用处

比特币 Taproot（BIP 340，2021 年激活）：在 secp256k1 上引入 Schnorr 签名。
MuSig2：多个人的 Schnorr 签名可以合并成一个普通签名，链上看起来和单人交易一模一样，省空间也更隐私。原理是 Schnorr 的回应 $s$ 对私钥是线性的： $s_1 + s_2 = (k_1 + k_2) + c(x_1 + x_2)$ 。
FROST：Schnorr 的门限签名协议，配合Shamir秘密分享实现"5 个人中任意 3 个签名"。
Ed25519（EdDSA）：SSH、Signal、Tor、许多区块链都在用，它是 Schnorr 的一个变体，并把随机数 $k$ 改为由私钥和消息哈希确定性地生成。

为什么比特币一开始没用 Schnorr

Schnorr 在 1989 年就申请了专利，直到 2008 年才过期。这期间业界转而使用绕开专利的 DSA / ECDSA，它们结构更复杂，也没有简洁的线性性。比特币诞生于 2009 年，当时 Schnorr 还没有成熟的标准化实现，所以沿用了 ECDSA。

第三层：数学原理

3.1 协议

设 $G = \langle g \rangle$ 是一个素数阶 $q$ 的循环群（ $\mathbb{Z}_p^\times$ 的子群或椭圆曲线群），私钥 $x \in \mathbb{Z}_q$ ，公钥 $y = g^x$ 。

承诺：随机 $k \in \mathbb{Z}_q$ ，发送 $R = g^k$ ；
挑战：验证者发送随机 $c \in \mathbb{Z}_q$ ；
回应：发送 $s = k + cx \bmod q$ ；
验证： $g^s \stackrel{?}{=} R \cdot y^c$ 。

正确性： $g^s = g^{k + cx} = g^k (g^x)^c = R\, y^c$ 。

3.2 可靠性：如果你能回答两个问题，你就一定知道 $x$

假设某个证明者对同一个 $R$ 能回答两个不同的挑战 $c \neq c'$ ，给出 $s, s'$ 。那么

$g^{s} = R\,y^{c},\quad g^{s'} = R\,y^{c'} \ \Rightarrow\ g^{s - s'} = y^{c - c'} \ \Rightarrow\ x = \frac{s - s'}{c - c'} \bmod q.$

所以"能骗过验证者"的人其实能算出 $x$ ，这叫特殊可靠性（special soundness），算出 $x$ 的这个过程叫提取器。这里用到 $q$ 是素数，使 $c - c'$ 在 $\mathbb{Z}_q$ 中可逆。

3.3 零知识：不知道 $x$ 也能造出一模一样的对话

模拟器倒着造：先随机选 $s$ 和 $c$ ，再令 $R = g^s y^{-c}$ 。这三个数满足验证等式，而且分布与真实对话完全相同（ $s$ 、 $c$ 均匀随机， $R$ 由它们决定）。

既然不知道 $x$ 的人也能造出同分布的对话记录，那么真实对话就不可能透露任何关于 $x$ 的信息。这就是零知识的定义方式。（严格说 Schnorr 协议是"诚实验证者零知识"。）

3.4 Fiat–Shamir 变换：变成签名

把挑战换成 $c = H(R \,\|\, y \,\|\, m)$ ：

签名： $(R, s)$ 或 $(c, s)$ ，其中 $s = k + cx$ ；
验证：重新算 $c$ ，检查 $g^s = R\,y^c$ 。

在随机预言机模型下，伪造签名等价于解离散对数。

3.5 手算例子

$p = 23$ ， $q = 11$ ， $g = 2$

$2^{11} = 2048 = 89 \cdot 23 + 1$ ，所以 $g = 2$ 在 $\mathbb{Z}_{23}^\times$ 中的阶是 $11$ 。

密钥：私钥 $x = 3$ ，公钥 $y = 2^3 = 8$ 。

签名（假设哈希给出 $c = 4$ ）：

选 $k = 5$ ， $R = 2^5 = 32 \equiv 9$
$s = 5 + 4 \cdot 3 = 17 \equiv 6 \pmod{11}$

验证：

左边 $g^s = 2^6 = 64 \equiv 18$
右边 $R\,y^c = 9 \cdot 8^4$ 。 $8^4 = 4096 = 178 \cdot 23 + 2 \equiv 2$ ，所以 $9 \cdot 2 = 18$
相等 ✓

重复使用 $k$ 的灾难：同一个 $k = 5$ 对另一条消息签名，哈希给出 $c' = 7$ ， $s' = 5 + 7 \cdot 3 = 26 \equiv 4$ 。攻击者看到两个签名的 $R$ 相同，套用 3.2 节的提取器： $x = \frac{s - s'}{c - c'} = \frac{6 - 4}{4 - 7} = \frac{2}{-3} \pmod{11}.$ $-3 \equiv 8$ ， $8^{-1} \equiv 7$ （ $8 \cdot 7 = 56 \equiv 1$ ），所以 $x = 2 \cdot 7 = 14 \equiv 3$ ，私钥被还原。

可靠性证明里的"提取器"，在现实中就是攻击者。（已用 Python 验算。）

总结

层次	要点
直觉	承诺、挑战、回应；先定 $R$ 再看题，所以骗不了
可靠性	同一 $R$ 答两题就能解出 $x$ （提取器）
零知识	倒着造的假对话与真对话分布相同（模拟器）
工程	Fiat–Shamir 变签名；线性结构带来 MuSig2、FROST； $k$ 绝不能重复