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