From c814e2e7e81fd01fcb07f4a28435741bdc463801 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 8 May 2018 20:24:06 -0700 Subject: Remove template matching and pseudo opcodes The current code contains a rather complex script template matching engine, which is only used for 3 particular script types (P2PK, P2PKH, multisig). The first two of these are trivial to match for otherwise, and a specialized matcher for multisig is both more compact and more efficient than a generic one. The goal is being more flexible, so that for example larger standard multisigs inside SegWit outputs are more easy to implement. As a side-effect, it also gets rid of the pseudo opcodes hack. --- src/pubkey.h | 8 +-- src/script/script.cpp | 5 -- src/script/script.h | 7 --- src/script/standard.cpp | 149 ++++++++++++++++++++---------------------------- 4 files changed, 66 insertions(+), 103 deletions(-) diff --git a/src/pubkey.h b/src/pubkey.h index 9c6c6b085e..bb254547c8 100644 --- a/src/pubkey.h +++ b/src/pubkey.h @@ -33,10 +33,10 @@ public: /** * secp256k1: */ - static const unsigned int PUBLIC_KEY_SIZE = 65; - static const unsigned int COMPRESSED_PUBLIC_KEY_SIZE = 33; - static const unsigned int SIGNATURE_SIZE = 72; - static const unsigned int COMPACT_SIGNATURE_SIZE = 65; + static constexpr unsigned int PUBLIC_KEY_SIZE = 65; + static constexpr unsigned int COMPRESSED_PUBLIC_KEY_SIZE = 33; + static constexpr unsigned int SIGNATURE_SIZE = 72; + static constexpr unsigned int COMPACT_SIGNATURE_SIZE = 65; /** * see www.keylength.com * script supports up to 75 for single byte push diff --git a/src/script/script.cpp b/src/script/script.cpp index 7f25d915a8..c84c7b8ec1 100644 --- a/src/script/script.cpp +++ b/src/script/script.cpp @@ -141,11 +141,6 @@ const char* GetOpName(opcodetype opcode) case OP_INVALIDOPCODE : return "OP_INVALIDOPCODE"; - // Note: - // The template matching params OP_SMALLINTEGER/etc are defined in opcodetype enum - // as kind of implementation hack, they are *NOT* real opcodes. If found in real - // Script, just let the default: case deal with them. - default: return "OP_UNKNOWN"; } diff --git a/src/script/script.h b/src/script/script.h index d8b7c06013..a4f377dd94 100644 --- a/src/script/script.h +++ b/src/script/script.h @@ -181,13 +181,6 @@ enum opcodetype OP_NOP9 = 0xb8, OP_NOP10 = 0xb9, - - // template matching params - OP_SMALLINTEGER = 0xfa, - OP_PUBKEYS = 0xfb, - OP_PUBKEYHASH = 0xfd, - OP_PUBKEY = 0xfe, - OP_INVALIDOPCODE = 0xff, }; diff --git a/src/script/standard.cpp b/src/script/standard.cpp index 76778112aa..53fcbe37de 100644 --- a/src/script/standard.cpp +++ b/src/script/standard.cpp @@ -35,22 +35,54 @@ const char* GetTxnOutputType(txnouttype t) return nullptr; } -bool Solver(const CScript& scriptPubKey, txnouttype& typeRet, std::vector >& vSolutionsRet) +static bool MatchPayToPubkey(const CScript& script, valtype& pubkey) { - // Templates - static std::multimap mTemplates; - if (mTemplates.empty()) - { - // Standard tx, sender provides pubkey, receiver adds signature - mTemplates.insert(std::make_pair(TX_PUBKEY, CScript() << OP_PUBKEY << OP_CHECKSIG)); + if (script.size() == CPubKey::PUBLIC_KEY_SIZE + 2 && script[0] == CPubKey::PUBLIC_KEY_SIZE && script.back() == OP_CHECKSIG) { + pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::PUBLIC_KEY_SIZE + 1); + return CPubKey::ValidSize(pubkey); + } + if (script.size() == CPubKey::COMPRESSED_PUBLIC_KEY_SIZE + 2 && script[0] == CPubKey::COMPRESSED_PUBLIC_KEY_SIZE && script.back() == OP_CHECKSIG) { + pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::COMPRESSED_PUBLIC_KEY_SIZE + 1); + return CPubKey::ValidSize(pubkey); + } + return false; +} - // Bitcoin address tx, sender provides hash of pubkey, receiver provides signature and pubkey - mTemplates.insert(std::make_pair(TX_PUBKEYHASH, CScript() << OP_DUP << OP_HASH160 << OP_PUBKEYHASH << OP_EQUALVERIFY << OP_CHECKSIG)); +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; +} - // Sender provides N pubkeys, receivers provides M signatures - mTemplates.insert(std::make_pair(TX_MULTISIG, CScript() << OP_SMALLINTEGER << OP_PUBKEYS << OP_SMALLINTEGER << OP_CHECKMULTISIG)); +static bool MatchMultisig(const CScript& script, unsigned int& required, std::vector& 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) || !IsSmallInteger(opcode)) return false; + required = CScript::DecodeOP_N(opcode); + while (script.GetOp(it, opcode, data) && CPubKey::ValidSize(data)) { + pubkeys.emplace_back(std::move(data)); } + if (!IsSmallInteger(opcode)) return false; + unsigned int keys = CScript::DecodeOP_N(opcode); + if (pubkeys.size() != keys || keys < required) return false; + return (it + 1 == script.end()); +} +bool Solver(const CScript& scriptPubKey, txnouttype& typeRet, std::vector >& vSolutionsRet) +{ vSolutionsRet.clear(); // Shortcut for pay-to-script-hash, which are more constrained than the other types: @@ -95,84 +127,27 @@ bool Solver(const CScript& scriptPubKey, txnouttype& typeRet, std::vector& tplate : mTemplates) - { - const CScript& script2 = tplate.second; - vSolutionsRet.clear(); + std::vector data; + if (MatchPayToPubkey(scriptPubKey, data)) { + typeRet = TX_PUBKEY; + vSolutionsRet.push_back(std::move(data)); + return true; + } - opcodetype opcode1, opcode2; - std::vector vch1, vch2; + if (MatchPayToPubkeyHash(scriptPubKey, data)) { + typeRet = TX_PUBKEYHASH; + vSolutionsRet.push_back(std::move(data)); + return true; + } - // Compare - CScript::const_iterator pc1 = script1.begin(); - CScript::const_iterator pc2 = script2.begin(); - while (true) - { - if (pc1 == script1.end() && pc2 == script2.end()) - { - // Found a match - typeRet = tplate.first; - if (typeRet == TX_MULTISIG) - { - // Additional checks for TX_MULTISIG: - unsigned char m = vSolutionsRet.front()[0]; - unsigned char n = vSolutionsRet.back()[0]; - if (m < 1 || n < 1 || m > n || vSolutionsRet.size()-2 != n) - return false; - } - return true; - } - if (!script1.GetOp(pc1, opcode1, vch1)) - break; - if (!script2.GetOp(pc2, opcode2, vch2)) - break; - - // Template matching opcodes: - if (opcode2 == OP_PUBKEYS) - { - while (CPubKey::ValidSize(vch1)) - { - vSolutionsRet.push_back(vch1); - if (!script1.GetOp(pc1, opcode1, vch1)) - break; - } - if (!script2.GetOp(pc2, opcode2, vch2)) - break; - // Normal situation is to fall through - // to other if/else statements - } - - if (opcode2 == OP_PUBKEY) - { - if (!CPubKey::ValidSize(vch1)) - break; - vSolutionsRet.push_back(vch1); - } - else if (opcode2 == OP_PUBKEYHASH) - { - if (vch1.size() != sizeof(uint160)) - break; - vSolutionsRet.push_back(vch1); - } - else if (opcode2 == OP_SMALLINTEGER) - { // Single-byte small integer pushed onto vSolutions - if (opcode1 == OP_0 || - (opcode1 >= OP_1 && opcode1 <= OP_16)) - { - char n = (char)CScript::DecodeOP_N(opcode1); - vSolutionsRet.push_back(valtype(1, n)); - } - else - break; - } - else if (opcode1 != opcode2 || vch1 != vch2) - { - // Others must match exactly - break; - } - } + unsigned int required; + std::vector> keys; + if (MatchMultisig(scriptPubKey, required, keys)) { + typeRet = TX_MULTISIG; + vSolutionsRet.push_back({static_cast(required)}); // safe as required is in range 1..16 + vSolutionsRet.insert(vSolutionsRet.end(), keys.begin(), keys.end()); + vSolutionsRet.push_back({static_cast(keys.size())}); // safe as size is in range 1..16 + return true; } vSolutionsRet.clear(); -- cgit v1.2.3