src/script.cpp

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