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)
 780                         return false;
 781                     int ikey = ++i;
 782                     i += nKeysCount;
 783                     if (stack.size() < i)
 784                         return false;
 785
 786                     int nSigsCount = CastToBigNum(stacktop(-i)).getint();
 787                     if (nSigsCount < 0 || nSigsCount > nKeysCount)
 788                         return false;
 789                     int isig = ++i;
 790                     i += nSigsCount;
 791                     if (stack.size() < i)
 792                         return false;
 793
 794                     // Subset of script starting at the most recent codeseparator
 795                     CScript scriptCode(pbegincodehash, pend);
 796
 797                     // Drop the signatures, since there's no way for a signature to sign itself
 798                     for (int k = 0; k < nSigsCount; k++)
 799                     {
 800                         valtype& vchSig = stacktop(-isig-k);
 801                         scriptCode.FindAndDelete(CScript(vchSig));
 802                     }
 803
 804                     bool fSuccess = true;
 805                     while (fSuccess && nSigsCount > 0)
 806                     {
 807                         valtype& vchSig    = stacktop(-isig);
 808                         valtype& vchPubKey = stacktop(-ikey);
 809
 810                         // Check signature
 811                         if (CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType))
 812                         {
 813                             isig++;
 814                             nSigsCount--;
 815                         }
 816                         ikey++;
 817                         nKeysCount--;
 818
 819                         // If there are more signatures left than keys left,
 820                         // then too many signatures have failed
 821                         if (nSigsCount > nKeysCount)
 822                             fSuccess = false;
 823                     }
 824
 825                     while (i-- > 0)
 826                         popstack(stack);
 827                     stack.push_back(fSuccess ? vchTrue : vchFalse);
 828
 829                     if (opcode == OP_CHECKMULTISIGVERIFY)
 830                     {
 831                         if (fSuccess)
 832                             popstack(stack);
 833                         else
 834                             return false;
 835                     }
 836                 }
 837                 break;
 838
 839                 default:
 840                     return false;
 841             }
 842
 843             // Size limits
 844             if (stack.size() + altstack.size() > 1000)
 845                 return false;
 846         }
 847     }
 848     catch (...)
 849     {
 850         return false;
 851     }
 852
 853
 854     if (!vfExec.empty())
 855         return false;
 856
 857     return true;
 858 }
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868 uint256 SignatureHash(CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType)
 869 {
 870     if (nIn >= txTo.vin.size())
 871     {
 872         printf("ERROR: SignatureHash() : nIn=%d out of range\n", nIn);
 873         return 1;
 874     }
 875     CTransaction txTmp(txTo);
 876
 877     // In case concatenating two scripts ends up with two codeseparators,
 878     // or an extra one at the end, this prevents all those possible incompatibilities.
 879     scriptCode.FindAndDelete(CScript(OP_CODESEPARATOR));
 880
 881     // Blank out other inputs' signatures
 882     for (int i = 0; i < txTmp.vin.size(); i++)
 883         txTmp.vin[i].scriptSig = CScript();
 884     txTmp.vin[nIn].scriptSig = scriptCode;
 885
 886     // Blank out some of the outputs
 887     if ((nHashType & 0x1f) == SIGHASH_NONE)
 888     {
 889         // Wildcard payee
 890         txTmp.vout.clear();
 891
 892         // Let the others update at will
 893         for (int i = 0; i < txTmp.vin.size(); i++)
 894             if (i != nIn)
 895                 txTmp.vin[i].nSequence = 0;
 896     }
 897     else if ((nHashType & 0x1f) == SIGHASH_SINGLE)
 898     {
 899         // Only lockin the txout payee at same index as txin
 900         unsigned int nOut = nIn;
 901         if (nOut >= txTmp.vout.size())
 902         {
 903             printf("ERROR: SignatureHash() : nOut=%d out of range\n", nOut);
 904             return 1;
 905         }
 906         txTmp.vout.resize(nOut+1);
 907         for (int i = 0; i < nOut; i++)
 908             txTmp.vout[i].SetNull();
 909
 910         // Let the others update at will
 911         for (int i = 0; i < txTmp.vin.size(); i++)
 912             if (i != nIn)
 913                 txTmp.vin[i].nSequence = 0;
 914     }
 915
 916     // Blank out other inputs completely, not recommended for open transactions
 917     if (nHashType & SIGHASH_ANYONECANPAY)
 918     {
 919         txTmp.vin[0] = txTmp.vin[nIn];
 920         txTmp.vin.resize(1);
 921     }
 922
 923     // Serialize and hash
 924     CDataStream ss(SER_GETHASH);
 925     ss.reserve(10000);
 926     ss << txTmp << nHashType;
 927     return Hash(ss.begin(), ss.end());
 928 }
 929
 930
 931 bool CheckSig(vector<unsigned char> vchSig, vector<unsigned char> vchPubKey, CScript scriptCode,
 932               const CTransaction& txTo, unsigned int nIn, int nHashType)
 933 {
 934     CKey key;
 935     if (!key.SetPubKey(vchPubKey))
 936         return false;
 937
 938     // Hash type is one byte tacked on to the end of the signature
 939     if (vchSig.empty())
 940         return false;
 941     if (nHashType == 0)
 942         nHashType = vchSig.back();
 943     else if (nHashType != vchSig.back())
 944         return false;
 945     vchSig.pop_back();
 946
 947     return key.Verify(SignatureHash(scriptCode, txTo, nIn, nHashType), vchSig);
 948 }
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959 bool Solver(const CScript& scriptPubKey, vector<pair<opcodetype, valtype> >& vSolutionRet)
 960 {
 961     // Templates
 962     static vector<CScript> vTemplates;
 963     if (vTemplates.empty())
 964     {
 965         // Standard tx, sender provides pubkey, receiver adds signature
 966         vTemplates.push_back(CScript() << OP_PUBKEY << OP_CHECKSIG);
 967
 968         // Bitcoin address tx, sender provides hash of pubkey, receiver provides signature and pubkey
 969         vTemplates.push_back(CScript() << OP_DUP << OP_HASH160 << OP_PUBKEYHASH << OP_EQUALVERIFY << OP_CHECKSIG);
 970     }
 971
 972     // Scan templates
 973     const CScript& script1 = scriptPubKey;
 974     foreach(const CScript& script2, vTemplates)
 975     {
 976         vSolutionRet.clear();
 977         opcodetype opcode1, opcode2;
 978         vector<unsigned char> vch1, vch2;
 979
 980         // Compare
 981         CScript::const_iterator pc1 = script1.begin();
 982         CScript::const_iterator pc2 = script2.begin();
 983         loop
 984         {
 985             if (pc1 == script1.end() && pc2 == script2.end())
 986             {
 987                 // Found a match
 988                 reverse(vSolutionRet.begin(), vSolutionRet.end());
 989                 return true;
 990             }
 991             if (!script1.GetOp(pc1, opcode1, vch1))
 992                 break;
 993             if (!script2.GetOp(pc2, opcode2, vch2))
 994                 break;
 995             if (opcode2 == OP_PUBKEY)
 996             {
 997                 if (vch1.size() < 33)
 998                     break;
 999                 vSolutionRet.push_back(make_pair(opcode2, vch1));
1000             }
1001             else if (opcode2 == OP_PUBKEYHASH)
1002             {
1003                 if (vch1.size() != sizeof(uint160))
1004                     break;
1005                 vSolutionRet.push_back(make_pair(opcode2, vch1));
1006             }
1007             else if (opcode1 != opcode2 || vch1 != vch2)
1008             {
1009                 break;
1010             }
1011         }
1012     }
1013
1014     vSolutionRet.clear();
1015     return false;
1016 }
1017
1018
1019 bool Solver(const CScript& scriptPubKey, uint256 hash, int nHashType, CScript& scriptSigRet)
1020 {
1021     scriptSigRet.clear();
1022
1023     vector<pair<opcodetype, valtype> > vSolution;
1024     if (!Solver(scriptPubKey, vSolution))
1025         return false;
1026
1027     // Compile solution
1028     CRITICAL_BLOCK(cs_mapKeys)
1029     {
1030         foreach(PAIRTYPE(opcodetype, valtype)& item, vSolution)
1031         {
1032             if (item.first == OP_PUBKEY)
1033             {
1034                 // Sign
1035                 const valtype& vchPubKey = item.second;
1036                 if (!mapKeys.count(vchPubKey))
1037                     return false;
1038                 if (hash != 0)
1039                 {
1040                     vector<unsigned char> vchSig;
1041                     if (!CKey::Sign(mapKeys[vchPubKey], hash, vchSig))
1042                         return false;
1043                     vchSig.push_back((unsigned char)nHashType);
1044                     scriptSigRet << vchSig;
1045                 }
1046             }
1047             else if (item.first == OP_PUBKEYHASH)
1048             {
1049                 // Sign and give pubkey
1050                 map<uint160, valtype>::iterator mi = mapPubKeys.find(uint160(item.second));
1051                 if (mi == mapPubKeys.end())
1052                     return false;
1053                 const vector<unsigned char>& vchPubKey = (*mi).second;
1054                 if (!mapKeys.count(vchPubKey))
1055                     return false;
1056                 if (hash != 0)
1057                 {
1058                     vector<unsigned char> vchSig;
1059                     if (!CKey::Sign(mapKeys[vchPubKey], hash, vchSig))
1060                         return false;
1061                     vchSig.push_back((unsigned char)nHashType);
1062                     scriptSigRet << vchSig << vchPubKey;
1063                 }
1064             }
1065             else
1066             {
1067                 return false;
1068             }
1069         }
1070     }
1071
1072     return true;
1073 }
1074
1075
1076 bool IsMine(const CScript& scriptPubKey)
1077 {
1078     CScript scriptSig;
1079     return Solver(scriptPubKey, 0, 0, scriptSig);
1080 }
1081
1082
1083 bool ExtractPubKey(const CScript& scriptPubKey, bool fMineOnly, vector<unsigned char>& vchPubKeyRet)
1084 {
1085     vchPubKeyRet.clear();
1086
1087     vector<pair<opcodetype, valtype> > vSolution;
1088     if (!Solver(scriptPubKey, vSolution))
1089         return false;
1090
1091     CRITICAL_BLOCK(cs_mapKeys)
1092     {
1093         foreach(PAIRTYPE(opcodetype, valtype)& item, vSolution)
1094         {
1095             valtype vchPubKey;
1096             if (item.first == OP_PUBKEY)
1097             {
1098                 vchPubKey = item.second;
1099             }
1100             else if (item.first == OP_PUBKEYHASH)
1101             {
1102                 map<uint160, valtype>::iterator mi = mapPubKeys.find(uint160(item.second));
1103                 if (mi == mapPubKeys.end())
1104                     continue;
1105                 vchPubKey = (*mi).second;
1106             }
1107             if (!fMineOnly || mapKeys.count(vchPubKey))
1108             {
1109                 vchPubKeyRet = vchPubKey;
1110                 return true;
1111             }
1112         }
1113     }
1114     return false;
1115 }
1116
1117
1118 bool ExtractHash160(const CScript& scriptPubKey, uint160& hash160Ret)
1119 {
1120     hash160Ret = 0;
1121
1122     vector<pair<opcodetype, valtype> > vSolution;
1123     if (!Solver(scriptPubKey, vSolution))
1124         return false;
1125
1126     foreach(PAIRTYPE(opcodetype, valtype)& item, vSolution)
1127     {
1128         if (item.first == OP_PUBKEYHASH)
1129         {
1130             hash160Ret = uint160(item.second);
1131             return true;
1132         }
1133     }
1134     return false;
1135 }
1136
1137
1138 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn, int nHashType)
1139 {
1140     vector<vector<unsigned char> > stack;
1141     if (!EvalScript(stack, scriptSig, txTo, nIn, nHashType))
1142         return false;
1143     if (!EvalScript(stack, scriptPubKey, txTo, nIn, nHashType))
1144         return false;
1145     if (stack.empty())
1146         return false;
1147     return CastToBool(stack.back());
1148 }
1149
1150
1151 bool SignSignature(const CTransaction& txFrom, CTransaction& txTo, unsigned int nIn, int nHashType, CScript scriptPrereq)
1152 {
1153     assert(nIn < txTo.vin.size());
1154     CTxIn& txin = txTo.vin[nIn];
1155     assert(txin.prevout.n < txFrom.vout.size());
1156     const CTxOut& txout = txFrom.vout[txin.prevout.n];
1157
1158     // Leave out the signature from the hash, since a signature can't sign itself.
1159     // The checksig op will also drop the signatures from its hash.
1160     uint256 hash = SignatureHash(scriptPrereq + txout.scriptPubKey, txTo, nIn, nHashType);
1161
1162     if (!Solver(txout.scriptPubKey, hash, nHashType, txin.scriptSig))
1163         return false;
1164
1165     txin.scriptSig = scriptPrereq + txin.scriptSig;
1166
1167     // Test solution
1168     if (scriptPrereq.empty())
1169         if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, 0))
1170             return false;
1171
1172     return true;
1173 }
1174
1175
1176 bool VerifySignature(const CTransaction& txFrom, const CTransaction& txTo, unsigned int nIn, int nHashType)
1177 {
1178     assert(nIn < txTo.vin.size());
1179     const CTxIn& txin = txTo.vin[nIn];
1180     if (txin.prevout.n >= txFrom.vout.size())
1181         return false;
1182     const CTxOut& txout = txFrom.vout[txin.prevout.n];
1183
1184     if (txin.prevout.hash != txFrom.GetHash())
1185         return false;
1186
1187     if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, nHashType))
1188         return false;
1189
1190     // Anytime a signature is successfully verified, it's proof the outpoint is spent,
1191     // so lets update the wallet spent flag if it doesn't know due to wallet.dat being
1192     // restored from backup or the user making copies of wallet.dat.
1193     WalletUpdateSpent(txin.prevout);
1194
1195     return true;
1196 }