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     case OP_CHECKSEQUENCEVERIFY    : return "OP_CHECKSEQUENCEVERIFY";
 153
 154     // stack ops
 155     case OP_TOALTSTACK             : return "OP_TOALTSTACK";
 156     case OP_FROMALTSTACK           : return "OP_FROMALTSTACK";
 157     case OP_2DROP                  : return "OP_2DROP";
 158     case OP_2DUP                   : return "OP_2DUP";
 159     case OP_3DUP                   : return "OP_3DUP";
 160     case OP_2OVER                  : return "OP_2OVER";
 161     case OP_2ROT                   : return "OP_2ROT";
 162     case OP_2SWAP                  : return "OP_2SWAP";
 163     case OP_IFDUP                  : return "OP_IFDUP";
 164     case OP_DEPTH                  : return "OP_DEPTH";
 165     case OP_DROP                   : return "OP_DROP";
 166     case OP_DUP                    : return "OP_DUP";
 167     case OP_NIP                    : return "OP_NIP";
 168     case OP_OVER                   : return "OP_OVER";
 169     case OP_PICK                   : return "OP_PICK";
 170     case OP_ROLL                   : return "OP_ROLL";
 171     case OP_ROT                    : return "OP_ROT";
 172     case OP_SWAP                   : return "OP_SWAP";
 173     case OP_TUCK                   : return "OP_TUCK";
 174
 175     // splice ops
 176     case OP_CAT                    : return "OP_CAT";
 177     case OP_SUBSTR                 : return "OP_SUBSTR";
 178     case OP_LEFT                   : return "OP_LEFT";
 179     case OP_RIGHT                  : return "OP_RIGHT";
 180     case OP_SIZE                   : return "OP_SIZE";
 181
 182     // bit logic
 183     case OP_INVERT                 : return "OP_INVERT";
 184     case OP_AND                    : return "OP_AND";
 185     case OP_OR                     : return "OP_OR";
 186     case OP_XOR                    : return "OP_XOR";
 187     case OP_EQUAL                  : return "OP_EQUAL";
 188     case OP_EQUALVERIFY            : return "OP_EQUALVERIFY";
 189     case OP_RESERVED1              : return "OP_RESERVED1";
 190     case OP_RESERVED2              : return "OP_RESERVED2";
 191
 192     // numeric
 193     case OP_1ADD                   : return "OP_1ADD";
 194     case OP_1SUB                   : return "OP_1SUB";
 195     case OP_2MUL                   : return "OP_2MUL";
 196     case OP_2DIV                   : return "OP_2DIV";
 197     case OP_NEGATE                 : return "OP_NEGATE";
 198     case OP_ABS                    : return "OP_ABS";
 199     case OP_NOT                    : return "OP_NOT";
 200     case OP_0NOTEQUAL              : return "OP_0NOTEQUAL";
 201     case OP_ADD                    : return "OP_ADD";
 202     case OP_SUB                    : return "OP_SUB";
 203     case OP_MUL                    : return "OP_MUL";
 204     case OP_DIV                    : return "OP_DIV";
 205     case OP_MOD                    : return "OP_MOD";
 206     case OP_LSHIFT                 : return "OP_LSHIFT";
 207     case OP_RSHIFT                 : return "OP_RSHIFT";
 208     case OP_BOOLAND                : return "OP_BOOLAND";
 209     case OP_BOOLOR                 : return "OP_BOOLOR";
 210     case OP_NUMEQUAL               : return "OP_NUMEQUAL";
 211     case OP_NUMEQUALVERIFY         : return "OP_NUMEQUALVERIFY";
 212     case OP_NUMNOTEQUAL            : return "OP_NUMNOTEQUAL";
 213     case OP_LESSTHAN               : return "OP_LESSTHAN";
 214     case OP_GREATERTHAN            : return "OP_GREATERTHAN";
 215     case OP_LESSTHANOREQUAL        : return "OP_LESSTHANOREQUAL";
 216     case OP_GREATERTHANOREQUAL     : return "OP_GREATERTHANOREQUAL";
 217     case OP_MIN                    : return "OP_MIN";
 218     case OP_MAX                    : return "OP_MAX";
 219     case OP_WITHIN                 : return "OP_WITHIN";
 220
 221     // crypto
 222     case OP_RIPEMD160              : return "OP_RIPEMD160";
 223     case OP_SHA1                   : return "OP_SHA1";
 224     case OP_SHA256                 : return "OP_SHA256";
 225     case OP_HASH160                : return "OP_HASH160";
 226     case OP_HASH256                : return "OP_HASH256";
 227     case OP_CODESEPARATOR          : return "OP_CODESEPARATOR";
 228     case OP_CHECKSIG               : return "OP_CHECKSIG";
 229     case OP_CHECKSIGVERIFY         : return "OP_CHECKSIGVERIFY";
 230     case OP_CHECKMULTISIG          : return "OP_CHECKMULTISIG";
 231     case OP_CHECKMULTISIGVERIFY    : return "OP_CHECKMULTISIGVERIFY";
 232
 233     // expanson
 234     case OP_NOP1                   : return "OP_NOP1";
 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_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                 case OP_CHECKSEQUENCEVERIFY:
 523                 {
 524                     if (!(flags & SCRIPT_VERIFY_CHECKSEQUENCEVERIFY))
 525                         // treat as a NOP if not enabled
 526                         break;
 527                     if (stack.size() < 1)
 528                         return false;
 529                     const CBigNum nInvSequence = CastToBigNum(stacktop(-1));
 530
 531                     // In the rare event that the argument may be < 0 due to
 532                     // some arithmetic being done first, you can always use
 533                     // 0 MAX CHECKSEQUENCEVERIFY.
 534                     if (nInvSequence < 0)
 535                         return false; // negative nSequence is senseless
 536
 537                     // Relative lock times are supported by comparing the passed
 538                     // in lock time to the sequence number of the input. All other
 539                     // logic is the same, all that differs is what we are comparing
 540                     // the lock time to.
 541                     int64_t txToLockTime = (int64_t)~txTo.vin[nIn].nSequence;
 542                     if (txToLockTime >= SEQUENCE_THRESHOLD)
 543                         return false;
 544
 545                     if (!(
 546                         (txToLockTime <  SEQUENCE_THRESHOLD && nInvSequence <  SEQUENCE_THRESHOLD) ||
 547                         (txToLockTime >= SEQUENCE_THRESHOLD && nInvSequence >= SEQUENCE_THRESHOLD)
 548                     ))
 549                         return false;
 550
 551                     // Now that we know we're comparing apples-to-apples, the
 552                     // comparison is a simple numeric one.
 553                     if (nInvSequence > txToLockTime)
 554                         return false;
 555
 556                     break;
 557                 }
 558
 559                 //
 560                 // Stack ops
 561                 //
 562                 case OP_TOALTSTACK:
 563                 {
 564                     if (stack.size() < 1)
 565                         return false;
 566                     altstack.push_back(stacktop(-1));
 567                     popstack(stack);
 568                 }
 569                 break;
 570
 571                 case OP_FROMALTSTACK:
 572                 {
 573                     if (altstack.size() < 1)
 574                         return false;
 575                     stack.push_back(altstacktop(-1));
 576                     popstack(altstack);
 577                 }
 578                 break;
 579
 580                 case OP_2DROP:
 581                 {
 582                     // (x1 x2 -- )
 583                     if (stack.size() < 2)
 584                         return false;
 585                     popstack(stack);
 586                     popstack(stack);
 587                 }
 588                 break;
 589
 590                 case OP_2DUP:
 591                 {
 592                     // (x1 x2 -- x1 x2 x1 x2)
 593                     if (stack.size() < 2)
 594                         return false;
 595                     valtype vch1 = stacktop(-2);
 596                     valtype vch2 = stacktop(-1);
 597                     stack.push_back(vch1);
 598                     stack.push_back(vch2);
 599                 }
 600                 break;
 601
 602                 case OP_3DUP:
 603                 {
 604                     // (x1 x2 x3 -- x1 x2 x3 x1 x2 x3)
 605                     if (stack.size() < 3)
 606                         return false;
 607                     valtype vch1 = stacktop(-3);
 608                     valtype vch2 = stacktop(-2);
 609                     valtype vch3 = stacktop(-1);
 610                     stack.push_back(vch1);
 611                     stack.push_back(vch2);
 612                     stack.push_back(vch3);
 613                 }
 614                 break;
 615
 616                 case OP_2OVER:
 617                 {
 618                     // (x1 x2 x3 x4 -- x1 x2 x3 x4 x1 x2)
 619                     if (stack.size() < 4)
 620                         return false;
 621                     valtype vch1 = stacktop(-4);
 622                     valtype vch2 = stacktop(-3);
 623                     stack.push_back(vch1);
 624                     stack.push_back(vch2);
 625                 }
 626                 break;
 627
 628                 case OP_2ROT:
 629                 {
 630                     // (x1 x2 x3 x4 x5 x6 -- x3 x4 x5 x6 x1 x2)
 631                     if (stack.size() < 6)
 632                         return false;
 633                     valtype vch1 = stacktop(-6);
 634                     valtype vch2 = stacktop(-5);
 635                     stack.erase(stack.end()-6, stack.end()-4);
 636                     stack.push_back(vch1);
 637                     stack.push_back(vch2);
 638                 }
 639                 break;
 640
 641                 case OP_2SWAP:
 642                 {
 643                     // (x1 x2 x3 x4 -- x3 x4 x1 x2)
 644                     if (stack.size() < 4)
 645                         return false;
 646                     swap(stacktop(-4), stacktop(-2));
 647                     swap(stacktop(-3), stacktop(-1));
 648                 }
 649                 break;
 650
 651                 case OP_IFDUP:
 652                 {
 653                     // (x - 0 | x x)
 654                     if (stack.size() < 1)
 655                         return false;
 656                     valtype vch = stacktop(-1);
 657                     if (CastToBool(vch))
 658                         stack.push_back(vch);
 659                 }
 660                 break;
 661
 662                 case OP_DEPTH:
 663                 {
 664                     // -- stacksize
 665                     CBigNum bn((uint16_t) stack.size());
 666                     stack.push_back(bn.getvch());
 667                 }
 668                 break;
 669
 670                 case OP_DROP:
 671                 {
 672                     // (x -- )
 673                     if (stack.size() < 1)
 674                         return false;
 675                     popstack(stack);
 676                 }
 677                 break;
 678
 679                 case OP_DUP:
 680                 {
 681                     // (x -- x x)
 682                     if (stack.size() < 1)
 683                         return false;
 684                     valtype vch = stacktop(-1);
 685                     stack.push_back(vch);
 686                 }
 687                 break;
 688
 689                 case OP_NIP:
 690                 {
 691                     // (x1 x2 -- x2)
 692                     if (stack.size() < 2)
 693                         return false;
 694                     stack.erase(stack.end() - 2);
 695                 }
 696                 break;
 697
 698                 case OP_OVER:
 699                 {
 700                     // (x1 x2 -- x1 x2 x1)
 701                     if (stack.size() < 2)
 702                         return false;
 703                     valtype vch = stacktop(-2);
 704                     stack.push_back(vch);
 705                 }
 706                 break;
 707
 708                 case OP_PICK:
 709                 case OP_ROLL:
 710                 {
 711                     // (xn ... x2 x1 x0 n - xn ... x2 x1 x0 xn)
 712                     // (xn ... x2 x1 x0 n - ... x2 x1 x0 xn)
 713                     if (stack.size() < 2)
 714                         return false;
 715                     int n = CastToBigNum(stacktop(-1)).getint32();
 716                     popstack(stack);
 717                     if (n < 0 || n >= (int)stack.size())
 718                         return false;
 719                     valtype vch = stacktop(-n-1);
 720                     if (opcode == OP_ROLL)
 721                         stack.erase(stack.end()-n-1);
 722                     stack.push_back(vch);
 723                 }
 724                 break;
 725
 726                 case OP_ROT:
 727                 {
 728                     // (x1 x2 x3 -- x2 x3 x1)
 729                     //  x2 x1 x3  after first swap
 730                     //  x2 x3 x1  after second swap
 731                     if (stack.size() < 3)
 732                         return false;
 733                     swap(stacktop(-3), stacktop(-2));
 734                     swap(stacktop(-2), stacktop(-1));
 735                 }
 736                 break;
 737
 738                 case OP_SWAP:
 739                 {
 740                     // (x1 x2 -- x2 x1)
 741                     if (stack.size() < 2)
 742                         return false;
 743                     swap(stacktop(-2), stacktop(-1));
 744                 }
 745                 break;
 746
 747                 case OP_TUCK:
 748                 {
 749                     // (x1 x2 -- x2 x1 x2)
 750                     if (stack.size() < 2)
 751                         return false;
 752                     valtype vch = stacktop(-1);
 753                     stack.insert(stack.end()-2, vch);
 754                 }
 755                 break;
 756
 757
 758                 case OP_SIZE:
 759                 {
 760                     // (in -- in size)
 761                     if (stack.size() < 1)
 762                         return false;
 763                     CBigNum bn((uint16_t) stacktop(-1).size());
 764                     stack.push_back(bn.getvch());
 765                 }
 766                 break;
 767
 768
 769                 //
 770                 // Bitwise logic
 771                 //
 772                 case OP_EQUAL:
 773                 case OP_EQUALVERIFY:
 774                 //case OP_NOTEQUAL: // use OP_NUMNOTEQUAL
 775                 {
 776                     // (x1 x2 - bool)
 777                     if (stack.size() < 2)
 778                         return false;
 779                     valtype& vch1 = stacktop(-2);
 780                     valtype& vch2 = stacktop(-1);
 781                     bool fEqual = (vch1 == vch2);
 782                     // OP_NOTEQUAL is disabled because it would be too easy to say
 783                     // something like n != 1 and have some wiseguy pass in 1 with extra
 784                     // zero bytes after it (numerically, 0x01 == 0x0001 == 0x000001)
 785                     //if (opcode == OP_NOTEQUAL)
 786                     //    fEqual = !fEqual;
 787                     popstack(stack);
 788                     popstack(stack);
 789                     stack.push_back(fEqual ? vchTrue : vchFalse);
 790                     if (opcode == OP_EQUALVERIFY)
 791                     {
 792                         if (fEqual)
 793                             popstack(stack);
 794                         else
 795                             return false;
 796                     }
 797                 }
 798                 break;
 799
 800
 801                 //
 802                 // Numeric
 803                 //
 804                 case OP_1ADD:
 805                 case OP_1SUB:
 806                 case OP_NEGATE:
 807                 case OP_ABS:
 808                 case OP_NOT:
 809                 case OP_0NOTEQUAL:
 810                 {
 811                     // (in -- out)
 812                     if (stack.size() < 1)
 813                         return false;
 814                     CBigNum bn = CastToBigNum(stacktop(-1));
 815                     switch (opcode)
 816                     {
 817                     case OP_1ADD:       bn += bnOne; break;
 818                     case OP_1SUB:       bn -= bnOne; break;
 819                     case OP_NEGATE:     bn = -bn; break;
 820                     case OP_ABS:        if (bn < bnZero) bn = -bn; break;
 821                     case OP_NOT:        bn = (bn == bnZero); break;
 822                     case OP_0NOTEQUAL:  bn = (bn != bnZero); break;
 823                     default:            assert(!"invalid opcode"); break;
 824                     }
 825                     popstack(stack);
 826                     stack.push_back(bn.getvch());
 827                 }
 828                 break;
 829
 830                 case OP_ADD:
 831                 case OP_SUB:
 832                 case OP_BOOLAND:
 833                 case OP_BOOLOR:
 834                 case OP_NUMEQUAL:
 835                 case OP_NUMEQUALVERIFY:
 836                 case OP_NUMNOTEQUAL:
 837                 case OP_LESSTHAN:
 838                 case OP_GREATERTHAN:
 839                 case OP_LESSTHANOREQUAL:
 840                 case OP_GREATERTHANOREQUAL:
 841                 case OP_MIN:
 842                 case OP_MAX:
 843                 {
 844                     // (x1 x2 -- out)
 845                     if (stack.size() < 2)
 846                         return false;
 847                     CBigNum bn1 = CastToBigNum(stacktop(-2));
 848                     CBigNum bn2 = CastToBigNum(stacktop(-1));
 849                     CBigNum bn;
 850                     switch (opcode)
 851                     {
 852                     case OP_ADD:
 853                         bn = bn1 + bn2;
 854                         break;
 855
 856                     case OP_SUB:
 857                         bn = bn1 - bn2;
 858                         break;
 859
 860                     case OP_BOOLAND:             bn = (bn1 != bnZero && bn2 != bnZero); break;
 861                     case OP_BOOLOR:              bn = (bn1 != bnZero || bn2 != bnZero); break;
 862                     case OP_NUMEQUAL:            bn = (bn1 == bn2); break;
 863                     case OP_NUMEQUALVERIFY:      bn = (bn1 == bn2); break;
 864                     case OP_NUMNOTEQUAL:         bn = (bn1 != bn2); break;
 865                     case OP_LESSTHAN:            bn = (bn1 < bn2); break;
 866                     case OP_GREATERTHAN:         bn = (bn1 > bn2); break;
 867                     case OP_LESSTHANOREQUAL:     bn = (bn1 <= bn2); break;
 868                     case OP_GREATERTHANOREQUAL:  bn = (bn1 >= bn2); break;
 869                     case OP_MIN:                 bn = (bn1 < bn2 ? bn1 : bn2); break;
 870                     case OP_MAX:                 bn = (bn1 > bn2 ? bn1 : bn2); break;
 871                     default:                     assert(!"invalid opcode"); break;
 872                     }
 873                     popstack(stack);
 874                     popstack(stack);
 875                     stack.push_back(bn.getvch());
 876
 877                     if (opcode == OP_NUMEQUALVERIFY)
 878                     {
 879                         if (CastToBool(stacktop(-1)))
 880                             popstack(stack);
 881                         else
 882                             return false;
 883                     }
 884                 }
 885                 break;
 886
 887                 case OP_WITHIN:
 888                 {
 889                     // (x min max -- out)
 890                     if (stack.size() < 3)
 891                         return false;
 892                     CBigNum bn1 = CastToBigNum(stacktop(-3));
 893                     CBigNum bn2 = CastToBigNum(stacktop(-2));
 894                     CBigNum bn3 = CastToBigNum(stacktop(-1));
 895                     bool fValue = (bn2 <= bn1 && bn1 < bn3);
 896                     popstack(stack);
 897                     popstack(stack);
 898                     popstack(stack);
 899                     stack.push_back(fValue ? vchTrue : vchFalse);
 900                 }
 901                 break;
 902
 903
 904                 //
 905                 // Crypto
 906                 //
 907                 case OP_RIPEMD160:
 908                 case OP_SHA1:
 909                 case OP_SHA256:
 910                 case OP_HASH160:
 911                 case OP_HASH256:
 912                 {
 913                     // (in -- hash)
 914                     if (stack.size() < 1)
 915                         return false;
 916                     valtype& vch = stacktop(-1);
 917                     valtype vchHash((opcode == OP_RIPEMD160 || opcode == OP_SHA1 || opcode == OP_HASH160) ? 20 : 32);
 918                     if (opcode == OP_RIPEMD160)
 919                         RIPEMD160(&vch[0], vch.size(), &vchHash[0]);
 920                     else if (opcode == OP_SHA1)
 921                         SHA1(&vch[0], vch.size(), &vchHash[0]);
 922                     else if (opcode == OP_SHA256)
 923                         SHA256(&vch[0], vch.size(), &vchHash[0]);
 924                     else if (opcode == OP_HASH160)
 925                     {
 926                         uint160 hash160 = Hash160(vch);
 927                         memcpy(&vchHash[0], &hash160, sizeof(hash160));
 928                     }
 929                     else if (opcode == OP_HASH256)
 930                     {
 931                         uint256 hash = Hash(vch.begin(), vch.end());
 932                         memcpy(&vchHash[0], &hash, sizeof(hash));
 933                     }
 934                     popstack(stack);
 935                     stack.push_back(vchHash);
 936                 }
 937                 break;
 938
 939                 case OP_CODESEPARATOR:
 940                 {
 941                     // Hash starts after the code separator
 942                     pbegincodehash = pc;
 943                 }
 944                 break;
 945
 946                 case OP_CHECKSIG:
 947                 case OP_CHECKSIGVERIFY:
 948                 {
 949                     // (sig pubkey -- bool)
 950                     if (stack.size() < 2)
 951                         return false;
 952
 953                     valtype& vchSig    = stacktop(-2);
 954                     valtype& vchPubKey = stacktop(-1);
 955
 956                     ////// debug print
 957                     //PrintHex(vchSig.begin(), vchSig.end(), "sig: %s\n");
 958                     //PrintHex(vchPubKey.begin(), vchPubKey.end(), "pubkey: %s\n");
 959
 960                     // Subset of script starting at the most recent codeseparator
 961                     CScript scriptCode(pbegincodehash, pend);
 962
 963                     // Drop the signature, since there's no way for a signature to sign itself
 964                     scriptCode.FindAndDelete(CScript(vchSig));
 965
 966                     bool fSuccess = IsCanonicalSignature(vchSig, flags) && IsCanonicalPubKey(vchPubKey, flags) &&
 967                         CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType, flags);
 968
 969                     popstack(stack);
 970                     popstack(stack);
 971                     stack.push_back(fSuccess ? vchTrue : vchFalse);
 972                     if (opcode == OP_CHECKSIGVERIFY)
 973                     {
 974                         if (fSuccess)
 975                             popstack(stack);
 976                         else
 977                             return false;
 978                     }
 979                 }
 980                 break;
 981
 982                 case OP_CHECKMULTISIG:
 983                 case OP_CHECKMULTISIGVERIFY:
 984                 {
 985                     // ([sig ...] num_of_signatures [pubkey ...] num_of_pubkeys -- bool)
 986
 987                     int i = 1;
 988                     if ((int)stack.size() < i)
 989                         return false;
 990
 991                     int nKeysCount = CastToBigNum(stacktop(-i)).getint32();
 992                     if (nKeysCount < 0 || nKeysCount > 20)
 993                         return false;
 994                     nOpCount += nKeysCount;
 995                     if (nOpCount > 201)
 996                         return false;
 997                     int ikey = ++i;
 998                     i += nKeysCount;
 999                     if ((int)stack.size() < i)
1000                         return false;
1001
1002                     int nSigsCount = CastToBigNum(stacktop(-i)).getint32();
1003                     if (nSigsCount < 0 || nSigsCount > nKeysCount)
1004                         return false;
1005                     int isig = ++i;
1006                     i += nSigsCount;
1007                     if ((int)stack.size() < i)
1008                         return false;
1009
1010                     // Subset of script starting at the most recent codeseparator
1011                     CScript scriptCode(pbegincodehash, pend);
1012
1013                     // Drop the signatures, since there's no way for a signature to sign itself
1014                     for (int k = 0; k < nSigsCount; k++)
1015                     {
1016                         valtype& vchSig = stacktop(-isig-k);
1017                         scriptCode.FindAndDelete(CScript(vchSig));
1018                     }
1019
1020                     bool fSuccess = true;
1021                     while (fSuccess && nSigsCount > 0)
1022                     {
1023                         valtype& vchSig    = stacktop(-isig);
1024                         valtype& vchPubKey = stacktop(-ikey);
1025
1026                         // Check signature
1027                         bool fOk = IsCanonicalSignature(vchSig, flags) && IsCanonicalPubKey(vchPubKey, flags) &&
1028                             CheckSig(vchSig, vchPubKey, scriptCode, txTo, nIn, nHashType, flags);
1029
1030                         if (fOk) {
1031                             isig++;
1032                             nSigsCount--;
1033                         }
1034                         ikey++;
1035                         nKeysCount--;
1036
1037                         // If there are more signatures left than keys left,
1038                         // then too many signatures have failed
1039                         if (nSigsCount > nKeysCount)
1040                             fSuccess = false;
1041                     }
1042
1043                     while (i-- > 1)
1044                         popstack(stack);
1045
1046                     // A bug causes CHECKMULTISIG to consume one extra argument
1047                     // whose contents were not checked in any way.
1048                     //
1049                     // Unfortunately this is a potential source of mutability,
1050                     // so optionally verify it is exactly equal to zero prior
1051                     // to removing it from the stack.
1052                     if (stack.size() < 1)
1053                         return false;
1054                     if ((flags & SCRIPT_VERIFY_NULLDUMMY) && stacktop(-1).size())
1055                         return error("CHECKMULTISIG dummy argument not null");
1056                     popstack(stack);
1057
1058                     stack.push_back(fSuccess ? vchTrue : vchFalse);
1059
1060                     if (opcode == OP_CHECKMULTISIGVERIFY)
1061                     {
1062                         if (fSuccess)
1063                             popstack(stack);
1064                         else
1065                             return false;
1066                     }
1067                 }
1068                 break;
1069
1070                 default:
1071                     return false;
1072             }
1073
1074             // Size limits
1075             if (stack.size() + altstack.size() > 1000)
1076                 return false;
1077         }
1078     }
1079     catch (...)
1080     {
1081         return false;
1082     }
1083
1084
1085     if (!vfExec.empty())
1086         return false;
1087
1088     return true;
1089 }
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099 uint256 SignatureHash(CScript scriptCode, const CTransaction& txTo, unsigned int nIn, int nHashType)
1100 {
1101     if (nIn >= txTo.vin.size())
1102     {
1103         printf("ERROR: SignatureHash() : nIn=%d out of range\n", nIn);
1104         return 1;
1105     }
1106     CTransaction txTmp(txTo);
1107
1108     // In case concatenating two scripts ends up with two codeseparators,
1109     // or an extra one at the end, this prevents all those possible incompatibilities.
1110     scriptCode.FindAndDelete(CScript(OP_CODESEPARATOR));
1111
1112     // Blank out other inputs' signatures
1113     for (unsigned int i = 0; i < txTmp.vin.size(); i++)
1114         txTmp.vin[i].scriptSig = CScript();
1115     txTmp.vin[nIn].scriptSig = scriptCode;
1116
1117     // Blank out some of the outputs
1118     if ((nHashType & 0x1f) == SIGHASH_NONE)
1119     {
1120         // Wildcard payee
1121         txTmp.vout.clear();
1122
1123         // Let the others update at will
1124         for (unsigned int i = 0; i < txTmp.vin.size(); i++)
1125             if (i != nIn)
1126                 txTmp.vin[i].nSequence = 0;
1127     }
1128     else if ((nHashType & 0x1f) == SIGHASH_SINGLE)
1129     {
1130         // Only lock-in the txout payee at same index as txin
1131         unsigned int nOut = nIn;
1132         if (nOut >= txTmp.vout.size())
1133         {
1134             printf("ERROR: SignatureHash() : nOut=%d out of range\n", nOut);
1135             return 1;
1136         }
1137         txTmp.vout.resize(nOut+1);
1138         for (unsigned int i = 0; i < nOut; i++)
1139             txTmp.vout[i].SetNull();
1140
1141         // Let the others update at will
1142         for (unsigned int i = 0; i < txTmp.vin.size(); i++)
1143             if (i != nIn)
1144                 txTmp.vin[i].nSequence = 0;
1145     }
1146
1147     // Blank out other inputs completely, not recommended for open transactions
1148     if (nHashType & SIGHASH_ANYONECANPAY)
1149     {
1150         txTmp.vin[0] = txTmp.vin[nIn];
1151         txTmp.vin.resize(1);
1152     }
1153
1154     // Serialize and hash
1155     CDataStream ss(SER_GETHASH, 0);
1156     ss.reserve(10000);
1157     ss << txTmp << nHashType;
1158     return Hash(ss.begin(), ss.end());
1159 }
1160
1161
1162 // Valid signature cache, to avoid doing expensive ECDSA signature checking
1163 // twice for every transaction (once when accepted into memory pool, and
1164 // again when accepted into the block chain)
1165
1166 class CSignatureCache
1167 {
1168 private:
1169      // sigdata_type is (signature hash, signature, public key):
1170     typedef boost::tuple<uint256, std::vector<unsigned char>, CPubKey > sigdata_type;
1171     std::set< sigdata_type> setValid;
1172     boost::shared_mutex cs_sigcache;
1173
1174 public:
1175     bool
1176     Get(const uint256 &hash, const std::vector<unsigned char>& vchSig, const CPubKey& pubKey)
1177     {
1178         boost::shared_lock<boost::shared_mutex> lock(cs_sigcache);
1179
1180         sigdata_type k(hash, vchSig, pubKey);
1181         std::set<sigdata_type>::iterator mi = setValid.find(k);
1182         if (mi != setValid.end())
1183             return true;
1184         return false;
1185     }
1186
1187     void Set(const uint256 &hash, const std::vector<unsigned char>& vchSig, const CPubKey& pubKey)
1188     {
1189         // DoS prevention: limit cache size to less than 10MB
1190         // (~200 bytes per cache entry times 50,000 entries)
1191         // Since there are a maximum of 20,000 signature operations per block
1192         // 50,000 is a reasonable default.
1193         int64_t nMaxCacheSize = GetArg("-maxsigcachesize", 50000);
1194         if (nMaxCacheSize <= 0) return;
1195
1196         boost::shared_lock<boost::shared_mutex> lock(cs_sigcache);
1197
1198         while (static_cast<int64_t>(setValid.size()) > nMaxCacheSize)
1199         {
1200             // Evict a random entry. Random because that helps
1201             // foil would-be DoS attackers who might try to pre-generate
1202             // and re-use a set of valid signatures just-slightly-greater
1203             // than our cache size.
1204             uint256 randomHash = GetRandHash();
1205             std::vector<unsigned char> unused;
1206             std::set<sigdata_type>::iterator it =
1207                 setValid.lower_bound(sigdata_type(randomHash, unused, unused));
1208             if (it == setValid.end())
1209                 it = setValid.begin();
1210             setValid.erase(*it);
1211         }
1212
1213         sigdata_type k(hash, vchSig, pubKey);
1214         setValid.insert(k);
1215     }
1216 };
1217
1218 bool CheckSig(vector<unsigned char> vchSig, const vector<unsigned char> &vchPubKey, const CScript &scriptCode,
1219               const CTransaction& txTo, unsigned int nIn, int nHashType, int flags)
1220 {
1221     static CSignatureCache signatureCache;
1222
1223     CKey key;
1224     if (!key.SetPubKey(vchPubKey))
1225          return false;
1226     CPubKey pubkey = key.GetPubKey();
1227     if (!pubkey.IsValid())
1228         return false;
1229
1230     // Hash type is one byte tacked on to the end of the signature
1231     if (vchSig.empty())
1232         return false;
1233     if (nHashType == 0)
1234         nHashType = vchSig.back();
1235     else if (nHashType != vchSig.back())
1236         return false;
1237     vchSig.pop_back();
1238
1239     uint256 sighash = SignatureHash(scriptCode, txTo, nIn, nHashType);
1240
1241     if (signatureCache.Get(sighash, vchSig, pubkey))
1242         return true;
1243
1244     if (!key.Verify(sighash, vchSig))
1245         return false;
1246
1247     if (!(flags & SCRIPT_VERIFY_NOCACHE))
1248         signatureCache.Set(sighash, vchSig, pubkey);
1249
1250     return true;
1251 }
1252
1253
1254
1255
1256
1257
1258
1259
1260 //
1261 // Return public keys or hashes from scriptPubKey, for 'standard' transaction types.
1262 //
1263 bool Solver(const CScript& scriptPubKey, txnouttype& typeRet, vector<vector<unsigned char> >& vSolutionsRet)
1264 {
1265     // Templates
1266     static map<txnouttype, CScript> mTemplates;
1267     if (mTemplates.empty())
1268     {
1269         // Standard tx, sender provides pubkey, receiver adds signature
1270         mTemplates.insert(make_pair(TX_PUBKEY, CScript() << OP_PUBKEY << OP_CHECKSIG));
1271
1272         if (fTestNet || GetTime() > SMALLDATA_SWITCH_TIME)
1273         {
1274             // Malleable pubkey tx hack, sender provides generated pubkey combined with R parameter. The R parameter is dropped before checking a signature.
1275             mTemplates.insert(make_pair(TX_PUBKEY_DROP, CScript() << OP_PUBKEY << OP_PUBKEY << OP_DROP << OP_CHECKSIG));
1276         }
1277
1278         // Bitcoin address tx, sender provides hash of pubkey, receiver provides signature and pubkey
1279         mTemplates.insert(make_pair(TX_PUBKEYHASH, CScript() << OP_DUP << OP_HASH160 << OP_PUBKEYHASH << OP_EQUALVERIFY << OP_CHECKSIG));
1280
1281         // Sender provides N pubkeys, receivers provides M signatures
1282         mTemplates.insert(make_pair(TX_MULTISIG, CScript() << OP_SMALLINTEGER << OP_PUBKEYS << OP_SMALLINTEGER << OP_CHECKMULTISIG));
1283
1284         // Empty, provably prunable, data-carrying output
1285         mTemplates.insert(make_pair(TX_NULL_DATA, CScript() << OP_RETURN << OP_SMALLDATA));
1286     }
1287
1288     vSolutionsRet.clear();
1289
1290     // Shortcut for pay-to-script-hash, which are more constrained than the other types:
1291     // it is always OP_HASH160 20 [20 byte hash] OP_EQUAL
1292     if (scriptPubKey.IsPayToScriptHash())
1293     {
1294         typeRet = TX_SCRIPTHASH;
1295         vector<unsigned char> hashBytes(scriptPubKey.begin()+2, scriptPubKey.begin()+22);
1296         vSolutionsRet.push_back(hashBytes);
1297         return true;
1298     }
1299
1300     // Provably prunable, data-carrying output
1301     //
1302     // So long as script passes the IsUnspendable() test and all but the first
1303     // byte passes the IsPushOnly() test we don't care what exactly is in the
1304     // script.
1305     if (scriptPubKey.size() >= 1 && scriptPubKey[0] == OP_RETURN && scriptPubKey.IsPushOnly(scriptPubKey.begin()+1)) {
1306         typeRet = TX_NULL_DATA;
1307         return true;
1308     }
1309
1310     // Scan templates
1311     const CScript& script1 = scriptPubKey;
1312     BOOST_FOREACH(const PAIRTYPE(txnouttype, CScript)& tplate, mTemplates)
1313     {
1314         const CScript& script2 = tplate.second;
1315         vSolutionsRet.clear();
1316
1317         opcodetype opcode1, opcode2;
1318         vector<unsigned char> vch1, vch2;
1319
1320         // Compare
1321         CScript::const_iterator pc1 = script1.begin();
1322         CScript::const_iterator pc2 = script2.begin();
1323         while (true)
1324         {
1325             if (pc1 == script1.end() && pc2 == script2.end())
1326             {
1327                 // Found a match
1328                 typeRet = tplate.first;
1329                 if (typeRet == TX_MULTISIG)
1330                 {
1331                     // Additional checks for TX_MULTISIG:
1332                     unsigned char m = vSolutionsRet.front()[0];
1333                     unsigned char n = vSolutionsRet.back()[0];
1334                     if (m < 1 || n < 1 || m > n || vSolutionsRet.size()-2 != n)
1335                         return false;
1336                 }
1337                 return true;
1338             }
1339             if (!script1.GetOp(pc1, opcode1, vch1))
1340                 break;
1341             if (!script2.GetOp(pc2, opcode2, vch2))
1342                 break;
1343
1344             // Template matching opcodes:
1345             if (opcode2 == OP_PUBKEYS)
1346             {
1347                 while (vch1.size() >= 33 && vch1.size() <= 120)
1348                 {
1349                     vSolutionsRet.push_back(vch1);
1350                     if (!script1.GetOp(pc1, opcode1, vch1))
1351                         break;
1352                 }
1353                 if (!script2.GetOp(pc2, opcode2, vch2))
1354                     break;
1355                 // Normal situation is to fall through
1356                 // to other if/else statements
1357             }
1358
1359             if (opcode2 == OP_PUBKEY)
1360             {
1361                 if (vch1.size() < 33 || vch1.size() > 120)
1362                     break;
1363                 vSolutionsRet.push_back(vch1);
1364             }
1365             else if (opcode2 == OP_PUBKEYHASH)
1366             {
1367                 if (vch1.size() != sizeof(uint160))
1368                     break;
1369                 vSolutionsRet.push_back(vch1);
1370             }
1371             else if (opcode2 == OP_SMALLINTEGER)
1372             {   // Single-byte small integer pushed onto vSolutions
1373                 if (opcode1 == OP_0 ||
1374                     (opcode1 >= OP_1 && opcode1 <= OP_16))
1375                 {
1376                     char n = (char)CScript::DecodeOP_N(opcode1);
1377                     vSolutionsRet.push_back(valtype(1, n));
1378                 }
1379                 else
1380                     break;
1381             }
1382             else if (opcode2 == OP_INTEGER)
1383             {   // Up to four-byte integer pushed onto vSolutions
1384                 try
1385                 {
1386                     CBigNum bnVal = CastToBigNum(vch1);
1387                     if (bnVal <= 16)
1388                         break; // It's better to use OP_0 ... OP_16 for small integers.
1389                     vSolutionsRet.push_back(vch1);
1390                 }
1391                 catch(...)
1392                 {
1393                     break;
1394                 }
1395             }
1396             else if (opcode2 == OP_SMALLDATA)
1397             {
1398                 // small pushdata, <= 1024 bytes
1399                 if (vch1.size() > (GetTime() > SMALLDATA_SWITCH_TIME ? 1024 : 80))
1400                     break;
1401             }
1402             else if (opcode1 != opcode2 || vch1 != vch2)
1403             {
1404                 // Others must match exactly
1405                 break;
1406             }
1407         }
1408     }
1409
1410     vSolutionsRet.clear();
1411     typeRet = TX_NONSTANDARD;
1412     return false;
1413 }
1414
1415
1416 bool Sign1(const CKeyID& address, const CKeyStore& keystore, const uint256& hash, int nHashType, CScript& scriptSigRet)
1417 {
1418     CKey key;
1419     if (!keystore.GetKey(address, key))
1420         return false;
1421
1422     vector<unsigned char> vchSig;
1423     if (!key.Sign(hash, vchSig))
1424         return false;
1425     vchSig.push_back((unsigned char)nHashType);
1426     scriptSigRet << vchSig;
1427
1428     return true;
1429 }
1430
1431 bool SignR(const CPubKey& pubKey, const CPubKey& R, const CKeyStore& keystore, const uint256& hash, int nHashType, CScript& scriptSigRet)
1432 {
1433     CKey key;
1434     if (!keystore.CreatePrivKey(pubKey, R, key))
1435         return false;
1436
1437     vector<unsigned char> vchSig;
1438     if (!key.Sign(hash, vchSig))
1439         return false;
1440     vchSig.push_back((unsigned char)nHashType);
1441     scriptSigRet << vchSig;
1442
1443     return true;
1444 }
1445
1446 bool SignN(const vector<valtype>& multisigdata, const CKeyStore& keystore, const uint256& hash, int nHashType, CScript& scriptSigRet)
1447 {
1448     int nSigned = 0;
1449     int nRequired = multisigdata.front()[0];
1450     for (unsigned int i = 1; i < multisigdata.size()-1 && nSigned < nRequired; i++)
1451     {
1452         const valtype& pubkey = multisigdata[i];
1453         CKeyID keyID = CPubKey(pubkey).GetID();
1454         if (Sign1(keyID, keystore, hash, nHashType, scriptSigRet))
1455             ++nSigned;
1456     }
1457     return nSigned==nRequired;
1458 }
1459
1460 //
1461 // Sign scriptPubKey with private keys stored in keystore, given transaction hash and hash type.
1462 // Signatures are returned in scriptSigRet (or returns false if scriptPubKey can't be signed),
1463 // unless whichTypeRet is TX_SCRIPTHASH, in which case scriptSigRet is the redemption script.
1464 // Returns false if scriptPubKey could not be completely satisfied.
1465 //
1466 bool Solver(const CKeyStore& keystore, const CScript& scriptPubKey, const uint256& hash, int nHashType,
1467                   CScript& scriptSigRet, txnouttype& whichTypeRet)
1468 {
1469     scriptSigRet.clear();
1470
1471     vector<valtype> vSolutions;
1472     if (!Solver(scriptPubKey, whichTypeRet, vSolutions))
1473         return false;
1474
1475     CKeyID keyID;
1476     switch (whichTypeRet)
1477     {
1478     case TX_NONSTANDARD:
1479     case TX_NULL_DATA:
1480         return false;
1481     case TX_PUBKEY:
1482         keyID = CPubKey(vSolutions[0]).GetID();
1483         return Sign1(keyID, keystore, hash, nHashType, scriptSigRet);
1484     case TX_PUBKEY_DROP:
1485         {
1486             CPubKey key = CPubKey(vSolutions[0]);
1487             CPubKey R = CPubKey(vSolutions[1]);
1488             return SignR(key, R, keystore, hash, nHashType, scriptSigRet);
1489         }
1490     case TX_PUBKEYHASH:
1491         keyID = CKeyID(uint160(vSolutions[0]));
1492         if (!Sign1(keyID, keystore, hash, nHashType, scriptSigRet))
1493             return false;
1494         else
1495         {
1496             CPubKey vch;
1497             keystore.GetPubKey(keyID, vch);
1498             scriptSigRet << vch;
1499         }
1500         return true;
1501     case TX_SCRIPTHASH:
1502         return keystore.GetCScript(uint160(vSolutions[0]), scriptSigRet);
1503
1504     case TX_MULTISIG:
1505         scriptSigRet << OP_0; // workaround CHECKMULTISIG bug
1506         return (SignN(vSolutions, keystore, hash, nHashType, scriptSigRet));
1507     }
1508     return false;
1509 }
1510
1511 int ScriptSigArgsExpected(txnouttype t, const std::vector<std::vector<unsigned char> >& vSolutions)
1512 {
1513     switch (t)
1514     {
1515     case TX_NONSTANDARD:
1516         return -1;
1517     case TX_NULL_DATA:
1518         return 1;
1519     case TX_PUBKEY:
1520     case TX_PUBKEY_DROP:
1521         return 1;
1522     case TX_PUBKEYHASH:
1523         return 2;
1524     case TX_MULTISIG:
1525         if (vSolutions.size() < 1 || vSolutions[0].size() < 1)
1526             return -1;
1527         return vSolutions[0][0] + 1;
1528     case TX_SCRIPTHASH:
1529         return 1; // doesn't include args needed by the script
1530     }
1531     return -1;
1532 }
1533
1534 bool IsStandard(const CScript& scriptPubKey, txnouttype& whichType)
1535 {
1536     vector<valtype> vSolutions;
1537     if (!Solver(scriptPubKey, whichType, vSolutions))
1538         return false;
1539
1540     if (whichType == TX_MULTISIG)
1541     {
1542         unsigned char m = vSolutions.front()[0];
1543         unsigned char n = vSolutions.back()[0];
1544         // Support up to x-of-3 multisig txns as standard
1545         if (n < 1 || n > 3)
1546             return false;
1547         if (m < 1 || m > n)
1548             return false;
1549     }
1550
1551     return whichType != TX_NONSTANDARD;
1552 }
1553
1554
1555 unsigned int HaveKeys(const vector<valtype>& pubkeys, const CKeyStore& keystore)
1556 {
1557     unsigned int nResult = 0;
1558     BOOST_FOREACH(const valtype& pubkey, pubkeys)
1559     {
1560         CKeyID keyID = CPubKey(pubkey).GetID();
1561         if (keystore.HaveKey(keyID))
1562             ++nResult;
1563     }
1564     return nResult;
1565 }
1566
1567
1568 class CKeyStoreIsMineVisitor : public boost::static_visitor<bool>
1569 {
1570 private:
1571     const CKeyStore *keystore;
1572 public:
1573     CKeyStoreIsMineVisitor(const CKeyStore *keystoreIn) : keystore(keystoreIn) { }
1574     bool operator()(const CNoDestination &dest) const { return false; }
1575     bool operator()(const CKeyID &keyID) const { return keystore->HaveKey(keyID); }
1576     bool operator()(const CScriptID &scriptID) const { return keystore->HaveCScript(scriptID); }
1577 };
1578
1579 isminetype IsMine(const CKeyStore &keystore, const CTxDestination& dest)
1580 {
1581     CScript script;
1582     script.SetDestination(dest);
1583     return IsMine(keystore, script);
1584 }
1585
1586 isminetype IsMine(const CKeyStore &keystore, const CScript& scriptPubKey)
1587 {
1588     vector<valtype> vSolutions;
1589     txnouttype whichType;
1590     if (!Solver(scriptPubKey, whichType, vSolutions)) {
1591         if (keystore.HaveWatchOnly(scriptPubKey))
1592             return MINE_WATCH_ONLY;
1593         return MINE_NO;
1594     }
1595
1596     CKeyID keyID;
1597     switch (whichType)
1598     {
1599     case TX_NONSTANDARD:
1600     case TX_NULL_DATA:
1601         break;
1602     case TX_PUBKEY:
1603         keyID = CPubKey(vSolutions[0]).GetID();
1604         if (keystore.HaveKey(keyID))
1605             return MINE_SPENDABLE;
1606         break;
1607     case TX_PUBKEY_DROP:
1608         {
1609             CPubKey key = CPubKey(vSolutions[0]);
1610             CPubKey R = CPubKey(vSolutions[1]);
1611             if (keystore.CheckOwnership(key, R))
1612                 return MINE_SPENDABLE;
1613         }
1614         break;
1615     case TX_PUBKEYHASH:
1616         keyID = CKeyID(uint160(vSolutions[0]));
1617         if (keystore.HaveKey(keyID))
1618             return MINE_SPENDABLE;
1619         break;
1620     case TX_SCRIPTHASH:
1621     {
1622         CScriptID scriptID = CScriptID(uint160(vSolutions[0]));
1623         CScript subscript;
1624         if (keystore.GetCScript(scriptID, subscript)) {
1625             isminetype ret = IsMine(keystore, subscript);
1626             if (ret == MINE_SPENDABLE)
1627                 return ret;
1628         }
1629         break;
1630     }
1631     case TX_MULTISIG:
1632     {
1633         // Only consider transactions "mine" if we own ALL the
1634         // keys involved. multi-signature transactions that are
1635         // partially owned (somebody else has a key that can spend
1636         // them) enable spend-out-from-under-you attacks, especially
1637         // in shared-wallet situations.
1638         vector<valtype> keys(vSolutions.begin()+1, vSolutions.begin()+vSolutions.size()-1);
1639         if (HaveKeys(keys, keystore) == keys.size())
1640             return MINE_SPENDABLE;
1641         break;
1642     }
1643     }
1644
1645     if (keystore.HaveWatchOnly(scriptPubKey))
1646         return MINE_WATCH_ONLY;
1647     return MINE_NO;
1648 }
1649
1650 bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
1651 {
1652     vector<valtype> vSolutions;
1653     txnouttype whichType;
1654     if (!Solver(scriptPubKey, whichType, vSolutions))
1655         return false;
1656
1657     if (whichType == TX_PUBKEY)
1658     {
1659         addressRet = CPubKey(vSolutions[0]).GetID();
1660         return true;
1661     }
1662     else if (whichType == TX_PUBKEYHASH)
1663     {
1664         addressRet = CKeyID(uint160(vSolutions[0]));
1665         return true;
1666     }
1667     else if (whichType == TX_SCRIPTHASH)
1668     {
1669         addressRet = CScriptID(uint160(vSolutions[0]));
1670         return true;
1671     }
1672     // Multisig txns have more than one address...
1673     return false;
1674 }
1675
1676 class CAffectedKeysVisitor : public boost::static_visitor<void> {
1677 private:
1678     const CKeyStore &keystore;
1679     CAffectedKeysVisitor& operator=(CAffectedKeysVisitor const&);
1680     std::vector<CKeyID> &vKeys;
1681
1682 public:
1683     CAffectedKeysVisitor(const CKeyStore &keystoreIn, std::vector<CKeyID> &vKeysIn) : keystore(keystoreIn), vKeys(vKeysIn) {}
1684
1685     void Process(const CScript &script) {
1686         txnouttype type;
1687         std::vector<CTxDestination> vDest;
1688         int nRequired;
1689         if (ExtractDestinations(script, type, vDest, nRequired)) {
1690             BOOST_FOREACH(const CTxDestination &dest, vDest)
1691                 boost::apply_visitor(*this, dest);
1692         }
1693     }
1694
1695     void operator()(const CKeyID &keyId) {
1696         if (keystore.HaveKey(keyId))
1697             vKeys.push_back(keyId);
1698     }
1699
1700     void operator()(const CScriptID &scriptId) {
1701         CScript script;
1702         if (keystore.GetCScript(scriptId, script))
1703             Process(script);
1704     }
1705
1706     void operator()(const CNoDestination &none) {}
1707 };
1708
1709
1710 void ExtractAffectedKeys(const CKeyStore &keystore, const CScript& scriptPubKey, std::vector<CKeyID> &vKeys) {
1711     CAffectedKeysVisitor(keystore, vKeys).Process(scriptPubKey);
1712 }
1713
1714 bool ExtractDestinations(const CScript& scriptPubKey, txnouttype& typeRet, vector<CTxDestination>& addressRet, int& nRequiredRet)
1715 {
1716     addressRet.clear();
1717     typeRet = TX_NONSTANDARD;
1718     vector<valtype> vSolutions;
1719     if (!Solver(scriptPubKey, typeRet, vSolutions))
1720         return false;
1721     if (typeRet == TX_NULL_DATA)
1722     {
1723         nRequiredRet = 0;
1724         return true;
1725     }
1726
1727     if (typeRet == TX_MULTISIG)
1728     {
1729         nRequiredRet = vSolutions.front()[0];
1730         for (unsigned int i = 1; i < vSolutions.size()-1; i++)
1731         {
1732             CTxDestination address = CPubKey(vSolutions[i]).GetID();
1733             addressRet.push_back(address);
1734         }
1735     }
1736     else
1737     {
1738         nRequiredRet = 1;
1739         if (typeRet == TX_PUBKEY_DROP)
1740             return true;
1741         CTxDestination address;
1742         if (!ExtractDestination(scriptPubKey, address))
1743            return false;
1744         addressRet.push_back(address);
1745     }
1746
1747     return true;
1748 }
1749
1750 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn,
1751                   unsigned int flags, int nHashType)
1752 {
1753     vector<vector<unsigned char> > stack, stackCopy;
1754     if (!EvalScript(stack, scriptSig, txTo, nIn, flags, nHashType))
1755         return false;
1756     if (flags & SCRIPT_VERIFY_P2SH)
1757         stackCopy = stack;
1758     if (!EvalScript(stack, scriptPubKey, txTo, nIn, flags, nHashType))
1759         return false;
1760     if (stack.empty())
1761         return false;
1762
1763     if (CastToBool(stack.back()) == false)
1764         return false;
1765
1766     // Additional validation for spend-to-script-hash transactions:
1767     if ((flags & SCRIPT_VERIFY_P2SH) && scriptPubKey.IsPayToScriptHash())
1768     {
1769         if (!scriptSig.IsPushOnly()) // scriptSig must be literals-only
1770             return false;            // or validation fails
1771
1772         // stackCopy cannot be empty here, because if it was the
1773         // P2SH  HASH <> EQUAL  scriptPubKey would be evaluated with
1774         // an empty stack and the EvalScript above would return false.
1775         assert(!stackCopy.empty());
1776
1777         const valtype& pubKeySerialized = stackCopy.back();
1778         CScript pubKey2(pubKeySerialized.begin(), pubKeySerialized.end());
1779         popstack(stackCopy);
1780
1781         if (!EvalScript(stackCopy, pubKey2, txTo, nIn, flags, nHashType))
1782             return false;
1783         if (stackCopy.empty())
1784             return false;
1785         return CastToBool(stackCopy.back());
1786     }
1787
1788     return true;
1789 }
1790
1791 bool SignSignature(const CKeyStore &keystore, const CScript& fromPubKey, CTransaction& txTo, unsigned int nIn, int nHashType)
1792 {
1793     assert(nIn < txTo.vin.size());
1794     CTxIn& txin = txTo.vin[nIn];
1795
1796     // Leave out the signature from the hash, since a signature can't sign itself.
1797     // The checksig op will also drop the signatures from its hash.
1798     uint256 hash = SignatureHash(fromPubKey, txTo, nIn, nHashType);
1799
1800     txnouttype whichType;
1801     if (!Solver(keystore, fromPubKey, hash, nHashType, txin.scriptSig, whichType))
1802         return false;
1803
1804     if (whichType == TX_SCRIPTHASH)
1805     {
1806         // Solver returns the subscript that need to be evaluated;
1807         // the final scriptSig is the signatures from that
1808         // and then the serialized subscript:
1809         CScript subscript = txin.scriptSig;
1810
1811         // Recompute txn hash using subscript in place of scriptPubKey:
1812         uint256 hash2 = SignatureHash(subscript, txTo, nIn, nHashType);
1813
1814         txnouttype subType;
1815         bool fSolved =
1816             Solver(keystore, subscript, hash2, nHashType, txin.scriptSig, subType) && subType != TX_SCRIPTHASH;
1817         // Append serialized subscript whether or not it is completely signed:
1818         txin.scriptSig << static_cast<valtype>(subscript);
1819         if (!fSolved) return false;
1820     }
1821
1822     // Test solution
1823     return VerifyScript(txin.scriptSig, fromPubKey, txTo, nIn, STRICT_FLAGS, 0);
1824 }
1825
1826 bool SignSignature(const CKeyStore &keystore, const CTransaction& txFrom, CTransaction& txTo, unsigned int nIn, int nHashType)
1827 {
1828     assert(nIn < txTo.vin.size());
1829     CTxIn& txin = txTo.vin[nIn];
1830     assert(txin.prevout.n < txFrom.vout.size());
1831     assert(txin.prevout.hash == txFrom.GetHash());
1832     const CTxOut& txout = txFrom.vout[txin.prevout.n];
1833
1834     return SignSignature(keystore, txout.scriptPubKey, txTo, nIn, nHashType);
1835 }
1836
1837 static CScript PushAll(const vector<valtype>& values)
1838 {
1839     CScript result;
1840     BOOST_FOREACH(const valtype& v, values)
1841         result << v;
1842     return result;
1843 }
1844
1845 static CScript CombineMultisig(const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn,
1846                                const vector<valtype>& vSolutions,
1847                                vector<valtype>& sigs1, vector<valtype>& sigs2)
1848 {
1849     // Combine all the signatures we've got:
1850     set<valtype> allsigs;
1851     BOOST_FOREACH(const valtype& v, sigs1)
1852     {
1853         if (!v.empty())
1854             allsigs.insert(v);
1855     }
1856     BOOST_FOREACH(const valtype& v, sigs2)
1857     {
1858         if (!v.empty())
1859             allsigs.insert(v);
1860     }
1861
1862     // Build a map of pubkey -> signature by matching sigs to pubkeys:
1863     assert(vSolutions.size() > 1);
1864     unsigned int nSigsRequired = vSolutions.front()[0];
1865     unsigned int nPubKeys = (unsigned int)(vSolutions.size()-2);
1866     map<valtype, valtype> sigs;
1867     BOOST_FOREACH(const valtype& sig, allsigs)
1868     {
1869         for (unsigned int i = 0; i < nPubKeys; i++)
1870         {
1871             const valtype& pubkey = vSolutions[i+1];
1872             if (sigs.count(pubkey))
1873                 continue; // Already got a sig for this pubkey
1874
1875             if (CheckSig(sig, pubkey, scriptPubKey, txTo, nIn, 0, 0))
1876             {
1877                 sigs[pubkey] = sig;
1878                 break;
1879             }
1880         }
1881     }
1882     // Now build a merged CScript:
1883     unsigned int nSigsHave = 0;
1884     CScript result; result << OP_0; // pop-one-too-many workaround
1885     for (unsigned int i = 0; i < nPubKeys && nSigsHave < nSigsRequired; i++)
1886     {
1887         if (sigs.count(vSolutions[i+1]))
1888         {
1889             result << sigs[vSolutions[i+1]];
1890             ++nSigsHave;
1891         }
1892     }
1893     // Fill any missing with OP_0:
1894     for (unsigned int i = nSigsHave; i < nSigsRequired; i++)
1895         result << OP_0;
1896
1897     return result;
1898 }
1899
1900 static CScript CombineSignatures(const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn,
1901                                  const txnouttype txType, const vector<valtype>& vSolutions,
1902                                  vector<valtype>& sigs1, vector<valtype>& sigs2)
1903 {
1904     switch (txType)
1905     {
1906     case TX_NONSTANDARD:
1907     case TX_NULL_DATA:
1908         // Don't know anything about this, assume bigger one is correct:
1909         if (sigs1.size() >= sigs2.size())
1910             return PushAll(sigs1);
1911         return PushAll(sigs2);
1912     case TX_PUBKEY:
1913     case TX_PUBKEY_DROP:
1914     case TX_PUBKEYHASH:
1915         // Signatures are bigger than placeholders or empty scripts:
1916         if (sigs1.empty() || sigs1[0].empty())
1917             return PushAll(sigs2);
1918         return PushAll(sigs1);
1919     case TX_SCRIPTHASH:
1920         if (sigs1.empty() || sigs1.back().empty())
1921             return PushAll(sigs2);
1922         else if (sigs2.empty() || sigs2.back().empty())
1923             return PushAll(sigs1);
1924         else
1925         {
1926             // Recur to combine:
1927             valtype spk = sigs1.back();
1928             CScript pubKey2(spk.begin(), spk.end());
1929
1930             txnouttype txType2;
1931             vector<vector<unsigned char> > vSolutions2;
1932             Solver(pubKey2, txType2, vSolutions2);
1933             sigs1.pop_back();
1934             sigs2.pop_back();
1935             CScript result = CombineSignatures(pubKey2, txTo, nIn, txType2, vSolutions2, sigs1, sigs2);
1936             result << spk;
1937             return result;
1938         }
1939     case TX_MULTISIG:
1940         return CombineMultisig(scriptPubKey, txTo, nIn, vSolutions, sigs1, sigs2);
1941     }
1942
1943     return CScript();
1944 }
1945
1946 CScript CombineSignatures(const CScript& scriptPubKey, const CTransaction& txTo, unsigned int nIn,
1947                           const CScript& scriptSig1, const CScript& scriptSig2)
1948 {
1949     txnouttype txType;
1950     vector<vector<unsigned char> > vSolutions;
1951     Solver(scriptPubKey, txType, vSolutions);
1952
1953     vector<valtype> stack1;
1954     EvalScript(stack1, scriptSig1, CTransaction(), 0, SCRIPT_VERIFY_STRICTENC, 0);
1955     vector<valtype> stack2;
1956     EvalScript(stack2, scriptSig2, CTransaction(), 0, SCRIPT_VERIFY_STRICTENC, 0);
1957
1958     return CombineSignatures(scriptPubKey, txTo, nIn, txType, vSolutions, stack1, stack2);
1959 }
1960
1961 unsigned int CScript::GetSigOpCount(bool fAccurate) const
1962 {
1963     unsigned int n = 0;
1964     const_iterator pc = begin();
1965     opcodetype lastOpcode = OP_INVALIDOPCODE;
1966     while (pc < end())
1967     {
1968         opcodetype opcode;
1969         if (!GetOp(pc, opcode))
1970             break;
1971         if (opcode == OP_CHECKSIG || opcode == OP_CHECKSIGVERIFY)
1972             n++;
1973         else if (opcode == OP_CHECKMULTISIG || opcode == OP_CHECKMULTISIGVERIFY)
1974         {
1975             if (fAccurate && lastOpcode >= OP_1 && lastOpcode <= OP_16)
1976                 n += DecodeOP_N(lastOpcode);
1977             else
1978                 n += 20;
1979         }
1980         lastOpcode = opcode;
1981     }
1982     return n;
1983 }
1984
1985 unsigned int CScript::GetSigOpCount(const CScript& scriptSig) const
1986 {
1987     if (!IsPayToScriptHash())
1988         return GetSigOpCount(true);
1989
1990     // This is a pay-to-script-hash scriptPubKey;
1991     // get the last item that the scriptSig
1992     // pushes onto the stack:
1993     const_iterator pc = scriptSig.begin();
1994     vector<unsigned char> data;
1995     while (pc < scriptSig.end())
1996     {
1997         opcodetype opcode;
1998         if (!scriptSig.GetOp(pc, opcode, data))
1999             return 0;
2000         if (opcode > OP_16)
2001             return 0;
2002     }
2003
2004     /// ... and return its opcount:
2005     CScript subscript(data.begin(), data.end());
2006     return subscript.GetSigOpCount(true);
2007 }
2008
2009 bool CScript::IsPayToScriptHash() const
2010 {
2011     // Extra-fast test for pay-to-script-hash CScripts:
2012     return (this->size() == 23 &&
2013             this->at(0) == OP_HASH160 &&
2014             this->at(1) == 0x14 &&
2015             this->at(22) == OP_EQUAL);
2016 }
2017
2018 bool CScript::HasCanonicalPushes() const
2019 {
2020     const_iterator pc = begin();
2021     while (pc < end())
2022     {
2023         opcodetype opcode;
2024         std::vector<unsigned char> data;
2025         if (!GetOp(pc, opcode, data))
2026             return false;
2027         if (opcode > OP_16)
2028             continue;
2029         if (opcode < OP_PUSHDATA1 && opcode > OP_0 && (data.size() == 1 && data[0] <= 16))
2030             // Could have used an OP_n code, rather than a 1-byte push.
2031             return false;
2032         if (opcode == OP_PUSHDATA1 && data.size() < OP_PUSHDATA1)
2033             // Could have used a normal n-byte push, rather than OP_PUSHDATA1.
2034             return false;
2035         if (opcode == OP_PUSHDATA2 && data.size() <= 0xFF)
2036             // Could have used an OP_PUSHDATA1.
2037             return false;
2038         if (opcode == OP_PUSHDATA4 && data.size() <= 0xFFFF)
2039             // Could have used an OP_PUSHDATA2.
2040             return false;
2041     }
2042     return true;
2043 }
2044
2045 class CScriptVisitor : public boost::static_visitor<bool>
2046 {
2047 private:
2048     CScript *script;
2049 public:
2050     CScriptVisitor(CScript *scriptin) { script = scriptin; }
2051
2052     bool operator()(const CNoDestination &dest) const {
2053         script->clear();
2054         return false;
2055     }
2056
2057     bool operator()(const CKeyID &keyID) const {
2058         script->clear();
2059         *script << OP_DUP << OP_HASH160 << keyID << OP_EQUALVERIFY << OP_CHECKSIG;
2060         return true;
2061     }
2062
2063     bool operator()(const CScriptID &scriptID) const {
2064         script->clear();
2065         *script << OP_HASH160 << scriptID << OP_EQUAL;
2066         return true;
2067     }
2068 };
2069
2070 void CScript::SetDestination(const CTxDestination& dest)
2071 {
2072     boost::apply_visitor(CScriptVisitor(this), dest);
2073 }
2074
2075 void CScript::SetDestination(const CPubKey& R, CPubKey& pubKeyVariant)
2076 {
2077     this->clear();
2078     *this << pubKeyVariant << R << OP_DROP << OP_CHECKSIG;
2079 }
2080
2081
2082 void CScript::SetMultisig(int nRequired, const std::vector<CKey>& keys)
2083 {
2084     this->clear();
2085
2086     *this << EncodeOP_N(nRequired);
2087     BOOST_FOREACH(const CKey& key, keys)
2088         *this << key.GetPubKey();
2089     *this << EncodeOP_N((int)(keys.size())) << OP_CHECKMULTISIG;
2090 }