Subject: Re: [bitcoin-dev] Wallet policies for descriptor wallets

From: Salvatore Ingala <[email-masked]>
Date: Mon, 21 Nov 2022 12:27:25 +0100

Hi list,

Following up on this topic, I now opened a pull request with the BIP
proposal:

     https://github.com/bitcoin/bips/pull/1389

I also attempted a proof-of-concept of how an integration of wallet
policies to HWI might look like:

     https://github.com/bitcoin-core/HWI/pull/647

which might help to provide context, and also serves as a demo of the
possible UX flows with hardware signers (as currently implemented in the
Ledger bitcoin app).

There are no substantial changes to the initial version proposed to the
list:
- some additional restrictions to the allowed descriptors were added as
further simplifications;
- added test vectors and observations on backwards compatibility;
- general improvements to the text.

I look forward to your comments and improvements.
Salvatore Ingala

On Thu, 5 May 2022 at 16:32, Salvatore Ingala <[email-masked]>
wrote:

> In the implementation work to implement descriptors and miniscript support
> in hardware wallets [a][b], I encountered a number of challenges. Some of
> them are technical in nature (e.g. due to constraints of embedded
> development). Others are related to the attempts of shaping a good user
> experience; with bitcoin reaching more people who are not tech-savvy,
> self-custody is only as secure as what those newcomers can use easily
> enough.
>
> The main tool that I am using to address some of these challenges is a
> layer that sits _on top_ of descriptors/miniscript, while staying very
> close to it. Since there is nothing that is vendor-specific in the vast
> majority of the approach I'm currently using, I tried to distill it here
> for your comments, and will propose a BIP if this is deemed valuable.
>
> I called the language "wallet policies" (suggestions for a better name are
> welcome). I believe an approach based on wallet policies can benefit all
> hardware wallets (stateless or not) that want to securely support complex
> scripts; moreover, wallet policies are close enough to descriptors that
> their integration should be extremely easy for any software wallet that is
> currently using descriptors.
>
> [a]: https://blog.ledger.com/bitcoin-2 - early demo
> [b]: https://blog.ledger.com/miniscript-is-coming - miniscript example
>
>
> Salvatore Ingala
>
>
> ======================================================
>
> This document starts with a discussion on the motivation for wallet
> policies, followed by their formal definition, and some recommendations for
> implementations.
>
> == Rationale ==
>
> Output script descriptors [1] were introduced in bitcoin-core as a way to
> represent collections of output scripts. It is a very general and flexible
> language, designed to catch all the possible use-cases of bitcoin wallets
> (that is, if you know the script and you have the necessary keys, it will
> be possible to sign transactions with bitcoin-core's descriptor-based
> wallets).
>
> Unfortunately, descriptors are not a perfect match for the typical usage
> of hardware wallets. Most hardware wallets have the following limitations
> compared to a general-purpose machine running bitcoin-core:
>
> - they are embedded devices with limited RAM and computational power;
> - they might not be able to import additional private keys (all the keys
> are generated from a single seed via [BIP-32](
> https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki));
> - they might not have permanent storage (*stateless* hardware wallet
> design).
>
> Moreover, other limitations like the limited size of the screen might
> affect what design choices are available in practice. Therefore, minimizing
> the size of the information shown on-screen is important for a good user
> experience.
>
> A more native, compact representation of the wallet receive/change would
> also benefit the UX of software wallets using descriptors to represent
> software wallets using descriptors/miniscript for multisignature or other
> complex locking conditions.
>
> === Security and UX concerns of scripts in hardware wallets ===
>
> For a hardware wallet, allowing the usage of complex scripts presents
> challenges in terms of both security and user experience.
>
> ==== Security issues ====
>
> One of the security properties that hardware wallets strive to guarantee
> is the following: **as long as the user correctly verifies the information
> that is shown on the hardware wallet's screen before approving, no action
> can be performed without the user's consent**.
> This must hold even in scenarios where the attacker has full control of
> the machine that is connected to the hardware wallet, and can execute
> arbitrary requests or tamper with the legitimate user's requests.
>
> Therefore, it is not at all trivial to allow complex scripts, especially
> if they contain keys that belong to third parties.
> The hardware wallet must guarantee that the user knows precisely *what*
> "policy" is being used to spend the funds, and that the "unspent" funds (if
> any) will be protected by the same policy. This makes it impossible for an
> attacker to surreptitiously modify the policy, therefore stealing or
> burning user's funds.
>
> ==== UX issues ====
>
> With miniscript (and taproot trees) allowing substantially more complex
> spending policies to be used, it becomes more challenging to make sure that
> the user is able _in practice_ to verify the information on the screen.
> Therefore, there are two fundamental design goals to strive for:
> - Minimize the amount of information that is shown on screen - so that the
> user can actually validate it.
> - Minimize the number of times the user has to validate such information.
>
> Designing a secure protocol for the coordination of a descriptor wallet
> among distant parties is also a challenging problem that is out of scope in
> this document. See BIP-129 [2] for an approach designed for multisignature
> wallets.
>
> === Policy registration as a solution ===
>
> A solution to address the security concerns, and part of the UX concerns,
> is to have a *registration* flow for the wallet policy in the hardware
> wallet. The "wallet policy" must contain enough information to generate all
> the relevant addresses/scripts, and for the hardware wallet to identify the
> keys that it controls and that are needed to spend the funds sent to those
> addresses.
>
> Before a new policy is used for the first time, the user will register a
> `wallet policy` into the hardware wallet. While the details of the process
> are out of scope in this document, the flow should be something similar to
> the following:
>
> 1) The software wallet initiates a _wallet policy registration_ on the
> hardware wallet; the information should include the wallet policy, but also
> a unique *name* that identifies the policy.
> 2) The hardware wallet shows the wallet policy to the user using the
> secure screen.
> 3) After inspecting the policy and comparing it with a trusted source (for
> example a printed backup), the user approves the policy.
> 4) If stateful, the hardware wallet persists the policy in its permanent
> memory; if stateless, it returns a "proof of registration".
>
> The details of how to create a proof of registration are out of scope for
> this document; using a *message authentication codes* on a hash committing
> to the wallet policy, its name and any additional metadata is an effective
> solution if correctly executed.
>
> Once a policy is registered, the hardware wallet can perform the usual
> operations securely:
> - generating receive and change addresses;
> - showing addresses on the secure screen;
> - sign transactions spending from a wallet, while correctly identifying
> change addresses and computing the transaction fees.
>
> Before any of the actions mentioned above, the hardware wallet will
> retrieve the policy from its permanent storage if stateful; if stateless it
> will validate the _proof of registration_ before using the wallet policy
> provided by the client.
> Once the previously registered policy is correctly identified and approved
> by the user (for example by its name), and *as long as the policy
> registration was executed securely*, hardware wallets can provide a user
> experience similar to the usual one for single-signature transactions.
>
> === Avoiding blowup in descriptor size ===
>
> While reusing a pubkey in different branches of a miniscript is explicitly
> forbidden by miniscript (as it has certain negative security implications),
> it is still reasonable to reuse the same *xpub* in multiple places, albeit
> with different final steps of derivation (so that the actual pubkeys that
> are used in the script are indeed different).
>
> For example, using Taproot, a *3*-of-*5* multisignature wallet could use:
> - a key path with a 5-of-5 MuSig
> - a script tree with a tree of 10 different 3-of-3 MuSig2 scripts, that
> are generated, plus a leaf with a fallback *3*-of-*5* multisignature using
> plain multisignature (with `OP_CHECKSIGADD`).
>
> This could look similar to:
>
> ```
> tr(musig2(xpubA,xpubB,xpubC,xpubD,xpubE)/<0;1>/*), {
>   {
>     {
>       pk(musig2(xpubA,xpubB,xpubC)/<2;3>/*),
>       {
>         pk(musig2(xpubA,xpubB,xpubD)/<4;5>/*)
>         pk(musig2(xpubA,xpubB,xpubE)/<6;7>/*),
>       }
>     },
>     {
>       pk(musig2(xpubA,xpubC,xpubD)/<8;9>/*),
>       {
>         pk(musig2(xpubA,xpubC,xpubE)/<10;11>/*),
>         pk(musig2(xpubA,xpubD,xpubE)/<12;13>/*)
>       }
>     }
>   },
>   {
>     {
>       pk(musig2(xpubB,xpubC,xpubD)/<14;15>/*),
>       pk(musig2(xpubB,xpubC,xpubE)/<16;17>/*)
>     },
>     {
>       pk(musig2(xpubB,xpubD,xpubE)/<18;19>/*),
>       {
>         pk(musig2(xpubC,xpubD,xpubE)/<20;21>/*),
>         sortedmulti_a(3,
>           xpubA/<22;23>/*,
>           xpubB/<22;23>/*,
>           xpubC/<22;23>/*,
>           xpubD/<22;23>/*,
>           xpubE/<22;23>/*)
>       }
>     }
>   }
> })
> ```
>
> Note that each root xpub appears 8 times. With xpubs being up to 118 bytes
> long, the length of the full descriptor can get extremely long (the problem
> gets *exponentially* worse with larger multisignature schemes).
>
> Replacing the common part of the key with a short key placeholder and
> moving the key expression separately helps to keep the size of the wallet
> policy small, which is crucial to allow human inspection in the
> registration flow.
>
> === Restrictions on the supported descriptors ====
>
> The policy language proposed in this document purposely targets only a
> stricter subset of the output descriptors language, and it attempts to
> generalize in the most natural way the approach that is already used for
> single-signature *accounts* (as described in BIP-44 [3], BIP-49 [4], BIP-84
> [5], or BIP-86 [6]), or in multisignature setups (see for example BIP-48
> [7] and BIP-87 [8]).
>
> Unlike the BIPs mentioned above, it is not tied to any specific script
> template, as it applies to arbitrary scripts that can be represented with
> descriptors and miniscript.
>
> Supporting only a reduced feature set when compared to output descriptors
> helps in implementations (especially on hardware wallets), while attempting
> to capture all the common use cases. More features can be added in the
> future if motivated by real world necessity.
>
> By keeping the structure of the wallet policy language very close to that
> of descriptors, it should be straightforward to:
> - write wallet policy parsers;
> - extract the descriptors defined by a wallet policy;
> - convert a pair of descriptors describing a wallet "account" used in
> current implementations into the corresponding wallet policy.
>
>
> == Wallet policies ==
>
> This section formally defines wallet policies, and how they relate to
> output script descriptors.
>
> === Formal definition ===
>
> A wallet policy is composed by a wallet descriptor template, together with
> a vector of key information items.
>
> ==== Wallet descriptor template ====
>
> A wallet descriptor template is a `SCRIPT` expression.
>
> `SCRIPT` expressions:
> - `sh(SCRIPT)` (top level only): P2SH embed the argument.
> - `wsh(SCRIPT)` (top level or inside `sh` only): P2WSH embed the argument.
> - `pkh(KP)` (not inside `tr`): P2PKH output for the given public key (use
> `addr` if you only know the pubkey hash).
> - `wpkh(KP)` (top level or inside `sh` only): P2WPKH output for the given
> compressed pubkey.
> - `multi(k,KP_1,KP_2,...,KP_n)`: k-of-n multisig script.
> - `sortedmulti(k,KP_1,KP_2,...,KP_n)`: k-of-n multisig script with keys
> sorted lexicographically in the resulting script.
> - `tr(KP)` or `tr(KP,TREE)` (top level only): P2TR output with the
> specified key as internal key, and optionally a tree of script paths.
> - any valid miniscript template (inside `wsh` or `tr` only).
>
> `TREE` expressions:
> - any `SCRIPT` expression
> - An open brace `{`, a `TREE` expression, a comma `,`, a `TREE`
> expression, and a closing brace `}`
>
> Note: "miniscript templates" are not formally defined in this version of
> the document, but it is straightforward to adapt this approach.
>
> `KP` expressions (key placeholders) consist of
> - a single character `@`
> - followed by a non-negative decimal number, with no leading zeros (except
> for `@0`).
> - possibly followed by either:
>   - the string  `/**`, or
>   - a string of the form `/<NUM;NUM>/*`, for two distinct decimal numbers
> `NUM` representing unhardened derivations
>
> The `/**` in the placeholder template represents commonly used paths for
> receive/change addresses, and is equivalent to `<0;1>`.
>
> The placeholder `@i` for some number *i* represents the *i*-th key in the
> vector of key origin information (which must be of size at least *i* + 1,
> or the wallet policy is invalid).
>
> ==== Key informations vector ====
>
> Each element of the key origin information vector is a `KEY` expression.
>
> - Optionally, key origin information, consisting of:
>   - An open bracket `[`
>   - Exactly 8 hex characters for the fingerprint of the master key from
> which this key is derived from (see [BIP32](
> https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki) for
> details)
>   - Followed by zero or more `/NUM'` path elements to indicate hardened
> derivation steps between the fingerprint and the xpub that follows
>   - A closing bracket `]`
> - Followed by the actual key, which is either
>   - a hex-encoded pubkey, which is either
>     - inside `wpkh` and `wsh`, only compressed public keys are permitted
> (exactly 66 hex characters starting with `02` or `03`.
>     - inside `tr`, x-only pubkeys are also permitted (exactly 64 hex
> characters).
>   - a serialized extended public key (`xpub`) (as defined in [BIP 32](
> https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki))
>
> The placeholder `@i` for some number *i* represents the *i*-th key in the
> vector of key orIgin information (which must be of size at least *i* + 1,
> or the wallet policy is invalid).
>
> The policy template is invalid if any placeholder `@i` has derivation
> steps while the corresponding `(i+1)`-th element of the keys vector is not
> an xpub.
>
> ==== Additional rules ====
>
> The wallet policy is invalid if any placeholder expression with additional
> derivation steps is used when the corresponding key information is not an
> xpub.
>
> The key information vector *should* be ordered so that placeholder `@i`
> never appear for the first time before an occurrence of `@j`  for some `j <
> i`; for example, the first placeholder is always `@0`, the next one is
> `@1`, etc.
>
> === Descriptor derivation ===
>
> From a wallet descriptor template (and the associated vector of key
> informations), one can therefore obtain the 1-dimensional descriptor for
> receive and change addresses by:
>
> - replacing each key placeholder with the corresponding key origin
> information;
> - replacing every `/**`  with `/0/*` for the receive descriptor, and
> `/1/*` for the change descriptor;
> - replacing every `/<M,N>` with  `/M` for the receive descriptor, and `/N`
> for the change descriptor.
>
> For example, the wallet descriptor `pkh(@0/**)` with key information
> `["[d34db33f/44'/0'/0']xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL"]`
> produces the following two descriptors:
>
> - Receive descriptor:
> `pkh([d34db33f/44'/0'/0']xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL/0/*)`
>
> - Change descriptor:
> `pkh([d34db33f/44'/0'/0']xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL/1/*)`
>
> === Implementation guidelines ===
>
> Implementations must not necessarily implement all of the possible wallet
> policies defined by this standard, but it is recommended to clearly
> document any limitation.
>
> Implementations can add additional metadata that is stored together with
> the wallet policy for the purpose of wallet policy registration and later
> usage. Metadata can be vendor-specific and is out of the scope of this
> document.
>
> Any implementation in a general-purpose software wallet allowing arbitrary
> scripts (or any scripts that involve external cosigners) should put great
> care into a process for backing up a wallet policy. In fact, unlike typical
> single-signature scenarios, the seed alone is no longer enough to discover
> wallet policies with existing funds, and the loss of the backup is likely
> to lead to permanent loss of funds.
>
> Avoiding key reuse among different wallet accounts is also extremely
> important, but out of scope for this document.
>
> == Examples ==
>
> Some examples of wallet descriptor templates (vectors of keys omitted for
> simplicity):
> - Template for a native segwit account:
>   wpkh(@0/**)
> - Template for a taproot BIP86 account:
>   tr(@0/**)
> - Template for a native segwit 2-of-3:
>   wsh(sortedmulti(2,@0/**,@1/**,@2/**))
> - Template with miniscript for "1 of 2 equally likely keys":
>   wsh(or_b(pk(@0/**),s:pk(@1/**)))
>
> More examples (esp. targeting miniscript on taproot) will be added in the
> future.
>
> == References ==
>
> * [1] - Output Script Descriptors:
> https://github.com/bitcoin/bitcoin/blob/master/doc/descriptors.md
> * [2] - BIP-129 (Bitcoin Secure Multisig Setup):
> https://github.com/bitcoin/bips/blob/master/bip-0129.mediawiki
> * [3] - BIP-44:
> https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki
> * [4] - BIP-49:
> https://github.com/bitcoin/bips/blob/master/bip-0049.mediawiki
> * [5] - BIP-84:
> https://github.com/bitcoin/bips/blob/master/bip-0084.mediawiki
> * [6] - BIP-86:
> https://github.com/bitcoin/bips/blob/master/bip-0086.mediawiki
> * [7] - BIP-48:
> https://github.com/bitcoin/bips/blob/master/bip-0048.mediawiki
> * [8] - BIP-87:
> https://github.com/bitcoin/bips/blob/master/bip-0087.mediawiki
>
>