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