script.h
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 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 inline bool operator< (const int64_t& rhs) const { return m_value < rhs; } 276 inline bool operator>=(const int64_t& rhs) const { return m_value >= rhs; } 277 inline bool operator> (const int64_t& rhs) const { return m_value > rhs; } 278 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 inline bool operator< (const CScriptNum& rhs) const { return operator< (rhs.m_value); } 283 inline bool operator>=(const CScriptNum& rhs) const { return operator>=(rhs.m_value); } 284 inline bool operator> (const CScriptNum& rhs) const { 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 int64_t& rhs) const { return CScriptNum(m_value - rhs);} 288 inline CScriptNum operator+( const CScriptNum& rhs) const { return operator+(rhs.m_value); } 289 inline CScriptNum operator-( const CScriptNum& rhs) const { return operator-(rhs.m_value); } 290 291 inline CScriptNum& operator+=( const CScriptNum& rhs) { return operator+=(rhs.m_value); } 292 inline CScriptNum& operator-=( const CScriptNum& rhs) { return operator-=(rhs.m_value); } 293 294 inline CScriptNum operator&( const int64_t& rhs) const { return CScriptNum(m_value & rhs);} 295 inline CScriptNum operator&( const CScriptNum& rhs) const { return operator&(rhs.m_value); } 296 297 inline CScriptNum& operator&=( const CScriptNum& rhs) { return operator&=(rhs.m_value); } 298 299 inline CScriptNum operator-() const 300 { 301 assert(m_value != std::numeric_limits<int64_t>::min()); 302 return CScriptNum(-m_value); 303 } 304 305 inline CScriptNum& operator=( const int64_t& rhs) 306 { 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>::max() - rhs) || 314 (rhs < 0 && m_value >= std::numeric_limits<int64_t>::min() - rhs)); 315 m_value += rhs; 316 return *this; 317 } 318 319 inline CScriptNum& operator-=( const int64_t& rhs) 320 { 321 assert(rhs == 0 || (rhs > 0 && m_value >= std::numeric_limits<int64_t>::min() + rhs) || 322 (rhs < 0 && m_value <= std::numeric_limits<int64_t>::max() + rhs)); 323 m_value -= rhs; 324 return *this; 325 } 326 327 inline CScriptNum& operator&=( const int64_t& rhs) 328 { 329 m_value &= rhs; 330 return *this; 331 } 332 333 int getint() const 334 { 335 if (m_value > std::numeric_limits<int>::max()) 336 return std::numeric_limits<int>::max(); 337 else if (m_value < std::numeric_limits<int>::min()) 338 return std::numeric_limits<int>::min(); 339 return m_value; 340 } 341 342 int64_t GetInt64() const { return m_value; } 343 344 std::vector<unsigned char> getvch() const 345 { 346 return serialize(m_value); 347 } 348 349 static std::vector<unsigned char> serialize(const int64_t& value) 350 { 351 if(value == 0) 352 return std::vector<unsigned char>(); 353 354 std::vector<unsigned char> result; 355 const bool neg = value < 0; 356 uint64_t absvalue = neg ? ~static_cast<uint64_t>(value) + 1 : static_cast<uint64_t>(value); 357 358 while(absvalue) 359 { 360 result.push_back(absvalue & 0xff); 361 absvalue >>= 8; 362 } 363 364 // - If the most significant byte is >= 0x80 and the value is positive, push a 365 // new zero-byte to make the significant byte < 0x80 again. 366 367 // - If the most significant byte is >= 0x80 and the value is negative, push a 368 // new 0x80 byte that will be popped off when converting to an integral. 369 370 // - If the most significant byte is < 0x80 and the value is negative, add 371 // 0x80 to it, since it will be subtracted and interpreted as a negative when 372 // converting to an integral. 373 374 if (result.back() & 0x80) 375 result.push_back(neg ? 0x80 : 0); 376 else if (neg) 377 result.back() |= 0x80; 378 379 return result; 380 } 381 382 private: 383 static int64_t set_vch(const std::vector<unsigned char>& vch) 384 { 385 if (vch.empty()) 386 return 0; 387 388 int64_t result = 0; 389 for (size_t i = 0; i != vch.size(); ++i) 390 result |= static_cast<int64_t>(vch[i]) << 8*i; 391 392 // If the input vector's most significant byte is 0x80, remove it from 393 // the result's msb and return a negative. 394 if (vch.back() & 0x80) 395 return -((int64_t)(result & ~(0x80ULL << (8 * (vch.size() - 1))))); 396 397 return result; 398 } 399 400 int64_t m_value; 401 }; 402 403 /** 404 * We use a prevector for the script to reduce the considerable memory overhead 405 * of vectors in cases where they normally contain a small number of small elements. 406 * Tests in October 2015 showed use of this reduced dbcache memory usage by 23% 407 * and made an initial sync 13% faster. 408 */ 409 typedef prevector<28, unsigned char> CScriptBase; 410 411 bool GetScriptOp(CScriptBase::const_iterator& pc, CScriptBase::const_iterator end, opcodetype& opcodeRet, std::vector<unsigned char>* pvchRet); 412 413 /** Serialized script, used inside transaction inputs and outputs */ 414 class CScript : public CScriptBase 415 { 416 private: 417 inline void AppendDataSize(const uint32_t size) 418 { 419 if (size < OP_PUSHDATA1) { 420 insert(end(), static_cast<value_type>(size)); 421 } else if (size <= 0xff) { 422 insert(end(), OP_PUSHDATA1); 423 insert(end(), static_cast<value_type>(size)); 424 } else if (size <= 0xffff) { 425 insert(end(), OP_PUSHDATA2); 426 value_type data[2]; 427 WriteLE16(data, size); 428 insert(end(), std::cbegin(data), std::cend(data)); 429 } else { 430 insert(end(), OP_PUSHDATA4); 431 value_type data[4]; 432 WriteLE32(data, size); 433 insert(end(), std::cbegin(data), std::cend(data)); 434 } 435 } 436 437 void AppendData(std::span<const value_type> data) 438 { 439 insert(end(), data.begin(), data.end()); 440 } 441 442 protected: 443 CScript& push_int64(int64_t n) 444 { 445 if (n == -1 || (n >= 1 && n <= 16)) 446 { 447 push_back(n + (OP_1 - 1)); 448 } 449 else if (n == 0) 450 { 451 push_back(OP_0); 452 } 453 else 454 { 455 *this << CScriptNum::serialize(n); 456 } 457 return *this; 458 } 459 460 public: 461 CScript() = default; 462 template <std::input_iterator InputIterator> 463 CScript(InputIterator first, InputIterator last) : CScriptBase{first, last} { } 464 465 SERIALIZE_METHODS(CScript, obj) { READWRITE(AsBase<CScriptBase>(obj)); } 466 467 explicit CScript(int64_t b) { operator<<(b); } 468 explicit CScript(opcodetype b) { operator<<(b); } 469 explicit CScript(const CScriptNum& b) { operator<<(b); } 470 // delete non-existent constructor to defend against future introduction 471 // e.g. via prevector 472 explicit CScript(const std::vector<unsigned char>& b) = delete; 473 474 /** Delete non-existent operator to defend against future introduction */ 475 CScript& operator<<(const CScript& b) = delete; 476 477 CScript& operator<<(int64_t b) LIFETIMEBOUND { return push_int64(b); } 478 479 CScript& operator<<(opcodetype opcode) LIFETIMEBOUND 480 { 481 if (opcode < 0 || opcode > 0xff) 482 throw std::runtime_error("CScript::operator<<(): invalid opcode"); 483 insert(end(), (unsigned char)opcode); 484 return *this; 485 } 486 487 CScript& operator<<(const CScriptNum& b) LIFETIMEBOUND 488 { 489 *this << b.getvch(); 490 return *this; 491 } 492 493 CScript& operator<<(std::span<const std::byte> b) LIFETIMEBOUND 494 { 495 AppendDataSize(b.size()); 496 AppendData({reinterpret_cast<const value_type*>(b.data()), b.size()}); 497 return *this; 498 } 499 500 // For compatibility reasons. In new code, prefer using std::byte instead of uint8_t. 501 CScript& operator<<(std::span<const value_type> b) LIFETIMEBOUND 502 { 503 return *this << std::as_bytes(b); 504 } 505 506 bool GetOp(const_iterator& pc, opcodetype& opcodeRet, std::vector<unsigned char>& vchRet) const 507 { 508 return GetScriptOp(pc, end(), opcodeRet, &vchRet); 509 } 510 511 bool GetOp(const_iterator& pc, opcodetype& opcodeRet) const 512 { 513 return GetScriptOp(pc, end(), opcodeRet, nullptr); 514 } 515 516 /** Encode/decode small integers: */ 517 static int DecodeOP_N(opcodetype opcode) 518 { 519 if (opcode == OP_0) 520 return 0; 521 assert(opcode >= OP_1 && opcode <= OP_16); 522 return (int)opcode - (int)(OP_1 - 1); 523 } 524 static opcodetype EncodeOP_N(int n) 525 { 526 assert(n >= 0 && n <= 16); 527 if (n == 0) 528 return OP_0; 529 return (opcodetype)(OP_1+n-1); 530 } 531 532 /** 533 * Pre-version-0.6, Bitcoin always counted CHECKMULTISIGs 534 * as 20 sigops. With pay-to-script-hash, that changed: 535 * CHECKMULTISIGs serialized in scriptSigs are 536 * counted more accurately, assuming they are of the form 537 * ... OP_N CHECKMULTISIG ... 538 */ 539 unsigned int GetSigOpCount(bool fAccurate) const; 540 541 /** 542 * Accurately count sigOps, including sigOps in 543 * pay-to-script-hash transactions: 544 */ 545 unsigned int GetSigOpCount(const CScript& scriptSig) const; 546 547 /* 548 * OP_1 <0x4e73> 549 */ 550 bool IsPayToAnchor() const; 551 /** Checks if output of IsWitnessProgram comes from a P2A output script 552 */ 553 static bool IsPayToAnchor(int version, const std::vector<unsigned char>& program); 554 555 bool IsPayToScriptHash() const; 556 bool IsPayToWitnessScriptHash() const; 557 bool IsWitnessProgram(int& version, std::vector<unsigned char>& program) const; 558 559 /** Called by IsStandardTx and P2SH/BIP62 VerifyScript (which makes it consensus-critical). */ 560 bool IsPushOnly(const_iterator pc) const; 561 bool IsPushOnly() const; 562 563 /** Check if the script contains valid OP_CODES */ 564 bool HasValidOps() const; 565 566 /** 567 * Returns whether the script is guaranteed to fail at execution, 568 * regardless of the initial stack. This allows outputs to be pruned 569 * instantly when entering the UTXO set. 570 */ 571 bool IsUnspendable() const 572 { 573 return (size() > 0 && *begin() == OP_RETURN) || (size() > MAX_SCRIPT_SIZE); 574 } 575 576 void clear() 577 { 578 // The default prevector::clear() does not release memory 579 CScriptBase::clear(); 580 shrink_to_fit(); 581 } 582 }; 583 584 struct CScriptWitness 585 { 586 // Note that this encodes the data elements being pushed, rather than 587 // encoding them as a CScript that pushes them. 588 std::vector<std::vector<unsigned char> > stack; 589 590 // Some compilers complain without a default constructor 591 CScriptWitness() = default; 592 593 bool IsNull() const { return stack.empty(); } 594 595 void SetNull() { stack.clear(); stack.shrink_to_fit(); } 596 597 std::string ToString() const; 598 }; 599 600 /** A reference to a CScript: the Hash160 of its serialization */ 601 class CScriptID : public BaseHash<uint160> 602 { 603 public: 604 CScriptID() : BaseHash() {} 605 explicit CScriptID(const CScript& in); 606 explicit CScriptID(const uint160& in) : BaseHash(in) {} 607 }; 608 609 /** Test for OP_SUCCESSx opcodes as defined by BIP342. */ 610 bool IsOpSuccess(const opcodetype& opcode); 611 612 bool CheckMinimalPush(const std::vector<unsigned char>& data, opcodetype opcode); 613 614 /** Build a script by concatenating other scripts, or any argument accepted by CScript::operator<<. */ 615 template<typename... Ts> 616 CScript BuildScript(Ts&&... inputs) 617 { 618 CScript ret; 619 int cnt{0}; 620 621 ([&ret, &cnt] (Ts&& input) { 622 if constexpr (std::is_same_v<std::remove_cv_t<std::remove_reference_t<Ts>>, CScript>) { 623 // If it is a CScript, extend ret with it. Move or copy the first element instead. 624 if (cnt == 0) { 625 ret = std::forward<Ts>(input); 626 } else { 627 ret.insert(ret.end(), input.begin(), input.end()); 628 } 629 } else { 630 // Otherwise invoke CScript::operator<<. 631 ret << input; 632 } 633 cnt++; 634 } (std::forward<Ts>(inputs)), ...); 635 636 return ret; 637 } 638 639 #endif // BITCOIN_SCRIPT_SCRIPT_H