[bitcoin-dev] BIP draft: BIP32 Path Templates

[bitcoin-dev] BIP draft: BIP32 Path Templates

[Dmitry Petukhov]

I think there should be standard format to describe constraints for
BIP32 paths.

I present a BIP draft that specifies "path templates" for BIP32 paths:

https://github.com/dgpv/bip32_template_parse_tplaplus_spec/blob/master/bip-path-templates.mediawiki

Matching against these templates allow to easily discern 'valid'
paths, that match the constraints, and 'invalid' paths, that exceed the
constraints. Extended motivation is given at the end of this message,
and in the text of the BIP draft.

A formal spec in TLA+ of a finite state machine implementing the parser
for the described format (and the matching operation) accompanies this
BIP draft: https://github.com/dgpv/bip32_template_parse_tplaplus_spec

This formal spec can be used with TLC model checker and a helper script
to generate thorough test data for implementations.

One (python) implementation of template parsing and matching already
exists (linked in the BIP draft).

Examples of the templates:

"m/[44,49,84]'/0'/0'/[0-1]/[0-50000]" 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

"[0-2,33,123]/*" 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

"*h/0" specifies a partial template that matches any hardened index
followed by any non-hardened index


Motivation:

BIP32 derivation path format is universal, and a number of schemes for
derivation were proposed in BIP43 and other documents, such as BIPs
44,45,49,84. The flexibility of the format allowed industry
participants to implement custom derivation shemes that fit particular
purposes, but not necessarily useful in general.

Unrestricted derivation path usage might be unsafe in certain contexts.
In particular, when "change" outputs of a transaction are sent to the
addresses derived via paths unknown to the sender, the sender might
loose access to the whole change amount.

A simplistic approach of hard-coding the checks for well-known paths
into software and firmware leads to reduced interoperability. Vendors
cannot choose custom paths that are appropriate for their particular,
non-general-purpose applications, and are forced to shoehorn their
solutions into using well-known paths, or convince other vendors to
support their custom paths. This approach scales poorly.

A flexible approach proposed is to define a standard notation for
"BIP32 path templates" that succintly describes the constraints to
impose on the derivation path.

Wide support for these path templates will increase interoperability
and flexibility of solutions, and will allow vendors and individual
developers to easily define their own custom restrictions. This way,
they will be able to deal with the risks of accidental or malicious use
of unrestricted derivation paths in a more flexible and precise manner.

Well-known path templates can be pre-configured by default on devices
and applications, but users can have an option to turn off the
templates that are not relevant to their uses.

Having standardized format for custom path templates will enable a
common approach to be developed to the enforcement of
application-specific path restrictions in devices and applications. One
example of such approach might be for devices to allow to install
application-specific profiles with path templates and possibly other
custom parameters. Care must be taken to prevent accidental
installation of malicious or incorrect profile, though. 

Re: [bitcoin-dev] BIP draft: BIP32 Path Templates

[David A. Harding]

[-- Attachment #1: Type: text/plain, Size: 848 bytes --]

On Thu, Jul 02, 2020 at 09:28:39PM +0500, Dmitry Petukhov via bitcoin-dev wrote:
> I think there should be standard format to describe constraints for
> BIP32 paths.
> 
> I present a BIP draft that specifies "path templates" for BIP32 paths:
> 
> https://github.com/dgpv/bip32_template_parse_tplaplus_spec/blob/master/bip-path-templates.mediawiki

Hi Dmitry,

How do path templates compare to key origin identification[1] in
output script descriptors?

Could you maybe give a specfic example of how path templates might be
used?  Are they for backups?  Multisig wallet coordination?  Managing
data between software transaction construction and hardware device
signing?

Thanks,

-Dave

[1] https://github.com/bitcoin/bitcoin/blob/master/doc/descriptors.md#key-origin-identification
    (See earlier in the doc for examples)

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] BIP draft: BIP32 Path Templates

[Dmitry Petukhov]

[-- Attachment #1: Type: text/plain, Size: 4135 bytes --]

IIUC, key origin identification specify chains of addresses, with
relation to specific keys. As the name suggests, they are for
identidication.

Path templates specify application-specific constraints for the
derivation paths. They are for imposing restrictions.

You could use path templates for identification, too, and in fact the
"path" part of the key origin identification would be a valid path
template. Path templates have potential to identify multiple chains
of addresses though, and I cannot say how useful it can be, if at all.

When a hardware wallet or some other type of autonomous signer signs a
transaction, there are two points where HD derivation can occur: 1) when
signing an input 2) when checking if the output is the change output

The second case is occurs more often, I think (determining actual
amount sent), but the first case can have uses, too -- when an
autonomous signer can impose restrictions on derivation path based on
the identity of the user that request the signing, for example. 

In both of these points an application-specific or usecase-specific
signing scheme might require that only certain whitelisted derivation
paths are used (sending change to the known key, but using derivation
path unknown to the sender allows an attacker to hold the change amount
for ransom, for example)

An autonomous signer might not be aware of the restrictions used in
particular scheme, because it might be developed by different vendor
than the implementor of the particular scheme. Or it might be difficult
to update the firmware of autonomous signer when the checks of the
path constraints are hard-coded in the program code. Having constraints
specified as data would allow to place them in configuration of the
signer.

One particular example of this being a problem is how hardware wallet
vendors seem to be inclined to decide to just restrict the derivation
paths allowed for the change addresses to the set of "well-known"
paths.

Such restrictions, on one hand, break custom schemes used by
various software solutions that rely on the ability of hardware wallet
to sign custom paths, and on the other hand, such hardcoded restrictions
might happen to be too relaxed, if the set of "well-known" path grows,
or the user or software vendor knows for sure that they won't use
addresses past index 1000, for example.

The format for the path templates described in the presented BIP draft
aims to provide a building block for interoperability between various
hardware and software vendors in regard to this particular task of
specifying derivation path restrictions.

Adopting a common format for specifying restictions is a flexible
alternative to everyone adopting a rigid set of "well-known" paths.
Such a set will inevitably grow, and those who really need custom
paths and do not have resources to push for standardization of their
custom paths will be at a disadvantage.

My hope is that having a clear specification and (possibly, in the
future) permissibly licensed quality implementations would make
adopting such format easier for vendors.

В Fri, 3 Jul 2020 10:39:45 -0400
"David A. Harding" <dave@dtrt.org> wrote:

> On Thu, Jul 02, 2020 at 09:28:39PM +0500, Dmitry Petukhov via
> bitcoin-dev wrote:
> > I think there should be standard format to describe constraints for
> > BIP32 paths.
> > 
> > I present a BIP draft that specifies "path templates" for BIP32
> > paths:
> > 
> > https://github.com/dgpv/bip32_template_parse_tplaplus_spec/blob/master/bip-path-templates.mediawiki
> >  
> 
> Hi Dmitry,
> 
> How do path templates compare to key origin identification[1] in
> output script descriptors?
> 
> Could you maybe give a specfic example of how path templates might be
> used?  Are they for backups?  Multisig wallet coordination?  Managing
> data between software transaction construction and hardware device
> signing?
> 
> Thanks,
> 
> -Dave
> 
> [1]
> https://github.com/bitcoin/bitcoin/blob/master/doc/descriptors.md#key-origin-identification
> (See earlier in the doc for examples)


[-- Attachment #2: Цифровая подпись OpenPGP --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] BIP draft: BIP32 Path Templates

[Dmitry Petukhov]

[-- Attachment #1: Type: text/plain, Size: 1276 bytes --]


В Fri, 3 Jul 2020 21:53:44 +0500
Dmitry Petukhov via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
wrote:

> The format for the path templates described in the presented BIP draft
> aims to provide a building block for interoperability between various
> hardware and software vendors in regard to this particular task of
> specifying derivation path restrictions.

One example of an interoperability workflow might be:

A software vendor that utilizes custom derivation paths in their
schemes create a "profile" that contains the constraints on the paths
(and possibly other parameters, but this is out of scope of the
proposal) for their particular scheme. In a simple case it might just
be a path template string provided in the documentation.

A user of a software solution from that vendor takes a hardware wallet
that supports path templates (or richer "profiles") and installs the
profile for that solution into hardware wallet. In a simple case, the
user just pastes a path template string into some configuration utility
program and then confirms the setting on-device.

The device statrts to enforce the constraints specified in the template
(or "profile"), and the software solution works as intended by the
software vendor.




[-- Attachment #2: Цифровая подпись OpenPGP --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] BIP draft: BIP32 Path Templates

[Dmitry Petukhov]

[-- Attachment #1: Type: text/plain, Size: 407 bytes --]

В Fri, 3 Jul 2020 21:53:44 +0500
Dmitry Petukhov via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
wrote:

> My hope is that having a clear specification and (possibly, in the
> future) permissibly licensed quality implementations would make
> adopting such format easier for vendors.

I have added a C implementation (MIT-licensed):
https://github.com/dgpv/bip32_template_c_implementation

[-- Attachment #2: Цифровая подпись OpenPGP --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] BIP draft: BIP32 Path Templates

[Dmitry Petukhov]

[-- Attachment #1: Type: text/plain, Size: 476 bytes --]

I have added a Python reference implementation of BIP32 path templates,
that is also compatible with micropython:

https://github.com/dgpv/bip32_template_python_implementation

The FSM formal spec has received a small corrections since the
announcement, and the reference implementations (C and this new python
implementation) are tested even more thoroughly now.

I submitted a PR to the bips repo:
https://github.com/bitcoin/bips/pull/1025, any comments welcome.

[-- Attachment #2: Цифровая подпись OpenPGP --]
[-- Type: application/pgp-signature, Size: 833 bytes --]