1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2016 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.
6 #ifndef BITCOIN_SCRIPT_SCRIPT_H
7 #define BITCOIN_SCRIPT_SCRIPT_H
9 #include "crypto/common.h"
10 #include "prevector.h"
11 #include "serialize.h"
22 // Maximum number of bytes pushable to the stack
23 static const unsigned int MAX_SCRIPT_ELEMENT_SIZE
= 520;
25 // Maximum number of non-push operations per script
26 static const int MAX_OPS_PER_SCRIPT
= 201;
28 // Maximum number of public keys per multisig
29 static const int MAX_PUBKEYS_PER_MULTISIG
= 20;
31 // Maximum script length in bytes
32 static const int MAX_SCRIPT_SIZE
= 10000;
34 // Maximum number of values on script interpreter stack
35 static const int MAX_STACK_SIZE
= 1000;
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
42 std::vector
<unsigned char> ToByteVector(const T
& in
)
44 return std::vector
<unsigned char>(in
.begin(), in
.end());
90 OP_FROMALTSTACK
= 0x6c,
122 OP_EQUALVERIFY
= 0x88,
147 OP_NUMEQUALVERIFY
= 0x9d,
148 OP_NUMNOTEQUAL
= 0x9e,
150 OP_GREATERTHAN
= 0xa0,
151 OP_LESSTHANOREQUAL
= 0xa1,
152 OP_GREATERTHANOREQUAL
= 0xa2,
164 OP_CODESEPARATOR
= 0xab,
166 OP_CHECKSIGVERIFY
= 0xad,
167 OP_CHECKMULTISIG
= 0xae,
168 OP_CHECKMULTISIGVERIFY
= 0xaf,
172 OP_CHECKLOCKTIMEVERIFY
= 0xb1,
173 OP_NOP2
= OP_CHECKLOCKTIMEVERIFY
,
174 OP_CHECKSEQUENCEVERIFY
= 0xb2,
175 OP_NOP3
= OP_CHECKSEQUENCEVERIFY
,
185 // template matching params
186 OP_SMALLINTEGER
= 0xfa,
188 OP_PUBKEYHASH
= 0xfd,
191 OP_INVALIDOPCODE
= 0xff,
194 // Maximum value that an opcode can be
195 static const unsigned int MAX_OPCODE
= OP_NOP10
;
197 const char* GetOpName(opcodetype opcode
);
199 class scriptnum_error
: public std::runtime_error
202 explicit scriptnum_error(const std::string
& str
) : std::runtime_error(str
) {}
208 * Numeric opcodes (OP_1ADD, etc) are restricted to operating on 4-byte integers.
209 * The semantics are subtle, though: operands must be in the range [-2^31 +1...2^31 -1],
210 * but results may overflow (and are valid as long as they are not used in a subsequent
211 * numeric operation). CScriptNum enforces those semantics by storing results as
212 * an int64 and allowing out-of-range values to be returned as a vector of bytes but
213 * throwing an exception if arithmetic is done or the result is interpreted as an integer.
217 explicit CScriptNum(const int64_t& n
)
222 static const size_t nDefaultMaxNumSize
= 4;
224 explicit CScriptNum(const std::vector
<unsigned char>& vch
, bool fRequireMinimal
,
225 const size_t nMaxNumSize
= nDefaultMaxNumSize
)
227 if (vch
.size() > nMaxNumSize
) {
228 throw scriptnum_error("script number overflow");
230 if (fRequireMinimal
&& vch
.size() > 0) {
231 // Check that the number is encoded with the minimum possible
234 // If the most-significant-byte - excluding the sign bit - is zero
235 // then we're not minimal. Note how this test also rejects the
236 // negative-zero encoding, 0x80.
237 if ((vch
.back() & 0x7f) == 0) {
238 // One exception: if there's more than one byte and the most
239 // significant bit of the second-most-significant-byte is set
240 // it would conflict with the sign bit. An example of this case
241 // is +-255, which encode to 0xff00 and 0xff80 respectively.
243 if (vch
.size() <= 1 || (vch
[vch
.size() - 2] & 0x80) == 0) {
244 throw scriptnum_error("non-minimally encoded script number");
248 m_value
= set_vch(vch
);
251 inline bool operator==(const int64_t& rhs
) const { return m_value
== rhs
; }
252 inline bool operator!=(const int64_t& rhs
) const { return m_value
!= rhs
; }
253 inline bool operator<=(const int64_t& rhs
) const { return m_value
<= rhs
; }
254 inline bool operator< (const int64_t& rhs
) const { return m_value
< rhs
; }
255 inline bool operator>=(const int64_t& rhs
) const { return m_value
>= rhs
; }
256 inline bool operator> (const int64_t& rhs
) const { return m_value
> rhs
; }
258 inline bool operator==(const CScriptNum
& rhs
) const { return operator==(rhs
.m_value
); }
259 inline bool operator!=(const CScriptNum
& rhs
) const { return operator!=(rhs
.m_value
); }
260 inline bool operator<=(const CScriptNum
& rhs
) const { return operator<=(rhs
.m_value
); }
261 inline bool operator< (const CScriptNum
& rhs
) const { return operator< (rhs
.m_value
); }
262 inline bool operator>=(const CScriptNum
& rhs
) const { return operator>=(rhs
.m_value
); }
263 inline bool operator> (const CScriptNum
& rhs
) const { return operator> (rhs
.m_value
); }
265 inline CScriptNum
operator+( const int64_t& rhs
) const { return CScriptNum(m_value
+ rhs
);}
266 inline CScriptNum
operator-( const int64_t& rhs
) const { return CScriptNum(m_value
- rhs
);}
267 inline CScriptNum
operator+( const CScriptNum
& rhs
) const { return operator+(rhs
.m_value
); }
268 inline CScriptNum
operator-( const CScriptNum
& rhs
) const { return operator-(rhs
.m_value
); }
270 inline CScriptNum
& operator+=( const CScriptNum
& rhs
) { return operator+=(rhs
.m_value
); }
271 inline CScriptNum
& operator-=( const CScriptNum
& rhs
) { return operator-=(rhs
.m_value
); }
273 inline CScriptNum
operator&( const int64_t& rhs
) const { return CScriptNum(m_value
& rhs
);}
274 inline CScriptNum
operator&( const CScriptNum
& rhs
) const { return operator&(rhs
.m_value
); }
276 inline CScriptNum
& operator&=( const CScriptNum
& rhs
) { return operator&=(rhs
.m_value
); }
278 inline CScriptNum
operator-() const
280 assert(m_value
!= std::numeric_limits
<int64_t>::min());
281 return CScriptNum(-m_value
);
284 inline CScriptNum
& operator=( const int64_t& rhs
)
290 inline CScriptNum
& operator+=( const int64_t& rhs
)
292 assert(rhs
== 0 || (rhs
> 0 && m_value
<= std::numeric_limits
<int64_t>::max() - rhs
) ||
293 (rhs
< 0 && m_value
>= std::numeric_limits
<int64_t>::min() - rhs
));
298 inline CScriptNum
& operator-=( const int64_t& rhs
)
300 assert(rhs
== 0 || (rhs
> 0 && m_value
>= std::numeric_limits
<int64_t>::min() + rhs
) ||
301 (rhs
< 0 && m_value
<= std::numeric_limits
<int64_t>::max() + rhs
));
306 inline CScriptNum
& operator&=( const int64_t& rhs
)
314 if (m_value
> std::numeric_limits
<int>::max())
315 return std::numeric_limits
<int>::max();
316 else if (m_value
< std::numeric_limits
<int>::min())
317 return std::numeric_limits
<int>::min();
321 std::vector
<unsigned char> getvch() const
323 return serialize(m_value
);
326 static std::vector
<unsigned char> serialize(const int64_t& value
)
329 return std::vector
<unsigned char>();
331 std::vector
<unsigned char> result
;
332 const bool neg
= value
< 0;
333 uint64_t absvalue
= neg
? -value
: value
;
337 result
.push_back(absvalue
& 0xff);
341 // - If the most significant byte is >= 0x80 and the value is positive, push a
342 // new zero-byte to make the significant byte < 0x80 again.
344 // - If the most significant byte is >= 0x80 and the value is negative, push a
345 // new 0x80 byte that will be popped off when converting to an integral.
347 // - If the most significant byte is < 0x80 and the value is negative, add
348 // 0x80 to it, since it will be subtracted and interpreted as a negative when
349 // converting to an integral.
351 if (result
.back() & 0x80)
352 result
.push_back(neg
? 0x80 : 0);
354 result
.back() |= 0x80;
360 static int64_t set_vch(const std::vector
<unsigned char>& vch
)
366 for (size_t i
= 0; i
!= vch
.size(); ++i
)
367 result
|= static_cast<int64_t>(vch
[i
]) << 8*i
;
369 // If the input vector's most significant byte is 0x80, remove it from
370 // the result's msb and return a negative.
371 if (vch
.back() & 0x80)
372 return -((int64_t)(result
& ~(0x80ULL
<< (8 * (vch
.size() - 1)))));
380 typedef prevector
<28, unsigned char> CScriptBase
;
382 /** Serialized script, used inside transaction inputs and outputs */
383 class CScript
: public CScriptBase
386 CScript
& push_int64(int64_t n
)
388 if (n
== -1 || (n
>= 1 && n
<= 16))
390 push_back(n
+ (OP_1
- 1));
398 *this << CScriptNum::serialize(n
);
404 CScript(const_iterator pbegin
, const_iterator pend
) : CScriptBase(pbegin
, pend
) { }
405 CScript(std::vector
<unsigned char>::const_iterator pbegin
, std::vector
<unsigned char>::const_iterator pend
) : CScriptBase(pbegin
, pend
) { }
406 CScript(const unsigned char* pbegin
, const unsigned char* pend
) : CScriptBase(pbegin
, pend
) { }
408 ADD_SERIALIZE_METHODS
;
410 template <typename Stream
, typename Operation
>
411 inline void SerializationOp(Stream
& s
, Operation ser_action
) {
412 READWRITE(static_cast<CScriptBase
&>(*this));
415 CScript
& operator+=(const CScript
& b
)
417 insert(end(), b
.begin(), b
.end());
421 friend CScript
operator+(const CScript
& a
, const CScript
& b
)
428 CScript(int64_t b
) { operator<<(b
); }
430 explicit CScript(opcodetype b
) { operator<<(b
); }
431 explicit CScript(const CScriptNum
& b
) { operator<<(b
); }
432 explicit CScript(const std::vector
<unsigned char>& b
) { operator<<(b
); }
435 CScript
& operator<<(int64_t b
) { return push_int64(b
); }
437 CScript
& operator<<(opcodetype opcode
)
439 if (opcode
< 0 || opcode
> 0xff)
440 throw std::runtime_error("CScript::operator<<(): invalid opcode");
441 insert(end(), (unsigned char)opcode
);
445 CScript
& operator<<(const CScriptNum
& b
)
451 CScript
& operator<<(const std::vector
<unsigned char>& b
)
453 if (b
.size() < OP_PUSHDATA1
)
455 insert(end(), (unsigned char)b
.size());
457 else if (b
.size() <= 0xff)
459 insert(end(), OP_PUSHDATA1
);
460 insert(end(), (unsigned char)b
.size());
462 else if (b
.size() <= 0xffff)
464 insert(end(), OP_PUSHDATA2
);
466 WriteLE16(_data
, b
.size());
467 insert(end(), _data
, _data
+ sizeof(_data
));
471 insert(end(), OP_PUSHDATA4
);
473 WriteLE32(_data
, b
.size());
474 insert(end(), _data
, _data
+ sizeof(_data
));
476 insert(end(), b
.begin(), b
.end());
480 CScript
& operator<<(const CScript
& b
)
482 // I'm not sure if this should push the script or concatenate scripts.
483 // If there's ever a use for pushing a script onto a script, delete this member fn
484 assert(!"Warning: Pushing a CScript onto a CScript with << is probably not intended, use + to concatenate!");
489 bool GetOp(iterator
& pc
, opcodetype
& opcodeRet
, std::vector
<unsigned char>& vchRet
)
491 // Wrapper so it can be called with either iterator or const_iterator
492 const_iterator pc2
= pc
;
493 bool fRet
= GetOp2(pc2
, opcodeRet
, &vchRet
);
494 pc
= begin() + (pc2
- begin());
498 bool GetOp(iterator
& pc
, opcodetype
& opcodeRet
)
500 const_iterator pc2
= pc
;
501 bool fRet
= GetOp2(pc2
, opcodeRet
, nullptr);
502 pc
= begin() + (pc2
- begin());
506 bool GetOp(const_iterator
& pc
, opcodetype
& opcodeRet
, std::vector
<unsigned char>& vchRet
) const
508 return GetOp2(pc
, opcodeRet
, &vchRet
);
511 bool GetOp(const_iterator
& pc
, opcodetype
& opcodeRet
) const
513 return GetOp2(pc
, opcodeRet
, nullptr);
516 bool GetOp2(const_iterator
& pc
, opcodetype
& opcodeRet
, std::vector
<unsigned char>* pvchRet
) const
518 opcodeRet
= OP_INVALIDOPCODE
;
527 unsigned int opcode
= *pc
++;
530 if (opcode
<= OP_PUSHDATA4
)
532 unsigned int nSize
= 0;
533 if (opcode
< OP_PUSHDATA1
)
537 else if (opcode
== OP_PUSHDATA1
)
543 else if (opcode
== OP_PUSHDATA2
)
547 nSize
= ReadLE16(&pc
[0]);
550 else if (opcode
== OP_PUSHDATA4
)
554 nSize
= ReadLE32(&pc
[0]);
557 if (end() - pc
< 0 || (unsigned int)(end() - pc
) < nSize
)
560 pvchRet
->assign(pc
, pc
+ nSize
);
564 opcodeRet
= (opcodetype
)opcode
;
568 /** Encode/decode small integers: */
569 static int DecodeOP_N(opcodetype opcode
)
573 assert(opcode
>= OP_1
&& opcode
<= OP_16
);
574 return (int)opcode
- (int)(OP_1
- 1);
576 static opcodetype
EncodeOP_N(int n
)
578 assert(n
>= 0 && n
<= 16);
581 return (opcodetype
)(OP_1
+n
-1);
584 int FindAndDelete(const CScript
& b
)
590 iterator pc
= begin(), pc2
= begin();
594 result
.insert(result
.end(), pc2
, pc
);
595 while (static_cast<size_t>(end() - pc
) >= b
.size() && std::equal(b
.begin(), b
.end(), pc
))
602 while (GetOp(pc
, opcode
));
605 result
.insert(result
.end(), pc2
, end());
611 int Find(opcodetype op
) const
615 for (const_iterator pc
= begin(); pc
!= end() && GetOp(pc
, opcode
);)
622 * Pre-version-0.6, Bitcoin always counted CHECKMULTISIGs
623 * as 20 sigops. With pay-to-script-hash, that changed:
624 * CHECKMULTISIGs serialized in scriptSigs are
625 * counted more accurately, assuming they are of the form
626 * ... OP_N CHECKMULTISIG ...
628 unsigned int GetSigOpCount(bool fAccurate
) const;
631 * Accurately count sigOps, including sigOps in
632 * pay-to-script-hash transactions:
634 unsigned int GetSigOpCount(const CScript
& scriptSig
) const;
636 bool IsPayToScriptHash() const;
637 bool IsPayToWitnessScriptHash() const;
638 bool IsWitnessProgram(int& version
, std::vector
<unsigned char>& program
) const;
640 /** Called by IsStandardTx and P2SH/BIP62 VerifyScript (which makes it consensus-critical). */
641 bool IsPushOnly(const_iterator pc
) const;
642 bool IsPushOnly() const;
644 /** Check if the script contains valid OP_CODES */
645 bool HasValidOps() const;
648 * Returns whether the script is guaranteed to fail at execution,
649 * regardless of the initial stack. This allows outputs to be pruned
650 * instantly when entering the UTXO set.
652 bool IsUnspendable() const
654 return (size() > 0 && *begin() == OP_RETURN
) || (size() > MAX_SCRIPT_SIZE
);
659 // The default prevector::clear() does not release memory
660 CScriptBase::clear();
665 struct CScriptWitness
667 // Note that this encodes the data elements being pushed, rather than
668 // encoding them as a CScript that pushes them.
669 std::vector
<std::vector
<unsigned char> > stack
;
671 // Some compilers complain without a default constructor
674 bool IsNull() const { return stack
.empty(); }
676 void SetNull() { stack
.clear(); stack
.shrink_to_fit(); }
678 std::string
ToString() const;
684 CScript reserveScript
;
685 virtual void KeepScript() {}
687 virtual ~CReserveScript() {}
690 #endif // BITCOIN_SCRIPT_SCRIPT_H