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?

  • 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. Jun 23 at 6:02
  • 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? Jun 23 at 6:13

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.

  • 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 Jun 23 at 6:10
  • 2
    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. Jun 23 at 6:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.