Support 3 new multisignature IsStandard transactions
[novacoin.git] / src / script.cpp
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2011 The Bitcoin developers
3 // Distributed under the MIT/X11 software license, see the accompanying
4 // file license.txt or http://www.opensource.org/licenses/mit-license.php.
5 #include "headers.h"
6
7 using namespace std;
8 using namespace boost;
9
10 bool CheckSig(vector<unsigned char> vchSig, vector<unsigned char> vchPubKey, CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType);
11
12
13
14 typedef vector<unsigned char> valtype;
15 static const valtype vchFalse(0);
16 static const valtype vchZero(0);
17 static const valtype vchTrue(1, 1);
18 static const CBigNum bnZero(0);
19 static const CBigNum bnOne(1);
20 static const CBigNum bnFalse(0);
21 static const CBigNum bnTrue(1);
22 static const size_t nMaxNumSize = 4;
23
24
25 CBigNum CastToBigNum(const valtype& vch)
26 {
27     if (vch.size() > nMaxNumSize)
28         throw runtime_error("CastToBigNum() : overflow");
29     // Get rid of extra leading zeros
30     return CBigNum(CBigNum(vch).getvch());
31 }
32
33 bool CastToBool(const valtype& vch)
34 {
35     for (int i = 0; i < vch.size(); i++)
36     {
37         if (vch[i] != 0)
38         {
39             // Can be negative zero
40             if (i == vch.size()-1 && vch[i] == 0x80)
41                 return false;
42             return true;
43         }
44     }
45     return false;
46 }
47
48 void MakeSameSize(valtype& vch1, valtype& vch2)
49 {
50     // Lengthen the shorter one
51     if (vch1.size() < vch2.size())
52         vch1.resize(vch2.size(), 0);
53     if (vch2.size() < vch1.size())
54         vch2.resize(vch1.size(), 0);
55 }
56
57
58
59 //
60 // Script is a stack machine (like Forth) that evaluates a predicate
61 // returning a bool indicating valid or not.  There are no loops.
62 //
63 #define stacktop(i)  (stack.at(stack.size()+(i)))
64 #define altstacktop(i)  (altstack.at(altstack.size()+(i)))
65 static inline void popstack(vector<valtype>& stack)
66 {
67     if (stack.empty())
68         throw runtime_error("popstack() : stack empty");
69     stack.pop_back();
70 }
71
72
73 bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, const CTransaction& txTo, unsigned int nIn, int nHashType)
74 {
75     CAutoBN_CTX pctx;
76     CScript::const_iterator pc = script.begin();
77     CScript::const_iterator pend = script.end();
78     CScript::const_iterator pbegincodehash = script.begin();
79     opcodetype opcode;
80     valtype vchPushValue;
81     vector<bool> vfExec;
82     vector<valtype> altstack;
83     if (script.size() > 10000)
84         return false;
85     int nOpCount = 0;
86
87
88     try
89     {
90         while (pc < pend)
91         {
92             bool fExec = !count(vfExec.begin(), vfExec.end(), false);
93
94             //
95             // Read instruction
96             //
97             if (!script.GetOp(pc, opcode, vchPushValue))
98                 return false;
99             if (vchPushValue.size() > 520)
100                 return false;
101             if (opcode > OP_16 && ++nOpCount > 201)
102                 return false;
103
104             if (opcode == OP_CAT ||
105                 opcode == OP_SUBSTR ||
106                 opcode == OP_LEFT ||
107                 opcode == OP_RIGHT ||
108                 opcode == OP_INVERT ||
109                 opcode == OP_AND ||
110                 opcode == OP_OR ||
111                 opcode == OP_XOR ||
112                 opcode == OP_2MUL ||
113                 opcode == OP_2DIV ||
114                 opcode == OP_MUL ||
115                 opcode == OP_DIV ||
116                 opcode == OP_MOD ||
117                 opcode == OP_LSHIFT ||
118                 opcode == OP_RSHIFT)
119                 return false;
120
121             if (fExec && 0 <= opcode && opcode <= OP_PUSHDATA4)
122                 stack.push_back(vchPushValue);
123             else if (fExec || (OP_IF <= opcode && opcode <= OP_ENDIF))
124             switch (opcode)
125             {
126                 //
127                 // Push value
128                 //
129                 case OP_1NEGATE:
130                 case OP_1:
131                 case OP_2:
132                 case OP_3:
133                 case OP_4:
134                 case OP_5:
135                 case OP_6:
136                 case OP_7:
137                 case OP_8:
138                 case OP_9:
139                 case OP_10:
140                 case OP_11:
141                 case OP_12:
142                 case OP_13:
143                 case OP_14:
144                 case OP_15:
145                 case OP_16:
146                 {
147                     // ( -- value)
148                     CBigNum bn((int)opcode - (int)(OP_1 - 1));
149                     stack.push_back(bn.getvch());
150                 }
151                 break;
152
153
154                 //
155                 // Control
156                 //
157                 case OP_NOP:
158                 case OP_NOP1: case OP_NOP2: case OP_NOP3: case OP_NOP4: case OP_NOP5:
159                 case OP_NOP6: case OP_NOP7: case OP_NOP8: case OP_NOP9: case OP_NOP10:
160                 break;
161
162                 case OP_IF:
163                 case OP_NOTIF:
164                 {
165                     // <expression> if [statements] [else [statements]] endif
166                     bool fValue = false;
167                     if (fExec)
168                     {
169                         if (stack.size() < 1)
170                             return false;
171                         valtype& vch = stacktop(-1);
172                         fValue = CastToBool(vch);
173                         if (opcode == OP_NOTIF)
174                             fValue = !fValue;
175                         popstack(stack);
176                     }
177                     vfExec.push_back(fValue);
178                 }
179                 break;
180
181                 case OP_ELSE:
182                 {
183                     if (vfExec.empty())
184                         return false;
185                     vfExec.back() = !vfExec.back();
186                 }
187                 break;
188
189                 case OP_ENDIF:
190                 {
191                     if (vfExec.empty())
192                         return false;
193                     vfExec.pop_back();
194                 }
195                 break;
196
197                 case OP_VERIFY:
198                 {
199                     // (true -- ) or
200                     // (false -- false) and return
201                     if (stack.size() < 1)
202                         return false;
203                     bool fValue = CastToBool(stacktop(-1));
204                     if (fValue)
205                         popstack(stack);
206                     else
207                         return false;
208                 }
209                 break;
210
211                 case OP_RETURN:
212                 {
213                     return false;
214                 }
215                 break;
216
217
218                 //
219                 // Stack ops
220                 //
221                 case OP_TOALTSTACK:
222                 {
223                     if (stack.size() < 1)
224                         return false;
225                     altstack.push_back(stacktop(-1));
226                     popstack(stack);
227                 }
228                 break;
229
230                 case OP_FROMALTSTACK:
231                 {
232                     if (altstack.size() < 1)
233                         return false;
234                     stack.push_back(altstacktop(-1));
235                     popstack(altstack);
236                 }
237                 break;
238
239                 case OP_2DROP:
240                 {
241                     // (x1 x2 -- )
242                     if (stack.size() < 2)
243                         return false;
244                     popstack(stack);
245                     popstack(stack);
246                 }
247                 break;
248
249                 case OP_2DUP:
250                 {
251                     // (x1 x2 -- x1 x2 x1 x2)
252                     if (stack.size() < 2)
253                         return false;
254                     valtype vch1 = stacktop(-2);
255                     valtype vch2 = stacktop(-1);
256                     stack.push_back(vch1);
257                     stack.push_back(vch2);
258                 }
259                 break;
260
261                 case OP_3DUP:
262                 {
263                     // (x1 x2 x3 -- x1 x2 x3 x1 x2 x3)
264                     if (stack.size() < 3)
265                         return false;
266                     valtype vch1 = stacktop(-3);
267                     valtype vch2 = stacktop(-2);
268                     valtype vch3 = stacktop(-1);
269                     stack.push_back(vch1);
270                     stack.push_back(vch2);
271                     stack.push_back(vch3);
272                 }
273                 break;
274
275                 case OP_2OVER:
276                 {
277                     // (x1 x2 x3 x4 -- x1 x2 x3 x4 x1 x2)
278                     if (stack.size() < 4)
279                         return false;
280                     valtype vch1 = stacktop(-4);
281                     valtype vch2 = stacktop(-3);
282                     stack.push_back(vch1);
283                     stack.push_back(vch2);
284                 }
285                 break;
286
287                 case OP_2ROT:
288                 {
289                     // (x1 x2 x3 x4 x5 x6 -- x3 x4 x5 x6 x1 x2)
290                     if (stack.size() < 6)
291                         return false;
292                     valtype vch1 = stacktop(-6);
293                     valtype vch2 = stacktop(-5);
294                     stack.erase(stack.end()-6, stack.end()-4);
295                     stack.push_back(vch1);
296                     stack.push_back(vch2);
297                 }
298                 break;
299
300                 case OP_2SWAP:
301                 {
302                     // (x1 x2 x3 x4 -- x3 x4 x1 x2)
303                     if (stack.size() < 4)
304                         return false;
305                     swap(stacktop(-4), stacktop(-2));
306                     swap(stacktop(-3), stacktop(-1));
307                 }
308                 break;
309
310                 case OP_IFDUP:
311                 {
312                     // (x - 0 | x x)
313                     if (stack.size() < 1)
314                         return false;
315                     valtype vch = stacktop(-1);
316                     if (CastToBool(vch))
317                         stack.push_back(vch);
318                 }
319                 break;
320
321                 case OP_DEPTH:
322                 {
323                     // -- stacksize
324                     CBigNum bn(stack.size());
325                     stack.push_back(bn.getvch());
326                 }
327                 break;
328
329                 case OP_DROP:
330                 {
331                     // (x -- )
332                     if (stack.size() < 1)
333                         return false;
334                     popstack(stack);
335                 }
336                 break;
337
338                 case OP_DUP:
339                 {
340                     // (x -- x x)
341                     if (stack.size() < 1)
342                         return false;
343                     valtype vch = stacktop(-1);
344                     stack.push_back(vch);
345                 }
346                 break;
347
348                 case OP_NIP:
349                 {
350                     // (x1 x2 -- x2)
351                     if (stack.size() < 2)
352                         return false;
353                     stack.erase(stack.end() - 2);
354                 }
355                 break;
356
357                 case OP_OVER:
358                 {
359                     // (x1 x2 -- x1 x2 x1)
360                     if (stack.size() < 2)
361                         return false;
362                     valtype vch = stacktop(-2);
363                     stack.push_back(vch);
364                 }
365                 break;
366
367                 case OP_PICK:
368                 case OP_ROLL:
369                 {
370                     // (xn ... x2 x1 x0 n - xn ... x2 x1 x0 xn)
371                     // (xn ... x2 x1 x0 n - ... x2 x1 x0 xn)
372                     if (stack.size() < 2)
373                         return false;
374                     int n = CastToBigNum(stacktop(-1)).getint();
375                     popstack(stack);
376                     if (n < 0 || n >= stack.size())
377                         return false;
378                     valtype vch = stacktop(-n-1);
379                     if (opcode == OP_ROLL)
380                         stack.erase(stack.end()-n-1);
381                     stack.push_back(vch);
382                 }
383                 break;
384
385                 case OP_ROT:
386                 {
387                     // (x1 x2 x3 -- x2 x3 x1)
388                     //  x2 x1 x3  after first swap
389                     //  x2 x3 x1  after second swap
390                     if (stack.size() < 3)
391                         return false;
392                     swap(stacktop(-3), stacktop(-2));
393                     swap(stacktop(-2), stacktop(-1));
394                 }
395                 break;
396
397                 case OP_SWAP:
398                 {
399                     // (x1 x2 -- x2 x1)
400                     if (stack.size() < 2)
401                         return false;
402                     swap(stacktop(-2), stacktop(-1));
403                 }
404                 break;
405
406                 case OP_TUCK:
407                 {
408                     // (x1 x2 -- x2 x1 x2)
409                     if (stack.size() < 2)
410                         return false;
411                     valtype vch = stacktop(-1);
412                     stack.insert(stack.end()-2, vch);
413                 }
414                 break;
415
416
417                 //
418                 // Splice ops
419                 //
420                 case OP_CAT:
421                 {
422                     // (x1 x2 -- out)
423                     if (stack.size() < 2)
424                         return false;
425                     valtype& vch1 = stacktop(-2);
426                     valtype& vch2 = stacktop(-1);
427                     vch1.insert(vch1.end(), vch2.begin(), vch2.end());
428                     popstack(stack);
429                     if (stacktop(-1).size() > 520)
430                         return false;
431                 }
432                 break;
433
434                 case OP_SUBSTR:
435                 {
436                     // (in begin size -- out)
437                     if (stack.size() < 3)
438                         return false;
439                     valtype& vch = stacktop(-3);
440                     int nBegin = CastToBigNum(stacktop(-2)).getint();
441                     int nEnd = nBegin + CastToBigNum(stacktop(-1)).getint();
442                     if (nBegin < 0 || nEnd < nBegin)
443                         return false;
444                     if (nBegin > vch.size())
445                         nBegin = vch.size();
446                     if (nEnd > vch.size())
447                         nEnd = vch.size();
448                     vch.erase(vch.begin() + nEnd, vch.end());
449                     vch.erase(vch.begin(), vch.begin() + nBegin);
450                     popstack(stack);
451                     popstack(stack);
452                 }
453                 break;
454
455                 case OP_LEFT:
456                 case OP_RIGHT:
457                 {
458                     // (in size -- out)
459                     if (stack.size() < 2)
460                         return false;
461                     valtype& vch = stacktop(-2);
462                     int nSize = CastToBigNum(stacktop(-1)).getint();
463                     if (nSize < 0)
464                         return false;
465                     if (nSize > vch.size())
466                         nSize = vch.size();
467                     if (opcode == OP_LEFT)
468                         vch.erase(vch.begin() + nSize, vch.end());
469                     else
470                         vch.erase(vch.begin(), vch.end() - nSize);
471                     popstack(stack);
472                 }
473                 break;
474
475                 case OP_SIZE:
476                 {
477                     // (in -- in size)
478                     if (stack.size() < 1)
479                         return false;
480                     CBigNum bn(stacktop(-1).size());
481                     stack.push_back(bn.getvch());
482                 }
483                 break;
484
485
486                 //
487                 // Bitwise logic
488                 //
489                 case OP_INVERT:
490                 {
491                     // (in - out)
492                     if (stack.size() < 1)
493                         return false;
494                     valtype& vch = stacktop(-1);
495                     for (int i = 0; i < vch.size(); i++)
496                         vch[i] = ~vch[i];
497                 }
498                 break;
499
500                 case OP_AND:
501                 case OP_OR:
502                 case OP_XOR:
503                 {
504                     // (x1 x2 - out)
505                     if (stack.size() < 2)
506                         return false;
507                     valtype& vch1 = stacktop(-2);
508                     valtype& vch2 = stacktop(-1);
509                     MakeSameSize(vch1, vch2);
510                     if (opcode == OP_AND)
511                     {
512                         for (int i = 0; i < vch1.size(); i++)
513                             vch1[i] &= vch2[i];
514                     }
515                     else if (opcode == OP_OR)
516                     {
517                         for (int i = 0; i < vch1.size(); i++)
518                             vch1[i] |= vch2[i];
519                     }
520                     else if (opcode == OP_XOR)
521                     {
522                         for (int i = 0; i < vch1.size(); i++)
523                             vch1[i] ^= vch2[i];
524                     }
525                     popstack(stack);
526                 }
527                 break;
528
529                 case OP_EQUAL:
530                 case OP_EQUALVERIFY:
531                 //case OP_NOTEQUAL: // use OP_NUMNOTEQUAL
532                 {
533                     // (x1 x2 - bool)
534                     if (stack.size() < 2)
535                         return false;
536                     valtype& vch1 = stacktop(-2);
537                     valtype& vch2 = stacktop(-1);
538                     bool fEqual = (vch1 == vch2);
539                     // OP_NOTEQUAL is disabled because it would be too easy to say
540                     // something like n != 1 and have some wiseguy pass in 1 with extra
541                     // zero bytes after it (numerically, 0x01 == 0x0001 == 0x000001)
542                     //if (opcode == OP_NOTEQUAL)
543                     //    fEqual = !fEqual;
544                     popstack(stack);
545                     popstack(stack);
546                     stack.push_back(fEqual ? vchTrue : vchFalse);
547                     if (opcode == OP_EQUALVERIFY)
548                     {
549                         if (fEqual)
550                             popstack(stack);
551                         else
552                             return false;
553                     }
554                 }
555                 break;
556
557
558                 //
559                 // Numeric
560                 //
561                 case OP_1ADD:
562                 case OP_1SUB:
563                 case OP_2MUL:
564                 case OP_2DIV:
565                 case OP_NEGATE:
566                 case OP_ABS:
567                 case OP_NOT:
568                 case OP_0NOTEQUAL:
569                 {
570                     // (in -- out)
571                     if (stack.size() < 1)
572                         return false;
573                     CBigNum bn = CastToBigNum(stacktop(-1));
574                     switch (opcode)
575                     {
576                     case OP_1ADD:       bn += bnOne; break;
577                     case OP_1SUB:       bn -= bnOne; break;
578                     case OP_2MUL:       bn <<= 1; break;
579                     case OP_2DIV:       bn >>= 1; break;
580                     case OP_NEGATE:     bn = -bn; break;
581                     case OP_ABS:        if (bn < bnZero) bn = -bn; break;
582                     case OP_NOT:        bn = (bn == bnZero); break;
583                     case OP_0NOTEQUAL:  bn = (bn != bnZero); break;
584                     default:            assert(!"invalid opcode"); break;
585                     }
586                     popstack(stack);
587                     stack.push_back(bn.getvch());
588                 }
589                 break;
590
591                 case OP_ADD:
592                 case OP_SUB:
593                 case OP_MUL:
594                 case OP_DIV:
595                 case OP_MOD:
596                 case OP_LSHIFT:
597                 case OP_RSHIFT:
598                 case OP_BOOLAND:
599                 case OP_BOOLOR:
600                 case OP_NUMEQUAL:
601                 case OP_NUMEQUALVERIFY:
602                 case OP_NUMNOTEQUAL:
603                 case OP_LESSTHAN:
604                 case OP_GREATERTHAN:
605                 case OP_LESSTHANOREQUAL:
606                 case OP_GREATERTHANOREQUAL:
607                 case OP_MIN:
608                 case OP_MAX:
609                 {
610                     // (x1 x2 -- out)
611                     if (stack.size() < 2)
612                         return false;
613                     CBigNum bn1 = CastToBigNum(stacktop(-2));
614                     CBigNum bn2 = CastToBigNum(stacktop(-1));
615                     CBigNum bn;
616                     switch (opcode)
617                     {
618                     case OP_ADD:
619                         bn = bn1 + bn2;
620                         break;
621
622                     case OP_SUB:
623                         bn = bn1 - bn2;
624                         break;
625
626                     case OP_MUL:
627                         if (!BN_mul(&bn, &bn1, &bn2, pctx))
628                             return false;
629                         break;
630
631                     case OP_DIV:
632                         if (!BN_div(&bn, NULL, &bn1, &bn2, pctx))
633                             return false;
634                         break;
635
636                     case OP_MOD:
637                         if (!BN_mod(&bn, &bn1, &bn2, pctx))
638                             return false;
639                         break;
640
641                     case OP_LSHIFT:
642                         if (bn2 < bnZero || bn2 > CBigNum(2048))
643                             return false;
644                         bn = bn1 << bn2.getulong();
645                         break;
646
647                     case OP_RSHIFT:
648                         if (bn2 < bnZero || bn2 > CBigNum(2048))
649                             return false;
650                         bn = bn1 >> bn2.getulong();
651                         break;
652
653                     case OP_BOOLAND:             bn = (bn1 != bnZero && bn2 != bnZero); break;
654                     case OP_BOOLOR:              bn = (bn1 != bnZero || bn2 != bnZero); break;
655                     case OP_NUMEQUAL:            bn = (bn1 == bn2); break;
656                     case OP_NUMEQUALVERIFY:      bn = (bn1 == bn2); break;
657                     case OP_NUMNOTEQUAL:         bn = (bn1 != bn2); break;
658                     case OP_LESSTHAN:            bn = (bn1 < bn2); break;
659                     case OP_GREATERTHAN:         bn = (bn1 > bn2); break;
660                     case OP_LESSTHANOREQUAL:     bn = (bn1 <= bn2); break;
661                     case OP_GREATERTHANOREQUAL:  bn = (bn1 >= bn2); break;
662                     case OP_MIN:                 bn = (bn1 < bn2 ? bn1 : bn2); break;
663                     case OP_MAX:                 bn = (bn1 > bn2 ? bn1 : bn2); break;
664                     default:                     assert(!"invalid opcode"); break;
665                     }
666                     popstack(stack);
667                     popstack(stack);
668                     stack.push_back(bn.getvch());
669
670                     if (opcode == OP_NUMEQUALVERIFY)
671                     {
672                         if (CastToBool(stacktop(-1)))
673                             popstack(stack);
674                         else
675                             return false;
676                     }
677                 }
678                 break;
679
680                 case OP_WITHIN:
681                 {
682                     // (x min max -- out)
683                     if (stack.size() < 3)
684                         return false;
685                     CBigNum bn1 = CastToBigNum(stacktop(-3));
686                     CBigNum bn2 = CastToBigNum(stacktop(-2));
687                     CBigNum bn3 = CastToBigNum(stacktop(-1));
688                     bool fValue = (bn2 <= bn1 && bn1 < bn3);
689                     popstack(stack);
690                     popstack(stack);
691                     popstack(stack);
692                     stack.push_back(fValue ? vchTrue : vchFalse);
693                 }
694                 break;
695
696
697                 //
698                 // Crypto
699                 //
700                 case OP_RIPEMD160:
701                 case OP_SHA1:
702                 case OP_SHA256:
703                 case OP_HASH160:
704                 case OP_HASH256:
705                 {
706                     // (in -- hash)
707                     if (stack.size() < 1)
708                         return false;
709                     valtype& vch = stacktop(-1);
710                     valtype vchHash((opcode == OP_RIPEMD160 || opcode == OP_SHA1 || opcode == OP_HASH160) ? 20 : 32);
711                     if (opcode == OP_RIPEMD160)
712                         RIPEMD160(&vch[0], vch.size(), &vchHash[0]);
713                     else if (opcode == OP_SHA1)
714                         SHA1(&vch[0], vch.size(), &vchHash[0]);
715                     else if (opcode == OP_SHA256)
716                         SHA256(&vch[0], vch.size(), &vchHash[0]);
717                     else if (opcode == OP_HASH160)
718                     {
719                         uint160 hash160 = Hash160(vch);
720                         memcpy(&vchHash[0], &hash160, sizeof(hash160));
721                     }
722                     else if (opcode == OP_HASH256)
723                     {
724                         uint256 hash = Hash(vch.begin(), vch.end());
725                         memcpy(&vchHash[0], &hash, sizeof(hash));
726                     }
727                     popstack(stack);
728                     stack.push_back(vchHash);
729                 }
730                 break;
731
732                 case OP_CODESEPARATOR:
733                 {
734                     // Hash starts after the code separator
735                     pbegincodehash = pc;
736                 }
737                 break;
738
739                 case OP_CHECKSIG:
740                 case OP_CHECKSIGVERIFY:
741                 {
742                     // (sig pubkey -- bool)
743                     if (stack.size() < 2)
744                         return false;
745
746                     valtype& vchSig    = stacktop(-2);
747                     valtype& vchPubKey = stacktop(-1);
748
749                     ////// debug print
750                     //PrintHex(vchSig.begin(), vchSig.end(), "sig: %s\n");
751                     //PrintHex(vchPubKey.begin(), vchPubKey.end(), "pubkey: %s\n");
752
753                     // Subset of script starting at the most recent codeseparator
754                     CScript scriptCode(pbegincodehash, pend);
755
756                     // Drop the signature, since there's no way for a signature to sign itself
757                     scriptCode.FindAndDelete(CScript(vchSig));
758
759                     bool fSuccess = CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType);
760
761                     popstack(stack);
762                     popstack(stack);
763                     stack.push_back(fSuccess ? vchTrue : vchFalse);
764                     if (opcode == OP_CHECKSIGVERIFY)
765                     {
766                         if (fSuccess)
767                             popstack(stack);
768                         else
769                             return false;
770                     }
771                 }
772                 break;
773
774                 case OP_CHECKMULTISIG:
775                 case OP_CHECKMULTISIGVERIFY:
776                 {
777                     // ([sig ...] num_of_signatures [pubkey ...] num_of_pubkeys -- bool)
778
779                     int i = 1;
780                     if (stack.size() < i)
781                         return false;
782
783                     int nKeysCount = CastToBigNum(stacktop(-i)).getint();
784                     if (nKeysCount < 0 || nKeysCount > 20)
785                         return false;
786                     nOpCount += nKeysCount;
787                     if (nOpCount > 201)
788                         return false;
789                     int ikey = ++i;
790                     i += nKeysCount;
791                     if (stack.size() < i)
792                         return false;
793
794                     int nSigsCount = CastToBigNum(stacktop(-i)).getint();
795                     if (nSigsCount < 0 || nSigsCount > nKeysCount)
796                         return false;
797                     int isig = ++i;
798                     i += nSigsCount;
799                     if (stack.size() < i)
800                         return false;
801
802                     // Subset of script starting at the most recent codeseparator
803                     CScript scriptCode(pbegincodehash, pend);
804
805                     // Drop the signatures, since there's no way for a signature to sign itself
806                     for (int k = 0; k < nSigsCount; k++)
807                     {
808                         valtype& vchSig = stacktop(-isig-k);
809                         scriptCode.FindAndDelete(CScript(vchSig));
810                     }
811
812                     bool fSuccess = true;
813                     while (fSuccess && nSigsCount > 0)
814                     {
815                         valtype& vchSig    = stacktop(-isig);
816                         valtype& vchPubKey = stacktop(-ikey);
817
818                         // Check signature
819                         if (CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType))
820                         {
821                             isig++;
822                             nSigsCount--;
823                         }
824                         ikey++;
825                         nKeysCount--;
826
827                         // If there are more signatures left than keys left,
828                         // then too many signatures have failed
829                         if (nSigsCount > nKeysCount)
830                             fSuccess = false;
831                     }
832
833                     while (i-- > 0)
834                         popstack(stack);
835                     stack.push_back(fSuccess ? vchTrue : vchFalse);
836
837                     if (opcode == OP_CHECKMULTISIGVERIFY)
838                     {
839                         if (fSuccess)
840                             popstack(stack);
841                         else
842                             return false;
843                     }
844                 }
845                 break;
846
847                 default:
848                     return false;
849             }
850
851             // Size limits
852             if (stack.size() + altstack.size() > 1000)
853                 return false;
854         }
855     }
856     catch (...)
857     {
858         return false;
859     }
860
861
862     if (!vfExec.empty())
863         return false;
864
865     return true;
866 }
867
868
869
870
871
872
873
874
875
876 uint256 SignatureHash(CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType)
877 {
878     if (nIn >= txTo.vin.size())
879     {
880         printf("ERROR: SignatureHash() : nIn=%d out of range\n", nIn);
881         return 1;
882     }
883     CTransaction txTmp(txTo);
884
885     // In case concatenating two scripts ends up with two codeseparators,
886     // or an extra one at the end, this prevents all those possible incompatibilities.
887     scriptCode.FindAndDelete(CScript(OP_CODESEPARATOR));
888
889     // Blank out other inputs' signatures
890     for (int i = 0; i < txTmp.vin.size(); i++)
891         txTmp.vin[i].scriptSig = CScript();
892     txTmp.vin[nIn].scriptSig = scriptCode;
893
894     // Blank out some of the outputs
895     if ((nHashType & 0x1f) == SIGHASH_NONE)
896     {
897         // Wildcard payee
898         txTmp.vout.clear();
899
900         // Let the others update at will
901         for (int i = 0; i < txTmp.vin.size(); i++)
902             if (i != nIn)
903                 txTmp.vin[i].nSequence = 0;
904     }
905     else if ((nHashType & 0x1f) == SIGHASH_SINGLE)
906     {
907         // Only lockin the txout payee at same index as txin
908         unsigned int nOut = nIn;
909         if (nOut >= txTmp.vout.size())
910         {
911             printf("ERROR: SignatureHash() : nOut=%d out of range\n", nOut);
912             return 1;
913         }
914         txTmp.vout.resize(nOut+1);
915         for (int i = 0; i < nOut; i++)
916             txTmp.vout[i].SetNull();
917
918         // Let the others update at will
919         for (int i = 0; i < txTmp.vin.size(); i++)
920             if (i != nIn)
921                 txTmp.vin[i].nSequence = 0;
922     }
923
924     // Blank out other inputs completely, not recommended for open transactions
925     if (nHashType & SIGHASH_ANYONECANPAY)
926     {
927         txTmp.vin[0] = txTmp.vin[nIn];
928         txTmp.vin.resize(1);
929     }
930
931     // Serialize and hash
932     CDataStream ss(SER_GETHASH);
933     ss.reserve(10000);
934     ss << txTmp << nHashType;
935     return Hash(ss.begin(), ss.end());
936 }
937
938
939 bool CheckSig(vector<unsigned char> vchSig, vector<unsigned char> vchPubKey, CScript scriptCode,
940               const CTransaction& txTo, unsigned int nIn, int nHashType)
941 {
942     CKey key;
943     if (!key.SetPubKey(vchPubKey))
944         return false;
945
946     // Hash type is one byte tacked on to the end of the signature
947     if (vchSig.empty())
948         return false;
949     if (nHashType == 0)
950         nHashType = vchSig.back();
951     else if (nHashType != vchSig.back())
952         return false;
953     vchSig.pop_back();
954
955     return key.Verify(SignatureHash(scriptCode, txTo, nIn, nHashType), vchSig);
956 }
957
958
959
960
961
962
963
964
965
966 //
967 // Returns lists of public keys (or public key hashes), any one of which can
968 // satisfy scriptPubKey
969 //
970 bool Solver(const CScript& scriptPubKey, vector<vector<pair<opcodetype, valtype> > >& vSolutionsRet)
971 {
972     // Templates
973     static vector<CScript> vTemplates;
974     if (vTemplates.empty())
975     {
976         // Standard tx, sender provides pubkey, receiver adds signature
977         vTemplates.push_back(CScript() << OP_PUBKEY << OP_CHECKSIG);
978
979         // Bitcoin address tx, sender provides hash of pubkey, receiver provides signature and pubkey
980         vTemplates.push_back(CScript() << OP_DUP << OP_HASH160 << OP_PUBKEYHASH << OP_EQUALVERIFY << OP_CHECKSIG);
981
982         // Sender provides two pubkeys, receivers provides two signatures
983         vTemplates.push_back(CScript() << OP_2 << OP_PUBKEY << OP_PUBKEY << OP_2 << OP_CHECKMULTISIG);
984
985         // Sender provides two pubkeys, receivers provides one of two signatures
986         vTemplates.push_back(CScript() << OP_1 << OP_PUBKEY << OP_PUBKEY << OP_2 << OP_CHECKMULTISIG);
987
988         // Sender provides three pubkeys, receiver provides 2 of 3 signatures.
989         vTemplates.push_back(CScript() << OP_2 << OP_PUBKEY << OP_PUBKEY << OP_PUBKEY << OP_3 << OP_CHECKMULTISIG);
990     }
991
992     // Scan templates
993     const CScript& script1 = scriptPubKey;
994     BOOST_FOREACH(const CScript& script2, vTemplates)
995     {
996         vSolutionsRet.clear();
997
998         vector<pair<opcodetype, valtype> > currentSolution;
999         opcodetype opcode1, opcode2;
1000         vector<unsigned char> vch1, vch2;
1001
1002         // Compare
1003         CScript::const_iterator pc1 = script1.begin();
1004         CScript::const_iterator pc2 = script2.begin();
1005         loop
1006         {
1007             if (pc1 == script1.end() && pc2 == script2.end())
1008             {
1009                 return !vSolutionsRet.empty();
1010             }
1011             if (!script1.GetOp(pc1, opcode1, vch1))
1012                 break;
1013             if (!script2.GetOp(pc2, opcode2, vch2))
1014                 break;
1015             if (opcode2 == OP_PUBKEY)
1016             {
1017                 if (vch1.size() < 33 || vch1.size() > 120)
1018                     break;
1019                 currentSolution.push_back(make_pair(opcode2, vch1));
1020             }
1021             else if (opcode2 == OP_PUBKEYHASH)
1022             {
1023                 if (vch1.size() != sizeof(uint160))
1024                     break;
1025                 currentSolution.push_back(make_pair(opcode2, vch1));
1026             }
1027             else if (opcode2 == OP_CHECKSIG)
1028             {
1029                 vSolutionsRet.push_back(currentSolution);
1030                 currentSolution.clear();
1031             }
1032             else if (opcode2 == OP_CHECKMULTISIG)
1033             {   // Dig out the "m" from before the pubkeys:
1034                 CScript::const_iterator it = script2.begin();
1035                 opcodetype op_m;
1036                 script2.GetOp(it, op_m, vch1);
1037                 int m = CScript::DecodeOP_N(op_m);
1038                 int n = currentSolution.size();
1039
1040                 if (m == 2 && n == 2)
1041                 {
1042                     vSolutionsRet.push_back(currentSolution);
1043                     currentSolution.clear();
1044                 }
1045                 else if (m == 1 && n == 2)
1046                 { // 2 solutions: either first key or second
1047                     for (int i = 0; i < 2; i++)
1048                     {
1049                         vector<pair<opcodetype, valtype> > s;
1050                         s.push_back(currentSolution[i]);
1051                         vSolutionsRet.push_back(s);
1052                     }
1053                     currentSolution.clear();
1054                 }
1055                 else if (m == 2 && n == 3)
1056                 { // 3 solutions: any pair
1057                     for (int i = 0; i < 2; i++)
1058                         for (int j = i+1; j < 3; j++)
1059                         {
1060                             vector<pair<opcodetype, valtype> > s;
1061                             s.push_back(currentSolution[i]);
1062                             s.push_back(currentSolution[j]);
1063                             vSolutionsRet.push_back(s);
1064                         }
1065                     currentSolution.clear();
1066                 }
1067             }
1068             else if (opcode1 != opcode2 || vch1 != vch2)
1069             {
1070                 break;
1071             }
1072         }
1073     }
1074
1075     vSolutionsRet.clear();
1076     return false;
1077 }
1078
1079
1080 bool Solver(const CKeyStore& keystore, const CScript& scriptPubKey, uint256 hash, int nHashType, CScript& scriptSigRet)
1081 {
1082     scriptSigRet.clear();
1083
1084     vector<vector<pair<opcodetype, valtype> > > vSolutions;
1085     if (!Solver(scriptPubKey, vSolutions))
1086         return false;
1087
1088     // See if we have all the keys for any of the solutions:
1089     int whichSolution = -1;
1090     for (int i = 0; i < vSolutions.size(); i++)
1091     {
1092         int keysFound = 0;
1093         CScript scriptSig;
1094
1095         BOOST_FOREACH(PAIRTYPE(opcodetype, valtype)& item, vSolutions[i])
1096         {
1097             if (item.first == OP_PUBKEY)
1098             {
1099                 const valtype& vchPubKey = item.second;
1100                 CKey key;
1101                 vector<unsigned char> vchSig;
1102                 if (keystore.GetKey(Hash160(vchPubKey), key) && key.GetPubKey() == vchPubKey
1103                     && hash != 0 && key.Sign(hash, vchSig))
1104                 {
1105                     vchSig.push_back((unsigned char)nHashType);
1106                     scriptSig << vchSig;
1107                     ++keysFound;
1108                 }
1109             }
1110             else if (item.first == OP_PUBKEYHASH)
1111             {
1112                 CKey key;
1113                 vector<unsigned char> vchSig;
1114                 if (keystore.GetKey(uint160(item.second), key) 
1115                     && hash != 0 && key.Sign(hash, vchSig))
1116                 {
1117                     vchSig.push_back((unsigned char)nHashType);
1118                     scriptSig << vchSig << key.GetPubKey();
1119                     ++keysFound;
1120                 }
1121             }
1122         }
1123         if (keysFound == vSolutions[i].size())
1124         {
1125             whichSolution = i;
1126             scriptSigRet = scriptSig;
1127             break;
1128         }
1129     }
1130     if (whichSolution == -1)
1131         return false;
1132
1133     // CHECKMULTISIG bug workaround:
1134     if (vSolutions.size() != 1 ||
1135         vSolutions[0].size() != 1)
1136     {
1137         scriptSigRet.insert(scriptSigRet.begin(), OP_0);
1138     }
1139
1140     return true;
1141 }
1142
1143
1144 bool IsStandard(const CScript& scriptPubKey)
1145 {
1146     vector<vector<pair<opcodetype, valtype> > > vSolutions;
1147     return Solver(scriptPubKey, vSolutions);
1148 }
1149
1150
1151 bool IsMine(const CKeyStore &keystore, const CScript& scriptPubKey)
1152 {
1153     vector<vector<pair<opcodetype, valtype> > > vSolutions;
1154     if (!Solver(scriptPubKey, vSolutions))
1155         return false;
1156
1157     int keysFound = 0;
1158     int keysRequired = 0;
1159     for (int i = 0; i < vSolutions.size(); i++)
1160     {
1161         BOOST_FOREACH(PAIRTYPE(opcodetype, valtype)& item, vSolutions[i])
1162         {
1163             ++keysRequired;
1164             if (item.first == OP_PUBKEY)
1165             {
1166                 const valtype& vchPubKey = item.second;
1167                 vector<unsigned char> vchPubKeyFound;
1168                 if (keystore.GetPubKey(Hash160(vchPubKey), vchPubKeyFound) && vchPubKeyFound == vchPubKey)
1169                     ++keysFound;
1170             }
1171             else if (item.first == OP_PUBKEYHASH)
1172             {
1173                 if (keystore.HaveKey(uint160(item.second)))
1174                     ++keysFound;
1175             }
1176         }
1177     }
1178
1179     // Only consider transactions "mine" if we own ALL the
1180     // keys involved. multi-signature transactions that are
1181     // partially owned (somebody else has a key that can spend
1182     // them) enable spend-out-from-under-you attacks, especially
1183     // for shared-wallet situations.
1184     return (keysFound == keysRequired);
1185 }
1186
1187 bool ExtractAddress(const CScript& scriptPubKey, const CKeyStore* keystore, CBitcoinAddress& addressRet)
1188 {
1189     vector<vector<pair<opcodetype, valtype> > > vSolutions;
1190     if (!Solver(scriptPubKey, vSolutions))
1191         return false;
1192
1193     for (int i = 0; i < vSolutions.size(); i++)
1194     {
1195         if (vSolutions[i].size() != 1)
1196             continue; // Can't return more than one address...
1197
1198         PAIRTYPE(opcodetype, valtype)& item = vSolutions[i][0];
1199         if (item.first == OP_PUBKEY)
1200             addressRet.SetPubKey(item.second);
1201         else if (item.first == OP_PUBKEYHASH)
1202             addressRet.SetHash160((uint160)item.second);
1203         if (keystore == NULL || keystore->HaveKey(addressRet))
1204             return true;
1205     }
1206     return false;
1207 }
1208
1209
1210
1211 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn, int nHashType)
1212 {
1213     vector<vector<unsigned char> > stack;
1214     if (!EvalScript(stack, scriptSig, txTo, nIn, nHashType))
1215         return false;
1216     if (!EvalScript(stack, scriptPubKey, txTo, nIn, nHashType))
1217         return false;
1218     if (stack.empty())
1219         return false;
1220     return CastToBool(stack.back());
1221 }
1222
1223
1224 bool SignSignature(const CKeyStore &keystore, const CTransaction& txFrom, CTransaction& txTo, unsigned int nIn, int nHashType, CScript scriptPrereq)
1225 {
1226     assert(nIn < txTo.vin.size());
1227     CTxIn& txin = txTo.vin[nIn];
1228     assert(txin.prevout.n < txFrom.vout.size());
1229     const CTxOut& txout = txFrom.vout[txin.prevout.n];
1230
1231     // Leave out the signature from the hash, since a signature can't sign itself.
1232     // The checksig op will also drop the signatures from its hash.
1233     uint256 hash = SignatureHash(scriptPrereq + txout.scriptPubKey, txTo, nIn, nHashType);
1234
1235     if (!Solver(keystore, txout.scriptPubKey, hash, nHashType, txin.scriptSig))
1236         return false;
1237
1238     txin.scriptSig = scriptPrereq + txin.scriptSig;
1239
1240     // Test solution
1241     if (scriptPrereq.empty())
1242         if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, 0))
1243             return false;
1244
1245     return true;
1246 }
1247
1248
1249 bool VerifySignature(const CTransaction& txFrom, const CTransaction& txTo, unsigned int nIn, int nHashType)
1250 {
1251     assert(nIn < txTo.vin.size());
1252     const CTxIn& txin = txTo.vin[nIn];
1253     if (txin.prevout.n >= txFrom.vout.size())
1254         return false;
1255     const CTxOut& txout = txFrom.vout[txin.prevout.n];
1256
1257     if (txin.prevout.hash != txFrom.GetHash())
1258         return false;
1259
1260     if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, nHashType))
1261         return false;
1262
1263     return true;
1264 }
1265
1266 void CScript::SetMultisigAnd(const std::vector<CKey>& keys)
1267 {
1268     assert(keys.size() >= 2);
1269     this->clear();
1270     *this << OP_2 << keys[0].GetPubKey() << keys[1].GetPubKey() << OP_2 << OP_CHECKMULTISIG;
1271 }
1272 void CScript::SetMultisigOr(const std::vector<CKey>& keys)
1273 {
1274     assert(keys.size() >= 2);
1275     this->clear();
1276     *this << OP_1 << keys[0].GetPubKey() << keys[1].GetPubKey() << OP_2 << OP_CHECKMULTISIG;
1277 }
1278 void CScript::SetMultisigEscrow(const std::vector<CKey>& keys)
1279 {
1280     assert(keys.size() >= 3);
1281     this->clear();
1282     *this << OP_2 << keys[0].GetPubKey() << keys[1].GetPubKey() << keys[1].GetPubKey() << OP_3 << OP_CHECKMULTISIG;
1283 }