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