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