Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2014 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 "crypto/common.h"
10 :
11 : #include <assert.h>
12 : #include <climits>
13 : #include <limits>
14 : #include <stdexcept>
15 : #include <stdint.h>
16 : #include <string.h>
17 : #include <string>
18 : #include <vector>
19 :
20 : static const unsigned int MAX_SCRIPT_ELEMENT_SIZE = 520; // bytes
21 :
22 : // Threshold for nLockTime: below this value it is interpreted as block number,
23 : // otherwise as UNIX timestamp.
24 : static const unsigned int LOCKTIME_THRESHOLD = 500000000; // Tue Nov 5 00:53:20 1985 UTC
25 :
26 : template <typename T>
27 1098 : std::vector<unsigned char> ToByteVector(const T& in)
28 : {
29 13573 : return std::vector<unsigned char>(in.begin(), in.end());
30 : }
31 :
32 : /** Script opcodes */
33 : enum opcodetype
34 : {
35 : // push value
36 : OP_0 = 0x00,
37 : OP_FALSE = OP_0,
38 : OP_PUSHDATA1 = 0x4c,
39 : OP_PUSHDATA2 = 0x4d,
40 : OP_PUSHDATA4 = 0x4e,
41 : OP_1NEGATE = 0x4f,
42 : OP_RESERVED = 0x50,
43 : OP_1 = 0x51,
44 : OP_TRUE=OP_1,
45 : OP_2 = 0x52,
46 : OP_3 = 0x53,
47 : OP_4 = 0x54,
48 : OP_5 = 0x55,
49 : OP_6 = 0x56,
50 : OP_7 = 0x57,
51 : OP_8 = 0x58,
52 : OP_9 = 0x59,
53 : OP_10 = 0x5a,
54 : OP_11 = 0x5b,
55 : OP_12 = 0x5c,
56 : OP_13 = 0x5d,
57 : OP_14 = 0x5e,
58 : OP_15 = 0x5f,
59 : OP_16 = 0x60,
60 :
61 : // control
62 : OP_NOP = 0x61,
63 : OP_VER = 0x62,
64 : OP_IF = 0x63,
65 : OP_NOTIF = 0x64,
66 : OP_VERIF = 0x65,
67 : OP_VERNOTIF = 0x66,
68 : OP_ELSE = 0x67,
69 : OP_ENDIF = 0x68,
70 : OP_VERIFY = 0x69,
71 : OP_RETURN = 0x6a,
72 :
73 : // stack ops
74 : OP_TOALTSTACK = 0x6b,
75 : OP_FROMALTSTACK = 0x6c,
76 : OP_2DROP = 0x6d,
77 : OP_2DUP = 0x6e,
78 : OP_3DUP = 0x6f,
79 : OP_2OVER = 0x70,
80 : OP_2ROT = 0x71,
81 : OP_2SWAP = 0x72,
82 : OP_IFDUP = 0x73,
83 : OP_DEPTH = 0x74,
84 : OP_DROP = 0x75,
85 : OP_DUP = 0x76,
86 : OP_NIP = 0x77,
87 : OP_OVER = 0x78,
88 : OP_PICK = 0x79,
89 : OP_ROLL = 0x7a,
90 : OP_ROT = 0x7b,
91 : OP_SWAP = 0x7c,
92 : OP_TUCK = 0x7d,
93 :
94 : // splice ops
95 : OP_CAT = 0x7e,
96 : OP_SUBSTR = 0x7f,
97 : OP_LEFT = 0x80,
98 : OP_RIGHT = 0x81,
99 : OP_SIZE = 0x82,
100 :
101 : // bit logic
102 : OP_INVERT = 0x83,
103 : OP_AND = 0x84,
104 : OP_OR = 0x85,
105 : OP_XOR = 0x86,
106 : OP_EQUAL = 0x87,
107 : OP_EQUALVERIFY = 0x88,
108 : OP_RESERVED1 = 0x89,
109 : OP_RESERVED2 = 0x8a,
110 :
111 : // numeric
112 : OP_1ADD = 0x8b,
113 : OP_1SUB = 0x8c,
114 : OP_2MUL = 0x8d,
115 : OP_2DIV = 0x8e,
116 : OP_NEGATE = 0x8f,
117 : OP_ABS = 0x90,
118 : OP_NOT = 0x91,
119 : OP_0NOTEQUAL = 0x92,
120 :
121 : OP_ADD = 0x93,
122 : OP_SUB = 0x94,
123 : OP_MUL = 0x95,
124 : OP_DIV = 0x96,
125 : OP_MOD = 0x97,
126 : OP_LSHIFT = 0x98,
127 : OP_RSHIFT = 0x99,
128 :
129 : OP_BOOLAND = 0x9a,
130 : OP_BOOLOR = 0x9b,
131 : OP_NUMEQUAL = 0x9c,
132 : OP_NUMEQUALVERIFY = 0x9d,
133 : OP_NUMNOTEQUAL = 0x9e,
134 : OP_LESSTHAN = 0x9f,
135 : OP_GREATERTHAN = 0xa0,
136 : OP_LESSTHANOREQUAL = 0xa1,
137 : OP_GREATERTHANOREQUAL = 0xa2,
138 : OP_MIN = 0xa3,
139 : OP_MAX = 0xa4,
140 :
141 : OP_WITHIN = 0xa5,
142 :
143 : // crypto
144 : OP_RIPEMD160 = 0xa6,
145 : OP_SHA1 = 0xa7,
146 : OP_SHA256 = 0xa8,
147 : OP_HASH160 = 0xa9,
148 : OP_HASH256 = 0xaa,
149 : OP_CODESEPARATOR = 0xab,
150 : OP_CHECKSIG = 0xac,
151 : OP_CHECKSIGVERIFY = 0xad,
152 : OP_CHECKMULTISIG = 0xae,
153 : OP_CHECKMULTISIGVERIFY = 0xaf,
154 :
155 : // expansion
156 : OP_NOP1 = 0xb0,
157 : OP_NOP2 = 0xb1,
158 : OP_CHECKLOCKTIMEVERIFY = OP_NOP2,
159 : OP_NOP3 = 0xb2,
160 : OP_NOP4 = 0xb3,
161 : OP_NOP5 = 0xb4,
162 : OP_NOP6 = 0xb5,
163 : OP_NOP7 = 0xb6,
164 : OP_NOP8 = 0xb7,
165 : OP_NOP9 = 0xb8,
166 : OP_NOP10 = 0xb9,
167 :
168 :
169 : // template matching params
170 : OP_SMALLINTEGER = 0xfa,
171 : OP_PUBKEYS = 0xfb,
172 : OP_PUBKEYHASH = 0xfd,
173 : OP_PUBKEY = 0xfe,
174 :
175 : OP_INVALIDOPCODE = 0xff,
176 : };
177 :
178 : const char* GetOpName(opcodetype opcode);
179 :
180 239 : class scriptnum_error : public std::runtime_error
181 : {
182 : public:
183 239 : explicit scriptnum_error(const std::string& str) : std::runtime_error(str) {}
184 : };
185 :
186 : class CScriptNum
187 : {
188 : /**
189 : * Numeric opcodes (OP_1ADD, etc) are restricted to operating on 4-byte integers.
190 : * The semantics are subtle, though: operands must be in the range [-2^31 +1...2^31 -1],
191 : * but results may overflow (and are valid as long as they are not used in a subsequent
192 : * numeric operation). CScriptNum enforces those semantics by storing results as
193 : * an int64 and allowing out-of-range values to be returned as a vector of bytes but
194 : * throwing an exception if arithmetic is done or the result is interpreted as an integer.
195 : */
196 : public:
197 :
198 0 : explicit CScriptNum(const int64_t& n)
199 : {
200 85338 : m_value = n;
201 0 : }
202 :
203 : static const size_t nDefaultMaxNumSize = 4;
204 :
205 8879 : explicit CScriptNum(const std::vector<unsigned char>& vch, bool fRequireMinimal,
206 : const size_t nMaxNumSize = nDefaultMaxNumSize)
207 : {
208 17758 : if (vch.size() > nMaxNumSize) {
209 393 : throw scriptnum_error("script number overflow");
210 : }
211 8748 : if (fRequireMinimal && vch.size() > 0) {
212 : // Check that the number is encoded with the minimum possible
213 : // number of bytes.
214 : //
215 : // If the most-significant-byte - excluding the sign bit - is zero
216 : // then we're not minimal. Note how this test also rejects the
217 : // negative-zero encoding, 0x80.
218 188 : if ((vch.back() & 0x7f) == 0) {
219 : // One exception: if there's more than one byte and the most
220 : // significant bit of the second-most-significant-byte is set
221 : // it would conflict with the sign bit. An example of this case
222 : // is +-255, which encode to 0xff00 and 0xff80 respectively.
223 : // (big-endian).
224 212 : if (vch.size() <= 1 || (vch[vch.size() - 2] & 0x80) == 0) {
225 324 : throw scriptnum_error("non-minimally encoded script number");
226 : }
227 : }
228 : }
229 8640 : m_value = set_vch(vch);
230 8640 : }
231 :
232 4086 : inline bool operator==(const int64_t& rhs) const { return m_value == rhs; }
233 3964 : inline bool operator!=(const int64_t& rhs) const { return m_value != rhs; }
234 3928 : inline bool operator<=(const int64_t& rhs) const { return m_value <= rhs; }
235 3975 : inline bool operator< (const int64_t& rhs) const { return m_value < rhs; }
236 3916 : inline bool operator>=(const int64_t& rhs) const { return m_value >= rhs; }
237 3941 : inline bool operator> (const int64_t& rhs) const { return m_value > rhs; }
238 :
239 2790 : inline bool operator==(const CScriptNum& rhs) const { return operator==(rhs.m_value); }
240 2668 : inline bool operator!=(const CScriptNum& rhs) const { return operator!=(rhs.m_value); }
241 2632 : inline bool operator<=(const CScriptNum& rhs) const { return operator<=(rhs.m_value); }
242 2654 : inline bool operator< (const CScriptNum& rhs) const { return operator< (rhs.m_value); }
243 2608 : inline bool operator>=(const CScriptNum& rhs) const { return operator>=(rhs.m_value); }
244 2622 : inline bool operator> (const CScriptNum& rhs) const { return operator> (rhs.m_value); }
245 :
246 3662 : inline CScriptNum operator+( const int64_t& rhs) const { return CScriptNum(m_value + rhs);}
247 4895 : inline CScriptNum operator-( const int64_t& rhs) const { return CScriptNum(m_value - rhs);}
248 1268 : inline CScriptNum operator+( const CScriptNum& rhs) const { return operator+(rhs.m_value); }
249 2454 : inline CScriptNum operator-( const CScriptNum& rhs) const { return operator-(rhs.m_value); }
250 :
251 15 : inline CScriptNum& operator+=( const CScriptNum& rhs) { return operator+=(rhs.m_value); }
252 6 : inline CScriptNum& operator-=( const CScriptNum& rhs) { return operator-=(rhs.m_value); }
253 :
254 1260 : inline CScriptNum operator-() const
255 : {
256 1260 : assert(m_value != std::numeric_limits<int64_t>::min());
257 1260 : return CScriptNum(-m_value);
258 : }
259 :
260 0 : inline CScriptNum& operator=( const int64_t& rhs)
261 : {
262 319 : m_value = rhs;
263 0 : return *this;
264 : }
265 :
266 15 : inline CScriptNum& operator+=( const int64_t& rhs)
267 : {
268 30 : assert(rhs == 0 || (rhs > 0 && m_value <= std::numeric_limits<int64_t>::max() - rhs) ||
269 15 : (rhs < 0 && m_value >= std::numeric_limits<int64_t>::min() - rhs));
270 15 : m_value += rhs;
271 15 : return *this;
272 : }
273 :
274 6 : inline CScriptNum& operator-=( const int64_t& rhs)
275 : {
276 12 : assert(rhs == 0 || (rhs > 0 && m_value >= std::numeric_limits<int64_t>::min() + rhs) ||
277 6 : (rhs < 0 && m_value <= std::numeric_limits<int64_t>::max() + rhs));
278 6 : m_value -= rhs;
279 6 : return *this;
280 : }
281 :
282 : int getint() const
283 : {
284 20389 : if (m_value > std::numeric_limits<int>::max())
285 : return std::numeric_limits<int>::max();
286 18668 : else if (m_value < std::numeric_limits<int>::min())
287 : return std::numeric_limits<int>::min();
288 16964 : return m_value;
289 : }
290 :
291 : std::vector<unsigned char> getvch() const
292 : {
293 89500 : return serialize(m_value);
294 : }
295 :
296 159525 : static std::vector<unsigned char> serialize(const int64_t& value)
297 : {
298 159525 : if(value == 0)
299 : return std::vector<unsigned char>();
300 :
301 : std::vector<unsigned char> result;
302 154523 : const bool neg = value < 0;
303 154523 : uint64_t absvalue = neg ? -value : value;
304 :
305 555010 : while(absvalue)
306 : {
307 245964 : result.push_back(absvalue & 0xff);
308 245964 : absvalue >>= 8;
309 : }
310 :
311 : // - If the most significant byte is >= 0x80 and the value is positive, push a
312 : // new zero-byte to make the significant byte < 0x80 again.
313 :
314 : // - If the most significant byte is >= 0x80 and the value is negative, push a
315 : // new 0x80 byte that will be popped off when converting to an integral.
316 :
317 : // - If the most significant byte is < 0x80 and the value is negative, add
318 : // 0x80 to it, since it will be subtracted and interpreted as a negative when
319 : // converting to an integral.
320 :
321 154523 : if (result.back() & 0x80)
322 37781 : result.push_back(neg ? 0x80 : 0);
323 116742 : else if (neg)
324 2710 : result.back() |= 0x80;
325 :
326 154523 : return result;
327 : }
328 :
329 : private:
330 8640 : static int64_t set_vch(const std::vector<unsigned char>& vch)
331 : {
332 8640 : if (vch.empty())
333 : return 0;
334 :
335 : int64_t result = 0;
336 6992 : for (size_t i = 0; i != vch.size(); ++i)
337 5308 : result |= static_cast<int64_t>(vch[i]) << 8*i;
338 :
339 : // If the input vector's most significant byte is 0x80, remove it from
340 : // the result's msb and return a negative.
341 1684 : if (vch.back() & 0x80)
342 594 : return -((int64_t)(result & ~(0x80ULL << (8 * (vch.size() - 1)))));
343 :
344 1387 : return result;
345 : }
346 :
347 : int64_t m_value;
348 : };
349 :
350 : /** Serialized script, used inside transaction inputs and outputs */
351 9245458 : class CScript : public std::vector<unsigned char>
352 : {
353 : protected:
354 74198 : CScript& push_int64(int64_t n)
355 : {
356 74198 : if (n == -1 || (n >= 1 && n <= 16))
357 : {
358 1593 : push_back(n + (OP_1 - 1));
359 : }
360 72605 : else if (n == 0)
361 : {
362 2580 : push_back(OP_0);
363 : }
364 : else
365 : {
366 140050 : *this << CScriptNum::serialize(n);
367 : }
368 74198 : return *this;
369 : }
370 : public:
371 2566417 : CScript() { }
372 8499551 : CScript(const CScript& b) : std::vector<unsigned char>(b.begin(), b.end()) { }
373 17362 : CScript(const_iterator pbegin, const_iterator pend) : std::vector<unsigned char>(pbegin, pend) { }
374 2284 : CScript(const unsigned char* pbegin, const unsigned char* pend) : std::vector<unsigned char>(pbegin, pend) { }
375 :
376 1345 : CScript& operator+=(const CScript& b)
377 : {
378 5380 : insert(end(), b.begin(), b.end());
379 1345 : return *this;
380 : }
381 :
382 1343 : friend CScript operator+(const CScript& a, const CScript& b)
383 : {
384 : CScript ret = a;
385 1343 : ret += b;
386 1343 : return ret;
387 : }
388 :
389 : CScript(int64_t b) { operator<<(b); }
390 :
391 100000 : explicit CScript(opcodetype b) { operator<<(b); }
392 : explicit CScript(const CScriptNum& b) { operator<<(b); }
393 10728 : explicit CScript(const std::vector<unsigned char>& b) { operator<<(b); }
394 :
395 :
396 74198 : CScript& operator<<(int64_t b) { return push_int64(b); }
397 :
398 1485678 : CScript& operator<<(opcodetype opcode)
399 : {
400 1485678 : if (opcode < 0 || opcode > 0xff)
401 0 : throw std::runtime_error("CScript::operator<<(): invalid opcode");
402 2971356 : insert(end(), (unsigned char)opcode);
403 1485678 : return *this;
404 : }
405 :
406 4086 : CScript& operator<<(const CScriptNum& b)
407 : {
408 8172 : *this << b.getvch();
409 4086 : return *this;
410 : }
411 :
412 88377 : CScript& operator<<(const std::vector<unsigned char>& b)
413 : {
414 176754 : if (b.size() < OP_PUSHDATA1)
415 : {
416 175674 : insert(end(), (unsigned char)b.size());
417 : }
418 540 : else if (b.size() <= 0xff)
419 : {
420 392 : insert(end(), OP_PUSHDATA1);
421 588 : insert(end(), (unsigned char)b.size());
422 : }
423 344 : else if (b.size() <= 0xffff)
424 : {
425 688 : insert(end(), OP_PUSHDATA2);
426 : uint8_t data[2];
427 688 : WriteLE16(data, b.size());
428 688 : insert(end(), data, data + sizeof(data));
429 : }
430 : else
431 : {
432 0 : insert(end(), OP_PUSHDATA4);
433 : uint8_t data[4];
434 0 : WriteLE32(data, b.size());
435 0 : insert(end(), data, data + sizeof(data));
436 : }
437 353512 : insert(end(), b.begin(), b.end());
438 88377 : return *this;
439 : }
440 :
441 : CScript& operator<<(const CScript& b)
442 : {
443 : // I'm not sure if this should push the script or concatenate scripts.
444 : // If there's ever a use for pushing a script onto a script, delete this member fn
445 : assert(!"Warning: Pushing a CScript onto a CScript with << is probably not intended, use + to concatenate!");
446 : return *this;
447 : }
448 :
449 :
450 : bool GetOp(iterator& pc, opcodetype& opcodeRet, std::vector<unsigned char>& vchRet)
451 : {
452 : // Wrapper so it can be called with either iterator or const_iterator
453 : const_iterator pc2 = pc;
454 : bool fRet = GetOp2(pc2, opcodeRet, &vchRet);
455 : pc = begin() + (pc2 - begin());
456 : return fRet;
457 : }
458 :
459 275893 : bool GetOp(iterator& pc, opcodetype& opcodeRet)
460 : {
461 : const_iterator pc2 = pc;
462 275893 : bool fRet = GetOp2(pc2, opcodeRet, NULL);
463 1379440 : pc = begin() + (pc2 - begin());
464 275888 : return fRet;
465 : }
466 :
467 : bool GetOp(const_iterator& pc, opcodetype& opcodeRet, std::vector<unsigned char>& vchRet) const
468 : {
469 480095 : return GetOp2(pc, opcodeRet, &vchRet);
470 : }
471 :
472 : bool GetOp(const_iterator& pc, opcodetype& opcodeRet) const
473 : {
474 3336069 : return GetOp2(pc, opcodeRet, NULL);
475 : }
476 :
477 4092223 : bool GetOp2(const_iterator& pc, opcodetype& opcodeRet, std::vector<unsigned char>* pvchRet) const
478 : {
479 4092223 : opcodeRet = OP_INVALIDOPCODE;
480 4092223 : if (pvchRet)
481 : pvchRet->clear();
482 12276669 : if (pc >= end())
483 : return false;
484 :
485 : // Read instruction
486 11771445 : if (end() - pc < 1)
487 : return false;
488 7847464 : unsigned int opcode = *pc++;
489 :
490 : // Immediate operand
491 3923732 : if (opcode <= OP_PUSHDATA4)
492 : {
493 2412965 : unsigned int nSize = 0;
494 2412965 : if (opcode < OP_PUSHDATA1)
495 : {
496 : nSize = opcode;
497 : }
498 9606 : else if (opcode == OP_PUSHDATA1)
499 : {
500 1635 : if (end() - pc < 1)
501 : return false;
502 1090 : nSize = *pc++;
503 : }
504 9061 : else if (opcode == OP_PUSHDATA2)
505 : {
506 27150 : if (end() - pc < 2)
507 : return false;
508 18096 : nSize = ReadLE16(&pc[0]);
509 : pc += 2;
510 : }
511 11 : else if (opcode == OP_PUSHDATA4)
512 : {
513 33 : if (end() - pc < 4)
514 : return false;
515 18 : nSize = ReadLE32(&pc[0]);
516 : pc += 4;
517 : }
518 12064809 : if (end() - pc < 0 || (unsigned int)(end() - pc) < nSize)
519 : return false;
520 2412524 : if (pvchRet)
521 136168 : pvchRet->assign(pc, pc + nSize);
522 2412535 : pc += nSize;
523 : }
524 :
525 3923302 : opcodeRet = (opcodetype)opcode;
526 3923302 : return true;
527 : }
528 :
529 : /** Encode/decode small integers: */
530 393 : static int DecodeOP_N(opcodetype opcode)
531 : {
532 393 : if (opcode == OP_0)
533 : return 0;
534 387 : assert(opcode >= OP_1 && opcode <= OP_16);
535 387 : return (int)opcode - (int)(OP_1 - 1);
536 : }
537 30 : static opcodetype EncodeOP_N(int n)
538 : {
539 30 : assert(n >= 0 && n <= 16);
540 30 : if (n == 0)
541 : return OP_0;
542 30 : return (opcodetype)(OP_1+n-1);
543 : }
544 :
545 55364 : int FindAndDelete(const CScript& b)
546 : {
547 55364 : int nFound = 0;
548 110728 : if (b.empty())
549 : return nFound;
550 110710 : iterator pc = begin();
551 : opcodetype opcode;
552 275891 : do
553 : {
554 1205088 : while (end() - pc >= (long)b.size() && memcmp(&pc[0], &b[0], b.size()) == 0)
555 : {
556 76154 : pc = erase(pc, pc + b.size());
557 25392 : ++nFound;
558 : }
559 : }
560 : while (GetOp(pc, opcode));
561 55362 : return nFound;
562 : }
563 : int Find(opcodetype op) const
564 : {
565 : int nFound = 0;
566 : opcodetype opcode;
567 : for (const_iterator pc = begin(); pc != end() && GetOp(pc, opcode);)
568 : if (opcode == op)
569 : ++nFound;
570 : return nFound;
571 : }
572 :
573 : /**
574 : * Pre-version-0.6, Bitcoin always counted CHECKMULTISIGs
575 : * as 20 sigops. With pay-to-script-hash, that changed:
576 : * CHECKMULTISIGs serialized in scriptSigs are
577 : * counted more accurately, assuming they are of the form
578 : * ... OP_N CHECKMULTISIG ...
579 : */
580 : unsigned int GetSigOpCount(bool fAccurate) const;
581 :
582 : /**
583 : * Accurately count sigOps, including sigOps in
584 : * pay-to-script-hash transactions:
585 : */
586 : unsigned int GetSigOpCount(const CScript& scriptSig) const;
587 :
588 : bool IsPayToScriptHash() const;
589 :
590 : /** Called by IsStandardTx and P2SH/BIP62 VerifyScript (which makes it consensus-critical). */
591 : bool IsPushOnly(const_iterator pc) const;
592 : bool IsPushOnly() const;
593 :
594 : /**
595 : * Returns whether the script is guaranteed to fail at execution,
596 : * regardless of the initial stack. This allows outputs to be pruned
597 : * instantly when entering the UTXO set.
598 : */
599 : bool IsUnspendable() const
600 : {
601 118927 : return (size() > 0 && *begin() == OP_RETURN);
602 : }
603 :
604 : void clear()
605 : {
606 : // The default std::vector::clear() does not release memory.
607 1248682 : std::vector<unsigned char>().swap(*this);
608 : }
609 : };
610 :
611 : class CReserveScript
612 : {
613 : public:
614 : CScript reserveScript;
615 0 : virtual void KeepScript() {}
616 421 : CReserveScript() {}
617 842 : virtual ~CReserveScript() {}
618 : };
619 :
620 : #endif // BITCOIN_SCRIPT_SCRIPT_H
|
