Merge bitcoin/bitcoin#25858: psbt: Only include PSBT_OUT_TAP_TREE when the output has a script path

9e386afb67bf8fa71b72f730da1695eeb11828cd tests: Test that PSBT_OUT_TAP_TREE is included correctly (Andrew Chow)
30ff25cf37eec4b09ab40424eb5d6a4a80410955 psbt: Only include m_tap_tree if it has scripts (Andrew Chow)
0577d423adda8e719d7611d03355680c8fbacab8 psbt: Change m_tap_tree to store just the tuples (Andrew Chow)
22c051ca70bae73e0430b05fb9d879591df27699 tests: Test that PSBT_OUT_TAP_TREE is combined correctly (Andrew Chow)
7df6e1bb77a96eac4fbcba424bbe780636b86650 psbt: Fix merging of m_tap_tree (Andrew Chow)
0652dc53b291bd295caff4093ec2854fd4b34645 [BugFix]: Do not allow deserializing PSBT with empty PSBT_OUT_TAP_TREE (Jeremy Rubin)

Pull request description:

  PSBT_OUT_TAP_TREE should not be included for outputs that do not have such a tree. This should be disallowed during parsing, as well as prior to serialization when the field is populated during updating.

  Also added some test cases.

  Alternative to #25856

ACKs for top commit:
  instagibbs:
    ACK https://github.com/bitcoin/bitcoin/pull/25858/commits/9e386afb67bf8fa71b72f730da1695eeb11828cd
  darosior:
    ACK 9e386afb67bf8fa71b72f730da1695eeb11828cd

Tree-SHA512: ce5c02a69752d176dbd967c1e8d30129b1905c8f186aeeef034576c1de82059271a1ee846bd040f5be4e66bb77ba711dcf14ac1e597c5707d7e7e2293f6cfefb

4 files changed, 25 insertions, 26 deletions

diff --git a/src/psbt.cpp b/src/psbt.cpp
index 36fec74bc9..cbf2f88788 100644
--- a/src/psbt.cpp
+++ b/src/psbt.cpp
@@ -218,8 +218,14 @@ void PSBTOutput::FillSignatureData(SignatureData& sigdata) const
     for (const auto& key_pair : hd_keypaths) {
         sigdata.misc_pubkeys.emplace(key_pair.first.GetID(), key_pair);
     }
-    if (m_tap_tree.has_value() && m_tap_internal_key.IsFullyValid()) {
-        TaprootSpendData spenddata = m_tap_tree->GetSpendData();
+    if (!m_tap_tree.empty() && m_tap_internal_key.IsFullyValid()) {
+        TaprootBuilder builder;
+        for (const auto& [depth, leaf_ver, script] : m_tap_tree) {
+            builder.Add((int)depth, script, (int)leaf_ver, /*track=*/true);
+        }
+        assert(builder.IsComplete());
+        builder.Finalize(m_tap_internal_key);
+        TaprootSpendData spenddata = builder.GetSpendData();
 
         sigdata.tr_spenddata.internal_key = m_tap_internal_key;
         sigdata.tr_spenddata.Merge(spenddata);
@@ -243,8 +249,8 @@ void PSBTOutput::FromSignatureData(const SignatureData& sigdata)
     if (!sigdata.tr_spenddata.internal_key.IsNull()) {
         m_tap_internal_key = sigdata.tr_spenddata.internal_key;
     }
-    if (sigdata.tr_builder.has_value()) {
-        m_tap_tree = sigdata.tr_builder;
+    if (sigdata.tr_builder.has_value() && sigdata.tr_builder->HasScripts()) {
+        m_tap_tree = sigdata.tr_builder->GetTreeTuples();
     }
     for (const auto& [pubkey, leaf_origin] : sigdata.taproot_misc_pubkeys) {
         m_tap_bip32_paths.emplace(pubkey, leaf_origin);
@@ -265,7 +271,7 @@ void PSBTOutput::Merge(const PSBTOutput& output)
     if (redeem_script.empty() && !output.redeem_script.empty()) redeem_script = output.redeem_script;
     if (witness_script.empty() && !output.witness_script.empty()) witness_script = output.witness_script;
     if (m_tap_internal_key.IsNull() && !output.m_tap_internal_key.IsNull()) m_tap_internal_key = output.m_tap_internal_key;
-    if (m_tap_tree.has_value() && !output.m_tap_tree.has_value()) m_tap_tree = output.m_tap_tree;
+    if (m_tap_tree.empty() && !output.m_tap_tree.empty()) m_tap_tree = output.m_tap_tree;
 }
 bool PSBTInputSigned(const PSBTInput& input)
 {
diff --git a/src/psbt.h b/src/psbt.h
index d5c67802c7..ddcdb8c68d 100644
--- a/src/psbt.h
+++ b/src/psbt.h
@@ -713,7 +713,7 @@ struct PSBTOutput
     CScript witness_script;
     std::map<CPubKey, KeyOriginInfo> hd_keypaths;
     XOnlyPubKey m_tap_internal_key;
-    std::optional<TaprootBuilder> m_tap_tree;
+    std::vector<std::tuple<uint8_t, uint8_t, CScript>> m_tap_tree;
     std::map<XOnlyPubKey, std::pair<std::set<uint256>, KeyOriginInfo>> m_tap_bip32_paths;
     std::map<std::vector<unsigned char>, std::vector<unsigned char>> unknown;
     std::set<PSBTProprietary> m_proprietary;
@@ -754,15 +754,11 @@ struct PSBTOutput
         }
 
         // Write taproot tree
-        if (m_tap_tree.has_value()) {
+        if (!m_tap_tree.empty()) {
             SerializeToVector(s, PSBT_OUT_TAP_TREE);
             std::vector<unsigned char> value;
             CVectorWriter s_value(s.GetType(), s.GetVersion(), value, 0);
-            const auto& tuples = m_tap_tree->GetTreeTuples();
-            for (const auto& tuple : tuples) {
-                uint8_t depth = std::get<0>(tuple);
-                uint8_t leaf_ver = std::get<1>(tuple);
-                CScript script = std::get<2>(tuple);
+            for (const auto& [depth, leaf_ver, script] : m_tap_tree) {
                 s_value << depth;
                 s_value << leaf_ver;
                 s_value << script;
@@ -858,10 +854,13 @@ struct PSBTOutput
                     } else if (key.size() != 1) {
                         throw std::ios_base::failure("Output Taproot tree key is more than one byte type");
                     }
-                    m_tap_tree.emplace();
                     std::vector<unsigned char> tree_v;
                     s >> tree_v;
                     SpanReader s_tree(s.GetType(), s.GetVersion(), tree_v);
+                    if (s_tree.empty()) {
+                        throw std::ios_base::failure("Output Taproot tree must not be empty");
+                    }
+                    TaprootBuilder builder;
                     while (!s_tree.empty()) {
                         uint8_t depth;
                         uint8_t leaf_ver;
@@ -875,9 +874,10 @@ struct PSBTOutput
                         if ((leaf_ver & ~TAPROOT_LEAF_MASK) != 0) {
                             throw std::ios_base::failure("Output Taproot tree has a leaf with an invalid leaf version");
                         }
-                        m_tap_tree->Add((int)depth, script, (int)leaf_ver, true /* track */);
+                        m_tap_tree.push_back(std::make_tuple(depth, leaf_ver, script));
+                        builder.Add((int)depth, script, (int)leaf_ver, true /* track */);
                     }
-                    if (!m_tap_tree->IsComplete()) {
+                    if (!builder.IsComplete()) {
                         throw std::ios_base::failure("Output Taproot tree is malformed");
                     }
                     break;
@@ -931,11 +931,6 @@ struct PSBTOutput
             }
         }
 
-        // Finalize m_tap_tree so that all of the computed things are computed
-        if (m_tap_tree.has_value() && m_tap_tree->IsComplete() && m_tap_internal_key.IsFullyValid()) {
-            m_tap_tree->Finalize(m_tap_internal_key);
-        }
-
         if (!found_sep) {
             throw std::ios_base::failure("Separator is missing at the end of an output map");
         }
diff --git a/src/rpc/rawtransaction.cpp b/src/rpc/rawtransaction.cpp
index f365de7d0c..d654de1862 100644
--- a/src/rpc/rawtransaction.cpp
+++ b/src/rpc/rawtransaction.cpp
@@ -1241,13 +1241,9 @@ static RPCHelpMan decodepsbt()
         }
 
         // Taproot tree
-        if (output.m_tap_tree.has_value()) {
+        if (!output.m_tap_tree.empty()) {
             UniValue tree(UniValue::VARR);
-            const auto& tuples = output.m_tap_tree->GetTreeTuples();
-            for (const auto& tuple : tuples) {
-                uint8_t depth = std::get<0>(tuple);
-                uint8_t leaf_ver = std::get<1>(tuple);
-                CScript script = std::get<2>(tuple);
+            for (const auto& [depth, leaf_ver, script] : output.m_tap_tree) {
                 UniValue elem(UniValue::VOBJ);
                 elem.pushKV("depth", (int)depth);
                 elem.pushKV("leaf_ver", (int)leaf_ver);
diff --git a/src/script/standard.h b/src/script/standard.h
index 1e6769782a..966a52b2c7 100644
--- a/src/script/standard.h
+++ b/src/script/standard.h
@@ -315,6 +315,8 @@ public:
     TaprootSpendData GetSpendData() const;
     /** Returns a vector of tuples representing the depth, leaf version, and script */
     std::vector<std::tuple<uint8_t, uint8_t, CScript>> GetTreeTuples() const;
+    /** Returns true if there are any tapscripts */
+    bool HasScripts() const { return !m_branch.empty(); }
 };
 
 /** Given a TaprootSpendData and the output key, reconstruct its script tree.