diff options
| -rw-r--r-- | src/psbt.h | 8 | ||||
| -rw-r--r-- | src/script/descriptor.cpp | 2 | ||||
| -rw-r--r-- | src/script/interpreter.cpp | 29 | ||||
| -rw-r--r-- | src/script/interpreter.h | 5 | ||||
| -rw-r--r-- | src/script/sign.cpp | 5 | ||||
| -rw-r--r-- | src/script/standard.cpp | 25 | ||||
| -rw-r--r-- | src/script/standard.h | 10 | ||||
| -rw-r--r-- | src/test/script_standard_tests.cpp | 5 | ||||
| -rw-r--r-- | src/test/script_tests.cpp | 7 |
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() |