6

The way I've understood Schnorr signatures is that multiple parties can combine their signatures into a one shared signature, thus obfuscating the number of participants involved in the signature scheme.

I wonder: is it possible for one of those signatures to itself be an aggregate signature? And can we keep on doing this multiple levels down?

EDIT: Here's a diagram to clarify my question. The grey nodes represent aggregate signatures, the black nodes represent keys/entities. In this example, A doesn't necessarily need to know all the complexity hidden below K2.

enter image description here

1 Answer 1

8
+50

TL;DR: depending on what you mean, there is probably no published scheme with a security proof, but there is hope for such a scheme.

First, a few clarifications

Aggregation is just a concept, not an actual protocol, and there are many ways of accomplishing that. It is made significantly simpler due to Schnorr's linearity property, but the security of a scheme depends on the specifics of the protocol, and cannot be answered generically.

Signature aggregation and key aggregation are not the same thing, and perhaps you're confusing them:

  • Signature aggregation is the ability for multiple signers to jointly produce a single compact signature that can be verified by a verifier that knows all the public keys and messages (as each signer can choose their own message). While signature-aggregation of variants of Schnorr signatures can be constructed, Bitcoin's Schnorr functionality (BIP340) does not support this.
  • A multi-signature scheme is like a signature aggregation scheme, except that all signers are signing the same message. Note that this isn't the same as what is called "multisig" in the context of Bitcoin.
  • Key aggregation is a multi-signature scheme for which the result can be verified by a verifier who only knows some aggregation of the keys. BIP340 is compatible with these (because the verifier is a simple Schnorr verifier that sees a single key), in the form of the MuSig family of algorithms (MuSig, MuSig2, MuSig-DN), or MSDL-pop. However, it's important to note that these protocols consist of multiple algorithms:
    • There is the key aggregation function, which given a number of public keys, computes the aggregate key for those (it is generally not just adding the keys together).
    • There is the signing protocol, which consists typically of multiple rounds of interactions between the signers (2 or 3), and the final outcome is a single signature valid for the aggregate key. It is not simply "adding up the signatures", and having things magically work.

Defining your question

I'm going to interpret your question as follows:

Does a secure key-aggregation scheme, compatible with Bitcoin's BIP340 signatures, exist where keys can be aggregated hierarchically without signers having knowledge about their "niece/nephew" keys (i.e., permits signing with key agg(B,K1) where K1=agg(C,D), but B does not need to be aware of the fact that K2 is an aggregate on its own or of the identity of C and D).

This "without knowledge about" part is essential. Without that part, a trivial solution exists: just "flatten" all the nesting (i.e., transform it into signing with agg(B,C,D) in the example above).

Note that all Schnorr key aggregation schemes require signers to be aware of at least the aggregated key they're signing for, and interact with their co-signers, so it's certainly not possible to accomplish in a setting where signers don't have knowledge about their siblings even.

Back to your question

As far as I know, no published scheme actually describes security in the nested settings.

However, MuSig2 was actually specifically designed to be compatible with nesting. The MuSig2 paper does not describe nesting because the nesting construction has no security proof yet (confirmed by Tim Ruffing in a comment below), and other advantages of MuSig2 over MuSig made it worth publishing on its own. (I know this from private communication with the paper's authors).

What this means is that it is fairly simple to modify the MuSig2 scheme to do what you're asking for (but, beware, there is no published security proof, so while it may work in that it produces valid signatures, that doesn't mean it doesn't open up the signers to attacks):

  • The aggregation function is allowed to be nested (i.e., can be applied on a key that is itself the result of aggregation).
  • In the first signing round, the "leaves" of the hierarchy produce 2 (or 4) nonces as normal, and send them "upwards" the tree. The inner nodes of the tree simply add them point-wise (i.e., given (R1a, R2a), (R1b, R2b) from sub-signers a and b, send on (R1a+R1b, R2a+R2b)).
  • In the second signing round, the multipliers do not depend on just the aggregate key, but on all intermediary aggregate keys between the signer and the root of the tree as well.

This is not possible with MuSig (1), because it has a precommitment round where all signers publish a hash of the nonce they're going to use. Given the hashes of the nonces of your "children", you cannot compute the hash of their sum. Trying to avoid this problem by first running both round 1 and 2 of the children before running round 1 of the parent is known to be insecure (other signers can trick you into revealing your private key this way).

1
  • 2
    The CoSi scheme supported this kind of nested aggregation but was broken by eprint.iacr.org/2020/945.pdf. However, it was broken not because of the nested key aggregation but because of the same reasons why the initial version of MuSig1 was broken. And these issues have been resolved with MuSig2. So we (the MuSig2 authors) conjecture that the protocol you sketch here is secure but noone has worked out a formal security proof so far. Nov 30, 2021 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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