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                     if (nBestHeight > 84000)
 782                     {
 783                         if (nKeysCount > 20)
 784                             return false;
 785                         nOpCount += nKeysCount;
 786                         if (nOpCount > 201)
 787                             return false;
 788                     }
 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 bool Solver(const CScript& scriptPubKey, vector<pair<opcodetype, valtype> >& vSolutionRet)
 968 {
 969     // Templates
 970     static vector<CScript> vTemplates;
 971     if (vTemplates.empty())
 972     {
 973         // Standard tx, sender provides pubkey, receiver adds signature
 974         vTemplates.push_back(CScript() << OP_PUBKEY << OP_CHECKSIG);
 975
 976         // Bitcoin address tx, sender provides hash of pubkey, receiver provides signature and pubkey
 977         vTemplates.push_back(CScript() << OP_DUP << OP_HASH160 << OP_PUBKEYHASH << OP_EQUALVERIFY << OP_CHECKSIG);
 978     }
 979
 980     // Scan templates
 981     const CScript& script1 = scriptPubKey;
 982     foreach(const CScript& script2, vTemplates)
 983     {
 984         vSolutionRet.clear();
 985         opcodetype opcode1, opcode2;
 986         vector<unsigned char> vch1, vch2;
 987
 988         // Compare
 989         CScript::const_iterator pc1 = script1.begin();
 990         CScript::const_iterator pc2 = script2.begin();
 991         loop
 992         {
 993             if (pc1 == script1.end() && pc2 == script2.end())
 994             {
 995                 // Found a match
 996                 reverse(vSolutionRet.begin(), vSolutionRet.end());
 997                 return true;
 998             }
 999             if (!script1.GetOp(pc1, opcode1, vch1))
1000                 break;
1001             if (!script2.GetOp(pc2, opcode2, vch2))
1002                 break;
1003             if (opcode2 == OP_PUBKEY)
1004             {
1005                 if (vch1.size() < 33)
1006                     break;
1007                 vSolutionRet.push_back(make_pair(opcode2, vch1));
1008             }
1009             else if (opcode2 == OP_PUBKEYHASH)
1010             {
1011                 if (vch1.size() != sizeof(uint160))
1012                     break;
1013                 vSolutionRet.push_back(make_pair(opcode2, vch1));
1014             }
1015             else if (opcode1 != opcode2 || vch1 != vch2)
1016             {
1017                 break;
1018             }
1019         }
1020     }
1021
1022     vSolutionRet.clear();
1023     return false;
1024 }
1025
1026
1027 bool Solver(const CScript& scriptPubKey, uint256 hash, int nHashType, CScript& scriptSigRet)
1028 {
1029     scriptSigRet.clear();
1030
1031     vector<pair<opcodetype, valtype> > vSolution;
1032     if (!Solver(scriptPubKey, vSolution))
1033         return false;
1034
1035     // Compile solution
1036     CRITICAL_BLOCK(cs_mapKeys)
1037     {
1038         foreach(PAIRTYPE(opcodetype, valtype)& item, vSolution)
1039         {
1040             if (item.first == OP_PUBKEY)
1041             {
1042                 // Sign
1043                 const valtype& vchPubKey = item.second;
1044                 if (!mapKeys.count(vchPubKey))
1045                     return false;
1046                 if (hash != 0)
1047                 {
1048                     vector<unsigned char> vchSig;
1049                     if (!CKey::Sign(mapKeys[vchPubKey], hash, vchSig))
1050                         return false;
1051                     vchSig.push_back((unsigned char)nHashType);
1052                     scriptSigRet << vchSig;
1053                 }
1054             }
1055             else if (item.first == OP_PUBKEYHASH)
1056             {
1057                 // Sign and give pubkey
1058                 map<uint160, valtype>::iterator mi = mapPubKeys.find(uint160(item.second));
1059                 if (mi == mapPubKeys.end())
1060                     return false;
1061                 const vector<unsigned char>& vchPubKey = (*mi).second;
1062                 if (!mapKeys.count(vchPubKey))
1063                     return false;
1064                 if (hash != 0)
1065                 {
1066                     vector<unsigned char> vchSig;
1067                     if (!CKey::Sign(mapKeys[vchPubKey], hash, vchSig))
1068                         return false;
1069                     vchSig.push_back((unsigned char)nHashType);
1070                     scriptSigRet << vchSig << vchPubKey;
1071                 }
1072             }
1073             else
1074             {
1075                 return false;
1076             }
1077         }
1078     }
1079
1080     return true;
1081 }
1082
1083
1084 bool IsMine(const CScript& scriptPubKey)
1085 {
1086     CScript scriptSig;
1087     return Solver(scriptPubKey, 0, 0, scriptSig);
1088 }
1089
1090
1091 bool ExtractPubKey(const CScript& scriptPubKey, bool fMineOnly, vector<unsigned char>& vchPubKeyRet)
1092 {
1093     vchPubKeyRet.clear();
1094
1095     vector<pair<opcodetype, valtype> > vSolution;
1096     if (!Solver(scriptPubKey, vSolution))
1097         return false;
1098
1099     CRITICAL_BLOCK(cs_mapKeys)
1100     {
1101         foreach(PAIRTYPE(opcodetype, valtype)& item, vSolution)
1102         {
1103             valtype vchPubKey;
1104             if (item.first == OP_PUBKEY)
1105             {
1106                 vchPubKey = item.second;
1107             }
1108             else if (item.first == OP_PUBKEYHASH)
1109             {
1110                 map<uint160, valtype>::iterator mi = mapPubKeys.find(uint160(item.second));
1111                 if (mi == mapPubKeys.end())
1112                     continue;
1113                 vchPubKey = (*mi).second;
1114             }
1115             if (!fMineOnly || mapKeys.count(vchPubKey))
1116             {
1117                 vchPubKeyRet = vchPubKey;
1118                 return true;
1119             }
1120         }
1121     }
1122     return false;
1123 }
1124
1125
1126 bool ExtractHash160(const CScript& scriptPubKey, uint160& hash160Ret)
1127 {
1128     hash160Ret = 0;
1129
1130     vector<pair<opcodetype, valtype> > vSolution;
1131     if (!Solver(scriptPubKey, vSolution))
1132         return false;
1133
1134     foreach(PAIRTYPE(opcodetype, valtype)& item, vSolution)
1135     {
1136         if (item.first == OP_PUBKEYHASH)
1137         {
1138             hash160Ret = uint160(item.second);
1139             return true;
1140         }
1141     }
1142     return false;
1143 }
1144
1145
1146 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn, int nHashType)
1147 {
1148     vector<vector<unsigned char> > stack;
1149     if (!EvalScript(stack, scriptSig, txTo, nIn, nHashType))
1150         return false;
1151     if (!EvalScript(stack, scriptPubKey, txTo, nIn, nHashType))
1152         return false;
1153     if (stack.empty())
1154         return false;
1155     return CastToBool(stack.back());
1156 }
1157
1158
1159 bool SignSignature(const CTransaction& txFrom, CTransaction& txTo, unsigned int nIn, int nHashType, CScript scriptPrereq)
1160 {
1161     assert(nIn < txTo.vin.size());
1162     CTxIn& txin = txTo.vin[nIn];
1163     assert(txin.prevout.n < txFrom.vout.size());
1164     const CTxOut& txout = txFrom.vout[txin.prevout.n];
1165
1166     // Leave out the signature from the hash, since a signature can't sign itself.
1167     // The checksig op will also drop the signatures from its hash.
1168     uint256 hash = SignatureHash(scriptPrereq + txout.scriptPubKey, txTo, nIn, nHashType);
1169
1170     if (!Solver(txout.scriptPubKey, hash, nHashType, txin.scriptSig))
1171         return false;
1172
1173     txin.scriptSig = scriptPrereq + txin.scriptSig;
1174
1175     // Test solution
1176     if (scriptPrereq.empty())
1177         if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, 0))
1178             return false;
1179
1180     return true;
1181 }
1182
1183
1184 bool VerifySignature(const CTransaction& txFrom, const CTransaction& txTo, unsigned int nIn, int nHashType)
1185 {
1186     assert(nIn < txTo.vin.size());
1187     const CTxIn& txin = txTo.vin[nIn];
1188     if (txin.prevout.n >= txFrom.vout.size())
1189         return false;
1190     const CTxOut& txout = txFrom.vout[txin.prevout.n];
1191
1192     if (txin.prevout.hash != txFrom.GetHash())
1193         return false;
1194
1195     if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, nHashType))
1196         return false;
1197
1198     // Anytime a signature is successfully verified, it's proof the outpoint is spent,
1199     // so lets update the wallet spent flag if it doesn't know due to wallet.dat being
1200     // restored from backup or the user making copies of wallet.dat.
1201     WalletUpdateSpent(txin.prevout);
1202
1203     return true;
1204 }