From 4b1cc08f9f94a1e6e1ecba6b97f99b73fb513872 Mon Sep 17 00:00:00 2001
From: Pieter Wuille <pieter@wuille.net>
Date: Sun, 23 May 2021 17:38:18 -0700
Subject: Make XOnlyPubKey act like byte container

---
 src/pubkey.h  | 15 ++++++++++++++-
 src/uint256.h |  2 +-
 2 files changed, 15 insertions(+), 2 deletions(-)

(limited to 'src')

diff --git a/src/pubkey.h b/src/pubkey.h
index 1af1187006..7d09faa9c1 100644
--- a/src/pubkey.h
+++ b/src/pubkey.h
@@ -222,6 +222,12 @@ private:
     uint256 m_keydata;
 
 public:
+    /** Construct an empty x-only pubkey. */
+    XOnlyPubKey() = default;
+
+    XOnlyPubKey(const XOnlyPubKey&) = default;
+    XOnlyPubKey& operator=(const XOnlyPubKey&) = default;
+
     /** Construct an x-only pubkey from exactly 32 bytes. */
     explicit XOnlyPubKey(Span<const unsigned char> bytes);
 
@@ -234,7 +240,14 @@ public:
 
     const unsigned char& operator[](int pos) const { return *(m_keydata.begin() + pos); }
     const unsigned char* data() const { return m_keydata.begin(); }
-    size_t size() const { return m_keydata.size(); }
+    static constexpr size_t size() { return decltype(m_keydata)::size(); }
+    const unsigned char* begin() const { return m_keydata.begin(); }
+    const unsigned char* end() const { return m_keydata.end(); }
+    unsigned char* begin() { return m_keydata.begin(); }
+    unsigned char* end() { return m_keydata.end(); }
+    bool operator==(const XOnlyPubKey& other) const { return m_keydata == other.m_keydata; }
+    bool operator!=(const XOnlyPubKey& other) const { return m_keydata != other.m_keydata; }
+    bool operator<(const XOnlyPubKey& other) const { return m_keydata < other.m_keydata; }
 };
 
 struct CExtPubKey {
diff --git a/src/uint256.h b/src/uint256.h
index fadf2320af..d4917d0eac 100644
--- a/src/uint256.h
+++ b/src/uint256.h
@@ -75,7 +75,7 @@ public:
         return &m_data[WIDTH];
     }
 
-    unsigned int size() const
+    static constexpr unsigned int size()
     {
         return sizeof(m_data);
     }
-- 
cgit v1.2.3


From 31df02a07091dbd5e0b315c8e5695e808f3a5505 Mon Sep 17 00:00:00 2001
From: Pieter Wuille <pieter@wuille.net>
Date: Sun, 23 May 2021 18:00:18 -0700
Subject: Change Solver() output for WITNESS_V1_TAPROOT

This is just a small simplification to prepare for the follow-up instruction
of a CTxDestination variant for taproot outputs.

In the old code, WITNESS_V1_TAPROOT and WITNESS_UNKNOWN both produced
{version, program} as Solver() output. Change this so that WITNESS_V1_TAPROOT
produces just {program}, like WITNESS_V0_* do.
---
 src/script/standard.cpp            | 16 ++++++++++++----
 src/test/script_standard_tests.cpp |  5 ++---
 2 files changed, 14 insertions(+), 7 deletions(-)

(limited to 'src')

diff --git a/src/script/standard.cpp b/src/script/standard.cpp
index 364fac3c84..540aa0f2d9 100644
--- a/src/script/standard.cpp
+++ b/src/script/standard.cpp
@@ -155,15 +155,14 @@ TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned c
     std::vector<unsigned char> witnessprogram;
     if (scriptPubKey.IsWitnessProgram(witnessversion, witnessprogram)) {
         if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_KEYHASH_SIZE) {
-            vSolutionsRet.push_back(witnessprogram);
+            vSolutionsRet.push_back(std::move(witnessprogram));
             return TxoutType::WITNESS_V0_KEYHASH;
         }
         if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_SCRIPTHASH_SIZE) {
-            vSolutionsRet.push_back(witnessprogram);
+            vSolutionsRet.push_back(std::move(witnessprogram));
             return TxoutType::WITNESS_V0_SCRIPTHASH;
         }
         if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE) {
-            vSolutionsRet.push_back(std::vector<unsigned char>{(unsigned char)witnessversion});
             vSolutionsRet.push_back(std::move(witnessprogram));
             return TxoutType::WITNESS_V1_TAPROOT;
         }
@@ -242,8 +241,17 @@ bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
         addressRet = hash;
         return true;
     }
-    case TxoutType::WITNESS_UNKNOWN:
     case TxoutType::WITNESS_V1_TAPROOT: {
+        /* For now, no WitnessV1Taproot variant in CTxDestination exists, so map
+         * this to WitnessUnknown. */
+        WitnessUnknown unk;
+        unk.version = 1;
+        std::copy(vSolutions[0].begin(), vSolutions[0].end(), unk.program);
+        unk.length = vSolutions[0].size();
+        addressRet = unk;
+        return true;
+    }
+    case TxoutType::WITNESS_UNKNOWN: {
         WitnessUnknown unk;
         unk.version = vSolutions[0][0];
         std::copy(vSolutions[1].begin(), vSolutions[1].end(), unk.program);
diff --git a/src/test/script_standard_tests.cpp b/src/test/script_standard_tests.cpp
index 44fbfa5970..950f3b970a 100644
--- a/src/test/script_standard_tests.cpp
+++ b/src/test/script_standard_tests.cpp
@@ -111,9 +111,8 @@ BOOST_AUTO_TEST_CASE(script_standard_Solver_success)
     s.clear();
     s << OP_1 << ToByteVector(uint256::ZERO);
     BOOST_CHECK_EQUAL(Solver(s, solutions), TxoutType::WITNESS_V1_TAPROOT);
-    BOOST_CHECK_EQUAL(solutions.size(), 2U);
-    BOOST_CHECK(solutions[0] == std::vector<unsigned char>{1});
-    BOOST_CHECK(solutions[1] == ToByteVector(uint256::ZERO));
+    BOOST_CHECK_EQUAL(solutions.size(), 1U);
+    BOOST_CHECK(solutions[0] == ToByteVector(uint256::ZERO));
 
     // TxoutType::WITNESS_UNKNOWN
     s.clear();
-- 
cgit v1.2.3


From 41839bdb89b3777ece2318877b9c7921ecca2472 Mon Sep 17 00:00:00 2001
From: Pieter Wuille <pieter@wuille.net>
Date: Sun, 23 May 2021 18:23:58 -0700
Subject: Avoid dependence on CTxDestination index order

---
 src/script/descriptor.cpp | 33 +++++++++++++++------------------
 1 file changed, 15 insertions(+), 18 deletions(-)

(limited to 'src')

diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
index b54ba204f0..19fad1009e 100644
--- a/src/script/descriptor.cpp
+++ b/src/script/descriptor.cpp
@@ -638,6 +638,19 @@ public:
     std::optional<OutputType> GetOutputType() const override { return std::nullopt; }
 };
 
+static std::optional<OutputType> OutputTypeFromDestination(const CTxDestination& dest) {
+    if (std::holds_alternative<PKHash>(dest) ||
+        std::holds_alternative<ScriptHash>(dest)) {
+        return OutputType::LEGACY;
+    }
+    if (std::holds_alternative<WitnessV0KeyHash>(dest) ||
+        std::holds_alternative<WitnessV0ScriptHash>(dest) ||
+        std::holds_alternative<WitnessUnknown>(dest)) {
+        return OutputType::BECH32;
+    }
+    return std::nullopt;
+}
+
 /** A parsed addr(A) descriptor. */
 class AddressDescriptor final : public DescriptorImpl
 {
@@ -651,15 +664,7 @@ public:
 
     std::optional<OutputType> GetOutputType() const override
     {
-        switch (m_destination.index()) {
-            case 1 /* PKHash */:
-            case 2 /* ScriptHash */: return OutputType::LEGACY;
-            case 3 /* WitnessV0ScriptHash */:
-            case 4 /* WitnessV0KeyHash */:
-            case 5 /* WitnessUnknown */: return OutputType::BECH32;
-            case 0 /* CNoDestination */:
-            default: return std::nullopt;
-        }
+        return OutputTypeFromDestination(m_destination);
     }
     bool IsSingleType() const final { return true; }
 };
@@ -679,15 +684,7 @@ public:
     {
         CTxDestination dest;
         ExtractDestination(m_script, dest);
-        switch (dest.index()) {
-            case 1 /* PKHash */:
-            case 2 /* ScriptHash */: return OutputType::LEGACY;
-            case 3 /* WitnessV0ScriptHash */:
-            case 4 /* WitnessV0KeyHash */:
-            case 5 /* WitnessUnknown */: return OutputType::BECH32;
-            case 0 /* CNoDestination */:
-            default: return std::nullopt;
-        }
+        return OutputTypeFromDestination(dest);
     }
     bool IsSingleType() const final { return true; }
 };
-- 
cgit v1.2.3


From a4bf84039c00b196b87f969acf6369d72c56ab46 Mon Sep 17 00:00:00 2001
From: Pieter Wuille <pieter@wuille.net>
Date: Sun, 23 May 2021 17:38:40 -0700
Subject: Separate WitnessV1Taproot variant in CTxDestination

---
 src/key_io.cpp            | 15 +++++++++++++++
 src/rpc/util.cpp          | 10 ++++++++++
 src/script/descriptor.cpp |  1 +
 src/script/standard.cpp   | 15 ++++++++-------
 src/script/standard.h     | 13 ++++++++++---
 src/wallet/rpcwallet.cpp  |  1 +
 6 files changed, 45 insertions(+), 10 deletions(-)

(limited to 'src')

diff --git a/src/key_io.cpp b/src/key_io.cpp
index dbcbfa1f29..615f4c9312 100644
--- a/src/key_io.cpp
+++ b/src/key_io.cpp
@@ -54,6 +54,14 @@ public:
         return bech32::Encode(bech32::Encoding::BECH32, m_params.Bech32HRP(), data);
     }
 
+    std::string operator()(const WitnessV1Taproot& tap) const
+    {
+        std::vector<unsigned char> data = {1};
+        data.reserve(53);
+        ConvertBits<8, 5, true>([&](unsigned char c) { data.push_back(c); }, tap.begin(), tap.end());
+        return bech32::Encode(bech32::Encoding::BECH32M, m_params.Bech32HRP(), data);
+    }
+
     std::string operator()(const WitnessUnknown& id) const
     {
         if (id.version < 1 || id.version > 16 || id.length < 2 || id.length > 40) {
@@ -135,6 +143,13 @@ CTxDestination DecodeDestination(const std::string& str, const CChainParams& par
                 return CNoDestination();
             }
 
+            if (version == 1 && data.size() == WITNESS_V1_TAPROOT_SIZE) {
+                static_assert(WITNESS_V1_TAPROOT_SIZE == WitnessV1Taproot::size());
+                WitnessV1Taproot tap;
+                std::copy(data.begin(), data.end(), tap.begin());
+                return tap;
+            }
+
             if (version > 16) {
                 error_str = "Invalid Bech32 address witness version";
                 return CNoDestination();
diff --git a/src/rpc/util.cpp b/src/rpc/util.cpp
index 7cf25e0c82..2059628b54 100644
--- a/src/rpc/util.cpp
+++ b/src/rpc/util.cpp
@@ -301,6 +301,16 @@ public:
         return obj;
     }
 
+    UniValue operator()(const WitnessV1Taproot& tap) const
+    {
+        UniValue obj(UniValue::VOBJ);
+        obj.pushKV("isscript", true);
+        obj.pushKV("iswitness", true);
+        obj.pushKV("witness_version", 1);
+        obj.pushKV("witness_program", HexStr(tap));
+        return obj;
+    }
+
     UniValue operator()(const WitnessUnknown& id) const
     {
         UniValue obj(UniValue::VOBJ);
diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
index 19fad1009e..d4b43932b9 100644
--- a/src/script/descriptor.cpp
+++ b/src/script/descriptor.cpp
@@ -645,6 +645,7 @@ static std::optional<OutputType> OutputTypeFromDestination(const CTxDestination&
     }
     if (std::holds_alternative<WitnessV0KeyHash>(dest) ||
         std::holds_alternative<WitnessV0ScriptHash>(dest) ||
+        std::holds_alternative<WitnessV1Taproot>(dest) ||
         std::holds_alternative<WitnessUnknown>(dest)) {
         return OutputType::BECH32;
     }
diff --git a/src/script/standard.cpp b/src/script/standard.cpp
index 540aa0f2d9..0a233b550a 100644
--- a/src/script/standard.cpp
+++ b/src/script/standard.cpp
@@ -242,13 +242,9 @@ bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
         return true;
     }
     case TxoutType::WITNESS_V1_TAPROOT: {
-        /* For now, no WitnessV1Taproot variant in CTxDestination exists, so map
-         * this to WitnessUnknown. */
-        WitnessUnknown unk;
-        unk.version = 1;
-        std::copy(vSolutions[0].begin(), vSolutions[0].end(), unk.program);
-        unk.length = vSolutions[0].size();
-        addressRet = unk;
+        WitnessV1Taproot tap;
+        std::copy(vSolutions[0].begin(), vSolutions[0].end(), tap.begin());
+        addressRet = tap;
         return true;
     }
     case TxoutType::WITNESS_UNKNOWN: {
@@ -337,6 +333,11 @@ public:
         return CScript() << OP_0 << ToByteVector(id);
     }
 
+    CScript operator()(const WitnessV1Taproot& tap) const
+    {
+        return CScript() << OP_1 << ToByteVector(tap);
+    }
+
     CScript operator()(const WitnessUnknown& id) const
     {
         return CScript() << CScript::EncodeOP_N(id.version) << std::vector<unsigned char>(id.program, id.program + id.length);
diff --git a/src/script/standard.h b/src/script/standard.h
index 12ab9979a8..a96b096fa7 100644
--- a/src/script/standard.h
+++ b/src/script/standard.h
@@ -6,6 +6,7 @@
 #ifndef BITCOIN_SCRIPT_STANDARD_H
 #define BITCOIN_SCRIPT_STANDARD_H
 
+#include <pubkey.h>
 #include <script/interpreter.h>
 #include <uint256.h>
 #include <util/hash_type.h>
@@ -113,6 +114,12 @@ struct WitnessV0KeyHash : public BaseHash<uint160>
 };
 CKeyID ToKeyID(const WitnessV0KeyHash& key_hash);
 
+struct WitnessV1Taproot : public XOnlyPubKey
+{
+    WitnessV1Taproot() : XOnlyPubKey() {}
+    explicit WitnessV1Taproot(const XOnlyPubKey& xpk) : XOnlyPubKey(xpk) {}
+};
+
 //! CTxDestination subtype to encode any future Witness version
 struct WitnessUnknown
 {
@@ -142,11 +149,11 @@ struct WitnessUnknown
  *  * ScriptHash: TxoutType::SCRIPTHASH destination (P2SH)
  *  * WitnessV0ScriptHash: TxoutType::WITNESS_V0_SCRIPTHASH destination (P2WSH)
  *  * WitnessV0KeyHash: TxoutType::WITNESS_V0_KEYHASH destination (P2WPKH)
- *  * WitnessUnknown: TxoutType::WITNESS_UNKNOWN/WITNESS_V1_TAPROOT destination (P2W???)
- *    (taproot outputs do not require their own type as long as no wallet support exists)
+ *  * WitnessV1Taproot: TxoutType::WITNESS_V1_TAPROOT destination (P2TR)
+ *  * WitnessUnknown: TxoutType::WITNESS_UNKNOWN destination (P2W???)
  *  A CTxDestination is the internal data type encoded in a bitcoin address
  */
-using CTxDestination = std::variant<CNoDestination, PKHash, ScriptHash, WitnessV0ScriptHash, WitnessV0KeyHash, WitnessUnknown>;
+using CTxDestination = std::variant<CNoDestination, PKHash, ScriptHash, WitnessV0ScriptHash, WitnessV0KeyHash, WitnessV1Taproot, WitnessUnknown>;
 
 /** Check whether a CTxDestination is a CNoDestination. */
 bool IsValidDestination(const CTxDestination& dest);
diff --git a/src/wallet/rpcwallet.cpp b/src/wallet/rpcwallet.cpp
index 4e3c8ce49d..dd74d9f36b 100644
--- a/src/wallet/rpcwallet.cpp
+++ b/src/wallet/rpcwallet.cpp
@@ -3737,6 +3737,7 @@ public:
         return obj;
     }
 
+    UniValue operator()(const WitnessV1Taproot& id) const { return UniValue(UniValue::VOBJ); }
     UniValue operator()(const WitnessUnknown& id) const { return UniValue(UniValue::VOBJ); }
 };
 
-- 
cgit v1.2.3


From 2fbfb1becb3c0c109cd7c30b245b51da22039932 Mon Sep 17 00:00:00 2001
From: Pieter Wuille <pieter@wuille.net>
Date: Mon, 1 Feb 2021 16:21:59 -0800
Subject: Make consensus checking of tweaks in pubkey.* Taproot-specific

That results in a much safer interface (making the tweak commit
to the key implicitly using a fixed tag means it can't be used for
unrelated tweaking).
---
 src/pubkey.cpp             | 22 ++++++++++++++++++----
 src/pubkey.h               | 15 ++++++++++++++-
 src/script/interpreter.cpp |  5 +----
 3 files changed, 33 insertions(+), 9 deletions(-)

(limited to 'src')

diff --git a/src/pubkey.cpp b/src/pubkey.cpp
index 334acb454e..f78779c182 100644
--- a/src/pubkey.cpp
+++ b/src/pubkey.cpp
@@ -188,11 +188,25 @@ 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 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());
+    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());
 }
 
 bool CPubKey::Verify(const uint256 &hash, const std::vector<unsigned char>& vchSig) const {
diff --git a/src/pubkey.h b/src/pubkey.h
index 7d09faa9c1..e5d9d08b52 100644
--- a/src/pubkey.h
+++ b/src/pubkey.h
@@ -236,7 +236,20 @@ public:
      * sigbytes must be exactly 64 bytes.
      */
     bool VerifySchnorr(const uint256& msg, Span<const unsigned char> sigbytes) const;
-    bool CheckPayToContract(const XOnlyPubKey& base, const uint256& hash, bool parity) const;
+
+    /** Compute the Taproot tweak as specified in BIP341, with *this as internal
+     * key:
+     *  - if merkle_root == nullptr: H_TapTweak(xonly_pubkey)
+     *  - otherwise:                 H_TapTweak(xonly_pubkey || *merkle_root)
+     *
+     * Note that the behavior of this function with merkle_root != nullptr is
+     * consensus critical.
+     */
+    uint256 ComputeTapTweakHash(const uint256* merkle_root) const;
+
+    /** Verify that this is a Taproot tweaked output point, against a specified internal key,
+     *  Merkle root, and parity. */
+    bool CheckTapTweak(const XOnlyPubKey& internal, const uint256& merkle_root, bool parity) const;
 
     const unsigned char& operator[](int pos) const { return *(m_keydata.begin() + pos); }
     const unsigned char* data() const { return m_keydata.begin(); }
diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
index dc0f165be0..5f04d486b1 100644
--- a/src/script/interpreter.cpp
+++ b/src/script/interpreter.cpp
@@ -1486,7 +1486,6 @@ template PrecomputedTransactionData::PrecomputedTransactionData(const CMutableTr
 static const CHashWriter HASHER_TAPSIGHASH = TaggedHash("TapSighash");
 static const CHashWriter HASHER_TAPLEAF = TaggedHash("TapLeaf");
 static const CHashWriter HASHER_TAPBRANCH = TaggedHash("TapBranch");
-static const CHashWriter HASHER_TAPTWEAK = TaggedHash("TapTweak");
 
 static bool HandleMissingData(MissingDataBehavior mdb)
 {
@@ -1869,10 +1868,8 @@ static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, c
         }
         k = ss_branch.GetSHA256();
     }
-    // Compute the tweak from the Merkle root and the internal pubkey.
-    k = (CHashWriter(HASHER_TAPTWEAK) << MakeSpan(p) << k).GetSHA256();
     // Verify that the output pubkey matches the tweaked internal pubkey, after correcting for parity.
-    return q.CheckPayToContract(p, k, control[0] & 1);
+    return q.CheckTapTweak(p, k, control[0] & 1);
 }
 
 static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector<unsigned char>& program, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror, bool is_p2sh)
-- 
cgit v1.2.3


From 5f6cc8daa83700d1c949d968a5cf0d935be337b7 Mon Sep 17 00:00:00 2001
From: Pieter Wuille <pieter@wuille.net>
Date: Sun, 23 May 2021 18:32:30 -0700
Subject: Add XOnlyPubKey::CreateTapTweak

---
 src/pubkey.cpp | 18 ++++++++++++++++++
 src/pubkey.h   |  4 ++++
 2 files changed, 22 insertions(+)

(limited to 'src')

diff --git a/src/pubkey.cpp b/src/pubkey.cpp
index f78779c182..8382897f95 100644
--- a/src/pubkey.cpp
+++ b/src/pubkey.cpp
@@ -209,6 +209,24 @@ bool XOnlyPubKey::CheckTapTweak(const XOnlyPubKey& internal, const uint256& merk
     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, 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;
diff --git a/src/pubkey.h b/src/pubkey.h
index e5d9d08b52..b9d5f5d622 100644
--- a/src/pubkey.h
+++ b/src/pubkey.h
@@ -13,6 +13,7 @@
 #include <uint256.h>
 
 #include <cstring>
+#include <optional>
 #include <vector>
 
 const unsigned int BIP32_EXTKEY_SIZE = 74;
@@ -251,6 +252,9 @@ public:
      *  Merkle root, and parity. */
     bool CheckTapTweak(const XOnlyPubKey& internal, const uint256& merkle_root, bool parity) const;
 
+    /** Construct a Taproot tweaked output point with this point as internal key. */
+    std::optional<std::pair<XOnlyPubKey, bool>> CreateTapTweak(const uint256* merkle_root) const;
+
     const unsigned char& operator[](int pos) const { return *(m_keydata.begin() + pos); }
     const unsigned char* data() const { return m_keydata.begin(); }
     static constexpr size_t size() { return decltype(m_keydata)::size(); }
-- 
cgit v1.2.3


From 90fcac365e1616779b40a69736428435df75fdf2 Mon Sep 17 00:00:00 2001
From: Pieter Wuille <pieter@wuille.net>
Date: Mon, 1 Feb 2021 18:53:24 -0800
Subject: Add TaprootBuilder class

This class functions as a utility for building taproot outputs, from
internal key and script leaves.
---
 src/pubkey.cpp                     |  6 +++
 src/pubkey.h                       |  5 ++
 src/script/interpreter.cpp         |  4 +-
 src/script/interpreter.h           |  4 ++
 src/script/standard.cpp            | 99 ++++++++++++++++++++++++++++++++++++++
 src/script/standard.h              | 78 ++++++++++++++++++++++++++++++
 src/test/script_standard_tests.cpp | 68 ++++++++++++++++++++++++++
 7 files changed, 262 insertions(+), 2 deletions(-)

(limited to 'src')

diff --git a/src/pubkey.cpp b/src/pubkey.cpp
index 8382897f95..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);
diff --git a/src/pubkey.h b/src/pubkey.h
index b9d5f5d622..4de1807a7f 100644
--- a/src/pubkey.h
+++ b/src/pubkey.h
@@ -229,6 +229,11 @@ public:
     XOnlyPubKey(const XOnlyPubKey&) = default;
     XOnlyPubKey& operator=(const XOnlyPubKey&) = default;
 
+    /** Determine if this pubkey is fully valid. This is true for approximately 50% of all
+     *  possible 32-byte arrays. If false, VerifySchnorr and CreatePayToContract will always
+     *  fail. */
+    bool IsFullyValid() const;
+
     /** Construct an x-only pubkey from exactly 32 bytes. */
     explicit XOnlyPubKey(Span<const unsigned char> bytes);
 
diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
index 5f04d486b1..3c3c3ac1a8 100644
--- a/src/script/interpreter.cpp
+++ b/src/script/interpreter.cpp
@@ -1484,8 +1484,8 @@ template PrecomputedTransactionData::PrecomputedTransactionData(const CTransacti
 template PrecomputedTransactionData::PrecomputedTransactionData(const CMutableTransaction& txTo);
 
 static const CHashWriter HASHER_TAPSIGHASH = TaggedHash("TapSighash");
-static const CHashWriter HASHER_TAPLEAF = TaggedHash("TapLeaf");
-static const CHashWriter HASHER_TAPBRANCH = TaggedHash("TapBranch");
+const CHashWriter HASHER_TAPLEAF = TaggedHash("TapLeaf");
+const CHashWriter HASHER_TAPBRANCH = TaggedHash("TapBranch");
 
 static bool HandleMissingData(MissingDataBehavior mdb)
 {
diff --git a/src/script/interpreter.h b/src/script/interpreter.h
index 212de17c7b..fa4ee83e04 100644
--- a/src/script/interpreter.h
+++ b/src/script/interpreter.h
@@ -6,6 +6,7 @@
 #ifndef BITCOIN_SCRIPT_INTERPRETER_H
 #define BITCOIN_SCRIPT_INTERPRETER_H
 
+#include <hash.h>
 #include <script/script_error.h>
 #include <span.h>
 #include <primitives/transaction.h>
@@ -218,6 +219,9 @@ static constexpr size_t TAPROOT_CONTROL_NODE_SIZE = 32;
 static constexpr size_t TAPROOT_CONTROL_MAX_NODE_COUNT = 128;
 static constexpr size_t TAPROOT_CONTROL_MAX_SIZE = TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * TAPROOT_CONTROL_MAX_NODE_COUNT;
 
+extern const CHashWriter HASHER_TAPLEAF;    //!< Hasher with tag "TapLeaf" pre-fed to it.
+extern const CHashWriter HASHER_TAPBRANCH;  //!< Hasher with tag "TapBranch" pre-fed to it.
+
 template <class T>
 uint256 SignatureHash(const CScript& scriptCode, const T& txTo, unsigned int nIn, int nHashType, const CAmount& amount, SigVersion sigversion, const PrecomputedTransactionData* cache = nullptr);
 
diff --git a/src/script/standard.cpp b/src/script/standard.cpp
index 0a233b550a..a4b11cc0a9 100644
--- a/src/script/standard.cpp
+++ b/src/script/standard.cpp
@@ -6,8 +6,11 @@
 #include <script/standard.h>
 
 #include <crypto/sha256.h>
+#include <hash.h>
 #include <pubkey.h>
+#include <script/interpreter.h>
 #include <script/script.h>
+#include <util/strencodings.h>
 
 #include <string>
 
@@ -370,3 +373,99 @@ CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys)
 bool IsValidDestination(const CTxDestination& dest) {
     return dest.index() != 0;
 }
+
+/*static*/ TaprootBuilder::NodeInfo TaprootBuilder::Combine(NodeInfo&& a, NodeInfo&& b)
+{
+    NodeInfo ret;
+    /* Lexicographically sort a and b's hash, and compute parent hash. */
+    if (a.hash < b.hash) {
+        ret.hash = (CHashWriter(HASHER_TAPBRANCH) << a.hash << b.hash).GetSHA256();
+    } else {
+        ret.hash = (CHashWriter(HASHER_TAPBRANCH) << b.hash << a.hash).GetSHA256();
+    }
+    return ret;
+}
+
+void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth)
+{
+    assert(depth >= 0 && (size_t)depth <= TAPROOT_CONTROL_MAX_NODE_COUNT);
+    /* We cannot insert a leaf at a lower depth while a deeper branch is unfinished. Doing
+     * so would mean the Add() invocations do not correspond to a DFS traversal of a
+     * binary tree. */
+    if ((size_t)depth + 1 < m_branch.size()) {
+        m_valid = false;
+        return;
+    }
+    /* As long as an entry in the branch exists at the specified depth, combine it and propagate up.
+     * The 'node' variable is overwritten here with the newly combined node. */
+    while (m_valid && m_branch.size() > (size_t)depth && m_branch[depth].has_value()) {
+        node = Combine(std::move(node), std::move(*m_branch[depth]));
+        m_branch.pop_back();
+        if (depth == 0) m_valid = false; /* Can't propagate further up than the root */
+        --depth;
+    }
+    if (m_valid) {
+        /* Make sure the branch is big enough to place the new node. */
+        if (m_branch.size() <= (size_t)depth) m_branch.resize((size_t)depth + 1);
+        assert(!m_branch[depth].has_value());
+        m_branch[depth] = std::move(node);
+    }
+}
+
+/*static*/ bool TaprootBuilder::ValidDepths(const std::vector<int>& depths)
+{
+    std::vector<bool> branch;
+    for (int depth : depths) {
+        // This inner loop corresponds to effectively the same logic on branch
+        // as what Insert() performs on the m_branch variable. Instead of
+        // storing a NodeInfo object, just remember whether or not there is one
+        // at that depth.
+        if (depth < 0 || (size_t)depth > TAPROOT_CONTROL_MAX_NODE_COUNT) return false;
+        if ((size_t)depth + 1 < branch.size()) return false;
+        while (branch.size() > (size_t)depth && branch[depth]) {
+            branch.pop_back();
+            if (depth == 0) return false;
+            --depth;
+        }
+        if (branch.size() <= (size_t)depth) branch.resize((size_t)depth + 1);
+        assert(!branch[depth]);
+        branch[depth] = true;
+    }
+    // And this check corresponds to the IsComplete() check on m_branch.
+    return branch.size() == 0 || (branch.size() == 1 && branch[0]);
+}
+
+TaprootBuilder& TaprootBuilder::Add(int depth, const CScript& script, int leaf_version)
+{
+    assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0);
+    if (!IsValid()) return *this;
+    /* Construct NodeInfo object with leaf hash. */
+    NodeInfo node;
+    node.hash = (CHashWriter{HASHER_TAPLEAF} << uint8_t(leaf_version) << script).GetSHA256();
+    /* Insert into the branch. */
+    Insert(std::move(node), depth);
+    return *this;
+}
+
+TaprootBuilder& TaprootBuilder::AddOmitted(int depth, const uint256& hash)
+{
+    if (!IsValid()) return *this;
+    /* Construct NodeInfo object with the hash directly, and insert it into the branch. */
+    NodeInfo node;
+    node.hash = hash;
+    Insert(std::move(node), depth);
+    return *this;
+}
+
+TaprootBuilder& TaprootBuilder::Finalize(const XOnlyPubKey& internal_key)
+{
+    /* Can only call this function when IsComplete() is true. */
+    assert(IsComplete());
+    m_internal_key = internal_key;
+    auto ret = m_internal_key.CreateTapTweak(m_branch.size() == 0 ? nullptr : &m_branch[0]->hash);
+    assert(ret.has_value());
+    std::tie(m_output_key, std::ignore) = *ret;
+    return *this;
+}
+
+WitnessV1Taproot TaprootBuilder::GetOutput() { return WitnessV1Taproot{m_output_key}; }
diff --git a/src/script/standard.h b/src/script/standard.h
index a96b096fa7..d7ea5cef27 100644
--- a/src/script/standard.h
+++ b/src/script/standard.h
@@ -209,4 +209,82 @@ CScript GetScriptForRawPubKey(const CPubKey& pubkey);
 /** Generate a multisig script. */
 CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys);
 
+/** Utility class to construct Taproot outputs from internal key and script tree. */
+class TaprootBuilder
+{
+private:
+    /** Information associated with a node in the Merkle tree. */
+    struct NodeInfo
+    {
+        /** Merkle hash of this node. */
+        uint256 hash;
+    };
+    /** Whether the builder is in a valid state so far. */
+    bool m_valid = true;
+
+    /** The current state of the builder.
+     *
+     * For each level in the tree, one NodeInfo object may be present. m_branch[0]
+     * is information about the root; further values are for deeper subtrees being
+     * explored.
+     *
+     * For every right branch taken to reach the position we're currently
+     * working in, there will be a (non-nullopt) entry in m_branch corresponding
+     * to the left branch at that level.
+     *
+     * For example, imagine this tree:     - N0 -
+     *                                    /      \
+     *                                   N1      N2
+     *                                  /  \    /  \
+     *                                 A    B  C   N3
+     *                                            /  \
+     *                                           D    E
+     *
+     * Initially, m_branch is empty. After processing leaf A, it would become
+     * {nullopt, nullopt, A}. When processing leaf B, an entry at level 2 already
+     * exists, and it would thus be combined with it to produce a level 1 one,
+     * resulting in {nullopt, N1}. Adding C and D takes us to {nullopt, N1, C}
+     * and {nullopt, N1, C, D} respectively. When E is processed, it is combined
+     * with D, and then C, and then N1, to produce the root, resulting in {N0}.
+     *
+     * This structure allows processing with just O(log n) overhead if the leaves
+     * are computed on the fly.
+     *
+     * As an invariant, there can never be nullopt entries at the end. There can
+     * also not be more than 128 entries (as that would mean more than 128 levels
+     * in the tree). The depth of newly added entries will always be at least
+     * equal to the current size of m_branch (otherwise it does not correspond
+     * to a depth-first traversal of a tree). m_branch is only empty if no entries
+     * have ever be processed. m_branch having length 1 corresponds to being done.
+     */
+    std::vector<std::optional<NodeInfo>> m_branch;
+
+    XOnlyPubKey m_internal_key;  //!< The internal key, set when finalizing.
+    XOnlyPubKey m_output_key; //!< The output key, computed when finalizing. */
+
+    /** Combine information about a parent Merkle tree node from its child nodes. */
+    static NodeInfo Combine(NodeInfo&& a, NodeInfo&& b);
+    /** Insert information about a node at a certain depth, and propagate information up. */
+    void Insert(NodeInfo&& node, int depth);
+
+public:
+    /** Add a new script at a certain depth in the tree. Add() operations must be called
+     *  in depth-first traversal order of binary tree. */
+    TaprootBuilder& Add(int depth, const CScript& script, int leaf_version);
+    /** Like Add(), but for a Merkle node with a given hash to the tree. */
+    TaprootBuilder& AddOmitted(int depth, const uint256& hash);
+    /** Finalize the construction. Can only be called when IsComplete() is true.
+        internal_key.IsFullyValid() must be true. */
+    TaprootBuilder& Finalize(const XOnlyPubKey& internal_key);
+
+    /** Return true if so far all input was valid. */
+    bool IsValid() const { return m_valid; }
+    /** Return whether there were either no leaves, or the leaves form a Huffman tree. */
+    bool IsComplete() const { return m_valid && (m_branch.size() == 0 || (m_branch.size() == 1 && m_branch[0].has_value())); }
+    /** Compute scriptPubKey (after Finalize()). */
+    WitnessV1Taproot GetOutput();
+    /** Check if a list of depths is legal (will lead to IsComplete()). */
+    static bool ValidDepths(const std::vector<int>& depths);
+};
+
 #endif // BITCOIN_SCRIPT_STANDARD_H
diff --git a/src/test/script_standard_tests.cpp b/src/test/script_standard_tests.cpp
index 950f3b970a..a01d3fa03a 100644
--- a/src/test/script_standard_tests.cpp
+++ b/src/test/script_standard_tests.cpp
@@ -3,10 +3,12 @@
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
 #include <key.h>
+#include <key_io.h>
 #include <script/script.h>
 #include <script/signingprovider.h>
 #include <script/standard.h>
 #include <test/util/setup_common.h>
+#include <util/strencodings.h>
 
 #include <boost/test/unit_test.hpp>
 
@@ -378,4 +380,70 @@ BOOST_AUTO_TEST_CASE(script_standard_GetScriptFor_)
     BOOST_CHECK(result == expected);
 }
 
+BOOST_AUTO_TEST_CASE(script_standard_taproot_builder)
+{
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({}), true);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0}), true);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,1}), true);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,0,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,0,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,0,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,1,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,1,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,1,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,2,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,2,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({0,2,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,0,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,0,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,0,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,1,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,1,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,1,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,2,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,2,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({1,2,2}), true);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,0,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,0,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,0,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,1,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,1,1}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,1,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,2,0}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,2,1}), true);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,2,2}), false);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({2,2,2,3,4,5,6,7,8,9,10,11,12,14,14,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,31,31,31,31,31,31,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,128}), true);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({128,128,127,126,125,124,123,122,121,120,119,118,117,116,115,114,113,112,111,110,109,108,107,106,105,104,103,102,101,100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}), true);
+    BOOST_CHECK_EQUAL(TaprootBuilder::ValidDepths({129,129,128,127,126,125,124,123,122,121,120,119,118,117,116,115,114,113,112,111,110,109,108,107,106,105,104,103,102,101,100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}), false);
+
+    XOnlyPubKey key_inner{ParseHex("79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798")};
+    XOnlyPubKey key_1{ParseHex("c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5")};
+    XOnlyPubKey key_2{ParseHex("f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9")};
+    CScript script_1 = CScript() << ToByteVector(key_1) << OP_CHECKSIG;
+    CScript script_2 = CScript() << ToByteVector(key_2) << OP_CHECKSIG;
+    uint256 hash_3 = uint256S("31fe7061656bea2a36aa60a2f7ef940578049273746935d296426dc0afd86b68");
+
+    TaprootBuilder builder;
+    BOOST_CHECK(builder.IsValid() && builder.IsComplete());
+    builder.Add(2, script_2, 0xc0);
+    BOOST_CHECK(builder.IsValid() && !builder.IsComplete());
+    builder.AddOmitted(2, hash_3);
+    BOOST_CHECK(builder.IsValid() && !builder.IsComplete());
+    builder.Add(1, script_1, 0xc0);
+    BOOST_CHECK(builder.IsValid() && builder.IsComplete());
+    builder.Finalize(key_inner);
+    BOOST_CHECK(builder.IsValid() && builder.IsComplete());
+    BOOST_CHECK_EQUAL(EncodeDestination(builder.GetOutput()), "bc1pj6gaw944fy0xpmzzu45ugqde4rz7mqj5kj0tg8kmr5f0pjq8vnaqgynnge");
+}
+
 BOOST_AUTO_TEST_SUITE_END()
-- 
cgit v1.2.3


From 7cedafc5412857404e9a6c3450b100cb8ee4081a Mon Sep 17 00:00:00 2001
From: Pieter Wuille <pieter@wuille.net>
Date: Sun, 7 Feb 2021 19:18:39 -0800
Subject: Add tr() descriptor (derivation only, no signing)

This adds a new descriptor with syntax e.g. tr(KEY,{S1,{{S2,S3},S4})
where KEY is a key expression for the internal key and S_i are
script expression for the leaves. They have to be organized in
nested {A,B} groups, with exactly two elements.

tr() only exists at the top level, and inside the script expressions
only pk() scripts are allowed for now.
---
 src/pubkey.h              |   3 +
 src/script/descriptor.cpp | 151 +++++++++++++++++++++++++++++++++++++++++++---
 src/util/spanparsing.cpp  |   6 +-
 3 files changed, 150 insertions(+), 10 deletions(-)

(limited to 'src')

diff --git a/src/pubkey.h b/src/pubkey.h
index 4de1807a7f..152a48dd18 100644
--- a/src/pubkey.h
+++ b/src/pubkey.h
@@ -237,6 +237,9 @@ public:
     /** Construct an x-only pubkey from exactly 32 bytes. */
     explicit XOnlyPubKey(Span<const unsigned char> bytes);
 
+    /** Construct an x-only pubkey from a normal pubkey. */
+    explicit XOnlyPubKey(const CPubKey& pubkey) : XOnlyPubKey(Span<const unsigned char>(pubkey.begin() + 1, pubkey.begin() + 33)) {}
+
     /** Verify a Schnorr signature against this public key.
      *
      * sigbytes must be exactly 64 bytes.
diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
index d4b43932b9..51cf8a7d62 100644
--- a/src/script/descriptor.cpp
+++ b/src/script/descriptor.cpp
@@ -241,9 +241,10 @@ public:
 class ConstPubkeyProvider final : public PubkeyProvider
 {
     CPubKey m_pubkey;
+    bool m_xonly;
 
 public:
-    ConstPubkeyProvider(uint32_t exp_index, const CPubKey& pubkey) : PubkeyProvider(exp_index), m_pubkey(pubkey) {}
+    ConstPubkeyProvider(uint32_t exp_index, const CPubKey& pubkey, bool xonly = false) : PubkeyProvider(exp_index), m_pubkey(pubkey), m_xonly(xonly) {}
     bool GetPubKey(int pos, const SigningProvider& arg, CPubKey& key, KeyOriginInfo& info, const DescriptorCache* read_cache = nullptr, DescriptorCache* write_cache = nullptr) override
     {
         key = m_pubkey;
@@ -254,7 +255,7 @@ public:
     }
     bool IsRange() const override { return false; }
     size_t GetSize() const override { return m_pubkey.size(); }
-    std::string ToString() const override { return HexStr(m_pubkey); }
+    std::string ToString() const override { return m_xonly ? HexStr(m_pubkey).substr(2) : HexStr(m_pubkey); }
     bool ToPrivateString(const SigningProvider& arg, std::string& ret) const override
     {
         CKey key;
@@ -505,6 +506,7 @@ protected:
 public:
     DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_args() {}
     DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, std::unique_ptr<DescriptorImpl> script, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_args(Vector(std::move(script))) {}
+    DescriptorImpl(std::vector<std::unique_ptr<PubkeyProvider>> pubkeys, std::vector<std::unique_ptr<DescriptorImpl>> scripts, const std::string& name) : m_pubkey_args(std::move(pubkeys)), m_name(name), m_subdescriptor_args(std::move(scripts)) {}
 
     bool IsSolvable() const override
     {
@@ -693,10 +695,20 @@ public:
 /** A parsed pk(P) descriptor. */
 class PKDescriptor final : public DescriptorImpl
 {
+private:
+    const bool m_xonly;
 protected:
-    std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider&) const override { return Vector(GetScriptForRawPubKey(keys[0])); }
+    std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript>, FlatSigningProvider&) const override
+    {
+        if (m_xonly) {
+            CScript script = CScript() << ToByteVector(XOnlyPubKey(keys[0])) << OP_CHECKSIG;
+            return Vector(std::move(script));
+        } else {
+            return Vector(GetScriptForRawPubKey(keys[0]));
+        }
+    }
 public:
-    PKDescriptor(std::unique_ptr<PubkeyProvider> prov) : DescriptorImpl(Vector(std::move(prov)), "pk") {}
+    PKDescriptor(std::unique_ptr<PubkeyProvider> prov, bool xonly = false) : DescriptorImpl(Vector(std::move(prov)), "pk"), m_xonly(xonly) {}
     bool IsSingleType() const final { return true; }
 };
 
@@ -814,6 +826,56 @@ public:
     bool IsSingleType() const final { return true; }
 };
 
+/** A parsed tr(...) descriptor. */
+class TRDescriptor final : public DescriptorImpl
+{
+    std::vector<int> m_depths;
+protected:
+    std::vector<CScript> MakeScripts(const std::vector<CPubKey>& keys, Span<const CScript> scripts, FlatSigningProvider& out) const override
+    {
+        TaprootBuilder builder;
+        assert(m_depths.size() == scripts.size());
+        for (size_t pos = 0; pos < m_depths.size(); ++pos) {
+            builder.Add(m_depths[pos], scripts[pos], TAPROOT_LEAF_TAPSCRIPT);
+        }
+        if (!builder.IsComplete()) return {};
+        assert(keys.size() == 1);
+        XOnlyPubKey xpk(keys[0]);
+        if (!xpk.IsFullyValid()) return {};
+        builder.Finalize(xpk);
+        return Vector(GetScriptForDestination(builder.GetOutput()));
+    }
+    bool ToStringSubScriptHelper(const SigningProvider* arg, std::string& ret, bool priv, bool normalized) const override
+    {
+        if (m_depths.empty()) return true;
+        std::vector<bool> path;
+        for (size_t pos = 0; pos < m_depths.size(); ++pos) {
+            if (pos) ret += ',';
+            while ((int)path.size() <= m_depths[pos]) {
+                if (path.size()) ret += '{';
+                path.push_back(false);
+            }
+            std::string tmp;
+            if (!m_subdescriptor_args[pos]->ToStringHelper(arg, tmp, priv, normalized)) return false;
+            ret += std::move(tmp);
+            while (!path.empty() && path.back()) {
+                if (path.size() > 1) ret += '}';
+                path.pop_back();
+            }
+            if (!path.empty()) path.back() = true;
+        }
+        return true;
+    }
+public:
+    TRDescriptor(std::unique_ptr<PubkeyProvider> internal_key, std::vector<std::unique_ptr<DescriptorImpl>> descs, std::vector<int> depths) :
+        DescriptorImpl(Vector(std::move(internal_key)), std::move(descs), "tr"), m_depths(std::move(depths))
+    {
+        assert(m_subdescriptor_args.size() == m_depths.size());
+    }
+    std::optional<OutputType> GetOutputType() const override { return OutputType::BECH32; }
+    bool IsSingleType() const final { return true; }
+};
+
 ////////////////////////////////////////////////////////////////////////////
 // Parser                                                                 //
 ////////////////////////////////////////////////////////////////////////////
@@ -823,6 +885,7 @@ enum class ParseScriptContext {
     P2SH,    //!< Inside sh() (script becomes P2SH redeemScript)
     P2WPKH,  //!< Inside wpkh() (no script, pubkey only)
     P2WSH,   //!< Inside wsh() (script becomes v0 witness script)
+    P2TR,    //!< Inside tr() (either internal key, or BIP342 script leaf)
 };
 
 /** Parse a key path, being passed a split list of elements (the first element is ignored). */
@@ -871,6 +934,13 @@ std::unique_ptr<PubkeyProvider> ParsePubkeyInner(uint32_t key_exp_index, const S
                     error = "Uncompressed keys are not allowed";
                     return nullptr;
                 }
+            } else if (data.size() == 32 && ctx == ParseScriptContext::P2TR) {
+                unsigned char fullkey[33] = {0x02};
+                std::copy(data.begin(), data.end(), fullkey + 1);
+                pubkey.Set(std::begin(fullkey), std::end(fullkey));
+                if (pubkey.IsFullyValid()) {
+                    return std::make_unique<ConstPubkeyProvider>(key_exp_index, pubkey, true);
+                }
             }
             error = strprintf("Pubkey '%s' is invalid", str);
             return nullptr;
@@ -958,13 +1028,16 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const
         auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error);
         if (!pubkey) return nullptr;
         ++key_exp_index;
-        return std::make_unique<PKDescriptor>(std::move(pubkey));
+        return std::make_unique<PKDescriptor>(std::move(pubkey), ctx == ParseScriptContext::P2TR);
     }
-    if (Func("pkh", expr)) {
+    if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH) && Func("pkh", expr)) {
         auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error);
         if (!pubkey) return nullptr;
         ++key_exp_index;
         return std::make_unique<PKHDescriptor>(std::move(pubkey));
+    } else if (Func("pkh", expr)) {
+        error = "Can only have pkh at top level, in sh(), or in wsh()";
+        return nullptr;
     }
     if (ctx == ParseScriptContext::TOP && Func("combo", expr)) {
         auto pubkey = ParsePubkey(key_exp_index, expr, ctx, out, error);
@@ -975,7 +1048,7 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const
         error = "Can only have combo() at top level";
         return nullptr;
     }
-    if ((sorted_multi = Func("sortedmulti", expr)) || Func("multi", expr)) {
+    if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH || ctx == ParseScriptContext::P2WSH) && ((sorted_multi = Func("sortedmulti", expr)) || Func("multi", expr))) {
         auto threshold = Expr(expr);
         uint32_t thres;
         std::vector<std::unique_ptr<PubkeyProvider>> providers;
@@ -1020,6 +1093,9 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const
             }
         }
         return std::make_unique<MultisigDescriptor>(thres, std::move(providers), sorted_multi);
+    } else if (Func("sortedmulti", expr) || Func("multi", expr)) {
+        error = "Can only have multi/sortedmulti at top level, in sh(), or in wsh()";
+        return nullptr;
     }
     if ((ctx == ParseScriptContext::TOP || ctx == ParseScriptContext::P2SH) && Func("wpkh", expr)) {
         auto pubkey = ParsePubkey(key_exp_index, expr, ParseScriptContext::P2WPKH, out, error);
@@ -1057,6 +1133,67 @@ std::unique_ptr<DescriptorImpl> ParseScript(uint32_t& key_exp_index, Span<const
         error = "Can only have addr() at top level";
         return nullptr;
     }
+    if (ctx == ParseScriptContext::TOP && Func("tr", expr)) {
+        auto arg = Expr(expr);
+        auto internal_key = ParsePubkey(key_exp_index, arg, ParseScriptContext::P2TR, out, error);
+        if (!internal_key) return nullptr;
+        ++key_exp_index;
+        std::vector<std::unique_ptr<DescriptorImpl>> subscripts; //!< list of script subexpressions
+        std::vector<int> depths; //!< depth in the tree of each subexpression (same length subscripts)
+        if (expr.size()) {
+            if (!Const(",", expr)) {
+                error = strprintf("tr: expected ',', got '%c'", expr[0]);
+                return nullptr;
+            }
+            /** The path from the top of the tree to what we're currently processing.
+             * branches[i] == false: left branch in the i'th step from the top; true: right branch.
+             */
+            std::vector<bool> branches;
+            // Loop over all provided scripts. In every iteration exactly one script will be processed.
+            // Use a do-loop because inside this if-branch we expect at least one script.
+            do {
+                // First process all open braces.
+                while (Const("{", expr)) {
+                    branches.push_back(false); // new left branch
+                    if (branches.size() > TAPROOT_CONTROL_MAX_NODE_COUNT) {
+                        error = strprintf("tr() supports at most %i nesting levels", TAPROOT_CONTROL_MAX_NODE_COUNT);
+                        return nullptr;
+                    }
+                }
+                // Process the actual script expression.
+                auto sarg = Expr(expr);
+                subscripts.emplace_back(ParseScript(key_exp_index, sarg, ParseScriptContext::P2TR, out, error));
+                if (!subscripts.back()) return nullptr;
+                depths.push_back(branches.size());
+                // Process closing braces; one is expected for every right branch we were in.
+                while (branches.size() && branches.back()) {
+                    if (!Const("}", expr)) {
+                        error = strprintf("tr(): expected '}' after script expression");
+                        return nullptr;
+                    }
+                    branches.pop_back(); // move up one level after encountering '}'
+                }
+                // If after that, we're at the end of a left branch, expect a comma.
+                if (branches.size() && !branches.back()) {
+                    if (!Const(",", expr)) {
+                        error = strprintf("tr(): expected ',' after script expression");
+                        return nullptr;
+                    }
+                    branches.back() = true; // And now we're in a right branch.
+                }
+            } while (branches.size());
+            // After we've explored a whole tree, we must be at the end of the expression.
+            if (expr.size()) {
+                error = strprintf("tr(): expected ')' after script expression");
+                return nullptr;
+            }
+        }
+        assert(TaprootBuilder::ValidDepths(depths));
+        return std::make_unique<TRDescriptor>(std::move(internal_key), std::move(subscripts), std::move(depths));
+    } else if (Func("tr", expr)) {
+        error = "Can only have tr at top level";
+        return nullptr;
+    }
     if (ctx == ParseScriptContext::TOP && Func("raw", expr)) {
         std::string str(expr.begin(), expr.end());
         if (!IsHex(str)) {
diff --git a/src/util/spanparsing.cpp b/src/util/spanparsing.cpp
index 0f68254f2c..e2e2782bec 100644
--- a/src/util/spanparsing.cpp
+++ b/src/util/spanparsing.cpp
@@ -34,11 +34,11 @@ Span<const char> Expr(Span<const char>& sp)
     int level = 0;
     auto it = sp.begin();
     while (it != sp.end()) {
-        if (*it == '(') {
+        if (*it == '(' || *it == '{') {
             ++level;
-        } else if (level && *it == ')') {
+        } else if (level && (*it == ')' || *it == '}')) {
             --level;
-        } else if (level == 0 && (*it == ')' || *it == ',')) {
+        } else if (level == 0 && (*it == ')' || *it == '}' || *it == ',')) {
             break;
         }
         ++it;
-- 
cgit v1.2.3