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