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