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