src/script.cpp

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