Merge bitcoin/bitcoin#22051: Basic Taproot derivation support for descriptors

2667366aaa69447a9de4d819669d254a5ebd4d4b tests: check derivation of P2TR (Pieter Wuille)
7cedafc5412857404e9a6c3450b100cb8ee4081a Add tr() descriptor (derivation only, no signing) (Pieter Wuille)
90fcac365e1616779b40a69736428435df75fdf2 Add TaprootBuilder class (Pieter Wuille)
5f6cc8daa83700d1c949d968a5cf0d935be337b7 Add XOnlyPubKey::CreateTapTweak (Pieter Wuille)
2fbfb1becb3c0c109cd7c30b245b51da22039932 Make consensus checking of tweaks in pubkey.* Taproot-specific (Pieter Wuille)
a4bf84039c00b196b87f969acf6369d72c56ab46 Separate WitnessV1Taproot variant in CTxDestination (Pieter Wuille)
41839bdb89b3777ece2318877b9c7921ecca2472 Avoid dependence on CTxDestination index order (Pieter Wuille)
31df02a07091dbd5e0b315c8e5695e808f3a5505 Change Solver() output for WITNESS_V1_TAPROOT (Pieter Wuille)
4b1cc08f9f94a1e6e1ecba6b97f99b73fb513872 Make XOnlyPubKey act like byte container (Pieter Wuille)

Pull request description:

  This is a subset of #21365, to aide review.

  This adds support `tr(KEY)` or `tr(KEY,SCRIPT)` or `tr(KEY,{{S1,{{S2,S3},...}},...})` descriptors, describing Taproot outputs with specified internal key, and optionally any number of scripts, in nested groups of 2 inside `{`/`}` if there are more than one. While it permits importing `tr(KEY)`, anything beyond that is just laying foundations for more features later.

  Missing:
  * Signing support (see #21365)
  * Support for more interesting scripts inside the tree (only `pk(KEY)` is supported for now). In particular, a multisig policy based on the new `OP_CHECKSIGADD` opcode would be very useful.
  * Inferring `tr()` descriptors from outputs (given sufficient information).
  * `getaddressinfo` support.
  * MuSig support. Standardizing that is still an ongoing effort, and is generally kind of useless without corresponding PSBT support.
  * Convenient ways of constructing descriptors without spendable internal key (especially ones that arent't trivially recognizable as such).

ACKs for top commit:
  Sjors:
    utACK 2667366 (based on https://github.com/bitcoin/bitcoin/pull/21365#issuecomment-846945215 review, plus the new functional test)
  achow101:
    Code Review ACK 2667366aaa69447a9de4d819669d254a5ebd4d4b
  lsilva01:
    Tested ACK https://github.com/bitcoin/bitcoin/pull/22051/commits/2667366aaa69447a9de4d819669d254a5ebd4d4b
  meshcollider:
    utACK 2667366aaa69447a9de4d819669d254a5ebd4d4b

Tree-SHA512: 61046fef22c561228338cb178422f0b782ef6587ec8208d3ce2bd07afcff29a664b54b35c6b01226eb70b6540b43f6dd245043d09aa6cb6db1381b6042667e75

1 files changed, 13 insertions, 5 deletions

diff --git a/doc/descriptors.md b/doc/descriptors.md
index c4fc2a66bf..e27ff87546 100644
--- a/doc/descriptors.md
+++ b/doc/descriptors.md
@@ -30,6 +30,7 @@ Output descriptors currently support:
 - Pay-to-witness-pubkey-hash scripts (P2WPKH), through the `wpkh` function.
 - Pay-to-script-hash scripts (P2SH), through the `sh` function.
 - Pay-to-witness-script-hash scripts (P2WSH), through the `wsh` function.
+- Pay-to-taproot outputs (P2TR), through the `tr` function.
 - Multisig scripts, through the `multi` function.
 - Multisig scripts where the public keys are sorted lexicographically, through the `sortedmulti` function.
 - Any type of supported address through the `addr` function.
@@ -54,6 +55,7 @@ Output descriptors currently support:
 - `pkh([d34db33f/44'/0'/0']xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL/1/*)` describes a set of P2PKH outputs, but additionally specifies that the specified xpub is a child of a master with fingerprint `d34db33f`, and derived using path `44'/0'/0'`.
 - `wsh(multi(1,xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB/1/0/*,xpub69H7F5d8KSRgmmdJg2KhpAK8SR3DjMwAdkxj3ZuxV27CprR9LgpeyGmXUbC6wb7ERfvrnKZjXoUmmDznezpbZb7ap6r1D3tgFxHmwMkQTPH/0/0/*))` describes a set of *1-of-2* P2WSH multisig outputs where the first multisig key is the *1/0/`i`* child of the first specified xpub and the second multisig key is the *0/0/`i`* child of the second specified xpub, and `i` is any number in a configurable range (`0-1000` by default).
 - `wsh(sortedmulti(1,xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB/1/0/*,xpub69H7F5d8KSRgmmdJg2KhpAK8SR3DjMwAdkxj3ZuxV27CprR9LgpeyGmXUbC6wb7ERfvrnKZjXoUmmDznezpbZb7ap6r1D3tgFxHmwMkQTPH/0/0/*))` describes a set of *1-of-2* P2WSH multisig outputs where one multisig key is the *1/0/`i`* child of the first specified xpub and the other multisig key is the *0/0/`i`* child of the second specified xpub, and `i` is any number in a configurable range (`0-1000` by default). The order of public keys in the resulting witnessScripts is determined by the lexicographic order of the public keys at that index.
+- `tr(c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5,{pk(fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556),pk(e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13)})` describes a P2TR output with the `c6...` x-only pubkey as internal key, and two script paths.
 
 ## Reference
 
@@ -61,13 +63,14 @@ Descriptors consist of several types of expressions. The top level expression is
 
 `SCRIPT` expressions:
 - `sh(SCRIPT)` (top level only): P2SH embed the argument.
-- `wsh(SCRIPT)` (not inside another 'wsh'): P2WSH embed the argument.
+- `wsh(SCRIPT)` (top level or inside `sh` only): P2WSH embed the argument.
 - `pk(KEY)` (anywhere): P2PK output for the given public key.
-- `pkh(KEY)` (anywhere): P2PKH output for the given public key (use `addr` if you only know the pubkey hash).
-- `wpkh(KEY)` (not inside `wsh`): P2WPKH output for the given compressed pubkey.
+- `pkh(KEY)` (not inside `tr`): P2PKH output for the given public key (use `addr` if you only know the pubkey hash).
+- `wpkh(KEY)` (top level or inside `sh` only): P2WPKH output for the given compressed pubkey.
 - `combo(KEY)` (top level only): an alias for the collection of `pk(KEY)` and `pkh(KEY)`. If the key is compressed, it also includes `wpkh(KEY)` and `sh(wpkh(KEY))`.
-- `multi(k,KEY_1,KEY_2,...,KEY_n)` (anywhere): k-of-n multisig script.
-- `sortedmulti(k,KEY_1,KEY_2,...,KEY_n)` (anywhere): k-of-n multisig script with keys sorted lexicographically in the resulting script.
+- `multi(k,KEY_1,KEY_2,...,KEY_n)` (not inside `tr`): k-of-n multisig script.
+- `sortedmulti(k,KEY_1,KEY_2,...,KEY_n)` (not inside `tr`): k-of-n multisig script with keys sorted lexicographically in the resulting script.
+- `tr(KEY)` or `tr(KEY,TREE)` (top level only): P2TR output with the specified key as internal key, and optionally a tree of script paths.
 - `addr(ADDR)` (top level only): the script which ADDR expands to.
 - `raw(HEX)` (top level only): the script whose hex encoding is HEX.
 
@@ -80,12 +83,17 @@ Descriptors consist of several types of expressions. The top level expression is
 - Followed by the actual key, which is either:
   - Hex encoded public keys (either 66 characters starting with `02` or `03` for a compressed pubkey, or 130 characters starting with `04` for an uncompressed pubkey).
     - Inside `wpkh` and `wsh`, only compressed public keys are permitted.
+    - Inside `tr`, x-only pubkeys are also permitted (64 hex characters).
   - [WIF](https://en.bitcoin.it/wiki/Wallet_import_format) encoded private keys may be specified instead of the corresponding public key, with the same meaning.
   - `xpub` encoded extended public key or `xprv` encoded extended private key (as defined in [BIP 32](https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki)).
     - Followed by zero or more `/NUM` unhardened and `/NUM'` hardened BIP32 derivation steps.
     - Optionally followed by a single `/*` or `/*'` final step to denote all (direct) unhardened or hardened children.
     - The usage of hardened derivation steps requires providing the private key.
 
+`TREE` expressions:
+- any `SCRIPT` expression
+- An open brace `{`, a `TREE` expression, a comma `,`, a `TREE` expression, and a closing brace `}`
+
 (Anywhere a `'` suffix is permitted to denote hardened derivation, the suffix `h` can be used instead.)
 
 `ADDR` expressions are any type of supported address: