How do MuSig2 and FROST compare for multisig key aggregation schemes?

Question

Although FROST is primarily for threshold (k-of-n, k<n) key aggregation schemes (and MuSig2 doesn't support threshold) FROST can support multisig (n-of-n) key aggregation. So what are the upsides and downsides to both for multisig and when might you use FROST over MuSig2 for multisig?

Answer 1

You would generally use MuSig2 for multisig key aggregation as it has fewer communication rounds (2) and less complexity than FROST. The additional complexity is illustrated in this graphic (shared by niftynei on Twitter).

The MuSig2 paper (Nick, Ruffing, Seurin) also states:

In comparison, the scope of our work is restricted to only “n-of-n” multi-signatures, which enables us to optimize for this case and achieve properties which, in the pure DL setting, are unique to multi-signatures, namely non-interactive key generation as well as non-interactive public key aggregation, two features not offered by FROST. A major difference between our work and their work is the cryptographic model. The FROST security proof relies on a non-standard heuristic which models the hash function (a public primitive) used for deriving the coefficients for the linear combination as a one-time VRF (a primitive with a secret key) in the security proof. This treatment requires an additional communication round in FROST preprocessing stage and to disallow concurrent sessions in this stage, resulting in a modified scheme FROST-Interactive. As a consequence, the FROST-Interactive scheme that is proven secure is in fact a three-round scheme and as such differs significantly from the two-round FROST scheme that is recommended for deployment. Komlo and Goldberg [KG20] show that the security of FROST-Interactive is implied by the DL assumption. In contrast, our MuSig2 proofs use the well-established ROM (or alternatively, AGM+ROM) to model the hash function as a random oracle and rely on a falsifiable and weaker variant of the OMDL assumption.

However, Jesse Posner highlighted a couple of benefits of FROST over MuSig2 at this Sydney Socratic. With FROST you can swap out public keys for other public keys or change the multisig scheme, say from a 3-of-3 to a 2-of-2 without needing an onchain transaction. (To do the same with MuSig2 would need an onchain transaction and MuSig2 does not support threshold if that is what you wanted to convert to.) So if you wanted to do this this might be a reason to use FROST over MuSig2.

Correction (June 2023): What is possible with regards to modifying FROST signers and the threshold is discussed in this Nick Farrow gist.

This was also discussed in this London BitDevs Socratic with Tim Ruffing and Elizabeth Crites. It is complicated by there being competing distributed key generation schemes and potentially different FROST standards between Bitcoin/BIPs and IRTF.

TR: I’m also not sure what Jesse is talking about here. I think in the pull request there were some discussions. What you certainly can do, you can downgrade n-of-n to k-of-n. This has been discussed. For example swapping out a key to a new key, maybe Elizabeth knows more, there are some key resharing schemes, I’m not really aware of those.

EC: Yeah. That’s what I was saying about doing the distributed key generation again. Say you run distributed key generation once and everybody has their secret shares of the overall group key. At least the DKG that is used in conjunction in FROST, the original one which is what we prove in our paper, it is based on Shamir’s Secret Sharing. There are some pretty standard ways to reshare using Shamir. That is possible. It is still non-trivial.

TR: You can do resharing but it is more like a forward security thing. You can’t reshare to an entirely new group of signers. You would still trust the old group of signers.

EC: You can transition from some group of signers to a new group of signers also. There are ways to reshare the keys. Or you can keep the same group and reshare a sharing of zero so your shares essentially stay the same, same group, or you can switch the group of signers. But it does involve performing the resharing. There’s a little bit that has to be done there.

MuSig2 and FROST could be used together in the same scheme. There could be a nested MuSig2 setup within a FROST setup or vice versa. Additionally if you wanted to move from a MuSig2 setup to a FROST setup MuSig2 keys can be converted to FROST keys without changing the aggregate public key. That is discussed here.