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, 41 insertions, 3 deletions

diff --git a/src/pubkey.cpp b/src/pubkey.cpp
index 334acb454e..51cc826b00 100644
--- a/src/pubkey.cpp
+++ b/src/pubkey.cpp
@@ -180,6 +180,12 @@ XOnlyPubKey::XOnlyPubKey(Span<const unsigned char> bytes)
     std::copy(bytes.begin(), bytes.end(), m_keydata.begin());
 }
 
+bool XOnlyPubKey::IsFullyValid() const
+{
+    secp256k1_xonly_pubkey pubkey;
+    return secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &pubkey, m_keydata.data());
+}
+
 bool XOnlyPubKey::VerifySchnorr(const uint256& msg, Span<const unsigned char> sigbytes) const
 {
     assert(sigbytes.size() == 64);
@@ -188,13 +194,45 @@ bool XOnlyPubKey::VerifySchnorr(const uint256& msg, Span<const unsigned char> si
     return secp256k1_schnorrsig_verify(secp256k1_context_verify, sigbytes.data(), msg.begin(), &pubkey);
 }
 
-bool XOnlyPubKey::CheckPayToContract(const XOnlyPubKey& base, const uint256& hash, bool parity) const
+static const CHashWriter HASHER_TAPTWEAK = TaggedHash("TapTweak");
+
+uint256 XOnlyPubKey::ComputeTapTweakHash(const uint256* merkle_root) const
+{
+    if (merkle_root == nullptr) {
+        // We have no scripts. The actual tweak does not matter, but follow BIP341 here to
+        // allow for reproducible tweaking.
+        return (CHashWriter(HASHER_TAPTWEAK) << m_keydata).GetSHA256();
+    } else {
+        return (CHashWriter(HASHER_TAPTWEAK) << m_keydata << *merkle_root).GetSHA256();
+    }
+}
+
+bool XOnlyPubKey::CheckTapTweak(const XOnlyPubKey& internal, const uint256& merkle_root, bool parity) const
+{
+    secp256k1_xonly_pubkey internal_key;
+    if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &internal_key, internal.data())) return false;
+    uint256 tweak = internal.ComputeTapTweakHash(&merkle_root);
+    return secp256k1_xonly_pubkey_tweak_add_check(secp256k1_context_verify, m_keydata.begin(), parity, &internal_key, tweak.begin());
+}
+
+std::optional<std::pair<XOnlyPubKey, bool>> XOnlyPubKey::CreateTapTweak(const uint256* merkle_root) const
 {
     secp256k1_xonly_pubkey base_point;
-    if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &base_point, base.data())) return false;
-    return secp256k1_xonly_pubkey_tweak_add_check(secp256k1_context_verify, m_keydata.begin(), parity, &base_point, hash.begin());
+    if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &base_point, data())) return std::nullopt;
+    secp256k1_pubkey out;
+    uint256 tweak = ComputeTapTweakHash(merkle_root);
+    if (!secp256k1_xonly_pubkey_tweak_add(secp256k1_context_verify, &out, &base_point, tweak.data())) return std::nullopt;
+    int parity = -1;
+    std::pair<XOnlyPubKey, bool> ret;
+    secp256k1_xonly_pubkey out_xonly;
+    if (!secp256k1_xonly_pubkey_from_pubkey(secp256k1_context_verify, &out_xonly, &parity, &out)) return std::nullopt;
+    secp256k1_xonly_pubkey_serialize(secp256k1_context_verify, ret.first.begin(), &out_xonly);
+    assert(parity == 0 || parity == 1);
+    ret.second = parity;
+    return ret;
 }
 
+
 bool CPubKey::Verify(const uint256 &hash, const std::vector<unsigned char>& vchSig) const {
     if (!IsValid())
         return false;