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