Schnorr 签名

Bitcoin 目前 ECDSA 和 Schnorr 两套签名算法并存，ECDSA 为原始方案，从 2009 年创世纪以来就在使用，Schnorr (BIP-340) 是在 2021 年 11 月 Taproot 升级激活后引入的。两者都基于 secp256k1 曲线。ECDSA 是为了绕开 Schnorr 专利而发明的算法，理解起来相当别扭，如今 Schnorr 的专利已经失效了，我们就不聊 ECDSA 了。

secp256k1

secp256k1 是一条定义在有限域上的椭圆曲线，公式如下：

$$y^2 = x^3 + 7 \pmod p$$

其中 $p = 2^{256} - 2^{32} - 977$，模数的存在使得 $x$ 和 $y$ 都必须是整数，所以 secp256k1 不是一条连续的曲线，而是一堆离散的点。

不过散点图不直观，难以建立几何感。下面这张是 取模之前、把曲线放在实数域 $\mathbb{R}$ 上画出来的样子（即去掉 $\bmod\, p$ 的 $y^2 = x^3 + 7$）。secp256k1 的真实形态是从这条曲线上”按模 $p$ 摘点”，但讨论点加法、切线、对称等几何性质时，用实数域的连续曲线来想就够了。

y² = x³ + 7secp256k1

a0

b7

此刻你可能会想，为什么叫椭圆曲线？椭圆曲线的一般形式叫 Weierstrass 方程：$y^2 = x^3 + ax + b$，将上图中的 $a$ 往左边拖动，你就会知道为什么叫椭圆曲线方程了。

点加法

点加法是椭圆曲线密码学的核心运算，后面要讲的公私钥、签名、验证全都建立在它之上。几何上的定义如下：

给定曲线上两个点 $P$、$Q$，规定 $P + Q$ 按以下三步求得：

1. 过 $P$ 和 $Q$ 画一条直线。
2. 这条直线会与曲线相交于第三个点 $R$。
3. 把 $R$ 关于 $x$ 轴对称翻折，得到的点就是 $P + Q$。

三种特殊情形

• $P = Q$：两点重合时，“过两点的直线” 退化为 “过 $P$ 的切线”。把切线与曲线的第三个交点翻折，得到 $2P$。
• $P$ 和 $-P$：定义 $-P$ 为 $P$ 关于 $x$ 轴的对称点，那么过它们的直线垂直于 $x$ 轴，与曲线只有这两个交点。数学家约定此时”第三个交点在无穷远处”，记作 $\mathcal{O}$（无穷远点 / point at infinity），翻折之后还是 $\mathcal{O}$。于是 $P + (-P) = \mathcal{O}$。
• 与 $\mathcal{O}$ 相加：$\mathcal{O}$ 是单位元，对任意点 $P$ 都有 $P + \mathcal{O} = P$。

构成阿贝尔群

把 $\mathcal{O}$ 也算进来，曲线上所有点在上述加法下满足：

• 封闭性：两点相加仍在曲线上
• 结合律：$(P + Q) + R = P + (Q + R)$
• 单位元：$\mathcal{O}$
• 逆元：每个 $P$ 的逆元是 $-P$
• 交换律：$P + Q = Q + P$

五条满足 → 阿贝尔群（Abelian group）。这意味着日常加法代数的所有性质在曲线点上都成立。

密钥对

secp256k1 上有一个特殊的点 $G$，称为基点（generator point），它的坐标是固定的、公开约定好的。$G$ 加自己 $n$ 次会回到 $\mathcal{O}$（一个无穷远的点）。$n$ 是一个接近 $2^{256}$ 的大素数，叫做基点的阶（order）。

在 $1$ 到 $n-1$ 之间随机选一个整数 $d$，把 $G$ 加自己 $d$ 次得到的点 $P = dG$ 就是公钥，$d$ 是私钥。

要让公钥 $P$ 和私钥 $d$ 之间的关系成立，必须满足知道 $d$ 可以快速算出 $P$，但知道 $P$ 却难以反推出 $d$。这也是椭圆曲线密码学安全性的基础。

我第一次看到这个等式时就有一个疑问，$P$ 是由 $G$ 加自己 $d$ 次得到的，那知道 $d$ 不也要计算 $d$ 次加法吗？那和暴力破解所需的时间不是一样的吗？其实不然，如果知道准确的 $d$，可以用二进制展开法（double-and-add）来计算 $P$。

假设 $d = 13$，二分法的计算过程如下：

1. $13$ 的二进制表示是 $1101$。
2. 从 $G$ 开始，依次计算 $2G = G + G$、$4G = 2G + 2G$、$8G = 4G + 4G$。
3. 根据二进制位，$13G = G + 4G + 8G$。

只需要计算 $G$、$2G$、$4G$、$8G$ 四次加法，就能得到 $13G$，而不是需要计算 $13$ 次加法。最多只需要计算 $256$ 次加法（因为 $d$ 的最大值是 $n-1$，接近 $2^{256}$）。并且 $2G$、$4G$、$8G$ 等中间结果可以缓存起来，进一步提高效率。对于不知道 $d$ 的攻击者来说，只能从头开始计算 $G$、$2G$、$3G$……直到找到 $P$。

Schnorr 签名

前提：生成密钥对 $(d, P)$，其中 $P = dG$。要签名消息 $m$。

签名

签名过程如下：

1. 选择一个随机数 $k$，计算 $R = kG$。
2. 计算哈希值 $e = H(R \| P \| m)$，其中 $m$ 是消息，$\|$ 表示连接。
3. 计算签名值 $s = k + ed \pmod n$。
4. 签名是 $(R, s)$。

验证

我们先来看看哪些信息是公开的：

• 公钥 $P$
• 消息 $m$
• 签名 $(R, s)$
• 哈希值 $e$（可以由 $R$、$P$、$m$ 计算得到）

回到签名值的计算公式 $s = k + ed \pmod n$，等式两边同时乘以 $G$，得到：

$$sG = kG + edG \pmod n$$

代入公开的信息 $R = kG$ 和 $P = dG$，可以把上式改写为：

$$sG = R + eP \pmod n$$

这个等式中的所有信息都是公开的，验证者只需要计算 $sG$ 和 $R + eP$ 是否相等，就可以判断签名是否有效。因为只有知道 $k$ 和 $d$ 的人才能计算出正确的 $s$，所以这证明了签名者确实拥有私钥 $d$。

随机数 $k$ 在其中起到了保护私钥 $d$ 的作用。因为等式 $s = k + ed \pmod n$ 中只有两个未知数 $k$ 和 $d$，如果知道 $k$，就可以直接计算出 $d$。如果被发现 $k$ 重复使用两次，那么攻击者即使不知道 $k$ 的具体值，也可以通过两个签名的差值来消除 $k$，从而求出 $d$。因此，确保每次签名使用不同的随机数 $k$ 是非常重要的。