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