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 : 11329 : static bool MatchPayToPubkey(const CScript& script, valtype& pubkey)
36 : : {
37 [ + + ][ + + ]: 11329 : if (script.size() == CPubKey::SIZE + 2 && script[0] == CPubKey::SIZE && script.back() == OP_CHECKSIG) {
[ + + ]
38 [ + - ]: 229 : pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::SIZE + 1);
39 : 229 : return CPubKey::ValidSize(pubkey);
40 : : }
41 [ + + ][ + + ]: 11100 : if (script.size() == CPubKey::COMPRESSED_SIZE + 2 && script[0] == CPubKey::COMPRESSED_SIZE && script.back() == OP_CHECKSIG) {
[ + + ]
42 [ - + ]: 460 : pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::COMPRESSED_SIZE + 1);
43 : 460 : return CPubKey::ValidSize(pubkey);
44 : : }
45 : 10640 : return false;
46 : 11329 : }
47 : :
48 : 10943 : static bool MatchPayToPubkeyHash(const CScript& script, valtype& pubkeyhash)
49 : : {
50 [ + + ][ + + ]: 10943 : if (script.size() == 25 && script[0] == OP_DUP && script[1] == OP_HASH160 && script[2] == 20 && script[23] == OP_EQUALVERIFY && script[24] == OP_CHECKSIG) {
[ + - ][ + - ]
[ + - ][ - + ]
51 [ - + ]: 2100 : pubkeyhash = valtype(script.begin () + 3, script.begin() + 23);
52 : 2100 : return true;
53 : : }
54 : 8843 : return false;
55 : 10943 : }
56 : :
57 : : /** Test for "small positive integer" script opcodes - OP_1 through OP_16. */
58 : 7624 : static constexpr bool IsSmallInteger(opcodetype opcode)
59 : : {
60 [ + + ]: 7624 : 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 : 7624 : static std::optional<int> GetScriptNumber(opcodetype opcode, valtype data, int min, int max)
66 : : {
67 : : int count;
68 [ + + ]: 7624 : if (IsSmallInteger(opcode)) {
69 : 3156 : count = CScript::DecodeOP_N(opcode);
70 [ + + ]: 7624 : } else if (IsPushdataOp(opcode)) {
71 [ + + ]: 3002 : if (!CheckMinimalPush(data, opcode)) return {};
72 : : try {
73 [ + + ][ + - ]: 2270 : count = CScriptNum(data, /* fRequireMinimal = */ true).getint();
74 [ + - ]: 2270 : } catch (const scriptnum_error&) {
75 : 1088 : return {};
76 : 1088 : }
77 : 1182 : } else {
78 : 1466 : return {};
79 : : }
80 [ + + ][ + + ]: 4338 : if (count < min || count > max) return {};
81 : 3444 : return count;
82 : 8712 : }
83 : :
84 : 8843 : static bool MatchMultisig(const CScript& script, int& required_sigs, std::vector<valtype>& pubkeys)
85 : : {
86 : : opcodetype opcode;
87 : 8843 : valtype data;
88 : :
89 [ + - ]: 8843 : CScript::const_iterator it = script.begin();
90 [ + - ][ + - ]: 8843 : if (script.size() < 1 || script.back() != OP_CHECKMULTISIG) return false;
[ + - ][ + + ]
91 : :
92 [ + - ][ + + ]: 4819 : if (!script.GetOp(it, opcode, data)) return false;
93 [ + - ][ + - ]: 4429 : auto req_sigs = GetScriptNumber(opcode, data, 1, MAX_PUBKEYS_PER_MULTISIG);
94 [ + + ]: 4429 : if (!req_sigs) return false;
95 : 3195 : required_sigs = *req_sigs;
96 [ + - ][ + + ]: 5764 : while (script.GetOp(it, opcode, data) && CPubKey::ValidSize(data)) {
[ + - ][ + + ]
97 [ + - ]: 67 : pubkeys.emplace_back(std::move(data));
98 : : }
99 [ + - ][ + - ]: 3195 : auto num_keys = GetScriptNumber(opcode, data, required_sigs, MAX_PUBKEYS_PER_MULTISIG);
100 [ + + ]: 3195 : if (!num_keys) return false;
101 [ + + ]: 249 : if (pubkeys.size() != static_cast<unsigned long>(*num_keys)) return false;
102 : :
103 [ + - ][ + - ]: 32 : return (it + 1 == script.end());
[ + - ]
104 : 8843 : }
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 : 20793 : TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned char>>& vSolutionsRet)
141 : : {
142 : 20793 : 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 [ + + ]: 20793 : if (scriptPubKey.IsPayToScriptHash())
147 : : {
148 [ + - ]: 941 : std::vector<unsigned char> hashBytes(scriptPubKey.begin()+2, scriptPubKey.begin()+22);
149 [ + - ]: 941 : vSolutionsRet.push_back(hashBytes);
150 : 941 : return TxoutType::SCRIPTHASH;
151 : 941 : }
152 : :
153 : : int witnessversion;
154 : 19852 : std::vector<unsigned char> witnessprogram;
155 [ + - ][ + + ]: 19852 : if (scriptPubKey.IsWitnessProgram(witnessversion, witnessprogram)) {
156 [ + + ][ + + ]: 8321 : if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_KEYHASH_SIZE) {
157 [ + - ]: 668 : vSolutionsRet.push_back(std::move(witnessprogram));
158 : 668 : return TxoutType::WITNESS_V0_KEYHASH;
159 : : }
160 [ + + ][ + + ]: 7653 : if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_SCRIPTHASH_SIZE) {
161 [ + - ]: 3179 : vSolutionsRet.push_back(std::move(witnessprogram));
162 : 3179 : return TxoutType::WITNESS_V0_SCRIPTHASH;
163 : : }
164 [ + + ][ + + ]: 4474 : if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE) {
165 [ + - ]: 3417 : vSolutionsRet.push_back(std::move(witnessprogram));
166 : 3417 : return TxoutType::WITNESS_V1_TAPROOT;
167 : : }
168 [ + + ]: 1057 : if (witnessversion != 0) {
169 [ + - ][ + - ]: 846 : vSolutionsRet.push_back(std::vector<unsigned char>{(unsigned char)witnessversion});
170 [ + - ]: 846 : vSolutionsRet.push_back(std::move(witnessprogram));
171 : 846 : return TxoutType::WITNESS_UNKNOWN;
172 : : }
173 : 211 : 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 [ + - ][ + - ]: 13766 : if (scriptPubKey.size() >= 1 && scriptPubKey[0] == OP_RETURN && scriptPubKey.IsPushOnly(scriptPubKey.begin()+1)) {
[ + - ][ + + ]
[ + - ][ + - ]
[ + - ][ + + ]
182 : 202 : return TxoutType::NULL_DATA;
183 : : }
184 : :
185 : 11329 : std::vector<unsigned char> data;
186 [ + - ][ + + ]: 11329 : if (MatchPayToPubkey(scriptPubKey, data)) {
187 [ + - ]: 386 : vSolutionsRet.push_back(std::move(data));
188 : 386 : return TxoutType::PUBKEY;
189 : : }
190 : :
191 [ + - ][ + + ]: 10943 : if (MatchPayToPubkeyHash(scriptPubKey, data)) {
192 [ + - ]: 2100 : vSolutionsRet.push_back(std::move(data));
193 : 2100 : return TxoutType::PUBKEYHASH;
194 : : }
195 : :
196 : : int required;
197 : 8843 : std::vector<std::vector<unsigned char>> keys;
198 [ + - ][ + + ]: 8843 : if (MatchMultisig(scriptPubKey, required, keys)) {
199 [ + - ][ + - ]: 32 : vSolutionsRet.push_back({static_cast<unsigned char>(required)}); // safe as required is in range 1..20
200 [ + - ]: 32 : vSolutionsRet.insert(vSolutionsRet.end(), keys.begin(), keys.end());
201 [ + - ][ - + ]: 32 : vSolutionsRet.push_back({static_cast<unsigned char>(keys.size())}); // safe as size is in range 1..20
202 : 32 : return TxoutType::MULTISIG;
203 : : }
204 : :
205 : 8811 : vSolutionsRet.clear();
206 : 8811 : return TxoutType::NONSTANDARD;
207 : 20793 : }
208 : :
209 : 27420 : CScript GetScriptForRawPubKey(const CPubKey& pubKey)
210 : : {
211 [ + - ][ + - ]: 27420 : return CScript() << std::vector<unsigned char>(pubKey.begin(), pubKey.end()) << OP_CHECKSIG;
[ - + ][ + - ]
[ + - ][ + - ]
212 : 0 : }
213 : :
214 : 13242 : CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys)
215 : : {
216 : 13242 : CScript script;
217 : :
218 [ + - ]: 13242 : script << nRequired;
219 [ + + ]: 67072 : for (const CPubKey& key : keys)
220 [ + - ][ + - ]: 53830 : script << ToByteVector(key);
221 [ + - ][ + - ]: 13242 : script << keys.size() << OP_CHECKMULTISIG;
222 : :
223 : 13242 : return script;
224 [ + - ]: 13242 : }
|
