[New BIP 389] Multipath descriptors #1354

achow101 commented at 5:55 PM on August 15, 2022: member

This was posted to the mailing list a couple of weeks ago.

in bip-multipath-descs.mediawiki:68 in 3a82a531d9 outdated

  63 | +Key Expressions using the format described in BIP 380 are compatible with this modification and parsers that implement this will still be able to parse such descriptors.
  64 | +However as this is an addition to Key Expressions, older parsers will not be able to understand such descriptors.
  65 | +
  66 | +This modification to Key Expressions uses two new characters: <tt><</tt> and <tt>;</tt>.
  67 | +These are part of the descriptor character set and so are covered by the checksum algorithm.
  68 | +As these are previously unused characters, old parsers will not accidentally mistake them for indicating something else.

luke-jr commented at 10:19 PM on September 29, 2022:

What prevents wallets from requiring multipath syntax, and losing support for the current split model?

(Do the benefits outweigh the complexity of having two different ways to implement this?)

achow101 commented at 12:32 AM on October 7, 2022:

I don't think it would make sense to only require multipath syntax. The single path syntax is still required in order to have multipath support as all of the other indices in the derivation path are standard single derivation items, and there's no guarantee of where the multipath specifier will even appear. The only way that multipath would be required is if the implementer went out of their way to specifically require it.

luke-jr renamed this:
~~[New BIP] Multipath descriptors~~
[New BIP 389] Multipath descriptors
on Sep 29, 2022

luke-jr commented at 10:27 PM on September 29, 2022: member

Assigned BIP 389

darosior cross-referenced this on Sep 30, 2022 from issue Multipath descriptors support by darosior

in bip-multipath-descs.mediawiki:43 in 3a82a531d9 outdated

  38 | +
  39 | +This is modifed to state:
  40 | +
  41 | +* <tt>xpub</tt> encoded extended public key or <tt>xprv</tt> encoded extended private key (as defined in BIP 32)
  42 | +** Followed by zero or more <tt>/NUM</tt> or <tt>/NUMh</tt> path elements indicating BIP 32 derivation steps to be taken after the given extended key.
  43 | +** Followed by zero or one <tt>/<NUM;NUM</tt> (<tt>NUM</tt> may be followed by <tt>h</tt> to indicated a hardened step) path element indicating a tuple of BIP 32 derivation steps to be taken after the given extended key.

darosior commented at 1:09 PM on October 2, 2022:

Are ' and H ruled out for indicating a hardened step? If not (which is better imo), then let's be explicit:

** Followed by zero or one <tt>/<NUM;NUM</tt> (<tt>NUM</tt> may be followed by <tt>h</tt>, <tt>H</tt> or <tt>'</tt> to indicated a hardened step) path element indicating a tuple of BIP 32 derivation steps to be taken after the given extended key.

achow101 commented at 12:47 AM on October 7, 2022:

Done

in bip-multipath-descs.mediawiki:50 in 3a82a531d9 outdated

  45 | +*** Followed by a single <tt>></tt>
  46 | +** Followed by zero or more <tt>/NUM</tt> or <tt>/NUMh</tt> path elements indicating BIP 32 derivation steps to be taken after the given extended key.
  47 | +** Optionally followed by a single <tt>/*</tt> or <tt>/*h</tt> final step to denote all direct unhardened or hardened children.
  48 | +
  49 | +When a <tt>/<NUM;NUM;...;NUM></tt> is encountered, parsers should produce multiple descriptors where the first descriptor uses the first <tt>NUM</tt>, and a second descriptor uses the second <tt>NUM</tt>, and so on, until each <tt>NUM</tt> is accounted for.
  50 | +Descriptors that contain multiple Key Expressions that each have a <tt>/<NUM;NUM;...;NUM></tt> must have tuples of exactly the same length.

darosior commented at 12:01 AM on October 3, 2022:

No strong opinion, but it's a bit awkward to have a parsing check for the key expression that isn't local to itself. By mandating a length of 2 there would be no need to go through all the keys of each descriptor you parsed to check if not 2 of them are "multipath keys" with different tuple lengths. And we can always change that in the future should we really need it.

sanket1729 commented at 5:32 PM on October 19, 2022:

Yeah, for this reason, I prefer having multipath(<NUM_PATHS>, <DESC>) syntax. But upon reading the ML post, seems like some people are already using the syntax presented in the BIP.

darosior cross-referenced this on Oct 3, 2022 from issue Multipath descriptors by darosior

dr-orlovsky commented at 10:30 AM on October 5, 2022: contributor

It seems to me that in "Backwards compatibility" section it would be nice to mention BIP88 - as well as in motivation to explain why this standard does not work and we need another one. I know about the discussion in https://github.com/bitcoin/bitcoin/issues/17190, but the standard needs a summary of it.

achow101 force-pushed on Oct 7, 2022

achow101 commented at 12:47 AM on October 7, 2022: member

Updated with the number.

It seems to me that in "Backwards compatibility" section it would be nice to mention BIP88 - as well as in motivation to explain why this standard does not work and we need another one. I know about the discussion in bitcoin/bitcoin#17190, but the standard needs a summary of it.

I've added a brief paragraph on that.

achow101 force-pushed on Oct 7, 2022

in bip-0389.mediawiki:49 in 1109ef2d07 outdated

  44 | +*** Followed by zero or more <tt>;NUM</tt> or <tt>;NUMh</tt> additional tuple values of BIP 32 derivation steps
  45 | +*** Followed by a single <tt>></tt>
  46 | +** Followed by zero or more <tt>/NUM</tt> or <tt>/NUMh</tt> path elements indicating BIP 32 derivation steps to be taken after the given extended key.
  47 | +** Optionally followed by a single <tt>/*</tt> or <tt>/*h</tt> final step to denote all direct unhardened or hardened children.
  48 | +
  49 | +When a <tt>/<NUM;NUM;...;NUM></tt> is encountered, parsers should produce multiple descriptors where the first descriptor uses the first <tt>NUM</tt>, and a second descriptor uses the second <tt>NUM</tt>, and so on, until each <tt>NUM</tt> is accounted for.

dr-orlovsky commented at 7:28 AM on October 7, 2022:

At least in some cases (for instance in our bitcoin wallet library https://github.com/BP-WG/descriptor-wallet/ by @LNP-BP Association) we do not work with descriptors directly, but instead with "descriptors templates", which are directly derived into specific public keys or addresses by providing derivation path pattern, filling in the template. That is why BIP-88 sounded reasonable to me.

Here, you propose to derive multiple descriptors and handle them separately, which (at least in our case) will result in more code and higher business logic complexity - we basically do not need this. With your BIP proposal we can have a standard guaranteeing that the length of "derivation pattern" is always 1, so we can still work with descriptor templates and generate specific public key or address without intermediate step of producing multiple descriptors.

Thus, I suggest to replace the sentence "parsers should produce multiple descriptors" in the following way

When a <tt>/<NUM;NUM;...;NUM></tt> is encountered, parsers should account for a presence of multiple descriptors where the first descriptor uses the first <tt>NUM</tt>, and a second descriptor uses the second <tt>NUM</tt>, and so on, until each <tt>NUM</tt> is accounted for in public key and/or address derivation, and in descriptor export/import operations.

jgriffiths commented at 4:39 AM on February 9, 2023:

I agree with the assessment from @dr-orlovsky, noting that combo descriptors work compatibly with the proposed change (they produce multiple addresses from the same expression, not multiple descriptors).

I would add script generation to the list i.e. public key, script generation and address derivation.

achow101 commented at 8:16 PM on February 9, 2023:

I've updated this sentence with the suggested wording (slightly modified, but should be the same meaning).

in bip-0389.mediawiki:58 in 1109ef2d07 outdated

  53 | +When interpreting for this use case, wallets should use the first descriptor for producing receiving addresses, and the second descriptor for producing change addresses.
  54 | +For this use case, the element will commonly be the value <tt>/<0;1></tt>
  55 | +
  56 | +Note that only one <tt>/<NUM;NUM;...;NUM></tt> specifier is allowed in a Key Expression.
  57 | +This is in contrast to proposals such as BIP 88 which allow for multiple derivation indexes in a single element.
  58 | +This limitation exists in order to reduce the number of descriptors that are expanded, avoid confusion about how to expand the descriptor, and avoid having expanded descriptors that users are not expecting.

dr-orlovsky commented at 7:29 AM on October 7, 2022:

It seems reasonable to move that paragraph into the "backwards compatibility" section

achow101 commented at 8:17 PM on February 9, 2023:

Moved the last two sentences. I think the first is necessary in the specification section.

dr-orlovsky commented at 7:29 AM on October 7, 2022: contributor

Two suggestions, otherwise looks good to me

haleemshal approved

darosior cross-referenced this on Oct 12, 2022 from issue Release 8.0.0 by sanket1729

darosior cross-referenced this on Oct 23, 2022 from issue Multipath descriptors support by darosior

darosior cross-referenced this on Oct 24, 2022 from issue Decent change management (using multipath descriptors) by darosior

darosior referenced this in commit 8b129fe3e5 on Oct 28, 2022

sanket1729 referenced this in commit 0daded488f on Dec 14, 2022

notmandatory cross-referenced this on Dec 27, 2022 from issue Descriptors for printable backup template community file by sbddesign

craigraw commented at 6:08 AM on January 29, 2023: contributor

Would be great to see this get merged - implementations following this approach already exist.

craigraw cross-referenced this on Jan 29, 2023 from issue [Bug] "Key path value '<0;1>' is not a valid uint32" - exported output descriptor is invalid and not recognized by Bitcoin Core by GregTonoski

darosior cross-referenced this on Feb 8, 2023 from issue Output descriptors/miniscript support by jgriffiths

in bip-0389.mediawiki:43 in 1109ef2d07 outdated

  38 | +
  39 | +This is modifed to state:
  40 | +
  41 | +* <tt>xpub</tt> encoded extended public key or <tt>xprv</tt> encoded extended private key (as defined in BIP 32)
  42 | +** Followed by zero or more <tt>/NUM</tt> or <tt>/NUMh</tt> path elements indicating BIP 32 derivation steps to be taken after the given extended key.
  43 | +** Followed by zero or one <tt>/<NUM;NUM</tt> (<tt>NUM</tt> may be followed by <tt>h</tt>, <tt>H</tt>, or <tt>'</tt> to indicate a hardened step) path element indicating a tuple of BIP 32 derivation steps to be taken after the given extended key.

jgriffiths commented at 12:38 AM on February 9, 2023:

Requiring range items to be either all hardened or all non-hardened seems like a good idea; if not then it should be specified either way.

achow101 commented at 8:17 PM on February 9, 2023:

Each one is treated individually, so not everything must be hardened or unhardened. Hopefully that's clarified sufficiently in the latest push.

in bip-0389.mediawiki:44 in 1109ef2d07 outdated

  39 | +This is modifed to state:
  40 | +
  41 | +* <tt>xpub</tt> encoded extended public key or <tt>xprv</tt> encoded extended private key (as defined in BIP 32)
  42 | +** Followed by zero or more <tt>/NUM</tt> or <tt>/NUMh</tt> path elements indicating BIP 32 derivation steps to be taken after the given extended key.
  43 | +** Followed by zero or one <tt>/<NUM;NUM</tt> (<tt>NUM</tt> may be followed by <tt>h</tt>, <tt>H</tt>, or <tt>'</tt> to indicate a hardened step) path element indicating a tuple of BIP 32 derivation steps to be taken after the given extended key.
  44 | +*** Followed by zero or more <tt>;NUM</tt> or <tt>;NUMh</tt> additional tuple values of BIP 32 derivation steps

jgriffiths commented at 4:33 AM on February 9, 2023:

' and H are also allowed, no?

achow101 commented at 8:17 PM on February 9, 2023:

Yes, just got lazy with typing. Updated.

in bip-0389.mediawiki:50 in 1109ef2d07 outdated

  45 | +*** Followed by a single <tt>></tt>
  46 | +** Followed by zero or more <tt>/NUM</tt> or <tt>/NUMh</tt> path elements indicating BIP 32 derivation steps to be taken after the given extended key.
  47 | +** Optionally followed by a single <tt>/*</tt> or <tt>/*h</tt> final step to denote all direct unhardened or hardened children.
  48 | +
  49 | +When a <tt>/<NUM;NUM;...;NUM></tt> is encountered, parsers should produce multiple descriptors where the first descriptor uses the first <tt>NUM</tt>, and a second descriptor uses the second <tt>NUM</tt>, and so on, until each <tt>NUM</tt> is accounted for.
  50 | +Descriptors that contain multiple Key Expressions that each have a <tt>/<NUM;NUM;...;NUM></tt> must have tuples of exactly the same length.

jgriffiths commented at 4:41 AM on February 9, 2023:

This is presumably because they must be derived in lockstep in a single descriptor expression in the same way as multiple trailing '/*' paths are handled - this should be explicitly stated.

achow101 commented at 8:17 PM on February 9, 2023:

Done

in bip-0389.mediawiki:53 in 1109ef2d07 outdated

  48 | +
  49 | +When a <tt>/<NUM;NUM;...;NUM></tt> is encountered, parsers should produce multiple descriptors where the first descriptor uses the first <tt>NUM</tt>, and a second descriptor uses the second <tt>NUM</tt>, and so on, until each <tt>NUM</tt> is accounted for.
  50 | +Descriptors that contain multiple Key Expressions that each have a <tt>/<NUM;NUM;...;NUM></tt> must have tuples of exactly the same length.
  51 | +
  52 | +The common use case for this is to represent descriptors for producing receiving and change addresses.
  53 | +When interpreting for this use case, wallets should use the first descriptor for producing receiving addresses, and the second descriptor for producing change addresses.

jgriffiths commented at 4:43 AM on February 9, 2023:

Should comment here about what any 3rd and subsequent elements are used for, even if thats use-case dependent. This reads as though it was written before more than 2 elements were allowed.

achow101 commented at 8:18 PM on February 9, 2023:

I'm not aware of any such use cases currently, but this was a suggestion that makes sense and I don't see that it is harmful.

jgriffiths commented at 12:49 AM on February 10, 2023:

I'm thinking something like Key expressions with multi-path tuples larger than 2 elements should not be assumed to follow the above receive/change scheme.

in bip-0389.mediawiki:60 in 1109ef2d07 outdated

  57 | +This is in contrast to proposals such as BIP 88 which allow for multiple derivation indexes in a single element.
  58 | +This limitation exists in order to reduce the number of descriptors that are expanded, avoid confusion about how to expand the descriptor, and avoid having expanded descriptors that users are not expecting.
  59 | +
  60 | +==Test Vectors==
  61 | +
  62 | +TBD

jgriffiths commented at 4:45 AM on February 9, 2023:

None of the descriptor BIPs have test vectors and this is a potential source of problems for people implementing these specs.

achow101 commented at 8:18 PM on February 9, 2023:

Yes, thanks for reminding me to write those.

in bip-0389.mediawiki:70 in 1109ef2d07 outdated

  67 | +Key Expressions using the format described in BIP 380 are compatible with this modification and parsers that implement this will still be able to parse such descriptors.
  68 | +However as this is an addition to Key Expressions, older parsers will not be able to understand such descriptors.
  69 | +
  70 | +This modification to Key Expressions uses two new characters: <tt><</tt> and <tt>;</tt>.
  71 | +These are part of the descriptor character set and so are covered by the checksum algorithm.
  72 | +As these are previously unused characters, old parsers will not accidentally mistake them for indicating something else.

jgriffiths commented at 4:47 AM on February 9, 2023:

The biggest back compatibility change is that this allows all non-combo descriptors to produce multiple outputs instead of a simple bijection from descriptor to script/address/key, this should probably be noted. Additionally, for combo descriptors this now allows the wpkh and sh-wpkh variants to themselves produce multiple outputs.

achow101 commented at 8:15 PM on February 9, 2023:

This was already the case for ranged descriptors (those with keys that have /*), so I don't think that's something that needs to be mentioned. For ranged descriptors, it's already impossible to get the real descriptor that generated a script since you don't know the parent xpub or the derivation.

jgriffiths commented at 12:45 AM on February 10, 2023:

This is a change because the mapping cardinality changes. Before multi-path:

A non-ranged descriptor resolves to a single script (0 inputs to 1 output).
A ranged descriptor plus bip32 child number resolves to a single script (1-1).
A non-ranged combo resolves to either 2 or 4 scripts (0-[2|4]).
A ranged combo plus bip32 child number resolves to 4 scripts (1-4).

Note that combo is its own BIP and may not be supported by some implementations.

After Multi-path, the above all hold if multi-path aren't used. Multipath adds the following cases:

A non-ranged descriptor with MP resolves to N scripts (0-N).
A ranged descriptor plus bip32 child number with MP resolves to N scripts (1-N).
A non-ranged combo with MP resolves to either 2N or 4N scripts (0-[2N|4N]).
A ranged combo plus bip32 child number with MP resolves to 4N scripts (1-4N).

i.e. the number of required inputs to resolve to a single address has changed when MP is present.

Specify 389: Multipath descriptors a3ad2547bc

achow101 force-pushed on Feb 9, 2023

apoelstra cross-referenced this on Mar 28, 2023 from issue wallet: add `seeds` argument to `importdescriptors` by apoelstra

stepansnigirev cross-referenced this on Apr 2, 2023 from issue switch to <m;n> multipart descriptors by default (bip-389) by stepansnigirev

darosior cross-referenced this on Jun 13, 2023 from issue descriptors: Be able to specify change and receiving in a single descriptor string by achow101

luke-jr merged this on Jun 29, 2023

luke-jr closed this on Jun 29, 2023