Merge bitcoin/bitcoin#25877: refactor: Do not use CScript for tapleaf scripts until the tapleaf version is known

dee89438b82e94474ebaa31367035f98b4636dac Abstract out ComputeTapbranchHash (Russell O'Connor)
8e3fc9942729716e95907008fcf36eee758c3a6a Do not use CScript for tapleaf scripts until the tapleaf version is known (Russell O'Connor)

Pull request description:

  While BIP-341 calls the contents of tapleaf a "script", only in the case that the tapleaf version is `0xc0` is this script known to be a tapscript.  Otherwise the tapleaf "script" is simply an uninterpreted string of bytes.

  This PR corrects the issue where the type `CScript` is used prior to the tapleaf version being known to be a tapscript.  This prevents `CScript` methods from erroneously being called on non-tapscript data.

  A second commit abstracts out the TapBranch hash computation in the same manner that the TapLeaf computation is already abstracted.  These two abstractions ensure that the TapLeaf and TapBranch tagged hashes are always constructed properly.

ACKs for top commit:
  ajtowns:
    ACK dee89438b82e94474ebaa31367035f98b4636dac
  instagibbs:
    ACK dee89438b82e94474ebaa31367035f98b4636dac
  achow101:
    ACK dee89438b82e94474ebaa31367035f98b4636dac
  sipa:
    ACK dee89438b82e94474ebaa31367035f98b4636dac
  aureleoules:
    reACK dee89438b82e94474ebaa31367035f98b4636dac - I verified that there is no behavior change.

Tree-SHA512: 4a1d37f3e9a1890e7f5eadcf65562688cc451389581fe6e2da0feb2368708edacdd95392578d8afff05270d88fc61dce732d83d1063d84d12cf47b5f4633ec7e

9 files changed, 53 insertions, 43 deletions

diff --git a/src/psbt.h b/src/psbt.h
index 40d69cd454..8fafadcea9 100644
--- a/src/psbt.h
+++ b/src/psbt.h
@@ -206,7 +206,7 @@ struct PSBTInput
     // Taproot fields
     std::vector<unsigned char> m_tap_key_sig;
     std::map<std::pair<XOnlyPubKey, uint256>, std::vector<unsigned char>> m_tap_script_sigs;
-    std::map<std::pair<CScript, int>, std::set<std::vector<unsigned char>, ShortestVectorFirstComparator>> m_tap_scripts;
+    std::map<std::pair<std::vector<unsigned char>, int>, std::set<std::vector<unsigned char>, ShortestVectorFirstComparator>> m_tap_scripts;
     std::map<XOnlyPubKey, std::pair<std::set<uint256>, KeyOriginInfo>> m_tap_bip32_paths;
     XOnlyPubKey m_tap_internal_key;
     uint256 m_tap_merkle_root;
@@ -621,7 +621,7 @@ struct PSBTInput
                     }
                     uint8_t leaf_ver = script_v.back();
                     script_v.pop_back();
-                    const auto leaf_script = std::make_pair(CScript(script_v.begin(), script_v.end()), (int)leaf_ver);
+                    const auto leaf_script = std::make_pair(script_v, (int)leaf_ver);
                     m_tap_scripts[leaf_script].insert(std::vector<unsigned char>(key.begin() + 1, key.end()));
                     break;
                 }
@@ -713,7 +713,7 @@ struct PSBTOutput
     CScript witness_script;
     std::map<CPubKey, KeyOriginInfo> hd_keypaths;
     XOnlyPubKey m_tap_internal_key;
-    std::vector<std::tuple<uint8_t, uint8_t, CScript>> m_tap_tree;
+    std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> 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;
@@ -864,7 +864,7 @@ struct PSBTOutput
                     while (!s_tree.empty()) {
                         uint8_t depth;
                         uint8_t leaf_ver;
-                        CScript script;
+                        std::vector<unsigned char> script;
                         s_tree >> depth;
                         s_tree >> leaf_ver;
                         s_tree >> script;
diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
index 864eb8864f..5815a059ae 100644
--- a/src/script/descriptor.cpp
+++ b/src/script/descriptor.cpp
@@ -1643,7 +1643,7 @@ std::unique_ptr<DescriptorImpl> InferScript(const CScript& script, ParseScriptCo
                 for (const auto& [depth, script, leaf_ver] : *tree) {
                     std::unique_ptr<DescriptorImpl> subdesc;
                     if (leaf_ver == TAPROOT_LEAF_TAPSCRIPT) {
-                        subdesc = InferScript(script, ParseScriptContext::P2TR, provider);
+                        subdesc = InferScript(CScript(script.begin(), script.end()), ParseScriptContext::P2TR, provider);
                     }
                     if (!subdesc) {
                         ok = false;
diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
index a942ff349b..03b157a847 100644
--- a/src/script/interpreter.cpp
+++ b/src/script/interpreter.cpp
@@ -1825,9 +1825,20 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS
     return true;
 }
 
-uint256 ComputeTapleafHash(uint8_t leaf_version, const CScript& script)
+uint256 ComputeTapleafHash(uint8_t leaf_version, Span<const unsigned char> script)
 {
-    return (HashWriter{HASHER_TAPLEAF} << leaf_version << script).GetSHA256();
+    return (HashWriter{HASHER_TAPLEAF} << leaf_version << CompactSizeWriter(script.size()) << script).GetSHA256();
+}
+
+uint256 ComputeTapbranchHash(Span<const unsigned char> a, Span<const unsigned char> b)
+{
+    HashWriter ss_branch{HASHER_TAPBRANCH};
+    if (std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end())) {
+        ss_branch << a << b;
+    } else {
+        ss_branch << b << a;
+    }
+    return ss_branch.GetSHA256();
 }
 
 uint256 ComputeTaprootMerkleRoot(Span<const unsigned char> control, const uint256& tapleaf_hash)
@@ -1839,14 +1850,8 @@ uint256 ComputeTaprootMerkleRoot(Span<const unsigned char> control, const uint25
     const int path_len = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
     uint256 k = tapleaf_hash;
     for (int i = 0; i < path_len; ++i) {
-        HashWriter ss_branch{HASHER_TAPBRANCH};
         Span node{Span{control}.subspan(TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * i, TAPROOT_CONTROL_NODE_SIZE)};
-        if (std::lexicographical_compare(k.begin(), k.end(), node.begin(), node.end())) {
-            ss_branch << k << node;
-        } else {
-            ss_branch << node << k;
-        }
-        k = ss_branch.GetSHA256();
+        k = ComputeTapbranchHash(k, node);
     }
     return k;
 }
@@ -1917,18 +1922,18 @@ static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion,
         } else {
             // Script path spending (stack size is >1 after removing optional annex)
             const valtype& control = SpanPopBack(stack);
-            const valtype& script_bytes = SpanPopBack(stack);
-            exec_script = CScript(script_bytes.begin(), script_bytes.end());
+            const valtype& script = SpanPopBack(stack);
             if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE || ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) {
                 return set_error(serror, SCRIPT_ERR_TAPROOT_WRONG_CONTROL_SIZE);
             }
-            execdata.m_tapleaf_hash = ComputeTapleafHash(control[0] & TAPROOT_LEAF_MASK, exec_script);
+            execdata.m_tapleaf_hash = ComputeTapleafHash(control[0] & TAPROOT_LEAF_MASK, script);
             if (!VerifyTaprootCommitment(control, program, execdata.m_tapleaf_hash)) {
                 return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH);
             }
             execdata.m_tapleaf_hash_init = true;
             if ((control[0] & TAPROOT_LEAF_MASK) == TAPROOT_LEAF_TAPSCRIPT) {
                 // Tapscript (leaf version 0xc0)
+                exec_script = CScript(script.begin(), script.end());
                 execdata.m_validation_weight_left = ::GetSerializeSize(witness.stack, PROTOCOL_VERSION) + VALIDATION_WEIGHT_OFFSET;
                 execdata.m_validation_weight_left_init = true;
                 return ExecuteWitnessScript(stack, exec_script, flags, SigVersion::TAPSCRIPT, checker, execdata, serror);
diff --git a/src/script/interpreter.h b/src/script/interpreter.h
index 42282e6e5c..ac1013302d 100644
--- a/src/script/interpreter.h
+++ b/src/script/interpreter.h
@@ -333,7 +333,10 @@ public:
 };
 
 /** Compute the BIP341 tapleaf hash from leaf version & script. */
-uint256 ComputeTapleafHash(uint8_t leaf_version, const CScript& script);
+uint256 ComputeTapleafHash(uint8_t leaf_version, Span<const unsigned char> script);
+/** Compute the BIP341 tapbranch hash from two branches.
+  * Spans must be 32 bytes each. */
+uint256 ComputeTapbranchHash(Span<const unsigned char> a, Span<const unsigned char> b);
 /** Compute the BIP341 taproot script tree Merkle root from control block and leaf hash.
  *  Requires control block to have valid length (33 + k*32, with k in {0,1,..,128}). */
 uint256 ComputeTaprootMerkleRoot(Span<const unsigned char> control, const uint256& tapleaf_hash);
diff --git a/src/script/sign.cpp b/src/script/sign.cpp
index 1a8558cd9f..d369d4960d 100644
--- a/src/script/sign.cpp
+++ b/src/script/sign.cpp
@@ -169,13 +169,14 @@ static bool CreateTaprootScriptSig(const BaseSignatureCreator& creator, Signatur
     return false;
 }
 
-static bool SignTaprootScript(const SigningProvider& provider, const BaseSignatureCreator& creator, SignatureData& sigdata, int leaf_version, const CScript& script, std::vector<valtype>& result)
+static bool SignTaprootScript(const SigningProvider& provider, const BaseSignatureCreator& creator, SignatureData& sigdata, int leaf_version, Span<const unsigned char> script_bytes, std::vector<valtype>& result)
 {
     // Only BIP342 tapscript signing is supported for now.
     if (leaf_version != TAPROOT_LEAF_TAPSCRIPT) return false;
     SigVersion sigversion = SigVersion::TAPSCRIPT;
 
-    uint256 leaf_hash = (HashWriter{HASHER_TAPLEAF} << uint8_t(leaf_version) << script).GetSHA256();
+    uint256 leaf_hash = ComputeTapleafHash(leaf_version, script_bytes);
+    CScript script = CScript(script_bytes.begin(), script_bytes.end());
 
     // <xonly pubkey> OP_CHECKSIG
     if (script.size() == 34 && script[33] == OP_CHECKSIG && script[0] == 0x20) {
diff --git a/src/script/standard.cpp b/src/script/standard.cpp
index 27b9a5c741..7c4a05b6e6 100644
--- a/src/script/standard.cpp
+++ b/src/script/standard.cpp
@@ -370,12 +370,7 @@ bool IsValidDestination(const CTxDestination& dest) {
         leaf.merkle_branch.push_back(a.hash);
         ret.leaves.emplace_back(std::move(leaf));
     }
-    /* Lexicographically sort a and b's hash, and compute parent hash. */
-    if (a.hash < b.hash) {
-        ret.hash = (HashWriter{HASHER_TAPBRANCH} << a.hash << b.hash).GetSHA256();
-    } else {
-        ret.hash = (HashWriter{HASHER_TAPBRANCH} << b.hash << a.hash).GetSHA256();
-    }
+    ret.hash = ComputeTapbranchHash(a.hash, b.hash);
     return ret;
 }
 
@@ -443,14 +438,14 @@ void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth)
     return branch.size() == 0 || (branch.size() == 1 && branch[0]);
 }
 
-TaprootBuilder& TaprootBuilder::Add(int depth, const CScript& script, int leaf_version, bool track)
+TaprootBuilder& TaprootBuilder::Add(int depth, Span<const unsigned char> script, int leaf_version, bool track)
 {
     assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0);
     if (!IsValid()) return *this;
     /* Construct NodeInfo object with leaf hash and (if track is true) also leaf information. */
     NodeInfo node;
-    node.hash = (HashWriter{HASHER_TAPLEAF} << uint8_t(leaf_version) << script).GetSHA256();
-    if (track) node.leaves.emplace_back(LeafInfo{script, leaf_version, {}});
+    node.hash = ComputeTapleafHash(leaf_version, script);
+    if (track) node.leaves.emplace_back(LeafInfo{std::vector<unsigned char>(script.begin(), script.end()), leaf_version, {}});
     /* Insert into the branch. */
     Insert(std::move(node), depth);
     return *this;
@@ -506,13 +501,13 @@ TaprootSpendData TaprootBuilder::GetSpendData() const
     return spd;
 }
 
-std::optional<std::vector<std::tuple<int, CScript, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output)
+std::optional<std::vector<std::tuple<int, std::vector<unsigned char>, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output)
 {
     // Verify that the output matches the assumed Merkle root and internal key.
     auto tweak = spenddata.internal_key.CreateTapTweak(spenddata.merkle_root.IsNull() ? nullptr : &spenddata.merkle_root);
     if (!tweak || tweak->first != output) return std::nullopt;
     // If the Merkle root is 0, the tree is empty, and we're done.
-    std::vector<std::tuple<int, CScript, int>> ret;
+    std::vector<std::tuple<int, std::vector<unsigned char>, int>> ret;
     if (spenddata.merkle_root.IsNull()) return ret;
 
     /** Data structure to represent the nodes of the tree we're going to build. */
@@ -523,7 +518,7 @@ std::optional<std::vector<std::tuple<int, CScript, int>>> InferTaprootTree(const
         std::unique_ptr<TreeNode> sub[2];
         /** If this is known to be a leaf node, a pointer to the (script, leaf_ver) pair.
          *  nullptr otherwise. */
-        const std::pair<CScript, int>* leaf = nullptr;
+        const std::pair<std::vector<unsigned char>, int>* leaf = nullptr;
         /** Whether or not this node has been explored (is known to be a leaf, or known to have children). */
         bool explored = false;
         /** Whether or not this node is an inner node (unknown until explored = true). */
@@ -607,7 +602,7 @@ std::optional<std::vector<std::tuple<int, CScript, int>>> InferTaprootTree(const
             node.done = true;
             stack.pop_back();
         } else if (node.sub[0]->done && !node.sub[1]->done && !node.sub[1]->explored && !node.sub[1]->hash.IsNull() &&
-                   (HashWriter{HASHER_TAPBRANCH} << node.sub[1]->hash << node.sub[1]->hash).GetSHA256() == node.hash) {
+                   ComputeTapbranchHash(node.sub[1]->hash, node.sub[1]->hash) == node.hash) {
             // Whenever there are nodes with two identical subtrees under it, we run into a problem:
             // the control blocks for the leaves underneath those will be identical as well, and thus
             // they will all be matched to the same path in the tree. The result is that at the location
@@ -641,10 +636,10 @@ std::optional<std::vector<std::tuple<int, CScript, int>>> InferTaprootTree(const
     return ret;
 }
 
-std::vector<std::tuple<uint8_t, uint8_t, CScript>> TaprootBuilder::GetTreeTuples() const
+std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> TaprootBuilder::GetTreeTuples() const
 {
     assert(IsComplete());
-    std::vector<std::tuple<uint8_t, uint8_t, CScript>> tuples;
+    std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> tuples;
     if (m_branch.size()) {
         const auto& leaves = m_branch[0]->leaves;
         for (const auto& leaf : leaves) {
diff --git a/src/script/standard.h b/src/script/standard.h
index f08258af4f..18cf5c8c88 100644
--- a/src/script/standard.h
+++ b/src/script/standard.h
@@ -217,7 +217,7 @@ struct TaprootSpendData
      *  inference can reconstruct the full tree. Within each set, the control
      *  blocks are sorted by size, so that the signing logic can easily
      *  prefer the cheapest one. */
-    std::map<std::pair<CScript, int>, std::set<std::vector<unsigned char>, ShortestVectorFirstComparator>> scripts;
+    std::map<std::pair<std::vector<unsigned char>, int>, std::set<std::vector<unsigned char>, ShortestVectorFirstComparator>> scripts;
     /** Merge other TaprootSpendData (for the same scriptPubKey) into this. */
     void Merge(TaprootSpendData other);
 };
@@ -229,7 +229,7 @@ private:
     /** Information about a tracked leaf in the Merkle tree. */
     struct LeafInfo
     {
-        CScript script;                      //!< The script.
+        std::vector<unsigned char> script;   //!< The script.
         int leaf_version;                    //!< The leaf version for that script.
         std::vector<uint256> merkle_branch;  //!< The hashing partners above this leaf.
     };
@@ -296,7 +296,7 @@ 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. If track is true, it will be included in
      *  the GetSpendData() output. */
-    TaprootBuilder& Add(int depth, const CScript& script, int leaf_version, bool track = true);
+    TaprootBuilder& Add(int depth, Span<const unsigned char> script, int leaf_version, bool track = true);
     /** 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.
@@ -314,7 +314,7 @@ public:
     /** Compute spending data (after Finalize()). */
     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;
+    std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> GetTreeTuples() const;
     /** Returns true if there are any tapscripts */
     bool HasScripts() const { return !m_branch.empty(); }
 };
@@ -325,6 +325,6 @@ public:
  * std::nullopt is returned. Otherwise, a vector of (depth, script, leaf_ver) tuples is
  * returned, corresponding to a depth-first traversal of the script tree.
  */
-std::optional<std::vector<std::tuple<int, CScript, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output);
+std::optional<std::vector<std::tuple<int, std::vector<unsigned char>, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output);
 
 #endif // BITCOIN_SCRIPT_STANDARD_H
diff --git a/src/test/script_standard_tests.cpp b/src/test/script_standard_tests.cpp
index 88df34ffe6..7bebadf224 100644
--- a/src/test/script_standard_tests.cpp
+++ b/src/test/script_standard_tests.cpp
@@ -400,12 +400,11 @@ BOOST_AUTO_TEST_CASE(bip341_spk_test_vectors)
 
     for (const auto& vec : vectors.getValues()) {
         TaprootBuilder spktest;
-        std::map<std::pair<CScript, int>, int> scriptposes;
+        std::map<std::pair<std::vector<unsigned char>, int>, int> scriptposes;
         std::function<void (const UniValue&, int)> parse_tree = [&](const UniValue& node, int depth) {
             if (node.isNull()) return;
             if (node.isObject()) {
-                auto script_bytes = ParseHex(node["script"].get_str());
-                CScript script(script_bytes.begin(), script_bytes.end());
+                auto script = ParseHex(node["script"].get_str());
                 int idx = node["id"].getInt<int>();
                 int leaf_version = node["leafVersion"].getInt<int>();
                 scriptposes[{script, leaf_version}] = idx;
diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp
index 472cba2aac..300760282b 100644
--- a/src/test/script_tests.cpp
+++ b/src/test/script_tests.cpp
@@ -1817,7 +1817,14 @@ BOOST_AUTO_TEST_CASE(bip341_keypath_test_vectors)
         }
 
     }
+}
 
+BOOST_AUTO_TEST_CASE(compute_tapbranch)
+{
+    uint256 hash1 = uint256S("8ad69ec7cf41c2a4001fd1f738bf1e505ce2277acdcaa63fe4765192497f47a7");
+    uint256 hash2 = uint256S("f224a923cd0021ab202ab139cc56802ddb92dcfc172b9212261a539df79a112a");
+    uint256 result = uint256S("a64c5b7b943315f9b805d7a7296bedfcfd08919270a1f7a1466e98f8693d8cd9");
+    BOOST_CHECK_EQUAL(ComputeTapbranchHash(hash1, hash2), result);
 }
 
 BOOST_AUTO_TEST_SUITE_END()