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