MuSig2 support

[Sjors]

BlockstreamResearch/secp256k1-zkp#131 adds MuSig2 support to secp256k1-zkp, which is an experimental fork of secp256k1. I think it would be useful to have a (series of) draft pr(s) implementing support for this in Bitcoin Core. If only to make it easier to actually test MuSig2.

MuSig2 paper: "MuSig2: Simple Two-Round Schnorr Multi-Signatures" (https://eprint.iacr.org/2020/1261)

To simplify things a bit, I'm assuming a things for now:

1. The Bitcoin Core wallet coordinates setup and also takes the initiative for proposing a new transaction
2. Two communication rounds are needed for signing (no storing nonces in advance)
3. Only key path spending (for script path spending we probably want miniscript support first anyway) (probably not an issue)
4. Our wallet has private keys (after setup we import the musig descriptor and mark that as active)

One challenge is how to include secp256k1-zkp (I suppose a proof of concept PR can just swap out the git subtree).

Wallet setup

We obtain an xpub with origin info from ourselves and the other signers. Perhaps at the BIP 87 derivation of m/87'/0'/0'.

Todo:

• rpc: add path to gethdkey #22341
• ...

Pass them into secp256k1_musig_pubkey_agg. Apparently it's possible to aggregate an xpub in one go, instead of calling this function on each and every derived key. But there's some caveats, perhaps @jonasnick can clarify:

• This results in a new xpub, which can be used just fine by a watch-only wallet (which doesn't need to know MuSig2 was involved); but
• agg(xpubA, xpubB)/* != agg(xpubA/, xpubB/)
• what about the chain codes?
• do we need to track xpub and/or origin info for the other signers? (this seems practical in any case when dealing with a dumb external signer)

Todo:

• RPC or bitcoin-util / bitcoin-wallet command that takes xpub(s), etc and does this
  • since we have to call libsecp functions, a Python script doesn't seem like the right approach
  • the result could be a fresh (public key) descriptor, that is either automatically or manually imported in the wallet
• add musig2 descriptor (which tracks our own xpub at minimum, as well as the aggregated xpub or/and the other xpubs)

Round one nonces

One nice aspect of MuSig2 is that the nonces required for round 1 can:

1. be generated in advance
2. be regenerated if a signer loses them
3. support only 1 cosigner if that's easier

So it's tempting to collect a bunch of nonces during the setup. However this is very non-trivial, so let's not for now... #23326 (comment)

Instead, we generate our nonce and request one from each participant. Probably the most practical way is to create a PSBT, put our first nonce in it, pass it to the next signer who reads ours and adds theirs. We then get the PSBT back from the last signer.

• add PSBT fields

Round two: signing

Perform step 1 and 2 of signing process on the nonces we have.

Generate our round 2 nonce with secp256k1_musig_nonce_gen (step 4) and add those to the PSBT

Pass the PSBT to the other signer(s):

1. if there's only 1 co-signer they can generate their nonce and secp256k1_musig_partial_sign in one go, and give us the result
2. if there's 2+ co-signers???

Add our partial signature:

• secp256k1_musig_partial_sign (by walletprocesspsbt?)

Generate full signature:

• have one or more of PSBT method(s) do secp256k1_musig_partial_sig_agg (does not need wallet)

Profit.

Updates
2021-10-20 18:48 UTC: forget about pre committing nonces for round 1, instead use two signing rounds: #23326 (comment)

[sipa]

@Sjors

My thinking was that once it's deemed ready, we'd forward port the MuSig(2) support in secp256k1-zkp to libsecp256k1. That'd solve the issue of implementation compatibility.

Beyond that, there are indeed a number of things that need to be decided:

• How to integrate into descriptors. One possibility is to only support an agg fragment as leaf key (e.g. agg(xpub1/.../*,xpub2/.../*)), but it's also possible I think to support treating agg of xpubs as a new "xpub" itself (e.g. agg(xpub1/...,xpub2/...)/*) for example by defining the aggregated chaincode as a hash of the child chaincodes. This complicates signing further, however, though I don't think there are fundamental problems with this (I've had some discussions with @jonasnick with this).

• Signing support feels like it'd be pretty much orthogonal to the descriptors integration. My thinking is that there is no need to restrict it - whatever our descriptors signing logic support will pretty much automatically be supported by MuSig signing code once we have it. tr() descriptors right now are very limited (only key path, and pk(X) leaves), but if that gets extended, all places that were key expressions are supported in there should also deal fine with MuSig keys.

• I think you're misunderstanding how the pre-generated nonce variant of MuSig2 works. It isn't sufficient to generate the nonces ahead of time - they also need to be distributed to the co-signers ahead of time (in such a way that they know which nonce is going to be used with which signing attempt, before that signing attempt is made). This is both logistically hard (it's essentially incompatible with descriptors, as you can't go and generate/pay to addresses before nonce material has been exchanged), and a huge footgun (all participants need to increment positions in lockstep, make sure never to reuse, need to re-distribute nonces in case of loss of key material; backups are a huge hazard, ...). In my view, this variant is for very specialized applications where latency matters, and you have a well-defined protocol between known-to-be-online co-signers already that it can be integrated into (e.g. I can imagine Lightning using them). In a more "general purpose" setting like Bitcoin Core should probably cater to, it feels much safer & saner to stick to the non-interactive setup + 2-round signing version of the protocol.

• PSBT extensions need to be defined for both rounds (for announcing which public nonces every co-signing is going to use, and for the partial signatures).

[Sjors]

it's deemed ready, we'd forward port the MuSig(2) support in secp256k1-zkp to libsecp256k1.

That makes sense, but I suspect more people will review the secp256k1 PR, and more practical issues will come to light, if there's a (draft) Bitcoin Core integration. So it's a bit of chicken-egg.

It isn't sufficient to generate the nonces ahead of time - they also need to be distributed to the co-signers ahead of time (in such a way that they know which nonce is going to be used with which signing attempt, before that signing attempt is made)

Ah, the first constraint might be solvable by exporting it along with descriptors (which hardware wallets should store anyway for change detection). But the second constraint makes that a lot more complicated.

it feels much safer & saner to stick to the non-interactive setup + 2-round signing version of the protocol

That makes sense. Two rounds is annoying when any physical travel is involved, but it does seem much more realistic to implement in the near term. For a simple computer + hardware wallet setup two rounds are no problem; just a matter of calling HWI twice.

I updated the description to reflect this.

[Rspigler]

If the non-interactive setup of MuSig 2 without preprocessing is what is being discussed, have the pros/cons of MuSig-DN been reconsidered? They would now be the same number of rounds, with MuSig-DN having all the security benefits of deterministic nonces (with the costs of implementation complexity and increased verification times).

[Sjors]

From the MuSig-DN paper: "This makes it possible to realize MuSig-DN efficiently using zero-knowledge proof frameworks for arithmetic circuits which support inputs given in Pedersen commitments, e.g., Bulletproofs. "

In other words this adds a cryptographic assumption, as well as additional dependencies to implement said cryptography.

[sipa]

So the advantages of MuSig-DN over MuSig:

• Stateless signing: signers don't need any memory between signing sessions (either within rounds, or across rounds).
• Compared to MuSig1: one fewer round (but 2-round MuSig2 has the same number of rounds).

It's easy to think MuSig-DN also avoids the need for randomness at signing time as well. While that's true on its face, MuSig2 can avoid it too: as the signers need state anyway, and a private key, they can use a counter in their state together with the private key to generate randomness (use H(counter++ || privkey) as RNG).

The disadvantages are:

• MuSig-DN is far slower (~1000x) in terms of CPU cost.
• Complicates setup (in addition to participant keys, co-signers also need to know each other's 512-bit host key) compared to 2-round MuSig2 (but 1-round MuSig2 is harder still).
• Implementation complexity (needs arithmetic over two different curves (not secp256k1), needs Bulletproofs or other NIZK proof system, and a relatively complex statement (2030 gates) to prove in it). Also, only very experimental code for MuSig-DN exists; MuSig2 has an implementation that's pretty close to production-ready.
• Additional security assumptions (DDH over two different elliptic curves).

So while MuSig-DN is conceptually a nice solution to the problem of having stateful signers (which is definitely annoying, and a risk for unsafe implementations), I don't think the downsides weigh up against it. The additional signing computational cost pretty much puts it pretty out of reach of hardware signing devices, for example. Plus, its only real advantage is a concern about unsafe implementations (which deal incorrectly with signing state) - but it does so by increasing implementation complexity in other ways which also increases risk. With MuSig2, the picture is even less rosy, as the round number advantage is gone too.

[Rspigler]

Thanks for the explanation!

I will have to think how this could affect systems like Qubes due to the hypervisor, or amnesiac systems like Tails.

[real-or-random]

So while MuSig-DN is conceptually a nice solution to the problem of having stateful signers (which is definitely annoying, and a risk for unsafe implementations), I don't think the downsides weigh up against it.

Agreed. MuSig-DN (or the more efficient scheme in https://eprint.iacr.org/2021/1055.pdf) is still more in the academic realm. Technically it does its job but it's hard to use in practice. I think we'll need more research to make deterministic nonces in multisig more efficient and simpler to implement if we want something that fits in Bitcoin Core.

[jonasnick]

it's also possible I think to support treating agg of xpubs as a new "xpub" itself (e.g. agg(xpub1/...,xpub2/...)/*) for example by defining the aggregated chaincode as a hash of the child chaincodes.

I don't think there's a fundamental problem with that. I opened a libsecp-zkp PR that allows BIP32-tweaking an aggregate public key and signing for it. Luckily, it's not terribly complicated (see the commit that updates the musig example code here).

[brandonblack]

I think it's useful to describe the required behaviors in more detail, and with reference to the PSBT roles:

Existing Creator, Updater, and Combiner behaviors...

MuSig2 Round 1

• PSBT is distributed to all Signers
• Signers generate nonces (either from a monotonic counter and PRF or high quality RNG)
• Signers add their nonces to PSBT
• Combiner merges Signers' PSBTs
• Optional: Combiner runs SignAgg on Signers' nonces
  • Combiner adds aggregated nonce to PSBT
  • Optional: Combiner removes individual Signers' nonces from PSBT

MuSig2 Round 2

• PSBT is distributed to all Signers
• If PSBT contains individual Signers' nonces
  • If PSBT does not contain aggregate nonce
    • Signers run SignAgg to produce aggregate nonce
  • Optional: Signers run Partial Verification
• Signers run Sign'
• Signers add their partial signatures to PSBT
• Finalizer aggregates partial signatures and nonces
• Finalizer validates final signature
• Finalizer adds final signature to PSBT

Existing Finalizer / Extractor behaviors...

[seedhammer]

Beyond that, there are indeed a number of things that need to be decided:

• How to integrate into descriptors. One possibility is to only support an agg fragment as leaf key (e.g. agg(xpub1/.../*,xpub2/.../*)), but it's also possible I think to support treating agg of xpubs as a new "xpub" itself (e.g. agg(xpub1/...,xpub2/...)/*) for example by defining the aggregated chaincode as a hash of the child chaincodes. This complicates signing further, however, though I don't think there are fundamental problems with this (I've had some discussions with @jonasnick with this).

We're engraving descriptors to metal and are thus very interested in having compact or even constant sized MuSig/FROST descriptors. Is it possible to support descriptors that include only the "aggregated xpub" and not every key as in the proposed agg() expression, leading to a O(1) size instead of O(number-of-keys)?

[achow101]

Is it possible to support descriptors that include only the "aggregated xpub" and not every key as in the proposed agg() expression, leading to a O(1) size instead of O(number-of-keys)?

The aggregated pubkey will look like any other pubkey, so it is trivial to substitute it in to the descriptor if you wish to do so. However this is lossy as you will lose the information about the pubkeys that are involved in that aggregated pubkey, and that information is necessary for spending. It will still need to be stored and backed up somewhere.

[AdamISZ]

Is it possible to support descriptors that include only the "aggregated xpub" and not every key as in the proposed agg() expression, leading to a O(1) size instead of O(number-of-keys)?

The aggregated pubkey will look like any other pubkey, so it is trivial to substitute it in to the descriptor if you wish to do so. However this is lossy as you will lose the information about the pubkeys that are involved in that aggregated pubkey, and that information is necessary for spending. It will still need to be stored and backed up somewhere.

After talking with @seedhammer about this a bit, and thinking about it, I came to the following tentative conclusion (after changing my mind about three times :) ):

MuSig2 aggregation is compatible with BIP32 derivation (that much is not controversial, it's described in the MuSig2 BIP and, well, here), but (claim:) even more specifically, a single participant in the scheme doesn't need to store more than O(1) information, in order to make partial signatures later: instead of storing their private key (call it x_i), they can store x_i_agg = H(L||P_i)x_i (their 'private aggregated key' or whatever we call it), along with the negotiated aggregate public key P_agg.
(Note: i'm specifically saying there that you don't store L, the full list of keys).
Then let's say we want to sign on BIP32 (unhardened) branch index j. That participant, i, can (a) calculate the new aggregate pubkey P_agg_j = P_agg + d_j G (where d_j is the BIP32 tweak, publically derivable if unhardened), then calculate their signature share (after following the MuSig2 nonce generation process, note that the factor 'b' only depends on the aggregate key, here P_agg_j), with the formula s_i = k_i_1 + bk_i_2 + H(P_agg_j||R_agg||m)x_i_agg. When these s_i are added, they do not form a full valid signature, but you only need to further add H(P_agg_j||R_agg||m)d_j to make it correct.

It's highly likely that that is either (a) already known or (b) wrong in some detail or possibly (c) there is some security issue with doing this [see note]. But I wasn't able to find it written anywhere?

A bit off topic here, but more relevant to @seedhammer 's needs, but I believe similar logic applies to FROST (if anything it's a little easier).

[note] a relevant point of course is that doing unhardened BIP32 with schnorr is only secure because of key-prefixing; ecdsa gets by without it because of non-linearity, but if we didn't use key-prefixing in BIP340 then unhardened i.e. publically derivable tweaks would allow forgery.

[BenWestgate]

Is it possible to support descriptors that include only the "aggregated xpub" and not every key as in the proposed agg() expression, leading to a O(1) size instead of O(number-of-keys)?

You should be able to use Shamir secret sharing between the private key data so that a spending threshold can recover all pubkey data needed to reconstruct the agg() expression.

[seedhammer]

Is it possible to support descriptors that include only the "aggregated xpub" and not every key as in the proposed agg() expression, leading to a O(1) size instead of O(number-of-keys)?

You should be able to use Shamir secret sharing between the private key data so that a spending threshold can recover all pubkey data needed to reconstruct the agg() expression.

As I understand it, the agg() expression requires all n public keys. I don't see how a threshold, m < n, can recover n keys and certainly not with constant O(1) storage. Can you elaborate?

[brandonblack]

In FROST

Is it possible to support descriptors that include only the "aggregated xpub" and not every key as in the proposed agg() expression, leading to a O(1) size instead of O(number-of-keys)?

You should be able to use Shamir secret sharing between the private key data so that a spending threshold can recover all pubkey data needed to reconstruct the agg() expression.

As I understand it, the agg() expression requires all n public keys. I don't see how a threshold, m < n, can recover n keys and certainly not with constant O(1) storage. Can you elaborate?

For MuSig2, each signer needs all pubkeys and its secret key in order to sign. Because MuSig2 is an n-of-n multi-signature, this means that if you can retrieve sufficient secret key material to sign, you also have everything you need to recreate all public keys.

Now most MuSig2 users will also be using some kind of a taptree, which may contain other MuSig2s or script multisigs. In that case, the situation is much like that in a plain script multsig. Each signer's secret key should be stored with n-minus-t (I think?) other signers' public keys, as that enables them to fully reconstruct each of the possible signing cases for each address.

For FROST, the situation is different. FROST's DKG itself results in something approximately equivalent to a Shamir's Secret Sharing split of a secret key. What is unique about that is that one can have a single Schnorr public key for which the multisig can sign and the quorum of secret key shares alone is sufficient to fully reconstruct the aggregate public and secret key. It is further possible, through a ceremony similar to that used for producing a FROST signature, to produce a new sharing of keys without ever reconstructing the aggregate secret key in a single location.

In short, FROST provides a significant improvement in the safe storage of multi-signature wallets compared to MuSig2 or script multisig.

[brandonblack]

For MuSig2, each signer needs all pubkeys and its secret key in order to sign.

To clarify, this is within spec MuSig2 as described in BIP327. @AdamISZ's construction is quite possibly also secure and correct, but it's way above my pay grade to evaluate the security or correctness of methods outside the spec :-P

[AdamISZ]

To clarify, this is within spec MuSig2 as described in BIP327. @AdamISZ's construction is quite possibly also secure and correct, but it's way above my pay grade to evaluate the security or correctness of methods outside the spec :-P

This would be a good time to mention that - even though it's sound advice to never step outside the procedure of a spec like this, because this is cryptography - there's a different reason why my suggestion there is "flawed", aside from the a) b) c) that I mentioned, it's d) : this procedure isn't useful for MuSig2, because we are limited to N of N signing policies and the nonce generation is interactive. Hence, in a recovery process with limited data, since all N parties would have to talk to each other, or a coordinator (modulo nonce pre-processing maybe?), they could also communicate pubkeys anyway. Instead of each party storing x_agg_i = H(L||P_i)x_i and P_agg as I analyzed there, they could each store x_i and P_i and the agg keys are trivially recovered.

Possibly the point I raised there is still of interest, though. I'm not sure.

And to reiterate, and as @brandonblack has gone into more detail on, this question is much more of interest with FROST.

[jonasnick]

@achow101 @seedhammer

you will lose the information about the pubkeys that are involved in that aggregated pubkey, and that information is necessary for spending. It will still need to be stored and backed up somewhere.

As @AdamISZ notes above it would be sufficient to store the aggregate pubkey, let some third party provide the individual pubkeys and then check whether the aggregate of the individual pubkeys matches the stored aggregate pubkey. Due to the collision resistance property of key aggregation, the check only passes if the provided individual pubkeys were correct. Not sure if that follows the design philosophy of descriptors.

@AdamISZ's proposed modification to the signing algorithm also looks secure (even if it may not be as useful) as it purely changes internal caching and leaves the output indistinguishable from the original signing algorithm.

[sipa]

I'm a bit confused by the discussion here.

The point of descriptors is encoding all information necessary to spend funds (apart from private key material, which is optional). If you remove information like which the co-signer public keys are, then signing no longer works. Of course, you could get that information from your cosigners, but if that's acceptable, why can't you get the descriptor in its entirety from the cosigners (and if desired, just keep the (master) private key)?

EDIT: I guess in case we're looking at MuSig2 aggregation of multiple keys, and then applying BIP32 derivation to the aggregated key, there is a point, as it'd let you derive keys without needing to know the individual participants' keys. You'd still need to know the participants at signing time, but if all you want is a descriptor for address derivation, this suffices. It's also related to #24114.

[jonasnick]

@sipa

Of course, you could get that information from your cosigners, but if that's acceptable, why can't you get the descriptor in its entirety from the cosigners (and if desired, just keep the (master) private key)?

My understanding was that it still makes sense to backup the descriptor even though its not sufficient to sign because it commits to your set of co-signers. If you don't back up such a descriptor and instead obtain it from somewhere, then you have to verify again somehow that the cosigners and their public keys are correct.

[sipa]

My understanding was that it still makes sense to backup the descriptor even though its not sufficient to sign because it commits to your set of co-signers.

The address also commits to the set of co-signers.

But see my edit above: if you're going to do aggregation and then BIP32 derivation on top, it makes sense to backup the descriptor with the aggregation pre-evaluated; that's effectively equivalent to having the information for all addresses you'd want to derive with it.

[real-or-random]

Related: bitcoin-core/secp256k1#1452

[Sjors]

WIP in #29675!