public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
* [bitcoin-dev] Wallet policies for descriptor wallets
@ 2022-05-05 14:32 Salvatore Ingala
  2022-05-08 17:41 ` Billy Tetrud
                   ` (3 more replies)
  0 siblings, 4 replies; 9+ messages in thread
From: Salvatore Ingala @ 2022-05-05 14:32 UTC (permalink / raw)
  To: Bitcoin Protocol Discussion

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

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

[-- Attachment #2: Type: text/html, Size: 19806 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Wallet policies for descriptor wallets
  2022-05-05 14:32 [bitcoin-dev] Wallet policies for descriptor wallets Salvatore Ingala
@ 2022-05-08 17:41 ` Billy Tetrud
  2022-05-09 11:36 ` darosior
                   ` (2 subsequent siblings)
  3 siblings, 0 replies; 9+ messages in thread
From: Billy Tetrud @ 2022-05-08 17:41 UTC (permalink / raw)
  To: Salvatore Ingala, Bitcoin Protocol Discussion

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

I took a look at the spec for the wallet descriptor format, and I like the
concept of having placeholder variables for keys. It reduces the size of
the descriptor, makes it substantially easier for a human to
read/verify, especially in the future when we have more complex
scripts, and provides a nice format for a script template which can make it
easier to verify that you're using the same script template as something
else (ie besides using different keys). I think the `/**` syntax is an
improvement over the current descriptor format, however it is a bit awkward
and inflexible. My understanding is that some of this inflexibility comes
from the goal of reducing memory usage, and I don't think I have a good
enough handle on that part of things to usefully comment. I've put
additional comments and suggestions on the format in this github issue
<https://github.com/LedgerHQ/app-bitcoin-new/issues/35>.

I think it would be very useful to come to agreement on a more flexible
format that can support a much broader set of use cases, and can
potentially be a widely supported standard. I understand low-ram devices
might have a much harder time using more flexible (and complex) formats.







On Thu, May 5, 2022 at 9:39 AM Salvatore Ingala via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> 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
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 22174 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Wallet policies for descriptor wallets
  2022-05-05 14:32 [bitcoin-dev] Wallet policies for descriptor wallets Salvatore Ingala
  2022-05-08 17:41 ` Billy Tetrud
@ 2022-05-09 11:36 ` darosior
  2022-05-10  9:37   ` Salvatore Ingala
  2022-09-29 23:56   ` Andrew Poelstra
  2022-05-17  8:44 ` Salvatore Ingala
  2022-11-21 11:27 ` Salvatore Ingala
  3 siblings, 2 replies; 9+ messages in thread
From: darosior @ 2022-05-09 11:36 UTC (permalink / raw)
  To: Salvatore Ingala, Bitcoin Protocol Discussion

Thanks for taking the time to write up about the implementation of output descriptors on signing devices, and
for proposing a method to overcome encountered difficulties for the following implementers.

I have some questions with regard to the modifications to the descriptor language required to make the
registration flow reasonable on a signing device.

To sum up, starting from the currently spec'd output descriptors [0] you need:
1. The `<NUM;NUM>` optimization for the common usecase of using 2 descriptors at different derivation indices
   for receive and change. [1]
2. The `/**` optimization for the common usecase of `/<0;1>` for point 1).
3. A new key expression `@i` referring to an index in a list of keys.

The first point was already discussed at great length [2]. Whether or not we agree using the derivation path
for change detection is a sane thing to do, most signing devices need to support this to not break
compatibility. I think the advantage boils down to not make the user write two almost-similar descriptors on
its backup, since it doesn't necessarily help readibility for human verification.

I'm not so sure about the second point. Is another deviation from the standard worth it just for saving 3
characters?
Disgressing, if we are to have a carve-out in the descriptor language for the common usecase of change/receive
keychains maybe your `/**` applies better than the proposed `/<NUM;NUM>` as the latter can open the door to
further carve-out requests.

For the third point, it does indeed seem unrealistic to check both the keys and the descriptor at the same
time. Even just because of the screen size (if the width an xpub is, what, 3 times the width of your screen,
by the time you finished verifying it you have forgotten the descriptor context in which this key was!). It
becomes harder as you get larger descriptors with Miniscript or Taproot, as you mentioned. Even the Miniscript
compiler at [3] supports key aliasing to workaround the inconvenience of long keys.
However, why does it need to be a change to the descriptor language? It looks a lot like something that needs
to be handled at the application level with key aliasing. The flow would be first to register known keys, and
then when registering a descriptor the keys would be replaced by their aliases for smoother verification. For
stateless devices, the registration of keys could use the same flow you described for descriptors.
In the end it's just replacing the vector and indices with a mapping and label, which make it a *much* better
UX (checking aliases vs looking up indices in a vector). For instance:
    Key registration:
        Alice: xpub6FLhTbeNidZkyC729yW6K6a5zuDxKUL8Q6oZm4XG2ov9PdxAyyDNEUm3jet8ENnvYsy6nCgsofN6FeVxakLDTdWGoxtmoYcu2exhqh9HjtV
        Bob: xpub6CoUua86qHYdDmnQL7imGN3zUMpVjRT4uDtRxYvfFj2v8JRvsaaGtf9ggv9NiL8sx3rFh6po92WBChwb37gDGuuU2Qo7zi3ZKC9cLjAsdQw
        Notary: xpub6DjUwtKmK7uqsd5p9w3eoJ4cjuML51nW85BTWuBaHEoxfmDGD3uPf6ZghsVeyuZUSuYEL4ajkVrfXzmotHHPtf6oBNYUQDSSBD4zUEiDoap

    Descriptor registration (policy language for simpl.):
        tr(NUMS,{
            multi(2,Alice,Bob),
            and(older(52560),and(Notary,Alice)),
            and(older(52560),and(Notary,Bob))
        })

In conclusion, if we were to have an optimization in the descriptor language for the common receive/change
usecase, i don't think you need another "wallet policy language" than the existing output descriptors language
with key aliasing/registration?


Unrelated question, since you mentioned `musig2` descriptors in this context. I thought Musig2 wasn't really
feasible for hardware signing devices, especially stateless ones. Do you think/know whether it is actually
possible for a HW to take part in a Musig2?


Thanks,
Antoine

[0] https://github.com/bitcoin/bips/blob/master/bip-0380.mediawiki
[1] https://github.com/bitcoin/bitcoin/pull/22838
[2] https://github.com/bitcoin/bitcoin/issues/17190
[3] https://bitcoin.sipa.be/miniscript/


------- Original Message -------
Le jeudi 5 mai 2022 à 4:32 PM, Salvatore Ingala via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> a écrit :


> 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


^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Wallet policies for descriptor wallets
  2022-05-09 11:36 ` darosior
@ 2022-05-10  9:37   ` Salvatore Ingala
  2022-09-29 23:56   ` Andrew Poelstra
  1 sibling, 0 replies; 9+ messages in thread
From: Salvatore Ingala @ 2022-05-10  9:37 UTC (permalink / raw)
  To: darosior; +Cc: Bitcoin Protocol Discussion

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

Hi Antoine and Billy,

Thank you for your comments and for looking into the proposal.

On Mon, 9 May 2022 at 12:36, darosior <darosior@protonmail.com> wrote:

> 1. The `<NUM;NUM>` optimization for the common usecase of using 2
> descriptors at different derivation indices
>    for receive and change. [1]
> 2. The `/**` optimization for the common usecase of `/<0;1>` for point 1).
>
> [...]
>
> I'm not so sure about the second point. Is another deviation from the
> standard worth it just for saving 3
> characters?
>

I agree with the concerns of both you and Billy on the `\**` syntax, and it
is certainly not a crucial part of the proposal, as it is arguably
redundant once `\<0;1>` is available.
I have been using it since before the `\<0;1>` syntax was proposed (afaik),
and I thought I would leave it mostly for the sake of optimizing the UX in
the most common use cases. I think that

    sh(sortedmulti(2,@0/**,@1/**,@2/**))

is quite a lot more readable (especially on a small screen) than

    sh(sortedmulti(2,@0/<0;1>/*,@1/<0;1>/*,@2/<0;1>/*))

Apart from the additional 5 characters *per placeholder*, there are a lot
more numbers to parse for the user.

Yet, I'm not too attached to the feature as it is probably not very useful
in taptrees. For the future, I expect further improvements will come from
the hardware wallets analyzing the wallet policy and recognizing the
commonly used patterns. No reason to show the full taptree of a complex
3-of-5 multisig setup − you can just say "Taproot 3-of-5 multisig". Show
the full taptree policy should be reserved for the 1% of advanced use-cases
that are not in the catalogue.

Slightly off-topic, but my impression is that descriptors are outgrowing
their original scope (probably the reason for sipa's comments[1] on the
early proposals for multiple derivation paths in one descriptor).
I think there is a case to be made for keeping the language of descriptors
limited to represent either (1) a single output, or (2) a list of outputs
with the `/*` syntax; in this interpretation, the `/<m;n>` syntax would
entirely be on a separate layer (the `combo` descriptor[2] would also be
extraneous in this interpretation).
I tried to design the policy wallet language in a way that is agnostic to
these details of descriptor specs (since I target a _subset_ of
descriptors, it will work either way).

However, why does it need to be a change to the descriptor language? It
> looks a lot like something that needs
> to be handled at the application level with key aliasing.


Key aliasing is not part of descriptors; therefore, "descriptors with key
aliasing" are still a language on top of descriptors.

Adding key aliases will indeed be a great UX improvement, but in my opinion
it is better built on top of wallet policies, rather than within the
language itself.
Note that by separating the *wallet descriptor template* from the keys
themselves, such a feature is already facilitated. Moreover, wallet
policies separate the KEY expressions of descriptors into two semantically
relevant parts: only the xpub and its origin info goes into the "vector of
key information", while the receive/change part of the derivation is kept
in the placeholder (therefore in the descriptor template). Adding
restrictions is also useful: `xpub/1/2/3/4/<0;1>/5/6/*` might be valid
miniscript, but supporting this kind of thing would be (arguably)
unreasonable and a lot more complicated for hardware wallets; therefore,
placeholders and key informations are a lot more limited in the wallet
policy language than their miniscript counterpart.

While I understand that descriptors are designed with a maximum flexibility
mindset, a minimized feature set is very valuable for hardware wallets, and
I believe it can be done with little to no practical loss of use cases.
Restrictions can be lifted in future versions when the need arises.

I think to better suit the needs of both hardware and software wallets, you
need both the *extensions* and the *restrictions*. That's why I propose to
keep them separated, rather than suggesting changes to descriptors.

Unrelated question, since you mentioned `musig2` descriptors in this
> context. I thought Musig2 wasn't really
> feasible for hardware signing devices, especially stateless ones. Do you
> think/know whether it is actually
> possible for a HW to take part in a Musig2?
>

I certainly have some more homework to do on musig2, and for this proposal
I was only concerned with making sure the wallet policy language won't
break with future upgrades to descriptors.
Yet, as far as I understand , the complications for hardware wallets are
(1) possible lack of good quality randomness, and (2) need to keep state
during a signing session. Ledger signers have a hardware TRNG, and while
the design is generally stateless, there is flash memory that can be used
to store the secret nonce during a signing session (or, more likely, a few
parallel signing sessions). Therefore, I don't think there are technical
blockers for musig2.

Salvatore


[1] https://github.com/bitcoin/bitcoin/issues/17190#issuecomment-543845642
[2] https://github.com/bitcoin/bips/blob/master/bip-0384.mediawiki

[-- Attachment #2: Type: text/html, Size: 6486 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Wallet policies for descriptor wallets
  2022-05-05 14:32 [bitcoin-dev] Wallet policies for descriptor wallets Salvatore Ingala
  2022-05-08 17:41 ` Billy Tetrud
  2022-05-09 11:36 ` darosior
@ 2022-05-17  8:44 ` Salvatore Ingala
  2022-11-21 11:27 ` Salvatore Ingala
  3 siblings, 0 replies; 9+ messages in thread
From: Salvatore Ingala @ 2022-05-17  8:44 UTC (permalink / raw)
  To: Bitcoin Protocol Discussion

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

Hi all,

TL;DR: It is easy to convert from wallet policy to descriptors and back;
imho aliases are better left out of descriptors in real world usage; some
more examples given.

I received some very useful feedback on the wallet policy proposal (in this
list and outside); that also led me to realize that my initial post lacked
some clarity and more practical examples.

This post wants to:
- clarify that extracting descriptors from the wallet policy is trivial;
- argue that figuring out the wallet policy (template and list of keys
information) from the descriptor is reasonably easy − automatable for sane
descriptors currently in use, and much more general ones as well;
- give an idea of what the information shown on a hardware wallet screen
would look like (emphasizing compactness);
- explain my point of view on "descriptors with aliases".

This gist demoes conversions from wallet policies to descriptors, and back:
https://gist.github.com/bigspider/10df51401be3aa6120217c03c2836ffa

Note that I would expect/hope software wallets to prefer working directly
with wallet policies − but it might help to have automated tools for the
conversion, for interoperability with tools that do not adopt wallet
policies.

(All the following examples use the `/**` notation as a shortcut for
`/<0,1>/*`; this notation might be dropped without consequences on the rest
of the proposal.)

All the keys in the example I'm proposing are followed by /**. It is
unclear to me if hardware wallets should allow *registration* of wallet
policies with static keys (that is, without any range operator), as that
would incentivize key reuse. The specs still support it as there might be
other use cases.

The policy for miniscript examples not using taproot was generated with the
online compiler: https://bitcoin.sipa.be/miniscript. Many examples are also
borrowed from there.
(To the best of my knowledge, there is no publicly released compiler for
miniscript on taproot, yet)

Note on aliases: it has been pointed out that many miniscript
implementations internally use aliases to refer to the keys. In my opinion,
aliases:
- should be external to the descriptor language, as they bear no
significance for the actual script(s) that the descriptor can produce
- fail to distinguish which part of the KEY expression is part of the
"wallet description", and which part is not

By clearly separating the key information in the vector (typically, an xpub
with key origin information) from the key placeholder expression (which
typically will have the `/**` or `/<0,1>/*` derivation step), wallet
policies semantically represent keys in a way that should be convenient to
both software wallets and hardware signers.

Associating recognizable names to the xpubs (and registering them on the
device) is a good idea for future developments and can greatly improve the
UX, both during wallet setup, or in recognizing outputs for repeated
payments; it should be easy to build this feature on top of wallet policies.

== Examples ==

All the examples show:
- Miniscript policy: semantic spending rules, and optimization hints (can
be compiled to miniscript automatically)
- Miniscript: the actual miniscript descriptor, compiles 1-to-1 to Bitcoin
Script
- Wallet template: the "wallet descriptor template"
- Vector of keys: the list of key information (with key origin information)

Together, the wallet template and the vector of keys are the complet
"wallet policy".

=== Example 1: Either of two keys (equally likely) ===

Miniscript policy: or(pk(key_0),pk(key_1))
Miniscript:
 wsh(or_b([d34db33f/44'/0'/0']xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL/<0;1>/*),s:pk([12345678/44'/0'/0']xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB/<0;1>/*)))

Descriptor template:   wsh(or_b(pk(@0/**),s:pk(@1/**)))
Vector of keys: [

"[d34db33f/44'/0'/0']xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL",

"[12345678/44'/0'/0']xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB"
]

In all the following examples, I will replace the xpubs with aliases in the
miniscript for brevity, and omit the corresponding vector of keys in the
wallet policy.

Of course, in comparing the "information density" (especially for UX
purposes), it is important to take the full descriptor into account.
It is always to be assumed that the keys are xpubs, complete with key
origin information if internal (that is, controlled by the software or
hardware signer that the wallet policy is being with).

=== Example 2: Either of two keys, but one is more likely ===

Miniscript policy: or(99@pk(key_likely),pk(key_unlikely))
Miniscript:           wsh(or_d(pk(key_likely),pkh(key_unlikely)))

Descriptor template: wsh(or_d(pk(@0/**),pkh(@1/**)))
Vector of keys:         <omitted>

=== Example 3: A 3-of-3 that turns into a 2-of-3 after 90 days ===

Miniscript policy: thresh(3,pk(key_0),pk(key_1),pk(key_2),older(12960))
Miniscript:
 wsh(thresh(3,pk(key_0),s:pk(key_1),s:pk(key_2),sln:older(12960)))

Descriptor template:
wsh(thresh(3,pk(@0/**),s:pk(@1/**),s:pk(@2/**),sln:older(12960)))))
Vector of keys:         <omitted>

=== Example 4: The BOLT #3 received HTLC policy ===

Miniscript policy:
andor(pk(key_remote),or_i(and_v(v:pkh(key_local),hash160(395e368b267d64945f30e4b71de1054f364c9473)),older(1008)),pk(key_revocation))
Miniscript:
 wsh(andor(pk(key_remote),or_i(and_v(v:pkh(key_local),hash160(395e368b267d64945f30e4b71de1054f364c9473)),older(1008)),pk(key_revocation)))

Descriptor template:
wsh(andor(pk(@0/**),or_i(and_v(v:pkh(@1/**),hash160(395e368b267d64945f30e4b71de1054f364c9473)),older(1008)),pk(@2/**)))
Vector of keys:          <omitted>

=== Example 5: Taproot complex script (2-of-2 with cold backup and
timelocked inheritance) ===

The likely path is a 2-of-2 of a hot_key and a cosigner_key (2FA-like
service). At any time, a cold_key can be used for signing, and after about
a year, a separate timelocked_key becomes active (for example, to a notary
for inheritance purposes).
The timelock is reset every time UTXOs are spent.

Miniscript policy: or(99@thresh(2,pk(hot_key),pk(cosigner_key)),1@or(99@pk
(cold_key),1@and(pk(timelocked_key),older(52596))))
Miniscript:
 tr(cold_key,{and_v(v:pk(timelocked_key),older(52596)),multi_a(2,hot_key,cosigner_key)})

Descriptor template:
tr(@0/**,{and_v(v:pk(@1/**),older(52596)),multi_a(2,@2/**,@3/**)})
Vector of keys:          <omitted>

=== Example 6: Taproot complex script with MuSig2 ===

The same policy as above, but we assume that the hot wallet and the
cosigner are able to engage in the MuSig2 protocol.
This greatly exemplifies the practical advantage of MuSig2 with taproot in
terms of both transaction cost and privacy.

Miniscript policy: or(99@musig2(hot_key,cosigner_key),1@or(99@pk
(cold_key),1@and(pk(timelocked_key),older(52596))))
Miniscript:
 tr(musig2(hot_key,cosigner_key),{and_v(v:pk(timelocked_key),older(52596)),pk(cold_key)})

Descriptor template:
tr(musig2(@0,@1)/**,{and_v(v:pk(@2/**),older(52596)),pk(@3/**)})
Vector of keys:         <omitted>. Note: the order of keys differs from the
previous example.



Salvatore Ingala

[-- Attachment #2: Type: text/html, Size: 9011 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Wallet policies for descriptor wallets
  2022-05-09 11:36 ` darosior
  2022-05-10  9:37   ` Salvatore Ingala
@ 2022-09-29 23:56   ` Andrew Poelstra
  1 sibling, 0 replies; 9+ messages in thread
From: Andrew Poelstra @ 2022-09-29 23:56 UTC (permalink / raw)
  To: darosior, Bitcoin Protocol Discussion

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


I'm really happy to see this discussion. I don't have any comments on the spec
because I think I'd have to be more in-the-weeds trying to implement a hww to
understand how well it works for realistic use cases. But a strong concept-ACk
from me and thanks to Salvatore for exploring this!

On Mon, May 09, 2022 at 11:36:47AM +0000, darosior via bitcoin-dev wrote:
> 
> Unrelated question, since you mentioned `musig2` descriptors in this context. I thought Musig2 wasn't really
> feasible for hardware signing devices, especially stateless ones. Do you think/know whether it is actually
> possible for a HW to take part in a Musig2?
>

As Salvatore mentioned in his reply, there are a couple ways that hwws can deal
with musig2 -- specifically, having state (and I believe you can get away with
as little state as a single monotonic counter) or having a RNG which is reliable
enough that it at least won't repeat values.

Because these aren't blockers for all hwws, even if they are blockers for some,
I'd really like to see musig2 support in these protocols, or at least for musig2
to be considered in their design.
 

-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster


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

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Wallet policies for descriptor wallets
  2022-05-05 14:32 [bitcoin-dev] Wallet policies for descriptor wallets Salvatore Ingala
                   ` (2 preceding siblings ...)
  2022-05-17  8:44 ` Salvatore Ingala
@ 2022-11-21 11:27 ` Salvatore Ingala
  2023-01-23 19:53   ` darosior
  3 siblings, 1 reply; 9+ messages in thread
From: Salvatore Ingala @ 2022-11-21 11:27 UTC (permalink / raw)
  To: Bitcoin Protocol Discussion

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

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 <salvatore.ingala@gmail.com>
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
>
>

[-- Attachment #2: Type: text/html, Size: 21454 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Wallet policies for descriptor wallets
  2022-11-21 11:27 ` Salvatore Ingala
@ 2023-01-23 19:53   ` darosior
  2023-01-24  8:38     ` Salvatore Ingala
  0 siblings, 1 reply; 9+ messages in thread
From: darosior @ 2023-01-23 19:53 UTC (permalink / raw)
  To: Salvatore Ingala, Bitcoin Protocol Discussion

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

Hello Salvatore,

It's not something about the specifications of wallet policies, but regarding the guidelines for implementers on signing devices. Quoting BIP-wallet-policies:

> 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; that is crucial since the ability for the user to completely validate on-screen the kind of script used (and each of the involved keys) is a prerequisite for secure usage, as the machine that is interacting with the hardware signer (and running the software wallet) is considered untrusted.

> The device shows the wallet policy to the user using the secure screen.
> - Template with miniscript for "1 of 2 equally likely keys":
>   wsh(or_b(pk(@0/**),s:pk(@1/**)))

​

Actually you can save a few more characters, and gain some clarity, by showing the "semantic policy" instead of the actual Miniscript.

If the intent is for the user to verify the semantic of the Bitcoin Script they are importing, you can just drop all the type information.

For instance, for a Miniscript representing the Miniscript policy "a 3-of-3 that becomes a 2-of-3 after 90 days" instead of showing:

thresh(3,pk(Alice),s:pk(Bob),s:pk(Carol),sln:older(12960))

You could show:

thresh(3,pk(Alice),pk(Bob),pk(Carol),older(12960))

For this specific example you'd save 8 (confusing) characters to be verified on the signing device.

I wonder if signing devices could even go further and display a plain english verification to the user, like "This policy contains 4 spending paths. Be ready to verify the 4 spending paths. The first spending path is Alice, Bob and Carol signing together. The second spending path is Bob and Carol signing together after 90 days. The third spending path is Alice and Carol signing together after 90 days.

The third spending path is Alice and Bob signing together after 90 days

."

It seems feasible to be doable in a general manner from a Miniscript "semantic policy".

I guess it clashes with the user willing to check their backup against the policy registered on the device. You could always have the user-friendly policy check at first and have an option to show the raw descriptor for them to be able to cross-check it with their backup.

PS: the numerous usage of the word "policy" is getting complex lol, is it a Miniscript concrete policy, a Miniscript semantic policy, a BIP-wallet-policies policy? :)

Antoine Poinsot

------- Original Message -------
Le lundi 21 novembre 2022 à 12:27 PM, Salvatore Ingala via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> a écrit :

> 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 <salvatore.ingala@gmail.com> 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

[-- Attachment #2: Type: text/html, Size: 26117 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [bitcoin-dev] Wallet policies for descriptor wallets
  2023-01-23 19:53   ` darosior
@ 2023-01-24  8:38     ` Salvatore Ingala
  0 siblings, 0 replies; 9+ messages in thread
From: Salvatore Ingala @ 2023-01-24  8:38 UTC (permalink / raw)
  To: Bitcoin Protocol Discussion

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

Hi Antoine,

Thanks for your very interesting suggestions!

On Mon, 23 Jan 2023 at 20:53, darosior <darosior@protonmail.com> wrote:

> Actually you can save a few more characters, and gain some clarity, by showing the "semantic policy" instead of the actual Miniscript. If the intent is for the user to verify the semantic of the Bitcoin Script they are importing, you can just drop all the type information.
> For instance, for a Miniscript representing the Miniscript policy "a 3-of-3 that becomes a 2-of-3 after 90 days" instead of showing:
>
> thresh(3,pk(Alice),s:pk(Bob),s:pk(Carol),sln:older(12960))
> You could show:
>
> thresh(3,pk(Alice),pk(Bob),pk(Carol),older(12960))
> For this specific example you'd save 8 (confusing) characters to be verified on the signing device.
>
>
I thought about that, and I still consider it a possible future improvement
in UX. However, I wasn't comfortable deploying it in this way for the
following reason: if there is malware in your software wallet at policy
registration time, the malware could find a different miniscript with the
same semantic policy.
The result is now a mismatch between the wallet policy in the user's backup
and the one where funds are actually received. The user might see funds
mysteriously disappear, while the attacker would know the actual miniscript
policy, enabling ransom attacks.

The attack seems very unlikely today, and for many interesting semantic
policies, there are probably not many miniscript policies to sift through
in case of recovery.
However, I suspect it will become more realistic in a taproot world, where
the semantic policy of each tapleaf could have multiple options, resulting
in combinatorial explosion.
For example, if there are 2 options for the miniscript of each leaf, and n
leaves, you would have 2^n possible descriptors with the same semantic
policy.

One solution might be to explicitly enumerate (or at least upper-bound) the
number of possible descriptors that are lifted to the same policy, and use
the simplified UX if this number is not too large.
Having a set of standard recovery tools for those situations might make
this approach more viable in my opinion.

I wonder if signing devices could even go further and display a plain
english verification to the user, like "This policy contains 4
spending paths. Be ready to verify the 4 spending paths. The first
spending path is Alice, Bob and Carol signing together. The second
spending path is Bob and Carol signing together after 90 days. The
third spending path is Alice and Carol signing together after 90 days.
The third spending path is Alice and Bob signing together after 90
days."
> It seems feasible to be doable in a general manner from a Miniscript "semantic policy".
>
> A lower-hanging fruit might be to find ways of registering
xpubs/identities on the device, so that one could replace xpubs with
"Alice" and "Bob".
Once that's done, that might be one of the possible approaches to simplify
the UX flow.
I suspect the design space to be quite large and I have not yet put enough
thought into it.

I guess it clashes with the user willing to check their backup against
the policy registered on the device. You could always have the
user-friendly policy check at first and have an option to show the raw
descriptor for them to be able to cross-check it with their backup.
>
> I'm assuming the user will do the minimum amount of work they are forced
to do, therefore I only consider this safe iff we address the
miniscript-combinatorial-explosion issues above.

PS: the numerous usage of the word "policy" is getting complex lol, is
it a Miniscript concrete policy, a Miniscript semantic policy, a
BIP-wallet-policies policy? :)
>
> ...yeah, we should have a policy against that!

Salvatore Ingala

[-- Attachment #2: Type: text/html, Size: 5166 bytes --]

^ permalink raw reply	[flat|nested] 9+ messages in thread

end of thread, other threads:[~2023-01-24  8:38 UTC | newest]

Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-05-05 14:32 [bitcoin-dev] Wallet policies for descriptor wallets Salvatore Ingala
2022-05-08 17:41 ` Billy Tetrud
2022-05-09 11:36 ` darosior
2022-05-10  9:37   ` Salvatore Ingala
2022-09-29 23:56   ` Andrew Poelstra
2022-05-17  8:44 ` Salvatore Ingala
2022-11-21 11:27 ` Salvatore Ingala
2023-01-23 19:53   ` darosior
2023-01-24  8:38     ` Salvatore Ingala

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox