Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2021 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 : #ifndef BITCOIN_SCRIPT_SCRIPT_H
7 : #define BITCOIN_SCRIPT_SCRIPT_H
8 :
9 : #include <attributes.h>
10 : #include <crypto/common.h>
11 : #include <prevector.h>
12 : #include <serialize.h>
13 :
14 : #include <assert.h>
15 : #include <climits>
16 : #include <limits>
17 : #include <stdexcept>
18 : #include <stdint.h>
19 : #include <string.h>
20 : #include <string>
21 : #include <vector>
22 :
23 : // Maximum number of bytes pushable to the stack
24 : static const unsigned int MAX_SCRIPT_ELEMENT_SIZE = 520;
25 :
26 : // Maximum number of non-push operations per script
27 : static const int MAX_OPS_PER_SCRIPT = 201;
28 :
29 : // Maximum number of public keys per multisig
30 : static const int MAX_PUBKEYS_PER_MULTISIG = 20;
31 :
32 : // Maximum script length in bytes
33 : static const int MAX_SCRIPT_SIZE = 10000;
34 :
35 : // Maximum number of values on script interpreter stack
36 : static const int MAX_STACK_SIZE = 1000;
37 :
38 : // Threshold for nLockTime: below this value it is interpreted as block number,
39 : // otherwise as UNIX timestamp.
40 : static const unsigned int LOCKTIME_THRESHOLD = 500000000; // Tue Nov 5 00:53:20 1985 UTC
41 :
42 : // Maximum nLockTime. Since a lock time indicates the last invalid timestamp, a
43 : // transaction with this lock time will never be valid unless lock time
44 : // checking is disabled (by setting all input sequence numbers to
45 : // SEQUENCE_FINAL).
46 : static const uint32_t LOCKTIME_MAX = 0xFFFFFFFFU;
47 :
48 : template <typename T>
49 1507709 : std::vector<unsigned char> ToByteVector(const T& in)
50 : {
51 1507709 : return std::vector<unsigned char>(in.begin(), in.end());
52 : }
53 :
54 : /** Script opcodes */
55 : enum opcodetype
56 : {
57 : // push value
58 : OP_0 = 0x00,
59 : OP_FALSE = OP_0,
60 : OP_PUSHDATA1 = 0x4c,
61 : OP_PUSHDATA2 = 0x4d,
62 : OP_PUSHDATA4 = 0x4e,
63 : OP_1NEGATE = 0x4f,
64 : OP_RESERVED = 0x50,
65 : OP_1 = 0x51,
66 : OP_TRUE=OP_1,
67 : OP_2 = 0x52,
68 : OP_3 = 0x53,
69 : OP_4 = 0x54,
70 : OP_5 = 0x55,
71 : OP_6 = 0x56,
72 : OP_7 = 0x57,
73 : OP_8 = 0x58,
74 : OP_9 = 0x59,
75 : OP_10 = 0x5a,
76 : OP_11 = 0x5b,
77 : OP_12 = 0x5c,
78 : OP_13 = 0x5d,
79 : OP_14 = 0x5e,
80 : OP_15 = 0x5f,
81 : OP_16 = 0x60,
82 :
83 : // control
84 : OP_NOP = 0x61,
85 : OP_VER = 0x62,
86 : OP_IF = 0x63,
87 : OP_NOTIF = 0x64,
88 : OP_VERIF = 0x65,
89 : OP_VERNOTIF = 0x66,
90 : OP_ELSE = 0x67,
91 : OP_ENDIF = 0x68,
92 : OP_VERIFY = 0x69,
93 : OP_RETURN = 0x6a,
94 :
95 : // stack ops
96 : OP_TOALTSTACK = 0x6b,
97 : OP_FROMALTSTACK = 0x6c,
98 : OP_2DROP = 0x6d,
99 : OP_2DUP = 0x6e,
100 : OP_3DUP = 0x6f,
101 : OP_2OVER = 0x70,
102 : OP_2ROT = 0x71,
103 : OP_2SWAP = 0x72,
104 : OP_IFDUP = 0x73,
105 : OP_DEPTH = 0x74,
106 : OP_DROP = 0x75,
107 : OP_DUP = 0x76,
108 : OP_NIP = 0x77,
109 : OP_OVER = 0x78,
110 : OP_PICK = 0x79,
111 : OP_ROLL = 0x7a,
112 : OP_ROT = 0x7b,
113 : OP_SWAP = 0x7c,
114 : OP_TUCK = 0x7d,
115 :
116 : // splice ops
117 : OP_CAT = 0x7e,
118 : OP_SPLIT = 0x7f,
119 : OP_SIZE = 0x82,
120 :
121 : // conversion ops
122 : OP_NUM2BIN = 0x80,
123 : OP_BIN2NUM = 0x81,
124 :
125 : // bit logic
126 : OP_INVERT = 0x83,
127 : OP_AND = 0x84,
128 : OP_OR = 0x85,
129 : OP_XOR = 0x86,
130 : OP_EQUAL = 0x87,
131 : OP_EQUALVERIFY = 0x88,
132 : OP_RESERVED1 = 0x89,
133 : OP_RESERVED2 = 0x8a,
134 :
135 : // numeric
136 : OP_1ADD = 0x8b,
137 : OP_1SUB = 0x8c,
138 : OP_2MUL = 0x8d,
139 : OP_2DIV = 0x8e,
140 : OP_NEGATE = 0x8f,
141 : OP_ABS = 0x90,
142 : OP_NOT = 0x91,
143 : OP_0NOTEQUAL = 0x92,
144 :
145 : OP_ADD = 0x93,
146 : OP_SUB = 0x94,
147 : OP_MUL = 0x95,
148 : OP_DIV = 0x96,
149 : OP_MOD = 0x97,
150 : OP_LSHIFT = 0x98,
151 : OP_RSHIFT = 0x99,
152 :
153 : OP_BOOLAND = 0x9a,
154 : OP_BOOLOR = 0x9b,
155 : OP_NUMEQUAL = 0x9c,
156 : OP_NUMEQUALVERIFY = 0x9d,
157 : OP_NUMNOTEQUAL = 0x9e,
158 : OP_LESSTHAN = 0x9f,
159 : OP_GREATERTHAN = 0xa0,
160 : OP_LESSTHANOREQUAL = 0xa1,
161 : OP_GREATERTHANOREQUAL = 0xa2,
162 : OP_MIN = 0xa3,
163 : OP_MAX = 0xa4,
164 :
165 : OP_WITHIN = 0xa5,
166 :
167 : // crypto
168 : OP_RIPEMD160 = 0xa6,
169 : OP_SHA1 = 0xa7,
170 : OP_SHA256 = 0xa8,
171 : OP_HASH160 = 0xa9,
172 : OP_HASH256 = 0xaa,
173 : OP_CODESEPARATOR = 0xab,
174 : OP_CHECKSIG = 0xac,
175 : OP_CHECKSIGVERIFY = 0xad,
176 : OP_CHECKMULTISIG = 0xae,
177 : OP_CHECKMULTISIGVERIFY = 0xaf,
178 :
179 : // expansion
180 : OP_NOP1 = 0xb0,
181 : OP_CHECKLOCKTIMEVERIFY = 0xb1,
182 : OP_NOP2 = OP_CHECKLOCKTIMEVERIFY,
183 : OP_CHECKSEQUENCEVERIFY = 0xb2,
184 : OP_NOP3 = OP_CHECKSEQUENCEVERIFY,
185 : OP_NOP4 = 0xb3,
186 : OP_NOP5 = 0xb4,
187 : OP_NOP6 = 0xb5,
188 : OP_NOP7 = 0xb6,
189 : OP_NOP8 = 0xb7,
190 : OP_NOP9 = 0xb8,
191 : OP_NOP10 = 0xb9,
192 :
193 : // More crypto
194 : OP_CHECKDATASIG = 0xba,
195 : OP_CHECKDATASIGVERIFY = 0xbb,
196 :
197 : OP_INVALIDOPCODE = 0xff,
198 : };
199 :
200 : // Maximum value that an opcode can be
201 : static const unsigned int MAX_OPCODE = OP_CHECKDATASIGVERIFY;
202 :
203 : std::string GetOpName(opcodetype opcode);
204 :
205 : class scriptnum_error : public std::runtime_error
206 : {
207 : public:
208 2258 : explicit scriptnum_error(const std::string& str) : std::runtime_error(str) {}
209 : };
210 :
211 : class CScriptNum
212 : {
213 : /**
214 : * Numeric opcodes (OP_1ADD, etc) are restricted to operating on 4-byte integers.
215 : * The semantics are subtle, though: operands must be in the range [-2^31 +1...2^31 -1],
216 : * but results may overflow (and are valid as long as they are not used in a subsequent
217 : * numeric operation). CScriptNum enforces those semantics by storing results as
218 : * an int64 and allowing out-of-range values to be returned as a vector of bytes but
219 : * throwing an exception if arithmetic is done or the result is interpreted as an integer.
220 : */
221 : public:
222 :
223 649481 : explicit CScriptNum(const int64_t& n)
224 324739 : {
225 324742 : m_value = n;
226 649481 : }
227 :
228 : static const size_t nDefaultMaxNumSize = 4;
229 :
230 226263 : explicit CScriptNum(const std::vector<unsigned char>& vch, bool fRequireMinimal,
231 : const size_t nMaxNumSize = nDefaultMaxNumSize)
232 113131 : {
233 113132 : if (vch.size() > nMaxNumSize) {
234 1129 : throw scriptnum_error("script number overflow");
235 : }
236 112802 : if (fRequireMinimal && !IsMinimallyEncoded(vch, nMaxNumSize)) {
237 799 : throw scriptnum_error("non-minimally encoded script number");
238 : }
239 112003 : m_value = set_vch(vch);
240 226263 : }
241 :
242 : static bool IsMinimallyEncoded(
243 : const std::vector<uint8_t>& vch,
244 : const size_t nMaxNumSize = nDefaultMaxNumSize);
245 :
246 : static bool MinimallyEncode(std::vector<uint8_t> &data);
247 :
248 20116 : inline bool operator==(const int64_t& rhs) const { return m_value == rhs; }
249 12642 : inline bool operator!=(const int64_t& rhs) const { return m_value != rhs; }
250 5998 : inline bool operator<=(const int64_t& rhs) const { return m_value <= rhs; }
251 28695 : inline bool operator< (const int64_t& rhs) const { return m_value < rhs; }
252 6276 : inline bool operator>=(const int64_t& rhs) const { return m_value >= rhs; }
253 16744 : inline bool operator> (const int64_t& rhs) const { return m_value > rhs; }
254 :
255 16397 : inline bool operator==(const CScriptNum& rhs) const { return operator==(rhs.m_value); }
256 3682 : inline bool operator!=(const CScriptNum& rhs) const { return operator!=(rhs.m_value); }
257 3190 : inline bool operator<=(const CScriptNum& rhs) const { return operator<=(rhs.m_value); }
258 3380 : inline bool operator< (const CScriptNum& rhs) const { return operator< (rhs.m_value); }
259 2946 : inline bool operator>=(const CScriptNum& rhs) const { return operator>=(rhs.m_value); }
260 3067 : inline bool operator> (const CScriptNum& rhs) const { return operator> (rhs.m_value); }
261 :
262 4862 : inline CScriptNum operator+( const int64_t& rhs) const { return CScriptNum(m_value + rhs);}
263 5727 : inline CScriptNum operator-( const int64_t& rhs) const { return CScriptNum(m_value - rhs);}
264 2054 : inline CScriptNum operator+( const CScriptNum& rhs) const { return operator+(rhs.m_value); }
265 2919 : inline CScriptNum operator-( const CScriptNum& rhs) const { return operator-(rhs.m_value); }
266 :
267 518 : inline CScriptNum operator/(const int64_t& rhs) const { return CScriptNum(m_value / rhs); }
268 239 : inline CScriptNum operator%(const int64_t& rhs) const { return CScriptNum(m_value % rhs); }
269 518 : inline CScriptNum operator/(const CScriptNum& rhs) const { return operator/(rhs.m_value); }
270 239 : inline CScriptNum operator%(const CScriptNum& rhs) const { return operator%(rhs.m_value); }
271 :
272 174 : inline CScriptNum& operator+=( const CScriptNum& rhs) { return operator+=(rhs.m_value); }
273 79 : inline CScriptNum& operator-=( const CScriptNum& rhs) { return operator-=(rhs.m_value); }
274 :
275 11701 : inline CScriptNum operator&( const int64_t& rhs) const { return CScriptNum(m_value & rhs);}
276 : inline CScriptNum operator&( const CScriptNum& rhs) const { return operator&(rhs.m_value); }
277 :
278 : inline CScriptNum& operator&=( const CScriptNum& rhs) { return operator&=(rhs.m_value); }
279 :
280 1507 : inline CScriptNum operator-() const
281 : {
282 1507 : assert(m_value != std::numeric_limits<int64_t>::min());
283 1507 : return CScriptNum(-m_value);
284 : }
285 :
286 14758 : inline CScriptNum& operator=( const int64_t& rhs)
287 : {
288 14758 : m_value = rhs;
289 14758 : return *this;
290 : }
291 :
292 174 : inline CScriptNum& operator+=( const int64_t& rhs)
293 : {
294 174 : assert(rhs == 0 || (rhs > 0 && m_value <= std::numeric_limits<int64_t>::max() - rhs) ||
295 : (rhs < 0 && m_value >= std::numeric_limits<int64_t>::min() - rhs));
296 174 : m_value += rhs;
297 174 : return *this;
298 : }
299 :
300 79 : inline CScriptNum& operator-=( const int64_t& rhs)
301 : {
302 79 : assert(rhs == 0 || (rhs > 0 && m_value >= std::numeric_limits<int64_t>::min() + rhs) ||
303 : (rhs < 0 && m_value <= std::numeric_limits<int64_t>::max() + rhs));
304 79 : m_value -= rhs;
305 79 : return *this;
306 : }
307 :
308 : inline CScriptNum& operator&=( const int64_t& rhs)
309 : {
310 : m_value &= rhs;
311 : return *this;
312 : }
313 :
314 92654 : int getint() const
315 : {
316 92654 : if (m_value > std::numeric_limits<int>::max())
317 1225 : return std::numeric_limits<int>::max();
318 91429 : else if (m_value < std::numeric_limits<int>::min())
319 874 : return std::numeric_limits<int>::min();
320 90555 : return m_value;
321 92654 : }
322 :
323 113 : int64_t GetInt64() const { return m_value; }
324 :
325 309794 : std::vector<unsigned char> getvch() const
326 : {
327 309794 : return serialize(m_value);
328 : }
329 :
330 636602 : static std::vector<unsigned char> serialize(const int64_t& value)
331 : {
332 636602 : if(value == 0)
333 7539 : return std::vector<unsigned char>();
334 :
335 629063 : std::vector<unsigned char> result;
336 629063 : const bool neg = value < 0;
337 629063 : uint64_t absvalue = neg ? ~static_cast<uint64_t>(value) + 1 : static_cast<uint64_t>(value);
338 :
339 1472377 : while(absvalue)
340 : {
341 843314 : result.push_back(absvalue & 0xff);
342 843314 : absvalue >>= 8;
343 : }
344 :
345 : // - If the most significant byte is >= 0x80 and the value is positive, push a
346 : // new zero-byte to make the significant byte < 0x80 again.
347 :
348 : // - If the most significant byte is >= 0x80 and the value is negative, push a
349 : // new 0x80 byte that will be popped off when converting to an integral.
350 :
351 : // - If the most significant byte is < 0x80 and the value is negative, add
352 : // 0x80 to it, since it will be subtracted and interpreted as a negative when
353 : // converting to an integral.
354 :
355 629063 : if (result.back() & 0x80)
356 94736 : result.push_back(neg ? 0x80 : 0);
357 534327 : else if (neg)
358 5766 : result.back() |= 0x80;
359 :
360 629063 : return result;
361 1265665 : }
362 :
363 : private:
364 112001 : static int64_t set_vch(const std::vector<unsigned char>& vch)
365 : {
366 112001 : if (vch.empty())
367 39210 : return 0;
368 :
369 72791 : int64_t result = 0;
370 182611 : for (size_t i = 0; i != vch.size(); ++i)
371 109820 : result |= static_cast<int64_t>(vch[i]) << 8*i;
372 :
373 : // If the input vector's most significant byte is 0x80, remove it from
374 : // the result's msb and return a negative.
375 72791 : if (vch.back() & 0x80)
376 3240 : return -((int64_t)(result & ~(0x80ULL << (8 * (vch.size() - 1)))));
377 :
378 69551 : return result;
379 112001 : }
380 :
381 : int64_t m_value;
382 : };
383 :
384 : /**
385 : * We use a prevector for the script to reduce the considerable memory overhead
386 : * of vectors in cases where they normally contain a small number of small elements.
387 : * Tests in October 2015 showed use of this reduced dbcache memory usage by 23%
388 : * and made an initial sync 13% faster.
389 : */
390 : typedef prevector<28, unsigned char> CScriptBase;
391 :
392 : bool GetScriptOp(CScriptBase::const_iterator& pc, CScriptBase::const_iterator end, opcodetype& opcodeRet, std::vector<unsigned char>* pvchRet);
393 :
394 : /** Serialized script, used inside transaction inputs and outputs */
395 : class CScript : public CScriptBase
396 : {
397 : protected:
398 418530 : CScript& push_int64(int64_t n)
399 : {
400 418530 : if (n == -1 || (n >= 1 && n <= 16))
401 : {
402 87651 : push_back(n + (OP_1 - 1));
403 87651 : }
404 330879 : else if (n == 0)
405 : {
406 4062 : push_back(OP_0);
407 4062 : }
408 : else
409 : {
410 326817 : *this << CScriptNum::serialize(n);
411 : }
412 418530 : return *this;
413 0 : }
414 : public:
415 252308996 : CScript() { }
416 2181515 : CScript(const_iterator pbegin, const_iterator pend) : CScriptBase(pbegin, pend) { }
417 560223 : CScript(std::vector<unsigned char>::const_iterator pbegin, std::vector<unsigned char>::const_iterator pend) : CScriptBase(pbegin, pend) { }
418 516 : CScript(const unsigned char* pbegin, const unsigned char* pend) : CScriptBase(pbegin, pend) { }
419 :
420 152163028 : SERIALIZE_METHODS(CScript, obj) { READWRITEAS(CScriptBase, obj); }
421 :
422 4 : explicit CScript(int64_t b) { operator<<(b); }
423 100000 : explicit CScript(opcodetype b) { operator<<(b); }
424 : explicit CScript(const CScriptNum& b) { operator<<(b); }
425 : // delete non-existent constructor to defend against future introduction
426 : // e.g. via prevector
427 : explicit CScript(const std::vector<unsigned char>& b) = delete;
428 :
429 : /** Delete non-existent operator to defend against future introduction */
430 : CScript& operator<<(const CScript& b) = delete;
431 :
432 418530 : CScript& operator<<(int64_t b) LIFETIMEBOUND { return push_int64(b); }
433 :
434 4347700 : CScript& operator<<(opcodetype opcode) LIFETIMEBOUND
435 : {
436 4347700 : if (opcode < 0 || opcode > 0xff)
437 0 : throw std::runtime_error("CScript::operator<<(): invalid opcode");
438 4347700 : insert(end(), (unsigned char)opcode);
439 4347700 : return *this;
440 0 : }
441 :
442 46599 : CScript& operator<<(const CScriptNum& b) LIFETIMEBOUND
443 : {
444 46599 : *this << b.getvch();
445 46599 : return *this;
446 0 : }
447 :
448 3808038 : CScript& operator<<(const std::vector<unsigned char>& b) LIFETIMEBOUND
449 : {
450 3808038 : if (b.size() < OP_PUSHDATA1)
451 : {
452 3787225 : insert(end(), (unsigned char)b.size());
453 3787225 : }
454 20813 : else if (b.size() <= 0xff)
455 : {
456 20409 : insert(end(), OP_PUSHDATA1);
457 20409 : insert(end(), (unsigned char)b.size());
458 20409 : }
459 404 : else if (b.size() <= 0xffff)
460 : {
461 404 : insert(end(), OP_PUSHDATA2);
462 : uint8_t _data[2];
463 404 : WriteLE16(_data, b.size());
464 404 : insert(end(), _data, _data + sizeof(_data));
465 404 : }
466 : else
467 : {
468 0 : insert(end(), OP_PUSHDATA4);
469 : uint8_t _data[4];
470 0 : WriteLE32(_data, b.size());
471 0 : insert(end(), _data, _data + sizeof(_data));
472 : }
473 3808038 : insert(end(), b.begin(), b.end());
474 3808038 : return *this;
475 : }
476 :
477 8503359 : bool GetOp(const_iterator& pc, opcodetype& opcodeRet, std::vector<unsigned char>& vchRet) const
478 : {
479 8503359 : return GetScriptOp(pc, end(), opcodeRet, &vchRet);
480 : }
481 :
482 42219929 : bool GetOp(const_iterator& pc, opcodetype& opcodeRet) const
483 : {
484 42219929 : return GetScriptOp(pc, end(), opcodeRet, nullptr);
485 : }
486 :
487 : /** Encode/decode small integers: */
488 3862 : static int DecodeOP_N(opcodetype opcode)
489 : {
490 3862 : if (opcode == OP_0)
491 0 : return 0;
492 3862 : assert(opcode >= OP_1 && opcode <= OP_16);
493 3862 : return (int)opcode - (int)(OP_1 - 1);
494 3862 : }
495 0 : static opcodetype EncodeOP_N(int n)
496 : {
497 0 : assert(n >= 0 && n <= 16);
498 0 : if (n == 0)
499 0 : return OP_0;
500 0 : return (opcodetype)(OP_1+n-1);
501 0 : }
502 :
503 : /**
504 : * Pre-version-0.6, Bitcoin always counted CHECKMULTISIGs
505 : * as 20 sigops. With pay-to-script-hash, that changed:
506 : * CHECKMULTISIGs serialized in scriptSigs are
507 : * counted more accurately, assuming they are of the form
508 : * ... OP_N CHECKMULTISIG ...
509 : */
510 : unsigned int GetSigOpCount(bool fAccurate) const;
511 :
512 : /**
513 : * Accurately count sigOps, including sigOps in
514 : * pay-to-script-hash transactions:
515 : */
516 : unsigned int GetSigOpCount(const CScript& scriptSig) const;
517 :
518 : bool IsPayToPublicKeyHash() const;
519 :
520 : bool IsPayToScriptHash() const;
521 :
522 : /** Used for obsolete pay-to-pubkey addresses indexing. */
523 : bool IsPayToPublicKey() const;
524 :
525 : /** Called by IsStandardTx and P2SH/BIP62 VerifyScript (which makes it consensus-critical). */
526 : bool IsPushOnly(const_iterator pc) const;
527 : bool IsPushOnly() const;
528 :
529 : /**
530 : * Returns whether the script is guaranteed to fail at execution,
531 : * regardless of the initial stack. This allows outputs to be pruned
532 : * instantly when entering the UTXO set.
533 : */
534 18094630 : bool IsUnspendable() const
535 : {
536 18094630 : return (size() > 0 && *begin() == OP_RETURN) || (size() > MAX_SCRIPT_SIZE);
537 : }
538 :
539 108739583 : void clear()
540 : {
541 : // The default prevector::clear() does not release memory
542 108739583 : CScriptBase::clear();
543 108739583 : shrink_to_fit();
544 108739583 : }
545 : };
546 :
547 : bool CheckMinimalPush(const std::vector<unsigned char>& data, opcodetype opcode);
548 :
549 : /** Build a script by concatenating other scripts, or any argument accepted by CScript::operator<<. */
550 : template<typename... Ts>
551 1162 : CScript BuildScript(Ts&&... inputs)
552 : {
553 1162 : CScript ret;
554 1162 : int cnt{0};
555 :
556 5112 : ([&ret, &cnt] (Ts&& input) {
557 : if constexpr (std::is_same_v<std::remove_cv_t<std::remove_reference_t<Ts>>, CScript>) {
558 : // If it is a CScript, extend ret with it. Move or copy the first element instead.
559 852 : if (cnt == 0) {
560 400 : ret = std::forward<Ts>(input);
561 400 : } else {
562 452 : ret.insert(ret.end(), input.begin(), input.end());
563 : }
564 : } else {
565 : // Otherwise invoke CScript::operator<<.
566 1936 : ret << input;
567 : }
568 2788 : cnt++;
569 3950 : } (std::forward<Ts>(inputs)), ...);
570 :
571 1162 : return ret;
572 1162 : }
573 :
574 : #endif // BITCOIN_SCRIPT_SCRIPT_H
|
