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