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