OP_CHECKSEQUENCEVERIFY
[novacoin.git] / src / script.h
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2012 The Bitcoin developers
3 // Distributed under the MIT/X11 software license, see the accompanying
4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
5 #ifndef H_BITCOIN_SCRIPT
6 #define H_BITCOIN_SCRIPT
7
8 #include <string>
9 #include <vector>
10
11 #include <boost/foreach.hpp>
12
13 #include "keystore.h"
14 #include "bignum.h"
15
16 typedef std::vector<uint8_t> valtype;
17
18 class CTransaction;
19
20 static const unsigned int MAX_SCRIPT_ELEMENT_SIZE = 520; // bytes
21
22 // Threshold for inverted nSequence: below this value it is interpreted
23 // as a relative lock-time, otherwise ignored.
24 static const uint32_t SEQUENCE_THRESHOLD = (1 << 31);
25
26 /** IsMine() return codes */
27 enum isminetype
28 {
29     MINE_NO = 0,
30     MINE_WATCH_ONLY = 1,
31     MINE_SPENDABLE = 2,
32     MINE_ALL = MINE_WATCH_ONLY | MINE_SPENDABLE
33 };
34
35 typedef uint8_t isminefilter;
36
37 /** Signature hash types/flags */
38 enum
39 {
40     SIGHASH_ALL = 1,
41     SIGHASH_NONE = 2,
42     SIGHASH_SINGLE = 3,
43     SIGHASH_ANYONECANPAY = 0x80
44 };
45
46 /** Script verification flags */
47 enum
48 {
49     SCRIPT_VERIFY_NONE      = 0,
50     SCRIPT_VERIFY_P2SH      = (1U << 0), // evaluate P2SH (BIP16) subscripts
51     SCRIPT_VERIFY_STRICTENC = (1U << 1), // enforce strict conformance to DER and SEC2 for signatures and pubkeys
52     SCRIPT_VERIFY_LOW_S     = (1U << 2), // enforce low S values in signatures (depends on STRICTENC)
53     SCRIPT_VERIFY_NOCACHE   = (1U << 3), // do not store results in signature cache (but do query it)
54     SCRIPT_VERIFY_NULLDUMMY = (1U << 4),  // verify dummy stack item consumed by CHECKMULTISIG is of zero-length
55     SCRIPT_VERIFY_CHECKLOCKTIMEVERIFY = (1U << 9),
56     SCRIPT_VERIFY_CHECKSEQUENCEVERIFY = (1U << 9)
57
58 };
59
60 // Strict verification:
61 //
62 // * force DER encoding;
63 // * force low S;
64 // * ensure that CHECKMULTISIG dummy argument is null.
65 static const unsigned int STRICT_FORMAT_FLAGS = SCRIPT_VERIFY_STRICTENC | SCRIPT_VERIFY_LOW_S | SCRIPT_VERIFY_NULLDUMMY;
66
67 // Mandatory script verification flags that all new blocks must comply with for
68 // them to be valid. (but old blocks may not comply with) Currently just P2SH,
69 // but in the future other flags may be added, such as a soft-fork to enforce
70 // strict DER encoding.
71 //
72 // Failing one of these tests may trigger a DoS ban - see ConnectInputs() for
73 // details.
74 static const unsigned int MANDATORY_SCRIPT_VERIFY_FLAGS = SCRIPT_VERIFY_P2SH;
75
76 // Standard script verification flags that standard transactions will comply
77 // with. However scripts violating these flags may still be present in valid
78 // blocks and we must accept those blocks.
79 static const unsigned int STRICT_FLAGS = MANDATORY_SCRIPT_VERIFY_FLAGS | STRICT_FORMAT_FLAGS;
80
81 enum txnouttype
82 {
83     TX_NONSTANDARD,
84     // 'standard' transaction types:
85     TX_PUBKEY,
86     TX_PUBKEY_DROP,
87     TX_PUBKEYHASH,
88     TX_SCRIPTHASH,
89     TX_MULTISIG,
90     TX_NULL_DATA
91 };
92
93 const char* GetTxnOutputType(txnouttype t);
94
95 /** Script opcodes */
96 enum opcodetype
97 {
98     // push value
99     OP_0 = 0x00,
100     OP_FALSE = OP_0,
101     OP_PUSHDATA1 = 0x4c,
102     OP_PUSHDATA2 = 0x4d,
103     OP_PUSHDATA4 = 0x4e,
104     OP_1NEGATE = 0x4f,
105     OP_RESERVED = 0x50,
106     OP_1 = 0x51,
107     OP_TRUE=OP_1,
108     OP_2 = 0x52,
109     OP_3 = 0x53,
110     OP_4 = 0x54,
111     OP_5 = 0x55,
112     OP_6 = 0x56,
113     OP_7 = 0x57,
114     OP_8 = 0x58,
115     OP_9 = 0x59,
116     OP_10 = 0x5a,
117     OP_11 = 0x5b,
118     OP_12 = 0x5c,
119     OP_13 = 0x5d,
120     OP_14 = 0x5e,
121     OP_15 = 0x5f,
122     OP_16 = 0x60,
123
124     // control
125     OP_NOP = 0x61,
126     OP_VER = 0x62,
127     OP_IF = 0x63,
128     OP_NOTIF = 0x64,
129     OP_VERIF = 0x65,
130     OP_VERNOTIF = 0x66,
131     OP_ELSE = 0x67,
132     OP_ENDIF = 0x68,
133     OP_VERIFY = 0x69,
134     OP_RETURN = 0x6a,
135     OP_CHECKLOCKTIMEVERIFY = 0xb1,
136     OP_CHECKSEQUENCEVERIFY = 0xb2,
137
138     // stack ops
139     OP_TOALTSTACK = 0x6b,
140     OP_FROMALTSTACK = 0x6c,
141     OP_2DROP = 0x6d,
142     OP_2DUP = 0x6e,
143     OP_3DUP = 0x6f,
144     OP_2OVER = 0x70,
145     OP_2ROT = 0x71,
146     OP_2SWAP = 0x72,
147     OP_IFDUP = 0x73,
148     OP_DEPTH = 0x74,
149     OP_DROP = 0x75,
150     OP_DUP = 0x76,
151     OP_NIP = 0x77,
152     OP_OVER = 0x78,
153     OP_PICK = 0x79,
154     OP_ROLL = 0x7a,
155     OP_ROT = 0x7b,
156     OP_SWAP = 0x7c,
157     OP_TUCK = 0x7d,
158
159     // splice ops
160     OP_CAT = 0x7e,
161     OP_SUBSTR = 0x7f,
162     OP_LEFT = 0x80,
163     OP_RIGHT = 0x81,
164     OP_SIZE = 0x82,
165
166     // bit logic
167     OP_INVERT = 0x83,
168     OP_AND = 0x84,
169     OP_OR = 0x85,
170     OP_XOR = 0x86,
171     OP_EQUAL = 0x87,
172     OP_EQUALVERIFY = 0x88,
173     OP_RESERVED1 = 0x89,
174     OP_RESERVED2 = 0x8a,
175
176     // numeric
177     OP_1ADD = 0x8b,
178     OP_1SUB = 0x8c,
179     OP_2MUL = 0x8d,
180     OP_2DIV = 0x8e,
181     OP_NEGATE = 0x8f,
182     OP_ABS = 0x90,
183     OP_NOT = 0x91,
184     OP_0NOTEQUAL = 0x92,
185
186     OP_ADD = 0x93,
187     OP_SUB = 0x94,
188     OP_MUL = 0x95,
189     OP_DIV = 0x96,
190     OP_MOD = 0x97,
191     OP_LSHIFT = 0x98,
192     OP_RSHIFT = 0x99,
193
194     OP_BOOLAND = 0x9a,
195     OP_BOOLOR = 0x9b,
196     OP_NUMEQUAL = 0x9c,
197     OP_NUMEQUALVERIFY = 0x9d,
198     OP_NUMNOTEQUAL = 0x9e,
199     OP_LESSTHAN = 0x9f,
200     OP_GREATERTHAN = 0xa0,
201     OP_LESSTHANOREQUAL = 0xa1,
202     OP_GREATERTHANOREQUAL = 0xa2,
203     OP_MIN = 0xa3,
204     OP_MAX = 0xa4,
205
206     OP_WITHIN = 0xa5,
207
208     // crypto
209     OP_RIPEMD160 = 0xa6,
210     OP_SHA1 = 0xa7,
211     OP_SHA256 = 0xa8,
212     OP_HASH160 = 0xa9,
213     OP_HASH256 = 0xaa,
214     OP_CODESEPARATOR = 0xab,
215     OP_CHECKSIG = 0xac,
216     OP_CHECKSIGVERIFY = 0xad,
217     OP_CHECKMULTISIG = 0xae,
218     OP_CHECKMULTISIGVERIFY = 0xaf,
219
220     // expansion
221     OP_NOP1 = 0xb0,
222     OP_NOP4 = 0xb3,
223     OP_NOP5 = 0xb4,
224     OP_NOP6 = 0xb5,
225     OP_NOP7 = 0xb6,
226     OP_NOP8 = 0xb7,
227     OP_NOP9 = 0xb8,
228     OP_NOP10 = 0xb9,
229
230     // template matching params
231     OP_SMALLDATA = 0xf9,
232     OP_SMALLINTEGER = 0xfa,
233     OP_PUBKEYS = 0xfb,
234     OP_INTEGER = 0xfc,
235     OP_PUBKEYHASH = 0xfd,
236     OP_PUBKEY = 0xfe,
237
238     OP_INVALIDOPCODE = 0xff
239 };
240
241 const char* GetOpName(opcodetype opcode);
242
243 inline std::string ValueString(const std::vector<unsigned char>& vch)
244 {
245     if (vch.size() <= 4)
246         return strprintf("%d", CBigNum(vch).getint32());
247     else
248         return HexStr(vch);
249 }
250
251 inline std::string StackString(const std::vector<std::vector<unsigned char> >& vStack)
252 {
253     std::string str;
254     BOOST_FOREACH(const std::vector<unsigned char>& vch, vStack)
255     {
256         if (!str.empty())
257             str += " ";
258         str += ValueString(vch);
259     }
260     return str;
261 }
262
263 /** Serialized script, used inside transaction inputs and outputs */
264 class CScript : public std::vector<uint8_t>
265 {
266 protected:
267     CScript& push_int64(int64_t n)
268     {
269         if (n == -1 || (n >= 1 && n <= 16))
270         {
271             push_back((uint8_t)n + (OP_1 - 1));
272         }
273         else
274         {
275             CBigNum bn(n);
276             *this << bn.getvch();
277         }
278         return *this;
279     }
280
281     CScript& push_uint64(uint64_t n)
282     {
283         if (n >= 1 && n <= 16)
284         {
285             push_back((uint8_t)n + (OP_1 - 1));
286         }
287         else
288         {
289             CBigNum bn(n);
290             *this << bn.getvch();
291         }
292         return *this;
293     }
294
295 public:
296     CScript() { }
297     CScript(const CScript& b) : std::vector<uint8_t>(b.begin(), b.end()) { }
298     CScript(const_iterator pbegin, const_iterator pend) : std::vector<uint8_t>(pbegin, pend) { }
299 #ifndef _MSC_VER
300     CScript(const uint8_t* pbegin, const uint8_t* pend) : std::vector<uint8_t>(pbegin, pend) { }
301 #endif
302
303     CScript& operator+=(const CScript& b)
304     {
305         insert(end(), b.begin(), b.end());
306         return *this;
307     }
308
309     friend CScript operator+(const CScript& a, const CScript& b)
310     {
311         CScript ret = a;
312         ret += b;
313         return ret;
314     }
315
316     explicit CScript(int8_t  b) { operator<<(b); }
317     explicit CScript(int16_t b) { operator<<(b); }
318     explicit CScript(int32_t b) { operator<<(b); }
319     explicit CScript(int64_t b) { operator<<(b); }
320
321     explicit CScript(uint8_t  b) { operator<<(b); }
322     explicit CScript(uint16_t b) { operator<<(b); }
323     explicit CScript(uint32_t b) { operator<<(b); }
324     explicit CScript(uint64_t b) { operator<<(b); }
325
326     explicit CScript(opcodetype b)     { operator<<(b); }
327     explicit CScript(const uint256& b) { operator<<(b); }
328     explicit CScript(const CBigNum& b) { operator<<(b); }
329     explicit CScript(const std::vector<uint8_t>& b) { operator<<(b); }
330
331     CScript& operator<<(int8_t  b) { return push_int64(b); }
332     CScript& operator<<(int16_t b) { return push_int64(b); }
333     CScript& operator<<(int32_t b) { return push_int64(b); }
334     CScript& operator<<(int64_t b) { return push_int64(b); }
335
336     CScript& operator<<(uint8_t  b) { return push_uint64(b); }
337     CScript& operator<<(uint16_t b) { return push_uint64(b); }
338     CScript& operator<<(uint32_t b) { return push_uint64(b); }
339     CScript& operator<<(uint64_t b) { return push_uint64(b); }
340
341     CScript& operator<<(opcodetype opcode)
342     {
343         if (opcode < 0 || opcode > 0xff)
344             throw std::runtime_error("CScript::operator<<() : invalid opcode");
345         insert(end(), (uint8_t)opcode);
346         return *this;
347     }
348
349     CScript& operator<<(const uint160& b)
350     {
351         insert(end(), sizeof(b));
352         insert(end(), (uint8_t*)&b, (uint8_t*)&b + sizeof(b));
353         return *this;
354     }
355
356     CScript& operator<<(const uint256& b)
357     {
358         insert(end(), sizeof(b));
359         insert(end(), (uint8_t*)&b, (uint8_t*)&b + sizeof(b));
360         return *this;
361     }
362
363     CScript& operator<<(const CPubKey& key)
364     {
365         std::vector<uint8_t> vchKey = key.Raw();
366         return (*this) << vchKey;
367     }
368
369     CScript& operator<<(const CBigNum& b)
370     {
371         *this << b.getvch();
372         return *this;
373     }
374
375     CScript& operator<<(const std::vector<uint8_t>& b)
376     {
377         if (b.size() < OP_PUSHDATA1)
378         {
379             insert(end(), (uint8_t)b.size());
380         }
381         else if (b.size() <= 0xff)
382         {
383             insert(end(), OP_PUSHDATA1);
384             insert(end(), (uint8_t)b.size());
385         }
386         else if (b.size() <= 0xffff)
387         {
388             insert(end(), OP_PUSHDATA2);
389             uint16_t nSize = (uint16_t) b.size();
390             insert(end(), (uint8_t*)&nSize, (uint8_t*)&nSize + sizeof(nSize));
391         }
392         else
393         {
394             insert(end(), OP_PUSHDATA4);
395             uint32_t nSize = (uint32_t) b.size();
396             insert(end(), (uint8_t*)&nSize, (uint8_t*)&nSize + sizeof(nSize));
397         }
398         insert(end(), b.begin(), b.end());
399         return *this;
400     }
401
402     CScript& operator<<(const CScript& b)
403     {
404         // I'm not sure if this should push the script or concatenate scripts.
405         // If there's ever a use for pushing a script onto a script, delete this member fn
406         assert(!"Warning: Pushing a CScript onto a CScript with << is probably not intended, use + to concatenate!");
407         return *this;
408     }
409
410
411     bool GetOp(iterator& pc, opcodetype& opcodeRet, std::vector<uint8_t>& vchRet)
412     {
413          // Wrapper so it can be called with either iterator or const_iterator
414          const_iterator pc2 = pc;
415          bool fRet = GetOp2(pc2, opcodeRet, &vchRet);
416          pc = begin() + (pc2 - begin());
417          return fRet;
418     }
419
420     bool GetOp(iterator& pc, opcodetype& opcodeRet)
421     {
422          const_iterator pc2 = pc;
423          bool fRet = GetOp2(pc2, opcodeRet, NULL);
424          pc = begin() + (pc2 - begin());
425          return fRet;
426     }
427
428     bool GetOp(const_iterator& pc, opcodetype& opcodeRet, std::vector<uint8_t>& vchRet) const
429     {
430         return GetOp2(pc, opcodeRet, &vchRet);
431     }
432
433     bool GetOp(const_iterator& pc, opcodetype& opcodeRet) const
434     {
435         return GetOp2(pc, opcodeRet, NULL);
436     }
437
438     bool GetOp2(const_iterator& pc, opcodetype& opcodeRet, std::vector<uint8_t>* pvchRet) const
439     {
440         opcodeRet = OP_INVALIDOPCODE;
441         if (pvchRet)
442             pvchRet->clear();
443         if (pc >= end())
444             return false;
445
446         // Read instruction
447         if (end() - pc < 1)
448             return false;
449         uint32_t opcode = *pc++;
450
451         // Immediate operand
452         if (opcode <= OP_PUSHDATA4)
453         {
454             uint32_t nSize = OP_0;
455             if (opcode < OP_PUSHDATA1)
456             {
457                 nSize = opcode;
458             }
459             else if (opcode == OP_PUSHDATA1)
460             {
461                 if (end() - pc < 1)
462                     return false;
463                 nSize = *pc++;
464             }
465             else if (opcode == OP_PUSHDATA2)
466             {
467                 if (end() - pc < 2)
468                     return false;
469                 memcpy(&nSize, &pc[0], 2);
470                 pc += 2;
471             }
472             else if (opcode == OP_PUSHDATA4)
473             {
474                 if (end() - pc < 4)
475                     return false;
476                 memcpy(&nSize, &pc[0], 4);
477                 pc += 4;
478             }
479             if (end() - pc < 0 || (uint32_t)(end() - pc) < nSize)
480                 return false;
481             if (pvchRet)
482                 pvchRet->assign(pc, pc + nSize);
483             pc += nSize;
484         }
485
486         opcodeRet = (opcodetype)opcode;
487         return true;
488     }
489
490     // Encode/decode small integers:
491     static int DecodeOP_N(opcodetype opcode)
492     {
493         if (opcode == OP_0)
494             return 0;
495         assert(opcode >= OP_1 && opcode <= OP_16);
496         return (opcode - (OP_1 - 1));
497     }
498     static opcodetype EncodeOP_N(int n)
499     {
500         assert(n >= 0 && n <= 16);
501         if (n == 0)
502             return OP_0;
503         return (opcodetype)(OP_1+n-1);
504     }
505
506     int FindAndDelete(const CScript& b)
507     {
508         int nFound = 0;
509         if (b.empty())
510             return nFound;
511         iterator pc = begin();
512         opcodetype opcode;
513         do
514         {
515             while (end() - pc >= (long)b.size() && memcmp(&pc[0], &b[0], b.size()) == 0)
516             {
517                 erase(pc, pc + b.size());
518                 ++nFound;
519             }
520         }
521         while (GetOp(pc, opcode));
522         return nFound;
523     }
524     int Find(opcodetype op) const
525     {
526         int nFound = 0;
527         opcodetype opcode;
528         for (const_iterator pc = begin(); pc != end() && GetOp(pc, opcode);)
529             if (opcode == op)
530                 ++nFound;
531         return nFound;
532     }
533
534     // Pre-version-0.6, Bitcoin always counted CHECKMULTISIGs
535     // as 20 sigops. With pay-to-script-hash, that changed:
536     // CHECKMULTISIGs serialized in scriptSigs are
537     // counted more accurately, assuming they are of the form
538     //  ... OP_N CHECKMULTISIG ...
539     unsigned int GetSigOpCount(bool fAccurate) const;
540
541     // Accurately count sigOps, including sigOps in
542     // pay-to-script-hash transactions:
543     unsigned int GetSigOpCount(const CScript& scriptSig) const;
544
545     bool IsPayToScriptHash() const;
546
547     bool IsPushOnly(const_iterator pc) const
548     {
549         while (pc < end())
550         {
551             opcodetype opcode;
552             if (!GetOp(pc, opcode))
553                 return false;
554             if (opcode > OP_16)
555                 return false;
556         }
557         return true;
558     }
559
560     // Called by CTransaction::IsStandard and P2SH VerifyScript (which makes it consensus-critical).
561     bool IsPushOnly() const
562     {
563         return this->IsPushOnly(begin());
564     }
565
566     // Called by CTransaction::IsStandard.
567     bool HasCanonicalPushes() const;
568
569     void SetDestination(const CTxDestination& address);
570     void SetDestination(const CPubKey& R, CPubKey& pubKeyVariant);
571     void SetMultisig(int nRequired, const std::vector<CKey>& keys);
572
573
574     void PrintHex() const
575     {
576         printf("CScript(%s)\n", HexStr(begin(), end(), true).c_str());
577     }
578
579     std::string ToString(bool fShort=false) const
580     {
581         std::string str;
582         opcodetype opcode;
583         std::vector<uint8_t> vch;
584         const_iterator pc = begin();
585         while (pc < end())
586         {
587             if (!str.empty())
588                 str += " ";
589             if (!GetOp(pc, opcode, vch))
590             {
591                 str += "[error]";
592                 return str;
593             }
594             if (0 <= opcode && opcode <= OP_PUSHDATA4)
595                 str += fShort? ValueString(vch).substr(0, 10) : ValueString(vch);
596             else
597                 str += GetOpName(opcode);
598         }
599         return str;
600     }
601
602     void print() const
603     {
604         printf("%s\n", ToString().c_str());
605     }
606
607     CScriptID GetID() const
608     {
609         return CScriptID(Hash160(*this));
610     }
611 };
612
613 bool IsCanonicalPubKey(const std::vector<unsigned char> &vchPubKey, unsigned int flags);
614 bool IsDERSignature(const valtype &vchSig, bool fWithHashType=false, bool fCheckLow=false);
615 bool IsCanonicalSignature(const std::vector<unsigned char> &vchSig, unsigned int flags);
616
617 bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, const CTransaction& txTo, unsigned int nIn, unsigned int flags, int nHashType);
618 bool Solver(const CScript& scriptPubKey, txnouttype& typeRet, std::vector<std::vector<unsigned char> >& vSolutionsRet);
619 int ScriptSigArgsExpected(txnouttype t, const std::vector<std::vector<unsigned char> >& vSolutions);
620 bool IsStandard(const CScript& scriptPubKey, txnouttype& whichType);
621 isminetype IsMine(const CKeyStore& keystore, const CScript& scriptPubKey);
622 isminetype IsMine(const CKeyStore& keystore, const CTxDestination& dest);
623 void ExtractAffectedKeys(const CKeyStore &keystore, const CScript& scriptPubKey, std::vector<CKeyID> &vKeys);
624 bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet);
625 bool ExtractDestinations(const CScript& scriptPubKey, txnouttype& typeRet, std::vector<CTxDestination>& addressRet, int& nRequiredRet);
626 bool SignSignature(const CKeyStore& keystore, const CScript& fromPubKey, CTransaction& txTo, unsigned int nIn, int nHashType=SIGHASH_ALL);
627 bool SignSignature(const CKeyStore& keystore, const CTransaction& txFrom, CTransaction& txTo, unsigned int nIn, int nHashType=SIGHASH_ALL);
628 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn, unsigned int flags, int nHashType);
629
630 // Given two sets of signatures for scriptPubKey, possibly with OP_0 placeholders,
631 // combine them intelligently and return the result.
632 CScript CombineSignatures(const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn, const CScript& scriptSig1, const CScript& scriptSig2);
633
634 #endif