Each section consists of ''index template'', optionally followed by the hardened marker: either an apostrophe (<code>'</code>) or letter <code>h</code>.
* A single <code>*</code> character, which denotes any value from 0 to 2147483647 ("Wildcard index template")
* The <code>{</code> character, followed by a number of ''index ranges'' delimited by commas (<code>,</code>), followed by <code>}</code> character ("Ranged index template")
Implementations MAY limit the maximum number of index ranges within the Ranged index template.
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.
Index range can be:
* An integer value from 0 to 2147483647 ("Unit range")
* An integer value from 0 to 2147483647, followed by the <code>-</code> character, followed by another integer value from 0 to 2147483647 ("Non-unit range")
For Non-unit range, value on the left side of the <code>-</code> character is the range_start, and the value on the right side of the <code>-</code> character is the range_end.
# If there is more than one index range within the Ranged index template, range_start of the second and any subsequent range MUST be larger than the range_end of the preceding range.
# To avoid ambiguity, if a hardened marker appears within any section in the path template, all preceding sections MUST also use the same hardened marker (either <code>h</code> or <code>'</code>).
# To avoid ambiguity, trailing slashes (for example, <code>1/2/</code>) and duplicate slashes (for example, <code>0//1</code>) MUST NOT appear in the template.
It may be desirable to have fully unambiguous encoding, where for each valid path template string, there is no other valid template string that matches the exact same set of paths. This would enable someone to compare templates for equality through a simple string equality check, without any parsing.
* Within Ranged index template, subsequent range MUST NOT start with the value that is equal to the end of the previous range plus one. Thus, <code>{1,2,3-5}</code> is not allowed, and should be specified as <code>{1-5}</code> instead. This rule might make templates less convenient for frequent edits, though.
Instead of requiring the second extra rule, implementations can simply replace one type of marker with another in the template strings before comparing them.
If the template does not start with <code>m/</code>, that means that this is a "partial" template, and it can be used to match a part of the path, in the contexts where this might be appropriate (for example, when constraints for the suffix of the path might be dynamic, while constraints for the prefix of the path are fixed).
Full template can be combined with partial template, where partial template extends full template,
resulting in new, longer full template.
Partial template can be combined with another partial template, resulting in new, longer partial template.
Full template can not be combined with another full template.
Implementations MUST support parsing full templates and matching paths against full templates.
Implementations MAY support parsing partial templates and matching portions of the paths against partial templates, as well as combining the templates.
The result of successful parsing of a valid path template can be represented by a list of sections, where each section is a list of index ranges, where index range is a tuple of (range_start, range_end). The length of the list of sections is also referred to as the "length of the template".
The matching is to be performed against a list of integer values that represent a BIP32 path (or a portion of BIP32 path, for partial templates). The length of this list is referred to as the "length of the path".
Non-hardened indexes in this list should be represented by values from 0 to 2147483647.
Hardened indexes in this list should be represented by values from 2147483648 to 4294967295.
The matching algorithm:
1. If the length of the path differs from the length of the template, fail
2. For each value V at position N in the path:
If for all index ranges within the section at position N in the template,
value V is either less than range_start, or greater than range_end, fail
3. Otherwise, succeed
==Formal specification==
The finite state machine (FSM) for the parser of the described template format,
and the matching formula are specified in TLA+ specification language at https://github.com/dgpv/bip32_template_parse_tplaplus_spec
The specification can be used with TLC checker and accompanying script to generate test data for the implementations.
==Implementations==
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.
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 approach might detect some of these errors earlier than FSM-based implementation, and vise versa.
* FSM implementation in C: https://github.com/dgpv/bip32_template_c_implementation
* FSM implementation in Python (micropython compatible): https://github.com/dgpv/bip32_template_python_implementation
* non-FSM implementation in python: BIP32PathTemplate class in bitcointx.core.key module of python-bitcointx library (https://github.com/Simplexum/python-bitcointx)
There is a discussion on path templating for bitcoin script descriptors at https://github.com/bitcoin/bitcoin/issues/17190, which proposes the format <code>xpub...{0,1}/*</code>, of which the <code>{0,1}/*</code> part would correspond to the partial path template in the format of this BIP.
<code>m/{44,49,84}'/0'/0'/{0-1}/{0-50000}</code> specifies a full template that matches both external and internal chains of BIP44, BIP49 and BIP84 paths, with a constraint that the address index cannot be larger than 50000
<code>{0-2,33,123}/*</code> specifies a partial template that matches non-hardened values 0, 1, 2, 33, 123 as first index, and any non-hardened value at second index
Special thanks to Peter D. Gray, Dr. Maxim Orlovsky, Robert Spigler and others for their feedback on the specification, and to Janine (github:@Enegnei) for the help in preparing the draft.
