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