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 "sync.h"
  17 #include "util.h"
  18
  19 bool CheckSig(vector<unsigned char> vchSig, const vector<unsigned char> &vchPubKey, const CScript &scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType, int flags);
  20
  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 //
  55 // WARNING: This does not work as expected for signed integers; the sign-bit
  56 // is left in place as the integer is zero-extended. The correct behavior
  57 // would be to move the most significant bit of the last byte during the
  58 // resize process. MakeSameSize() is currently only used by the disabled
  59 // opcodes OP_AND, OP_OR, and OP_XOR.
  60 //
  61 void MakeSameSize(valtype& vch1, valtype& vch2)
  62 {
  63     // Lengthen the shorter one
  64     if (vch1.size() < vch2.size())
  65         // PATCH:
  66         // +unsigned char msb = vch1[vch1.size()-1];
  67         // +vch1[vch1.size()-1] &= 0x7f;
  68         //  vch1.resize(vch2.size(), 0);
  69         // +vch1[vch1.size()-1] = msb;
  70         vch1.resize(vch2.size(), 0);
  71     if (vch2.size() < vch1.size())
  72         // PATCH:
  73         // +unsigned char msb = vch2[vch2.size()-1];
  74         // +vch2[vch2.size()-1] &= 0x7f;
  75         //  vch2.resize(vch1.size(), 0);
  76         // +vch2[vch2.size()-1] = msb;
  77         vch2.resize(vch1.size(), 0);
  78 }
  79
  80
  81
  82 //
  83 // Script is a stack machine (like Forth) that evaluates a predicate
  84 // returning a bool indicating valid or not.  There are no loops.
  85 //
  86 #define stacktop(i)  (stack.at(stack.size()+(i)))
  87 #define altstacktop(i)  (altstack.at(altstack.size()+(i)))
  88 static inline void popstack(vector<valtype>& stack)
  89 {
  90     if (stack.empty())
  91         throw runtime_error("popstack() : stack empty");
  92     stack.pop_back();
  93 }
  94
  95
  96 const char* GetTxnOutputType(txnouttype t)
  97 {
  98     switch (t)
  99     {
 100     case TX_NONSTANDARD: return "nonstandard";
 101     case TX_PUBKEY: return "pubkey";
 102     case TX_PUBKEY_DROP: return "pubkeydrop";
 103     case TX_PUBKEYHASH: return "pubkeyhash";
 104     case TX_SCRIPTHASH: return "scripthash";
 105     case TX_MULTISIG: return "multisig";
 106     case TX_NULL_DATA: return "nulldata";
 107     }
 108     return NULL;
 109 }
 110
 111
 112 const char* GetOpName(opcodetype opcode)
 113 {
 114     switch (opcode)
 115     {
 116     // push value
 117     case OP_0                      : return "0";
 118     case OP_PUSHDATA1              : return "OP_PUSHDATA1";
 119     case OP_PUSHDATA2              : return "OP_PUSHDATA2";
 120     case OP_PUSHDATA4              : return "OP_PUSHDATA4";
 121     case OP_1NEGATE                : return "-1";
 122     case OP_RESERVED               : return "OP_RESERVED";
 123     case OP_1                      : return "1";
 124     case OP_2                      : return "2";
 125     case OP_3                      : return "3";
 126     case OP_4                      : return "4";
 127     case OP_5                      : return "5";
 128     case OP_6                      : return "6";
 129     case OP_7                      : return "7";
 130     case OP_8                      : return "8";
 131     case OP_9                      : return "9";
 132     case OP_10                     : return "10";
 133     case OP_11                     : return "11";
 134     case OP_12                     : return "12";
 135     case OP_13                     : return "13";
 136     case OP_14                     : return "14";
 137     case OP_15                     : return "15";
 138     case OP_16                     : return "16";
 139
 140     // control
 141     case OP_NOP                    : return "OP_NOP";
 142     case OP_VER                    : return "OP_VER";
 143     case OP_IF                     : return "OP_IF";
 144     case OP_NOTIF                  : return "OP_NOTIF";
 145     case OP_VERIF                  : return "OP_VERIF";
 146     case OP_VERNOTIF               : return "OP_VERNOTIF";
 147     case OP_ELSE                   : return "OP_ELSE";
 148     case OP_ENDIF                  : return "OP_ENDIF";
 149     case OP_VERIFY                 : return "OP_VERIFY";
 150     case OP_RETURN                 : return "OP_RETURN";
 151     case OP_CHECKLOCKTIMEVERIFY    : return "OP_CHECKLOCKTIMEVERIFY";
 152
 153     // stack ops
 154     case OP_TOALTSTACK             : return "OP_TOALTSTACK";
 155     case OP_FROMALTSTACK           : return "OP_FROMALTSTACK";
 156     case OP_2DROP                  : return "OP_2DROP";
 157     case OP_2DUP                   : return "OP_2DUP";
 158     case OP_3DUP                   : return "OP_3DUP";
 159     case OP_2OVER                  : return "OP_2OVER";
 160     case OP_2ROT                   : return "OP_2ROT";
 161     case OP_2SWAP                  : return "OP_2SWAP";
 162     case OP_IFDUP                  : return "OP_IFDUP";
 163     case OP_DEPTH                  : return "OP_DEPTH";
 164     case OP_DROP                   : return "OP_DROP";
 165     case OP_DUP                    : return "OP_DUP";
 166     case OP_NIP                    : return "OP_NIP";
 167     case OP_OVER                   : return "OP_OVER";
 168     case OP_PICK                   : return "OP_PICK";
 169     case OP_ROLL                   : return "OP_ROLL";
 170     case OP_ROT                    : return "OP_ROT";
 171     case OP_SWAP                   : return "OP_SWAP";
 172     case OP_TUCK                   : return "OP_TUCK";
 173
 174     // splice ops
 175     case OP_CAT                    : return "OP_CAT";
 176     case OP_SUBSTR                 : return "OP_SUBSTR";
 177     case OP_LEFT                   : return "OP_LEFT";
 178     case OP_RIGHT                  : return "OP_RIGHT";
 179     case OP_SIZE                   : return "OP_SIZE";
 180
 181     // bit logic
 182     case OP_INVERT                 : return "OP_INVERT";
 183     case OP_AND                    : return "OP_AND";
 184     case OP_OR                     : return "OP_OR";
 185     case OP_XOR                    : return "OP_XOR";
 186     case OP_EQUAL                  : return "OP_EQUAL";
 187     case OP_EQUALVERIFY            : return "OP_EQUALVERIFY";
 188     case OP_RESERVED1              : return "OP_RESERVED1";
 189     case OP_RESERVED2              : return "OP_RESERVED2";
 190
 191     // numeric
 192     case OP_1ADD                   : return "OP_1ADD";
 193     case OP_1SUB                   : return "OP_1SUB";
 194     case OP_2MUL                   : return "OP_2MUL";
 195     case OP_2DIV                   : return "OP_2DIV";
 196     case OP_NEGATE                 : return "OP_NEGATE";
 197     case OP_ABS                    : return "OP_ABS";
 198     case OP_NOT                    : return "OP_NOT";
 199     case OP_0NOTEQUAL              : return "OP_0NOTEQUAL";
 200     case OP_ADD                    : return "OP_ADD";
 201     case OP_SUB                    : return "OP_SUB";
 202     case OP_MUL                    : return "OP_MUL";
 203     case OP_DIV                    : return "OP_DIV";
 204     case OP_MOD                    : return "OP_MOD";
 205     case OP_LSHIFT                 : return "OP_LSHIFT";
 206     case OP_RSHIFT                 : return "OP_RSHIFT";
 207     case OP_BOOLAND                : return "OP_BOOLAND";
 208     case OP_BOOLOR                 : return "OP_BOOLOR";
 209     case OP_NUMEQUAL               : return "OP_NUMEQUAL";
 210     case OP_NUMEQUALVERIFY         : return "OP_NUMEQUALVERIFY";
 211     case OP_NUMNOTEQUAL            : return "OP_NUMNOTEQUAL";
 212     case OP_LESSTHAN               : return "OP_LESSTHAN";
 213     case OP_GREATERTHAN            : return "OP_GREATERTHAN";
 214     case OP_LESSTHANOREQUAL        : return "OP_LESSTHANOREQUAL";
 215     case OP_GREATERTHANOREQUAL     : return "OP_GREATERTHANOREQUAL";
 216     case OP_MIN                    : return "OP_MIN";
 217     case OP_MAX                    : return "OP_MAX";
 218     case OP_WITHIN                 : return "OP_WITHIN";
 219
 220     // crypto
 221     case OP_RIPEMD160              : return "OP_RIPEMD160";
 222     case OP_SHA1                   : return "OP_SHA1";
 223     case OP_SHA256                 : return "OP_SHA256";
 224     case OP_HASH160                : return "OP_HASH160";
 225     case OP_HASH256                : return "OP_HASH256";
 226     case OP_CODESEPARATOR          : return "OP_CODESEPARATOR";
 227     case OP_CHECKSIG               : return "OP_CHECKSIG";
 228     case OP_CHECKSIGVERIFY         : return "OP_CHECKSIGVERIFY";
 229     case OP_CHECKMULTISIG          : return "OP_CHECKMULTISIG";
 230     case OP_CHECKMULTISIGVERIFY    : return "OP_CHECKMULTISIGVERIFY";
 231
 232     // expanson
 233     case OP_NOP1                   : return "OP_NOP1";
 234     case OP_NOP3                   : return "OP_NOP3";
 235     case OP_NOP4                   : return "OP_NOP4";
 236     case OP_NOP5                   : return "OP_NOP5";
 237     case OP_NOP6                   : return "OP_NOP6";
 238     case OP_NOP7                   : return "OP_NOP7";
 239     case OP_NOP8                   : return "OP_NOP8";
 240     case OP_NOP9                   : return "OP_NOP9";
 241     case OP_NOP10                  : return "OP_NOP10";
 242
 243
 244
 245     // template matching params
 246     case OP_PUBKEYHASH             : return "OP_PUBKEYHASH";
 247     case OP_PUBKEY                 : return "OP_PUBKEY";
 248     case OP_SMALLDATA              : return "OP_SMALLDATA";
 249
 250     case OP_INVALIDOPCODE          : return "OP_INVALIDOPCODE";
 251     default:
 252         return "OP_UNKNOWN";
 253     }
 254 }
 255
 256 bool IsCanonicalPubKey(const valtype &vchPubKey, unsigned int flags) {
 257     if (!(flags & SCRIPT_VERIFY_STRICTENC))
 258         return true;
 259
 260     if (vchPubKey.size() < 33)
 261         return error("Non-canonical public key: too short");
 262     if (vchPubKey[0] == 0x04) {
 263         if (vchPubKey.size() != 65)
 264             return error("Non-canonical public key: invalid length for uncompressed key");
 265     } else if (vchPubKey[0] == 0x02 || vchPubKey[0] == 0x03) {
 266         if (vchPubKey.size() != 33)
 267             return error("Non-canonical public key: invalid length for compressed key");
 268     } else {
 269         return error("Non-canonical public key: compressed nor uncompressed");
 270     }
 271     return true;
 272 }
 273
 274 bool IsDERSignature(const valtype &vchSig, bool fWithHashType, bool fCheckLow) {
 275     // See https://bitcointalk.org/index.php?topic=8392.msg127623#msg127623
 276     // A canonical signature exists of: <30> <total len> <02> <len R> <R> <02> <len S> <S> <hashtype>
 277     // Where R and S are not negative (their first byte has its highest bit not set), and not
 278     // excessively padded (do not start with a 0 byte, unless an otherwise negative number follows,
 279     // in which case a single 0 byte is necessary and even required).
 280     if (vchSig.size() < 9)
 281         return error("Non-canonical signature: too short");
 282     if (vchSig.size() > 73)
 283         return error("Non-canonical signature: too long");
 284     if (vchSig[0] != 0x30)
 285         return error("Non-canonical signature: wrong type");
 286     if (vchSig[1] != vchSig.size() - (fWithHashType ? 3 : 2))
 287         return error("Non-canonical signature: wrong length marker");
 288     if (fWithHashType) {
 289         unsigned char nHashType = vchSig[vchSig.size() - 1] & (~(SIGHASH_ANYONECANPAY));
 290         if (nHashType < SIGHASH_ALL || nHashType > SIGHASH_SINGLE)
 291             return error("Non-canonical signature: unknown hashtype byte");
 292     }
 293     unsigned int nLenR = vchSig[3];
 294     if (5 + nLenR >= vchSig.size())
 295         return error("Non-canonical signature: S length misplaced");
 296     unsigned int nLenS = vchSig[5+nLenR];
 297     if ((nLenR + nLenS + (fWithHashType ? 7 : 6)) != vchSig.size())
 298         return error("Non-canonical signature: R+S length mismatch");
 299
 300     const unsigned char *R = &vchSig[4];
 301     if (R[-2] != 0x02)
 302         return error("Non-canonical signature: R value type mismatch");
 303     if (nLenR == 0)
 304         return error("Non-canonical signature: R length is zero");
 305     if (R[0] & 0x80)
 306         return error("Non-canonical signature: R value negative");
 307     if (nLenR > 1 && (R[0] == 0x00) && !(R[1] & 0x80))
 308         return error("Non-canonical signature: R value excessively padded");
 309
 310     const unsigned char *S = &vchSig[6+nLenR];
 311     if (S[-2] != 0x02)
 312         return error("Non-canonical signature: S value type mismatch");
 313     if (nLenS == 0)
 314         return error("Non-canonical signature: S length is zero");
 315     if (S[0] & 0x80)
 316         return error("Non-canonical signature: S value negative");
 317     if (nLenS > 1 && (S[0] == 0x00) && !(S[1] & 0x80))
 318         return error("Non-canonical signature: S value excessively padded");
 319
 320     if (fCheckLow) {
 321         unsigned int nLenR = vchSig[3];
 322         unsigned int nLenS = vchSig[5+nLenR];
 323         const unsigned char *S = &vchSig[6+nLenR];
 324         // If the S value is above the order of the curve divided by two, its
 325         // complement modulo the order could have been used instead, which is
 326         // one byte shorter when encoded correctly.
 327         if (!CKey::CheckSignatureElement(S, nLenS, true))
 328             return error("Non-canonical signature: S value is unnecessarily high");
 329     }
 330
 331     return true;
 332 }
 333
 334 bool IsCanonicalSignature(const valtype &vchSig, unsigned int flags) {
 335     if (!(flags & SCRIPT_VERIFY_STRICTENC))
 336         return true;
 337
 338     return IsDERSignature(vchSig, true, (flags & SCRIPT_VERIFY_LOW_S) != 0);
 339 }
 340
 341 bool EvalScript(vector<vector<unsigned char> >& stack, const CScript& script, const CTransaction& txTo, unsigned int nIn, unsigned int flags, int nHashType)
 342 {
 343     CAutoBN_CTX pctx;
 344     CScript::const_iterator pc = script.begin();
 345     CScript::const_iterator pend = script.end();
 346     CScript::const_iterator pbegincodehash = script.begin();
 347     opcodetype opcode;
 348     valtype vchPushValue;
 349     vector<bool> vfExec;
 350     vector<valtype> altstack;
 351     if (script.size() > 10000)
 352         return false;
 353     int nOpCount = 0;
 354
 355     try
 356     {
 357         while (pc < pend)
 358         {
 359             bool fExec = !count(vfExec.begin(), vfExec.end(), false);
 360
 361             //
 362             // Read instruction
 363             //
 364             if (!script.GetOp(pc, opcode, vchPushValue))
 365                 return false;
 366             if (vchPushValue.size() > MAX_SCRIPT_ELEMENT_SIZE)
 367                 return false;
 368             if (opcode > OP_16 && ++nOpCount > 201)
 369                 return false;
 370
 371             if (opcode == OP_CAT ||
 372                 opcode == OP_SUBSTR ||
 373                 opcode == OP_LEFT ||
 374                 opcode == OP_RIGHT ||
 375                 opcode == OP_INVERT ||
 376                 opcode == OP_AND ||
 377                 opcode == OP_OR ||
 378                 opcode == OP_XOR ||
 379                 opcode == OP_2MUL ||
 380                 opcode == OP_2DIV ||
 381                 opcode == OP_MUL ||
 382                 opcode == OP_DIV ||
 383                 opcode == OP_MOD ||
 384                 opcode == OP_LSHIFT ||
 385                 opcode == OP_RSHIFT)
 386                 return false; // Disabled opcodes.
 387
 388             if (fExec && 0 <= opcode && opcode <= OP_PUSHDATA4)
 389                 stack.push_back(vchPushValue);
 390             else if (fExec || (OP_IF <= opcode && opcode <= OP_ENDIF))
 391             switch (opcode)
 392             {
 393                 //
 394                 // Push value
 395                 //
 396                 case OP_1NEGATE:
 397                 case OP_1:
 398                 case OP_2:
 399                 case OP_3:
 400                 case OP_4:
 401                 case OP_5:
 402                 case OP_6:
 403                 case OP_7:
 404                 case OP_8:
 405                 case OP_9:
 406                 case OP_10:
 407                 case OP_11:
 408                 case OP_12:
 409                 case OP_13:
 410                 case OP_14:
 411                 case OP_15:
 412                 case OP_16:
 413                 {
 414                     // ( -- value)
 415                     CBigNum bn((int)opcode - (int)(OP_1 - 1));
 416                     stack.push_back(bn.getvch());
 417                 }
 418                 break;
 419
 420
 421                 //
 422                 // Control
 423                 //
 424                 case OP_NOP:
 425                 case OP_NOP1: case OP_NOP3: case OP_NOP4: case OP_NOP5:
 426                 case OP_NOP6: case OP_NOP7: case OP_NOP8: case OP_NOP9: case OP_NOP10:
 427                 break;
 428
 429                 case OP_IF:
 430                 case OP_NOTIF:
 431                 {
 432                     // <expression> if [statements] [else [statements]] endif
 433                     bool fValue = false;
 434                     if (fExec)
 435                     {
 436                         if (stack.size() < 1)
 437                             return false;
 438                         valtype& vch = stacktop(-1);
 439                         fValue = CastToBool(vch);
 440                         if (opcode == OP_NOTIF)
 441                             fValue = !fValue;
 442                         popstack(stack);
 443                     }
 444                     vfExec.push_back(fValue);
 445                 }
 446                 break;
 447
 448                 case OP_ELSE:
 449                 {
 450                     if (vfExec.empty())
 451                         return false;
 452                     vfExec.back() = !vfExec.back();
 453                 }
 454                 break;
 455
 456                 case OP_ENDIF:
 457                 {
 458                     if (vfExec.empty())
 459                         return false;
 460                     vfExec.pop_back();
 461                 }
 462                 break;
 463
 464                 case OP_VERIFY:
 465                 {
 466                     // (true -- ) or
 467                     // (false -- false) and return
 468                     if (stack.size() < 1)
 469                         return false;
 470                     bool fValue = CastToBool(stacktop(-1));
 471                     if (fValue)
 472                         popstack(stack);
 473                     else
 474                         return false;
 475                 }
 476                 break;
 477
 478                 case OP_RETURN:
 479                 {
 480                     return false;
 481                 }
 482                 break;
 483
 484                 case OP_CHECKLOCKTIMEVERIFY:
 485                 {
 486                     // CHECKLOCKTIMEVERIFY
 487                     //
 488                     // (nLockTime -- nLockTime)
 489                     if (!(flags & SCRIPT_VERIFY_CHECKLOCKTIMEVERIFY))
 490                         break; // treat as a NOP is not enabled
 491                     if (stack.size() < 1)
 492                         return false;
 493                     const CBigNum nLockTime = CastToBigNum(stacktop(-1));
 494                     if (nLockTime < 0)
 495                         return false; // Negative argument is senseless.
 496
 497                     if (!( // We can have either lock-by-blockheight or lock-by-blocktime.
 498                           (txTo.nLockTime <  LOCKTIME_THRESHOLD && nLockTime <  LOCKTIME_THRESHOLD) ||
 499                           (txTo.nLockTime >= LOCKTIME_THRESHOLD && nLockTime >= LOCKTIME_THRESHOLD)
 500                     ))
 501                         return false;
 502
 503                     // Now we can perform a simple numerical comparison
 504                     if (nLockTime > (int64_t)txTo.nLockTime)
 505                         return false;
 506
 507                     // Finally the nLockTime feature can be disabled and thus
 508                     // CHECKLOCKTIMEVERIFY bypassed if every txin has been
 509                     // finalized by setting nSequence to maxint. The
 510                     // transaction would be allowed into the blockchain, making
 511                     // the opcode ineffective.
 512                     //
 513                     // Testing if this vin is not final is sufficient to
 514                     // prevent this condition. Alternatively we could test all
 515                     // inputs, but testing just this input minimizes the data
 516                     // required to prove correct CHECKLOCKTIMEVERIFY execution.
 517                     if (txTo.vin[nIn].IsFinal())
 518                         return false;
 519                     break;
 520                 }
 521
 522                 //
 523                 // Stack ops
 524                 //
 525                 case OP_TOALTSTACK:
 526                 {
 527                     if (stack.size() < 1)
 528                         return false;
 529                     altstack.push_back(stacktop(-1));
 530                     popstack(stack);
 531                 }
 532                 break;
 533
 534                 case OP_FROMALTSTACK:
 535                 {
 536                     if (altstack.size() < 1)
 537                         return false;
 538                     stack.push_back(altstacktop(-1));
 539                     popstack(altstack);
 540                 }
 541                 break;
 542
 543                 case OP_2DROP:
 544                 {
 545                     // (x1 x2 -- )
 546                     if (stack.size() < 2)
 547                         return false;
 548                     popstack(stack);
 549                     popstack(stack);
 550                 }
 551                 break;
 552
 553                 case OP_2DUP:
 554                 {
 555                     // (x1 x2 -- x1 x2 x1 x2)
 556                     if (stack.size() < 2)
 557                         return false;
 558                     valtype vch1 = stacktop(-2);
 559                     valtype vch2 = stacktop(-1);
 560                     stack.push_back(vch1);
 561                     stack.push_back(vch2);
 562                 }
 563                 break;
 564
 565                 case OP_3DUP:
 566                 {
 567                     // (x1 x2 x3 -- x1 x2 x3 x1 x2 x3)
 568                     if (stack.size() < 3)
 569                         return false;
 570                     valtype vch1 = stacktop(-3);
 571                     valtype vch2 = stacktop(-2);
 572                     valtype vch3 = stacktop(-1);
 573                     stack.push_back(vch1);
 574                     stack.push_back(vch2);
 575                     stack.push_back(vch3);
 576                 }
 577                 break;
 578
 579                 case OP_2OVER:
 580                 {
 581                     // (x1 x2 x3 x4 -- x1 x2 x3 x4 x1 x2)
 582                     if (stack.size() < 4)
 583                         return false;
 584                     valtype vch1 = stacktop(-4);
 585                     valtype vch2 = stacktop(-3);
 586                     stack.push_back(vch1);
 587                     stack.push_back(vch2);
 588                 }
 589                 break;
 590
 591                 case OP_2ROT:
 592                 {
 593                     // (x1 x2 x3 x4 x5 x6 -- x3 x4 x5 x6 x1 x2)
 594                     if (stack.size() < 6)
 595                         return false;
 596                     valtype vch1 = stacktop(-6);
 597                     valtype vch2 = stacktop(-5);
 598                     stack.erase(stack.end()-6, stack.end()-4);
 599                     stack.push_back(vch1);
 600                     stack.push_back(vch2);
 601                 }
 602                 break;
 603
 604                 case OP_2SWAP:
 605                 {
 606                     // (x1 x2 x3 x4 -- x3 x4 x1 x2)
 607                     if (stack.size() < 4)
 608                         return false;
 609                     swap(stacktop(-4), stacktop(-2));
 610                     swap(stacktop(-3), stacktop(-1));
 611                 }
 612                 break;
 613
 614                 case OP_IFDUP:
 615                 {
 616                     // (x - 0 | x x)
 617                     if (stack.size() < 1)
 618                         return false;
 619                     valtype vch = stacktop(-1);
 620                     if (CastToBool(vch))
 621                         stack.push_back(vch);
 622                 }
 623                 break;
 624
 625                 case OP_DEPTH:
 626                 {
 627                     // -- stacksize
 628                     CBigNum bn((uint16_t) stack.size());
 629                     stack.push_back(bn.getvch());
 630                 }
 631                 break;
 632
 633                 case OP_DROP:
 634                 {
 635                     // (x -- )
 636                     if (stack.size() < 1)
 637                         return false;
 638                     popstack(stack);
 639                 }
 640                 break;
 641
 642                 case OP_DUP:
 643                 {
 644                     // (x -- x x)
 645                     if (stack.size() < 1)
 646                         return false;
 647                     valtype vch = stacktop(-1);
 648                     stack.push_back(vch);
 649                 }
 650                 break;
 651
 652                 case OP_NIP:
 653                 {
 654                     // (x1 x2 -- x2)
 655                     if (stack.size() < 2)
 656                         return false;
 657                     stack.erase(stack.end() - 2);
 658                 }
 659                 break;
 660
 661                 case OP_OVER:
 662                 {
 663                     // (x1 x2 -- x1 x2 x1)
 664                     if (stack.size() < 2)
 665                         return false;
 666                     valtype vch = stacktop(-2);
 667                     stack.push_back(vch);
 668                 }
 669                 break;
 670
 671                 case OP_PICK:
 672                 case OP_ROLL:
 673                 {
 674                     // (xn ... x2 x1 x0 n - xn ... x2 x1 x0 xn)
 675                     // (xn ... x2 x1 x0 n - ... x2 x1 x0 xn)
 676                     if (stack.size() < 2)
 677                         return false;
 678                     int n = CastToBigNum(stacktop(-1)).getint32();
 679                     popstack(stack);
 680                     if (n < 0 || n >= (int)stack.size())
 681                         return false;
 682                     valtype vch = stacktop(-n-1);
 683                     if (opcode == OP_ROLL)
 684                         stack.erase(stack.end()-n-1);
 685                     stack.push_back(vch);
 686                 }
 687                 break;
 688
 689                 case OP_ROT:
 690                 {
 691                     // (x1 x2 x3 -- x2 x3 x1)
 692                     //  x2 x1 x3  after first swap
 693                     //  x2 x3 x1  after second swap
 694                     if (stack.size() < 3)
 695                         return false;
 696                     swap(stacktop(-3), stacktop(-2));
 697                     swap(stacktop(-2), stacktop(-1));
 698                 }
 699                 break;
 700
 701                 case OP_SWAP:
 702                 {
 703                     // (x1 x2 -- x2 x1)
 704                     if (stack.size() < 2)
 705                         return false;
 706                     swap(stacktop(-2), stacktop(-1));
 707                 }
 708                 break;
 709
 710                 case OP_TUCK:
 711                 {
 712                     // (x1 x2 -- x2 x1 x2)
 713                     if (stack.size() < 2)
 714                         return false;
 715                     valtype vch = stacktop(-1);
 716                     stack.insert(stack.end()-2, vch);
 717                 }
 718                 break;
 719
 720
 721                 case OP_SIZE:
 722                 {
 723                     // (in -- in size)
 724                     if (stack.size() < 1)
 725                         return false;
 726                     CBigNum bn((uint16_t) stacktop(-1).size());
 727                     stack.push_back(bn.getvch());
 728                 }
 729                 break;
 730
 731
 732                 //
 733                 // Bitwise logic
 734                 //
 735                 case OP_EQUAL:
 736                 case OP_EQUALVERIFY:
 737                 //case OP_NOTEQUAL: // use OP_NUMNOTEQUAL
 738                 {
 739                     // (x1 x2 - bool)
 740                     if (stack.size() < 2)
 741                         return false;
 742                     valtype& vch1 = stacktop(-2);
 743                     valtype& vch2 = stacktop(-1);
 744                     bool fEqual = (vch1 == vch2);
 745                     // OP_NOTEQUAL is disabled because it would be too easy to say
 746                     // something like n != 1 and have some wiseguy pass in 1 with extra
 747                     // zero bytes after it (numerically, 0x01 == 0x0001 == 0x000001)
 748                     //if (opcode == OP_NOTEQUAL)
 749                     //    fEqual = !fEqual;
 750                     popstack(stack);
 751                     popstack(stack);
 752                     stack.push_back(fEqual ? vchTrue : vchFalse);
 753                     if (opcode == OP_EQUALVERIFY)
 754                     {
 755                         if (fEqual)
 756                             popstack(stack);
 757                         else
 758                             return false;
 759                     }
 760                 }
 761                 break;
 762
 763
 764                 //
 765                 // Numeric
 766                 //
 767                 case OP_1ADD:
 768                 case OP_1SUB:
 769                 case OP_NEGATE:
 770                 case OP_ABS:
 771                 case OP_NOT:
 772                 case OP_0NOTEQUAL:
 773                 {
 774                     // (in -- out)
 775                     if (stack.size() < 1)
 776                         return false;
 777                     CBigNum bn = CastToBigNum(stacktop(-1));
 778                     switch (opcode)
 779                     {
 780                     case OP_1ADD:       bn += bnOne; break;
 781                     case OP_1SUB:       bn -= bnOne; break;
 782                     case OP_NEGATE:     bn = -bn; break;
 783                     case OP_ABS:        if (bn < bnZero) bn = -bn; break;
 784                     case OP_NOT:        bn = (bn == bnZero); break;
 785                     case OP_0NOTEQUAL:  bn = (bn != bnZero); break;
 786                     default:            assert(!"invalid opcode"); break;
 787                     }
 788                     popstack(stack);
 789                     stack.push_back(bn.getvch());
 790                 }
 791                 break;
 792
 793                 case OP_ADD:
 794                 case OP_SUB:
 795                 case OP_BOOLAND:
 796                 case OP_BOOLOR:
 797                 case OP_NUMEQUAL:
 798                 case OP_NUMEQUALVERIFY:
 799                 case OP_NUMNOTEQUAL:
 800                 case OP_LESSTHAN:
 801                 case OP_GREATERTHAN:
 802                 case OP_LESSTHANOREQUAL:
 803                 case OP_GREATERTHANOREQUAL:
 804                 case OP_MIN:
 805                 case OP_MAX:
 806                 {
 807                     // (x1 x2 -- out)
 808                     if (stack.size() < 2)
 809                         return false;
 810                     CBigNum bn1 = CastToBigNum(stacktop(-2));
 811                     CBigNum bn2 = CastToBigNum(stacktop(-1));
 812                     CBigNum bn;
 813                     switch (opcode)
 814                     {
 815                     case OP_ADD:
 816                         bn = bn1 + bn2;
 817                         break;
 818
 819                     case OP_SUB:
 820                         bn = bn1 - bn2;
 821                         break;
 822
 823                     case OP_BOOLAND:             bn = (bn1 != bnZero && bn2 != bnZero); break;
 824                     case OP_BOOLOR:              bn = (bn1 != bnZero || bn2 != bnZero); break;
 825                     case OP_NUMEQUAL:            bn = (bn1 == bn2); break;
 826                     case OP_NUMEQUALVERIFY:      bn = (bn1 == bn2); break;
 827                     case OP_NUMNOTEQUAL:         bn = (bn1 != bn2); break;
 828                     case OP_LESSTHAN:            bn = (bn1 < bn2); break;
 829                     case OP_GREATERTHAN:         bn = (bn1 > bn2); break;
 830                     case OP_LESSTHANOREQUAL:     bn = (bn1 <= bn2); break;
 831                     case OP_GREATERTHANOREQUAL:  bn = (bn1 >= bn2); break;
 832                     case OP_MIN:                 bn = (bn1 < bn2 ? bn1 : bn2); break;
 833                     case OP_MAX:                 bn = (bn1 > bn2 ? bn1 : bn2); break;
 834                     default:                     assert(!"invalid opcode"); break;
 835                     }
 836                     popstack(stack);
 837                     popstack(stack);
 838                     stack.push_back(bn.getvch());
 839
 840                     if (opcode == OP_NUMEQUALVERIFY)
 841                     {
 842                         if (CastToBool(stacktop(-1)))
 843                             popstack(stack);
 844                         else
 845                             return false;
 846                     }
 847                 }
 848                 break;
 849
 850                 case OP_WITHIN:
 851                 {
 852                     // (x min max -- out)
 853                     if (stack.size() < 3)
 854                         return false;
 855                     CBigNum bn1 = CastToBigNum(stacktop(-3));
 856                     CBigNum bn2 = CastToBigNum(stacktop(-2));
 857                     CBigNum bn3 = CastToBigNum(stacktop(-1));
 858                     bool fValue = (bn2 <= bn1 && bn1 < bn3);
 859                     popstack(stack);
 860                     popstack(stack);
 861                     popstack(stack);
 862                     stack.push_back(fValue ? vchTrue : vchFalse);
 863                 }
 864                 break;
 865
 866
 867                 //
 868                 // Crypto
 869                 //
 870                 case OP_RIPEMD160:
 871                 case OP_SHA1:
 872                 case OP_SHA256:
 873                 case OP_HASH160:
 874                 case OP_HASH256:
 875                 {
 876                     // (in -- hash)
 877                     if (stack.size() < 1)
 878                         return false;
 879                     valtype& vch = stacktop(-1);
 880                     valtype vchHash((opcode == OP_RIPEMD160 || opcode == OP_SHA1 || opcode == OP_HASH160) ? 20 : 32);
 881                     if (opcode == OP_RIPEMD160)
 882                         RIPEMD160(&vch[0], vch.size(), &vchHash[0]);
 883                     else if (opcode == OP_SHA1)
 884                         SHA1(&vch[0], vch.size(), &vchHash[0]);
 885                     else if (opcode == OP_SHA256)
 886                         SHA256(&vch[0], vch.size(), &vchHash[0]);
 887                     else if (opcode == OP_HASH160)
 888                     {
 889                         uint160 hash160 = Hash160(vch);
 890                         memcpy(&vchHash[0], &hash160, sizeof(hash160));
 891                     }
 892                     else if (opcode == OP_HASH256)
 893                     {
 894                         uint256 hash = Hash(vch.begin(), vch.end());
 895                         memcpy(&vchHash[0], &hash, sizeof(hash));
 896                     }
 897                     popstack(stack);
 898                     stack.push_back(vchHash);
 899                 }
 900                 break;
 901
 902                 case OP_CODESEPARATOR:
 903                 {
 904                     // Hash starts after the code separator
 905                     pbegincodehash = pc;
 906                 }
 907                 break;
 908
 909                 case OP_CHECKSIG:
 910                 case OP_CHECKSIGVERIFY:
 911                 {
 912                     // (sig pubkey -- bool)
 913                     if (stack.size() < 2)
 914                         return false;
 915
 916                     valtype& vchSig    = stacktop(-2);
 917                     valtype& vchPubKey = stacktop(-1);
 918
 919                     ////// debug print
 920                     //PrintHex(vchSig.begin(), vchSig.end(), "sig: %s\n");
 921                     //PrintHex(vchPubKey.begin(), vchPubKey.end(), "pubkey: %s\n");
 922
 923                     // Subset of script starting at the most recent codeseparator
 924                     CScript scriptCode(pbegincodehash, pend);
 925
 926                     // Drop the signature, since there's no way for a signature to sign itself
 927                     scriptCode.FindAndDelete(CScript(vchSig));
 928
 929                     bool fSuccess = IsCanonicalSignature(vchSig, flags) && IsCanonicalPubKey(vchPubKey, flags) &&
 930                         CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType, flags);
 931
 932                     popstack(stack);
 933                     popstack(stack);
 934                     stack.push_back(fSuccess ? vchTrue : vchFalse);
 935                     if (opcode == OP_CHECKSIGVERIFY)
 936                     {
 937                         if (fSuccess)
 938                             popstack(stack);
 939                         else
 940                             return false;
 941                     }
 942                 }
 943                 break;
 944
 945                 case OP_CHECKMULTISIG:
 946                 case OP_CHECKMULTISIGVERIFY:
 947                 {
 948                     // ([sig ...] num_of_signatures [pubkey ...] num_of_pubkeys -- bool)
 949
 950                     int i = 1;
 951                     if ((int)stack.size() < i)
 952                         return false;
 953
 954                     int nKeysCount = CastToBigNum(stacktop(-i)).getint32();
 955                     if (nKeysCount < 0 || nKeysCount > 20)
 956                         return false;
 957                     nOpCount += nKeysCount;
 958                     if (nOpCount > 201)
 959                         return false;
 960                     int ikey = ++i;
 961                     i += nKeysCount;
 962                     if ((int)stack.size() < i)
 963                         return false;
 964
 965                     int nSigsCount = CastToBigNum(stacktop(-i)).getint32();
 966                     if (nSigsCount < 0 || nSigsCount > nKeysCount)
 967                         return false;
 968                     int isig = ++i;
 969                     i += nSigsCount;
 970                     if ((int)stack.size() < i)
 971                         return false;
 972
 973                     // Subset of script starting at the most recent codeseparator
 974                     CScript scriptCode(pbegincodehash, pend);
 975
 976                     // Drop the signatures, since there's no way for a signature to sign itself
 977                     for (int k = 0; k < nSigsCount; k++)
 978                     {
 979                         valtype& vchSig = stacktop(-isig-k);
 980                         scriptCode.FindAndDelete(CScript(vchSig));
 981                     }
 982
 983                     bool fSuccess = true;
 984                     while (fSuccess && nSigsCount > 0)
 985                     {
 986                         valtype& vchSig    = stacktop(-isig);
 987                         valtype& vchPubKey = stacktop(-ikey);
 988
 989                         // Check signature
 990                         bool fOk = IsCanonicalSignature(vchSig, flags) && IsCanonicalPubKey(vchPubKey, flags) &&
 991                             CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType, flags);
 992
 993                         if (fOk) {
 994                             isig++;
 995                             nSigsCount--;
 996                         }
 997                         ikey++;
 998                         nKeysCount--;
 999
1000                         // If there are more signatures left than keys left,
1001                         // then too many signatures have failed
1002                         if (nSigsCount > nKeysCount)
1003                             fSuccess = false;
1004                     }
1005
1006                     while (i-- > 1)
1007                         popstack(stack);
1008
1009                     // A bug causes CHECKMULTISIG to consume one extra argument
1010                     // whose contents were not checked in any way.
1011                     //
1012                     // Unfortunately this is a potential source of mutability,
1013                     // so optionally verify it is exactly equal to zero prior
1014                     // to removing it from the stack.
1015                     if (stack.size() < 1)
1016                         return false;
1017                     if ((flags & SCRIPT_VERIFY_NULLDUMMY) && stacktop(-1).size())
1018                         return error("CHECKMULTISIG dummy argument not null");
1019                     popstack(stack);
1020
1021                     stack.push_back(fSuccess ? vchTrue : vchFalse);
1022
1023                     if (opcode == OP_CHECKMULTISIGVERIFY)
1024                     {
1025                         if (fSuccess)
1026                             popstack(stack);
1027                         else
1028                             return false;
1029                     }
1030                 }
1031                 break;
1032
1033                 default:
1034                     return false;
1035             }
1036
1037             // Size limits
1038             if (stack.size() + altstack.size() > 1000)
1039                 return false;
1040         }
1041     }
1042     catch (...)
1043     {
1044         return false;
1045     }
1046
1047
1048     if (!vfExec.empty())
1049         return false;
1050
1051     return true;
1052 }
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062 uint256 SignatureHash(CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType)
1063 {
1064     if (nIn >= txTo.vin.size())
1065     {
1066         printf("ERROR: SignatureHash() : nIn=%d out of range\n", nIn);
1067         return 1;
1068     }
1069     CTransaction txTmp(txTo);
1070
1071     // In case concatenating two scripts ends up with two codeseparators,
1072     // or an extra one at the end, this prevents all those possible incompatibilities.
1073     scriptCode.FindAndDelete(CScript(OP_CODESEPARATOR));
1074
1075     // Blank out other inputs' signatures
1076     for (unsigned int i = 0; i < txTmp.vin.size(); i++)
1077         txTmp.vin[i].scriptSig = CScript();
1078     txTmp.vin[nIn].scriptSig = scriptCode;
1079
1080     // Blank out some of the outputs
1081     if ((nHashType & 0x1f) == SIGHASH_NONE)
1082     {
1083         // Wildcard payee
1084         txTmp.vout.clear();
1085
1086         // Let the others update at will
1087         for (unsigned int i = 0; i < txTmp.vin.size(); i++)
1088             if (i != nIn)
1089                 txTmp.vin[i].nSequence = 0;
1090     }
1091     else if ((nHashType & 0x1f) == SIGHASH_SINGLE)
1092     {
1093         // Only lock-in the txout payee at same index as txin
1094         unsigned int nOut = nIn;
1095         if (nOut >= txTmp.vout.size())
1096         {
1097             printf("ERROR: SignatureHash() : nOut=%d out of range\n", nOut);
1098             return 1;
1099         }
1100         txTmp.vout.resize(nOut+1);
1101         for (unsigned int i = 0; i < nOut; i++)
1102             txTmp.vout[i].SetNull();
1103
1104         // Let the others update at will
1105         for (unsigned int i = 0; i < txTmp.vin.size(); i++)
1106             if (i != nIn)
1107                 txTmp.vin[i].nSequence = 0;
1108     }
1109
1110     // Blank out other inputs completely, not recommended for open transactions
1111     if (nHashType & SIGHASH_ANYONECANPAY)
1112     {
1113         txTmp.vin[0] = txTmp.vin[nIn];
1114         txTmp.vin.resize(1);
1115     }
1116
1117     // Serialize and hash
1118     CDataStream ss(SER_GETHASH, 0);
1119     ss.reserve(10000);
1120     ss << txTmp << nHashType;
1121     return Hash(ss.begin(), ss.end());
1122 }
1123
1124
1125 // Valid signature cache, to avoid doing expensive ECDSA signature checking
1126 // twice for every transaction (once when accepted into memory pool, and
1127 // again when accepted into the block chain)
1128
1129 class CSignatureCache
1130 {
1131 private:
1132      // sigdata_type is (signature hash, signature, public key):
1133     typedef boost::tuple<uint256, std::vector<unsigned char>, CPubKey > sigdata_type;
1134     std::set< sigdata_type> setValid;
1135     boost::shared_mutex cs_sigcache;
1136
1137 public:
1138     bool
1139     Get(const uint256 &hash, const std::vector<unsigned char>& vchSig, const CPubKey& pubKey)
1140     {
1141         boost::shared_lock<boost::shared_mutex> lock(cs_sigcache);
1142
1143         sigdata_type k(hash, vchSig, pubKey);
1144         std::set<sigdata_type>::iterator mi = setValid.find(k);
1145         if (mi != setValid.end())
1146             return true;
1147         return false;
1148     }
1149
1150     void Set(const uint256 &hash, const std::vector<unsigned char>& vchSig, const CPubKey& pubKey)
1151     {
1152         // DoS prevention: limit cache size to less than 10MB
1153         // (~200 bytes per cache entry times 50,000 entries)
1154         // Since there are a maximum of 20,000 signature operations per block
1155         // 50,000 is a reasonable default.
1156         int64_t nMaxCacheSize = GetArg("-maxsigcachesize", 50000);
1157         if (nMaxCacheSize <= 0) return;
1158
1159         boost::shared_lock<boost::shared_mutex> lock(cs_sigcache);
1160
1161         while (static_cast<int64_t>(setValid.size()) > nMaxCacheSize)
1162         {
1163             // Evict a random entry. Random because that helps
1164             // foil would-be DoS attackers who might try to pre-generate
1165             // and re-use a set of valid signatures just-slightly-greater
1166             // than our cache size.
1167             uint256 randomHash = GetRandHash();
1168             std::vector<unsigned char> unused;
1169             std::set<sigdata_type>::iterator it =
1170                 setValid.lower_bound(sigdata_type(randomHash, unused, unused));
1171             if (it == setValid.end())
1172                 it = setValid.begin();
1173             setValid.erase(*it);
1174         }
1175
1176         sigdata_type k(hash, vchSig, pubKey);
1177         setValid.insert(k);
1178     }
1179 };
1180
1181 bool CheckSig(vector<unsigned char> vchSig, const vector<unsigned char> &vchPubKey, const CScript &scriptCode,
1182               const CTransaction& txTo, unsigned int nIn, int nHashType, int flags)
1183 {
1184     static CSignatureCache signatureCache;
1185
1186     CKey key;
1187     if (!key.SetPubKey(vchPubKey))
1188          return false;
1189     CPubKey pubkey = key.GetPubKey();
1190     if (!pubkey.IsValid())
1191         return false;
1192
1193     // Hash type is one byte tacked on to the end of the signature
1194     if (vchSig.empty())
1195         return false;
1196     if (nHashType == 0)
1197         nHashType = vchSig.back();
1198     else if (nHashType != vchSig.back())
1199         return false;
1200     vchSig.pop_back();
1201
1202     uint256 sighash = SignatureHash(scriptCode, txTo, nIn, nHashType);
1203
1204     if (signatureCache.Get(sighash, vchSig, pubkey))
1205         return true;
1206
1207     if (!key.Verify(sighash, vchSig))
1208         return false;
1209
1210     if (!(flags & SCRIPT_VERIFY_NOCACHE))
1211         signatureCache.Set(sighash, vchSig, pubkey);
1212
1213     return true;
1214 }
1215
1216
1217
1218
1219
1220
1221
1222
1223 //
1224 // Return public keys or hashes from scriptPubKey, for 'standard' transaction types.
1225 //
1226 bool Solver(const CScript& scriptPubKey, txnouttype& typeRet, vector<vector<unsigned char> >& vSolutionsRet)
1227 {
1228     // Templates
1229     static map<txnouttype, CScript> mTemplates;
1230     if (mTemplates.empty())
1231     {
1232         // Standard tx, sender provides pubkey, receiver adds signature
1233         mTemplates.insert(make_pair(TX_PUBKEY, CScript() << OP_PUBKEY << OP_CHECKSIG));
1234
1235         if (fTestNet || GetTime() > SMALLDATA_SWITCH_TIME)
1236         {
1237             // Malleable pubkey tx hack, sender provides generated pubkey combined with R parameter. The R parameter is dropped before checking a signature.
1238             mTemplates.insert(make_pair(TX_PUBKEY_DROP, CScript() << OP_PUBKEY << OP_PUBKEY << OP_DROP << OP_CHECKSIG));
1239         }
1240
1241         // Bitcoin address tx, sender provides hash of pubkey, receiver provides signature and pubkey
1242         mTemplates.insert(make_pair(TX_PUBKEYHASH, CScript() << OP_DUP << OP_HASH160 << OP_PUBKEYHASH << OP_EQUALVERIFY << OP_CHECKSIG));
1243
1244         // Sender provides N pubkeys, receivers provides M signatures
1245         mTemplates.insert(make_pair(TX_MULTISIG, CScript() << OP_SMALLINTEGER << OP_PUBKEYS << OP_SMALLINTEGER << OP_CHECKMULTISIG));
1246
1247         // Empty, provably prunable, data-carrying output
1248         mTemplates.insert(make_pair(TX_NULL_DATA, CScript() << OP_RETURN << OP_SMALLDATA));
1249     }
1250
1251     vSolutionsRet.clear();
1252
1253     // Shortcut for pay-to-script-hash, which are more constrained than the other types:
1254     // it is always OP_HASH160 20 [20 byte hash] OP_EQUAL
1255     if (scriptPubKey.IsPayToScriptHash())
1256     {
1257         typeRet = TX_SCRIPTHASH;
1258         vector<unsigned char> hashBytes(scriptPubKey.begin()+2, scriptPubKey.begin()+22);
1259         vSolutionsRet.push_back(hashBytes);
1260         return true;
1261     }
1262
1263     // Provably prunable, data-carrying output
1264     //
1265     // So long as script passes the IsUnspendable() test and all but the first
1266     // byte passes the IsPushOnly() test we don't care what exactly is in the
1267     // script.
1268     if (scriptPubKey.size() >= 1 && scriptPubKey[0] == OP_RETURN && scriptPubKey.IsPushOnly(scriptPubKey.begin()+1)) {
1269         typeRet = TX_NULL_DATA;
1270         return true;
1271     }
1272
1273     // Scan templates
1274     const CScript& script1 = scriptPubKey;
1275     BOOST_FOREACH(const PAIRTYPE(txnouttype, CScript)& tplate, mTemplates)
1276     {
1277         const CScript& script2 = tplate.second;
1278         vSolutionsRet.clear();
1279
1280         opcodetype opcode1, opcode2;
1281         vector<unsigned char> vch1, vch2;
1282
1283         // Compare
1284         CScript::const_iterator pc1 = script1.begin();
1285         CScript::const_iterator pc2 = script2.begin();
1286         while (true)
1287         {
1288             if (pc1 == script1.end() && pc2 == script2.end())
1289             {
1290                 // Found a match
1291                 typeRet = tplate.first;
1292                 if (typeRet == TX_MULTISIG)
1293                 {
1294                     // Additional checks for TX_MULTISIG:
1295                     unsigned char m = vSolutionsRet.front()[0];
1296                     unsigned char n = vSolutionsRet.back()[0];
1297                     if (m < 1 || n < 1 || m > n || vSolutionsRet.size()-2 != n)
1298                         return false;
1299                 }
1300                 return true;
1301             }
1302             if (!script1.GetOp(pc1, opcode1, vch1))
1303                 break;
1304             if (!script2.GetOp(pc2, opcode2, vch2))
1305                 break;
1306
1307             // Template matching opcodes:
1308             if (opcode2 == OP_PUBKEYS)
1309             {
1310                 while (vch1.size() >= 33 && vch1.size() <= 120)
1311                 {
1312                     vSolutionsRet.push_back(vch1);
1313                     if (!script1.GetOp(pc1, opcode1, vch1))
1314                         break;
1315                 }
1316                 if (!script2.GetOp(pc2, opcode2, vch2))
1317                     break;
1318                 // Normal situation is to fall through
1319                 // to other if/else statements
1320             }
1321
1322             if (opcode2 == OP_PUBKEY)
1323             {
1324                 if (vch1.size() < 33 || vch1.size() > 120)
1325                     break;
1326                 vSolutionsRet.push_back(vch1);
1327             }
1328             else if (opcode2 == OP_PUBKEYHASH)
1329             {
1330                 if (vch1.size() != sizeof(uint160))
1331                     break;
1332                 vSolutionsRet.push_back(vch1);
1333             }
1334             else if (opcode2 == OP_SMALLINTEGER)
1335             {   // Single-byte small integer pushed onto vSolutions
1336                 if (opcode1 == OP_0 ||
1337                     (opcode1 >= OP_1 && opcode1 <= OP_16))
1338                 {
1339                     char n = (char)CScript::DecodeOP_N(opcode1);
1340                     vSolutionsRet.push_back(valtype(1, n));
1341                 }
1342                 else
1343                     break;
1344             }
1345             else if (opcode2 == OP_INTEGER)
1346             {   // Up to four-byte integer pushed onto vSolutions
1347                 try
1348                 {
1349                     CBigNum bnVal = CastToBigNum(vch1);
1350                     if (bnVal <= 16)
1351                         break; // It's better to use OP_0 ... OP_16 for small integers.
1352                     vSolutionsRet.push_back(vch1);
1353                 }
1354                 catch(...)
1355                 {
1356                     break;
1357                 }
1358             }
1359             else if (opcode2 == OP_SMALLDATA)
1360             {
1361                 // small pushdata, <= 1024 bytes
1362                 if (vch1.size() > (GetTime() > SMALLDATA_SWITCH_TIME ? 1024 : 80))
1363                     break;
1364             }
1365             else if (opcode1 != opcode2 || vch1 != vch2)
1366             {
1367                 // Others must match exactly
1368                 break;
1369             }
1370         }
1371     }
1372
1373     vSolutionsRet.clear();
1374     typeRet = TX_NONSTANDARD;
1375     return false;
1376 }
1377
1378
1379 bool Sign1(const CKeyID& address, const CKeyStore& keystore, const uint256& hash, int nHashType, CScript& scriptSigRet)
1380 {
1381     CKey key;
1382     if (!keystore.GetKey(address, key))
1383         return false;
1384
1385     vector<unsigned char> vchSig;
1386     if (!key.Sign(hash, vchSig))
1387         return false;
1388     vchSig.push_back((unsigned char)nHashType);
1389     scriptSigRet << vchSig;
1390
1391     return true;
1392 }
1393
1394 bool SignR(const CPubKey& pubKey, const CPubKey& R, const CKeyStore& keystore, const uint256& hash, int nHashType, CScript& scriptSigRet)
1395 {
1396     CKey key;
1397     if (!keystore.CreatePrivKey(pubKey, R, key))
1398         return false;
1399
1400     vector<unsigned char> vchSig;
1401     if (!key.Sign(hash, vchSig))
1402         return false;
1403     vchSig.push_back((unsigned char)nHashType);
1404     scriptSigRet << vchSig;
1405
1406     return true;
1407 }
1408
1409 bool SignN(const vector<valtype>& multisigdata, const CKeyStore& keystore, const uint256& hash, int nHashType, CScript& scriptSigRet)
1410 {
1411     int nSigned = 0;
1412     int nRequired = multisigdata.front()[0];
1413     for (unsigned int i = 1; i < multisigdata.size()-1 && nSigned < nRequired; i++)
1414     {
1415         const valtype& pubkey = multisigdata[i];
1416         CKeyID keyID = CPubKey(pubkey).GetID();
1417         if (Sign1(keyID, keystore, hash, nHashType, scriptSigRet))
1418             ++nSigned;
1419     }
1420     return nSigned==nRequired;
1421 }
1422
1423 //
1424 // Sign scriptPubKey with private keys stored in keystore, given transaction hash and hash type.
1425 // Signatures are returned in scriptSigRet (or returns false if scriptPubKey can't be signed),
1426 // unless whichTypeRet is TX_SCRIPTHASH, in which case scriptSigRet is the redemption script.
1427 // Returns false if scriptPubKey could not be completely satisfied.
1428 //
1429 bool Solver(const CKeyStore& keystore, const CScript& scriptPubKey, const uint256& hash, int nHashType,
1430                   CScript& scriptSigRet, txnouttype& whichTypeRet)
1431 {
1432     scriptSigRet.clear();
1433
1434     vector<valtype> vSolutions;
1435     if (!Solver(scriptPubKey, whichTypeRet, vSolutions))
1436         return false;
1437
1438     CKeyID keyID;
1439     switch (whichTypeRet)
1440     {
1441     case TX_NONSTANDARD:
1442     case TX_NULL_DATA:
1443         return false;
1444     case TX_PUBKEY:
1445         keyID = CPubKey(vSolutions[0]).GetID();
1446         return Sign1(keyID, keystore, hash, nHashType, scriptSigRet);
1447     case TX_PUBKEY_DROP:
1448         {
1449             CPubKey key = CPubKey(vSolutions[0]);
1450             CPubKey R = CPubKey(vSolutions[1]);
1451             return SignR(key, R, keystore, hash, nHashType, scriptSigRet);
1452         }
1453     case TX_PUBKEYHASH:
1454         keyID = CKeyID(uint160(vSolutions[0]));
1455         if (!Sign1(keyID, keystore, hash, nHashType, scriptSigRet))
1456             return false;
1457         else
1458         {
1459             CPubKey vch;
1460             keystore.GetPubKey(keyID, vch);
1461             scriptSigRet << vch;
1462         }
1463         return true;
1464     case TX_SCRIPTHASH:
1465         return keystore.GetCScript(uint160(vSolutions[0]), scriptSigRet);
1466
1467     case TX_MULTISIG:
1468         scriptSigRet << OP_0; // workaround CHECKMULTISIG bug
1469         return (SignN(vSolutions, keystore, hash, nHashType, scriptSigRet));
1470     }
1471     return false;
1472 }
1473
1474 int ScriptSigArgsExpected(txnouttype t, const std::vector<std::vector<unsigned char> >& vSolutions)
1475 {
1476     switch (t)
1477     {
1478     case TX_NONSTANDARD:
1479         return -1;
1480     case TX_NULL_DATA:
1481         return 1;
1482     case TX_PUBKEY:
1483     case TX_PUBKEY_DROP:
1484         return 1;
1485     case TX_PUBKEYHASH:
1486         return 2;
1487     case TX_MULTISIG:
1488         if (vSolutions.size() < 1 || vSolutions[0].size() < 1)
1489             return -1;
1490         return vSolutions[0][0] + 1;
1491     case TX_SCRIPTHASH:
1492         return 1; // doesn't include args needed by the script
1493     }
1494     return -1;
1495 }
1496
1497 bool IsStandard(const CScript& scriptPubKey, txnouttype& whichType)
1498 {
1499     vector<valtype> vSolutions;
1500     if (!Solver(scriptPubKey, whichType, vSolutions))
1501         return false;
1502
1503     if (whichType == TX_MULTISIG)
1504     {
1505         unsigned char m = vSolutions.front()[0];
1506         unsigned char n = vSolutions.back()[0];
1507         // Support up to x-of-3 multisig txns as standard
1508         if (n < 1 || n > 3)
1509             return false;
1510         if (m < 1 || m > n)
1511             return false;
1512     }
1513
1514     return whichType != TX_NONSTANDARD;
1515 }
1516
1517
1518 unsigned int HaveKeys(const vector<valtype>& pubkeys, const CKeyStore& keystore)
1519 {
1520     unsigned int nResult = 0;
1521     BOOST_FOREACH(const valtype& pubkey, pubkeys)
1522     {
1523         CKeyID keyID = CPubKey(pubkey).GetID();
1524         if (keystore.HaveKey(keyID))
1525             ++nResult;
1526     }
1527     return nResult;
1528 }
1529
1530
1531 class CKeyStoreIsMineVisitor : public boost::static_visitor<bool>
1532 {
1533 private:
1534     const CKeyStore *keystore;
1535 public:
1536     CKeyStoreIsMineVisitor(const CKeyStore *keystoreIn) : keystore(keystoreIn) { }
1537     bool operator()(const CNoDestination &dest) const { return false; }
1538     bool operator()(const CKeyID &keyID) const { return keystore->HaveKey(keyID); }
1539     bool operator()(const CScriptID &scriptID) const { return keystore->HaveCScript(scriptID); }
1540 };
1541
1542 isminetype IsMine(const CKeyStore &keystore, const CTxDestination& dest)
1543 {
1544     CScript script;
1545     script.SetDestination(dest);
1546     return IsMine(keystore, script);
1547 }
1548
1549 isminetype IsMine(const CKeyStore &keystore, const CScript& scriptPubKey)
1550 {
1551     vector<valtype> vSolutions;
1552     txnouttype whichType;
1553     if (!Solver(scriptPubKey, whichType, vSolutions)) {
1554         if (keystore.HaveWatchOnly(scriptPubKey))
1555             return MINE_WATCH_ONLY;
1556         return MINE_NO;
1557     }
1558
1559     CKeyID keyID;
1560     switch (whichType)
1561     {
1562     case TX_NONSTANDARD:
1563     case TX_NULL_DATA:
1564         break;
1565     case TX_PUBKEY:
1566         keyID = CPubKey(vSolutions[0]).GetID();
1567         if (keystore.HaveKey(keyID))
1568             return MINE_SPENDABLE;
1569         break;
1570     case TX_PUBKEY_DROP:
1571         {
1572             CPubKey key = CPubKey(vSolutions[0]);
1573             CPubKey R = CPubKey(vSolutions[1]);
1574             if (keystore.CheckOwnership(key, R))
1575                 return MINE_SPENDABLE;
1576         }
1577         break;
1578     case TX_PUBKEYHASH:
1579         keyID = CKeyID(uint160(vSolutions[0]));
1580         if (keystore.HaveKey(keyID))
1581             return MINE_SPENDABLE;
1582         break;
1583     case TX_SCRIPTHASH:
1584     {
1585         CScriptID scriptID = CScriptID(uint160(vSolutions[0]));
1586         CScript subscript;
1587         if (keystore.GetCScript(scriptID, subscript)) {
1588             isminetype ret = IsMine(keystore, subscript);
1589             if (ret == MINE_SPENDABLE)
1590                 return ret;
1591         }
1592         break;
1593     }
1594     case TX_MULTISIG:
1595     {
1596         // Only consider transactions "mine" if we own ALL the
1597         // keys involved. multi-signature transactions that are
1598         // partially owned (somebody else has a key that can spend
1599         // them) enable spend-out-from-under-you attacks, especially
1600         // in shared-wallet situations.
1601         vector<valtype> keys(vSolutions.begin()+1, vSolutions.begin()+vSolutions.size()-1);
1602         if (HaveKeys(keys, keystore) == keys.size())
1603             return MINE_SPENDABLE;
1604         break;
1605     }
1606     }
1607
1608     if (keystore.HaveWatchOnly(scriptPubKey))
1609         return MINE_WATCH_ONLY;
1610     return MINE_NO;
1611 }
1612
1613 bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
1614 {
1615     vector<valtype> vSolutions;
1616     txnouttype whichType;
1617     if (!Solver(scriptPubKey, whichType, vSolutions))
1618         return false;
1619
1620     if (whichType == TX_PUBKEY)
1621     {
1622         addressRet = CPubKey(vSolutions[0]).GetID();
1623         return true;
1624     }
1625     else if (whichType == TX_PUBKEYHASH)
1626     {
1627         addressRet = CKeyID(uint160(vSolutions[0]));
1628         return true;
1629     }
1630     else if (whichType == TX_SCRIPTHASH)
1631     {
1632         addressRet = CScriptID(uint160(vSolutions[0]));
1633         return true;
1634     }
1635     // Multisig txns have more than one address...
1636     return false;
1637 }
1638
1639 class CAffectedKeysVisitor : public boost::static_visitor<void> {
1640 private:
1641     const CKeyStore &keystore;
1642     CAffectedKeysVisitor& operator=(CAffectedKeysVisitor const&);
1643     std::vector<CKeyID> &vKeys;
1644
1645 public:
1646     CAffectedKeysVisitor(const CKeyStore &keystoreIn, std::vector<CKeyID> &vKeysIn) : keystore(keystoreIn), vKeys(vKeysIn) {}
1647
1648     void Process(const CScript &script) {
1649         txnouttype type;
1650         std::vector<CTxDestination> vDest;
1651         int nRequired;
1652         if (ExtractDestinations(script, type, vDest, nRequired)) {
1653             BOOST_FOREACH(const CTxDestination &dest, vDest)
1654                 boost::apply_visitor(*this, dest);
1655         }
1656     }
1657
1658     void operator()(const CKeyID &keyId) {
1659         if (keystore.HaveKey(keyId))
1660             vKeys.push_back(keyId);
1661     }
1662
1663     void operator()(const CScriptID &scriptId) {
1664         CScript script;
1665         if (keystore.GetCScript(scriptId, script))
1666             Process(script);
1667     }
1668
1669     void operator()(const CNoDestination &none) {}
1670 };
1671
1672
1673 void ExtractAffectedKeys(const CKeyStore &keystore, const CScript& scriptPubKey, std::vector<CKeyID> &vKeys) {
1674     CAffectedKeysVisitor(keystore, vKeys).Process(scriptPubKey);
1675 }
1676
1677 bool ExtractDestinations(const CScript& scriptPubKey, txnouttype& typeRet, vector<CTxDestination>& addressRet, int& nRequiredRet)
1678 {
1679     addressRet.clear();
1680     typeRet = TX_NONSTANDARD;
1681     vector<valtype> vSolutions;
1682     if (!Solver(scriptPubKey, typeRet, vSolutions))
1683         return false;
1684     if (typeRet == TX_NULL_DATA)
1685     {
1686         nRequiredRet = 0;
1687         return true;
1688     }
1689
1690     if (typeRet == TX_MULTISIG)
1691     {
1692         nRequiredRet = vSolutions.front()[0];
1693         for (unsigned int i = 1; i < vSolutions.size()-1; i++)
1694         {
1695             CTxDestination address = CPubKey(vSolutions[i]).GetID();
1696             addressRet.push_back(address);
1697         }
1698     }
1699     else
1700     {
1701         nRequiredRet = 1;
1702         if (typeRet == TX_PUBKEY_DROP)
1703             return true;
1704         CTxDestination address;
1705         if (!ExtractDestination(scriptPubKey, address))
1706            return false;
1707         addressRet.push_back(address);
1708     }
1709
1710     return true;
1711 }
1712
1713 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn,
1714                   unsigned int flags, int nHashType)
1715 {
1716     vector<vector<unsigned char> > stack, stackCopy;
1717     if (!EvalScript(stack, scriptSig, txTo, nIn, flags, nHashType))
1718         return false;
1719     if (flags & SCRIPT_VERIFY_P2SH)
1720         stackCopy = stack;
1721     if (!EvalScript(stack, scriptPubKey, txTo, nIn, flags, nHashType))
1722         return false;
1723     if (stack.empty())
1724         return false;
1725
1726     if (CastToBool(stack.back()) == false)
1727         return false;
1728
1729     // Additional validation for spend-to-script-hash transactions:
1730     if ((flags & SCRIPT_VERIFY_P2SH) && scriptPubKey.IsPayToScriptHash())
1731     {
1732         if (!scriptSig.IsPushOnly()) // scriptSig must be literals-only
1733             return false;            // or validation fails
1734
1735         // stackCopy cannot be empty here, because if it was the
1736         // P2SH  HASH <> EQUAL  scriptPubKey would be evaluated with
1737         // an empty stack and the EvalScript above would return false.
1738         assert(!stackCopy.empty());
1739
1740         const valtype& pubKeySerialized = stackCopy.back();
1741         CScript pubKey2(pubKeySerialized.begin(), pubKeySerialized.end());
1742         popstack(stackCopy);
1743
1744         if (!EvalScript(stackCopy, pubKey2, txTo, nIn, flags, nHashType))
1745             return false;
1746         if (stackCopy.empty())
1747             return false;
1748         return CastToBool(stackCopy.back());
1749     }
1750
1751     return true;
1752 }
1753
1754 bool SignSignature(const CKeyStore &keystore, const CScript& fromPubKey, CTransaction& txTo, unsigned int nIn, int nHashType)
1755 {
1756     assert(nIn < txTo.vin.size());
1757     CTxIn& txin = txTo.vin[nIn];
1758
1759     // Leave out the signature from the hash, since a signature can't sign itself.
1760     // The checksig op will also drop the signatures from its hash.
1761     uint256 hash = SignatureHash(fromPubKey, txTo, nIn, nHashType);
1762
1763     txnouttype whichType;
1764     if (!Solver(keystore, fromPubKey, hash, nHashType, txin.scriptSig, whichType))
1765         return false;
1766
1767     if (whichType == TX_SCRIPTHASH)
1768     {
1769         // Solver returns the subscript that need to be evaluated;
1770         // the final scriptSig is the signatures from that
1771         // and then the serialized subscript:
1772         CScript subscript = txin.scriptSig;
1773
1774         // Recompute txn hash using subscript in place of scriptPubKey:
1775         uint256 hash2 = SignatureHash(subscript, txTo, nIn, nHashType);
1776
1777         txnouttype subType;
1778         bool fSolved =
1779             Solver(keystore, subscript, hash2, nHashType, txin.scriptSig, subType) && subType != TX_SCRIPTHASH;
1780         // Append serialized subscript whether or not it is completely signed:
1781         txin.scriptSig << static_cast<valtype>(subscript);
1782         if (!fSolved) return false;
1783     }
1784
1785     // Test solution
1786     return VerifyScript(txin.scriptSig, fromPubKey, txTo, nIn, STRICT_FLAGS, 0);
1787 }
1788
1789 bool SignSignature(const CKeyStore &keystore, const CTransaction& txFrom, CTransaction& txTo, unsigned int nIn, int nHashType)
1790 {
1791     assert(nIn < txTo.vin.size());
1792     CTxIn& txin = txTo.vin[nIn];
1793     assert(txin.prevout.n < txFrom.vout.size());
1794     assert(txin.prevout.hash == txFrom.GetHash());
1795     const CTxOut& txout = txFrom.vout[txin.prevout.n];
1796
1797     return SignSignature(keystore, txout.scriptPubKey, txTo, nIn, nHashType);
1798 }
1799
1800 static CScript PushAll(const vector<valtype>& values)
1801 {
1802     CScript result;
1803     BOOST_FOREACH(const valtype& v, values)
1804         result << v;
1805     return result;
1806 }
1807
1808 static CScript CombineMultisig(const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn,
1809                                const vector<valtype>& vSolutions,
1810                                vector<valtype>& sigs1, vector<valtype>& sigs2)
1811 {
1812     // Combine all the signatures we've got:
1813     set<valtype> allsigs;
1814     BOOST_FOREACH(const valtype& v, sigs1)
1815     {
1816         if (!v.empty())
1817             allsigs.insert(v);
1818     }
1819     BOOST_FOREACH(const valtype& v, sigs2)
1820     {
1821         if (!v.empty())
1822             allsigs.insert(v);
1823     }
1824
1825     // Build a map of pubkey -> signature by matching sigs to pubkeys:
1826     assert(vSolutions.size() > 1);
1827     unsigned int nSigsRequired = vSolutions.front()[0];
1828     unsigned int nPubKeys = (unsigned int)(vSolutions.size()-2);
1829     map<valtype, valtype> sigs;
1830     BOOST_FOREACH(const valtype& sig, allsigs)
1831     {
1832         for (unsigned int i = 0; i < nPubKeys; i++)
1833         {
1834             const valtype& pubkey = vSolutions[i+1];
1835             if (sigs.count(pubkey))
1836                 continue; // Already got a sig for this pubkey
1837
1838             if (CheckSig(sig, pubkey, scriptPubKey, txTo, nIn, 0, 0))
1839             {
1840                 sigs[pubkey] = sig;
1841                 break;
1842             }
1843         }
1844     }
1845     // Now build a merged CScript:
1846     unsigned int nSigsHave = 0;
1847     CScript result; result << OP_0; // pop-one-too-many workaround
1848     for (unsigned int i = 0; i < nPubKeys && nSigsHave < nSigsRequired; i++)
1849     {
1850         if (sigs.count(vSolutions[i+1]))
1851         {
1852             result << sigs[vSolutions[i+1]];
1853             ++nSigsHave;
1854         }
1855     }
1856     // Fill any missing with OP_0:
1857     for (unsigned int i = nSigsHave; i < nSigsRequired; i++)
1858         result << OP_0;
1859
1860     return result;
1861 }
1862
1863 static CScript CombineSignatures(const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn,
1864                                  const txnouttype txType, const vector<valtype>& vSolutions,
1865                                  vector<valtype>& sigs1, vector<valtype>& sigs2)
1866 {
1867     switch (txType)
1868     {
1869     case TX_NONSTANDARD:
1870     case TX_NULL_DATA:
1871         // Don't know anything about this, assume bigger one is correct:
1872         if (sigs1.size() >= sigs2.size())
1873             return PushAll(sigs1);
1874         return PushAll(sigs2);
1875     case TX_PUBKEY:
1876     case TX_PUBKEY_DROP:
1877     case TX_PUBKEYHASH:
1878         // Signatures are bigger than placeholders or empty scripts:
1879         if (sigs1.empty() || sigs1[0].empty())
1880             return PushAll(sigs2);
1881         return PushAll(sigs1);
1882     case TX_SCRIPTHASH:
1883         if (sigs1.empty() || sigs1.back().empty())
1884             return PushAll(sigs2);
1885         else if (sigs2.empty() || sigs2.back().empty())
1886             return PushAll(sigs1);
1887         else
1888         {
1889             // Recur to combine:
1890             valtype spk = sigs1.back();
1891             CScript pubKey2(spk.begin(), spk.end());
1892
1893             txnouttype txType2;
1894             vector<vector<unsigned char> > vSolutions2;
1895             Solver(pubKey2, txType2, vSolutions2);
1896             sigs1.pop_back();
1897             sigs2.pop_back();
1898             CScript result = CombineSignatures(pubKey2, txTo, nIn, txType2, vSolutions2, sigs1, sigs2);
1899             result << spk;
1900             return result;
1901         }
1902     case TX_MULTISIG:
1903         return CombineMultisig(scriptPubKey, txTo, nIn, vSolutions, sigs1, sigs2);
1904     }
1905
1906     return CScript();
1907 }
1908
1909 CScript CombineSignatures(const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn,
1910                           const CScript& scriptSig1, const CScript& scriptSig2)
1911 {
1912     txnouttype txType;
1913     vector<vector<unsigned char> > vSolutions;
1914     Solver(scriptPubKey, txType, vSolutions);
1915
1916     vector<valtype> stack1;
1917     EvalScript(stack1, scriptSig1, CTransaction(), 0, SCRIPT_VERIFY_STRICTENC, 0);
1918     vector<valtype> stack2;
1919     EvalScript(stack2, scriptSig2, CTransaction(), 0, SCRIPT_VERIFY_STRICTENC, 0);
1920
1921     return CombineSignatures(scriptPubKey, txTo, nIn, txType, vSolutions, stack1, stack2);
1922 }
1923
1924 unsigned int CScript::GetSigOpCount(bool fAccurate) const
1925 {
1926     unsigned int n = 0;
1927     const_iterator pc = begin();
1928     opcodetype lastOpcode = OP_INVALIDOPCODE;
1929     while (pc < end())
1930     {
1931         opcodetype opcode;
1932         if (!GetOp(pc, opcode))
1933             break;
1934         if (opcode == OP_CHECKSIG || opcode == OP_CHECKSIGVERIFY)
1935             n++;
1936         else if (opcode == OP_CHECKMULTISIG || opcode == OP_CHECKMULTISIGVERIFY)
1937         {
1938             if (fAccurate && lastOpcode >= OP_1 && lastOpcode <= OP_16)
1939                 n += DecodeOP_N(lastOpcode);
1940             else
1941                 n += 20;
1942         }
1943         lastOpcode = opcode;
1944     }
1945     return n;
1946 }
1947
1948 unsigned int CScript::GetSigOpCount(const CScript& scriptSig) const
1949 {
1950     if (!IsPayToScriptHash())
1951         return GetSigOpCount(true);
1952
1953     // This is a pay-to-script-hash scriptPubKey;
1954     // get the last item that the scriptSig
1955     // pushes onto the stack:
1956     const_iterator pc = scriptSig.begin();
1957     vector<unsigned char> data;
1958     while (pc < scriptSig.end())
1959     {
1960         opcodetype opcode;
1961         if (!scriptSig.GetOp(pc, opcode, data))
1962             return 0;
1963         if (opcode > OP_16)
1964             return 0;
1965     }
1966
1967     /// ... and return its opcount:
1968     CScript subscript(data.begin(), data.end());
1969     return subscript.GetSigOpCount(true);
1970 }
1971
1972 bool CScript::IsPayToScriptHash() const
1973 {
1974     // Extra-fast test for pay-to-script-hash CScripts:
1975     return (this->size() == 23 &&
1976             this->at(0) == OP_HASH160 &&
1977             this->at(1) == 0x14 &&
1978             this->at(22) == OP_EQUAL);
1979 }
1980
1981 bool CScript::HasCanonicalPushes() const
1982 {
1983     const_iterator pc = begin();
1984     while (pc < end())
1985     {
1986         opcodetype opcode;
1987         std::vector<unsigned char> data;
1988         if (!GetOp(pc, opcode, data))
1989             return false;
1990         if (opcode > OP_16)
1991             continue;
1992         if (opcode < OP_PUSHDATA1 && opcode > OP_0 && (data.size() == 1 && data[0] <= 16))
1993             // Could have used an OP_n code, rather than a 1-byte push.
1994             return false;
1995         if (opcode == OP_PUSHDATA1 && data.size() < OP_PUSHDATA1)
1996             // Could have used a normal n-byte push, rather than OP_PUSHDATA1.
1997             return false;
1998         if (opcode == OP_PUSHDATA2 && data.size() <= 0xFF)
1999             // Could have used an OP_PUSHDATA1.
2000             return false;
2001         if (opcode == OP_PUSHDATA4 && data.size() <= 0xFFFF)
2002             // Could have used an OP_PUSHDATA2.
2003             return false;
2004     }
2005     return true;
2006 }
2007
2008 class CScriptVisitor : public boost::static_visitor<bool>
2009 {
2010 private:
2011     CScript *script;
2012 public:
2013     CScriptVisitor(CScript *scriptin) { script = scriptin; }
2014
2015     bool operator()(const CNoDestination &dest) const {
2016         script->clear();
2017         return false;
2018     }
2019
2020     bool operator()(const CKeyID &keyID) const {
2021         script->clear();
2022         *script << OP_DUP << OP_HASH160 << keyID << OP_EQUALVERIFY << OP_CHECKSIG;
2023         return true;
2024     }
2025
2026     bool operator()(const CScriptID &scriptID) const {
2027         script->clear();
2028         *script << OP_HASH160 << scriptID << OP_EQUAL;
2029         return true;
2030     }
2031 };
2032
2033 void CScript::SetDestination(const CTxDestination& dest)
2034 {
2035     boost::apply_visitor(CScriptVisitor(this), dest);
2036 }
2037
2038 void CScript::SetDestination(const CPubKey& R, CPubKey& pubKeyVariant)
2039 {
2040     this->clear();
2041     *this << pubKeyVariant << R << OP_DROP << OP_CHECKSIG;
2042 }
2043
2044
2045 void CScript::SetMultisig(int nRequired, const std::vector<CKey>& keys)
2046 {
2047     this->clear();
2048
2049     *this << EncodeOP_N(nRequired);
2050     BOOST_FOREACH(const CKey& key, keys)
2051         *this << key.GetPubKey();
2052     *this << EncodeOP_N((int)(keys.size())) << OP_CHECKMULTISIG;
2053 }