script.cpp

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