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