作者：Nadav Kohen

来源：https://suredbits.com/introduction-to-schnorr-signatures/

欢迎阅读 Suredbits 撰写的 Schnorr 签名系列博客！

本文中我会解释 Schnorr 签名是什么、直观上它是如何工作的。到了下一篇文章，我会给出证据，证明这种方案是安全而且正确的。除了这两部分，本系列博客剩下的文章会介绍 Schnorr 签名能够支持的多种签名方案以及它们的应用场景。

在开始阅读之前，建议你先检查一下自己是否熟悉下列几个概念，因为我的讲解预设了读者具备有关它们的一些基础知识：

1. 求模运算 —— 也就是只关心余数的数学（译者注：对正数来说，“模 n” 或 “对 n 求模” 即求除以 n 的余数，故求模运算的结果必定小于 n）
2. 哈希函数 —— 密码学领域的这部分
3. 公钥和椭圆曲线 —— 只需 阅读/略读 至 “How to prove you know x” 部分即可，因为后续的部分在本文中都有讲解

虽然本系列博客的主旨是一般化地讲解 Schnorr 签名，但本系列的主要动机是 Schnorr 签名即将引入比特币区块链；比特币区块链当前使用着一种名为 ECDSA 的签名算法，我们会经常比较这两者。

直观来说，Schnorr 签名是如何工作的？

免责声明：本章节不是安全性证明或相关的具有严格含义的内容，只是尝试讲解有关 Schnorr 签名工作方式的一些直觉。

那么，先假设我们生已经发现，在我们这个世界里，离散对数问题在椭圆曲线上是难解的 —— 即，假设 x 是一个很大的数，而 G 是椭圆曲线上的一个点，仅知道 x * G 我们很难反推出 x。所以，我们可以使用 x * G = X 来作为私钥 x 的公钥。已经明确了我们想利用这一事实来创造一种数字签名方案，但还没开发出来。那我们可以尝试什么思路呢？

我们先想一想，我们的签名方案要实现什么样的目标？我们希望一个数字签名同时承诺了一个人的私钥和被签名的那条消息。我们也希望，签名不会泄露关于签名者私钥的任何信息。最后，我们希望有一种办法，只需使用公开的信息就能验证签名的正确性。

把我们的私钥和消息都看成是编码为数字的数据；我首先想到的将它们结合在一起从而能承诺它们两者的两种办法：加法 (x + m) 和乘法 (x * m)。注意，两种操作最后都会对某个数字 p 求模，因为我们不想让签名的体积很大，而且希望密钥只需是 256 位（二进制位），所以我们在稍小于 2²⁵⁶ 的数字中选出一个吉利的作为 p（参见 secp256k1 的 p 值定义）。这两种结合的办法当然满足我们想要的第一种属性（承诺），但都不满足我们想要的第二种属性，因为无论是加法后模 p 还是乘法后模 p，都是可以反推的，这样就会泄露我们的私钥！不过，也许我们仍然可以通过添加一个额外的混淆步骤来保存这两种方法之一，那么，给定加法 (x + m) 或乘法 (x * m)，我们能做什么 “调整” 来隐藏我们的私钥呢？我们可以生成一个完全随机的数 k，使之与我们的 x 和 m 相结合。现在，到底该用哪种方法，就变成了一个可以用试错来解决的问题了，因为不论如何它都能提供可靠的计算方法来满足我们想要的前两种属性，但不是所有的结合方法都能让签名可以验证。

在尝试了这三个数字的多种加法乘法苏荷之后，我们选中了 s = k + m * x，它既使用 m * x 承诺了消息和密钥，又使用随机的密钥 k 隐藏起了这些信息。这种结合方式与其它方式相比，最大的区别在于：只要把这个数字转化为（椭圆曲线上的）一个点，我们就得到了一种很棒的结构，只需使用公钥就可以验证签名：给定椭圆曲线上的一个标准点 G 用于生成公钥（需要所有参与者都知晓；见 secp256k1 曲线的 G 值定义）；我们可以用 G 乘上我们的签名，得到：

$$s*G = (k + m * x) * G = k * G + (m * x) * G$$

这里 R = k * G 就是 k 的公钥，而 X = x * G 是 x 的公钥。所以只需要公开的信息就能验证我们的签名（假设 R 已经公开）！

我们要做的最后一个事情是优化，使用 H(m) （就是 m 的哈希值）来替代 m，因为 m（要签名的消息）可能非常大。这个替换式可以接受的，因为 H(m) 仍然承诺了 m，所以我们的签名也是（承诺了 m）。

因此，我们现在的签名方案，在给定私钥 x 和消息 m 时，是生成一个随机数 k，并公开 s = k + H(m) * x 和 R = k * G。验证者可以通过检查 s * G = R + H(m) * X 是否成立来验证签名的有效性（如前所述，s 和 R 是签名的内容，而 m 是被签名的消息，X 是签名者的公钥）。

至此，我觉得我们已经没有问题了，但在我们尝试正式分析和证明这个方案的安全性之前，我们先来尝试攻击它。我想到的第一种攻击是伪造攻击：不知道这个私钥的人，想伪造这个私钥的签名。作为这种类型的攻击者，我们知道 X（x 的公钥）和 m（待签名的消息），尝试生成一个能够通过验证的有效签名。换句话来说，仅知 X 和 m，我们想搞出一组（R, s）来通过签名验证。回想我们的验证等式 s * G = R + H(m) * X，我们知道它等价于：R = s * G – H(m) * X（这是通过在等式两边都减去 H(m) * X 得到的）。但是，且慢，我们已经知道了 H(m) * X ，那只需要选出 s（就能凑出这个等式来了） —— 那么，我们只需选出一个随机数作为 s，再根据算式 s*G – H(m) * X 的结果来设定 R，就成了。也就是说，我们可以生成任意的 s 值，然后根据这个值来计算 R 值；只用到了公开的信息，就可以任意创建有效的数字签名 …… 大事不妙啊。

跟前面一样，我们发现，这个方案还是可以挽救的，我们只需要调整一些东西来打破这种攻击。从目前来看，要说显然可以哪种办法会有点牵强，但我们会在证明 Schnorr 签名安全性的讨论（下一篇文章）中介绍它的真正起源，也许能让下一个选择理解起来更加自然。

可以尝试的其中一种思路是使得 s 依赖于 R，从而打破等式 R = s * G – H(m) * X。办法之一是在我们哈希那条消息时使用 R，也就是让 s = k + H(R, m) * x，此处的 H(R, m) 就是拿 R 作为消息 m 的前缀，一起去做哈希计算（有时候会写成 H(R||m)，这里的 || 表示拼接）。这就打破了我们的伪造攻击，因为现在，给定一个随机的 s，找出一个 R 使得 R = s * G – H(R, m) * X 成立是很难的，因为 R 也参与了哈希值的生成，除了暴力破解之外，没有更好的办法来找出合适的 R。

我想重申，这不是 Schnorr 签名实际上的安全形态，因为仍有其它方式可以伪造签名。但它确实看起来能应对明显的攻击，可以证明是安全的。我们成功地 “发明” 了 Schnorr 签名！

Schnorr 签名的定义

如果你有一个公私钥对 (x, X = x * G)，那么该私钥对一条消息 m 的 Schnorr 签名是一对数值 (R, s)，其中 k 是一个随机的密钥：

$$ R = k * G$$

$$s = k + H(R, m) * x$$

分析一下，对每一个签名，签名者都生成一个随机的数值作为 k 的值，k 本质上就是这个签名的一次性私钥。签名者计算出 R，也就是 k 的公钥，一般我们称之为 nonce。接下来，我们取 R 和 m 一起的哈希值。这个哈希值才是实际上被签名的东西：被哈希的对象包括消息和一个公开的数值，所以这个哈希值是对这条消息和 R 的承诺。后面我们会看到，我们需要对 R 的承诺来保证这种签名方案是安全的。最后，签名者使用私钥与这个哈希值执行乘法（模 p）运算；得出的结果再与一次性私钥 k 做加法（模 p）运算，得出的结果就是 s。R 与 s 一道构成了签名的内容，这个签名本质上就是证明，知道 x 的某人签名了消息 m，而 R 是一次性公钥，与普通的公钥 X 一样都是验证这个签名所需的数据。在比特币中，签名 (R, s) 会被编码成 64 个字节，前面 32 个字节表示 R， 后面 32 个字节表示 s。

这只是故事的一半：签名的生成。签名生成之后，任何知道消息 m 和公钥 X 的人都应该能够验证这个签名。签名的验证就是检查下列等式是否成立：

$$s * G =? R + H(R, m) * X$$

你可以看出， m 和 X 必须是验证者已知的，而 R 和 s 就是签名。

这些就是围绕 “山寨” Schnorr 签名的全部计算了！生成一个签名要用到一个（一次性）的私钥、一次哈希计算、一次乘法和一次加法。而验证签名只需要得到一个哈希值，运用两次点乘法和一次点加法。有了这些知识，你现在应该能够自己阅读和理解 BIP-340 的主要内容了：它基本上就是我在这里讲述的方案的更详细的版本，它会更关心这些数据是如何编码的、 k 值是如何生成的，等等。

虽然多了解一些 Schnorr 签名以便实现它们是很棒的事，但我们还想挖得更深一些！Schnorr 签名有一些什么样的特点呢？它跟（比特币现在使用的）ECDSA 签名相比如何？在它们的工作原理背后，有一些什么样的直觉？我们怎么知道它们是安全的？甚至于，对这些东西来说，“安全性” 到底意味着什么？我们一个一个来回答这些问题。

Schnorr 签名的特性

首先，我们来列举一下大部分签名方案都有的一些共同特点。

Schnorr 签名看起来就像随机数。具体来说，k 合 x 都是随机数，而 H(R, m) 应该也是个随机数，因为它是哈希函数的一个输出；不严格地来说，把一堆随机数组合在一起也会给我么一个随机数。这里的意思，无论被签名的消息实际是什么样的、签名者是谁，（这些因素都不会使签名的值产生明显的偏差），s 看起来都差不多。注意，这只是一个说法，并不能证明 Schnorr 签名不会泄露有关签名者私钥的任何信息。不过，我们后面详解其安全性时，还会讲到这个属性。

Nonce 绝对不可以重复使用！我把密钥对 (k, R) 称为一次性密钥是有理由的：如果你在签名两条不同的消息时用上了同一个 (k, R) 密钥对，你就会完全泄露你的私钥。我们来看看你要是犯了这个错误，攻击者可以如何获得你的私钥：攻击者一开始获得了 X（你的公钥），R（被重用的 nonce 值），m₁ （第一条消息），s₁（第一个签名），m₂ （第二条消息），s₁（第二个签名）；回想一下，s 值是对某条消息和私钥 x 的承诺，但经过了随机数 k 的调整。因此，如果攻击者把两个 s 值相减，那用来隐藏私钥 x 的随机数调整，就完全没有效果了（因为 nonce 重用意味着两个调整的效果是相同的）！攻击者可以依次计算：

s_1 – s_2 = (k + H(R, m_1) * x) – (k + H(R, m_2) * x) （根据定义）
        = H(R, m_1) * x – H(R, m_2) * x             （因为 k - k）
        = (H(R, m_1) – H(R, m_2)) * x             （有相同乘数）

让我所说，k 的调整（隐藏）效果没有了之后，两个签名的差值就只剩下了 H(...)*x，也就是两个哈希值的差值乘以 x。最后，因为这两个哈希值都是已知的（它们是公开信息的哈希值），所以我们可以利用这个等式：

$$s_1 – s_2 = (H(R, m_1) – H(R, m_2)) * x$$

这个式子中只有 x 是不公开的了。攻击者可以根据下面的式子解出 x：

$$x = \frac{(s1 – s2)}{H(R, m1) – H(R, m2)}$$

任何人只要看到了你重用了一个 nonce ，就知道了你的私钥，可以拿走你所有的比特币！BIP 340 试图通过在生成 k 时使用消息作为密钥生成函数的其中一个输入，来保证 nonce 不会被重用：如果消息改变了，那 nonce 也会跟着改变。

这两种属性对 ECDSA 和许多其它类型的签名协议也是一样的，实际上我们会看到，这两种属性实际上也是 Schnorr 签名安全性的一部分。现在，我们来看看 ECDSA 与 Schnorr 的两个最主要的区别，这些区别使得 Schnorr 更为独特和优秀。

Schnorr 签名体积比 ECDSA 更小，计算和验证起来更快。在比特币现在使用的 ECDSA 签名方案中，一个签名（DER 编码）是 70 或 71 字节长；而 Schnorr 签名的长度是 64 字节。此外，计算和验证 Schnorr 签名都比 ECDSA 签名快得多。

Schnorr 签名是线性的。这是 Schnorr 与众不同的关键之处，使之能支持我们将在这系列博客中介绍的大部分方案。线性是签名函数的属性（签名函数以密钥和一条消息作为输入，输出签名），也就是说：

$$Sign(x_1, k_1, m) + Sign(x_2, k_2, m) = Sign(x_1 + x_2, k_1 + k_2, m)$$

这个等式的意思是，如果有两方签名同一条消息，并将他们的签名加起来，就可以得到他们的聚合密钥的一条有效签名！使之成真需要一个略微改动过的 Schnorr 签名版本：令总 nonce 值 R = R₁ + R₂ （也就是每一个 nonce 值的和），并在生成消息哈希值时使用 R（而非参与方各自的 nonce 值），由此可得：

    SchnorrSign(x_1, k_1, m) + SchnorrSign(x_2, k_2, m)
= (k_1 + H(R, m) * x_1) + (k_2 + H(R, m) * x_2)
= (k_1 + k_2) + H(R, m) * (x_1 + x_2)
= SchnorrSign(x_1 + x_2, k_1 + k_2, m)

换句话说，因为我们把签名方案修改成使用同一条哈希值，加总两个签名的结果相当于把两个随机数相加以及把两个私钥相加，这就给了我们一个很棒的线性签名函数。

而 ECDSA 并没有同样的属性。我们会在本系列博客的后续篇章中探究这种线性属性的用场。

最后，如 BIP 340 所说，“在取得所有这些好处时，它几乎没有缺点”。Schnorr 是最简单的基于椭圆曲线的签名方案，而比特币只会从中获益，别无所失。

结论

本文中我们定义了 Schnorr 签名，讨论了它的一些属性，拿它跟 ECDSA 作了比较，甚至还搞出了一段我们凭直觉为自己发明了（大部分）Schnorr 签名的 “假历史”。此外，我还偷偷塞进了我们将用来证明 Schnorr 是一种安全签名方案的许多线索：nonce 重用会泄露私钥、我们的幼稚方案 k + H(m) * x 无法抵御伪造攻击。我们会使用这些事实和其它的一些事实来证明 Schnorr 是安全的，就在下一篇文章；然后我们会讨论如何利用 Schnorr 和它的线性属性做出许多很酷的事情，敬请期待！

（完）

续篇中文译本