Why is full blockwide signature aggregation of schnorr signatures non-interactive?

Question

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?

Answer 1

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, 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.