<p>First a definition:</p>
<ul>
<li>A <strong>multisignature</strong> scheme is a scheme where multiple parties jointly produce a signature on a <em>single</em> message, which can be verified against the set of all participating public keys.</li>
<li>A <strong>aggregated signature</strong> scheme is a scheme where multiple parties jointly produce a signature, each on their own message, which can be verified against the set of all (pubkey,message) pairs.</li>
</ul>
<p>MuSig is a multisignature scheme, which happens to also support something called <strong>key aggregation</strong>. Key aggregation means that the signature that comes out can also be <em>alternatively</em> verified by a verifier who does not know the individual signers' public keys, but only an aggregation of them. Key aggregation is unrelated to signature aggregation; we're still talking about a multisignature scheme here and not an aggregated signature scheme.</p>
<p>Next is the concept of interactivity: at which point do the signers in either of these schemes need to interact? All (currently known) Schnorr-based signature schemes (including multisignature schemes like MuSig) are interactive; either at setup time, or at signing time. That means that at some point, all signers need to be aware of each other and communicate with each other in order to produce the joint signature.</p>
<p>When we're talking about block wide aggregated signatures, we need two things:</p>
<ul>
<li><em>An aggregated signature scheme</em> - not a multisignature scheme. Every transaction is obviously its own message, that its participants sign off on. Since transactions are independently created from blocks, you cannot expect all participants to sign the same message.</li>
<li><em>Non-interactivity</em>. It cannot be required that all parties whose transactions are going to be included in the same block communicate with each other. Transactions may have been pre-signed years before they get included, to give an extreme example.</li>
</ul>
<p>MuSig is neither. It is possible to construct an aggregated signature scheme analogously to it, as is described in the <a href="https://eprint.iacr.org/2018/068" rel="nofollow noreferrer">MuSig(1) paper</a>, Appendix A, though there are some overcomeable pitfalls to avoid. The interactivity part is however unsolvable: no discrete logarithm based signature schemes that are known support non-interactive aggregation. Non-interactive aggregation signature schemes are possible using pairing-based cryptography however, but these add additional security assumptions.</p>

CC BY-SA 4.0
2021-06-23T06:10:09.830Z
First thanks a lot for the review of notation and providing clear definitions. Being only a hobby cryptographer I most certainly mixed up key and signature aggregation in my mental representation! However you say the interactivity part is unsolvable. Is that provable or do we just not know a way of doing it? While saying we don't know a way of doing this is technically an answer to my question I am curious if we have some theoretical insight of why this is hard / has not been found yet
Rene Pickhardt
CC BY-SA 4.0
2021-06-23T06:12:00.717Z
I don't think there is quite a proof that this is impossible, but I can give some intuition: these signature schemes require (good) randomness to be provided by all participants, and they need to agree on that randomness before they can sign. This agreement appears to necessitate at least one round of interaction between them. The pairing-based schemes that do support non-interactive aggregation all involve no randomness.
Pieter Wuille
CC BY-SA 4.0
2021-12-27T13:19:40.210Z
“*All (currently known) Schnorr-based signature schemes (including multisignature schemes like MuSig) are interactive; either at setup time, or at signing time.*”. What are some examples of schemes that require interaction only at setup time?
runeks
CC BY-SA 4.0
2021-12-27T13:42:16.183Z
MuSig2 has two rounds, the first of which can be precomputed (i.e., done before the message is known). If you do that, the first round effectively becomes part of the setup, which is then interactive, but signing is only a single round.
Pieter Wuille
CC BY-SA 4.0
2021-06-23T05:56:54.980Z
2021-06-23T05:56:54.980Z
Pieter Wuille
<p>I can only think of the MuSig paper describing how Rouge attacks are prevented by also committing to the public key of all signers. But as far as I understand the case of multisig is not the same as later adding all signatures?</p>
<p>I do however see the issue that adding signatures requires the signatures being produced on the same message wich if they are only produced for every tx is not given. Can someone confirm that this is the reason why it doesn't work in an interactive way as people signing tx would already have to know which other tx will be in the block?</p>

CC BY-SA 4.0
2021-06-23T06:02:12.240Z
The question sounds a bit confused - Schnorr-based signature aggregation *is* interactive, and that is the problem. I hope I've addressed it in my answer, but let me know if I missed it.
Pieter Wuille
CC BY-SA 4.0
2021-06-23T06:13:36.867Z
Yes it was and yes you did. Would you allow me to edit my question later by moving part of your definitions to the question?
Rene Pickhardt
<signature><message-signing><schnorr-signatures>
Why is full blockwide signature aggregation of schnorr signatures non-interactive?
Rene Pickhardt
# Why is full blockwide signature aggregation of schnorr signatures non-interactive?

(Asked by: username_0 on 2021-06-23)

I can only think of the MuSig paper describing how Rouge attacks are prevented by also committing to the public key of all signers. But as far as I understand the case of multisig is not the same as later adding all signatures?

I do however see the issue that adding signatures requires the signatures being produced on the same message wich if they are only produced for every tx is not given. Can someone confirm that this is the reason why it doesn't work in an interactive way as people signing tx would already have to know which other tx will be in the block?

**Tags:** signature, message-signing, schnorr-signatures

> **Comments:**
> **username_1**: The question sounds a bit confused - Schnorr-based signature aggregation *is* interactive, and that is the problem. I hope I've addressed it in my answer, but let me know if I missed it.  
> **username_0**: Yes it was and yes you did. Would you allow me to edit my question later by moving part of your definitions to the question?  

---

## 1 answers

### Answer by username_1 on 2021-06-23. Score: 4

First a definition:

* A **multisignature** scheme is a scheme where multiple parties jointly produce a signature on a *single* message, which can be verified against the set of all participating public keys.
* A **aggregated signature** scheme is a scheme where multiple parties jointly produce a signature, each on their own message, which can be verified against the set of all (pubkey,message) pairs.

MuSig is a multisignature scheme, which happens to also support something called **key aggregation**. Key aggregation means that the signature that comes out can also be *alternatively* verified by a verifier who does not know the individual signers' public keys, but only an aggregation of them. Key aggregation is unrelated to signature aggregation; we're still talking about a multisignature scheme here and not an aggregated signature scheme.

Next is the concept of interactivity: at which point do the signers in either of these schemes need to interact? All (currently known) Schnorr-based signature schemes (including multisignature schemes like MuSig) are interactive; either at setup time, or at signing time. That means that at some point, all signers need to be aware of each other and communicate with each other in order to produce the joint signature.

When we're talking about block wide aggregated signatures, we need two things:

* *An aggregated signature scheme* - not a multisignature scheme. Every transaction is obviously its own message, that its participants sign off on. Since transactions are independently created from blocks, you cannot expect all participants to sign the same message.
* *Non-interactivity*. It cannot be required that all parties whose transactions are going to be included in the same block communicate with each other. Transactions may have been pre-signed years before they get included, to give an extreme example.

MuSig is neither. It is possible to construct an aggregated signature scheme analogously to it, as is described in the [MuSig(1) paper](https://eprint.iacr.org/2018/068), Appendix A, though there are some overcomeable pitfalls to avoid. The interactivity part is however unsolvable: no discrete logarithm based signature schemes that are known support non-interactive aggregation. Non-interactive aggregation signature schemes are possible using pairing-based cryptography however, but these add additional security assumptions.

> **Comments:**
> **username_0**: First thanks a lot for the review of notation and providing clear definitions. Being only a hobby cryptographer I most certainly mixed up key and signature aggregation in my mental representation! However you say the interactivity part is unsolvable. Is that provable or do we just not know a way of doing it? While saying we don't know a way of doing this is technically an answer to my question I am curious if we have some theoretical insight of why this is hard / has not been found yet  
> **username_1**: I don't think there is quite a proof that this is impossible, but I can give some intuition: these signature schemes require (good) randomness to be provided by all participants, and they need to agree on that randomness before they can sign. This agreement appears to necessitate at least one round of interaction between them. The pairing-based schemes that do support non-interactive aggregation all involve no randomness.  
> **username_2**: “*All (currently known) Schnorr-based signature schemes (including multisignature schemes like MuSig) are interactive; either at setup time, or at signing time.*”. What are some examples of schemes that require interaction only at setup time?  
> **username_1**: MuSig2 has two rounds, the first of which can be precomputed (i.e., done before the message is known). If you do that, the first round effectively becomes part of the setup, which is then interactive, but signing is only a single round.  

---

