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