Date: Thu, 2 Jul 2020 21:28:39 +0500
From: Dmitry Petukhov <dp@simplexum.com>
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <20200702212839.2d59e435@simplexum.com>
Organization: simplexum.com
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Subject: [bitcoin-dev] BIP draft: BIP32 Path Templates
Precedence: list

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.