Branch data Line data Source code
# 1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto
# 2 : : // Copyright (c) 2009-2021 The Bitcoin Core developers
# 3 : : // Distributed under the MIT software license, see the accompanying
# 4 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
# 5 : :
# 6 : : #include <script/standard.h>
# 7 : :
# 8 : : #include <crypto/sha256.h>
# 9 : : #include <hash.h>
# 10 : : #include <pubkey.h>
# 11 : : #include <script/interpreter.h>
# 12 : : #include <script/script.h>
# 13 : : #include <util/strencodings.h>
# 14 : :
# 15 : : #include <string>
# 16 : :
# 17 : : typedef std::vector<unsigned char> valtype;
# 18 : :
# 19 : : bool fAcceptDatacarrier = DEFAULT_ACCEPT_DATACARRIER;
# 20 : : unsigned nMaxDatacarrierBytes = MAX_OP_RETURN_RELAY;
# 21 : :
# 22 : 1017760 : CScriptID::CScriptID(const CScript& in) : BaseHash(Hash160(in)) {}
# 23 : 3524 : CScriptID::CScriptID(const ScriptHash& in) : BaseHash(static_cast<uint160>(in)) {}
# 24 : :
# 25 : 132725 : ScriptHash::ScriptHash(const CScript& in) : BaseHash(Hash160(in)) {}
# 26 : 1437 : ScriptHash::ScriptHash(const CScriptID& in) : BaseHash(static_cast<uint160>(in)) {}
# 27 : :
# 28 : 26815 : PKHash::PKHash(const CPubKey& pubkey) : BaseHash(pubkey.GetID()) {}
# 29 : 148868 : PKHash::PKHash(const CKeyID& pubkey_id) : BaseHash(pubkey_id) {}
# 30 : :
# 31 : 12501 : WitnessV0KeyHash::WitnessV0KeyHash(const CPubKey& pubkey) : BaseHash(pubkey.GetID()) {}
# 32 : 1657 : WitnessV0KeyHash::WitnessV0KeyHash(const PKHash& pubkey_hash) : BaseHash(static_cast<uint160>(pubkey_hash)) {}
# 33 : :
# 34 : : CKeyID ToKeyID(const PKHash& key_hash)
# 35 : 652 : {
# 36 : 652 : return CKeyID{static_cast<uint160>(key_hash)};
# 37 : 652 : }
# 38 : :
# 39 : : CKeyID ToKeyID(const WitnessV0KeyHash& key_hash)
# 40 : 1677 : {
# 41 : 1677 : return CKeyID{static_cast<uint160>(key_hash)};
# 42 : 1677 : }
# 43 : :
# 44 : : WitnessV0ScriptHash::WitnessV0ScriptHash(const CScript& in)
# 45 : 21817 : {
# 46 : 21817 : CSHA256().Write(in.data(), in.size()).Finalize(begin());
# 47 : 21817 : }
# 48 : :
# 49 : : std::string GetTxnOutputType(TxoutType t)
# 50 : 84551 : {
# 51 [ - + ]: 84551 : switch (t) {
# 52 [ + + ]: 5760 : case TxoutType::NONSTANDARD: return "nonstandard";
# 53 [ + + ]: 6056 : case TxoutType::PUBKEY: return "pubkey";
# 54 [ + + ]: 6199 : case TxoutType::PUBKEYHASH: return "pubkeyhash";
# 55 [ + + ]: 6192 : case TxoutType::SCRIPTHASH: return "scripthash";
# 56 [ + + ]: 5930 : case TxoutType::MULTISIG: return "multisig";
# 57 [ + + ]: 20597 : case TxoutType::NULL_DATA: return "nulldata";
# 58 [ + + ]: 12440 : case TxoutType::WITNESS_V0_KEYHASH: return "witness_v0_keyhash";
# 59 [ + + ]: 5879 : case TxoutType::WITNESS_V0_SCRIPTHASH: return "witness_v0_scripthash";
# 60 [ + + ]: 9793 : case TxoutType::WITNESS_V1_TAPROOT: return "witness_v1_taproot";
# 61 [ + + ]: 5705 : case TxoutType::WITNESS_UNKNOWN: return "witness_unknown";
# 62 : 84551 : } // no default case, so the compiler can warn about missing cases
# 63 : 0 : assert(false);
# 64 : 0 : }
# 65 : :
# 66 : : static bool MatchPayToPubkey(const CScript& script, valtype& pubkey)
# 67 : 2192968 : {
# 68 [ + + ][ + - ]: 2192968 : if (script.size() == CPubKey::SIZE + 2 && script[0] == CPubKey::SIZE && script.back() == OP_CHECKSIG) {
# [ + - ]
# 69 : 2257 : pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::SIZE + 1);
# 70 : 2257 : return CPubKey::ValidSize(pubkey);
# 71 : 2257 : }
# 72 [ + + ][ + - ]: 2190711 : if (script.size() == CPubKey::COMPRESSED_SIZE + 2 && script[0] == CPubKey::COMPRESSED_SIZE && script.back() == OP_CHECKSIG) {
# [ + - ]
# 73 : 43163 : pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::COMPRESSED_SIZE + 1);
# 74 : 43163 : return CPubKey::ValidSize(pubkey);
# 75 : 43163 : }
# 76 : 2147548 : return false;
# 77 : 2190711 : }
# 78 : :
# 79 : : static bool MatchPayToPubkeyHash(const CScript& script, valtype& pubkeyhash)
# 80 : 2147548 : {
# 81 [ + + ][ + - ]: 2147548 : if (script.size() == 25 && script[0] == OP_DUP && script[1] == OP_HASH160 && script[2] == 20 && script[23] == OP_EQUALVERIFY && script[24] == OP_CHECKSIG) {
# [ + - ][ + - ]
# [ + - ][ + - ]
# 82 : 2122178 : pubkeyhash = valtype(script.begin () + 3, script.begin() + 23);
# 83 : 2122178 : return true;
# 84 : 2122178 : }
# 85 : 25370 : return false;
# 86 : 2147548 : }
# 87 : :
# 88 : : /** Test for "small positive integer" script opcodes - OP_1 through OP_16. */
# 89 : : static constexpr bool IsSmallInteger(opcodetype opcode)
# 90 : 32037 : {
# 91 [ + + ][ + + ]: 32037 : return opcode >= OP_1 && opcode <= OP_16;
# 92 : 32037 : }
# 93 : :
# 94 : : /** Retrieve a minimally-encoded number in range [min,max] from an (opcode, data) pair,
# 95 : : * whether it's OP_n or through a push. */
# 96 : : static std::optional<int> GetScriptNumber(opcodetype opcode, valtype data, int min, int max)
# 97 : 32037 : {
# 98 : 32037 : int count;
# 99 [ + + ]: 32037 : if (IsSmallInteger(opcode)) {
# 100 : 31809 : count = CScript::DecodeOP_N(opcode);
# 101 [ + + ]: 31809 : } else if (IsPushdataOp(opcode)) {
# 102 [ + + ]: 220 : if (!CheckMinimalPush(data, opcode)) return {};
# 103 : 212 : try {
# 104 : 212 : count = CScriptNum(data, /* fRequireMinimal = */ true).getint();
# 105 : 212 : } catch (const scriptnum_error&) {
# 106 : 0 : return {};
# 107 : 0 : }
# 108 : 212 : } else {
# 109 : 8 : return {};
# 110 : 8 : }
# 111 [ + + ][ - + ]: 32021 : if (count < min || count > max) return {};
# 112 : 32017 : return count;
# 113 : 32021 : }
# 114 : :
# 115 : : static bool MatchMultisig(const CScript& script, int& required_sigs, std::vector<valtype>& pubkeys)
# 116 : 25370 : {
# 117 : 25370 : opcodetype opcode;
# 118 : 25370 : valtype data;
# 119 : :
# 120 : 25370 : CScript::const_iterator it = script.begin();
# 121 [ + + ][ + + ]: 25370 : if (script.size() < 1 || script.back() != OP_CHECKMULTISIG) return false;
# 122 : :
# 123 [ - + ]: 15953 : if (!script.GetOp(it, opcode, data)) return false;
# 124 : 15953 : auto req_sigs = GetScriptNumber(opcode, data, 1, MAX_PUBKEYS_PER_MULTISIG);
# 125 [ + + ]: 15953 : if (!req_sigs) return false;
# 126 : 15945 : required_sigs = *req_sigs;
# 127 [ + - ][ + + ]: 49404 : while (script.GetOp(it, opcode, data) && CPubKey::ValidSize(data)) {
# 128 : 33459 : pubkeys.emplace_back(std::move(data));
# 129 : 33459 : }
# 130 : 15945 : auto num_keys = GetScriptNumber(opcode, data, required_sigs, MAX_PUBKEYS_PER_MULTISIG);
# 131 [ + + ]: 15945 : if (!num_keys) return false;
# 132 [ + + ]: 15933 : if (pubkeys.size() != static_cast<unsigned long>(*num_keys)) return false;
# 133 : :
# 134 : 15927 : return (it + 1 == script.end());
# 135 : 15933 : }
# 136 : :
# 137 : : std::optional<std::pair<int, std::vector<Span<const unsigned char>>>> MatchMultiA(const CScript& script)
# 138 : 139 : {
# 139 : 139 : std::vector<Span<const unsigned char>> keyspans;
# 140 : :
# 141 : : // Redundant, but very fast and selective test.
# 142 [ - + ][ - + ]: 139 : if (script.size() == 0 || script[0] != 32 || script.back() != OP_NUMEQUAL) return {};
# [ - + ]
# 143 : :
# 144 : : // Parse keys
# 145 : 139 : auto it = script.begin();
# 146 [ + + ]: 20397 : while (script.end() - it >= 34) {
# 147 [ - + ]: 20258 : if (*it != 32) return {};
# 148 : 20258 : ++it;
# 149 : 20258 : keyspans.emplace_back(&*it, 32);
# 150 : 20258 : it += 32;
# 151 [ - + ][ + + ]: 20258 : if (*it != (keyspans.size() == 1 ? OP_CHECKSIG : OP_CHECKSIGADD)) return {};
# 152 : 20258 : ++it;
# 153 : 20258 : }
# 154 [ - + ][ - + ]: 139 : if (keyspans.size() == 0 || keyspans.size() > MAX_PUBKEYS_PER_MULTI_A) return {};
# 155 : :
# 156 : : // Parse threshold.
# 157 : 139 : opcodetype opcode;
# 158 : 139 : std::vector<unsigned char> data;
# 159 [ - + ]: 139 : if (!script.GetOp(it, opcode, data)) return {};
# 160 [ - + ]: 139 : if (it == script.end()) return {};
# 161 [ - + ]: 139 : if (*it != OP_NUMEQUAL) return {};
# 162 : 139 : ++it;
# 163 [ - + ]: 139 : if (it != script.end()) return {};
# 164 : 139 : auto threshold = GetScriptNumber(opcode, data, 1, (int)keyspans.size());
# 165 [ - + ]: 139 : if (!threshold) return {};
# 166 : :
# 167 : : // Construct result.
# 168 : 139 : return std::pair{*threshold, std::move(keyspans)};
# 169 : 139 : }
# 170 : :
# 171 : : TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned char>>& vSolutionsRet)
# 172 : 4746762 : {
# 173 : 4746762 : vSolutionsRet.clear();
# 174 : :
# 175 : : // Shortcut for pay-to-script-hash, which are more constrained than the other types:
# 176 : : // it is always OP_HASH160 20 [20 byte hash] OP_EQUAL
# 177 [ + + ]: 4746762 : if (scriptPubKey.IsPayToScriptHash())
# 178 : 147382 : {
# 179 : 147382 : std::vector<unsigned char> hashBytes(scriptPubKey.begin()+2, scriptPubKey.begin()+22);
# 180 : 147382 : vSolutionsRet.push_back(hashBytes);
# 181 : 147382 : return TxoutType::SCRIPTHASH;
# 182 : 147382 : }
# 183 : :
# 184 : 4599380 : int witnessversion;
# 185 : 4599380 : std::vector<unsigned char> witnessprogram;
# 186 [ + + ]: 4599380 : if (scriptPubKey.IsWitnessProgram(witnessversion, witnessprogram)) {
# 187 [ + + ][ + + ]: 2061916 : if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_KEYHASH_SIZE) {
# 188 : 1908073 : vSolutionsRet.push_back(std::move(witnessprogram));
# 189 : 1908073 : return TxoutType::WITNESS_V0_KEYHASH;
# 190 : 1908073 : }
# 191 [ + + ][ + + ]: 153843 : if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_SCRIPTHASH_SIZE) {
# 192 : 38387 : vSolutionsRet.push_back(std::move(witnessprogram));
# 193 : 38387 : return TxoutType::WITNESS_V0_SCRIPTHASH;
# 194 : 38387 : }
# 195 [ + + ][ + + ]: 115456 : if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE) {
# 196 : 114143 : vSolutionsRet.push_back(std::move(witnessprogram));
# 197 : 114143 : return TxoutType::WITNESS_V1_TAPROOT;
# 198 : 114143 : }
# 199 [ + + ]: 1313 : if (witnessversion != 0) {
# 200 : 1310 : vSolutionsRet.push_back(std::vector<unsigned char>{(unsigned char)witnessversion});
# 201 : 1310 : vSolutionsRet.push_back(std::move(witnessprogram));
# 202 : 1310 : return TxoutType::WITNESS_UNKNOWN;
# 203 : 1310 : }
# 204 : 3 : return TxoutType::NONSTANDARD;
# 205 : 1313 : }
# 206 : :
# 207 : : // Provably prunable, data-carrying output
# 208 : : //
# 209 : : // So long as script passes the IsUnspendable() test and all but the first
# 210 : : // byte passes the IsPushOnly() test we don't care what exactly is in the
# 211 : : // script.
# 212 [ + + ][ + + ]: 2537464 : if (scriptPubKey.size() >= 1 && scriptPubKey[0] == OP_RETURN && scriptPubKey.IsPushOnly(scriptPubKey.begin()+1)) {
# [ + + ][ + + ]
# 213 : 344505 : return TxoutType::NULL_DATA;
# 214 : 344505 : }
# 215 : :
# 216 : 2192959 : std::vector<unsigned char> data;
# 217 [ + + ]: 2192959 : if (MatchPayToPubkey(scriptPubKey, data)) {
# 218 : 45420 : vSolutionsRet.push_back(std::move(data));
# 219 : 45420 : return TxoutType::PUBKEY;
# 220 : 45420 : }
# 221 : :
# 222 [ + + ]: 2147539 : if (MatchPayToPubkeyHash(scriptPubKey, data)) {
# 223 : 2122178 : vSolutionsRet.push_back(std::move(data));
# 224 : 2122178 : return TxoutType::PUBKEYHASH;
# 225 : 2122178 : }
# 226 : :
# 227 : 25361 : int required;
# 228 : 25361 : std::vector<std::vector<unsigned char>> keys;
# 229 [ + + ]: 25361 : if (MatchMultisig(scriptPubKey, required, keys)) {
# 230 : 15927 : vSolutionsRet.push_back({static_cast<unsigned char>(required)}); // safe as required is in range 1..20
# 231 : 15927 : vSolutionsRet.insert(vSolutionsRet.end(), keys.begin(), keys.end());
# 232 : 15927 : vSolutionsRet.push_back({static_cast<unsigned char>(keys.size())}); // safe as size is in range 1..20
# 233 : 15927 : return TxoutType::MULTISIG;
# 234 : 15927 : }
# 235 : :
# 236 : 9434 : vSolutionsRet.clear();
# 237 : 9434 : return TxoutType::NONSTANDARD;
# 238 : 25361 : }
# 239 : :
# 240 : : bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
# 241 : 607614 : {
# 242 : 607614 : std::vector<valtype> vSolutions;
# 243 : 607614 : TxoutType whichType = Solver(scriptPubKey, vSolutions);
# 244 : :
# 245 [ - + ]: 607614 : switch (whichType) {
# 246 [ + + ]: 2086 : case TxoutType::PUBKEY: {
# 247 : 2086 : CPubKey pubKey(vSolutions[0]);
# 248 [ - + ]: 2086 : if (!pubKey.IsValid())
# 249 : 0 : return false;
# 250 : :
# 251 : 2086 : addressRet = PKHash(pubKey);
# 252 : 2086 : return true;
# 253 : 2086 : }
# 254 [ + + ]: 130994 : case TxoutType::PUBKEYHASH: {
# 255 : 130994 : addressRet = PKHash(uint160(vSolutions[0]));
# 256 : 130994 : return true;
# 257 : 2086 : }
# 258 [ + + ]: 15503 : case TxoutType::SCRIPTHASH: {
# 259 : 15503 : addressRet = ScriptHash(uint160(vSolutions[0]));
# 260 : 15503 : return true;
# 261 : 2086 : }
# 262 [ + + ]: 327780 : case TxoutType::WITNESS_V0_KEYHASH: {
# 263 : 327780 : WitnessV0KeyHash hash;
# 264 : 327780 : std::copy(vSolutions[0].begin(), vSolutions[0].end(), hash.begin());
# 265 : 327780 : addressRet = hash;
# 266 : 327780 : return true;
# 267 : 2086 : }
# 268 [ + + ]: 1766 : case TxoutType::WITNESS_V0_SCRIPTHASH: {
# 269 : 1766 : WitnessV0ScriptHash hash;
# 270 : 1766 : std::copy(vSolutions[0].begin(), vSolutions[0].end(), hash.begin());
# 271 : 1766 : addressRet = hash;
# 272 : 1766 : return true;
# 273 : 2086 : }
# 274 [ + + ]: 8738 : case TxoutType::WITNESS_V1_TAPROOT: {
# 275 : 8738 : WitnessV1Taproot tap;
# 276 : 8738 : std::copy(vSolutions[0].begin(), vSolutions[0].end(), tap.begin());
# 277 : 8738 : addressRet = tap;
# 278 : 8738 : return true;
# 279 : 2086 : }
# 280 [ + + ]: 28 : case TxoutType::WITNESS_UNKNOWN: {
# 281 : 28 : WitnessUnknown unk;
# 282 : 28 : unk.version = vSolutions[0][0];
# 283 : 28 : std::copy(vSolutions[1].begin(), vSolutions[1].end(), unk.program);
# 284 : 28 : unk.length = vSolutions[1].size();
# 285 : 28 : addressRet = unk;
# 286 : 28 : return true;
# 287 : 2086 : }
# 288 [ + + ]: 377 : case TxoutType::MULTISIG:
# 289 [ + + ]: 120500 : case TxoutType::NULL_DATA:
# 290 [ + + ]: 120719 : case TxoutType::NONSTANDARD:
# 291 : 120719 : return false;
# 292 : 607614 : } // no default case, so the compiler can warn about missing cases
# 293 : 0 : assert(false);
# 294 : 0 : }
# 295 : :
# 296 : : namespace {
# 297 : : class CScriptVisitor
# 298 : : {
# 299 : : public:
# 300 : : CScript operator()(const CNoDestination& dest) const
# 301 : 33 : {
# 302 : 33 : return CScript();
# 303 : 33 : }
# 304 : :
# 305 : : CScript operator()(const PKHash& keyID) const
# 306 : 693251 : {
# 307 : 693251 : return CScript() << OP_DUP << OP_HASH160 << ToByteVector(keyID) << OP_EQUALVERIFY << OP_CHECKSIG;
# 308 : 693251 : }
# 309 : :
# 310 : : CScript operator()(const ScriptHash& scriptID) const
# 311 : 133651 : {
# 312 : 133651 : return CScript() << OP_HASH160 << ToByteVector(scriptID) << OP_EQUAL;
# 313 : 133651 : }
# 314 : :
# 315 : : CScript operator()(const WitnessV0KeyHash& id) const
# 316 : 540169 : {
# 317 : 540169 : return CScript() << OP_0 << ToByteVector(id);
# 318 : 540169 : }
# 319 : :
# 320 : : CScript operator()(const WitnessV0ScriptHash& id) const
# 321 : 23095 : {
# 322 : 23095 : return CScript() << OP_0 << ToByteVector(id);
# 323 : 23095 : }
# 324 : :
# 325 : : CScript operator()(const WitnessV1Taproot& tap) const
# 326 : 66104 : {
# 327 : 66104 : return CScript() << OP_1 << ToByteVector(tap);
# 328 : 66104 : }
# 329 : :
# 330 : : CScript operator()(const WitnessUnknown& id) const
# 331 : 50 : {
# 332 : 50 : return CScript() << CScript::EncodeOP_N(id.version) << std::vector<unsigned char>(id.program, id.program + id.length);
# 333 : 50 : }
# 334 : : };
# 335 : : } // namespace
# 336 : :
# 337 : : CScript GetScriptForDestination(const CTxDestination& dest)
# 338 : 1456353 : {
# 339 : 1456353 : return std::visit(CScriptVisitor(), dest);
# 340 : 1456353 : }
# 341 : :
# 342 : : CScript GetScriptForRawPubKey(const CPubKey& pubKey)
# 343 : 99084 : {
# 344 : 99084 : return CScript() << std::vector<unsigned char>(pubKey.begin(), pubKey.end()) << OP_CHECKSIG;
# 345 : 99084 : }
# 346 : :
# 347 : : CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys)
# 348 : 24443 : {
# 349 : 24443 : CScript script;
# 350 : :
# 351 : 24443 : script << nRequired;
# 352 [ + + ]: 24443 : for (const CPubKey& key : keys)
# 353 : 127116 : script << ToByteVector(key);
# 354 : 24443 : script << keys.size() << OP_CHECKMULTISIG;
# 355 : :
# 356 : 24443 : return script;
# 357 : 24443 : }
# 358 : :
# 359 : 31202 : bool IsValidDestination(const CTxDestination& dest) {
# 360 : 31202 : return dest.index() != 0;
# 361 : 31202 : }
# 362 : :
# 363 : : /*static*/ TaprootBuilder::NodeInfo TaprootBuilder::Combine(NodeInfo&& a, NodeInfo&& b)
# 364 : 23275 : {
# 365 : 23275 : NodeInfo ret;
# 366 : : /* Iterate over all tracked leaves in a, add b's hash to their Merkle branch, and move them to ret. */
# 367 [ + + ]: 42918 : for (auto& leaf : a.leaves) {
# 368 : 42918 : leaf.merkle_branch.push_back(b.hash);
# 369 : 42918 : ret.leaves.emplace_back(std::move(leaf));
# 370 : 42918 : }
# 371 : : /* Iterate over all tracked leaves in b, add a's hash to their Merkle branch, and move them to ret. */
# 372 [ + + ]: 29763 : for (auto& leaf : b.leaves) {
# 373 : 29763 : leaf.merkle_branch.push_back(a.hash);
# 374 : 29763 : ret.leaves.emplace_back(std::move(leaf));
# 375 : 29763 : }
# 376 : : /* Lexicographically sort a and b's hash, and compute parent hash. */
# 377 [ + + ]: 23275 : if (a.hash < b.hash) {
# 378 : 5220 : ret.hash = (CHashWriter(HASHER_TAPBRANCH) << a.hash << b.hash).GetSHA256();
# 379 : 18055 : } else {
# 380 : 18055 : ret.hash = (CHashWriter(HASHER_TAPBRANCH) << b.hash << a.hash).GetSHA256();
# 381 : 18055 : }
# 382 : 23275 : return ret;
# 383 : 23275 : }
# 384 : :
# 385 : : void TaprootSpendData::Merge(TaprootSpendData other)
# 386 : 64051 : {
# 387 : : // TODO: figure out how to better deal with conflicting information
# 388 : : // being merged.
# 389 [ + - ][ + - ]: 64051 : if (internal_key.IsNull() && !other.internal_key.IsNull()) {
# 390 : 64051 : internal_key = other.internal_key;
# 391 : 64051 : }
# 392 [ + - ][ + + ]: 64051 : if (merkle_root.IsNull() && !other.merkle_root.IsNull()) {
# 393 : 17016 : merkle_root = other.merkle_root;
# 394 : 17016 : }
# 395 [ + + ]: 64051 : for (auto& [key, control_blocks] : other.scripts) {
# 396 : 26024 : scripts[key].merge(std::move(control_blocks));
# 397 : 26024 : }
# 398 : 64051 : }
# 399 : :
# 400 : : void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth)
# 401 : 38053 : {
# 402 : 38053 : assert(depth >= 0 && (size_t)depth <= TAPROOT_CONTROL_MAX_NODE_COUNT);
# 403 : : /* We cannot insert a leaf at a lower depth while a deeper branch is unfinished. Doing
# 404 : : * so would mean the Add() invocations do not correspond to a DFS traversal of a
# 405 : : * binary tree. */
# 406 [ - + ]: 38053 : if ((size_t)depth + 1 < m_branch.size()) {
# 407 : 0 : m_valid = false;
# 408 : 0 : return;
# 409 : 0 : }
# 410 : : /* As long as an entry in the branch exists at the specified depth, combine it and propagate up.
# 411 : : * The 'node' variable is overwritten here with the newly combined node. */
# 412 [ + - ][ + + ]: 61328 : while (m_valid && m_branch.size() > (size_t)depth && m_branch[depth].has_value()) {
# [ + + ]
# 413 : 23275 : node = Combine(std::move(node), std::move(*m_branch[depth]));
# 414 : 23275 : m_branch.pop_back();
# 415 [ - + ]: 23275 : if (depth == 0) m_valid = false; /* Can't propagate further up than the root */
# 416 : 23275 : --depth;
# 417 : 23275 : }
# 418 [ + - ]: 38053 : if (m_valid) {
# 419 : : /* Make sure the branch is big enough to place the new node. */
# 420 [ + + ]: 38053 : if (m_branch.size() <= (size_t)depth) m_branch.resize((size_t)depth + 1);
# 421 : 38053 : assert(!m_branch[depth].has_value());
# 422 : 0 : m_branch[depth] = std::move(node);
# 423 : 38053 : }
# 424 : 38053 : }
# 425 : :
# 426 : : /*static*/ bool TaprootBuilder::ValidDepths(const std::vector<int>& depths)
# 427 : 975 : {
# 428 : 975 : std::vector<bool> branch;
# 429 [ + + ]: 1426 : for (int depth : depths) {
# 430 : : // This inner loop corresponds to effectively the same logic on branch
# 431 : : // as what Insert() performs on the m_branch variable. Instead of
# 432 : : // storing a NodeInfo object, just remember whether or not there is one
# 433 : : // at that depth.
# 434 [ - + ][ + + ]: 1426 : if (depth < 0 || (size_t)depth > TAPROOT_CONTROL_MAX_NODE_COUNT) return false;
# 435 [ + + ]: 1424 : if ((size_t)depth + 1 < branch.size()) return false;
# 436 [ + + ][ + + ]: 2374 : while (branch.size() > (size_t)depth && branch[depth]) {
# [ + + ]
# 437 : 998 : branch.pop_back();
# 438 [ + + ]: 998 : if (depth == 0) return false;
# 439 : 986 : --depth;
# 440 : 986 : }
# 441 [ + + ]: 1376 : if (branch.size() <= (size_t)depth) branch.resize((size_t)depth + 1);
# 442 : 1376 : assert(!branch[depth]);
# 443 : 0 : branch[depth] = true;
# 444 : 1376 : }
# 445 : : // And this check corresponds to the IsComplete() check on m_branch.
# 446 [ + + ][ + + ]: 925 : return branch.size() == 0 || (branch.size() == 1 && branch[0]);
# [ + - ]
# 447 : 975 : }
# 448 : :
# 449 : : TaprootBuilder& TaprootBuilder::Add(int depth, const CScript& script, int leaf_version, bool track)
# 450 : 38051 : {
# 451 : 38051 : assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0);
# 452 [ - + ]: 38051 : if (!IsValid()) return *this;
# 453 : : /* Construct NodeInfo object with leaf hash and (if track is true) also leaf information. */
# 454 : 38051 : NodeInfo node;
# 455 : 38051 : node.hash = (CHashWriter{HASHER_TAPLEAF} << uint8_t(leaf_version) << script).GetSHA256();
# 456 [ + - ]: 38051 : if (track) node.leaves.emplace_back(LeafInfo{script, leaf_version, {}});
# 457 : : /* Insert into the branch. */
# 458 : 38051 : Insert(std::move(node), depth);
# 459 : 38051 : return *this;
# 460 : 38051 : }
# 461 : :
# 462 : : TaprootBuilder& TaprootBuilder::AddOmitted(int depth, const uint256& hash)
# 463 : 2 : {
# 464 [ - + ]: 2 : if (!IsValid()) return *this;
# 465 : : /* Construct NodeInfo object with the hash directly, and insert it into the branch. */
# 466 : 2 : NodeInfo node;
# 467 : 2 : node.hash = hash;
# 468 : 2 : Insert(std::move(node), depth);
# 469 : 2 : return *this;
# 470 : 2 : }
# 471 : :
# 472 : : TaprootBuilder& TaprootBuilder::Finalize(const XOnlyPubKey& internal_key)
# 473 : 61284 : {
# 474 : : /* Can only call this function when IsComplete() is true. */
# 475 : 61284 : assert(IsComplete());
# 476 : 0 : m_internal_key = internal_key;
# 477 [ + + ]: 61284 : auto ret = m_internal_key.CreateTapTweak(m_branch.size() == 0 ? nullptr : &m_branch[0]->hash);
# 478 : 61284 : assert(ret.has_value());
# 479 : 0 : std::tie(m_output_key, m_parity) = *ret;
# 480 : 61284 : return *this;
# 481 : 61284 : }
# 482 : :
# 483 : 61298 : WitnessV1Taproot TaprootBuilder::GetOutput() { return WitnessV1Taproot{m_output_key}; }
# 484 : :
# 485 : : TaprootSpendData TaprootBuilder::GetSpendData() const
# 486 : 61282 : {
# 487 : 61282 : assert(IsComplete());
# 488 : 0 : TaprootSpendData spd;
# 489 [ + + ]: 61282 : spd.merkle_root = m_branch.size() == 0 ? uint256() : m_branch[0]->hash;
# 490 : 61282 : spd.internal_key = m_internal_key;
# 491 [ + + ]: 61282 : if (m_branch.size()) {
# 492 : : // If any script paths exist, they have been combined into the root m_branch[0]
# 493 : : // by now. Compute the control block for each of its tracked leaves, and put them in
# 494 : : // spd.scripts.
# 495 [ + + ]: 38047 : for (const auto& leaf : m_branch[0]->leaves) {
# 496 : 38047 : std::vector<unsigned char> control_block;
# 497 : 38047 : control_block.resize(TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size());
# 498 [ + + ]: 38047 : control_block[0] = leaf.leaf_version | (m_parity ? 1 : 0);
# 499 : 38047 : std::copy(m_internal_key.begin(), m_internal_key.end(), control_block.begin() + 1);
# 500 [ + + ]: 38047 : if (leaf.merkle_branch.size()) {
# 501 : 31125 : std::copy(leaf.merkle_branch[0].begin(),
# 502 : 31125 : leaf.merkle_branch[0].begin() + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size(),
# 503 : 31125 : control_block.begin() + TAPROOT_CONTROL_BASE_SIZE);
# 504 : 31125 : }
# 505 : 38047 : spd.scripts[{leaf.script, leaf.leaf_version}].insert(std::move(control_block));
# 506 : 38047 : }
# 507 : 14776 : }
# 508 : 61282 : return spd;
# 509 : 61282 : }
# 510 : :
# 511 : : std::optional<std::vector<std::tuple<int, CScript, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output)
# 512 : 117 : {
# 513 : : // Verify that the output matches the assumed Merkle root and internal key.
# 514 [ + + ]: 117 : auto tweak = spenddata.internal_key.CreateTapTweak(spenddata.merkle_root.IsNull() ? nullptr : &spenddata.merkle_root);
# 515 [ - + ][ - + ]: 117 : if (!tweak || tweak->first != output) return std::nullopt;
# 516 : : // If the Merkle root is 0, the tree is empty, and we're done.
# 517 : 117 : std::vector<std::tuple<int, CScript, int>> ret;
# 518 [ + + ]: 117 : if (spenddata.merkle_root.IsNull()) return ret;
# 519 : :
# 520 : : /** Data structure to represent the nodes of the tree we're going to build. */
# 521 : 96 : struct TreeNode {
# 522 : : /** Hash of this node, if known; 0 otherwise. */
# 523 : 96 : uint256 hash;
# 524 : : /** The left and right subtrees (note that their order is irrelevant). */
# 525 : 96 : std::unique_ptr<TreeNode> sub[2];
# 526 : : /** If this is known to be a leaf node, a pointer to the (script, leaf_ver) pair.
# 527 : : * nullptr otherwise. */
# 528 : 96 : const std::pair<CScript, int>* leaf = nullptr;
# 529 : : /** Whether or not this node has been explored (is known to be a leaf, or known to have children). */
# 530 : 96 : bool explored = false;
# 531 : : /** Whether or not this node is an inner node (unknown until explored = true). */
# 532 : 96 : bool inner;
# 533 : : /** Whether or not we have produced output for this subtree. */
# 534 : 96 : bool done = false;
# 535 : 96 : };
# 536 : :
# 537 : : // Build tree from the provided branches.
# 538 : 96 : TreeNode root;
# 539 : 96 : root.hash = spenddata.merkle_root;
# 540 [ + + ]: 140 : for (const auto& [key, control_blocks] : spenddata.scripts) {
# 541 : 140 : const auto& [script, leaf_ver] = key;
# 542 [ + + ]: 184 : for (const auto& control : control_blocks) {
# 543 : : // Skip script records with nonsensical leaf version.
# 544 [ - + ][ - + ]: 184 : if (leaf_ver < 0 || leaf_ver >= 0x100 || leaf_ver & 1) continue;
# [ - + ]
# 545 : : // Skip script records with invalid control block sizes.
# 546 [ - + ][ - + ]: 184 : if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE ||
# 547 [ - + ]: 184 : ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) continue;
# 548 : : // Skip script records that don't match the control block.
# 549 [ - + ]: 184 : if ((control[0] & TAPROOT_LEAF_MASK) != leaf_ver) continue;
# 550 : : // Skip script records that don't match the provided Merkle root.
# 551 : 184 : const uint256 leaf_hash = ComputeTapleafHash(leaf_ver, script);
# 552 : 184 : const uint256 merkle_root = ComputeTaprootMerkleRoot(control, leaf_hash);
# 553 [ - + ]: 184 : if (merkle_root != spenddata.merkle_root) continue;
# 554 : :
# 555 : 184 : TreeNode* node = &root;
# 556 : 184 : size_t levels = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
# 557 [ + + ]: 448 : for (size_t depth = 0; depth < levels; ++depth) {
# 558 : : // Can't descend into a node which we already know is a leaf.
# 559 [ + + ][ - + ]: 264 : if (node->explored && !node->inner) return std::nullopt;
# 560 : :
# 561 : : // Extract partner hash from Merkle branch in control block.
# 562 : 264 : uint256 hash;
# 563 : 264 : std::copy(control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - 1 - depth) * TAPROOT_CONTROL_NODE_SIZE,
# 564 : 264 : control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - depth) * TAPROOT_CONTROL_NODE_SIZE,
# 565 : 264 : hash.begin());
# 566 : :
# 567 [ + + ]: 264 : if (node->sub[0]) {
# 568 : : // Descend into the existing left or right branch.
# 569 : 160 : bool desc = false;
# 570 [ + - ]: 191 : for (int i = 0; i < 2; ++i) {
# 571 [ + + ][ + + ]: 191 : if (node->sub[i]->hash == hash || (node->sub[i]->hash.IsNull() && node->sub[1-i]->hash != hash)) {
# [ + + ]
# 572 : 160 : node->sub[i]->hash = hash;
# 573 : 160 : node = &*node->sub[1-i];
# 574 : 160 : desc = true;
# 575 : 160 : break;
# 576 : 160 : }
# 577 : 191 : }
# 578 [ - + ]: 160 : if (!desc) return std::nullopt; // This probably requires a hash collision to hit.
# 579 : 160 : } else {
# 580 : : // We're in an unexplored node. Create subtrees and descend.
# 581 : 104 : node->explored = true;
# 582 : 104 : node->inner = true;
# 583 : 104 : node->sub[0] = std::make_unique<TreeNode>();
# 584 : 104 : node->sub[1] = std::make_unique<TreeNode>();
# 585 : 104 : node->sub[1]->hash = hash;
# 586 : 104 : node = &*node->sub[0];
# 587 : 104 : }
# 588 : 264 : }
# 589 : : // Cannot turn a known inner node into a leaf.
# 590 [ - + ]: 184 : if (node->sub[0]) return std::nullopt;
# 591 : 184 : node->explored = true;
# 592 : 184 : node->inner = false;
# 593 : 184 : node->leaf = &key;
# 594 : 184 : node->hash = leaf_hash;
# 595 : 184 : }
# 596 : 140 : }
# 597 : :
# 598 : : // Recursive processing to turn the tree into flattened output. Use an explicit stack here to avoid
# 599 : : // overflowing the call stack (the tree may be 128 levels deep).
# 600 : 96 : std::vector<TreeNode*> stack{&root};
# 601 [ + + ]: 676 : while (!stack.empty()) {
# 602 : 580 : TreeNode& node = *stack.back();
# 603 [ - + ]: 580 : if (!node.explored) {
# 604 : : // Unexplored node, which means the tree is incomplete.
# 605 : 0 : return std::nullopt;
# 606 [ + + ]: 580 : } else if (!node.inner) {
# 607 : : // Leaf node; produce output.
# 608 : 212 : ret.emplace_back(stack.size() - 1, node.leaf->first, node.leaf->second);
# 609 : 212 : node.done = true;
# 610 : 212 : stack.pop_back();
# 611 [ + + ][ + + ]: 368 : } else if (node.sub[0]->done && !node.sub[1]->done && !node.sub[1]->explored && !node.sub[1]->hash.IsNull() &&
# [ + + ][ + + ]
# [ + - ]
# 612 [ + - ]: 368 : (CHashWriter{HASHER_TAPBRANCH} << node.sub[1]->hash << node.sub[1]->hash).GetSHA256() == node.hash) {
# 613 : : // Whenever there are nodes with two identical subtrees under it, we run into a problem:
# 614 : : // the control blocks for the leaves underneath those will be identical as well, and thus
# 615 : : // they will all be matched to the same path in the tree. The result is that at the location
# 616 : : // where the duplicate occurred, the left child will contain a normal tree that can be explored
# 617 : : // and processed, but the right one will remain unexplored.
# 618 : : //
# 619 : : // This situation can be detected, by encountering an inner node with unexplored right subtree
# 620 : : // with known hash, and H_TapBranch(hash, hash) is equal to the parent node (this node)'s hash.
# 621 : : //
# 622 : : // To deal with this, simply process the left tree a second time (set its done flag to false;
# 623 : : // noting that the done flag of its children have already been set to false after processing
# 624 : : // those). To avoid ending up in an infinite loop, set the done flag of the right (unexplored)
# 625 : : // subtree to true.
# 626 : 20 : node.sub[0]->done = false;
# 627 : 20 : node.sub[1]->done = true;
# 628 [ + + ][ + + ]: 348 : } else if (node.sub[0]->done && node.sub[1]->done) {
# 629 : : // An internal node which we're finished with.
# 630 : 116 : node.sub[0]->done = false;
# 631 : 116 : node.sub[1]->done = false;
# 632 : 116 : node.done = true;
# 633 : 116 : stack.pop_back();
# 634 [ + + ]: 232 : } else if (!node.sub[0]->done) {
# 635 : : // An internal node whose left branch hasn't been processed yet. Do so first.
# 636 : 136 : stack.push_back(&*node.sub[0]);
# 637 [ + - ]: 136 : } else if (!node.sub[1]->done) {
# 638 : : // An internal node whose right branch hasn't been processed yet. Do so first.
# 639 : 96 : stack.push_back(&*node.sub[1]);
# 640 : 96 : }
# 641 : 580 : }
# 642 : :
# 643 : 96 : return ret;
# 644 : 96 : }
|
