作者：cryptography. 编译：Cointime.com QDD

导言

在我上一篇文章中，我详细介绍了Schnorr签名相对于ECDSA的优越性。我留下了一个悬念：Schnorr的线性签名聚合似乎容易受到最后分享公钥的人的攻击。

因此，我觉得现在是适合详细介绍MuSig的优雅解决方案的时候了。MuSig是由Maxwell、Poelstra、Seurin和Wuille提出的一种协议，它允许共同签署者在不需要相互信任或证明密钥的情况下协同签署一条共同消息。

目前有三个版本的MuSig：

1. InsecureMuSig - 一个过时且不安全的2轮版本

2. MuSig1 - 安全的3轮变体

3. MuSig2 - 更快但稍微不太安全的2轮变体

这里的“轮”指的是签名会话所需的通信往返次数。

本文涵盖了MuSig1：安全的3轮多重签名变体。我的目标是让MuSig1背后一开始看起来很棘手的数学变得更加直观和易于理解。幸运的是，与MuSig2相比，MuSig1要简单得多，这样我的工作就更容易了。MuSig2更加深奥，需要更多的努力才能牢固掌握。但这是另一天的任务了。

我们将从我在上一篇文章中介绍的签名聚合的天真例子开始，并逐步解决每个问题，最终得到MuSig1。

符号表示

MuSig依赖于命名空间哈希函数，用 表示，其中 是哈希的命名空间。命名空间哈希函数是普通的密码哈希函数，但是每个哈希消息都添加了一些常量位，以确保命名空间哈希函数的输出不能被用于其他命名空间。可以这样定义命名空间哈希函数。

不良公钥

让我们回到我在Schnorr文章中的例子中的Alice、Bob和Carol。

我们的三位朋友都希望签署相同的消息，但他们尚不知道彼此的公钥。他们不相信彼此会提供诚实的公钥。没有人愿意分享他们的公钥，因为其他人可能串通一气提供一个恶意计算的不良公钥，从而让恶意方独占最终聚合公钥的所有权。

例如，Carol可以等待Alice和Bob暴露他们的公钥，然后将自己的公钥声明为D‘C＝Dc-Da-Db 在总结所有公钥之后，Alice和Bob将计算出一个聚合公钥D＝Dc ，使Carol独占。

我们需要解决的第一个显而易见的问题是不良公钥攻击，我在Schnorr签名文章中也提到过。

选项1：KOSK

不良公钥可以通过简单要求每个共同签署者证明她知道自己公钥的私钥来避免。这种确认称为知识-密钥（KOSK）。

为什么这样做呢？

Carol基于Alice和Bob的公钥选择了 ，但她选择的点实际上是曲线上的一个随机抽样点，Carol并不知道它的私钥。强制Carol证明KOSK将防止Alice和Bob接受这样一个恶意计算的不良公钥。

问题

这种方法是有缺陷的，因为我想与之进行聚合的并不总是在我完全控制之下。也许我现在想与一个公钥进行聚合，但我只能期望在下周（例如在离散对数合约中）学到它的私钥。也许我想与一个公钥进行聚合，而这个公钥本身是一个聚合的公钥，其组成的私钥由目前不在线的第三方所有。

理想情况下，我们希望避免强制共同签署者证明他们知道私钥，因为他们的密钥可能并不完全属于他们，但他们仍然希望能够与这些密钥合作进行签署。然而，与此同时，我们不能允许共同签署者基于他们的同伴的密钥计算他们的公钥。那么密码朋克该怎么办呢？

选项2：密钥承诺

一个稍微不那么晦涩的解决方案是要求每个共同签署者在公钥之前承诺他们的公钥。每个人在其他人都已经承诺了他们的公钥之后才分享自己的公钥。

想象每个人都将自己的公钥放入信封中，并将这些信封放在桌子上供所有人查看。一旦每个人都把自己的信封放在桌子上（即每个人都完全承诺了），共同签署者就可以开始撕开信封并揭示公钥。任何没有承诺的公钥都是不可信任的。

通过事先承诺公钥，然后验证其他人的承诺，共同签署者确保在签署队伍中没有人基于彼此的公钥计算自己的公钥，即每个公钥都是独立选择的。

示例

实现密钥承诺方案的一种简单方法是要求每个共同签署者在看到其他人的公钥之前，先提供其公钥的哈希值（即承诺）。每个共同签署者在揭示自己的公钥之前，将这个哈希值（也称为承诺）发送给其他人。一旦每个共同签署者收到其他所有人的承诺，他们可以自信地与其余的同伴分享自己的公钥。在收到同伴的公钥后，他们验证所有的承诺，以确保每个人在选择自己的公钥时都诚实行事。

从Alice的角度来看(cb , cc)，她分享ca，并从Bob和Carol那里收到 。一旦她拥有了Bob和Carol的承诺，她分享Da并收到(Db , Dc) 。然后她检查cb等于Hcom（Db）和cc＝Hcom（Dc）。如果或与其各自的承诺不匹配，Alice就不会接受它们。

这种形式避免了“谁先行动”的问题：无论谁首先暴露他们的承诺或公钥，都没有关系，只要每个参与者在分享自己的公钥之前都已经获得了其他人的承诺。命名空间哈希函数的输出不能用于计算不良公钥。命名空间也使得承诺除了验证密钥承诺之外无法用于其他任何用途。同时，它将Alice、Bob和Carol锁定在他们所承诺的公钥上，这些公钥在他们看到彼此的公钥之前就已经被承诺了。

问题

这在纸上是可行的，但在硅上却不太好。它有一个明显的问题：公钥不能在不同的签名会话之间重复使用。

如果Alice与Bob和Carol一起揭示她的公钥，那么她将不能再安全地与一个未知的共同签署者Dave使用该密钥。Dave以全新的方式加入共同签署队伍，因此Alice还不知道他的公钥。Dave现在有机会与Bob或Carol串通。

如果Dave能说服Bob或Carol将Alice的公钥Da给他，Dave可以计算一个恶意的公钥，将Alice排除在新的聚合密钥之外。

Dave在与Alice进行任何通信之前就能够做到这一点，因为他可以从Bob或Carol那里了解到她的公钥。因此，我们现在必须面对密钥承诺解决方案的实际问题：一旦Alice向任何人暴露了她的公钥，她只能与在她揭示公钥之前就已经承诺的公钥一起进行共同签署。任何其他的新公钥都可能是恶意的。

密钥系数

如果最终的聚合密钥不能被恶意方预测，而是可以选择恶意的密钥，那会怎么样？这样，即使一些共同签署者可以选择恶意密钥，最终聚合密钥也将无法使用。这与恶意方选择一个他们不知道任何现有密钥的随机公钥一样。

示例

为了实现这一点，我们可以使用共同签署者的密钥的命名空间哈希来混淆最终的聚合密钥。假设L是Alice、Bob和Carol公钥的确定性（例如字典排序）编码。

一旦所有各方分享了他们的pubkeys，每个联合签名者都可以计算出L的namepaced hash。

中的某些公钥可能是恶意的，但这没有关系，因为接下来的步骤会解决这个问题。在计算聚合密钥时，所有方将所有公钥的总和乘以 。这形成了最终的聚合密钥D。

如果H是密码学上安全的，它将具有抗预象性。Carol将无法找到一个会导致被破坏的聚合密钥的恶意密钥，因为她无法预测Hagg（L）的输出。即使Carol拥有一组大量她控制的密钥，她能做的最好的办法就是猜测和检查随机的恶意密钥，直到她找到一个能产生被破坏的聚合钥匙D。

非交会按照之前的简单聚合示例计算。

共同签署者在彼此之间分享他们的公共非交值后，每个人可以计算聚合的非交值。

回顾之前的文章，来自公钥的Schnorr签名可以通过以下断言进行验证。

为了使聚合签名对这些方程式有效，必须以允许从公钥中分解的方式对签名进行聚合。为了实现这一点，可以按照以下方式计算关于消息的部分签名。

最终的签名将被聚合，以使得α与e并列。。

我们通过这个想法确实取得了一些进展！对于我们的初级多重签名协议来说，恶意密钥攻击不再可行，因为攻击者必须猜测和检查哪个恶意公钥来影响最终聚合密钥，而同时其他人正在不耐烦地等待她的回应。

一种更隐蔽的攻击方式

猜测和检查并不是一个很好的选择，因此Carol无法实际上欺骗Alice和Bob使用她完全控制的密钥。这似乎应该实现我们所有的目标，但要小心！

Carol仍然有机会操纵Alice和Bob签署他们原本不想签署的内容。当我们谈论比特币签名时，伪造相当于完全丢失一个或多个UTXO。这种攻击比恶意密钥攻击更难理解，但不要让它的复杂性蒙蔽了你：这种威胁是非常真实的。它被称为Wagner’s Generalized Birthday攻击。

这种攻击的内部工作方式很复杂，我花了很多精力才完全理解它们。我在这里进行了总结，并将在以后的文章中详细介绍数学的工作原理。

起初，Wagner的攻击似乎与恶意密钥攻击类似，因为它要求攻击者等待其他共同签署者首先揭示一些内容，并根据揭示的信息计算出一个响应。虽然这种攻击需要一些大量的计算，但大部分工作可以由攻击者预先计算。

在与Alice和Bob进行大量并发的签名会话之后，Carol等待她的共同签署者首先揭示他们的非交值 。Carol给Alice和Bob一个虚假的非交值 。Alice和Bob毫不知情地使用 签署了一些表面上无害的消息。如果执行正确，Carol可以将这些无害消息上的签名聚合成一个伪造的签名，用于Alice和Bob从未看到的恶意消息。幸运的是，对于Carol的CPU来说，她可以在要求Alice和Bob签署任何东西之前预先计算大部分重量级计算，并且她可以打开的并发签名会话越多，在预先计算阶段需要做的工作就越少。

这似乎非常神奇，但实际上不过是一些非常简洁的分析数学与一个优雅的搜索算法（具体来说是Wagner的算法）相结合的结果。请参阅这篇论文，了解将该攻击应用于CoSi算法的完整描述，该算法类似于MuSig1，但建立在这样一个假设上，即每个共同签署者必须提供一个知识-密钥证明以避免恶意密钥攻击。

出于简洁性的考虑，我省略了这种攻击的全部工作原理，但重要的是要知道：Wagner的攻击取决于攻击者在揭示自己的非交值之前学习他的受害者的公共非交值。如果攻击者不能将自己的非交值选择为受害者非交值的函数，那么他所做的所有预先计算都将被浪费。

非交承诺

为了防止Carol计算出R‘c作为非交值（Ra ，Rb）的函数，我们可以重用选项2中的承诺概念，但应用于非交而不是公钥。

共同签署者不直接分享他们的公共非交值，而是首先对其非交值进行哈希，并将哈希输出作为对同行的承诺发送。在收到所有共同签署者的承诺后，共同签署者可以公开他们的真实公共非交值。一旦每个人都分享了承诺和非交值，所有人都可以进行验证并欢庆，确信在共同签署的团队中没有人试图更改他们的非交值。

这样可以避免Wagner的攻击，因为攻击者无法控制每个并发签名会话中使用的最终聚合的非交值。只要签名团队中至少有一方是诚实的，最终聚合的非交值将是一个无偏的随机曲线点，由每个共同签署者共同选择（正如应该的那样）。

示例

Alice、Bob和Carol各自随机选择一个秘密非交值，并像以前一样使用它来计算他们的公共非交值。

与先前的协议不同，他们不立即将R值与彼此共享。而是按照以下方式计算承诺值（ta, tb, tc）。

他们可以按任意顺序与对方共享（ta, tb, tc）。因为每个承诺对其原像（非交值）不透露任何信息，因此没有任何一方通过等待接收其他人的承诺来获得任何信息。

例如，只要Alice在分享Ra之前收到（tb, tc），并且在收到Rb和Rc后验证它们与承诺值tb和tc匹配，她就不会受到风险。请注意，Alice在同时拥有tb和tc之前不能暴露她的非交值Ra。即使她从Bob那里收到了tb，她也不能将Ra发送给他，因为Bob和Carol可能串通一气，或者他们可能是同一个人。在Carol提交到tc之前将Ra 交给Bob可能会让Carol提供一个恶意非交值。

然后，签名将按照上一节中讨论的方式计算和聚合。

最后的一个注意事项

好吧，我必须承认我对下一个设计选择感到困惑。现在，这个协议似乎是安全的，但是我描述的共同签署协议与MuSig1论文中描述的官方协议之间仍然有一个小的差异。

回顾一下，我们定义 L为Alice、Bob和Carol的公钥的确定性（排序）编码。

然后，我们将L 哈希为签署团队的密钥系数。将此系数与每个方的公钥相乘，以生成聚合的公钥D。

在计算签名时，每个共同签署者通过将他们的私钥乘以相同的密钥系数 α 来计算他们的部分签名。

真正的MuSig请站出来？

在我刚刚描述的协议中，我们使用了一个对整个团队共享的单个密钥系数 。在真正的MuSig1协议中，每个共同签署者都有自己的密钥系数，其他所有人可以独立计算。

每个共同签署者特定的密钥系数（αa，αb，αc）是由与某个特定共同签署者的公钥连接后进行哈希计算得到的。

在聚合公钥时，D将是每个公钥乘以其相应的密钥系数的和。

每个共同签署者可以轻松计算出他们的同行的密钥系数并独立确定 ，前提是他们拥有整个团队的公钥的完整列表 。

在签名时，每个共同签署者通过将他们自己的密钥系数与他们的私钥相乘来计算部分签名。

聚合签名可以分解如下。

但为什么呢？

好问题。我在网上找不到这个决定的任何理由，包括MuSig1白皮书。这种方法与全局密钥系数 之间的唯一代数区别在于，使用特定于密钥的系数时，它们无法与私钥同时从各项中分解出来，因为在每个术语 ， 等中它们是不同的。但是，我不清楚这个显然有意的设计选择的动机。对于大型签名团队来说，全局密钥系数将更快，因为每个共同签署者只需要运行一次，而不是为队伍中的每个共同签署者运行一次。

可能是MuSig1的作者选择这样做是为了简化他们的安全证明，而不是因为这对于方案本身的安全性是必要的。然而，最好不要去实现带有全局密钥系数的MuSig1，以防万一。

如果有人知道这个选择背后的意图或者为什么全局密钥系数 会是坏消息，请告诉我！或者提交一个拉取请求来修复这篇文章。

真正的MuSig1协议

经过漫长的探索，我们终于到达了几乎完全合理的MuSig1协议。让我们再给Alice、Bob和Carol一次合作签名的机会。

1. 密钥聚合

共同签署者彼此分享他们的公钥。现在每个人都可以计算其他人的密钥系数，并因此计算聚合的公钥。

这些伪随机密钥系数 防止任何共同签署者执行恶意密钥攻击，因为他们无法通过分析确定要提供的哪个恶意公钥来控制 。

2. 非交值承诺

每个共同签署者随机选择一个秘密非交值，并私下计算相应的公共非交值。他们将公共非交值哈希为承诺。

非交值承诺（ta, tb, tc）可以在共同签署者之间自由共享。请注意，非交值承诺可以安全地缓存和预共享以提高往返性能，而不危及安全性。

3. 消息选择

必须协商要签署的消息。

重要的是，在揭示非交值之前就要确定 ，否则Wagner的攻击将再次出现。

4. 非交值揭示

共同签署者彼此揭示他们的非交值（Ra, Rb, Rc），并验证非交值与相应的承诺值（ta, tb, tc）是否匹配。

如果任何人的非交值与承诺不匹配，协议必须强制执行丢弃暴露的非交值，并且不会再次使用它们。也可以使用新的非交值从第2步重新尝试。

一旦共同签署者拥有其同行的公共非交值，他们可以计算聚合的公共非交值。

5. 挑战哈希

非交值R、聚合的公钥D和消息m与一个命名空间哈希函数进行哈希运算，以产生挑战e。

每个共同签署者可以独立计算 ，一旦 确定，且所有非交值已知。

6. 部分签名

共同签署者通过将他们的密钥系数、私钥和挑战e相乘，再加上他们的秘密非交值，计算他们的部分签名（sa,sb,sc）。

7. 签名聚合

部分签名可以随意与其他参与者共享。

一旦每个共同签署者都有了（sa,sb,sc），他们可以将它们聚合成最终的签名(R,s)。

共同签署者已经在第4步学习到了聚合的非交值R。

请注意，这里存在“谁先行动”的问题。Alice、Bob和Carol不能同时了解彼此的部分签名。谁最后分享他们的签名，谁可能会“逃走”，也就是说，学到最终聚合签名的秘密 而不让任何其他人计算。

这通常被称为免费选择问题，不幸的是没有办法解决它：总有人会先学到 ，所以团队签署的内容最好设置为一个方案，一个方可能有使用签名的选项，而其他人则不能。

8. 签名验证

验证这个签名与验证任何正常的Schnorr签名(R,s)使用单个公钥D完全相同，只要验证者知道使用正确的哈希函数Hsig。

对于聚合签名来说，这将是正确的。

回顾聚合非交值和聚合公钥的定义。

因此：

结论

与MuSig2相比，我更喜欢MuSig1，因为与MuSig2的神奇相比，它非常简单。

MuSig2有一些花哨的技巧，可以避免整个非交值承诺问题，同时又不让其容易受到Wagner的攻击。也许将来我会讨论MuSig2，但我认为下一步我想更详细地讨论Wagner的攻击。令人惊讶的是，这样一个表面上看来不可能的攻击通过一个简单的列表搜索算法变得微不足道，我认为这个机制非常值得讨论。