Bitcoin Core  27.99.0
P2P Digital Currency
solver.cpp
Go to the documentation of this file.
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 
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 
58 static constexpr bool IsSmallInteger(opcodetype opcode)
59 {
60  return opcode >= OP_1 && opcode <= OP_16;
61 }
62 
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));
159  }
160  if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_SCRIPTHASH_SIZE) {
161  vSolutionsRet.push_back(std::move(witnessprogram));
163  }
164  if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE) {
165  vSolutionsRet.push_back(std::move(witnessprogram));
167  }
168  if (witnessversion != 0) {
169  vSolutionsRet.push_back(std::vector<unsigned char>{(unsigned char)witnessversion});
170  vSolutionsRet.push_back(std::move(witnessprogram));
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 
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 }
std::vector< unsigned char > valtype
Definition: addresstype.cpp:18
An encapsulated public key.
Definition: pubkey.h:34
const unsigned char * end() const
Definition: pubkey.h:115
static constexpr unsigned int COMPRESSED_SIZE
Definition: pubkey.h:40
static constexpr unsigned int SIZE
secp256k1:
Definition: pubkey.h:39
static bool ValidSize(const std::vector< unsigned char > &vch)
Definition: pubkey.h:77
const unsigned char * begin() const
Definition: pubkey.h:114
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:414
bool IsPushOnly(const_iterator pc) const
Called by IsStandardTx and P2SH/BIP62 VerifyScript (which makes it consensus-critical).
Definition: script.cpp:242
bool IsPayToScriptHash() const
Definition: script.cpp:207
static int DecodeOP_N(opcodetype opcode)
Encode/decode small integers:
Definition: script.h:506
bool IsWitnessProgram(int &version, std::vector< unsigned char > &program) const
Definition: script.cpp:226
int getint() const
Definition: script.h:332
size_type size() const
Definition: prevector.h:296
iterator begin()
Definition: prevector.h:304
static constexpr size_t WITNESS_V0_KEYHASH_SIZE
Definition: interpreter.h:228
static constexpr size_t WITNESS_V0_SCRIPTHASH_SIZE
Signature hash sizes.
Definition: interpreter.h:227
static constexpr size_t WITNESS_V1_TAPROOT_SIZE
Definition: interpreter.h:229
bool CheckMinimalPush(const std::vector< unsigned char > &data, opcodetype opcode)
Definition: script.cpp:349
std::vector< unsigned char > ToByteVector(const T &in)
Definition: script.h:66
opcodetype
Script opcodes.
Definition: script.h:73
@ OP_CHECKMULTISIG
Definition: script.h:191
@ OP_CHECKSIG
Definition: script.h:189
@ OP_16
Definition: script.h:98
@ OP_NUMEQUAL
Definition: script.h:170
@ OP_DUP
Definition: script.h:124
@ OP_HASH160
Definition: script.h:186
@ OP_1
Definition: script.h:82
@ OP_CHECKSIGADD
Definition: script.h:209
@ OP_RETURN
Definition: script.h:110
@ OP_EQUALVERIFY
Definition: script.h:146
static constexpr unsigned int MAX_PUBKEYS_PER_MULTI_A
The limit of keys in OP_CHECKSIGADD-based scripts.
Definition: script.h:36
static const int MAX_PUBKEYS_PER_MULTISIG
Definition: script.h:33
static std::optional< int > GetScriptNumber(opcodetype opcode, valtype data, int min, int max)
Retrieve a minimally-encoded number in range [min,max] from an (opcode, data) pair,...
Definition: solver.cpp:65
TxoutType Solver(const CScript &scriptPubKey, std::vector< std::vector< unsigned char >> &vSolutionsRet)
Parse a scriptPubKey and identify script type for standard scripts.
Definition: solver.cpp:140
std::optional< std::pair< int, std::vector< Span< const unsigned char > > > > MatchMultiA(const CScript &script)
Definition: solver.cpp:106
static bool MatchPayToPubkeyHash(const CScript &script, valtype &pubkeyhash)
Definition: solver.cpp:48
static constexpr bool IsSmallInteger(opcodetype opcode)
Test for "small positive integer" script opcodes - OP_1 through OP_16.
Definition: solver.cpp:58
CScript GetScriptForMultisig(int nRequired, const std::vector< CPubKey > &keys)
Generate a multisig script.
Definition: solver.cpp:214
std::vector< unsigned char > valtype
Definition: solver.cpp:16
std::string GetTxnOutputType(TxoutType t)
Get the name of a TxoutType as a string.
Definition: solver.cpp:18
CScript GetScriptForRawPubKey(const CPubKey &pubKey)
Generate a P2PK script for the given pubkey.
Definition: solver.cpp:209
static bool MatchMultisig(const CScript &script, int &required_sigs, std::vector< valtype > &pubkeys)
Definition: solver.cpp:84
static bool MatchPayToPubkey(const CScript &script, valtype &pubkey)
Definition: solver.cpp:35
constexpr bool IsPushdataOp(opcodetype opcode)
Definition: solver.h:39
TxoutType
Definition: solver.h:22
@ WITNESS_V1_TAPROOT
@ WITNESS_UNKNOWN
Only for Witness versions not already defined above.
@ WITNESS_V0_SCRIPTHASH
@ NULL_DATA
unspendable OP_RETURN script that carries data
@ WITNESS_V0_KEYHASH
static int count
assert(!tx.IsCoinBase())