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