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