BIP 88: Templates for Hierarchical Deterministic derivation paths

dgpv commented at 12:52 pm on October 26, 2020: contributor

Was first announced in https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-July/018024.html

Motivation and descriptions of usecases are given in the BIP draft, in the mailing-list post, and expanded in the replies to this mailing-list post and in Bitcoin Optech newsletter 105.

While this draft BIP did not receive extensive public discussions, it did not receive any rejections or criticism either. Within private or semi-private discussions, people said that they like the idea, noted the usefulness of this format and having it standardized. I attribute the lack of public discussions to the template format being boring but practical, and thus uncontroversial. I think that having this as a formal standard will be a benefit to the Bitcoin-related software and hardware ecosystem. I hope that submitting this as PR will bring more discussion and comments.

There are three implementations, including two reference implementations: in C and in Python (that is also compatible with micropython to be suitable for embedded applications). The implementations are thoroughly tested with the test data generated from the formal specification, and thus their behaviour follows the formal spec closely.

My thanks to @Enegnei for the help in fixing grammatical and punctuation errors in the early draft.

dgpv force-pushed on Oct 27, 2020

luke-jr commented at 10:01 pm on February 3, 2021: member

Missing a backward compatibility section

luke-jr added the label New BIP on Feb 3, 2021

dgpv commented at 8:07 am on February 4, 2021: contributor

IIUC, backward compatibility applies if there’s a prior standard or software that implements some prior (maybe de-facto) standard. I am not aware of any prior standard or any software that implements BIP32 path templates beyond the software that is linked in the BIP text (and that linked software is compatible with the spec).

The https://walletsrecovery.org/ website uses their own format to describe derivation paths, but it seems to me the format they use is intended for illustration rather than being processed by software. The format https://walletsrecovery.org/ uses to illustrate paths is obviously not compatible, but it was not a “previous spec” to this spec in any way, and I doubt that this fact need to be explicitly stated in the BIP.

BIP2 says “Motivation and backward compatibility (when applicable) must be addressed”. Since there’s no prior specs or implementation, it seems to me that backward compatibility is not applicable here.

dgpv commented at 8:12 am on February 4, 2021: contributor

If needed, I can add a note after the link to walletrecovery.org saying that their format is not compatible. But as the website is not a static document like the BIP, they can change their format at any time, and this would mean the information in the BIP may become out of date.

luke-jr commented at 9:30 pm on February 12, 2021: member

Sounds like a plan. Maybe just reference their current thing?

dgpv force-pushed on Feb 15, 2021

dgpv commented at 9:42 am on February 15, 2021: contributor

Added the “Known solutions” section to “Motivation” part.

dr-orlovsky commented at 7:12 pm on February 18, 2021: contributor

The proposed encoding for the index ranges will not work very well with current way how descriptors are structured in Bitcoin Core and rust-miniscript. In particular, square bracket notation [...] is already widely used in these implementation (and in many other software) for introducing public keys (XpubIndetifirer, fingerprints, extended private and public keys etc). So I proposet:

Avoid square brackets for index paths and use simple ranges (like m/5-16'/.. etc).
Allow embedding a public key information into derivation paths as already done by Bitcoin Core descriptors and miniscript using squared box notation. If a public key is given inside the path, use = separator (m/47'/5'=[xpubkey]/0-1/*)

With this such a BIP will be more interoperable with existing software and will allow keeping track of derivation paths which can be used without knowledge of extended private keys (when the last hardened index is provided with corresponding extended public key).

I have a reference Rust implementation for the format above here: https://github.com/LNP-BP/descriptor-wallet/tree/master/src/bip32 (path.rs, range.rs and xpubref.rs files). It is rust-miniscript compatible already used in the software:

Bitcoin Pro (tool for work with descriptors etc) https://github.com/pandoracore/bitcoin-pro
MyCitadel Wallet https://github.com/mycitadel/mycitadel-node

dgpv commented at 9:04 am on February 19, 2021: contributor

Avoid square brackets for index paths and use simple ranges (like m/5-16’/.. etc).

Brackets were added for better visual identification of ranges, for readability and less ambiguity.

I think that m/[5-16]'/0'/[1,2]' or m/{5-16}'/0'/{1,2}' is easier to parse for human brain than m/5-16'/0'/1,2', and there’s no ambiguity that the hardened marker ' applies to the range and not only to the index 16 or 2. Of course for software this might not matter, but for humans working with ranges IMO this will matter. Also there’s no confusion of how you should write /1',2'/ or 1,2' - while for software ‘hardened marker is at the end of the range’ is unambiguous, for humans it will be more confusing. Allowing to write this both ways means that the formal spec and therefore correct implementations will be more complex.

Allow embedding a public key information into derivation paths as already done by Bitcoin Core descriptors and miniscript using squared box notation. If a public key is given inside the path, use = separator (m/47’/5’=[xpubkey]/0-1/*)

This will complicate the formal spec by requiring to either add xpub parsing or at least maintaining additional storage for arbitrary strings found between [ and ]. The goal of this BIP is to be complete and unambiguous, adding complexity means that the spec will grow and will be much harder to analyze (the number of states in FSM grows very fast when adding complexity)

AFAIK squared box notation is only used by Core in descriptors to denote master key fingerprints, not xpubs. The miniscript spec at http://bitcoin.sipa.be/miniscript/ also does not have any usage of square brackets to delimit keys.

dr-orlovsky commented at 10:13 am on February 19, 2021: contributor

Well, it’s not about convenience, it is mostly about compatibility. Bitcoin Core currently use square brackets for xpub identifiers and fingerprints, so this renders standard already incompatible. Rust miniscript implementation uses them even more widely (not the site, but the rust code which is already part of Square Crypto BDK) – and I know about ongoing work of making that part of Bitcoin Core as well. So without this this standard will be just another standard contradicting existing “de facto” standards, not used by anybody other than author.

Without this compatibility I am concept NACK it

dgpv commented at 11:01 am on February 19, 2021: contributor

The square brackets can be replaced with curly brackets without problem, I think. In https://github.com/bitcoin/bitcoin/issues/17190 curly brackets were used, for example.

The spec won’t be any more complex without brackets at all. But I think that visually, bracket-less templates are more confusing. Having explicit grouping is better for UX when working with templates. This might be just my perception, though. Would be great to have more opinions on this.

Including ‘correct xpubs’ is out of the question, because this means that the formal spec will either be incomplete, or very complex. It might be useful and relatively simple spec-wise to allow arbitrary strings (with limited charset), and then xpubs or other interpretations of these strings might be defined in a separate BIP. Might be useful for labels/comments, for example: m/{44,49,84}'=@purpose/0'=xpubABCDEF/0'/{0-1}/{0-50000}=@should_be_enough. The parsing algorithm will then produce label=>position mapping like "@purpose": 0, "xpubABCDEF": 1, "@should_be_enough": 4. For the spec, these will be just arbitrary strings with limited charset starting from = and ending at /

dgpv commented at 11:05 am on February 19, 2021: contributor

Adding these arbitrary strings will increase the number of states to check when running TLC with the formal spec, and the amount of generated test data for comprehensive tests, so I’m not sure if it is worth it.

dr-orlovsky commented at 11:43 am on February 19, 2021: contributor

I am fine with curly (or any other) brackets unless they are squared, which breaks compatibility :) Let’s hear other opinions.

As for the annotations, I doubt that we need arbitrary strings. We need to standardize already present [fingerprint] and [xpubid] in bitcoin core and it will be nice to extend it with a single (standard) encoding of full xpub data. Not sure why it will be hard to make formal: we just reference encoding from BIP-32.

dgpv commented at 11:50 am on February 19, 2021: contributor

why it will be hard to make formal:

formal in the sense of using a formal specification language, in this case TLA+ (the spec is referenced in the BIP text: https://github.com/dgpv/bip32_template_parse_tplaplus_spec)

dgpv commented at 1:32 pm on February 19, 2021: contributor

Right now the prose spec (the BIP) corresponds to the TLA+ spec, and generated test data from the run of TLC on the TLA+ spec can be used to comprehensively test the reference implementations. If the notion of xpub is added and it is stated that it should be the correct xpub, the prose/formal spec correspondence will not be complete, because it is infeasible to implement a formal spec of xpub format for this purpose. The formal spec will either need to ignore the xpub part (and the comprehensiveness of the tests for reference implementations will be diminished), or have a simplified version - that is, the ‘arbitrary string of a limited charset’.

prusnak commented at 1:49 pm on February 19, 2021: contributor

Thank you @dgpv for bringing this BIP effort up again. We already use your proposal in Trezor for internal purposes: https://github.com/trezor/trezor-firmware/blob/master/core/src/apps/common/paths.py

We use almost exactly the same syntax with one extension:

0    - m/* can be followed by any number of _unhardened_ path components
1    - m/*' can be followed by any number of _hardened_ path components
2    - m/** can be followed by any number of _any_ path components

dgpv commented at 2:04 pm on February 19, 2021: contributor

I think that

any number of path components

is dangerous when using it for path restrictions (as ‘can we allow a change output to go to this path’) because it creates a possibility of some arbitrary paths to pass the ‘filter’ of the template, and create a situation where change amount can be held ransom, for example. Because of this, I made decision to use * to denote only a range of indexes at one level, rather than ‘any path with matching prefix’.

What is the usecase for allowing an arbitrary-length path tail ? Is it justified vs the dangers it can enable ? Can it be substituted with just using different match functions (full_match vs prefix_match) ?

dgpv commented at 2:06 pm on February 19, 2021: contributor

edited the above comment: ‘can we allow to sign for this path’ -> ‘can we allow a change output to go to this path’ because that’s what I meant actually.

dgpv commented at 8:46 am on February 21, 2021: contributor

@prusnak what do you think about switching from square brackets to curly brackets to denote index ranges ? (on the reason that square brackets are used for other purposes in descriptors)

prusnak commented at 10:24 am on February 21, 2021: contributor

@prusnak what do you think about switching from square brackets to curly brackets to denote index ranges ? (on the reason that square brackets are used for other purposes in descriptors)

I don’t mind this

luke-jr commented at 7:12 pm on April 25, 2021: member

@dgpv Were you going to add a bit on compatibility?

dgpv force-pushed on May 11, 2021

dgpv cross-referenced this on May 11, 2021 from issue BIP 129: Bitcoin Secure Multisig Setup (BSMS) by hugohn

dgpv force-pushed on May 11, 2021

dgpv commented at 12:48 pm on May 11, 2021: contributor

Changed the chars to describe ranges from {} to []: https://github.com/dgpv/bips/commit/4af4299ba286acb953a0adad7f2a9c9137376ce9

Added the description of Wildcard range ("*"): https://github.com/dgpv/bips/commit/a3204d41a57b0e24d8b40b27c560e1b37f3c7b1d

Added Compatibility section: https://github.com/dgpv/bips/commit/56de314913351c61d0e255197a0d046564f27a33

luke-jr renamed this:
~~Add BIP draft for BIP32 path templates~~
BIP 88: Templates for Hierarchical Deterministic derivation paths
on May 14, 2021

luke-jr commented at 10:55 pm on May 14, 2021: member

Assigned BIP number 88. Please rename & update README

dgpv force-pushed on May 15, 2021

Add BIP draft for BIP32 path templates 2305c5bda6

bip-path-templates: Change chars for ranges from "[]" to "{}" 6ffc3542f8

bip-path-templates: describe Wildcard index range c90c76bc1b

bip-path-templates: Add Compatibility section 25f8c3e694

dgpv force-pushed on May 15, 2021

dgpv commented at 6:32 am on May 15, 2021: contributor

Done. @luke-jr

dgpv commented at 6:33 am on May 15, 2021: contributor

I dropped the word “derivation” from the title to fit into 44 max chars limit.

BIP88: number assigned, rename file and update README 3d9a359d1d

Rspigler commented at 10:25 am on May 15, 2021: contributor

Strong Concept ACK

Rspigler commented at 10:50 am on May 15, 2021: contributor

@dgpv Trying to go through this, have some questions. Are you on IRC?

dgpv commented at 4:10 pm on May 15, 2021: contributor

I think you can just ask here, in a comment at relevant line of the file.

I’ve changed the status from “Draft” to “Proposed”, because it seemed that the only disagreement that were emerged was about {} vs [], and it is settled now. But if you had thoughts that may warrant further discussion, then maybe it should stay at the “Draft” status a bit longer…

in bip-0088.mediawiki:98 in 3d9a359d1d outdated

93+
94+Template starts with optional prefix "m/", and then one or more sections delimited by the slash character ("/").
95+
96+Implementations MAY limit the maximum number of sections.
97+
98+Each section consists of ''index template'', optionally followed by the hardened marker: either an apostrophe ("'") or letter "h".

Rspigler commented at 6:13 pm on May 15, 2021:

nit: “’” is hard to read (for me), <code>'</code> is easier

dgpv commented at 7:48 am on May 16, 2021:

Fixed in https://github.com/bitcoin/bips/pull/1025/commits/01679c8f29d0454d7003805d30031623f194a93b

Also used more <code> tags instead of double quotes, in https://github.com/bitcoin/bips/pull/1025/commits/b628a13e2124c7f927c033f5fed81671cb559ae5

in bip-0088.mediawiki:108 in 3d9a359d1d outdated

103+* A single "*" character, which denotes any value from 0 to 2147483647 ("Wildcard index template")
104+* The <nowiki>"{"</nowiki> character, followed by a number of ''index ranges'' delimited by commas (","), followed by <nowiki>"}"</nowiki> character ("Ranged index template")
105+
106+Implementations MAY limit the maximum number of index ranges within the Ranged index template.
107+
108+If an index template is immediately followed by hardened marker, this means that all values specified in this index template is to be increased by 2147483648 for the purposes of matching.

Rspigler commented at 6:20 pm on May 15, 2021:

This confuses me? 2,147,483,648 is the max value allowed by BIP32/44. Why does hardening double this, and how is this allowed?

Rspigler commented at 6:38 pm on May 15, 2021:

I realized how dumb that was after typing it out… :facepalm: Disregard

For people reading: it’s 2^31 for hardened and non-hardened keys

Rspigler commented at 6:21 pm on May 15, 2021: contributor

I think it is my misunderstanding (and I don’t want to crowd the PR), but I will comment here, thanks

in bip-0088.mediawiki:128 in 3d9a359d1d outdated

123+Constraints:
124+
125+# To avoid ambiguity, whitespace MUST NOT appear within the path template.
126+# Commas within the Ranged index template MUST only appear in between index ranges.
127+# To avoid ambiguity, an index range that matches a single value MUST be specified as Unit range.
128+# To avoid ambiguity, an index template that matches any value from 0 to 2147483647 MUST be specified as Wildcard index template

Rspigler commented at 6:26 pm on May 15, 2021:

If a template was restricted to (0-1,000) that is a value that is within (0-2147483647) - should that be represented as a Wildcard? I don’t think so, but I was confused with how this was worded.

dgpv commented at 5:30 am on May 16, 2021:

The wording may be confusing, I agree. Maybe it should say “an index template that will match any value from 0 to 2147483647 MUST be specified as Wildcard index template” ?

dgpv commented at 5:33 am on May 16, 2021:

hm, maybe it is better to explicitly specify, “an index range 0-2147483647 is not allowed, and MUST be specified as Wildcard index template instead”

dgpv commented at 7:49 am on May 16, 2021:

Rephrased in https://github.com/bitcoin/bips/commit/01679c8f29d0454d7003805d30031623f194a93b

in bip-0088.mediawiki:157 in 3d9a359d1d outdated

152+Full template can be combined with partial template, where partial template extends full template,
153+resulting in new, longer full template.
154+
155+Partial template can be combined with another partial template, resulting in new, longer partial template.
156+
157+Full template can not be combined with another full template.

Rspigler commented at 6:30 pm on May 15, 2021:

Can you provide examples for these?

dgpv commented at 5:37 am on May 16, 2021:

m/49/0 (full) 0/1/* (partial) m/49/0/1/* (combined)

1/{3-5} + 0/0/{1-5555} => 1/{3-5}/0/0/{1-5555} - combining two partial templates, resulting in a new partial template

That’s what I meant. Do you think something like this example should go into BIP text ?

Rspigler commented at 5:04 am on May 17, 2021:

That makes total sense to me now, maybe I was being dumb, but the examples helped. Your call. Only question is, when combining two partial templates, how do you know the order? Ex: 1/{3-5} + 0/0/{1-5555} => 1/{3-5}/0/0/{1-5555} or 1/{3-5} + 0/0/{1-5555} => 0/0/{1-5555}/1/{3-5}

Obviously, the first is more likely, but both

dgpv commented at 9:40 am on May 17, 2021:

When combining partial templates, the order is determined by the software that is combining it, and depend on the concrete usecase and the designation of each partial template (“account part”, “suffix part” of the template, etc)

I can’t even come up with a plausible example where this would be needed, but I see no need add any restriction on combining partial templates in this specification.

in bip-0088.mediawiki:161 in 3d9a359d1d outdated

156+
157+Full template can not be combined with another full template.
158+
159+Implementations MUST support parsing full templates and matching paths against full templates.
160+
161+Implementations MAY support parsing partial templates and matching portions of the paths against partial templates, as well as combining the templates.

Rspigler commented at 6:31 pm on May 15, 2021:

Why only ‘MAY’ for partial templates?

dgpv commented at 7:17 am on May 16, 2021:

Because partial templates are a more complex feature - it allows to make a compound template out of several partial templates. Not every implementation would want to have the extra logic needed for this.

in bip-0088.mediawiki:177 in 3d9a359d1d outdated

172+
173+Hardened indexes in this list should be represented by values from 2147483648 to 4294967295.
174+
175+The matching algorithm:
176+
177+    1. If the length of the path differs from the length of the template, fail

Rspigler commented at 6:48 pm on May 15, 2021:

Could you explain this for me? You used “path template” previously in the BIP (for example #1 and #8 under constraints), so I am confused by the different definitions of path and template?

Rspigler commented at 6:50 pm on May 15, 2021:

Do you mean section? as defined in the 2nd line under #Specification?

dgpv commented at 7:11 am on May 16, 2021:

“path” is something that is being matched, like m/44'/0'/0'/1/5, the “path template”, or simply “template” in this case, is something that the path is matched against, like m/44'/0'/0'/{0-1}/{0-5000}. Since the length of the template (number of sections in it) is the same as the length of the path (number of indexes in it), this matching step passes. If the template would be just m/44'/0'/0', for example, the matching would fail immediately. The implementation could implement partial match, of course, by taking a portion of the path of the same length as the template, and matching it, but I don’t think this needs to be specified.

Rspigler commented at 5:08 am on May 17, 2021:

Length has a lot of definitions, and was confusing. You have already defined sections. So maybe re-word as: If the number of sections of the path differs from the number of indexes of the path template, fail. Also might want to include that definition of path in the BIP

dgpv commented at 10:02 am on May 17, 2021:

Added the definitions of “length of the template”, “length of the path”: https://github.com/dgpv/bips/commit/abc113edd4bc2339c6b64689c0b33635615c297e

I don’t think that we should include the definition of the path. Throughout the text of this BIP, “BIP32 derivation path” is mentioned many times, and it is obvious that it is the main thing that the BIP88 itself is focused on.

BIP32 or BIP43 do not define “path”, while BIP44 just goes and uses the term “path” straight away without additional definition. I think we can just leave it as it is and not add specific definition for the path.

But if you have a good idea for such definition, it may not hurt to add it.

BIP88: clarifications, mistype fixes 01679c8f29

BIP88: use <code> tags more, instead of double quotes b628a13e21

BIP88: Add definition for "length of the template", "length of the path" abc113edd4

in bip-0088.mediawiki:194 in 3d9a359d1d outdated

189+
190+==Implementations==
191+
192+While the formal specification specifies an FSM, which would be convenient for implementation without access to rich string handling facilities, when such facilities are available, the implementation might use the whole-string deconstruction approach where the templates are first split into sections, then sections are split into index templates, and then each index template are parsed individually.
193+
194+A FSM-based approach can be made close to the formal specification, though, and the test data generated with TLC checker would give much better coverage for a FSM based implementation. If the template string contains several errors, an implementation that uses deconstruction apporach might detect some of these errors earlier than FSM-based implementation, and vise versa.

Rspigler commented at 6:52 pm on May 15, 2021:

nit: spelling - approach

dgpv commented at 7:49 am on May 16, 2021:

fixed in https://github.com/bitcoin/bips/commit/01679c8f29d0454d7003805d30031623f194a93b

luke-jr merged this on May 17, 2021

luke-jr closed this on May 17, 2021

luke-jr commented at 11:20 pm on May 17, 2021: member

Further changes can be added in additional PRs

Rspigler commented at 6:51 am on May 18, 2021: contributor

ACK commit abc113edd4bc2339c6b64689c0b33635615c297e

Happy with all the changes!

dgpv commented at 7:52 am on May 18, 2021: contributor

Thanks!

I didn’t add the Acknowledgements section in time before the BIP88 was merged, doing it in a separate PR: https://github.com/bitcoin/bips/pull/1123

BIP 88: Templates for Hierarchical Deterministic derivation paths #1025