干货| Schnorr 签名如何改进比特币

在阅读 Blockstream 的 MuSig 论文时，我一直在想象这对我作为比特币用户意味着什么。 我发现 Schnorr 签名的某些功能非常酷且方便，而某些功能则非常烦人。 在本文中，我希望与您分享我的想法。 但首先，让我们快速回顾一下。

椭圆曲线签名算法

当前的比特币所有权系统使用 ECDSA（椭圆曲线签名算法）。 在对消息m进行签名时，我们先对消息进行哈希运算得到一个哈希值，即z = hash(m)。 我们还需要一个随机（或至少看似随机）的数字 k。 在这里，我们不想信任随机数生成器（有太多的错误和与不合格的随机数生成器相关的错误），所以我们通常使用RFC6979，基于我们知道的秘密值并且我们想要签署消息，计算确定性的 k。

使用私钥 pk，我们可以为包含两个数字的消息 m 生成签名：r（随机点的 x 坐标 R = k * G）和 s = (z + r*pk)/k。

然后，使用我们的公钥 P = pk * G，任何人都可以验证我们的签名，即检查 (z/s)×G+(r/s)×P 的 x 坐标确实是 r。

- ECDSA 算法图。 出于说明目的，椭圆曲线在实数域上运行 -

这个算法很常见，也很容易使用。 但仍有改进的余地。 首先，签名的验证涉及除法（1/s）和两个点的乘法，这些操作计算量很大。 在比特币网络中，每个节点都要验证每一笔交易，所以当你在网络中发送一笔交易时，全网成千上万的节点都要验证你的签名。 所以即使签名过程变得更加昂贵，让验证签名变得更容易仍然是非常有益的。

其次，当节点验证签名时，每个签名都是单独验证的。 在 mn 的多重签名交易中，节点必须多次验证同一个签名。 例如，7-11 多重签名交易包含 7 个签名，网络中的每个节点都必须验证 7 个签名。 此外，此类交易量也非常大，用户为此要支付更多的费用。

Schnorr 签名

Schnorr 签名的生成方式略有不同。 它不是两个标量 (r, s)，而是一个点 R 和一个标量 s。 类似于 ECDSA 签名，R 是椭圆曲线上的随机点 R = k * G。 签名第二部分s的计算过程也有点不同：s = k + hash(P,R,m) ⋅ pk。 这里pk是你的私钥，P = pk * G是你的公钥，m是消息。 验证过程是检查s * G = R + hash(P,R,m) * P。

-图解Schnorr签名和验证-

该方程是线性的，因此可以在等号仍然成立的情况下对多个方程进行加减。 这给我们带来了 Schnorr 签名的几个不错的属性。

1.批量验证

在区块链上验证一个区块时，我们需要验证区块中所有交易的签名是否有效。 如果其中一个无效，那么哪一个都无关紧要——我们必须拒绝整个区块。

ECDSA的每一个签名都要具体验证，也就是说如果一个区块包含1000个签名，那么我们需要计算1000次除法和2000次点乘，总共约3000次重运算。

但是使用 Schnorr 签名，我们可以将所有签名验证方程相加并节省一些计算量。 在一个包含 1000 笔交易的区块中，我们可以验证：

(s1+s2+…+s1000)×G=(R1+…+R1000)+(散列(P1,R1,m1)×P1+散列(P2,R2,m2)×P2+…+散列(P1000,R1000,m1000)× P1000)

那是一大堆点加法（从计算的角度来看毫无意义）和 1001 点乘法。 几乎已经提高了 3 倍的性能 - 每个签名只需重新计算一次即可进行验证。

- 批量验证两个签名。 因为验证方程是线性相加的比特币多签钱包，只要所有签名都有效，这些方程的和也必须成立。 我们节省了一些计算量，因为标量和点加法比点乘法更容易计算。 -

2.密钥生成

我们希望保证我们的比特币安全，所以我们可能希望使用至少两个不同的私钥来控制它们。 一个用于笔记本电脑或手机（在线钱包、热钱包），另一个保存在硬件钱包/冷钱包中。 即使其中之一泄露，我们仍然控制着我们的比特币。

目前实现这种钱包的方式是通过2-2多重签名脚本。 即一笔交易需要包含两个独立的签名。

使用 Schnorr 签名，我们可以取一对密钥 (pk1,pk2) 并使用共享公钥 P = P1 + P2 = pk1 * G + pk2 * G 生成一个公共签名。生成签名时，我们需要生成一个两个设备上的随机数(k1, k2)，生成两个随机点Ri = ki * G，加上hash(P, R1 + R2, m)，可以得到s1和s2(因为si = ki + hash( P, R, m)* pki). 最后将它们全部相加得到签名(R,s)=(R1+R2,s1+s2)，这就是我们的共享签名，可以用共享公钥进行验证。 没有其他人可以判断它是否是一个聚合签名，它看起来就像一个普通的 Schnorr 签名。

但是，这种方法存在三个问题。

第一个问题是在用户界面上。 要发起交易，我们需要在两个设备之间发起多轮交互——用于计算公共 R 和签名。 在两个私钥的情况下，我们只需要访问一次冷钱包：我们可以在热钱包中准备待签名的交易，选择k1并生成R1 = k1 * G，然后将待签名的交易放在一起将这些数据传入冷钱包并签名。 因为已经有了R1，签名交易在冷钱包中只需一轮即可完成。 我们从冷钱包中获取 R2 和 s2 并将其发送回热钱包。 热钱包使用前述的(k1,R1)签名交易，两个签名之和可以对外广播交易。

这种体验和我们现在能做的没什么两样，每增加一个私钥，问题就会变得更复杂。 假设你有一笔财富，由 10 把私钥共同控制，这 10 把私钥分别存放在世界不同的地方。 你这个时候发送交易多麻烦啊！ 在目前的ECDSA算法中，每个设备只需要访问一次，但是如果使用Schnorr的key aggregation，则需要访问两次才能得到所有的Ri并签名。 在这种情况下，与其聚合，不如单独使用每个私钥签名——这样只需要一轮交互。

文章写完后，得到Manu Drijvers的反馈：在一个可证明安全的多重签名方案中，需要3轮交互：

第二个问题是已知的流氓密钥攻击。 论文里解释的很好，我就不赘述了。 大概意思是，如果你的一台设备被黑了（比如你的热钱包被劫持了），假装你的公钥是（P1 - P2），你就可以只用私钥控制两个私钥的共享私钥关键pk1资金。 一个简单的解决方案是在设置设备时要求私钥签署相应的公钥。 还有第三个主要问题。 你不能用确定性的 k 签名。 如果你使用确定性 k，黑客只需一次简单的攻击就可以得到你的私钥。 攻击是这样的：一些黑客侵入了你的笔记本电脑并完全控制了其中一个私钥（比如 pk1）。 我们觉得资金仍然安全，因为使用我们的比特币需要 pk1 和 pk2 的聚合签名。 于是我们照常发起一个交易，准备一个待签名的交易和R1，发送到我们的硬件钱包，硬件钱包签名后，将(R2,s2)传回热钱包……然后，热钱包钱包出错，无法完成签名和广播。 所以我们再试一次，但这次被黑的计算机使用了另一个随机数——R1'。 我们在我们的硬件钱包中签署了相同的交易并将 (R2, s2') 发送回被黑的计算机。 这一次，没有了——我们所有的比特币都不见了。 在这次攻击中，黑客获得了同一笔交易的两个有效签名：(R1, s1, R2, s2) 和(R1', s1', R2, s2')。 这个R2是一样的，但是R=R1+R2和R'=R1'+R2是不一样的。 这意味着黑客可以计算出我们的第二个私钥：s2-s2'=(hash(P,R1+R2,m)-hash(P,R1'+R2,m))⋅pk2 或 pk2 =(s2-s2' )/(散列(P,R1+R2,m)-散列(P,R1'+R2,m))。 我发现这是密钥聚合中最不方便的部分——我们每次都必须使用一个好的随机数生成器才能安全地聚合。

3. MusigMuSig 解决了其中一个问题——流氓密钥攻击将不再有效。 这里的目标是聚合来自多方/多个设置的签名和公钥，而不需要您证明您拥有与这些公钥对应的私钥。 聚合签名对应于聚合公钥。 但在 MuSig 中比特币多签钱包，我们不是直接将所有共同签名者的公钥相加，而是将它们乘以一些参数，使得聚合后的公钥 P = hash(L,P1)×P1 + ... + hash(L,Pn )×Pn。 这里，L = hash(P1,...,Pn) - 这个公钥是基于所有公钥的。 L的非线性特性使得攻击者无法构造特殊的公钥发起攻击。 即使攻击者知道他的 hash(L,Patk)×Patk 应该是什么，他也不能从中推导出 Patk——这就像你想从公钥推导出私钥一样。 签名构建的其他过程与上述过程非常相似。 在生成签名时，每个共同签名者选择一个随机数 ki 并与其他人共享 Ri = ki * G。 然后他们把所有的随机点加起来得到R=R1+…+Rn，然后生成签名si = ki + hash(P,R,m) ⋅ hash(L,Pi) ⋅ pki。 因此，聚合签名为(R, s)=(R1+…+Rn, s1+…+sn)，验证签名的方法同上：s×G = R + hash(P,R,m )×P。

4. Merkle 多重签名 您可能已经注意到，MuSig 和密钥聚合需要*所有签名者签署交易*。 但是如果你要做的是一个2-3个多重签名的脚本呢？ 我们此时可以使用签名聚合，还是必须使用通常的 OP_CHECKMULTISIG 并单独签名？ （译者注：OP_CHECKMULTISIG是比特币验证椭圆曲线多重签名脚本的操作代码）先说答案，可以，只是协议会略有不同。 我们可以开发一个类似于 OP_CHECKMULTISIG 的操作码，除了它检查聚合签名是否对应于公钥 Merkle 树上的一个元素。 比如我们要用公钥P1,P2,P3组成一个2-3的多重签名脚本，就需要用到这些公钥的所有对(P1,P2),(P2,P3),(P1 , P3)构建默克尔树，并在锁定脚本中发布默克尔树的根。 我们在消费比特币时，需要提交一个签名，以及这个签名对应的公钥位于这个树根标记的默克尔树上的证明。 对于一个2-3的多重签名合约，树中只有3个元素，证明只需要2个哈希值——我们要使用的公钥组合的哈希值，和一个邻居的。 对于7-11多重签名脚本，共有11!/7!/4!=330个公钥组合，证明需要8个哈希值。 一般来说，证据中包含的元素数量与多重签名密钥的数量大致成正比，即log2(n!/m!/(nm))。 但是有了 Merkle 公钥树，我们就不必局限于 mn 个多重签名脚本。 我们可以使用公钥的任意组合来创建一棵树。 例如，如果我们有笔记本电脑、手机、硬件钱包和助记词，我们可以构建一个 Merkle 树，让我们可以使用笔记本电脑 + 硬件钱包，手机 + 硬件钱包，或者单独记忆单词来使用比特币. 这是目前的 OP_CHECKMULTISIG 做不到的——除非你使用“IF - Else”风格的流程控制来构造更复杂的脚本。

- 聚合公钥的 Merkle 树。 不仅仅是多重签名——

综上所述

Schnorr 签名很棒，它们解决了块验证中的一些计算开销，还为我们提供了密钥聚合。 后者使用起来有些不便，但我们并不强迫人们使用它——无论如何我们仍然可以使用普通的多重签名方案，使用单独的、非聚合的签名。 我迫不及待地想使用 Schnorr 签名，希望比特币协议能尽快将它们合并。 另外，我真的很喜欢 MuSig，它是一个优雅的解决方案，而且这篇论文很容易理解。 我强烈建议您在闲暇时阅读全文。 （结束）

（结束）

（本文链接较多，可点击左下方“阅读原文”从EthFans网站获取）

原文链接：