src/script.cpp

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2012 The Bitcoin developers
   3 // Distributed under the MIT/X11 software license, see the accompanying
   4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   5 #include "headers.h"
   6
   7 using namespace std;
   8 using namespace boost;
   9
  10 bool CheckSig(vector<unsigned char> vchSig, vector<unsigned char> vchPubKey, CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType);
  11
  12
  13
  14 typedef vector<unsigned char> valtype;
  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 const char* GetTxnOutputType(txnouttype t)
  74 {
  75     switch (t)
  76     {
  77     case TX_NONSTANDARD: return "nonstandard";
  78     case TX_PUBKEY: return "pubkey";
  79     case TX_PUBKEYHASH: return "pubkeyhash";
  80     case TX_SCRIPTHASH: return "scripthash";
  81     case TX_MULTISIG: return "multisig";
  82     }
  83     return NULL;
  84 }
  85
  86
  87 const char* GetOpName(opcodetype opcode)
  88 {
  89     switch (opcode)
  90     {
  91     // push value
  92     case OP_0                      : return "0";
  93     case OP_PUSHDATA1              : return "OP_PUSHDATA1";
  94     case OP_PUSHDATA2              : return "OP_PUSHDATA2";
  95     case OP_PUSHDATA4              : return "OP_PUSHDATA4";
  96     case OP_1NEGATE                : return "-1";
  97     case OP_RESERVED               : return "OP_RESERVED";
  98     case OP_1                      : return "1";
  99     case OP_2                      : return "2";
 100     case OP_3                      : return "3";
 101     case OP_4                      : return "4";
 102     case OP_5                      : return "5";
 103     case OP_6                      : return "6";
 104     case OP_7                      : return "7";
 105     case OP_8                      : return "8";
 106     case OP_9                      : return "9";
 107     case OP_10                     : return "10";
 108     case OP_11                     : return "11";
 109     case OP_12                     : return "12";
 110     case OP_13                     : return "13";
 111     case OP_14                     : return "14";
 112     case OP_15                     : return "15";
 113     case OP_16                     : return "16";
 114
 115     // control
 116     case OP_NOP                    : return "OP_NOP";
 117     case OP_VER                    : return "OP_VER";
 118     case OP_IF                     : return "OP_IF";
 119     case OP_NOTIF                  : return "OP_NOTIF";
 120     case OP_VERIF                  : return "OP_VERIF";
 121     case OP_VERNOTIF               : return "OP_VERNOTIF";
 122     case OP_ELSE                   : return "OP_ELSE";
 123     case OP_ENDIF                  : return "OP_ENDIF";
 124     case OP_VERIFY                 : return "OP_VERIFY";
 125     case OP_RETURN                 : return "OP_RETURN";
 126
 127     // stack ops
 128     case OP_TOALTSTACK             : return "OP_TOALTSTACK";
 129     case OP_FROMALTSTACK           : return "OP_FROMALTSTACK";
 130     case OP_2DROP                  : return "OP_2DROP";
 131     case OP_2DUP                   : return "OP_2DUP";
 132     case OP_3DUP                   : return "OP_3DUP";
 133     case OP_2OVER                  : return "OP_2OVER";
 134     case OP_2ROT                   : return "OP_2ROT";
 135     case OP_2SWAP                  : return "OP_2SWAP";
 136     case OP_IFDUP                  : return "OP_IFDUP";
 137     case OP_DEPTH                  : return "OP_DEPTH";
 138     case OP_DROP                   : return "OP_DROP";
 139     case OP_DUP                    : return "OP_DUP";
 140     case OP_NIP                    : return "OP_NIP";
 141     case OP_OVER                   : return "OP_OVER";
 142     case OP_PICK                   : return "OP_PICK";
 143     case OP_ROLL                   : return "OP_ROLL";
 144     case OP_ROT                    : return "OP_ROT";
 145     case OP_SWAP                   : return "OP_SWAP";
 146     case OP_TUCK                   : return "OP_TUCK";
 147
 148     // splice ops
 149     case OP_CAT                    : return "OP_CAT";
 150     case OP_SUBSTR                 : return "OP_SUBSTR";
 151     case OP_LEFT                   : return "OP_LEFT";
 152     case OP_RIGHT                  : return "OP_RIGHT";
 153     case OP_SIZE                   : return "OP_SIZE";
 154
 155     // bit logic
 156     case OP_INVERT                 : return "OP_INVERT";
 157     case OP_AND                    : return "OP_AND";
 158     case OP_OR                     : return "OP_OR";
 159     case OP_XOR                    : return "OP_XOR";
 160     case OP_EQUAL                  : return "OP_EQUAL";
 161     case OP_EQUALVERIFY            : return "OP_EQUALVERIFY";
 162     case OP_RESERVED1              : return "OP_RESERVED1";
 163     case OP_RESERVED2              : return "OP_RESERVED2";
 164
 165     // numeric
 166     case OP_1ADD                   : return "OP_1ADD";
 167     case OP_1SUB                   : return "OP_1SUB";
 168     case OP_2MUL                   : return "OP_2MUL";
 169     case OP_2DIV                   : return "OP_2DIV";
 170     case OP_NEGATE                 : return "OP_NEGATE";
 171     case OP_ABS                    : return "OP_ABS";
 172     case OP_NOT                    : return "OP_NOT";
 173     case OP_0NOTEQUAL              : return "OP_0NOTEQUAL";
 174     case OP_ADD                    : return "OP_ADD";
 175     case OP_SUB                    : return "OP_SUB";
 176     case OP_MUL                    : return "OP_MUL";
 177     case OP_DIV                    : return "OP_DIV";
 178     case OP_MOD                    : return "OP_MOD";
 179     case OP_LSHIFT                 : return "OP_LSHIFT";
 180     case OP_RSHIFT                 : return "OP_RSHIFT";
 181     case OP_BOOLAND                : return "OP_BOOLAND";
 182     case OP_BOOLOR                 : return "OP_BOOLOR";
 183     case OP_NUMEQUAL               : return "OP_NUMEQUAL";
 184     case OP_NUMEQUALVERIFY         : return "OP_NUMEQUALVERIFY";
 185     case OP_NUMNOTEQUAL            : return "OP_NUMNOTEQUAL";
 186     case OP_LESSTHAN               : return "OP_LESSTHAN";
 187     case OP_GREATERTHAN            : return "OP_GREATERTHAN";
 188     case OP_LESSTHANOREQUAL        : return "OP_LESSTHANOREQUAL";
 189     case OP_GREATERTHANOREQUAL     : return "OP_GREATERTHANOREQUAL";
 190     case OP_MIN                    : return "OP_MIN";
 191     case OP_MAX                    : return "OP_MAX";
 192     case OP_WITHIN                 : return "OP_WITHIN";
 193
 194     // crypto
 195     case OP_RIPEMD160              : return "OP_RIPEMD160";
 196     case OP_SHA1                   : return "OP_SHA1";
 197     case OP_SHA256                 : return "OP_SHA256";
 198     case OP_HASH160                : return "OP_HASH160";
 199     case OP_HASH256                : return "OP_HASH256";
 200     case OP_CODESEPARATOR          : return "OP_CODESEPARATOR";
 201     case OP_CHECKSIG               : return "OP_CHECKSIG";
 202     case OP_CHECKSIGVERIFY         : return "OP_CHECKSIGVERIFY";
 203     case OP_CHECKMULTISIG          : return "OP_CHECKMULTISIG";
 204     case OP_CHECKMULTISIGVERIFY    : return "OP_CHECKMULTISIGVERIFY";
 205
 206     // expanson
 207     case OP_NOP1                   : return "OP_NOP1";
 208     case OP_NOP2                   : return "OP_NOP2";
 209     case OP_NOP3                   : return "OP_NOP3";
 210     case OP_NOP4                   : return "OP_NOP4";
 211     case OP_NOP5                   : return "OP_NOP5";
 212     case OP_NOP6                   : return "OP_NOP6";
 213     case OP_NOP7                   : return "OP_NOP7";
 214     case OP_NOP8                   : return "OP_NOP8";
 215     case OP_NOP9                   : return "OP_NOP9";
 216     case OP_NOP10                  : return "OP_NOP10";
 217
 218
 219
 220     // template matching params
 221     case OP_PUBKEYHASH             : return "OP_PUBKEYHASH";
 222     case OP_PUBKEY                 : return "OP_PUBKEY";
 223
 224     case OP_INVALIDOPCODE          : return "OP_INVALIDOPCODE";
 225     default:
 226         return "OP_UNKNOWN";
 227     }
 228 }
 229
 230 bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, const CTransaction& txTo, unsigned int nIn, int nHashType)
 231 {
 232     CAutoBN_CTX pctx;
 233     CScript::const_iterator pc = script.begin();
 234     CScript::const_iterator pend = script.end();
 235     CScript::const_iterator pbegincodehash = script.begin();
 236     opcodetype opcode;
 237     valtype vchPushValue;
 238     vector<bool> vfExec;
 239     vector<valtype> altstack;
 240     if (script.size() > 10000)
 241         return false;
 242     int nOpCount = 0;
 243
 244
 245     try
 246     {
 247         while (pc < pend)
 248         {
 249             bool fExec = !count(vfExec.begin(), vfExec.end(), false);
 250
 251             //
 252             // Read instruction
 253             //
 254             if (!script.GetOp(pc, opcode, vchPushValue))
 255                 return false;
 256             if (vchPushValue.size() > 520)
 257                 return false;
 258             if (opcode > OP_16 && ++nOpCount > 201)
 259                 return false;
 260
 261             if (opcode == OP_CAT ||
 262                 opcode == OP_SUBSTR ||
 263                 opcode == OP_LEFT ||
 264                 opcode == OP_RIGHT ||
 265                 opcode == OP_INVERT ||
 266                 opcode == OP_AND ||
 267                 opcode == OP_OR ||
 268                 opcode == OP_XOR ||
 269                 opcode == OP_2MUL ||
 270                 opcode == OP_2DIV ||
 271                 opcode == OP_MUL ||
 272                 opcode == OP_DIV ||
 273                 opcode == OP_MOD ||
 274                 opcode == OP_LSHIFT ||
 275                 opcode == OP_RSHIFT)
 276                 return false;
 277
 278             if (fExec && 0 <= opcode && opcode <= OP_PUSHDATA4)
 279                 stack.push_back(vchPushValue);
 280             else if (fExec || (OP_IF <= opcode && opcode <= OP_ENDIF))
 281             switch (opcode)
 282             {
 283                 //
 284                 // Push value
 285                 //
 286                 case OP_1NEGATE:
 287                 case OP_1:
 288                 case OP_2:
 289                 case OP_3:
 290                 case OP_4:
 291                 case OP_5:
 292                 case OP_6:
 293                 case OP_7:
 294                 case OP_8:
 295                 case OP_9:
 296                 case OP_10:
 297                 case OP_11:
 298                 case OP_12:
 299                 case OP_13:
 300                 case OP_14:
 301                 case OP_15:
 302                 case OP_16:
 303                 {
 304                     // ( -- value)
 305                     CBigNum bn((int)opcode - (int)(OP_1 - 1));
 306                     stack.push_back(bn.getvch());
 307                 }
 308                 break;
 309
 310
 311                 //
 312                 // Control
 313                 //
 314                 case OP_NOP:
 315                 case OP_NOP1: case OP_NOP2: case OP_NOP3: case OP_NOP4: case OP_NOP5:
 316                 case OP_NOP6: case OP_NOP7: case OP_NOP8: case OP_NOP9: case OP_NOP10:
 317                 break;
 318
 319                 case OP_IF:
 320                 case OP_NOTIF:
 321                 {
 322                     // <expression> if [statements] [else [statements]] endif
 323                     bool fValue = false;
 324                     if (fExec)
 325                     {
 326                         if (stack.size() < 1)
 327                             return false;
 328                         valtype& vch = stacktop(-1);
 329                         fValue = CastToBool(vch);
 330                         if (opcode == OP_NOTIF)
 331                             fValue = !fValue;
 332                         popstack(stack);
 333                     }
 334                     vfExec.push_back(fValue);
 335                 }
 336                 break;
 337
 338                 case OP_ELSE:
 339                 {
 340                     if (vfExec.empty())
 341                         return false;
 342                     vfExec.back() = !vfExec.back();
 343                 }
 344                 break;
 345
 346                 case OP_ENDIF:
 347                 {
 348                     if (vfExec.empty())
 349                         return false;
 350                     vfExec.pop_back();
 351                 }
 352                 break;
 353
 354                 case OP_VERIFY:
 355                 {
 356                     // (true -- ) or
 357                     // (false -- false) and return
 358                     if (stack.size() < 1)
 359                         return false;
 360                     bool fValue = CastToBool(stacktop(-1));
 361                     if (fValue)
 362                         popstack(stack);
 363                     else
 364                         return false;
 365                 }
 366                 break;
 367
 368                 case OP_RETURN:
 369                 {
 370                     return false;
 371                 }
 372                 break;
 373
 374
 375                 //
 376                 // Stack ops
 377                 //
 378                 case OP_TOALTSTACK:
 379                 {
 380                     if (stack.size() < 1)
 381                         return false;
 382                     altstack.push_back(stacktop(-1));
 383                     popstack(stack);
 384                 }
 385                 break;
 386
 387                 case OP_FROMALTSTACK:
 388                 {
 389                     if (altstack.size() < 1)
 390                         return false;
 391                     stack.push_back(altstacktop(-1));
 392                     popstack(altstack);
 393                 }
 394                 break;
 395
 396                 case OP_2DROP:
 397                 {
 398                     // (x1 x2 -- )
 399                     if (stack.size() < 2)
 400                         return false;
 401                     popstack(stack);
 402                     popstack(stack);
 403                 }
 404                 break;
 405
 406                 case OP_2DUP:
 407                 {
 408                     // (x1 x2 -- x1 x2 x1 x2)
 409                     if (stack.size() < 2)
 410                         return false;
 411                     valtype vch1 = stacktop(-2);
 412                     valtype vch2 = stacktop(-1);
 413                     stack.push_back(vch1);
 414                     stack.push_back(vch2);
 415                 }
 416                 break;
 417
 418                 case OP_3DUP:
 419                 {
 420                     // (x1 x2 x3 -- x1 x2 x3 x1 x2 x3)
 421                     if (stack.size() < 3)
 422                         return false;
 423                     valtype vch1 = stacktop(-3);
 424                     valtype vch2 = stacktop(-2);
 425                     valtype vch3 = stacktop(-1);
 426                     stack.push_back(vch1);
 427                     stack.push_back(vch2);
 428                     stack.push_back(vch3);
 429                 }
 430                 break;
 431
 432                 case OP_2OVER:
 433                 {
 434                     // (x1 x2 x3 x4 -- x1 x2 x3 x4 x1 x2)
 435                     if (stack.size() < 4)
 436                         return false;
 437                     valtype vch1 = stacktop(-4);
 438                     valtype vch2 = stacktop(-3);
 439                     stack.push_back(vch1);
 440                     stack.push_back(vch2);
 441                 }
 442                 break;
 443
 444                 case OP_2ROT:
 445                 {
 446                     // (x1 x2 x3 x4 x5 x6 -- x3 x4 x5 x6 x1 x2)
 447                     if (stack.size() < 6)
 448                         return false;
 449                     valtype vch1 = stacktop(-6);
 450                     valtype vch2 = stacktop(-5);
 451                     stack.erase(stack.end()-6, stack.end()-4);
 452                     stack.push_back(vch1);
 453                     stack.push_back(vch2);
 454                 }
 455                 break;
 456
 457                 case OP_2SWAP:
 458                 {
 459                     // (x1 x2 x3 x4 -- x3 x4 x1 x2)
 460                     if (stack.size() < 4)
 461                         return false;
 462                     swap(stacktop(-4), stacktop(-2));
 463                     swap(stacktop(-3), stacktop(-1));
 464                 }
 465                 break;
 466
 467                 case OP_IFDUP:
 468                 {
 469                     // (x - 0 | x x)
 470                     if (stack.size() < 1)
 471                         return false;
 472                     valtype vch = stacktop(-1);
 473                     if (CastToBool(vch))
 474                         stack.push_back(vch);
 475                 }
 476                 break;
 477
 478                 case OP_DEPTH:
 479                 {
 480                     // -- stacksize
 481                     CBigNum bn(stack.size());
 482                     stack.push_back(bn.getvch());
 483                 }
 484                 break;
 485
 486                 case OP_DROP:
 487                 {
 488                     // (x -- )
 489                     if (stack.size() < 1)
 490                         return false;
 491                     popstack(stack);
 492                 }
 493                 break;
 494
 495                 case OP_DUP:
 496                 {
 497                     // (x -- x x)
 498                     if (stack.size() < 1)
 499                         return false;
 500                     valtype vch = stacktop(-1);
 501                     stack.push_back(vch);
 502                 }
 503                 break;
 504
 505                 case OP_NIP:
 506                 {
 507                     // (x1 x2 -- x2)
 508                     if (stack.size() < 2)
 509                         return false;
 510                     stack.erase(stack.end() - 2);
 511                 }
 512                 break;
 513
 514                 case OP_OVER:
 515                 {
 516                     // (x1 x2 -- x1 x2 x1)
 517                     if (stack.size() < 2)
 518                         return false;
 519                     valtype vch = stacktop(-2);
 520                     stack.push_back(vch);
 521                 }
 522                 break;
 523
 524                 case OP_PICK:
 525                 case OP_ROLL:
 526                 {
 527                     // (xn ... x2 x1 x0 n - xn ... x2 x1 x0 xn)
 528                     // (xn ... x2 x1 x0 n - ... x2 x1 x0 xn)
 529                     if (stack.size() < 2)
 530                         return false;
 531                     int n = CastToBigNum(stacktop(-1)).getint();
 532                     popstack(stack);
 533                     if (n < 0 || n >= stack.size())
 534                         return false;
 535                     valtype vch = stacktop(-n-1);
 536                     if (opcode == OP_ROLL)
 537                         stack.erase(stack.end()-n-1);
 538                     stack.push_back(vch);
 539                 }
 540                 break;
 541
 542                 case OP_ROT:
 543                 {
 544                     // (x1 x2 x3 -- x2 x3 x1)
 545                     //  x2 x1 x3  after first swap
 546                     //  x2 x3 x1  after second swap
 547                     if (stack.size() < 3)
 548                         return false;
 549                     swap(stacktop(-3), stacktop(-2));
 550                     swap(stacktop(-2), stacktop(-1));
 551                 }
 552                 break;
 553
 554                 case OP_SWAP:
 555                 {
 556                     // (x1 x2 -- x2 x1)
 557                     if (stack.size() < 2)
 558                         return false;
 559                     swap(stacktop(-2), stacktop(-1));
 560                 }
 561                 break;
 562
 563                 case OP_TUCK:
 564                 {
 565                     // (x1 x2 -- x2 x1 x2)
 566                     if (stack.size() < 2)
 567                         return false;
 568                     valtype vch = stacktop(-1);
 569                     stack.insert(stack.end()-2, vch);
 570                 }
 571                 break;
 572
 573
 574                 //
 575                 // Splice ops
 576                 //
 577                 case OP_CAT:
 578                 {
 579                     // (x1 x2 -- out)
 580                     if (stack.size() < 2)
 581                         return false;
 582                     valtype& vch1 = stacktop(-2);
 583                     valtype& vch2 = stacktop(-1);
 584                     vch1.insert(vch1.end(), vch2.begin(), vch2.end());
 585                     popstack(stack);
 586                     if (stacktop(-1).size() > 520)
 587                         return false;
 588                 }
 589                 break;
 590
 591                 case OP_SUBSTR:
 592                 {
 593                     // (in begin size -- out)
 594                     if (stack.size() < 3)
 595                         return false;
 596                     valtype& vch = stacktop(-3);
 597                     int nBegin = CastToBigNum(stacktop(-2)).getint();
 598                     int nEnd = nBegin + CastToBigNum(stacktop(-1)).getint();
 599                     if (nBegin < 0 || nEnd < nBegin)
 600                         return false;
 601                     if (nBegin > vch.size())
 602                         nBegin = vch.size();
 603                     if (nEnd > vch.size())
 604                         nEnd = vch.size();
 605                     vch.erase(vch.begin() + nEnd, vch.end());
 606                     vch.erase(vch.begin(), vch.begin() + nBegin);
 607                     popstack(stack);
 608                     popstack(stack);
 609                 }
 610                 break;
 611
 612                 case OP_LEFT:
 613                 case OP_RIGHT:
 614                 {
 615                     // (in size -- out)
 616                     if (stack.size() < 2)
 617                         return false;
 618                     valtype& vch = stacktop(-2);
 619                     int nSize = CastToBigNum(stacktop(-1)).getint();
 620                     if (nSize < 0)
 621                         return false;
 622                     if (nSize > vch.size())
 623                         nSize = vch.size();
 624                     if (opcode == OP_LEFT)
 625                         vch.erase(vch.begin() + nSize, vch.end());
 626                     else
 627                         vch.erase(vch.begin(), vch.end() - nSize);
 628                     popstack(stack);
 629                 }
 630                 break;
 631
 632                 case OP_SIZE:
 633                 {
 634                     // (in -- in size)
 635                     if (stack.size() < 1)
 636                         return false;
 637                     CBigNum bn(stacktop(-1).size());
 638                     stack.push_back(bn.getvch());
 639                 }
 640                 break;
 641
 642
 643                 //
 644                 // Bitwise logic
 645                 //
 646                 case OP_INVERT:
 647                 {
 648                     // (in - out)
 649                     if (stack.size() < 1)
 650                         return false;
 651                     valtype& vch = stacktop(-1);
 652                     for (int i = 0; i < vch.size(); i++)
 653                         vch[i] = ~vch[i];
 654                 }
 655                 break;
 656
 657                 case OP_AND:
 658                 case OP_OR:
 659                 case OP_XOR:
 660                 {
 661                     // (x1 x2 - out)
 662                     if (stack.size() < 2)
 663                         return false;
 664                     valtype& vch1 = stacktop(-2);
 665                     valtype& vch2 = stacktop(-1);
 666                     MakeSameSize(vch1, vch2);
 667                     if (opcode == OP_AND)
 668                     {
 669                         for (int i = 0; i < vch1.size(); i++)
 670                             vch1[i] &= vch2[i];
 671                     }
 672                     else if (opcode == OP_OR)
 673                     {
 674                         for (int i = 0; i < vch1.size(); i++)
 675                             vch1[i] |= vch2[i];
 676                     }
 677                     else if (opcode == OP_XOR)
 678                     {
 679                         for (int i = 0; i < vch1.size(); i++)
 680                             vch1[i] ^= vch2[i];
 681                     }
 682                     popstack(stack);
 683                 }
 684                 break;
 685
 686                 case OP_EQUAL:
 687                 case OP_EQUALVERIFY:
 688                 //case OP_NOTEQUAL: // use OP_NUMNOTEQUAL
 689                 {
 690                     // (x1 x2 - bool)
 691                     if (stack.size() < 2)
 692                         return false;
 693                     valtype& vch1 = stacktop(-2);
 694                     valtype& vch2 = stacktop(-1);
 695                     bool fEqual = (vch1 == vch2);
 696                     // OP_NOTEQUAL is disabled because it would be too easy to say
 697                     // something like n != 1 and have some wiseguy pass in 1 with extra
 698                     // zero bytes after it (numerically, 0x01 == 0x0001 == 0x000001)
 699                     //if (opcode == OP_NOTEQUAL)
 700                     //    fEqual = !fEqual;
 701                     popstack(stack);
 702                     popstack(stack);
 703                     stack.push_back(fEqual ? vchTrue : vchFalse);
 704                     if (opcode == OP_EQUALVERIFY)
 705                     {
 706                         if (fEqual)
 707                             popstack(stack);
 708                         else
 709                             return false;
 710                     }
 711                 }
 712                 break;
 713
 714
 715                 //
 716                 // Numeric
 717                 //
 718                 case OP_1ADD:
 719                 case OP_1SUB:
 720                 case OP_2MUL:
 721                 case OP_2DIV:
 722                 case OP_NEGATE:
 723                 case OP_ABS:
 724                 case OP_NOT:
 725                 case OP_0NOTEQUAL:
 726                 {
 727                     // (in -- out)
 728                     if (stack.size() < 1)
 729                         return false;
 730                     CBigNum bn = CastToBigNum(stacktop(-1));
 731                     switch (opcode)
 732                     {
 733                     case OP_1ADD:       bn += bnOne; break;
 734                     case OP_1SUB:       bn -= bnOne; break;
 735                     case OP_2MUL:       bn <<= 1; break;
 736                     case OP_2DIV:       bn >>= 1; break;
 737                     case OP_NEGATE:     bn = -bn; break;
 738                     case OP_ABS:        if (bn < bnZero) bn = -bn; break;
 739                     case OP_NOT:        bn = (bn == bnZero); break;
 740                     case OP_0NOTEQUAL:  bn = (bn != bnZero); break;
 741                     default:            assert(!"invalid opcode"); break;
 742                     }
 743                     popstack(stack);
 744                     stack.push_back(bn.getvch());
 745                 }
 746                 break;
 747
 748                 case OP_ADD:
 749                 case OP_SUB:
 750                 case OP_MUL:
 751                 case OP_DIV:
 752                 case OP_MOD:
 753                 case OP_LSHIFT:
 754                 case OP_RSHIFT:
 755                 case OP_BOOLAND:
 756                 case OP_BOOLOR:
 757                 case OP_NUMEQUAL:
 758                 case OP_NUMEQUALVERIFY:
 759                 case OP_NUMNOTEQUAL:
 760                 case OP_LESSTHAN:
 761                 case OP_GREATERTHAN:
 762                 case OP_LESSTHANOREQUAL:
 763                 case OP_GREATERTHANOREQUAL:
 764                 case OP_MIN:
 765                 case OP_MAX:
 766                 {
 767                     // (x1 x2 -- out)
 768                     if (stack.size() < 2)
 769                         return false;
 770                     CBigNum bn1 = CastToBigNum(stacktop(-2));
 771                     CBigNum bn2 = CastToBigNum(stacktop(-1));
 772                     CBigNum bn;
 773                     switch (opcode)
 774                     {
 775                     case OP_ADD:
 776                         bn = bn1 + bn2;
 777                         break;
 778
 779                     case OP_SUB:
 780                         bn = bn1 - bn2;
 781                         break;
 782
 783                     case OP_MUL:
 784                         if (!BN_mul(&bn, &bn1, &bn2, pctx))
 785                             return false;
 786                         break;
 787
 788                     case OP_DIV:
 789                         if (!BN_div(&bn, NULL, &bn1, &bn2, pctx))
 790                             return false;
 791                         break;
 792
 793                     case OP_MOD:
 794                         if (!BN_mod(&bn, &bn1, &bn2, pctx))
 795                             return false;
 796                         break;
 797
 798                     case OP_LSHIFT:
 799                         if (bn2 < bnZero || bn2 > CBigNum(2048))
 800                             return false;
 801                         bn = bn1 << bn2.getulong();
 802                         break;
 803
 804                     case OP_RSHIFT:
 805                         if (bn2 < bnZero || bn2 > CBigNum(2048))
 806                             return false;
 807                         bn = bn1 >> bn2.getulong();
 808                         break;
 809
 810                     case OP_BOOLAND:             bn = (bn1 != bnZero && bn2 != bnZero); break;
 811                     case OP_BOOLOR:              bn = (bn1 != bnZero || bn2 != bnZero); break;
 812                     case OP_NUMEQUAL:            bn = (bn1 == bn2); break;
 813                     case OP_NUMEQUALVERIFY:      bn = (bn1 == bn2); break;
 814                     case OP_NUMNOTEQUAL:         bn = (bn1 != bn2); break;
 815                     case OP_LESSTHAN:            bn = (bn1 < bn2); break;
 816                     case OP_GREATERTHAN:         bn = (bn1 > bn2); break;
 817                     case OP_LESSTHANOREQUAL:     bn = (bn1 <= bn2); break;
 818                     case OP_GREATERTHANOREQUAL:  bn = (bn1 >= bn2); break;
 819                     case OP_MIN:                 bn = (bn1 < bn2 ? bn1 : bn2); break;
 820                     case OP_MAX:                 bn = (bn1 > bn2 ? bn1 : bn2); break;
 821                     default:                     assert(!"invalid opcode"); break;
 822                     }
 823                     popstack(stack);
 824                     popstack(stack);
 825                     stack.push_back(bn.getvch());
 826
 827                     if (opcode == OP_NUMEQUALVERIFY)
 828                     {
 829                         if (CastToBool(stacktop(-1)))
 830                             popstack(stack);
 831                         else
 832                             return false;
 833                     }
 834                 }
 835                 break;
 836
 837                 case OP_WITHIN:
 838                 {
 839                     // (x min max -- out)
 840                     if (stack.size() < 3)
 841                         return false;
 842                     CBigNum bn1 = CastToBigNum(stacktop(-3));
 843                     CBigNum bn2 = CastToBigNum(stacktop(-2));
 844                     CBigNum bn3 = CastToBigNum(stacktop(-1));
 845                     bool fValue = (bn2 <= bn1 && bn1 < bn3);
 846                     popstack(stack);
 847                     popstack(stack);
 848                     popstack(stack);
 849                     stack.push_back(fValue ? vchTrue : vchFalse);
 850                 }
 851                 break;
 852
 853
 854                 //
 855                 // Crypto
 856                 //
 857                 case OP_RIPEMD160:
 858                 case OP_SHA1:
 859                 case OP_SHA256:
 860                 case OP_HASH160:
 861                 case OP_HASH256:
 862                 {
 863                     // (in -- hash)
 864                     if (stack.size() < 1)
 865                         return false;
 866                     valtype& vch = stacktop(-1);
 867                     valtype vchHash((opcode == OP_RIPEMD160 || opcode == OP_SHA1 || opcode == OP_HASH160) ? 20 : 32);
 868                     if (opcode == OP_RIPEMD160)
 869                         RIPEMD160(&vch[0], vch.size(), &vchHash[0]);
 870                     else if (opcode == OP_SHA1)
 871                         SHA1(&vch[0], vch.size(), &vchHash[0]);
 872                     else if (opcode == OP_SHA256)
 873                         SHA256(&vch[0], vch.size(), &vchHash[0]);
 874                     else if (opcode == OP_HASH160)
 875                     {
 876                         uint160 hash160 = Hash160(vch);
 877                         memcpy(&vchHash[0], &hash160, sizeof(hash160));
 878                     }
 879                     else if (opcode == OP_HASH256)
 880                     {
 881                         uint256 hash = Hash(vch.begin(), vch.end());
 882                         memcpy(&vchHash[0], &hash, sizeof(hash));
 883                     }
 884                     popstack(stack);
 885                     stack.push_back(vchHash);
 886                 }
 887                 break;
 888
 889                 case OP_CODESEPARATOR:
 890                 {
 891                     // Hash starts after the code separator
 892                     pbegincodehash = pc;
 893                 }
 894                 break;
 895
 896                 case OP_CHECKSIG:
 897                 case OP_CHECKSIGVERIFY:
 898                 {
 899                     // (sig pubkey -- bool)
 900                     if (stack.size() < 2)
 901                         return false;
 902
 903                     valtype& vchSig    = stacktop(-2);
 904                     valtype& vchPubKey = stacktop(-1);
 905
 906                     ////// debug print
 907                     //PrintHex(vchSig.begin(), vchSig.end(), "sig: %s\n");
 908                     //PrintHex(vchPubKey.begin(), vchPubKey.end(), "pubkey: %s\n");
 909
 910                     // Subset of script starting at the most recent codeseparator
 911                     CScript scriptCode(pbegincodehash, pend);
 912
 913                     // Drop the signature, since there's no way for a signature to sign itself
 914                     scriptCode.FindAndDelete(CScript(vchSig));
 915
 916                     bool fSuccess = CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType);
 917
 918                     popstack(stack);
 919                     popstack(stack);
 920                     stack.push_back(fSuccess ? vchTrue : vchFalse);
 921                     if (opcode == OP_CHECKSIGVERIFY)
 922                     {
 923                         if (fSuccess)
 924                             popstack(stack);
 925                         else
 926                             return false;
 927                     }
 928                 }
 929                 break;
 930
 931                 case OP_CHECKMULTISIG:
 932                 case OP_CHECKMULTISIGVERIFY:
 933                 {
 934                     // ([sig ...] num_of_signatures [pubkey ...] num_of_pubkeys -- bool)
 935
 936                     int i = 1;
 937                     if (stack.size() < i)
 938                         return false;
 939
 940                     int nKeysCount = CastToBigNum(stacktop(-i)).getint();
 941                     if (nKeysCount < 0 || nKeysCount > 20)
 942                         return false;
 943                     nOpCount += nKeysCount;
 944                     if (nOpCount > 201)
 945                         return false;
 946                     int ikey = ++i;
 947                     i += nKeysCount;
 948                     if (stack.size() < i)
 949                         return false;
 950
 951                     int nSigsCount = CastToBigNum(stacktop(-i)).getint();
 952                     if (nSigsCount < 0 || nSigsCount > nKeysCount)
 953                         return false;
 954                     int isig = ++i;
 955                     i += nSigsCount;
 956                     if (stack.size() < i)
 957                         return false;
 958
 959                     // Subset of script starting at the most recent codeseparator
 960                     CScript scriptCode(pbegincodehash, pend);
 961
 962                     // Drop the signatures, since there's no way for a signature to sign itself
 963                     for (int k = 0; k < nSigsCount; k++)
 964                     {
 965                         valtype& vchSig = stacktop(-isig-k);
 966                         scriptCode.FindAndDelete(CScript(vchSig));
 967                     }
 968
 969                     bool fSuccess = true;
 970                     while (fSuccess && nSigsCount > 0)
 971                     {
 972                         valtype& vchSig    = stacktop(-isig);
 973                         valtype& vchPubKey = stacktop(-ikey);
 974
 975                         // Check signature
 976                         if (CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType))
 977                         {
 978                             isig++;
 979                             nSigsCount--;
 980                         }
 981                         ikey++;
 982                         nKeysCount--;
 983
 984                         // If there are more signatures left than keys left,
 985                         // then too many signatures have failed
 986                         if (nSigsCount > nKeysCount)
 987                             fSuccess = false;
 988                     }
 989
 990                     while (i-- > 0)
 991                         popstack(stack);
 992                     stack.push_back(fSuccess ? vchTrue : vchFalse);
 993
 994                     if (opcode == OP_CHECKMULTISIGVERIFY)
 995                     {
 996                         if (fSuccess)
 997                             popstack(stack);
 998                         else
 999                             return false;
1000                     }
1001                 }
1002                 break;
1003
1004                 default:
1005                     return false;
1006             }
1007
1008             // Size limits
1009             if (stack.size() + altstack.size() > 1000)
1010                 return false;
1011         }
1012     }
1013     catch (...)
1014     {
1015         return false;
1016     }
1017
1018
1019     if (!vfExec.empty())
1020         return false;
1021
1022     return true;
1023 }
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033 uint256 SignatureHash(CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType)
1034 {
1035     if (nIn >= txTo.vin.size())
1036     {
1037         printf("ERROR: SignatureHash() : nIn=%d out of range\n", nIn);
1038         return 1;
1039     }
1040     CTransaction txTmp(txTo);
1041
1042     // In case concatenating two scripts ends up with two codeseparators,
1043     // or an extra one at the end, this prevents all those possible incompatibilities.
1044     scriptCode.FindAndDelete(CScript(OP_CODESEPARATOR));
1045
1046     // Blank out other inputs' signatures
1047     for (int i = 0; i < txTmp.vin.size(); i++)
1048         txTmp.vin[i].scriptSig = CScript();
1049     txTmp.vin[nIn].scriptSig = scriptCode;
1050
1051     // Blank out some of the outputs
1052     if ((nHashType & 0x1f) == SIGHASH_NONE)
1053     {
1054         // Wildcard payee
1055         txTmp.vout.clear();
1056
1057         // Let the others update at will
1058         for (int i = 0; i < txTmp.vin.size(); i++)
1059             if (i != nIn)
1060                 txTmp.vin[i].nSequence = 0;
1061     }
1062     else if ((nHashType & 0x1f) == SIGHASH_SINGLE)
1063     {
1064         // Only lockin the txout payee at same index as txin
1065         unsigned int nOut = nIn;
1066         if (nOut >= txTmp.vout.size())
1067         {
1068             printf("ERROR: SignatureHash() : nOut=%d out of range\n", nOut);
1069             return 1;
1070         }
1071         txTmp.vout.resize(nOut+1);
1072         for (int i = 0; i < nOut; i++)
1073             txTmp.vout[i].SetNull();
1074
1075         // Let the others update at will
1076         for (int i = 0; i < txTmp.vin.size(); i++)
1077             if (i != nIn)
1078                 txTmp.vin[i].nSequence = 0;
1079     }
1080
1081     // Blank out other inputs completely, not recommended for open transactions
1082     if (nHashType & SIGHASH_ANYONECANPAY)
1083     {
1084         txTmp.vin[0] = txTmp.vin[nIn];
1085         txTmp.vin.resize(1);
1086     }
1087
1088     // Serialize and hash
1089     CDataStream ss(SER_GETHASH);
1090     ss.reserve(10000);
1091     ss << txTmp << nHashType;
1092     return Hash(ss.begin(), ss.end());
1093 }
1094
1095
1096 bool CheckSig(vector<unsigned char> vchSig, vector<unsigned char> vchPubKey, CScript scriptCode,
1097               const CTransaction& txTo, unsigned int nIn, int nHashType)
1098 {
1099     CKey key;
1100     if (!key.SetPubKey(vchPubKey))
1101         return false;
1102
1103     // Hash type is one byte tacked on to the end of the signature
1104     if (vchSig.empty())
1105         return false;
1106     if (nHashType == 0)
1107         nHashType = vchSig.back();
1108     else if (nHashType != vchSig.back())
1109         return false;
1110     vchSig.pop_back();
1111
1112     return key.Verify(SignatureHash(scriptCode, txTo, nIn, nHashType), vchSig);
1113 }
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123 //
1124 // Return public keys or hashes from scriptPubKey, for 'standard' transaction types.
1125 //
1126 bool Solver(const CScript& scriptPubKey, txnouttype& typeRet, vector<vector<unsigned char> >& vSolutionsRet)
1127 {
1128     // Templates
1129     static map<txnouttype, CScript> mTemplates;
1130     if (mTemplates.empty())
1131     {
1132         // Standard tx, sender provides pubkey, receiver adds signature
1133         mTemplates.insert(make_pair(TX_PUBKEY, CScript() << OP_PUBKEY << OP_CHECKSIG));
1134
1135         // Bitcoin address tx, sender provides hash of pubkey, receiver provides signature and pubkey
1136         mTemplates.insert(make_pair(TX_PUBKEYHASH, CScript() << OP_DUP << OP_HASH160 << OP_PUBKEYHASH << OP_EQUALVERIFY << OP_CHECKSIG));
1137
1138         // Sender provides N pubkeys, receivers provides M signatures
1139         mTemplates.insert(make_pair(TX_MULTISIG, CScript() << OP_SMALLINTEGER << OP_PUBKEYS << OP_SMALLINTEGER << OP_CHECKMULTISIG));
1140     }
1141
1142     // Shortcut for pay-to-script-hash, which are more constrained than the other types:
1143     // it is always OP_HASH160 20 [20 byte hash] OP_EQUAL
1144     if (scriptPubKey.IsPayToScriptHash())
1145     {
1146         typeRet = TX_SCRIPTHASH;
1147         vector<unsigned char> hashBytes(scriptPubKey.begin()+2, scriptPubKey.begin()+22);
1148         vSolutionsRet.push_back(hashBytes);
1149         return true;
1150     }
1151
1152     // Scan templates
1153     const CScript& script1 = scriptPubKey;
1154     BOOST_FOREACH(const PAIRTYPE(txnouttype, CScript)& tplate, mTemplates)
1155     {
1156         const CScript& script2 = tplate.second;
1157         vSolutionsRet.clear();
1158
1159         opcodetype opcode1, opcode2;
1160         vector<unsigned char> vch1, vch2;
1161
1162         // Compare
1163         CScript::const_iterator pc1 = script1.begin();
1164         CScript::const_iterator pc2 = script2.begin();
1165         loop
1166         {
1167             if (pc1 == script1.end() && pc2 == script2.end())
1168             {
1169                 // Found a match
1170                 typeRet = tplate.first;
1171                 if (typeRet == TX_MULTISIG)
1172                 {
1173                     // Additional checks for TX_MULTISIG:
1174                     unsigned char m = vSolutionsRet.front()[0];
1175                     unsigned char n = vSolutionsRet.back()[0];
1176                     if (m < 1 || n < 1 || m > n || vSolutionsRet.size()-2 != n)
1177                         return false;
1178                 }
1179                 return true;
1180             }
1181             if (!script1.GetOp(pc1, opcode1, vch1))
1182                 break;
1183             if (!script2.GetOp(pc2, opcode2, vch2))
1184                 break;
1185
1186             // Template matching opcodes:
1187             if (opcode2 == OP_PUBKEYS)
1188             {
1189                 while (vch1.size() >= 33 && vch1.size() <= 120)
1190                 {
1191                     vSolutionsRet.push_back(vch1);
1192                     if (!script1.GetOp(pc1, opcode1, vch1))
1193                         break;
1194                 }
1195                 if (!script2.GetOp(pc2, opcode2, vch2))
1196                     break;
1197                 // Normal situation is to fall through
1198                 // to other if/else statments
1199             }
1200
1201             if (opcode2 == OP_PUBKEY)
1202             {
1203                 if (vch1.size() < 33 || vch1.size() > 120)
1204                     break;
1205                 vSolutionsRet.push_back(vch1);
1206             }
1207             else if (opcode2 == OP_PUBKEYHASH)
1208             {
1209                 if (vch1.size() != sizeof(uint160))
1210                     break;
1211                 vSolutionsRet.push_back(vch1);
1212             }
1213             else if (opcode2 == OP_SMALLINTEGER)
1214             {   // Single-byte small integer pushed onto vSolutions
1215                 if (opcode1 == OP_0 ||
1216                     (opcode1 >= OP_1 && opcode1 <= OP_16))
1217                 {
1218                     char n = (char)CScript::DecodeOP_N(opcode1);
1219                     vSolutionsRet.push_back(valtype(1, n));
1220                 }
1221                 else
1222                     break;
1223             }
1224             else if (opcode1 != opcode2 || vch1 != vch2)
1225             {
1226                 // Others must match exactly
1227                 break;
1228             }
1229         }
1230     }
1231
1232     vSolutionsRet.clear();
1233     typeRet = TX_NONSTANDARD;
1234     return false;
1235 }
1236
1237
1238 bool Sign1(const CBitcoinAddress& address, const CKeyStore& keystore, uint256 hash, int nHashType, CScript& scriptSigRet)
1239 {
1240     CKey key;
1241     if (!keystore.GetKey(address, key))
1242         return false;
1243
1244     vector<unsigned char> vchSig;
1245     if (!key.Sign(hash, vchSig))
1246         return false;
1247     vchSig.push_back((unsigned char)nHashType);
1248     scriptSigRet << vchSig;
1249
1250     return true;
1251 }
1252
1253 bool SignN(const vector<valtype>& multisigdata, const CKeyStore& keystore, uint256 hash, int nHashType, CScript& scriptSigRet)
1254 {
1255     int nSigned = 0;
1256     int nRequired = multisigdata.front()[0];
1257     for (vector<valtype>::const_iterator it = multisigdata.begin()+1; it != multisigdata.begin()+multisigdata.size()-1; it++)
1258     {
1259         const valtype& pubkey = *it;
1260         CBitcoinAddress address;
1261         address.SetPubKey(pubkey);
1262         if (Sign1(address, keystore, hash, nHashType, scriptSigRet))
1263         {
1264             ++nSigned;
1265             if (nSigned == nRequired) break;
1266         }
1267     }
1268     return nSigned==nRequired;
1269 }
1270
1271 //
1272 // Sign scriptPubKey with private keys stored in keystore, given transaction hash and hash type.
1273 // Signatures are returned in scriptSigRet (or returns false if scriptPubKey can't be signed),
1274 // unless whichTypeRet is TX_SCRIPTHASH, in which case scriptSigRet is the redemption script.
1275 // Returns false if scriptPubKey could not be completely satisified.
1276 //
1277 bool Solver(const CKeyStore& keystore, const CScript& scriptPubKey, uint256 hash, int nHashType,
1278                   CScript& scriptSigRet, txnouttype& whichTypeRet)
1279 {
1280     scriptSigRet.clear();
1281
1282     vector<valtype> vSolutions;
1283     if (!Solver(scriptPubKey, whichTypeRet, vSolutions))
1284         return false;
1285
1286     CBitcoinAddress address;
1287     switch (whichTypeRet)
1288     {
1289     case TX_NONSTANDARD:
1290         return false;
1291     case TX_PUBKEY:
1292         address.SetPubKey(vSolutions[0]);
1293         return Sign1(address, keystore, hash, nHashType, scriptSigRet);
1294     case TX_PUBKEYHASH:
1295         address.SetHash160(uint160(vSolutions[0]));
1296         if (!Sign1(address, keystore, hash, nHashType, scriptSigRet))
1297             return false;
1298         else
1299         {
1300             valtype vch;
1301             keystore.GetPubKey(address, vch);
1302             scriptSigRet << vch;
1303         }
1304         return true;
1305     case TX_SCRIPTHASH:
1306         return keystore.GetCScript(uint160(vSolutions[0]), scriptSigRet);
1307
1308     case TX_MULTISIG:
1309         scriptSigRet << OP_0; // workaround CHECKMULTISIG bug
1310         return (SignN(vSolutions, keystore, hash, nHashType, scriptSigRet));
1311     }
1312     return false;
1313 }
1314
1315 int ScriptSigArgsExpected(txnouttype t, const std::vector<std::vector<unsigned char> >& vSolutions)
1316 {
1317     switch (t)
1318     {
1319     case TX_NONSTANDARD:
1320         return -1;
1321     case TX_PUBKEY:
1322         return 1;
1323     case TX_PUBKEYHASH:
1324         return 2;
1325     case TX_MULTISIG:
1326         if (vSolutions.size() < 1 || vSolutions[0].size() < 1)
1327             return -1;
1328         return vSolutions[0][0] + 1;
1329     case TX_SCRIPTHASH:
1330         return 1; // doesn't include args needed by the script
1331     }
1332     return -1;
1333 }
1334
1335 bool IsStandard(const CScript& scriptPubKey)
1336 {
1337     vector<valtype> vSolutions;
1338     txnouttype whichType;
1339     if (!Solver(scriptPubKey, whichType, vSolutions))
1340         return false;
1341
1342     if (whichType == TX_MULTISIG)
1343     {
1344         unsigned char m = vSolutions.front()[0];
1345         unsigned char n = vSolutions.back()[0];
1346         // Support up to x-of-3 multisig txns as standard
1347         if (n < 1 || n > 3)
1348             return false;
1349         if (m < 1 || m > n)
1350             return false;
1351     }
1352
1353     return whichType != TX_NONSTANDARD;
1354 }
1355
1356
1357 int HaveKeys(const vector<valtype>& pubkeys, const CKeyStore& keystore)
1358 {
1359     int nResult = 0;
1360     BOOST_FOREACH(const valtype& pubkey, pubkeys)
1361     {
1362         CBitcoinAddress address;
1363         address.SetPubKey(pubkey);
1364         if (keystore.HaveKey(address))
1365             ++nResult;
1366     }
1367     return nResult;
1368 }
1369
1370 bool IsMine(const CKeyStore &keystore, const CScript& scriptPubKey)
1371 {
1372     vector<valtype> vSolutions;
1373     txnouttype whichType;
1374     if (!Solver(scriptPubKey, whichType, vSolutions))
1375         return false;
1376
1377     CBitcoinAddress address;
1378     switch (whichType)
1379     {
1380     case TX_NONSTANDARD:
1381         return false;
1382     case TX_PUBKEY:
1383         address.SetPubKey(vSolutions[0]);
1384         return keystore.HaveKey(address);
1385     case TX_PUBKEYHASH:
1386         address.SetHash160(uint160(vSolutions[0]));
1387         return keystore.HaveKey(address);
1388     case TX_SCRIPTHASH:
1389     {
1390         CScript subscript;
1391         if (!keystore.GetCScript(uint160(vSolutions[0]), subscript))
1392             return false;
1393         return IsMine(keystore, subscript);
1394     }
1395     case TX_MULTISIG:
1396     {
1397         // Only consider transactions "mine" if we own ALL the
1398         // keys involved. multi-signature transactions that are
1399         // partially owned (somebody else has a key that can spend
1400         // them) enable spend-out-from-under-you attacks, especially
1401         // in shared-wallet situations.
1402         vector<valtype> keys(vSolutions.begin()+1, vSolutions.begin()+vSolutions.size()-1);
1403         return HaveKeys(keys, keystore) == keys.size();
1404     }
1405     }
1406     return false;
1407 }
1408
1409 bool ExtractAddress(const CScript& scriptPubKey, CBitcoinAddress& addressRet)
1410 {
1411     vector<valtype> vSolutions;
1412     txnouttype whichType;
1413     if (!Solver(scriptPubKey, whichType, vSolutions))
1414         return false;
1415
1416     if (whichType == TX_PUBKEY)
1417     {
1418         addressRet.SetPubKey(vSolutions[0]);
1419         return true;
1420     }
1421     else if (whichType == TX_PUBKEYHASH)
1422     {
1423         addressRet.SetHash160(uint160(vSolutions[0]));
1424         return true;
1425     }
1426     else if (whichType == TX_SCRIPTHASH)
1427     {
1428         addressRet.SetScriptHash160(uint160(vSolutions[0]));
1429         return true;
1430     }
1431     // Multisig txns have more than one address...
1432     return false;
1433 }
1434
1435 bool ExtractAddresses(const CScript& scriptPubKey, txnouttype& typeRet, vector<CBitcoinAddress>& addressRet, int& nRequiredRet)
1436 {
1437     addressRet.clear();
1438     typeRet = TX_NONSTANDARD;
1439     vector<valtype> vSolutions;
1440     if (!Solver(scriptPubKey, typeRet, vSolutions))
1441         return false;
1442
1443     if (typeRet == TX_MULTISIG)
1444     {
1445         nRequiredRet = vSolutions.front()[0];
1446         for (int i = 1; i < vSolutions.size()-1; i++)
1447         {
1448             CBitcoinAddress address;
1449             address.SetPubKey(vSolutions[i]);
1450             addressRet.push_back(address);
1451         }
1452     }
1453     else
1454     {
1455         nRequiredRet = 1;
1456         CBitcoinAddress address;
1457         if (typeRet == TX_PUBKEYHASH)
1458             address.SetHash160(uint160(vSolutions.front()));
1459         else if (typeRet == TX_SCRIPTHASH)
1460             address.SetScriptHash160(uint160(vSolutions.front()));
1461         else if (typeRet == TX_PUBKEY)
1462             address.SetPubKey(vSolutions.front());
1463         addressRet.push_back(address);
1464     }
1465
1466     return true;
1467 }
1468
1469 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn,
1470                   bool fValidatePayToScriptHash, int nHashType)
1471 {
1472     vector<vector<unsigned char> > stack, stackCopy;
1473     if (!EvalScript(stack, scriptSig, txTo, nIn, nHashType))
1474         return false;
1475     if (fValidatePayToScriptHash)
1476         stackCopy = stack;
1477     if (!EvalScript(stack, scriptPubKey, txTo, nIn, nHashType))
1478         return false;
1479     if (stack.empty())
1480         return false;
1481
1482     if (CastToBool(stack.back()) == false)
1483         return false;
1484
1485     // Additional validation for spend-to-script-hash transactions:
1486     if (fValidatePayToScriptHash && scriptPubKey.IsPayToScriptHash())
1487     {
1488         if (!scriptSig.IsPushOnly()) // scriptSig must be literals-only
1489             return false;            // or validation fails
1490
1491         const valtype& pubKeySerialized = stackCopy.back();
1492         CScript pubKey2(pubKeySerialized.begin(), pubKeySerialized.end());
1493         popstack(stackCopy);
1494
1495         if (!EvalScript(stackCopy, pubKey2, txTo, nIn, nHashType))
1496             return false;
1497         if (stackCopy.empty())
1498             return false;
1499         return CastToBool(stackCopy.back());
1500     }
1501
1502     return true;
1503 }
1504
1505
1506 bool SignSignature(const CKeyStore &keystore, const CTransaction& txFrom, CTransaction& txTo, unsigned int nIn, int nHashType)
1507 {
1508     assert(nIn < txTo.vin.size());
1509     CTxIn& txin = txTo.vin[nIn];
1510     assert(txin.prevout.n < txFrom.vout.size());
1511     const CTxOut& txout = txFrom.vout[txin.prevout.n];
1512
1513     // Leave out the signature from the hash, since a signature can't sign itself.
1514     // The checksig op will also drop the signatures from its hash.
1515     uint256 hash = SignatureHash(txout.scriptPubKey, txTo, nIn, nHashType);
1516
1517     txnouttype whichType;
1518     if (!Solver(keystore, txout.scriptPubKey, hash, nHashType, txin.scriptSig, whichType))
1519         return false;
1520
1521     if (whichType == TX_SCRIPTHASH)
1522     {
1523         // Solver returns the subscript that need to be evaluated;
1524         // the final scriptSig is the signatures from that
1525         // and then the serialized subscript:
1526         CScript subscript = txin.scriptSig;
1527
1528         // Recompute txn hash using subscript in place of scriptPubKey:
1529         uint256 hash2 = SignatureHash(subscript, txTo, nIn, nHashType);
1530         txnouttype subType;
1531         if (!Solver(keystore, subscript, hash2, nHashType, txin.scriptSig, subType))
1532             return false;
1533         if (subType == TX_SCRIPTHASH)
1534             return false;
1535         txin.scriptSig << static_cast<valtype>(subscript); // Append serialized subscript
1536     }
1537
1538     // Test solution
1539     if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, true, 0))
1540         return false;
1541
1542     return true;
1543 }
1544
1545
1546 bool VerifySignature(const CTransaction& txFrom, const CTransaction& txTo, unsigned int nIn, bool fValidatePayToScriptHash, int nHashType)
1547 {
1548     assert(nIn < txTo.vin.size());
1549     const CTxIn& txin = txTo.vin[nIn];
1550     if (txin.prevout.n >= txFrom.vout.size())
1551         return false;
1552     const CTxOut& txout = txFrom.vout[txin.prevout.n];
1553
1554     if (txin.prevout.hash != txFrom.GetHash())
1555         return false;
1556
1557     if (!VerifyScript(txin.scriptSig, txout.scriptPubKey, txTo, nIn, fValidatePayToScriptHash, nHashType))
1558         return false;
1559
1560     return true;
1561 }
1562
1563 int CScript::GetSigOpCount(bool fAccurate) const
1564 {
1565     int n = 0;
1566     const_iterator pc = begin();
1567     opcodetype lastOpcode = OP_INVALIDOPCODE;
1568     while (pc < end())
1569     {
1570         opcodetype opcode;
1571         if (!GetOp(pc, opcode))
1572             break;
1573         if (opcode == OP_CHECKSIG || opcode == OP_CHECKSIGVERIFY)
1574             n++;
1575         else if (opcode == OP_CHECKMULTISIG || opcode == OP_CHECKMULTISIGVERIFY)
1576         {
1577             if (fAccurate && lastOpcode >= OP_1 && lastOpcode <= OP_16)
1578                 n += DecodeOP_N(lastOpcode);
1579             else
1580                 n += 20;
1581         }
1582         lastOpcode = opcode;
1583     }
1584     return n;
1585 }
1586
1587 int CScript::GetSigOpCount(const CScript& scriptSig) const
1588 {
1589     if (!IsPayToScriptHash())
1590         return GetSigOpCount(true);
1591
1592     // This is a pay-to-script-hash scriptPubKey;
1593     // get the last item that the scriptSig
1594     // pushes onto the stack:
1595     const_iterator pc = scriptSig.begin();
1596     vector<unsigned char> data;
1597     while (pc < scriptSig.end())
1598     {
1599         opcodetype opcode;
1600         if (!scriptSig.GetOp(pc, opcode, data))
1601             return 0;
1602         if (opcode > OP_16)
1603             return 0;
1604     }
1605
1606     /// ... and return it's opcount:
1607     CScript subscript(data.begin(), data.end());
1608     return subscript.GetSigOpCount(true);
1609 }
1610
1611 bool CScript::IsPayToScriptHash() const
1612 {
1613     // Extra-fast test for pay-to-script-hash CScripts:
1614     return (this->size() == 23 &&
1615             this->at(0) == OP_HASH160 &&
1616             this->at(1) == 0x14 &&
1617             this->at(22) == OP_EQUAL);
1618 }
1619
1620 void CScript::SetBitcoinAddress(const CBitcoinAddress& address)
1621 {
1622     this->clear();
1623     if (address.IsScript())
1624         *this << OP_HASH160 << address.GetHash160() << OP_EQUAL;
1625     else
1626         *this << OP_DUP << OP_HASH160 << address.GetHash160() << OP_EQUALVERIFY << OP_CHECKSIG;
1627 }
1628
1629 void CScript::SetMultisig(int nRequired, const std::vector<CKey>& keys)
1630 {
1631     this->clear();
1632
1633     *this << EncodeOP_N(nRequired);
1634     BOOST_FOREACH(const CKey& key, keys)
1635         *this << key.GetPubKey();
1636     *this << EncodeOP_N(keys.size()) << OP_CHECKMULTISIG;
1637 }
1638
1639 void CScript::SetPayToScriptHash(const CScript& subscript)
1640 {
1641     assert(!subscript.empty());
1642     uint160 subscriptHash = Hash160(subscript);
1643     this->clear();
1644     *this << OP_HASH160 << subscriptHash << OP_EQUAL;
1645 }