diff options
Diffstat (limited to 'src/script/solver.cpp')
| -rw-r--r-- | src/script/solver.cpp | 223 |
1 files changed, 223 insertions, 0 deletions
diff --git a/src/script/solver.cpp b/src/script/solver.cpp new file mode 100644 index 0000000000..1cd388b061 --- /dev/null +++ b/src/script/solver.cpp @@ -0,0 +1,223 @@ +// Copyright (c) 2009-2010 Satoshi Nakamoto +// Copyright (c) 2009-2022 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include <script/solver.h> +#include <pubkey.h> +#include <script/interpreter.h> +#include <script/script.h> +#include <span.h> + +#include <string> +#include <algorithm> + +typedef std::vector<unsigned char> valtype; + +std::string GetTxnOutputType(TxoutType t) +{ + switch (t) { + case TxoutType::NONSTANDARD: return "nonstandard"; + case TxoutType::PUBKEY: return "pubkey"; + case TxoutType::PUBKEYHASH: return "pubkeyhash"; + case TxoutType::SCRIPTHASH: return "scripthash"; + case TxoutType::MULTISIG: return "multisig"; + case TxoutType::NULL_DATA: return "nulldata"; + case TxoutType::WITNESS_V0_KEYHASH: return "witness_v0_keyhash"; + case TxoutType::WITNESS_V0_SCRIPTHASH: return "witness_v0_scripthash"; + case TxoutType::WITNESS_V1_TAPROOT: return "witness_v1_taproot"; + case TxoutType::WITNESS_UNKNOWN: return "witness_unknown"; + } // no default case, so the compiler can warn about missing cases + assert(false); +} + +static bool MatchPayToPubkey(const CScript& script, valtype& pubkey) +{ + if (script.size() == CPubKey::SIZE + 2 && script[0] == CPubKey::SIZE && script.back() == OP_CHECKSIG) { + pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::SIZE + 1); + return CPubKey::ValidSize(pubkey); + } + if (script.size() == CPubKey::COMPRESSED_SIZE + 2 && script[0] == CPubKey::COMPRESSED_SIZE && script.back() == OP_CHECKSIG) { + pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::COMPRESSED_SIZE + 1); + return CPubKey::ValidSize(pubkey); + } + return false; +} + +static bool MatchPayToPubkeyHash(const CScript& script, valtype& pubkeyhash) +{ + if (script.size() == 25 && script[0] == OP_DUP && script[1] == OP_HASH160 && script[2] == 20 && script[23] == OP_EQUALVERIFY && script[24] == OP_CHECKSIG) { + pubkeyhash = valtype(script.begin () + 3, script.begin() + 23); + return true; + } + return false; +} + +/** Test for "small positive integer" script opcodes - OP_1 through OP_16. */ +static constexpr bool IsSmallInteger(opcodetype opcode) +{ + return opcode >= OP_1 && opcode <= OP_16; +} + +/** Retrieve a minimally-encoded number in range [min,max] from an (opcode, data) pair, + * whether it's OP_n or through a push. */ +static std::optional<int> GetScriptNumber(opcodetype opcode, valtype data, int min, int max) +{ + int count; + if (IsSmallInteger(opcode)) { + count = CScript::DecodeOP_N(opcode); + } else if (IsPushdataOp(opcode)) { + if (!CheckMinimalPush(data, opcode)) return {}; + try { + count = CScriptNum(data, /* fRequireMinimal = */ true).getint(); + } catch (const scriptnum_error&) { + return {}; + } + } else { + return {}; + } + if (count < min || count > max) return {}; + return count; +} + +static bool MatchMultisig(const CScript& script, int& required_sigs, std::vector<valtype>& pubkeys) +{ + opcodetype opcode; + valtype data; + + CScript::const_iterator it = script.begin(); + if (script.size() < 1 || script.back() != OP_CHECKMULTISIG) return false; + + if (!script.GetOp(it, opcode, data)) return false; + auto req_sigs = GetScriptNumber(opcode, data, 1, MAX_PUBKEYS_PER_MULTISIG); + if (!req_sigs) return false; + required_sigs = *req_sigs; + while (script.GetOp(it, opcode, data) && CPubKey::ValidSize(data)) { + pubkeys.emplace_back(std::move(data)); + } + auto num_keys = GetScriptNumber(opcode, data, required_sigs, MAX_PUBKEYS_PER_MULTISIG); + if (!num_keys) return false; + if (pubkeys.size() != static_cast<unsigned long>(*num_keys)) return false; + + return (it + 1 == script.end()); +} + +std::optional<std::pair<int, std::vector<Span<const unsigned char>>>> MatchMultiA(const CScript& script) +{ + std::vector<Span<const unsigned char>> keyspans; + + // Redundant, but very fast and selective test. + if (script.size() == 0 || script[0] != 32 || script.back() != OP_NUMEQUAL) return {}; + + // Parse keys + auto it = script.begin(); + while (script.end() - it >= 34) { + if (*it != 32) return {}; + ++it; + keyspans.emplace_back(&*it, 32); + it += 32; + if (*it != (keyspans.size() == 1 ? OP_CHECKSIG : OP_CHECKSIGADD)) return {}; + ++it; + } + if (keyspans.size() == 0 || keyspans.size() > MAX_PUBKEYS_PER_MULTI_A) return {}; + + // Parse threshold. + opcodetype opcode; + std::vector<unsigned char> data; + if (!script.GetOp(it, opcode, data)) return {}; + if (it == script.end()) return {}; + if (*it != OP_NUMEQUAL) return {}; + ++it; + if (it != script.end()) return {}; + auto threshold = GetScriptNumber(opcode, data, 1, (int)keyspans.size()); + if (!threshold) return {}; + + // Construct result. + return std::pair{*threshold, std::move(keyspans)}; +} + +TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned char>>& vSolutionsRet) +{ + vSolutionsRet.clear(); + + // Shortcut for pay-to-script-hash, which are more constrained than the other types: + // it is always OP_HASH160 20 [20 byte hash] OP_EQUAL + if (scriptPubKey.IsPayToScriptHash()) + { + std::vector<unsigned char> hashBytes(scriptPubKey.begin()+2, scriptPubKey.begin()+22); + vSolutionsRet.push_back(hashBytes); + return TxoutType::SCRIPTHASH; + } + + int witnessversion; + std::vector<unsigned char> witnessprogram; + if (scriptPubKey.IsWitnessProgram(witnessversion, witnessprogram)) { + if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_KEYHASH_SIZE) { + vSolutionsRet.push_back(std::move(witnessprogram)); + return TxoutType::WITNESS_V0_KEYHASH; + } + if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_SCRIPTHASH_SIZE) { + vSolutionsRet.push_back(std::move(witnessprogram)); + return TxoutType::WITNESS_V0_SCRIPTHASH; + } + if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE) { + vSolutionsRet.push_back(std::move(witnessprogram)); + return TxoutType::WITNESS_V1_TAPROOT; + } + if (witnessversion != 0) { + vSolutionsRet.push_back(std::vector<unsigned char>{(unsigned char)witnessversion}); + vSolutionsRet.push_back(std::move(witnessprogram)); + return TxoutType::WITNESS_UNKNOWN; + } + return TxoutType::NONSTANDARD; + } + + // Provably prunable, data-carrying output + // + // So long as script passes the IsUnspendable() test and all but the first + // byte passes the IsPushOnly() test we don't care what exactly is in the + // script. + if (scriptPubKey.size() >= 1 && scriptPubKey[0] == OP_RETURN && scriptPubKey.IsPushOnly(scriptPubKey.begin()+1)) { + return TxoutType::NULL_DATA; + } + + std::vector<unsigned char> data; + if (MatchPayToPubkey(scriptPubKey, data)) { + vSolutionsRet.push_back(std::move(data)); + return TxoutType::PUBKEY; + } + + if (MatchPayToPubkeyHash(scriptPubKey, data)) { + vSolutionsRet.push_back(std::move(data)); + return TxoutType::PUBKEYHASH; + } + + int required; + std::vector<std::vector<unsigned char>> keys; + if (MatchMultisig(scriptPubKey, required, keys)) { + vSolutionsRet.push_back({static_cast<unsigned char>(required)}); // safe as required is in range 1..20 + vSolutionsRet.insert(vSolutionsRet.end(), keys.begin(), keys.end()); + vSolutionsRet.push_back({static_cast<unsigned char>(keys.size())}); // safe as size is in range 1..20 + return TxoutType::MULTISIG; + } + + vSolutionsRet.clear(); + return TxoutType::NONSTANDARD; +} + +CScript GetScriptForRawPubKey(const CPubKey& pubKey) +{ + return CScript() << std::vector<unsigned char>(pubKey.begin(), pubKey.end()) << OP_CHECKSIG; +} + +CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys) +{ + CScript script; + + script << nRequired; + for (const CPubKey& key : keys) + script << ToByteVector(key); + script << keys.size() << OP_CHECKMULTISIG; + + return script; +} |