388: Add support for `musig` in descriptor templates

bigspider commented at 10:44 am on November 8, 2024: contributor

This required a few changes in the grammar describing descriptor templates: the single symbol KP is no longer enough to cleanly represent the syntax. Therefore, it’s now replaced by a more fine-grained symbol hierarchy:

KEY, mapping 1-on-1 to KEY expressions of descriptors
KP, key placeholders, that represent a single root key, or an aggregate musig key; regardless of the nature of the key, key placeholders are what is followed by /** or /<M;N>/*.
KI, key index, the actual “pointer” to the key information vector.

While the validity checks to avoid pubkey reuse before this change were feasible by looking at all the @i expressions in the descriptor template, they are now at the level of the KEY expressions, by comparing their key placeholders. This means that the specs do not prevent having @i somewhere and musig(@i,...) elsewhere (which does not cause pubkey reuse in the actual scripts).

Note that there is no breaking change with the previous specs, just more fine-grained grammar in order to keep everything working in the presence of musig.

bigspider force-pushed on Nov 8, 2024

bigspider commented at 10:49 am on November 8, 2024: contributor

cc @jgriffiths @benma

in bip-0388.mediawiki:154 in be5029f322 outdated

149@@ -147,25 +150,38 @@ See [[bip-0379.md|BIP-379]] for a precise specification of all the valid miniscr
150 * An open brace <tt>{</tt>, a <tt>TREE</tt> expression, a comma <tt>,</tt>, a <tt>TREE</tt> expression, and a closing brace <tt>}</tt>
151 
152 
153-<tt>KP</tt> expressions (key placeholders) consist of
154-* a single character <tt>@</tt>
155-* followed by a non-negative decimal number, with no leading zeros (except for <tt>@0</tt>)
156+<tt>KEY</tt> expressions consist of
157+* a <tt>KP</tt> expressions

jgriffiths commented at 11:32 am on November 8, 2024:

nit: expression, not expressions

bigspider commented at 12:47 pm on November 8, 2024:

Thanks! Fixed.

jgriffiths commented at 11:49 am on November 8, 2024: none

@bigspider thanks for the ping. Only one initial question before I review more thoroughly - why do we not allow derivation inside the musig expression KP elements, subject to the same rules as BIP-0390?

bigspider commented at 12:04 pm on November 8, 2024: contributor

@bigspider thanks for the ping. Only one initial question before I review more thoroughly - why do we not allow derivation inside the musig expression KP elements, subject to the same rules as BIP-0390?

I did indeed suggest removing that from descriptors as well, and I don’t know of use cases that justify the (substantial) added complexity for signers.

It is much more inefficient in practice (especially for a transaction with many inputs coming from the same account, since the result of the key aggregation can be cached for all the inputs/change outputs, instead of repeating it each time with different keys).

Finally, it breaks the key placeholder concept, as it would imply that we need to support derivations at different nesting levels in the grammar.

bigspider commented at 12:48 pm on November 8, 2024: contributor

I added a sentence explicitly mentioning that the same key index can’t be repeated inside musig.

in bip-0388.mediawiki:176 in 299a412f5f outdated

175-The placeholder <tt>@i</tt> for some number ''i'' represents the ''i''-th key in the vector of key information items (which must be of size at least ''i + 1'', or the wallet policy is invalid).
176+<tt>SCRIPT</tt>, <tt>TREE</tt> and <tt>KEY</tt> expressions map directly to the corresponding concepts defined in [[bip-0380.mediawiki|BIP-380]] for output script descriptors.
177+
178+Each <tt>KEY</tt> expression always correspond to a precise public key in the final bitcoin Script. Therefore, all the derivation steps in the BIP-32 hierarchy are included in a <tt>KEY</tt> expression.
179+
180+Each <tt>KP</tt> (key placeholder) expressions, on the other hand, maps to the root of all the corresponding public keys for all the possible UTXOs that belong to the account represented in the wallet policy. Therefore, no derivation steps are allowed in a <tt>KP</tt> expression.

jonatack commented at 2:57 pm on November 8, 2024:

0Each <tt>KP</tt> (key placeholder) expression, on the other hand, maps to the root of all the corresponding public keys for all the possible UTXOs that belong to the account represented in the wallet policy. Therefore, no derivation steps are allowed in a <tt>KP</tt> expression.

in bip-0388.mediawiki:2 in 299a412f5f outdated

0@@ -1,3 +1,6 @@
1+RECENT CHANGES:
2+* (06 Nov 2024) Added <tt>musig</tt> key placeholders

jonatack commented at 3:03 pm on November 8, 2024:

Perhaps a few more details, not sure.

0* (06 Nov 2024) Added support for <tt>musig</tt> key placeholders in descriptor templates

nit, if this change is backward compatible and doesn’t break anything, perhaps make a changelog section below instead (can be deferred to later).

bigspider commented at 4:06 pm on November 8, 2024:

Indeed, I was trying to find examples of other BIPs, and I copied the style from BIP-32, but a small ‘Changelog’ section like in BIP-340 is probably better. I’ll do it later, once I don’t expect further changes from the review.

in bip-0388.mediawiki:86 in 299a412f5f outdated

82@@ -80,7 +83,7 @@ We set two fundamental design goals:
83 * Minimize the amount of information that is shown on screen - so that the user can actually validate it.
84 * Minimize the number of times the user has to validate such information.
85 
86-Designing a secure protocol for the coordination of a descriptor wallet among distant parties is also a challenging problem that is out of scope in this document. See [[bip-0129.mediawiki|BIP-129 (Bitcoin Secure Multisig Setup)]] for an approach designed for multisignature wallets. Regardless of the approach, the ability for the user to carefully verify all the details of the spending policies using the hardware signer's screen is a prerequisite for security in adversarial environments.
87+Designing a secure protocol for the coordination of a descriptor wallet among distant parties is also a challenging problem that is out of scope in this document. See [[bip-0129.mediawiki|BIP-129 (Bitcoin Secure Multisig Setup)]] for an approach designed for multisig wallets. Regardless of the approach, the ability for the user to carefully verify all the details of the spending policies using the hardware signer's screen is a prerequisite for security in adversarial environments.

jonatack commented at 3:04 pm on November 8, 2024:

nit while touching this sentence

0Designing a secure protocol for the coordination of a descriptor wallet among distant parties is also a challenging problem that is out of the scope of this document. See [[bip-0129.mediawiki|BIP-129 (Bitcoin Secure Multisig Setup)]] for an approach designed for multisig wallets. Regardless of the approach, the ability for the user to carefully verify all the details of the spending policies using the hardware signer's screen is a prerequisite for security in adversarial environments.

jonatack commented at 3:06 pm on November 8, 2024: member

A few minor comments.

jonatack added the label Proposed BIP modification on Nov 8, 2024

jonatack requested review from jgriffiths on Nov 8, 2024

in bip-0388.mediawiki:3 in 4c897bf294 outdated

0@@ -1,3 +1,6 @@
1+RECENT CHANGES:
2+* (06 Nov 2024) Added support for <tt>musig</tt> key placeholders in descriptor templates
3+

murchandamus commented at 10:09 pm on November 8, 2024:

The BIP formatting rules prescribe that the document starts with the preamble. May I suggest that you introduce a Change Log section in the style of BIP 327 or BIP 352 toward the end of the document where you incorporate this note?

jonatack commented at 10:27 pm on November 8, 2024:

@murchandamus yes, see #1697 (review) @bigspider fwiw a suggested order at #1691 (review)

bigspider commented at 9:53 am on November 9, 2024:

Good suggestion, done in eec10546357af967978a13aa0c989a31d4309b17.

jgriffiths commented at 3:04 am on November 9, 2024: none

It is much more inefficient in practice

This is true but only applies if the feature is used. Support for it could be optional for example; wallets are free to limit the format and type of templates they support.

Finally, it breaks the key placeholder concept, as it would imply that we need to support derivations at different nesting levels in the grammar.

IIUC this only requires that any wildcards in the musig keys to aggregate must be derived at the same index as other keys when a wildcard is present, which is the same restriction as any wildcards in any key expression elsewhere. IOW, the entire expression must be derivable with a single value for all wildcards, whether inside musig() or elsewhere. Perhaps I’m failing to grok your meaning here, or perhaps things would be clearer if I worked through implementing support for this extension personally.

I did indeed suggest removing that from descriptors as well, and I don’t know of use cases that justify the (substantial) added complexity for signers.

You raise reasonable points in the linked mail IMO. I can see that there may be a desire to not limit future use-cases, and I can also see that potentially allowing a mixture of fixed and derived keys to aggregate may have some uses (assuming its safe to do so). It is disappointing that (AFAICS) you did not receive a reply.

My concern here is that it appears on the descriptor side we have a technical decision with no clear rationale/documented justification, while on the descriptor template side there is an opposing technical decision with rationale but that may limit future interop or valuable use-cases.

I would prefer to have these two sides aligned, or at least the rationale for differing be explicit on both side (i.e. a reply to the points you raised on the record somewhere).

bigspider commented at 11:14 am on November 9, 2024: contributor

This is true but only applies if the feature is used. Support for it could be optional for example; wallets are free to limit the format and type of templates they support.

If the language supports it, software wallet developers will use it; performance will probably be ok on their test transactions spending 1 UTXO; then one of their users who is trying to consolidate 50 UTXOs will discover it’s incredibly slow, complain to the vendor, and there will be no way to fix it at that point.

To make a stronger case on the stark difference in performance: for a n-of-n multisig and a transaction spending t inputs

aggregate-and-derive: 1 KeyAgg, plus 2 * t BIP32 child pubkey derivations
derive-and-aggregate: t KeyAgg, plus 2 * n * t BIP32 child pubkey derivations (some caching might be possible, but it doesn’t change the substance).

In other words, aggregate-and-derive doesn’t cost significantly more than normal multisigs in hardware signer’s performance once you have a few UTXOs (apart from needing 2 rounds, of course), while the penalty cost of derive-and-aggregate is enormous. BIP32 derivations are currently the biggest performance bottleneck in the Ledger bitcoin app, when using multi-user policies.

Therefore, by not supporting it, I expect it will result in more efficient implementations, less debugging, less support tickets, and no loss of functionality.

Finally, it breaks the key placeholder concept, as it would imply that we need to support derivations at different nesting levels in the grammar.

IIUC this only requires that any wildcards in the musig keys to aggregate must be derived at the same index as other keys when a wildcard is present, which is the same restriction as any wildcards in any key expression elsewhere. IOW, the entire expression must be derivable with a single value for all wildcards, whether inside musig() or elsewhere. Perhaps I’m failing to grok your meaning here, or perhaps things would be clearer if I worked through implementing support for this extension personally.

Even just parsing a descriptor template supporting both versions becomes a lot harder. This is more or less what a key expression in my AST looks like:

 0typedef struct {
 1    uint32_t num_first;   // NUM_a of /<NUM_a,NUM_b>/*
 2    uint32_t num_second;  // NUM_b of /<NUM_a,NUM_b>/*
 3
 4    KeyExpressionType type;
 5    union {
 6        // type == 0
 7        struct {
 8            int16_t key_index;  // index of the key
 9        } k;
10        // type == 1
11        struct {
12            rptr_musig_aggr_key_info_t musig_info;
13        } m;
14    };
15} policy_node_keyexpr_t;

They are very simple objects, derivations can only go in one place, and the grammar to describe them is context-free (so parsing for them is based on a trivial lookahead on the next one or few characters).

My concern here is that it appears on the descriptor side we have a technical decision with no clear rationale/documented justification, while on the descriptor template side there is an opposing technical decision with rationale but that may limit future interop or valuable use-cases.

I would prefer to have these two sides aligned, or at least the rationale for differing be explicit on both side (i.e. a reply to the points you raised on the record somewhere).

I understand the concern, and it is my desire to keep wallet policies as aligned as possible in order to minimize friction.

However, wallet policies are not representing the same thing as descriptors:

descriptors represent arbitrary outputs that can be spent with arbitrarily complicated spending logic that hardware signing devices might or might not support.
wallet policies represent scripts for a vast class of smart contracts where the logic is however quite simple and uniform: “you’re spending from an account, and change (if any) goes back to the same account”.

Therefore, wallet policies do not need to be as general as descriptors. It is fine if they are opinionated and much more structured - in fact, this makes them more useful, by implicitly leading wallet developers to only use sane descriptors. It’s the same reason why miniscript doesn’t (and can’t) support arbitrary Scripts, despite many other Scripts have perfectly valid use cases.

jgriffiths commented at 8:14 pm on November 9, 2024: none

@bigspider Thanks for the detailed response.

Note that as stated I don’t disagree with your points on performance (original or as further fleshed out here), except to note that we already have an extension for non-bip44-style policies which e.g. Ledger doesn’t support. However, on reflection I think there is nothing here that prevents derivation-before-aggregation being supported later, so this is not a blocker.

BIP32 derivations are currently the biggest performance bottleneck in the Ledger bitcoin app, when using multi-user policies.

Somewhat OT, but you should implement the libwally optimization to avoid computing the parent fingerprint (a) when it is not needed at all (saves a hash160 per derivation) and (b) when deriving a path (only the final derived key may need the fingerprint, the intermediate steps do not). In your impl, get_derived_pubkey never needs the fingerprint so adding a flag to bip32_CKDpub to skip calculating it would be a trivially implemented win there. In fact AFAICS none of your uses of that call require the fingerprint (e.g. PSBT).

Even just parsing a descriptor template supporting both versions becomes a lot harder.

Agreed the parsing gets more difficult. I will likely try adding support for this in wally to see how true that is for different impls.

Therefore, wallet policies do not need to be as general as descriptors. It is fine if they are opinionated and much more structured - in fact, this makes them more useful, by implicitly leading wallet developers to only use sane descriptors.

Disagree with the the sane moniker but I accept/agree with this statement otherwise. I will final review and ack next week when I get a chance to compare implementing these changes with the PR contents, thanks.

bigspider commented at 8:00 am on November 10, 2024: contributor

Somewhat OT, but you should implement the libwally optimization to avoid computing the parent fingerprint (a) when it is not needed at all (saves a hash160 per derivation) and (b) when deriving a path (only the final derived key may need the fingerprint, the intermediate steps do not). In your impl, get_derived_pubkey never needs the fingerprint so adding a flag to bip32_CKDpub to skip calculating it would be a trivially implemented win there. In fact AFAICS none of your uses of that call require the fingerprint (e.g. PSBT).

I actually had this implemented few months ago but ended up not merging it because the performance impact is negligible for our implementation. It turns out that almost the entire cost of bip32_CKDpub is the single scalar multiplication. A one line-change with a faster scalar implementation ended up saving close to 50% total running time for some complex transactions! We still have some room for improvements there.

bitcoin deleted a comment on Dec 5, 2024

murchandamus commented at 8:22 pm on December 9, 2024: contributor

These changes appear to be only adding additional options, specifically to support MuSig2, and to improve a few phrases. @bigspider: What would you consider the next steps? Are you waiting for some ACKs from stakeholders, or do you feel this is ready to go?

bigspider commented at 10:38 am on December 10, 2024: contributor

@bigspider: What would you consider the next steps? Are you waiting for some ACKs from stakeholders, or do you feel this is ready to go?

If nobody has further comments, it’s good to go from my point of view. I already implemented MuSig2 support in the Ledger Bitcoin app matching these specs.

murchandamus approved

murchandamus commented at 6:26 pm on December 10, 2024: contributor

Looks good to me from an editorial perspective. I have not contributed to any implementations of this BIP, nor fully analyzed it from the perspective of an implementer, but it looks to me that the KP expression was simply extended with MuSig support.

I’m gonna leave this open for a few more days in case someone else is still looking to add review, and merge it after that unless the subsequent interactions indicate otherwise or someone else does so before me.

in bip-0388.mediawiki:171 in eec1054635 outdated

170 Note that while [[bip-0389.mediawiki|BIP-389]] allows multipath <tt>/<NUM;NUM;...;NUM></tt> expressions with an arbitrary number of options, this specification restricts it to exactly 2 choices (with the typical meaning of receive/change addresses).
171 
172-The placeholder <tt>@i</tt> for some number ''i'' represents the ''i''-th key in the vector of key information items (which must be of size at least ''i + 1'', or the wallet policy is invalid).
173+<tt>SCRIPT</tt>, <tt>TREE</tt> and <tt>KEY</tt> expressions map directly to the corresponding concepts defined in [[bip-0380.mediawiki|BIP-380]] for output script descriptors.
174+
175+Each <tt>KEY</tt> expression always correspond to a precise public key in the final bitcoin Script. Therefore, all the derivation steps in the BIP-32 hierarchy are included in a <tt>KEY</tt> expression.

jonatack commented at 2:03 pm on December 17, 2024:

0Each <tt>KEY</tt> expression always corresponds to a precise public key in the final bitcoin Script. Therefore, all the derivation steps in the BIP-32 hierarchy are included in a <tt>KEY</tt> expression.

in bip-0388.mediawiki:243 in eec1054635 outdated

238@@ -224,9 +239,10 @@ Common single-signature account patterns:
239 * <tt>sh(wpkh(@0/**))</tt> (nested segwit).
240 * <tt>tr(@0/**)</tt> (taproot single-signature account).
241 
242-Common multisignature schemes:
243+Common multisig schemes:
244 * <tt>wsh(multi(2,@0/**,@1/**))</tt> - SegWit 2-of-2 multisignature, keys in order.

jonatack commented at 2:07 pm on December 17, 2024:

One last remaining use of “multisignature” if you wanted to convert them all to “multisig” in commit be5029f3224db8d5217a92a1ee7c90f000cf3d83

0* <tt>wsh(multi(2,@0/**,@1/**))</tt> - SegWit 2-of-2 multisig, keys in order.

in bip-0388.mediawiki:151 in 299a412f5f outdated

150@@ -151,7 +151,7 @@ See [[bip-0379.md|BIP-379]] for a precise specification of all the valid miniscr
151 
152 
153 <tt>KEY</tt> expressions consist of
154-* a <tt>KP</tt> expressions
155+* a <tt>KP</tt> expression

jonatack commented at 2:10 pm on December 17, 2024:

In commit 299a412f5f9ae0c210f8e08a5646749eda098e83, would be clearer to make this change in the first commit a3928806b93bdf83 rather than amending it in this one

bigspider commented at 11:37 am on December 19, 2024:

Done

in bip-0388.mediawiki:341 in eec1054635 outdated

337+
338+To help implementers understand updates to this document, we attach a version number that resembles ''semantic versioning'' (<code>MAJOR.MINOR.PATCH</code>).
339+The <code>MAJOR</code> version is incremented if changes to the BIP are introduced that are incompatible with prior versions.
340+An exception to this rule is <code>MAJOR</code> version zero (0.y.z) which is for development and does not need to be incremented if backwards incompatible changes are introduced.
341+The <code>MINOR</code> version is incremented whenever the inputs or the output of an algorithm changes in a backward-compatible way or new backward-compatible functionality is added.
342+The <code>PATCH</code> version is incremented for other changes that are noteworthy (bug fixes, test vectors, important clarifications, etc.).

jonatack commented at 2:17 pm on December 17, 2024:

In commit eec10546357af967978a13aa0c989a31d4309b17, I think the paragraph describing a changelog can be omitted. We’ll describe the changelogs in one place in BIP-2 (or #1712) and drop this paragraph from any other places.

bigspider commented at 11:37 am on December 19, 2024:

Nice, done!

Add support for musig key placeholders 662f4c73d7

Consistency of multisig/multisignature/threshold wording e103ddeb1e

Explicitly forbid repeated key indexes in musig() a4d9938ed2

Apply suggestions from code review

Co-authored-by: Jon Atack <jon@atack.com>

c2026e1de6

Move changelog to standalone section 2faf09d395

bigspider force-pushed on Dec 19, 2024

murchandamus approved

murchandamus commented at 3:33 pm on December 19, 2024: contributor

LGTM

murchandamus merged this on Dec 19, 2024

murchandamus closed this on Dec 19, 2024

jonatack commented at 4:51 pm on December 19, 2024: member

Post-merge LGTM.

388: Add support for musig in descriptor templates #1697

388: Add support for `musig` in descriptor templates #1697