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