Date: Mon, 09 May 2022 11:36:47 +0000
To: Salvatore Ingala <salvatore.ingala@gmail.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: darosior <darosior@protonmail.com>
Reply-To: darosior <darosior@protonmail.com>
Message-ID: <osdF1jSCUyGyaLZ6YytSB7ub1MwdbaP6PMCYEJZXmMRaSs4vS7bs_SZTErxZh_K7oLYLAtAqqgl0Vcdl1ftAusM_1DHSDHtz1kSUzqnmwsk=@protonmail.com>
In-Reply-To: <CAMhCMoHfdsQMsVigFqPexTE_q-Cyg7pfRvORUoy2sZtvyzd1cg@mail.gmail.com>
References: <CAMhCMoHfdsQMsVigFqPexTE_q-Cyg7pfRvORUoy2sZtvyzd1cg@mail.gmail.com>
Feedback-ID: 7060259:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] Wallet policies for descriptor wallets
Precedence: list

Thanks for taking the time to write up about the implementation of output d=
escriptors on signing devices, and
for proposing a method to overcome encountered difficulties for the followi=
ng implementers.

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

To sum up, starting from the currently spec'd output descriptors [0] you ne=
ed:
1. The `<NUM;NUM>` optimization for the common usecase of using 2 descripto=
rs 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 w=
e agree using the derivation path
for change detection is a sane thing to do, most signing devices need to su=
pport 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 verific=
ation.

I'm not so sure about the second point. Is another deviation from the stand=
ard worth it just for saving 3
characters?
Disgressing, if we are to have a carve-out in the descriptor language for t=
he 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 con=
text 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 lo=
ng keys.
However, why does it need to be a change to the descriptor language? It loo=
ks 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 alia=
ses for smoother verification. For
stateless devices, the registration of keys could use the same flow you des=
cribed for descriptors.
In the end it's just replacing the vector and indices with a mapping and la=
bel, which make it a *much* better
UX (checking aliases vs looking up indices in a vector). For instance:
    Key registration:
        Alice: xpub6FLhTbeNidZkyC729yW6K6a5zuDxKUL8Q6oZm4XG2ov9PdxAyyDNEUm3=
jet8ENnvYsy6nCgsofN6FeVxakLDTdWGoxtmoYcu2exhqh9HjtV
        Bob: xpub6CoUua86qHYdDmnQL7imGN3zUMpVjRT4uDtRxYvfFj2v8JRvsaaGtf9ggv=
9NiL8sx3rFh6po92WBChwb37gDGuuU2Qo7zi3ZKC9cLjAsdQw
        Notary: xpub6DjUwtKmK7uqsd5p9w3eoJ4cjuML51nW85BTWuBaHEoxfmDGD3uPf6Z=
ghsVeyuZUSuYEL4ajkVrfXzmotHHPtf6oBNYUQDSSBD4zUEiDoap

    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 languag=
e for the common receive/change
usecase, i don't think you need another "wallet policy language" than the e=
xisting output descriptors language
with key aliasing/registration?


Unrelated question, since you mentioned `musig2` descriptors in this contex=
t. I thought Musig2 wasn't really
feasible for hardware signing devices, especially stateless ones. Do you th=
ink/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 =C3=A0 4:32 PM, Salvatore Ingala via bitcoin-dev <bitco=
in-dev@lists.linuxfoundation.org> a =C3=A9crit :


> In the implementation work to implement descriptors and miniscript suppor=
t 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 developm=
ent). 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 la=
yer 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 co=
mments, and will propose a BIP if this is deemed valuable.
>
> I called the language "wallet policies" (suggestions for a better name ar=
e welcome). I believe an approach based on wallet policies can benefit all =
hardware wallets (stateless or not) that want to securely support complex s=
cripts; moreover, wallet policies are close enough to descriptors that thei=
r integration should be extremely easy for any software wallet that is curr=
ently using descriptors.
>
> [a]: https://blog.ledger.com/bitcoin-2 - early demo[b]: https://blog.ledg=
er.com/miniscript-is-coming - miniscript example
>
> Salvatore Ingala
>
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D
>
> This document starts with a discussion on the motivation for wallet polic=
ies, followed by their formal definition, and some recommendations for impl=
ementations.
> =3D=3D Rationale =3D=3D
> 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 b=
e possible to sign transactions with bitcoin-core's descriptor-based wallet=
s).
>
> Unfortunately, descriptors are not a perfect match for the typical usage =
of hardware wallets. Most hardware wallets have the following limitations c=
ompared 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/bi=
ps/blob/master/bip-0032.mediawiki));
> - they might not have permanent storage (*stateless* hardware wallet desi=
gn).
>
> Moreover, other limitations like the limited size of the screen might aff=
ect what design choices are available in practice. Therefore, minimizing th=
e size of the information shown on-screen is important for a good user expe=
rience.
>
> A more native, compact representation of the wallet receive/change would =
also benefit the UX of software wallets using descriptors to represent soft=
ware wallets using descriptors/miniscript for multisignature or other compl=
ex locking conditions.
>
> =3D=3D=3D Security and UX concerns of scripts in hardware wallets =3D=3D=
=3D
> For a hardware wallet, allowing the usage of complex scripts presents cha=
llenges in terms of both security and user experience.
>
> =3D=3D=3D=3D Security issues =3D=3D=3D=3D
> 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 c=
an be performed without the user's consent**.
> This must hold even in scenarios where the attacker has full control of t=
he machine that is connected to the hardware wallet, and can execute arbitr=
ary 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 burnin=
g user's funds.
>
> =3D=3D=3D=3D UX issues =3D=3D=3D=3D
> With miniscript (and taproot trees) allowing substantially more complex s=
pending 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. The=
refore, there are two fundamental design goals to strive for:
> - Minimize the amount of information that is shown on screen - so that th=
e 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 a=
mong 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.
>
> =3D=3D=3D Policy registration as a solution =3D=3D=3D
> 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 wal=
let. The "wallet policy" must contain enough information to generate all th=
e relevant addresses/scripts, and for the hardware wallet to identify the k=
eys that it controls and that are needed to spend the funds sent to those a=
ddresses.
>
> 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 ha=
rdware 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 secu=
re screen.
> 3) After inspecting the policy and comparing it with a trusted source (fo=
r 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 op=
erations securely:
> - generating receive and change addresses;
> - showing addresses on the secure screen;
> - sign transactions spending from a wallet, while correctly identifying c=
hange addresses and computing the transaction fees.
>
> Before any of the actions mentioned above, the hardware wallet will retri=
eve the policy from its permanent storage if stateful; if stateless it will=
 validate the _proof of registration_ before using the wallet policy provid=
ed by the client.
> Once the previously registered policy is correctly identified and approve=
d by the user (for example by its name), and *as long as the policy registr=
ation was executed securely*, hardware wallets can provide a user experienc=
e similar to the usual one for single-signature transactions.
>
> =3D=3D=3D Avoiding blowup in descriptor size =3D=3D=3D
> While reusing a pubkey in different branches of a miniscript is explicitl=
y forbidden by miniscript (as it has certain negative security implications=
), it is still reasonable to reuse the same *xpub* in multiple places, albe=
it with different final steps of derivation (so that the actual pubkeys tha=
t 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 a=
re generated, plus a leaf with a fallback *3*-of-*5* multisignature using p=
lain 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 byte=
s long, the length of the full descriptor can get extremely long (the probl=
em gets *exponentially* worse with larger multisignature schemes).
>
> Replacing the common part of the key with a short key placeholder and mov=
ing the key expression separately helps to keep the size of the wallet poli=
cy small, which is crucial to allow human inspection in the registration fl=
ow.
>
> =3D=3D=3D Restrictions on the supported descriptors =3D=3D=3D=3D
>
> The policy language proposed in this document purposely targets only a st=
ricter subset of the output descriptors language, and it attempts to genera=
lize in the most natural way the approach that is already used for single-s=
ignature *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 B=
IP-87 [8]).
> Unlike the BIPs mentioned above, it is not tied to any specific script te=
mplate, as it applies to arbitrary scripts that can be represented with des=
criptors and miniscript.
>
> Supporting only a reduced feature set when compared to output descriptors=
 helps in implementations (especially on hardware wallets), while attemptin=
g to capture all the common use cases. More features can be added in the fu=
ture 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 cur=
rent implementations into the corresponding wallet policy.
>
>
> =3D=3D Wallet policies =3D=3D
> This section formally defines wallet policies, and how they relate to out=
put script descriptors.
> =3D=3D=3D Formal definition =3D=3D=3D
> A wallet policy is composed by a wallet descriptor template, together wit=
h a vector of key information items.
>
> =3D=3D=3D=3D Wallet descriptor template =3D=3D=3D=3D
>
> 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 s=
orted lexicographically in the resulting script.
> - `tr(KP)` or `tr(KP,TREE)` (top level only): P2TR output with the specif=
ied 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` expressio=
n, 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 (excep=
t 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).
>
> =3D=3D=3D=3D Key informations vector =3D=3D=3D=3D
>
> 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 whi=
ch this key is derived from (see [BIP32](https://github.com/bitcoin/bips/bl=
ob/master/bip-0032.mediawiki) for details)
> - Followed by zero or more `/NUM'` path elements to indicate hardened der=
ivation 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 (exa=
ctly 66 hex characters starting with `02` or `03`.
> - inside `tr`, x-only pubkeys are also permitted (exactly 64 hex characte=
rs).
> - 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 ste=
ps while the corresponding `(i+1)`-th element of the keys vector is not an =
xpub.
>
> =3D=3D=3D=3D Additional rules =3D=3D=3D=3D
> The wallet policy is invalid if any placeholder expression with additiona=
l derivation steps is used when the corresponding key information is not an=
 xpub.
>
> The key information vector *should* be ordered so that placeholder `@i` n=
ever 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.
>
> =3D=3D=3D Descriptor derivation =3D=3D=3D
> From a wallet descriptor template (and the associated vector of key infor=
mations), one can therefore obtain the 1-dimensional descriptor for receive=
 and change addresses by:
>
> - replacing each key placeholder with the corresponding key origin inform=
ation;
> - 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']xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhg=
bmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL"]` produces the fol=
lowing two descriptors:
>
> - Receive descriptor: `pkh([d34db33f/44'/0'/0']xpub6ERApfZwUNrhLCkDtcHTcx=
d75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJv=
LJuZZvRcEL/0/*)`
>
> - Change descriptor: `pkh([d34db33f/44'/0'/0']xpub6ERApfZwUNrhLCkDtcHTcxd=
75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvL=
JuZZvRcEL/1/*)`
>
> =3D=3D=3D Implementation guidelines =3D=3D=3D
> Implementations must not necessarily implement all of the possible wallet=
 policies defined by this standard, but it is recommended to clearly docume=
nt any limitation.
>
> Implementations can add additional metadata that is stored together with =
the wallet policy for the purpose of wallet policy registration and later u=
sage. Metadata can be vendor-specific and is out of the scope of this docum=
ent.
>
> Any implementation in a general-purpose software wallet allowing arbitrar=
y scripts (or any scripts that involve external cosigners) should put great=
 care into a process for backing up a wallet policy. In fact, unlike typica=
l single-signature scenarios, the seed alone is no longer enough to discove=
r 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 impo=
rtant, but out of scope for this document.
>
> =3D=3D Examples =3D=3D
>
> 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.
> =3D=3D References =3D=3D
>
> * [1] - Output Script Descriptors: https://github.com/bitcoin/bitcoin/blo=
b/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.medi=
awiki* [4] - BIP-49: https://github.com/bitcoin/bips/blob/master/bip-0049.m=
ediawiki* [5] - BIP-84: https://github.com/bitcoin/bips/blob/master/bip-008=
4.mediawiki* [6] - BIP-86: https://github.com/bitcoin/bips/blob/master/bip-=
0086.mediawiki* [7] - BIP-48: https://github.com/bitcoin/bips/blob/master/b=
ip-0048.mediawiki* [8] - BIP-87: https://github.com/bitcoin/bips/blob/maste=
r/bip-0087.mediawiki