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