From 8e3fc9942729716e95907008fcf36eee758c3a6a Mon Sep 17 00:00:00 2001 From: Russell O'Connor Date: Fri, 19 Aug 2022 10:40:28 -0400 Subject: Do not use CScript for tapleaf scripts until the tapleaf version is known Prevents use of CScript methods until the tapleaf is known to be a tapscript. --- src/psbt.h | 8 ++++---- src/script/descriptor.cpp | 2 +- src/script/interpreter.cpp | 10 +++++----- src/script/interpreter.h | 2 +- src/script/sign.cpp | 5 +++-- src/script/standard.cpp | 16 ++++++++-------- src/script/standard.h | 10 +++++----- src/test/script_standard_tests.cpp | 5 ++--- 8 files changed, 29 insertions(+), 29 deletions(-) diff --git a/src/psbt.h b/src/psbt.h index 37bf142366..da75a60412 100644 --- a/src/psbt.h +++ b/src/psbt.h @@ -206,7 +206,7 @@ struct PSBTInput // Taproot fields std::vector m_tap_key_sig; std::map, std::vector> m_tap_script_sigs; - std::map, std::set, ShortestVectorFirstComparator>> m_tap_scripts; + std::map, int>, std::set, ShortestVectorFirstComparator>> m_tap_scripts; std::map, 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(key.begin() + 1, key.end())); break; } @@ -713,7 +713,7 @@ struct PSBTOutput CScript witness_script; std::map hd_keypaths; XOnlyPubKey m_tap_internal_key; - std::vector> m_tap_tree; + std::vector>> m_tap_tree; std::map, KeyOriginInfo>> m_tap_bip32_paths; std::map, std::vector> unknown; std::set m_proprietary; @@ -864,7 +864,7 @@ struct PSBTOutput while (!s_tree.empty()) { uint8_t depth; uint8_t leaf_ver; - CScript script; + std::vector 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 InferScript(const CScript& script, ParseScriptCo for (const auto& [depth, script, leaf_ver] : *tree) { std::unique_ptr 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 38bb11aad4..5148265b9c 100644 --- a/src/script/interpreter.cpp +++ b/src/script/interpreter.cpp @@ -1825,9 +1825,9 @@ static bool ExecuteWitnessScript(const Span& stack_span, const CS return true; } -uint256 ComputeTapleafHash(uint8_t leaf_version, const CScript& script) +uint256 ComputeTapleafHash(uint8_t leaf_version, Span script) { - return (HashWriter{HASHER_TAPLEAF} << leaf_version << script).GetSHA256(); + return (HashWriter{HASHER_TAPLEAF} << leaf_version << CompactSizeWriter(script.size()) << script).GetSHA256(); } uint256 ComputeTaprootMerkleRoot(Span control, const uint256& tapleaf_hash) @@ -1917,18 +1917,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 ba910cc945..5530d824f2 100644 --- a/src/script/interpreter.h +++ b/src/script/interpreter.h @@ -333,7 +333,7 @@ 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 script); /** 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 control, const uint256& tapleaf_hash); diff --git a/src/script/sign.cpp b/src/script/sign.cpp index 0d74a661a5..53377560e8 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& result) +static bool SignTaprootScript(const SigningProvider& provider, const BaseSignatureCreator& creator, SignatureData& sigdata, int leaf_version, Span script_bytes, std::vector& 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()); // 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 6101738061..b5ba542ce0 100644 --- a/src/script/standard.cpp +++ b/src/script/standard.cpp @@ -443,14 +443,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 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(script.begin(), script.end()), leaf_version, {}}); /* Insert into the branch. */ Insert(std::move(node), depth); return *this; @@ -506,13 +506,13 @@ TaprootSpendData TaprootBuilder::GetSpendData() const return spd; } -std::optional>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output) +std::optional, 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> ret; + std::vector, 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 +523,7 @@ std::optional>> InferTaprootTree(const std::unique_ptr sub[2]; /** If this is known to be a leaf node, a pointer to the (script, leaf_ver) pair. * nullptr otherwise. */ - const std::pair* leaf = nullptr; + const std::pair, 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). */ @@ -641,10 +641,10 @@ std::optional>> InferTaprootTree(const return ret; } -std::vector> TaprootBuilder::GetTreeTuples() const +std::vector>> TaprootBuilder::GetTreeTuples() const { assert(IsComplete()); - std::vector> tuples; + std::vector>> 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 966a52b2c7..60b5bd38e7 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::set, ShortestVectorFirstComparator>> scripts; + std::map, int>, std::set, 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 script; //!< The script. int leaf_version; //!< The leaf version for that script. std::vector 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 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> GetTreeTuples() const; + std::vector>> 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>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output); +std::optional, 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 25e47c0fb0..13a1f0f9eb 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, int> scriptposes; + std::map, int>, int> scriptposes; std::function 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 leaf_version = node["leafVersion"].getInt(); scriptposes[{script, leaf_version}] = idx; -- cgit v1.2.3 From dee89438b82e94474ebaa31367035f98b4636dac Mon Sep 17 00:00:00 2001 From: Russell O'Connor Date: Fri, 19 Aug 2022 11:59:18 -0400 Subject: Abstract out ComputeTapbranchHash --- src/script/interpreter.cpp | 19 ++++++++++++------- src/script/interpreter.h | 3 +++ src/script/standard.cpp | 9 ++------- src/test/script_tests.cpp | 7 +++++++ 4 files changed, 24 insertions(+), 14 deletions(-) diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp index 5148265b9c..c06d0370c9 100644 --- a/src/script/interpreter.cpp +++ b/src/script/interpreter.cpp @@ -1830,6 +1830,17 @@ uint256 ComputeTapleafHash(uint8_t leaf_version, Span scrip return (HashWriter{HASHER_TAPLEAF} << leaf_version << CompactSizeWriter(script.size()) << script).GetSHA256(); } +uint256 ComputeTapbranchHash(Span a, Span 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 control, const uint256& tapleaf_hash) { assert(control.size() >= TAPROOT_CONTROL_BASE_SIZE); @@ -1839,14 +1850,8 @@ uint256 ComputeTaprootMerkleRoot(Span 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; } diff --git a/src/script/interpreter.h b/src/script/interpreter.h index 5530d824f2..790098f9df 100644 --- a/src/script/interpreter.h +++ b/src/script/interpreter.h @@ -334,6 +334,9 @@ public: /** Compute the BIP341 tapleaf hash from leaf version & script. */ uint256 ComputeTapleafHash(uint8_t leaf_version, Span script); +/** Compute the BIP341 tapbranch hash from two branches. + * Spans must be 32 bytes each. */ +uint256 ComputeTapbranchHash(Span a, Span 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 control, const uint256& tapleaf_hash); diff --git a/src/script/standard.cpp b/src/script/standard.cpp index b5ba542ce0..2b7c120eaf 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; } @@ -607,7 +602,7 @@ std::optional, int>>> Inf 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 diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp index 935194057c..e74678394f 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() -- cgit v1.2.3