<p>SpeedyMusig requires each signer to collect all n nonce pairs (Ri,Si) as input to the hash which determines how they are combined for the final nonce.  Musig2 allows a single untrusted aggregator to collect the (Ri,Si) for all n signers and send only the aggregate (R,S) to each signer.  So, SpeedyMusig requires O(n^2) communication, whereas Musig2 can be done in O(n) with a dedicated aggregator.</p>
<p>However, I am not sure the security is the same.  SpeedyMusig says the signer much check the list (Ri,Si) to insure that no pair occurs more than once, in order for their security proof to be valid.  If this check is also needed for Musig2, then the O(n) communication pattern would depend on the supposedly untrusted aggregator to do this correctly.</p>
<p>Musig2 uses more complicated public key aggregation, requiring n exponentiations, to solve the rogue key problem, whereas SpeedyMusig has simple key aggregation under Verified Key model.  I am not sure if this interacts with the above issue somehow, or whether there is alternative security proof or some other aspect of operation that doesn't need the &quot;no duplicates&quot; assumption.</p>
<p>For myself, I would really like to combine these 2 approaches, using the O(n) nonce aggregation pattern of Musig2 but with the simple public key aggregation of SpeedyMusig.</p>

CC BY-SA 4.0
2022-08-05T14:56:54.720Z
(Disclosure: I'm one of the authors of the MuSig2 paper.) I'm pretty sure that the two mentioned drawbacks in SpeedyMuSig (less flexible nonce aggregation and rejecting duplicate nonces) are artifacts of the proof technique used by CKM, and the scheme would be secure with O(n) nonce aggregation and without the check for duplicate keys. Disclaimer: As long as we don't have a proper proof that establishes the security of the modified, "I'm pretty sure" is not a formal proof and there can be dragons. Don't implement a scheme because someone said in comment on StackExchange that it's secure.
real-or-random
CC BY-SA 4.0
2022-08-25T23:36:27.640Z
Thanks @real-or-random, would you have any thoughts on musig2 + BIP-32 style nonces?  https://bitcoin.stackexchange.com/questions/115036/musig2-with-bip-32-style-nonce-chain
user1055568
CC BY-SA 4.0
2022-08-04T15:52:32.457Z
2022-08-04T15:52:32.457Z
user1055568
<p>There is a comparison table included in the Crites, Komlo, Maller paper.</p>
<p><a href="https://i.sstatic.net/98Cxp.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/98Cxp.png" alt="speedymusig" /></a></p>
<p>The only downsides (included in the table and the paper) of SpeedyMuSig are the additional group exponentiations in the KeyGen phase and KeyVerify phases.</p>
<p>The MuSig2 <a href="https://eprint.iacr.org/2020/1261.pdf" rel="nofollow noreferrer">paper</a> (Nick, Ruffing, Seurin) does address the proof of possession approach:</p>
<blockquote>
<p>One way to generically prevent rogue-key attacks is to require that users prove possession of
the secret key, e.g., by attaching a zero-knowledge proof of knowledge to their public keys [RY07;
BDN18]. However, this makes key management cumbersome, complicates implementations, and is
not compatible with existing and widely used key serialization formats.</p>
</blockquote>

CC BY-SA 4.0
2022-06-27T09:44:18.260Z
2022-07-17T11:17:41.790Z
2022-07-17T11:17:41.790Z
Michael Folkson
<p>This <a href="https://eprint.iacr.org/2021/1375.pdf" rel="nofollow noreferrer">paper</a> (Crites, Komlo, Maller) on the security of Schnorr multisig and threshold signature schemes introduces a new variant of MuSig2 called SpeedyMuSig that includes proofs of possession and faster key aggregation.</p>
<p>As the paper states:</p>
<blockquote>
<p>This is because proofs of possession allow the aggregate public key under which the multisignature is formed to be simply the
product of the signers’ individual public keys. It involves group multiplications instead of costly group exponentiations and
remains secure against rogue-key attacks.</p>
</blockquote>
<p>What are the downsides or costs of SpeedyMuSig in comparison to MuSig2?</p>

<multi-signature><schnorr-signatures><musig>
How does SpeedyMuSig compare to MuSig2?
Michael Folkson
# How does SpeedyMuSig compare to MuSig2?

(Asked by: username_0 on 2022-06-27)

This [paper](https://eprint.iacr.org/2021/1375.pdf) (Crites, Komlo, Maller) on the security of Schnorr multisig and threshold signature schemes introduces a new variant of MuSig2 called SpeedyMuSig that includes proofs of possession and faster key aggregation.

As the paper states:

> This is because proofs of possession allow the aggregate public key under which the multisignature is formed to be simply the
> product of the signers’ individual public keys. It involves group multiplications instead of costly group exponentiations and
> remains secure against rogue-key attacks.

What are the downsides or costs of SpeedyMuSig in comparison to MuSig2?

**Tags:** multi-signature, schnorr-signatures, musig


---

## 2 answers

### Answer by username_1 on 2022-08-04. Score: 2 | Accepted answer

SpeedyMusig requires each signer to collect all n nonce pairs (Ri,Si) as input to the hash which determines how they are combined for the final nonce. Musig2 allows a single untrusted aggregator to collect the (Ri,Si) for all n signers and send only the aggregate (R,S) to each signer. So, SpeedyMusig requires O(n^2) communication, whereas Musig2 can be done in O(n) with a dedicated aggregator.

However, I am not sure the security is the same. SpeedyMusig says the signer much check the list (Ri,Si) to insure that no pair occurs more than once, in order for their security proof to be valid. If this check is also needed for Musig2, then the O(n) communication pattern would depend on the supposedly untrusted aggregator to do this correctly.

Musig2 uses more complicated public key aggregation, requiring n exponentiations, to solve the rogue key problem, whereas SpeedyMusig has simple key aggregation under Verified Key model. I am not sure if this interacts with the above issue somehow, or whether there is alternative security proof or some other aspect of operation that doesn't need the "no duplicates" assumption.

For myself, I would really like to combine these 2 approaches, using the O(n) nonce aggregation pattern of Musig2 but with the simple public key aggregation of SpeedyMusig.

> **Comments:**
> **username_2**: (Disclosure: I'm one of the authors of the MuSig2 paper.) I'm pretty sure that the two mentioned drawbacks in SpeedyMuSig (less flexible nonce aggregation and rejecting duplicate nonces) are artifacts of the proof technique used by CKM, and the scheme would be secure with O(n) nonce aggregation and without the check for duplicate keys. Disclaimer: As long as we don't have a proper proof that establishes the security of the modified, "I'm pretty sure" is not a formal proof and there can be dragons. Don't implement a scheme because someone said in comment on StackExchange that it's secure.  
> **username_1**: Thanks @username_2, would you have any thoughts on musig2 + BIP-32 style nonces?  https://bitcoin.stackexchange.com/questions/115036/musig2-with-bip-32-style-nonce-chain  

---

### Answer by username_0 on 2022-06-27. Score: 0

There is a comparison table included in the Crites, Komlo, Maller paper.

[![speedymusig](https://i.sstatic.net/98Cxp.png)](https://i.sstatic.net/98Cxp.png)

The only downsides (included in the table and the paper) of SpeedyMuSig are the additional group exponentiations in the KeyGen phase and KeyVerify phases.

The MuSig2 [paper](https://eprint.iacr.org/2020/1261.pdf) (Nick, Ruffing, Seurin) does address the proof of possession approach:

> One way to generically prevent rogue-key attacks is to require that users prove possession of
> the secret key, e.g., by attaching a zero-knowledge proof of knowledge to their public keys [RY07;
> BDN18]. However, this makes key management cumbersome, complicates implementations, and is
> not compatible with existing and widely used key serialization formats.


---

