LCOV - code coverage report
Current view: top level - src/script - solver.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 13 134 9.7 %
Date: 2023-11-06 23:13:05 Functions: 1 10 10.0 %
Branches: 20 299 6.7 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 2009-2010 Satoshi Nakamoto
       2                 :            : // Copyright (c) 2009-2022 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 <pubkey.h>
       7                 :            : #include <script/interpreter.h>
       8                 :            : #include <script/script.h>
       9                 :            : #include <script/solver.h>
      10                 :            : #include <span.h>
      11                 :            : 
      12                 :            : #include <algorithm>
      13                 :            : #include <cassert>
      14                 :            : #include <string>
      15                 :            : 
      16                 :            : typedef std::vector<unsigned char> valtype;
      17                 :            : 
      18                 :        100 : std::string GetTxnOutputType(TxoutType t)
      19                 :            : {
      20   [ +  +  +  +  :        100 :     switch (t) {
          +  +  +  +  +  
                   +  - ]
      21         [ +  - ]:         10 :     case TxoutType::NONSTANDARD: return "nonstandard";
      22         [ +  - ]:         10 :     case TxoutType::PUBKEY: return "pubkey";
      23         [ +  - ]:         10 :     case TxoutType::PUBKEYHASH: return "pubkeyhash";
      24         [ +  - ]:         10 :     case TxoutType::SCRIPTHASH: return "scripthash";
      25         [ +  - ]:         10 :     case TxoutType::MULTISIG: return "multisig";
      26         [ +  - ]:         10 :     case TxoutType::NULL_DATA: return "nulldata";
      27         [ +  - ]:         10 :     case TxoutType::WITNESS_V0_KEYHASH: return "witness_v0_keyhash";
      28         [ +  - ]:         10 :     case TxoutType::WITNESS_V0_SCRIPTHASH: return "witness_v0_scripthash";
      29         [ +  - ]:         10 :     case TxoutType::WITNESS_V1_TAPROOT: return "witness_v1_taproot";
      30         [ +  - ]:         10 :     case TxoutType::WITNESS_UNKNOWN: return "witness_unknown";
      31                 :            :     } // no default case, so the compiler can warn about missing cases
      32                 :          0 :     assert(false);
      33                 :        100 : }
      34                 :            : 
      35                 :          0 : static bool MatchPayToPubkey(const CScript& script, valtype& pubkey)
      36                 :            : {
      37 [ #  # ][ #  # ]:          0 :     if (script.size() == CPubKey::SIZE + 2 && script[0] == CPubKey::SIZE && script.back() == OP_CHECKSIG) {
                 [ #  # ]
      38         [ #  # ]:          0 :         pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::SIZE + 1);
      39                 :          0 :         return CPubKey::ValidSize(pubkey);
      40                 :            :     }
      41 [ #  # ][ #  # ]:          0 :     if (script.size() == CPubKey::COMPRESSED_SIZE + 2 && script[0] == CPubKey::COMPRESSED_SIZE && script.back() == OP_CHECKSIG) {
                 [ #  # ]
      42         [ #  # ]:          0 :         pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::COMPRESSED_SIZE + 1);
      43                 :          0 :         return CPubKey::ValidSize(pubkey);
      44                 :            :     }
      45                 :          0 :     return false;
      46                 :          0 : }
      47                 :            : 
      48                 :          0 : static bool MatchPayToPubkeyHash(const CScript& script, valtype& pubkeyhash)
      49                 :            : {
      50 [ #  # ][ #  # ]:          0 :     if (script.size() == 25 && script[0] == OP_DUP && script[1] == OP_HASH160 && script[2] == 20 && script[23] == OP_EQUALVERIFY && script[24] == OP_CHECKSIG) {
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
      51         [ #  # ]:          0 :         pubkeyhash = valtype(script.begin () + 3, script.begin() + 23);
      52                 :          0 :         return true;
      53                 :            :     }
      54                 :          0 :     return false;
      55                 :          0 : }
      56                 :            : 
      57                 :            : /** Test for "small positive integer" script opcodes - OP_1 through OP_16. */
      58                 :          0 : static constexpr bool IsSmallInteger(opcodetype opcode)
      59                 :            : {
      60         [ #  # ]:          0 :     return opcode >= OP_1 && opcode <= OP_16;
      61                 :            : }
      62                 :            : 
      63                 :            : /** Retrieve a minimally-encoded number in range [min,max] from an (opcode, data) pair,
      64                 :            :  *  whether it's OP_n or through a push. */
      65                 :          0 : static std::optional<int> GetScriptNumber(opcodetype opcode, valtype data, int min, int max)
      66                 :            : {
      67                 :            :     int count;
      68         [ #  # ]:          0 :     if (IsSmallInteger(opcode)) {
      69                 :          0 :         count = CScript::DecodeOP_N(opcode);
      70         [ #  # ]:          0 :     } else if (IsPushdataOp(opcode)) {
      71         [ #  # ]:          0 :         if (!CheckMinimalPush(data, opcode)) return {};
      72                 :            :         try {
      73 [ #  # ][ #  # ]:          0 :             count = CScriptNum(data, /* fRequireMinimal = */ true).getint();
      74         [ #  # ]:          0 :         } catch (const scriptnum_error&) {
      75                 :          0 :             return {};
      76                 :          0 :         }
      77                 :          0 :     } else {
      78                 :          0 :         return {};
      79                 :            :     }
      80 [ #  # ][ #  # ]:          0 :     if (count < min || count > max) return {};
      81                 :          0 :     return count;
      82                 :          0 : }
      83                 :            : 
      84                 :          0 : static bool MatchMultisig(const CScript& script, int& required_sigs, std::vector<valtype>& pubkeys)
      85                 :            : {
      86                 :            :     opcodetype opcode;
      87                 :          0 :     valtype data;
      88                 :            : 
      89         [ #  # ]:          0 :     CScript::const_iterator it = script.begin();
      90 [ #  # ][ #  # ]:          0 :     if (script.size() < 1 || script.back() != OP_CHECKMULTISIG) return false;
         [ #  # ][ #  # ]
      91                 :            : 
      92 [ #  # ][ #  # ]:          0 :     if (!script.GetOp(it, opcode, data)) return false;
      93 [ #  # ][ #  # ]:          0 :     auto req_sigs = GetScriptNumber(opcode, data, 1, MAX_PUBKEYS_PER_MULTISIG);
      94         [ #  # ]:          0 :     if (!req_sigs) return false;
      95                 :          0 :     required_sigs = *req_sigs;
      96 [ #  # ][ #  # ]:          0 :     while (script.GetOp(it, opcode, data) && CPubKey::ValidSize(data)) {
         [ #  # ][ #  # ]
      97         [ #  # ]:          0 :         pubkeys.emplace_back(std::move(data));
      98                 :            :     }
      99 [ #  # ][ #  # ]:          0 :     auto num_keys = GetScriptNumber(opcode, data, required_sigs, MAX_PUBKEYS_PER_MULTISIG);
     100         [ #  # ]:          0 :     if (!num_keys) return false;
     101         [ #  # ]:          0 :     if (pubkeys.size() != static_cast<unsigned long>(*num_keys)) return false;
     102                 :            : 
     103 [ #  # ][ #  # ]:          0 :     return (it + 1 == script.end());
                 [ #  # ]
     104                 :          0 : }
     105                 :            : 
     106                 :          0 : std::optional<std::pair<int, std::vector<Span<const unsigned char>>>> MatchMultiA(const CScript& script)
     107                 :            : {
     108                 :          0 :     std::vector<Span<const unsigned char>> keyspans;
     109                 :            : 
     110                 :            :     // Redundant, but very fast and selective test.
     111 [ #  # ][ #  # ]:          0 :     if (script.size() == 0 || script[0] != 32 || script.back() != OP_NUMEQUAL) return {};
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     112                 :            : 
     113                 :            :     // Parse keys
     114         [ #  # ]:          0 :     auto it = script.begin();
     115 [ #  # ][ #  # ]:          0 :     while (script.end() - it >= 34) {
                 [ #  # ]
     116 [ #  # ][ #  # ]:          0 :         if (*it != 32) return {};
     117         [ #  # ]:          0 :         ++it;
     118 [ #  # ][ #  # ]:          0 :         keyspans.emplace_back(&*it, 32);
     119         [ #  # ]:          0 :         it += 32;
     120 [ #  # ][ #  # ]:          0 :         if (*it != (keyspans.size() == 1 ? OP_CHECKSIG : OP_CHECKSIGADD)) return {};
     121         [ #  # ]:          0 :         ++it;
     122                 :            :     }
     123 [ #  # ][ #  # ]:          0 :     if (keyspans.size() == 0 || keyspans.size() > MAX_PUBKEYS_PER_MULTI_A) return {};
     124                 :            : 
     125                 :            :     // Parse threshold.
     126                 :            :     opcodetype opcode;
     127                 :          0 :     std::vector<unsigned char> data;
     128 [ #  # ][ #  # ]:          0 :     if (!script.GetOp(it, opcode, data)) return {};
     129 [ #  # ][ #  # ]:          0 :     if (it == script.end()) return {};
                 [ #  # ]
     130 [ #  # ][ #  # ]:          0 :     if (*it != OP_NUMEQUAL) return {};
     131         [ #  # ]:          0 :     ++it;
     132 [ #  # ][ #  # ]:          0 :     if (it != script.end()) return {};
                 [ #  # ]
     133 [ #  # ][ #  # ]:          0 :     auto threshold = GetScriptNumber(opcode, data, 1, (int)keyspans.size());
     134         [ #  # ]:          0 :     if (!threshold) return {};
     135                 :            : 
     136                 :            :     // Construct result.
     137         [ #  # ]:          0 :     return std::pair{*threshold, std::move(keyspans)};
     138                 :          0 : }
     139                 :            : 
     140                 :          0 : TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned char>>& vSolutionsRet)
     141                 :            : {
     142                 :          0 :     vSolutionsRet.clear();
     143                 :            : 
     144                 :            :     // Shortcut for pay-to-script-hash, which are more constrained than the other types:
     145                 :            :     // it is always OP_HASH160 20 [20 byte hash] OP_EQUAL
     146         [ #  # ]:          0 :     if (scriptPubKey.IsPayToScriptHash())
     147                 :            :     {
     148         [ #  # ]:          0 :         std::vector<unsigned char> hashBytes(scriptPubKey.begin()+2, scriptPubKey.begin()+22);
     149         [ #  # ]:          0 :         vSolutionsRet.push_back(hashBytes);
     150                 :          0 :         return TxoutType::SCRIPTHASH;
     151                 :          0 :     }
     152                 :            : 
     153                 :            :     int witnessversion;
     154                 :          0 :     std::vector<unsigned char> witnessprogram;
     155 [ #  # ][ #  # ]:          0 :     if (scriptPubKey.IsWitnessProgram(witnessversion, witnessprogram)) {
     156 [ #  # ][ #  # ]:          0 :         if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_KEYHASH_SIZE) {
     157         [ #  # ]:          0 :             vSolutionsRet.push_back(std::move(witnessprogram));
     158                 :          0 :             return TxoutType::WITNESS_V0_KEYHASH;
     159                 :            :         }
     160 [ #  # ][ #  # ]:          0 :         if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_SCRIPTHASH_SIZE) {
     161         [ #  # ]:          0 :             vSolutionsRet.push_back(std::move(witnessprogram));
     162                 :          0 :             return TxoutType::WITNESS_V0_SCRIPTHASH;
     163                 :            :         }
     164 [ #  # ][ #  # ]:          0 :         if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE) {
     165         [ #  # ]:          0 :             vSolutionsRet.push_back(std::move(witnessprogram));
     166                 :          0 :             return TxoutType::WITNESS_V1_TAPROOT;
     167                 :            :         }
     168         [ #  # ]:          0 :         if (witnessversion != 0) {
     169 [ #  # ][ #  # ]:          0 :             vSolutionsRet.push_back(std::vector<unsigned char>{(unsigned char)witnessversion});
     170         [ #  # ]:          0 :             vSolutionsRet.push_back(std::move(witnessprogram));
     171                 :          0 :             return TxoutType::WITNESS_UNKNOWN;
     172                 :            :         }
     173                 :          0 :         return TxoutType::NONSTANDARD;
     174                 :            :     }
     175                 :            : 
     176                 :            :     // Provably prunable, data-carrying output
     177                 :            :     //
     178                 :            :     // So long as script passes the IsUnspendable() test and all but the first
     179                 :            :     // byte passes the IsPushOnly() test we don't care what exactly is in the
     180                 :            :     // script.
     181 [ #  # ][ #  # ]:          0 :     if (scriptPubKey.size() >= 1 && scriptPubKey[0] == OP_RETURN && scriptPubKey.IsPushOnly(scriptPubKey.begin()+1)) {
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     182                 :          0 :         return TxoutType::NULL_DATA;
     183                 :            :     }
     184                 :            : 
     185                 :          0 :     std::vector<unsigned char> data;
     186 [ #  # ][ #  # ]:          0 :     if (MatchPayToPubkey(scriptPubKey, data)) {
     187         [ #  # ]:          0 :         vSolutionsRet.push_back(std::move(data));
     188                 :          0 :         return TxoutType::PUBKEY;
     189                 :            :     }
     190                 :            : 
     191 [ #  # ][ #  # ]:          0 :     if (MatchPayToPubkeyHash(scriptPubKey, data)) {
     192         [ #  # ]:          0 :         vSolutionsRet.push_back(std::move(data));
     193                 :          0 :         return TxoutType::PUBKEYHASH;
     194                 :            :     }
     195                 :            : 
     196                 :            :     int required;
     197                 :          0 :     std::vector<std::vector<unsigned char>> keys;
     198 [ #  # ][ #  # ]:          0 :     if (MatchMultisig(scriptPubKey, required, keys)) {
     199 [ #  # ][ #  # ]:          0 :         vSolutionsRet.push_back({static_cast<unsigned char>(required)}); // safe as required is in range 1..20
     200         [ #  # ]:          0 :         vSolutionsRet.insert(vSolutionsRet.end(), keys.begin(), keys.end());
     201 [ #  # ][ #  # ]:          0 :         vSolutionsRet.push_back({static_cast<unsigned char>(keys.size())}); // safe as size is in range 1..20
     202                 :          0 :         return TxoutType::MULTISIG;
     203                 :            :     }
     204                 :            : 
     205                 :          0 :     vSolutionsRet.clear();
     206                 :          0 :     return TxoutType::NONSTANDARD;
     207                 :          0 : }
     208                 :            : 
     209                 :          0 : CScript GetScriptForRawPubKey(const CPubKey& pubKey)
     210                 :            : {
     211 [ #  # ][ #  # ]:          0 :     return CScript() << std::vector<unsigned char>(pubKey.begin(), pubKey.end()) << OP_CHECKSIG;
         [ #  # ][ #  # ]
         [ #  # ][ #  # ]
     212                 :          0 : }
     213                 :            : 
     214                 :          0 : CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys)
     215                 :            : {
     216                 :          0 :     CScript script;
     217                 :            : 
     218         [ #  # ]:          0 :     script << nRequired;
     219         [ #  # ]:          0 :     for (const CPubKey& key : keys)
     220 [ #  # ][ #  # ]:          0 :         script << ToByteVector(key);
     221 [ #  # ][ #  # ]:          0 :     script << keys.size() << OP_CHECKMULTISIG;
     222                 :            : 
     223                 :          0 :     return script;
     224         [ #  # ]:          0 : }

Generated by: LCOV version 1.14