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                     default:            assert(!"invalid opcode"); break;
 584                     }
 585                     popstack(stack);
 586                     stack.push_back(bn.getvch());
 587                 }
 588                 break;
 589
 590                 case OP_ADD:
 591                 case OP_SUB:
 592                 case OP_MUL:
 593                 case OP_DIV:
 594                 case OP_MOD:
 595                 case OP_LSHIFT:
 596                 case OP_RSHIFT:
 597                 case OP_BOOLAND:
 598                 case OP_BOOLOR:
 599                 case OP_NUMEQUAL:
 600                 case OP_NUMEQUALVERIFY:
 601                 case OP_NUMNOTEQUAL:
 602                 case OP_LESSTHAN:
 603                 case OP_GREATERTHAN:
 604                 case OP_LESSTHANOREQUAL:
 605                 case OP_GREATERTHANOREQUAL:
 606                 case OP_MIN:
 607                 case OP_MAX:
 608                 {
 609                     // (x1 x2 -- out)
 610                     if (stack.size() < 2)
 611                         return false;
 612                     CBigNum bn1 = CastToBigNum(stacktop(-2));
 613                     CBigNum bn2 = CastToBigNum(stacktop(-1));
 614                     CBigNum bn;
 615                     switch (opcode)
 616                     {
 617                     case OP_ADD:
 618                         bn = bn1 + bn2;
 619                         break;
 620
 621                     case OP_SUB:
 622                         bn = bn1 - bn2;
 623                         break;
 624
 625                     case OP_MUL:
 626                         if (!BN_mul(&bn, &bn1, &bn2, pctx))
 627                             return false;
 628                         break;
 629
 630                     case OP_DIV:
 631                         if (!BN_div(&bn, NULL, &bn1, &bn2, pctx))
 632                             return false;
 633                         break;
 634
 635                     case OP_MOD:
 636                         if (!BN_mod(&bn, &bn1, &bn2, pctx))
 637                             return false;
 638                         break;
 639
 640                     case OP_LSHIFT:
 641                         if (bn2 < bnZero || bn2 > CBigNum(2048))
 642                             return false;
 643                         bn = bn1 << bn2.getulong();
 644                         break;
 645
 646                     case OP_RSHIFT:
 647                         if (bn2 < bnZero || bn2 > CBigNum(2048))
 648                             return false;
 649                         bn = bn1 >> bn2.getulong();
 650                         break;
 651
 652                     case OP_BOOLAND:             bn = (bn1 != bnZero && bn2 != bnZero); break;
 653                     case OP_BOOLOR:              bn = (bn1 != bnZero || bn2 != bnZero); break;
 654                     case OP_NUMEQUAL:            bn = (bn1 == bn2); break;
 655                     case OP_NUMEQUALVERIFY:      bn = (bn1 == bn2); break;
 656                     case OP_NUMNOTEQUAL:         bn = (bn1 != bn2); break;
 657                     case OP_LESSTHAN:            bn = (bn1 < bn2); break;
 658                     case OP_GREATERTHAN:         bn = (bn1 > bn2); break;
 659                     case OP_LESSTHANOREQUAL:     bn = (bn1 <= bn2); break;
 660                     case OP_GREATERTHANOREQUAL:  bn = (bn1 >= bn2); break;
 661                     case OP_MIN:                 bn = (bn1 < bn2 ? bn1 : bn2); break;
 662                     case OP_MAX:                 bn = (bn1 > bn2 ? bn1 : bn2); break;
 663                     default:                     assert(!"invalid opcode"); break;
 664                     }
 665                     popstack(stack);
 666                     popstack(stack);
 667                     stack.push_back(bn.getvch());
 668
 669                     if (opcode == OP_NUMEQUALVERIFY)
 670                     {
 671                         if (CastToBool(stacktop(-1)))
 672                             popstack(stack);
 673                         else
 674                             return false;
 675                     }
 676                 }
 677                 break;
 678
 679                 case OP_WITHIN:
 680                 {
 681                     // (x min max -- out)
 682                     if (stack.size() < 3)
 683                         return false;
 684                     CBigNum bn1 = CastToBigNum(stacktop(-3));
 685                     CBigNum bn2 = CastToBigNum(stacktop(-2));
 686                     CBigNum bn3 = CastToBigNum(stacktop(-1));
 687                     bool fValue = (bn2 <= bn1 && bn1 < bn3);
 688                     popstack(stack);
 689                     popstack(stack);
 690                     popstack(stack);
 691                     stack.push_back(fValue ? vchTrue : vchFalse);
 692                 }
 693                 break;
 694
 695
 696                 //
 697                 // Crypto
 698                 //
 699                 case OP_RIPEMD160:
 700                 case OP_SHA1:
 701                 case OP_SHA256:
 702                 case OP_HASH160:
 703                 case OP_HASH256:
 704                 {
 705                     // (in -- hash)
 706                     if (stack.size() < 1)
 707                         return false;
 708                     valtype& vch = stacktop(-1);
 709                     valtype vchHash((opcode == OP_RIPEMD160 || opcode == OP_SHA1 || opcode == OP_HASH160) ? 20 : 32);
 710                     if (opcode == OP_RIPEMD160)
 711                         RIPEMD160(&vch[0], vch.size(), &vchHash[0]);
 712                     else if (opcode == OP_SHA1)
 713                         SHA1(&vch[0], vch.size(), &vchHash[0]);
 714                     else if (opcode == OP_SHA256)
 715                         SHA256(&vch[0], vch.size(), &vchHash[0]);
 716                     else if (opcode == OP_HASH160)
 717                     {
 718                         uint160 hash160 = Hash160(vch);
 719                         memcpy(&vchHash[0], &hash160, sizeof(hash160));
 720                     }
 721                     else if (opcode == OP_HASH256)
 722                     {
 723                         uint256 hash = Hash(vch.begin(), vch.end());
 724                         memcpy(&vchHash[0], &hash, sizeof(hash));
 725                     }
 726                     popstack(stack);
 727                     stack.push_back(vchHash);
 728                 }
 729                 break;
 730
 731                 case OP_CODESEPARATOR:
 732                 {
 733                     // Hash starts after the code separator
 734                     pbegincodehash = pc;
 735                 }
 736                 break;
 737
 738                 case OP_CHECKSIG:
 739                 case OP_CHECKSIGVERIFY:
 740                 {
 741                     // (sig pubkey -- bool)
 742                     if (stack.size() < 2)
 743                         return false;
 744
 745                     valtype& vchSig    = stacktop(-2);
 746                     valtype& vchPubKey = stacktop(-1);
 747
 748                     ////// debug print
 749                     //PrintHex(vchSig.begin(), vchSig.end(), "sig: %s\n");
 750                     //PrintHex(vchPubKey.begin(), vchPubKey.end(), "pubkey: %s\n");
 751
 752                     // Subset of script starting at the most recent codeseparator
 753                     CScript scriptCode(pbegincodehash, pend);
 754
 755                     // Drop the signature, since there's no way for a signature to sign itself
 756                     scriptCode.FindAndDelete(CScript(vchSig));
 757
 758                     bool fSuccess = CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType);
 759
 760                     popstack(stack);
 761                     popstack(stack);
 762                     stack.push_back(fSuccess ? vchTrue : vchFalse);
 763                     if (opcode == OP_CHECKSIGVERIFY)
 764                     {
 765                         if (fSuccess)
 766                             popstack(stack);
 767                         else
 768                             return false;
 769                     }
 770                 }
 771                 break;
 772
 773                 case OP_CHECKMULTISIG:
 774                 case OP_CHECKMULTISIGVERIFY:
 775                 {
 776                     // ([sig ...] num_of_signatures [pubkey ...] num_of_pubkeys -- bool)
 777
 778                     int i = 1;
 779                     if (stack.size() < i)
 780                         return false;
 781
 782                     int nKeysCount = CastToBigNum(stacktop(-i)).getint();
 783                     if (nKeysCount < 0 || nKeysCount > 20)
 784                         return false;
 785                     nOpCount += nKeysCount;
 786                     if (nOpCount > 201)
 787                         return false;
 788                     int ikey = ++i;
 789                     i += nKeysCount;
 790                     if (stack.size() < i)
 791                         return false;
 792
 793                     int nSigsCount = CastToBigNum(stacktop(-i)).getint();
 794                     if (nSigsCount < 0 || nSigsCount > nKeysCount)
 795                         return false;
 796                     int isig = ++i;
 797                     i += nSigsCount;
 798                     if (stack.size() < i)
 799                         return false;
 800
 801                     // Subset of script starting at the most recent codeseparator
 802                     CScript scriptCode(pbegincodehash, pend);
 803
 804                     // Drop the signatures, since there's no way for a signature to sign itself
 805                     for (int k = 0; k < nSigsCount; k++)
 806                     {
 807                         valtype& vchSig = stacktop(-isig-k);
 808                         scriptCode.FindAndDelete(CScript(vchSig));
 809                     }
 810
 811                     bool fSuccess = true;
 812                     while (fSuccess && nSigsCount > 0)
 813                     {
 814                         valtype& vchSig    = stacktop(-isig);
 815                         valtype& vchPubKey = stacktop(-ikey);
 816
 817                         // Check signature
 818                         if (CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType))
 819                         {
 820                             isig++;
 821                             nSigsCount--;
 822                         }
 823                         ikey++;
 824                         nKeysCount--;
 825
 826                         // If there are more signatures left than keys left,
 827                         // then too many signatures have failed
 828                         if (nSigsCount > nKeysCount)
 829                             fSuccess = false;
 830                     }
 831
 832                     while (i-- > 0)
 833                         popstack(stack);
 834                     stack.push_back(fSuccess ? vchTrue : vchFalse);
 835
 836                     if (opcode == OP_CHECKMULTISIGVERIFY)
 837                     {
 838                         if (fSuccess)
 839                             popstack(stack);
 840                         else
 841                             return false;
 842                     }
 843                 }
 844                 break;
 845
 846                 default:
 847                     return false;
 848             }
 849
 850             // Size limits
 851             if (stack.size() + altstack.size() > 1000)
 852                 return false;
 853         }
 854     }
 855     catch (...)
 856     {
 857         return false;
 858     }
 859
 860
 861     if (!vfExec.empty())
 862         return false;
 863
 864     return true;
 865 }
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875 uint256 SignatureHash(CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType)
 876 {
 877     if (nIn >= txTo.vin.size())
 878     {
 879         printf("ERROR: SignatureHash() : nIn=%d out of range\n", nIn);
 880         return 1;
 881     }
 882     CTransaction txTmp(txTo);
 883
 884     // In case concatenating two scripts ends up with two codeseparators,
 885     // or an extra one at the end, this prevents all those possible incompatibilities.
 886     scriptCode.FindAndDelete(CScript(OP_CODESEPARATOR));
 887
 888     // Blank out other inputs' signatures
 889     for (int i = 0; i < txTmp.vin.size(); i++)
 890         txTmp.vin[i].scriptSig = CScript();
 891     txTmp.vin[nIn].scriptSig = scriptCode;
 892
 893     // Blank out some of the outputs
 894     if ((nHashType & 0x1f) == SIGHASH_NONE)
 895     {
 896         // Wildcard payee
 897         txTmp.vout.clear();
 898
 899         // Let the others update at will
 900         for (int i = 0; i < txTmp.vin.size(); i++)
 901             if (i != nIn)
 902                 txTmp.vin[i].nSequence = 0;
 903     }
 904     else if ((nHashType & 0x1f) == SIGHASH_SINGLE)
 905     {
 906         // Only lockin the txout payee at same index as txin
 907         unsigned int nOut = nIn;
 908         if (nOut >= txTmp.vout.size())
 909         {
 910             printf("ERROR: SignatureHash() : nOut=%d out of range\n", nOut);
 911             return 1;
 912         }
 913         txTmp.vout.resize(nOut+1);
 914         for (int i = 0; i < nOut; i++)
 915             txTmp.vout[i].SetNull();
 916
 917         // Let the others update at will
 918         for (int i = 0; i < txTmp.vin.size(); i++)
 919             if (i != nIn)
 920                 txTmp.vin[i].nSequence = 0;
 921     }
 922
 923     // Blank out other inputs completely, not recommended for open transactions
 924     if (nHashType & SIGHASH_ANYONECANPAY)
 925     {
 926         txTmp.vin[0] = txTmp.vin[nIn];
 927         txTmp.vin.resize(1);
 928     }
 929
 930     // Serialize and hash
 931     CDataStream ss(SER_GETHASH);
 932     ss.reserve(10000);
 933     ss << txTmp << nHashType;
 934     return Hash(ss.begin(), ss.end());
 935 }
 936
 937
 938 bool CheckSig(vector<unsigned char> vchSig, vector<unsigned char> vchPubKey, CScript scriptCode,
 939               const CTransaction& txTo, unsigned int nIn, int nHashType)
 940 {
 941     CKey key;
 942     if (!key.SetPubKey(vchPubKey))
 943         return false;
 944
 945     // Hash type is one byte tacked on to the end of the signature
 946     if (vchSig.empty())
 947         return false;
 948     if (nHashType == 0)
 949         nHashType = vchSig.back();
 950     else if (nHashType != vchSig.back())
 951         return false;
 952     vchSig.pop_back();
 953
 954     return key.Verify(SignatureHash(scriptCode, txTo, nIn, nHashType), vchSig);
 955 }
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966 bool Solver(const CScript& scriptPubKey, vector<pair<opcodetype, valtype> >& vSolutionRet)
 967 {
 968     // Templates
 969     static vector<CScript> vTemplates;
 970     if (vTemplates.empty())
 971     {
 972         // Standard tx, sender provides pubkey, receiver adds signature
 973         vTemplates.push_back(CScript() << OP_PUBKEY << OP_CHECKSIG);
 974
 975         // Bitcoin address tx, sender provides hash of pubkey, receiver provides signature and pubkey
 976         vTemplates.push_back(CScript() << OP_DUP << OP_HASH160 << OP_PUBKEYHASH << OP_EQUALVERIFY << OP_CHECKSIG);
 977     }
 978
 979     // Scan templates
 980     const CScript& script1 = scriptPubKey;
 981     BOOST_FOREACH(const CScript& script2, vTemplates)
 982     {
 983         vSolutionRet.clear();
 984         opcodetype opcode1, opcode2;
 985         vector<unsigned char> vch1, vch2;
 986
 987         // Compare
 988         CScript::const_iterator pc1 = script1.begin();
 989         CScript::const_iterator pc2 = script2.begin();
 990         loop
 991         {
 992             if (pc1 == script1.end() && pc2 == script2.end())
 993             {
 994                 // Found a match
 995                 reverse(vSolutionRet.begin(), vSolutionRet.end());
 996                 return true;
 997             }
 998             if (!script1.GetOp(pc1, opcode1, vch1))
 999                 break;
1000             if (!script2.GetOp(pc2, opcode2, vch2))
1001                 break;
1002             if (opcode2 == OP_PUBKEY)
1003             {
1004                 if (vch1.size() < 33 || vch1.size() > 120)
1005                     break;
1006                 vSolutionRet.push_back(make_pair(opcode2, vch1));
1007             }
1008             else if (opcode2 == OP_PUBKEYHASH)
1009             {
1010                 if (vch1.size() != sizeof(uint160))
1011                     break;
1012                 vSolutionRet.push_back(make_pair(opcode2, vch1));
1013             }
1014             else if (opcode1 != opcode2 || vch1 != vch2)
1015             {
1016                 break;
1017             }
1018         }
1019     }
1020
1021     vSolutionRet.clear();
1022     return false;
1023 }
1024
1025
1026 bool Solver(const CKeyStore& keystore, const CScript& scriptPubKey, uint256 hash, int nHashType, CScript& scriptSigRet)
1027 {
1028     scriptSigRet.clear();
1029
1030     vector<pair<opcodetype, valtype> > vSolution;
1031     if (!Solver(scriptPubKey, vSolution))
1032         return false;
1033
1034     // Compile solution
1035     CRITICAL_BLOCK(keystore.cs_KeyStore)
1036     {
1037         BOOST_FOREACH(PAIRTYPE(opcodetype, valtype)& item, vSolution)
1038         {
1039             if (item.first == OP_PUBKEY)
1040             {
1041                 // Sign
1042                 const valtype& vchPubKey = item.second;
1043                 CKey key;
1044                 if (!keystore.GetKey(Hash160(vchPubKey), key))
1045                     return false;
1046                 if (key.GetPubKey() != vchPubKey)
1047                     return false;
1048                 if (hash != 0)
1049                 {
1050                     vector<unsigned char> vchSig;
1051                     if (!key.Sign(hash, vchSig))
1052                         return false;
1053                     vchSig.push_back((unsigned char)nHashType);
1054                     scriptSigRet << vchSig;
1055                 }
1056             }
1057             else if (item.first == OP_PUBKEYHASH)
1058             {
1059                 // Sign and give pubkey
1060                 CKey key;
1061                 if (!keystore.GetKey(uint160(item.second), key))
1062                     return false;
1063                 if (hash != 0)
1064                 {
1065                     vector<unsigned char> vchSig;
1066                     if (!key.Sign(hash, vchSig))
1067                         return false;
1068                     vchSig.push_back((unsigned char)nHashType);
1069                     scriptSigRet << vchSig << key.GetPubKey();
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                 const valtype& vchPubKey = item.second;
1104                 vector<unsigned char> vchPubKeyFound;
1105                 if (!keystore.GetPubKey(Hash160(vchPubKey), vchPubKeyFound))
1106                     return false;
1107                 if (vchPubKeyFound != vchPubKey)
1108                     return false;
1109             }
1110             else if (item.first == OP_PUBKEYHASH)
1111             {
1112                 if (!keystore.HaveKey(uint160(item.second)))
1113                     return false;
1114             }
1115             else
1116             {
1117                 return false;
1118             }
1119         }
1120     }
1121
1122     return true;
1123 }
1124
1125 // requires either keystore==0, or a lock on keystore->cs_KeyStore
1126 bool static ExtractAddressInner(const CScript& scriptPubKey, const CKeyStore* keystore, CBitcoinAddress& addressRet)
1127 {
1128     vector<pair<opcodetype, valtype> > vSolution;
1129     if (!Solver(scriptPubKey, vSolution))
1130         return false;
1131
1132     BOOST_FOREACH(PAIRTYPE(opcodetype, valtype)& item, vSolution)
1133     {
1134         if (item.first == OP_PUBKEY)
1135             addressRet.SetPubKey(item.second);
1136         else if (item.first == OP_PUBKEYHASH)
1137             addressRet.SetHash160((uint160)item.second);
1138         if (keystore == NULL || keystore->HaveKey(addressRet))
1139             return true;
1140     }
1141     return false;
1142 }
1143
1144
1145 bool ExtractAddress(const CScript& scriptPubKey, const CKeyStore* keystore, CBitcoinAddress& addressRet)
1146 {
1147     if (keystore)
1148         CRITICAL_BLOCK(keystore->cs_KeyStore)
1149             return ExtractAddressInner(scriptPubKey, keystore, addressRet);
1150     else
1151         return ExtractAddressInner(scriptPubKey, NULL, addressRet);
1152     return false;
1153 }
1154
1155
1156 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn, int nHashType)
1157 {
1158     vector<vector<unsigned char> > stack;
1159     if (!EvalScript(stack, scriptSig, txTo, nIn, nHashType))
1160         return false;
1161     if (!EvalScript(stack, scriptPubKey, txTo, nIn, nHashType))
1162         return false;
1163     if (stack.empty())
1164         return false;
1165     return CastToBool(stack.back());
1166 }
1167
1168
1169 bool SignSignature(const CKeyStore &keystore, const CTransaction& txFrom, CTransaction& txTo, unsigned int nIn, int nHashType, CScript scriptPrereq)
1170 {
1171     assert(nIn < txTo.vin.size());
1172     CTxIn& txin = txTo.vin[nIn];
1173     assert(txin.prevout.n < txFrom.vout.size());
1174     const CTxOut& txout = txFrom.vout[txin.prevout.n];
1175
1176     // Leave out the signature from the hash, since a signature can't sign itself.
1177     // The checksig op will also drop the signatures from its hash.
1178     uint256 hash = SignatureHash(scriptPrereq + txout.scriptPubKey, txTo, nIn, nHashType);
1179
1180     if (!Solver(keystore, txout.scriptPubKey, hash, nHashType, txin.scriptSig))
1181         return false;
1182
1183     txin.scriptSig = scriptPrereq + txin.scriptSig;
1184
1185     // Test solution
1186     if (scriptPrereq.empty())
1187         if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, 0))
1188             return false;
1189
1190     return true;
1191 }
1192
1193
1194 bool VerifySignature(const CTransaction& txFrom, const CTransaction& txTo, unsigned int nIn, int nHashType)
1195 {
1196     assert(nIn < txTo.vin.size());
1197     const CTxIn& txin = txTo.vin[nIn];
1198     if (txin.prevout.n >= txFrom.vout.size())
1199         return false;
1200     const CTxOut& txout = txFrom.vout[txin.prevout.n];
1201
1202     if (txin.prevout.hash != txFrom.GetHash())
1203         return false;
1204
1205     if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, nHashType))
1206         return false;
1207
1208     return true;
1209 }