src/main.h

   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 #ifndef BITCOIN_MAIN_H
   6 #define BITCOIN_MAIN_H
   7
   8 #include "bignum.h"
   9 #include "sync.h"
  10 #include "net.h"
  11 #include "script.h"
  12
  13 #include <list>
  14
  15 class CWallet;
  16 class CBlock;
  17 class CBlockIndex;
  18 class CKeyItem;
  19 class CReserveKey;
  20
  21 class CAddress;
  22 class CInv;
  23 class CNode;
  24
  25 struct CBlockIndexWorkComparator;
  26
  27 /** The maximum allowed size for a serialized block, in bytes (network rule) */
  28 static const unsigned int MAX_BLOCK_SIZE = 1000000;
  29 /** The maximum size for mined blocks */
  30 static const unsigned int MAX_BLOCK_SIZE_GEN = MAX_BLOCK_SIZE/2;
  31 /** The maximum size for transactions we're willing to relay/mine **/
  32 static const unsigned int MAX_STANDARD_TX_SIZE = MAX_BLOCK_SIZE_GEN/5;
  33 /** The maximum allowed number of signature check operations in a block (network rule) */
  34 static const unsigned int MAX_BLOCK_SIGOPS = MAX_BLOCK_SIZE/50;
  35 /** The maximum number of orphan transactions kept in memory */
  36 static const unsigned int MAX_ORPHAN_TRANSACTIONS = MAX_BLOCK_SIZE/100;
  37 /** The maximum number of entries in an 'inv' protocol message */
  38 static const unsigned int MAX_INV_SZ = 50000;
  39 /** The maximum size of a blk?????.dat file (since 0.8) */
  40 static const unsigned int MAX_BLOCKFILE_SIZE = 0x8000000; // 128 MiB
  41 /** The pre-allocation chunk size for blk?????.dat files (since 0.8) */
  42 static const unsigned int BLOCKFILE_CHUNK_SIZE = 0x1000000; // 16 MiB
  43 /** The pre-allocation chunk size for rev?????.dat files (since 0.8) */
  44 static const unsigned int UNDOFILE_CHUNK_SIZE = 0x100000; // 1 MiB
  45 /** Fake height value used in CCoins to signify they are only in the memory pool (since 0.8) */
  46 static const unsigned int MEMPOOL_HEIGHT = 0x7FFFFFFF;
  47 /** Fees smaller than this (in satoshi) are considered zero fee (for transaction creation) */
  48 static const int64 MIN_TX_FEE = 50000;
  49 /** Fees smaller than this (in satoshi) are considered zero fee (for relaying) */
  50 static const int64 MIN_RELAY_TX_FEE = 10000;
  51 /** No amount larger than this (in satoshi) is valid */
  52 static const int64 MAX_MONEY = 21000000 * COIN;
  53 inline bool MoneyRange(int64 nValue) { return (nValue >= 0 && nValue <= MAX_MONEY); }
  54 /** Coinbase transaction outputs can only be spent after this number of new blocks (network rule) */
  55 static const int COINBASE_MATURITY = 100;
  56 /** Threshold for nLockTime: below this value it is interpreted as block number, otherwise as UNIX timestamp. */
  57 static const unsigned int LOCKTIME_THRESHOLD = 500000000; // Tue Nov  5 00:53:20 1985 UTC
  58 /** Maximum number of script-checking threads allowed */
  59 static const int MAX_SCRIPTCHECK_THREADS = 16;
  60 #ifdef USE_UPNP
  61 static const int fHaveUPnP = true;
  62 #else
  63 static const int fHaveUPnP = false;
  64 #endif
  65
  66
  67 extern CScript COINBASE_FLAGS;
  68
  69
  70
  71
  72
  73
  74 extern CCriticalSection cs_main;
  75 extern std::map<uint256, CBlockIndex*> mapBlockIndex;
  76 extern std::set<CBlockIndex*, CBlockIndexWorkComparator> setBlockIndexValid;
  77 extern uint256 hashGenesisBlock;
  78 extern CBlockIndex* pindexGenesisBlock;
  79 extern int nBestHeight;
  80 extern CBigNum bnBestChainWork;
  81 extern CBigNum bnBestInvalidWork;
  82 extern uint256 hashBestChain;
  83 extern CBlockIndex* pindexBest;
  84 extern unsigned int nTransactionsUpdated;
  85 extern uint64 nLastBlockTx;
  86 extern uint64 nLastBlockSize;
  87 extern const std::string strMessageMagic;
  88 extern double dHashesPerSec;
  89 extern int64 nHPSTimerStart;
  90 extern int64 nTimeBestReceived;
  91 extern CCriticalSection cs_setpwalletRegistered;
  92 extern std::set<CWallet*> setpwalletRegistered;
  93 extern unsigned char pchMessageStart[4];
  94 extern bool fImporting;
  95 extern bool fReindex;
  96 extern bool fBenchmark;
  97 extern int nScriptCheckThreads;
  98 extern bool fTxIndex;
  99 extern unsigned int nCoinCacheSize;
 100
 101 // Settings
 102 extern int64 nTransactionFee;
 103
 104 // Minimum disk space required - used in CheckDiskSpace()
 105 static const uint64 nMinDiskSpace = 52428800;
 106
 107
 108 class CReserveKey;
 109 class CCoinsDB;
 110 class CBlockTreeDB;
 111 struct CDiskBlockPos;
 112 class CCoins;
 113 class CTxUndo;
 114 class CCoinsView;
 115 class CCoinsViewCache;
 116 class CScriptCheck;
 117 class CValidationState;
 118
 119 struct CBlockTemplate;
 120
 121
 122 /** Register a wallet to receive updates from core */
 123 void RegisterWallet(CWallet* pwalletIn);
 124 /** Unregister a wallet from core */
 125 void UnregisterWallet(CWallet* pwalletIn);
 126 /** Push an updated transaction to all registered wallets */
 127 void SyncWithWallets(const uint256 &hash, const CTransaction& tx, const CBlock* pblock = NULL, bool fUpdate = false);
 128 /** Process an incoming block */
 129 bool ProcessBlock(CValidationState &state, CNode* pfrom, CBlock* pblock, CDiskBlockPos *dbp = NULL);
 130 /** Check whether enough disk space is available for an incoming block */
 131 bool CheckDiskSpace(uint64 nAdditionalBytes = 0);
 132 /** Open a block file (blk?????.dat) */
 133 FILE* OpenBlockFile(const CDiskBlockPos &pos, bool fReadOnly = false);
 134 /** Open an undo file (rev?????.dat) */
 135 FILE* OpenUndoFile(const CDiskBlockPos &pos, bool fReadOnly = false);
 136 /** Import blocks from an external file */
 137 bool LoadExternalBlockFile(FILE* fileIn, CDiskBlockPos *dbp = NULL);
 138 /** Initialize a new block tree database + block data on disk */
 139 bool InitBlockIndex();
 140 /** Load the block tree and coins database from disk */
 141 bool LoadBlockIndex();
 142 /** Unload database information */
 143 void UnloadBlockIndex();
 144 /** Verify consistency of the block and coin databases */
 145 bool VerifyDB();
 146 /** Print the loaded block tree */
 147 void PrintBlockTree();
 148 /** Find a block by height in the currently-connected chain */
 149 CBlockIndex* FindBlockByHeight(int nHeight);
 150 /** Process protocol messages received from a given node */
 151 bool ProcessMessages(CNode* pfrom);
 152 /** Send queued protocol messages to be sent to a give node */
 153 bool SendMessages(CNode* pto, bool fSendTrickle);
 154 /** Run the importer thread, which deals with reindexing, loading bootstrap.dat, and whatever is passed to -loadblock */
 155 void ThreadImport(void *parg);
 156 /** Run an instance of the script checking thread */
 157 void ThreadScriptCheck(void* parg);
 158 /** Stop the script checking threads */
 159 void ThreadScriptCheckQuit();
 160 /** Run the miner threads */
 161 void GenerateBitcoins(bool fGenerate, CWallet* pwallet);
 162 /** Generate a new block, without valid proof-of-work */
 163 CBlockTemplate* CreateNewBlock(CReserveKey& reservekey);
 164 /** Modify the extranonce in a block */
 165 void IncrementExtraNonce(CBlock* pblock, CBlockIndex* pindexPrev, unsigned int& nExtraNonce);
 166 /** Do mining precalculation */
 167 void FormatHashBuffers(CBlock* pblock, char* pmidstate, char* pdata, char* phash1);
 168 /** Check mined block */
 169 bool CheckWork(CBlock* pblock, CWallet& wallet, CReserveKey& reservekey);
 170 /** Check whether a block hash satisfies the proof-of-work requirement specified by nBits */
 171 bool CheckProofOfWork(uint256 hash, unsigned int nBits);
 172 /** Calculate the minimum amount of work a received block needs, without knowing its direct parent */
 173 unsigned int ComputeMinWork(unsigned int nBase, int64 nTime);
 174 /** Get the number of active peers */
 175 int GetNumBlocksOfPeers();
 176 /** Check whether we are doing an initial block download (synchronizing from disk or network) */
 177 bool IsInitialBlockDownload();
 178 /** Format a string that describes several potential problems detected by the core */
 179 std::string GetWarnings(std::string strFor);
 180 /** Retrieve a transaction (from memory pool, or from disk, if possible) */
 181 bool GetTransaction(const uint256 &hash, CTransaction &tx, uint256 &hashBlock, bool fAllowSlow = false);
 182 /** Connect/disconnect blocks until pindexNew is the new tip of the active block chain */
 183 bool SetBestChain(CValidationState &state, CBlockIndex* pindexNew);
 184 /** Find the best known block, and make it the tip of the block chain */
 185 bool ConnectBestBlock(CValidationState &state);
 186 /** Create a new block index entry for a given block hash */
 187 CBlockIndex * InsertBlockIndex(uint256 hash);
 188 /** Verify a signature */
 189 bool VerifySignature(const CCoins& txFrom, const CTransaction& txTo, unsigned int nIn, unsigned int flags, int nHashType);
 190 /** Abort with a message */
 191 bool AbortNode(const std::string &msg);
 192
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203 static inline std::string BlockHashStr(const uint256& hash)
 204 {
 205     return hash.ToString();
 206 }
 207
 208 bool GetWalletFile(CWallet* pwallet, std::string &strWalletFileOut);
 209
 210 struct CDiskBlockPos
 211 {
 212     int nFile;
 213     unsigned int nPos;
 214
 215     IMPLEMENT_SERIALIZE(
 216         READWRITE(VARINT(nFile));
 217         READWRITE(VARINT(nPos));
 218     )
 219
 220     CDiskBlockPos() {
 221         SetNull();
 222     }
 223
 224     CDiskBlockPos(int nFileIn, unsigned int nPosIn) {
 225         nFile = nFileIn;
 226         nPos = nPosIn;
 227     }
 228
 229     friend bool operator==(const CDiskBlockPos &a, const CDiskBlockPos &b) {
 230         return (a.nFile == b.nFile && a.nPos == b.nPos);
 231     }
 232
 233     friend bool operator!=(const CDiskBlockPos &a, const CDiskBlockPos &b) {
 234         return !(a == b);
 235     }
 236
 237     void SetNull() { nFile = -1; nPos = 0; }
 238     bool IsNull() const { return (nFile == -1); }
 239 };
 240
 241 struct CDiskTxPos : public CDiskBlockPos
 242 {
 243     unsigned int nTxOffset; // after header
 244
 245     IMPLEMENT_SERIALIZE(
 246         READWRITE(*(CDiskBlockPos*)this);
 247         READWRITE(VARINT(nTxOffset));
 248     )
 249
 250     CDiskTxPos(const CDiskBlockPos &blockIn, unsigned int nTxOffsetIn) : CDiskBlockPos(blockIn.nFile, blockIn.nPos), nTxOffset(nTxOffsetIn) {
 251     }
 252
 253     CDiskTxPos() {
 254         SetNull();
 255     }
 256
 257     void SetNull() {
 258         CDiskBlockPos::SetNull();
 259         nTxOffset = 0;
 260     }
 261 };
 262
 263
 264 /** An inpoint - a combination of a transaction and an index n into its vin */
 265 class CInPoint
 266 {
 267 public:
 268     CTransaction* ptx;
 269     unsigned int n;
 270
 271     CInPoint() { SetNull(); }
 272     CInPoint(CTransaction* ptxIn, unsigned int nIn) { ptx = ptxIn; n = nIn; }
 273     void SetNull() { ptx = NULL; n = (unsigned int) -1; }
 274     bool IsNull() const { return (ptx == NULL && n == (unsigned int) -1); }
 275 };
 276
 277
 278
 279 /** An outpoint - a combination of a transaction hash and an index n into its vout */
 280 class COutPoint
 281 {
 282 public:
 283     uint256 hash;
 284     unsigned int n;
 285
 286     COutPoint() { SetNull(); }
 287     COutPoint(uint256 hashIn, unsigned int nIn) { hash = hashIn; n = nIn; }
 288     IMPLEMENT_SERIALIZE( READWRITE(FLATDATA(*this)); )
 289     void SetNull() { hash = 0; n = (unsigned int) -1; }
 290     bool IsNull() const { return (hash == 0 && n == (unsigned int) -1); }
 291
 292     friend bool operator<(const COutPoint& a, const COutPoint& b)
 293     {
 294         return (a.hash < b.hash || (a.hash == b.hash && a.n < b.n));
 295     }
 296
 297     friend bool operator==(const COutPoint& a, const COutPoint& b)
 298     {
 299         return (a.hash == b.hash && a.n == b.n);
 300     }
 301
 302     friend bool operator!=(const COutPoint& a, const COutPoint& b)
 303     {
 304         return !(a == b);
 305     }
 306
 307     std::string ToString() const
 308     {
 309         return strprintf("COutPoint(%s, %u)", hash.ToString().substr(0,10).c_str(), n);
 310     }
 311
 312     void print() const
 313     {
 314         printf("%s\n", ToString().c_str());
 315     }
 316 };
 317
 318
 319
 320
 321 /** An input of a transaction.  It contains the location of the previous
 322  * transaction's output that it claims and a signature that matches the
 323  * output's public key.
 324  */
 325 class CTxIn
 326 {
 327 public:
 328     COutPoint prevout;
 329     CScript scriptSig;
 330     unsigned int nSequence;
 331
 332     CTxIn()
 333     {
 334         nSequence = std::numeric_limits<unsigned int>::max();
 335     }
 336
 337     explicit CTxIn(COutPoint prevoutIn, CScript scriptSigIn=CScript(), unsigned int nSequenceIn=std::numeric_limits<unsigned int>::max())
 338     {
 339         prevout = prevoutIn;
 340         scriptSig = scriptSigIn;
 341         nSequence = nSequenceIn;
 342     }
 343
 344     CTxIn(uint256 hashPrevTx, unsigned int nOut, CScript scriptSigIn=CScript(), unsigned int nSequenceIn=std::numeric_limits<unsigned int>::max())
 345     {
 346         prevout = COutPoint(hashPrevTx, nOut);
 347         scriptSig = scriptSigIn;
 348         nSequence = nSequenceIn;
 349     }
 350
 351     IMPLEMENT_SERIALIZE
 352     (
 353         READWRITE(prevout);
 354         READWRITE(scriptSig);
 355         READWRITE(nSequence);
 356     )
 357
 358     bool IsFinal() const
 359     {
 360         return (nSequence == std::numeric_limits<unsigned int>::max());
 361     }
 362
 363     friend bool operator==(const CTxIn& a, const CTxIn& b)
 364     {
 365         return (a.prevout   == b.prevout &&
 366                 a.scriptSig == b.scriptSig &&
 367                 a.nSequence == b.nSequence);
 368     }
 369
 370     friend bool operator!=(const CTxIn& a, const CTxIn& b)
 371     {
 372         return !(a == b);
 373     }
 374
 375     std::string ToString() const
 376     {
 377         std::string str;
 378         str += "CTxIn(";
 379         str += prevout.ToString();
 380         if (prevout.IsNull())
 381             str += strprintf(", coinbase %s", HexStr(scriptSig).c_str());
 382         else
 383             str += strprintf(", scriptSig=%s", scriptSig.ToString().substr(0,24).c_str());
 384         if (nSequence != std::numeric_limits<unsigned int>::max())
 385             str += strprintf(", nSequence=%u", nSequence);
 386         str += ")";
 387         return str;
 388     }
 389
 390     void print() const
 391     {
 392         printf("%s\n", ToString().c_str());
 393     }
 394 };
 395
 396
 397
 398
 399 /** An output of a transaction.  It contains the public key that the next input
 400  * must be able to sign with to claim it.
 401  */
 402 class CTxOut
 403 {
 404 public:
 405     int64 nValue;
 406     CScript scriptPubKey;
 407
 408     CTxOut()
 409     {
 410         SetNull();
 411     }
 412
 413     CTxOut(int64 nValueIn, CScript scriptPubKeyIn)
 414     {
 415         nValue = nValueIn;
 416         scriptPubKey = scriptPubKeyIn;
 417     }
 418
 419     IMPLEMENT_SERIALIZE
 420     (
 421         READWRITE(nValue);
 422         READWRITE(scriptPubKey);
 423     )
 424
 425     void SetNull()
 426     {
 427         nValue = -1;
 428         scriptPubKey.clear();
 429     }
 430
 431     bool IsNull() const
 432     {
 433         return (nValue == -1);
 434     }
 435
 436     uint256 GetHash() const
 437     {
 438         return SerializeHash(*this);
 439     }
 440
 441     friend bool operator==(const CTxOut& a, const CTxOut& b)
 442     {
 443         return (a.nValue       == b.nValue &&
 444                 a.scriptPubKey == b.scriptPubKey);
 445     }
 446
 447     friend bool operator!=(const CTxOut& a, const CTxOut& b)
 448     {
 449         return !(a == b);
 450     }
 451
 452     std::string ToString() const
 453     {
 454         if (scriptPubKey.size() < 6)
 455             return "CTxOut(error)";
 456         return strprintf("CTxOut(nValue=%"PRI64d".%08"PRI64d", scriptPubKey=%s)", nValue / COIN, nValue % COIN, scriptPubKey.ToString().substr(0,30).c_str());
 457     }
 458
 459     void print() const
 460     {
 461         printf("%s\n", ToString().c_str());
 462     }
 463 };
 464
 465
 466
 467 enum GetMinFee_mode
 468 {
 469     GMF_BLOCK,
 470     GMF_RELAY,
 471     GMF_SEND,
 472 };
 473
 474 /** The basic transaction that is broadcasted on the network and contained in
 475  * blocks. A transaction can contain multiple inputs and outputs.
 476  */
 477 class CTransaction
 478 {
 479 public:
 480     static const int CURRENT_VERSION=1;
 481     int nVersion;
 482     std::vector<CTxIn> vin;
 483     std::vector<CTxOut> vout;
 484     unsigned int nLockTime;
 485
 486     CTransaction()
 487     {
 488         SetNull();
 489     }
 490
 491     IMPLEMENT_SERIALIZE
 492     (
 493         READWRITE(this->nVersion);
 494         nVersion = this->nVersion;
 495         READWRITE(vin);
 496         READWRITE(vout);
 497         READWRITE(nLockTime);
 498     )
 499
 500     void SetNull()
 501     {
 502         nVersion = CTransaction::CURRENT_VERSION;
 503         vin.clear();
 504         vout.clear();
 505         nLockTime = 0;
 506     }
 507
 508     bool IsNull() const
 509     {
 510         return (vin.empty() && vout.empty());
 511     }
 512
 513     uint256 GetHash() const
 514     {
 515         return SerializeHash(*this);
 516     }
 517
 518     bool IsFinal(int nBlockHeight=0, int64 nBlockTime=0) const
 519     {
 520         // Time based nLockTime implemented in 0.1.6
 521         if (nLockTime == 0)
 522             return true;
 523         if (nBlockHeight == 0)
 524             nBlockHeight = nBestHeight;
 525         if (nBlockTime == 0)
 526             nBlockTime = GetAdjustedTime();
 527         if ((int64)nLockTime < ((int64)nLockTime < LOCKTIME_THRESHOLD ? (int64)nBlockHeight : nBlockTime))
 528             return true;
 529         BOOST_FOREACH(const CTxIn& txin, vin)
 530             if (!txin.IsFinal())
 531                 return false;
 532         return true;
 533     }
 534
 535     bool IsNewerThan(const CTransaction& old) const
 536     {
 537         if (vin.size() != old.vin.size())
 538             return false;
 539         for (unsigned int i = 0; i < vin.size(); i++)
 540             if (vin[i].prevout != old.vin[i].prevout)
 541                 return false;
 542
 543         bool fNewer = false;
 544         unsigned int nLowest = std::numeric_limits<unsigned int>::max();
 545         for (unsigned int i = 0; i < vin.size(); i++)
 546         {
 547             if (vin[i].nSequence != old.vin[i].nSequence)
 548             {
 549                 if (vin[i].nSequence <= nLowest)
 550                 {
 551                     fNewer = false;
 552                     nLowest = vin[i].nSequence;
 553                 }
 554                 if (old.vin[i].nSequence < nLowest)
 555                 {
 556                     fNewer = true;
 557                     nLowest = old.vin[i].nSequence;
 558                 }
 559             }
 560         }
 561         return fNewer;
 562     }
 563
 564     bool IsCoinBase() const
 565     {
 566         return (vin.size() == 1 && vin[0].prevout.IsNull());
 567     }
 568
 569     /** Check for standard transaction types
 570         @return True if all outputs (scriptPubKeys) use only standard transaction forms
 571     */
 572     bool IsStandard() const;
 573
 574     /** Check for standard transaction types
 575         @param[in] mapInputs    Map of previous transactions that have outputs we're spending
 576         @return True if all inputs (scriptSigs) use only standard transaction forms
 577     */
 578     bool AreInputsStandard(CCoinsViewCache& mapInputs) const;
 579
 580     /** Count ECDSA signature operations the old-fashioned (pre-0.6) way
 581         @return number of sigops this transaction's outputs will produce when spent
 582     */
 583     unsigned int GetLegacySigOpCount() const;
 584
 585     /** Count ECDSA signature operations in pay-to-script-hash inputs.
 586
 587         @param[in] mapInputs    Map of previous transactions that have outputs we're spending
 588         @return maximum number of sigops required to validate this transaction's inputs
 589      */
 590     unsigned int GetP2SHSigOpCount(CCoinsViewCache& mapInputs) const;
 591
 592     /** Amount of bitcoins spent by this transaction.
 593         @return sum of all outputs (note: does not include fees)
 594      */
 595     int64 GetValueOut() const
 596     {
 597         int64 nValueOut = 0;
 598         BOOST_FOREACH(const CTxOut& txout, vout)
 599         {
 600             nValueOut += txout.nValue;
 601             if (!MoneyRange(txout.nValue) || !MoneyRange(nValueOut))
 602                 throw std::runtime_error("CTransaction::GetValueOut() : value out of range");
 603         }
 604         return nValueOut;
 605     }
 606
 607     /** Amount of bitcoins coming in to this transaction
 608         Note that lightweight clients may not know anything besides the hash of previous transactions,
 609         so may not be able to calculate this.
 610
 611         @param[in] mapInputs    Map of previous transactions that have outputs we're spending
 612         @return Sum of value of all inputs (scriptSigs)
 613      */
 614     int64 GetValueIn(CCoinsViewCache& mapInputs) const;
 615
 616     static bool AllowFree(double dPriority)
 617     {
 618         // Large (in bytes) low-priority (new, small-coin) transactions
 619         // need a fee.
 620         return dPriority > COIN * 144 / 250;
 621     }
 622
 623     int64 GetMinFee(unsigned int nBlockSize=1, bool fAllowFree=true, enum GetMinFee_mode mode=GMF_BLOCK) const;
 624
 625     friend bool operator==(const CTransaction& a, const CTransaction& b)
 626     {
 627         return (a.nVersion  == b.nVersion &&
 628                 a.vin       == b.vin &&
 629                 a.vout      == b.vout &&
 630                 a.nLockTime == b.nLockTime);
 631     }
 632
 633     friend bool operator!=(const CTransaction& a, const CTransaction& b)
 634     {
 635         return !(a == b);
 636     }
 637
 638
 639     std::string ToString() const
 640     {
 641         std::string str;
 642         str += strprintf("CTransaction(hash=%s, ver=%d, vin.size=%"PRIszu", vout.size=%"PRIszu", nLockTime=%u)\n",
 643             GetHash().ToString().substr(0,10).c_str(),
 644             nVersion,
 645             vin.size(),
 646             vout.size(),
 647             nLockTime);
 648         for (unsigned int i = 0; i < vin.size(); i++)
 649             str += "    " + vin[i].ToString() + "\n";
 650         for (unsigned int i = 0; i < vout.size(); i++)
 651             str += "    " + vout[i].ToString() + "\n";
 652         return str;
 653     }
 654
 655     void print() const
 656     {
 657         printf("%s", ToString().c_str());
 658     }
 659
 660
 661     // Check whether all prevouts of this transaction are present in the UTXO set represented by view
 662     bool HaveInputs(CCoinsViewCache &view) const;
 663
 664     // Check whether all inputs of this transaction are valid (no double spends, scripts & sigs, amounts)
 665     // This does not modify the UTXO set. If pvChecks is not NULL, script checks are pushed onto it
 666     // instead of being performed inline.
 667     bool CheckInputs(CValidationState &state, CCoinsViewCache &view, bool fScriptChecks = true,
 668                      unsigned int flags = SCRIPT_VERIFY_P2SH | SCRIPT_VERIFY_STRICTENC,
 669                      std::vector<CScriptCheck> *pvChecks = NULL) const;
 670
 671     // Apply the effects of this transaction on the UTXO set represented by view
 672     bool UpdateCoins(CValidationState &state, CCoinsViewCache &view, CTxUndo &txundo, int nHeight, const uint256 &txhash) const;
 673
 674     // Context-independent validity checks
 675     bool CheckTransaction(CValidationState &state) const;
 676
 677     // Try to accept this transaction into the memory pool
 678     bool AcceptToMemoryPool(CValidationState &state, bool fCheckInputs=true, bool fLimitFree = true, bool* pfMissingInputs=NULL);
 679
 680 protected:
 681     static const CTxOut &GetOutputFor(const CTxIn& input, CCoinsViewCache& mapInputs);
 682 };
 683
 684 /** wrapper for CTxOut that provides a more compact serialization */
 685 class CTxOutCompressor
 686 {
 687 private:
 688     CTxOut &txout;
 689
 690 public:
 691     static uint64 CompressAmount(uint64 nAmount);
 692     static uint64 DecompressAmount(uint64 nAmount);
 693
 694     CTxOutCompressor(CTxOut &txoutIn) : txout(txoutIn) { }
 695
 696     IMPLEMENT_SERIALIZE(({
 697         if (!fRead) {
 698             uint64 nVal = CompressAmount(txout.nValue);
 699             READWRITE(VARINT(nVal));
 700         } else {
 701             uint64 nVal = 0;
 702             READWRITE(VARINT(nVal));
 703             txout.nValue = DecompressAmount(nVal);
 704         }
 705         CScriptCompressor cscript(REF(txout.scriptPubKey));
 706         READWRITE(cscript);
 707     });)
 708 };
 709
 710 /** Undo information for a CTxIn
 711  *
 712  *  Contains the prevout's CTxOut being spent, and if this was the
 713  *  last output of the affected transaction, its metadata as well
 714  *  (coinbase or not, height, transaction version)
 715  */
 716 class CTxInUndo
 717 {
 718 public:
 719     CTxOut txout;         // the txout data before being spent
 720     bool fCoinBase;       // if the outpoint was the last unspent: whether it belonged to a coinbase
 721     unsigned int nHeight; // if the outpoint was the last unspent: its height
 722     int nVersion;         // if the outpoint was the last unspent: its version
 723
 724     CTxInUndo() : txout(), fCoinBase(false), nHeight(0), nVersion(0) {}
 725     CTxInUndo(const CTxOut &txoutIn, bool fCoinBaseIn = false, unsigned int nHeightIn = 0, int nVersionIn = 0) : txout(txoutIn), fCoinBase(fCoinBaseIn), nHeight(nHeightIn), nVersion(nVersionIn) { }
 726
 727     unsigned int GetSerializeSize(int nType, int nVersion) const {
 728         return ::GetSerializeSize(VARINT(nHeight*2+(fCoinBase ? 1 : 0)), nType, nVersion) +
 729                (nHeight > 0 ? ::GetSerializeSize(VARINT(this->nVersion), nType, nVersion) : 0) +
 730                ::GetSerializeSize(CTxOutCompressor(REF(txout)), nType, nVersion);
 731     }
 732
 733     template<typename Stream>
 734     void Serialize(Stream &s, int nType, int nVersion) const {
 735         ::Serialize(s, VARINT(nHeight*2+(fCoinBase ? 1 : 0)), nType, nVersion);
 736         if (nHeight > 0)
 737             ::Serialize(s, VARINT(this->nVersion), nType, nVersion);
 738         ::Serialize(s, CTxOutCompressor(REF(txout)), nType, nVersion);
 739     }
 740
 741     template<typename Stream>
 742     void Unserialize(Stream &s, int nType, int nVersion) {
 743         unsigned int nCode = 0;
 744         ::Unserialize(s, VARINT(nCode), nType, nVersion);
 745         nHeight = nCode / 2;
 746         fCoinBase = nCode & 1;
 747         if (nHeight > 0)
 748             ::Unserialize(s, VARINT(this->nVersion), nType, nVersion);
 749         ::Unserialize(s, REF(CTxOutCompressor(REF(txout))), nType, nVersion);
 750     }
 751 };
 752
 753 /** Undo information for a CTransaction */
 754 class CTxUndo
 755 {
 756 public:
 757     // undo information for all txins
 758     std::vector<CTxInUndo> vprevout;
 759
 760     IMPLEMENT_SERIALIZE(
 761         READWRITE(vprevout);
 762     )
 763 };
 764
 765 /** Undo information for a CBlock */
 766 class CBlockUndo
 767 {
 768 public:
 769     std::vector<CTxUndo> vtxundo; // for all but the coinbase
 770
 771     IMPLEMENT_SERIALIZE(
 772         READWRITE(vtxundo);
 773     )
 774
 775     bool WriteToDisk(CDiskBlockPos &pos, const uint256 &hashBlock)
 776     {
 777         // Open history file to append
 778         CAutoFile fileout = CAutoFile(OpenUndoFile(pos), SER_DISK, CLIENT_VERSION);
 779         if (!fileout)
 780             return error("CBlockUndo::WriteToDisk() : OpenUndoFile failed");
 781
 782         // Write index header
 783         unsigned int nSize = fileout.GetSerializeSize(*this);
 784         fileout << FLATDATA(pchMessageStart) << nSize;
 785
 786         // Write undo data
 787         long fileOutPos = ftell(fileout);
 788         if (fileOutPos < 0)
 789             return error("CBlockUndo::WriteToDisk() : ftell failed");
 790         pos.nPos = (unsigned int)fileOutPos;
 791         fileout << *this;
 792
 793         // calculate & write checksum
 794         CHashWriter hasher(SER_GETHASH, PROTOCOL_VERSION);
 795         hasher << hashBlock;
 796         hasher << *this;
 797         fileout << hasher.GetHash();
 798
 799         // Flush stdio buffers and commit to disk before returning
 800         fflush(fileout);
 801         if (!IsInitialBlockDownload())
 802             FileCommit(fileout);
 803
 804         return true;
 805     }
 806
 807     bool ReadFromDisk(const CDiskBlockPos &pos, const uint256 &hashBlock)
 808     {
 809         // Open history file to read
 810         CAutoFile filein = CAutoFile(OpenUndoFile(pos, true), SER_DISK, CLIENT_VERSION);
 811         if (!filein)
 812             return error("CBlockUndo::ReadFromDisk() : OpenBlockFile failed");
 813
 814         // Read block
 815         uint256 hashChecksum;
 816         try {
 817             filein >> *this;
 818             filein >> hashChecksum;
 819         }
 820         catch (std::exception &e) {
 821             return error("%s() : deserialize or I/O error", __PRETTY_FUNCTION__);
 822         }
 823
 824         // Verify checksum
 825         CHashWriter hasher(SER_GETHASH, PROTOCOL_VERSION);
 826         hasher << hashBlock;
 827         hasher << *this;
 828         if (hashChecksum != hasher.GetHash())
 829             return error("CBlockUndo::ReadFromDisk() : checksum mismatch");
 830
 831         return true;
 832     }
 833 };
 834
 835 /** pruned version of CTransaction: only retains metadata and unspent transaction outputs
 836  *
 837  * Serialized format:
 838  * - VARINT(nVersion)
 839  * - VARINT(nCode)
 840  * - unspentness bitvector, for vout[2] and further; least significant byte first
 841  * - the non-spent CTxOuts (via CTxOutCompressor)
 842  * - VARINT(nHeight)
 843  *
 844  * The nCode value consists of:
 845  * - bit 1: IsCoinBase()
 846  * - bit 2: vout[0] is not spent
 847  * - bit 4: vout[1] is not spent
 848  * - The higher bits encode N, the number of non-zero bytes in the following bitvector.
 849  *   - In case both bit 2 and bit 4 are unset, they encode N-1, as there must be at
 850  *     least one non-spent output).
 851  *
 852  * Example: 0104835800816115944e077fe7c803cfa57f29b36bf87c1d358bb85e
 853  *          <><><--------------------------------------------><---->
 854  *          |  \                  |                             /
 855  *    version   code             vout[1]                  height
 856  *
 857  *    - version = 1
 858  *    - code = 4 (vout[1] is not spent, and 0 non-zero bytes of bitvector follow)
 859  *    - unspentness bitvector: as 0 non-zero bytes follow, it has length 0
 860  *    - vout[1]: 835800816115944e077fe7c803cfa57f29b36bf87c1d35
 861  *               * 8358: compact amount representation for 60000000000 (600 BTC)
 862  *               * 00: special txout type pay-to-pubkey-hash
 863  *               * 816115944e077fe7c803cfa57f29b36bf87c1d35: address uint160
 864  *    - height = 203998
 865  *
 866  *
 867  * Example: 0109044086ef97d5790061b01caab50f1b8e9c50a5057eb43c2d9563a4eebbd123008c988f1a4a4de2161e0f50aac7f17e7f9555caa486af3b
 868  *          <><><--><--------------------------------------------------><----------------------------------------------><---->
 869  *         /  \   \                     |                                                           |                     /
 870  *  version  code  unspentness       vout[4]                                                     vout[16]           height
 871  *
 872  *  - version = 1
 873  *  - code = 9 (coinbase, neither vout[0] or vout[1] are unspent,
 874  *                2 (1, +1 because both bit 2 and bit 4 are unset) non-zero bitvector bytes follow)
 875  *  - unspentness bitvector: bits 2 (0x04) and 14 (0x4000) are set, so vout[2+2] and vout[14+2] are unspent
 876  *  - vout[4]: 86ef97d5790061b01caab50f1b8e9c50a5057eb43c2d9563a4ee
 877  *             * 86ef97d579: compact amount representation for 234925952 (2.35 BTC)
 878  *             * 00: special txout type pay-to-pubkey-hash
 879  *             * 61b01caab50f1b8e9c50a5057eb43c2d9563a4ee: address uint160
 880  *  - vout[16]: bbd123008c988f1a4a4de2161e0f50aac7f17e7f9555caa4
 881  *              * bbd123: compact amount representation for 110397 (0.001 BTC)
 882  *              * 00: special txout type pay-to-pubkey-hash
 883  *              * 8c988f1a4a4de2161e0f50aac7f17e7f9555caa4: address uint160
 884  *  - height = 120891
 885  */
 886 class CCoins
 887 {
 888 public:
 889     // whether transaction is a coinbase
 890     bool fCoinBase;
 891
 892     // unspent transaction outputs; spent outputs are .IsNull(); spent outputs at the end of the array are dropped
 893     std::vector<CTxOut> vout;
 894
 895     // at which height this transaction was included in the active block chain
 896     int nHeight;
 897
 898     // version of the CTransaction; accesses to this value should probably check for nHeight as well,
 899     // as new tx version will probably only be introduced at certain heights
 900     int nVersion;
 901
 902     // construct a CCoins from a CTransaction, at a given height
 903     CCoins(const CTransaction &tx, int nHeightIn) : fCoinBase(tx.IsCoinBase()), vout(tx.vout), nHeight(nHeightIn), nVersion(tx.nVersion) { }
 904
 905     // empty constructor
 906     CCoins() : fCoinBase(false), vout(0), nHeight(0), nVersion(0) { }
 907
 908     // remove spent outputs at the end of vout
 909     void Cleanup() {
 910         while (vout.size() > 0 && vout.back().IsNull())
 911             vout.pop_back();
 912     }
 913
 914     // equality test
 915     friend bool operator==(const CCoins &a, const CCoins &b) {
 916          return a.fCoinBase == b.fCoinBase &&
 917                 a.nHeight == b.nHeight &&
 918                 a.nVersion == b.nVersion &&
 919                 a.vout == b.vout;
 920     }
 921     friend bool operator!=(const CCoins &a, const CCoins &b) {
 922         return !(a == b);
 923     }
 924
 925     // calculate number of bytes for the bitmask, and its number of non-zero bytes
 926     // each bit in the bitmask represents the availability of one output, but the
 927     // availabilities of the first two outputs are encoded separately
 928     void CalcMaskSize(unsigned int &nBytes, unsigned int &nNonzeroBytes) const {
 929         unsigned int nLastUsedByte = 0;
 930         for (unsigned int b = 0; 2+b*8 < vout.size(); b++) {
 931             bool fZero = true;
 932             for (unsigned int i = 0; i < 8 && 2+b*8+i < vout.size(); i++) {
 933                 if (!vout[2+b*8+i].IsNull()) {
 934                     fZero = false;
 935                     continue;
 936                 }
 937             }
 938             if (!fZero) {
 939                 nLastUsedByte = b + 1;
 940                 nNonzeroBytes++;
 941             }
 942         }
 943         nBytes += nLastUsedByte;
 944     }
 945
 946     bool IsCoinBase() const {
 947         return fCoinBase;
 948     }
 949
 950     unsigned int GetSerializeSize(int nType, int nVersion) const {
 951         unsigned int nSize = 0;
 952         unsigned int nMaskSize = 0, nMaskCode = 0;
 953         CalcMaskSize(nMaskSize, nMaskCode);
 954         bool fFirst = vout.size() > 0 && !vout[0].IsNull();
 955         bool fSecond = vout.size() > 1 && !vout[1].IsNull();
 956         assert(fFirst || fSecond || nMaskCode);
 957         unsigned int nCode = 8*(nMaskCode - (fFirst || fSecond ? 0 : 1)) + (fCoinBase ? 1 : 0) + (fFirst ? 2 : 0) + (fSecond ? 4 : 0);
 958         // version
 959         nSize += ::GetSerializeSize(VARINT(this->nVersion), nType, nVersion);
 960         // size of header code
 961         nSize += ::GetSerializeSize(VARINT(nCode), nType, nVersion);
 962         // spentness bitmask
 963         nSize += nMaskSize;
 964         // txouts themself
 965         for (unsigned int i = 0; i < vout.size(); i++)
 966             if (!vout[i].IsNull())
 967                 nSize += ::GetSerializeSize(CTxOutCompressor(REF(vout[i])), nType, nVersion);
 968         // height
 969         nSize += ::GetSerializeSize(VARINT(nHeight), nType, nVersion);
 970         return nSize;
 971     }
 972
 973     template<typename Stream>
 974     void Serialize(Stream &s, int nType, int nVersion) const {
 975         unsigned int nMaskSize = 0, nMaskCode = 0;
 976         CalcMaskSize(nMaskSize, nMaskCode);
 977         bool fFirst = vout.size() > 0 && !vout[0].IsNull();
 978         bool fSecond = vout.size() > 1 && !vout[1].IsNull();
 979         assert(fFirst || fSecond || nMaskCode);
 980         unsigned int nCode = 8*(nMaskCode - (fFirst || fSecond ? 0 : 1)) + (fCoinBase ? 1 : 0) + (fFirst ? 2 : 0) + (fSecond ? 4 : 0);
 981         // version
 982         ::Serialize(s, VARINT(this->nVersion), nType, nVersion);
 983         // header code
 984         ::Serialize(s, VARINT(nCode), nType, nVersion);
 985         // spentness bitmask
 986         for (unsigned int b = 0; b<nMaskSize; b++) {
 987             unsigned char chAvail = 0;
 988             for (unsigned int i = 0; i < 8 && 2+b*8+i < vout.size(); i++)
 989                 if (!vout[2+b*8+i].IsNull())
 990                     chAvail |= (1 << i);
 991             ::Serialize(s, chAvail, nType, nVersion);
 992         }
 993         // txouts themself
 994         for (unsigned int i = 0; i < vout.size(); i++) {
 995             if (!vout[i].IsNull())
 996                 ::Serialize(s, CTxOutCompressor(REF(vout[i])), nType, nVersion);
 997         }
 998         // coinbase height
 999         ::Serialize(s, VARINT(nHeight), nType, nVersion);
1000     }
1001
1002     template<typename Stream>
1003     void Unserialize(Stream &s, int nType, int nVersion) {
1004         unsigned int nCode = 0;
1005         // version
1006         ::Unserialize(s, VARINT(this->nVersion), nType, nVersion);
1007         // header code
1008         ::Unserialize(s, VARINT(nCode), nType, nVersion);
1009         fCoinBase = nCode & 1;
1010         std::vector<bool> vAvail(2, false);
1011         vAvail[0] = nCode & 2;
1012         vAvail[1] = nCode & 4;
1013         unsigned int nMaskCode = (nCode / 8) + ((nCode & 6) != 0 ? 0 : 1);
1014         // spentness bitmask
1015         while (nMaskCode > 0) {
1016             unsigned char chAvail = 0;
1017             ::Unserialize(s, chAvail, nType, nVersion);
1018             for (unsigned int p = 0; p < 8; p++) {
1019                 bool f = (chAvail & (1 << p)) != 0;
1020                 vAvail.push_back(f);
1021             }
1022             if (chAvail != 0)
1023                 nMaskCode--;
1024         }
1025         // txouts themself
1026         vout.assign(vAvail.size(), CTxOut());
1027         for (unsigned int i = 0; i < vAvail.size(); i++) {
1028             if (vAvail[i])
1029                 ::Unserialize(s, REF(CTxOutCompressor(vout[i])), nType, nVersion);
1030         }
1031         // coinbase height
1032         ::Unserialize(s, VARINT(nHeight), nType, nVersion);
1033         Cleanup();
1034     }
1035
1036     // mark an outpoint spent, and construct undo information
1037     bool Spend(const COutPoint &out, CTxInUndo &undo) {
1038         if (out.n >= vout.size())
1039             return false;
1040         if (vout[out.n].IsNull())
1041             return false;
1042         undo = CTxInUndo(vout[out.n]);
1043         vout[out.n].SetNull();
1044         Cleanup();
1045         if (vout.size() == 0) {
1046             undo.nHeight = nHeight;
1047             undo.fCoinBase = fCoinBase;
1048             undo.nVersion = this->nVersion;
1049         }
1050         return true;
1051     }
1052
1053     // mark a vout spent
1054     bool Spend(int nPos) {
1055         CTxInUndo undo;
1056         COutPoint out(0, nPos);
1057         return Spend(out, undo);
1058     }
1059
1060     // check whether a particular output is still available
1061     bool IsAvailable(unsigned int nPos) const {
1062         return (nPos < vout.size() && !vout[nPos].IsNull());
1063     }
1064
1065     // check whether the entire CCoins is spent
1066     // note that only !IsPruned() CCoins can be serialized
1067     bool IsPruned() const {
1068         BOOST_FOREACH(const CTxOut &out, vout)
1069             if (!out.IsNull())
1070                 return false;
1071         return true;
1072     }
1073 };
1074
1075 /** Closure representing one script verification
1076  *  Note that this stores references to the spending transaction */
1077 class CScriptCheck
1078 {
1079 private:
1080     CScript scriptPubKey;
1081     const CTransaction *ptxTo;
1082     unsigned int nIn;
1083     unsigned int nFlags;
1084     int nHashType;
1085
1086 public:
1087     CScriptCheck() {}
1088     CScriptCheck(const CCoins& txFromIn, const CTransaction& txToIn, unsigned int nInIn, unsigned int nFlagsIn, int nHashTypeIn) :
1089         scriptPubKey(txFromIn.vout[txToIn.vin[nInIn].prevout.n].scriptPubKey),
1090         ptxTo(&txToIn), nIn(nInIn), nFlags(nFlagsIn), nHashType(nHashTypeIn) { }
1091
1092     bool operator()() const;
1093
1094     void swap(CScriptCheck &check) {
1095         scriptPubKey.swap(check.scriptPubKey);
1096         std::swap(ptxTo, check.ptxTo);
1097         std::swap(nIn, check.nIn);
1098         std::swap(nFlags, check.nFlags);
1099         std::swap(nHashType, check.nHashType);
1100     }
1101 };
1102
1103 /** A transaction with a merkle branch linking it to the block chain. */
1104 class CMerkleTx : public CTransaction
1105 {
1106 public:
1107     uint256 hashBlock;
1108     std::vector<uint256> vMerkleBranch;
1109     int nIndex;
1110
1111     // memory only
1112     mutable bool fMerkleVerified;
1113
1114
1115     CMerkleTx()
1116     {
1117         Init();
1118     }
1119
1120     CMerkleTx(const CTransaction& txIn) : CTransaction(txIn)
1121     {
1122         Init();
1123     }
1124
1125     void Init()
1126     {
1127         hashBlock = 0;
1128         nIndex = -1;
1129         fMerkleVerified = false;
1130     }
1131
1132
1133     IMPLEMENT_SERIALIZE
1134     (
1135         nSerSize += SerReadWrite(s, *(CTransaction*)this, nType, nVersion, ser_action);
1136         nVersion = this->nVersion;
1137         READWRITE(hashBlock);
1138         READWRITE(vMerkleBranch);
1139         READWRITE(nIndex);
1140     )
1141
1142
1143     int SetMerkleBranch(const CBlock* pblock=NULL);
1144     int GetDepthInMainChain(CBlockIndex* &pindexRet) const;
1145     int GetDepthInMainChain() const { CBlockIndex *pindexRet; return GetDepthInMainChain(pindexRet); }
1146     bool IsInMainChain() const { return GetDepthInMainChain() > 0; }
1147     int GetBlocksToMaturity() const;
1148     bool AcceptToMemoryPool(bool fCheckInputs=true, bool fLimitFree=true);
1149 };
1150
1151
1152
1153
1154
1155 /** Data structure that represents a partial merkle tree.
1156  *
1157  * It respresents a subset of the txid's of a known block, in a way that
1158  * allows recovery of the list of txid's and the merkle root, in an
1159  * authenticated way.
1160  *
1161  * The encoding works as follows: we traverse the tree in depth-first order,
1162  * storing a bit for each traversed node, signifying whether the node is the
1163  * parent of at least one matched leaf txid (or a matched txid itself). In
1164  * case we are at the leaf level, or this bit is 0, its merkle node hash is
1165  * stored, and its children are not explorer further. Otherwise, no hash is
1166  * stored, but we recurse into both (or the only) child branch. During
1167  * decoding, the same depth-first traversal is performed, consuming bits and
1168  * hashes as they written during encoding.
1169  *
1170  * The serialization is fixed and provides a hard guarantee about the
1171  * encoded size:
1172  *
1173  *   SIZE <= 10 + ceil(32.25*N)
1174  *
1175  * Where N represents the number of leaf nodes of the partial tree. N itself
1176  * is bounded by:
1177  *
1178  *   N <= total_transactions
1179  *   N <= 1 + matched_transactions*tree_height
1180  *
1181  * The serialization format:
1182  *  - uint32     total_transactions (4 bytes)
1183  *  - varint     number of hashes   (1-3 bytes)
1184  *  - uint256[]  hashes in depth-first order (<= 32*N bytes)
1185  *  - varint     number of bytes of flag bits (1-3 bytes)
1186  *  - byte[]     flag bits, packed per 8 in a byte, least significant bit first (<= 2*N-1 bits)
1187  * The size constraints follow from this.
1188  */
1189 class CPartialMerkleTree
1190 {
1191 protected:
1192     // the total number of transactions in the block
1193     unsigned int nTransactions;
1194
1195     // node-is-parent-of-matched-txid bits
1196     std::vector<bool> vBits;
1197
1198     // txids and internal hashes
1199     std::vector<uint256> vHash;
1200
1201     // flag set when encountering invalid data
1202     bool fBad;
1203
1204     // helper function to efficiently calculate the number of nodes at given height in the merkle tree
1205     unsigned int CalcTreeWidth(int height) {
1206         return (nTransactions+(1 << height)-1) >> height;
1207     }
1208
1209     // calculate the hash of a node in the merkle tree (at leaf level: the txid's themself)
1210     uint256 CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid);
1211
1212     // recursive function that traverses tree nodes, storing the data as bits and hashes
1213     void TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch);
1214
1215     // recursive function that traverses tree nodes, consuming the bits and hashes produced by TraverseAndBuild.
1216     // it returns the hash of the respective node.
1217     uint256 TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch);
1218
1219 public:
1220
1221     // serialization implementation
1222     IMPLEMENT_SERIALIZE(
1223         READWRITE(nTransactions);
1224         READWRITE(vHash);
1225         std::vector<unsigned char> vBytes;
1226         if (fRead) {
1227             READWRITE(vBytes);
1228             CPartialMerkleTree &us = *(const_cast<CPartialMerkleTree*>(this));
1229             us.vBits.resize(vBytes.size() * 8);
1230             for (unsigned int p = 0; p < us.vBits.size(); p++)
1231                 us.vBits[p] = (vBytes[p / 8] & (1 << (p % 8))) != 0;
1232             us.fBad = false;
1233         } else {
1234             vBytes.resize((vBits.size()+7)/8);
1235             for (unsigned int p = 0; p < vBits.size(); p++)
1236                 vBytes[p / 8] |= vBits[p] << (p % 8);
1237             READWRITE(vBytes);
1238         }
1239     )
1240
1241     // Construct a partial merkle tree from a list of transaction id's, and a mask that selects a subset of them
1242     CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch);
1243
1244     CPartialMerkleTree();
1245
1246     // extract the matching txid's represented by this partial merkle tree.
1247     // returns the merkle root, or 0 in case of failure
1248     uint256 ExtractMatches(std::vector<uint256> &vMatch);
1249 };
1250
1251
1252 /** Nodes collect new transactions into a block, hash them into a hash tree,
1253  * and scan through nonce values to make the block's hash satisfy proof-of-work
1254  * requirements.  When they solve the proof-of-work, they broadcast the block
1255  * to everyone and the block is added to the block chain.  The first transaction
1256  * in the block is a special one that creates a new coin owned by the creator
1257  * of the block.
1258  */
1259 class CBlockHeader
1260 {
1261 public:
1262     // header
1263     static const int CURRENT_VERSION=2;
1264     int nVersion;
1265     uint256 hashPrevBlock;
1266     uint256 hashMerkleRoot;
1267     unsigned int nTime;
1268     unsigned int nBits;
1269     unsigned int nNonce;
1270
1271     CBlockHeader()
1272     {
1273         SetNull();
1274     }
1275
1276     IMPLEMENT_SERIALIZE
1277     (
1278         READWRITE(this->nVersion);
1279         nVersion = this->nVersion;
1280         READWRITE(hashPrevBlock);
1281         READWRITE(hashMerkleRoot);
1282         READWRITE(nTime);
1283         READWRITE(nBits);
1284         READWRITE(nNonce);
1285     )
1286
1287     void SetNull()
1288     {
1289         nVersion = CBlockHeader::CURRENT_VERSION;
1290         hashPrevBlock = 0;
1291         hashMerkleRoot = 0;
1292         nTime = 0;
1293         nBits = 0;
1294         nNonce = 0;
1295     }
1296
1297     bool IsNull() const
1298     {
1299         return (nBits == 0);
1300     }
1301
1302     uint256 GetHash() const
1303     {
1304         return Hash(BEGIN(nVersion), END(nNonce));
1305     }
1306
1307     int64 GetBlockTime() const
1308     {
1309         return (int64)nTime;
1310     }
1311
1312     void UpdateTime(const CBlockIndex* pindexPrev);
1313 };
1314
1315 class CBlock : public CBlockHeader
1316 {
1317 public:
1318     // network and disk
1319     std::vector<CTransaction> vtx;
1320
1321     // memory only
1322     mutable std::vector<uint256> vMerkleTree;
1323
1324     CBlock()
1325     {
1326         SetNull();
1327     }
1328
1329     CBlock(const CBlockHeader &header)
1330     {
1331         SetNull();
1332         *((CBlockHeader*)this) = header;
1333     }
1334
1335     IMPLEMENT_SERIALIZE
1336     (
1337         READWRITE(*(CBlockHeader*)this);
1338         READWRITE(vtx);
1339     )
1340
1341     void SetNull()
1342     {
1343         CBlockHeader::SetNull();
1344         vtx.clear();
1345         vMerkleTree.clear();
1346     }
1347
1348     CBlockHeader GetBlockHeader() const
1349     {
1350         CBlockHeader block;
1351         block.nVersion       = nVersion;
1352         block.hashPrevBlock  = hashPrevBlock;
1353         block.hashMerkleRoot = hashMerkleRoot;
1354         block.nTime          = nTime;
1355         block.nBits          = nBits;
1356         block.nNonce         = nNonce;
1357         return block;
1358     }
1359
1360     uint256 BuildMerkleTree() const
1361     {
1362         vMerkleTree.clear();
1363         BOOST_FOREACH(const CTransaction& tx, vtx)
1364             vMerkleTree.push_back(tx.GetHash());
1365         int j = 0;
1366         for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
1367         {
1368             for (int i = 0; i < nSize; i += 2)
1369             {
1370                 int i2 = std::min(i+1, nSize-1);
1371                 vMerkleTree.push_back(Hash(BEGIN(vMerkleTree[j+i]),  END(vMerkleTree[j+i]),
1372                                            BEGIN(vMerkleTree[j+i2]), END(vMerkleTree[j+i2])));
1373             }
1374             j += nSize;
1375         }
1376         return (vMerkleTree.empty() ? 0 : vMerkleTree.back());
1377     }
1378
1379     const uint256 &GetTxHash(unsigned int nIndex) const {
1380         assert(vMerkleTree.size() > 0); // BuildMerkleTree must have been called first
1381         assert(nIndex < vtx.size());
1382         return vMerkleTree[nIndex];
1383     }
1384
1385     std::vector<uint256> GetMerkleBranch(int nIndex) const
1386     {
1387         if (vMerkleTree.empty())
1388             BuildMerkleTree();
1389         std::vector<uint256> vMerkleBranch;
1390         int j = 0;
1391         for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
1392         {
1393             int i = std::min(nIndex^1, nSize-1);
1394             vMerkleBranch.push_back(vMerkleTree[j+i]);
1395             nIndex >>= 1;
1396             j += nSize;
1397         }
1398         return vMerkleBranch;
1399     }
1400
1401     static uint256 CheckMerkleBranch(uint256 hash, const std::vector<uint256>& vMerkleBranch, int nIndex)
1402     {
1403         if (nIndex == -1)
1404             return 0;
1405         BOOST_FOREACH(const uint256& otherside, vMerkleBranch)
1406         {
1407             if (nIndex & 1)
1408                 hash = Hash(BEGIN(otherside), END(otherside), BEGIN(hash), END(hash));
1409             else
1410                 hash = Hash(BEGIN(hash), END(hash), BEGIN(otherside), END(otherside));
1411             nIndex >>= 1;
1412         }
1413         return hash;
1414     }
1415
1416     bool WriteToDisk(CDiskBlockPos &pos)
1417     {
1418         // Open history file to append
1419         CAutoFile fileout = CAutoFile(OpenBlockFile(pos), SER_DISK, CLIENT_VERSION);
1420         if (!fileout)
1421             return error("CBlock::WriteToDisk() : OpenBlockFile failed");
1422
1423         // Write index header
1424         unsigned int nSize = fileout.GetSerializeSize(*this);
1425         fileout << FLATDATA(pchMessageStart) << nSize;
1426
1427         // Write block
1428         long fileOutPos = ftell(fileout);
1429         if (fileOutPos < 0)
1430             return error("CBlock::WriteToDisk() : ftell failed");
1431         pos.nPos = (unsigned int)fileOutPos;
1432         fileout << *this;
1433
1434         // Flush stdio buffers and commit to disk before returning
1435         fflush(fileout);
1436         if (!IsInitialBlockDownload())
1437             FileCommit(fileout);
1438
1439         return true;
1440     }
1441
1442     bool ReadFromDisk(const CDiskBlockPos &pos)
1443     {
1444         SetNull();
1445
1446         // Open history file to read
1447         CAutoFile filein = CAutoFile(OpenBlockFile(pos, true), SER_DISK, CLIENT_VERSION);
1448         if (!filein)
1449             return error("CBlock::ReadFromDisk() : OpenBlockFile failed");
1450
1451         // Read block
1452         try {
1453             filein >> *this;
1454         }
1455         catch (std::exception &e) {
1456             return error("%s() : deserialize or I/O error", __PRETTY_FUNCTION__);
1457         }
1458
1459         // Check the header
1460         if (!CheckProofOfWork(GetHash(), nBits))
1461             return error("CBlock::ReadFromDisk() : errors in block header");
1462
1463         return true;
1464     }
1465
1466
1467
1468     void print() const
1469     {
1470         printf("CBlock(hash=%s, ver=%d, hashPrevBlock=%s, hashMerkleRoot=%s, nTime=%u, nBits=%08x, nNonce=%u, vtx=%"PRIszu")\n",
1471             BlockHashStr(GetHash()).c_str(),
1472             nVersion,
1473             BlockHashStr(hashPrevBlock).c_str(),
1474             hashMerkleRoot.ToString().substr(0,10).c_str(),
1475             nTime, nBits, nNonce,
1476             vtx.size());
1477         for (unsigned int i = 0; i < vtx.size(); i++)
1478         {
1479             printf("  ");
1480             vtx[i].print();
1481         }
1482         printf("  vMerkleTree: ");
1483         for (unsigned int i = 0; i < vMerkleTree.size(); i++)
1484             printf("%s ", vMerkleTree[i].ToString().substr(0,10).c_str());
1485         printf("\n");
1486     }
1487
1488
1489     /** Undo the effects of this block (with given index) on the UTXO set represented by coins.
1490      *  In case pfClean is provided, operation will try to be tolerant about errors, and *pfClean
1491      *  will be true if no problems were found. Otherwise, the return value will be false in case
1492      *  of problems. Note that in any case, coins may be modified. */
1493     bool DisconnectBlock(CValidationState &state, CBlockIndex *pindex, CCoinsViewCache &coins, bool *pfClean = NULL);
1494
1495     // Apply the effects of this block (with given index) on the UTXO set represented by coins
1496     bool ConnectBlock(CValidationState &state, CBlockIndex *pindex, CCoinsViewCache &coins, bool fJustCheck=false);
1497
1498     // Read a block from disk
1499     bool ReadFromDisk(const CBlockIndex* pindex);
1500
1501     // Add this block to the block index, and if necessary, switch the active block chain to this
1502     bool AddToBlockIndex(CValidationState &state, const CDiskBlockPos &pos);
1503
1504     // Context-independent validity checks
1505     bool CheckBlock(CValidationState &state, bool fCheckPOW=true, bool fCheckMerkleRoot=true) const;
1506
1507     // Store block on disk
1508     // if dbp is provided, the file is known to already reside on disk
1509     bool AcceptBlock(CValidationState &state, CDiskBlockPos *dbp = NULL);
1510 };
1511
1512
1513
1514
1515
1516 class CBlockFileInfo
1517 {
1518 public:
1519     unsigned int nBlocks;      // number of blocks stored in file
1520     unsigned int nSize;        // number of used bytes of block file
1521     unsigned int nUndoSize;    // number of used bytes in the undo file
1522     unsigned int nHeightFirst; // lowest height of block in file
1523     unsigned int nHeightLast;  // highest height of block in file
1524     uint64 nTimeFirst;         // earliest time of block in file
1525     uint64 nTimeLast;          // latest time of block in file
1526
1527     IMPLEMENT_SERIALIZE(
1528         READWRITE(VARINT(nBlocks));
1529         READWRITE(VARINT(nSize));
1530         READWRITE(VARINT(nUndoSize));
1531         READWRITE(VARINT(nHeightFirst));
1532         READWRITE(VARINT(nHeightLast));
1533         READWRITE(VARINT(nTimeFirst));
1534         READWRITE(VARINT(nTimeLast));
1535      )
1536
1537      void SetNull() {
1538          nBlocks = 0;
1539          nSize = 0;
1540          nUndoSize = 0;
1541          nHeightFirst = 0;
1542          nHeightLast = 0;
1543          nTimeFirst = 0;
1544          nTimeLast = 0;
1545      }
1546
1547      CBlockFileInfo() {
1548          SetNull();
1549      }
1550
1551      std::string ToString() const {
1552          return strprintf("CBlockFileInfo(blocks=%u, size=%u, heights=%u..%u, time=%s..%s)", nBlocks, nSize, nHeightFirst, nHeightLast, DateTimeStrFormat("%Y-%m-%d", nTimeFirst).c_str(), DateTimeStrFormat("%Y-%m-%d", nTimeLast).c_str());
1553      }
1554
1555      // update statistics (does not update nSize)
1556      void AddBlock(unsigned int nHeightIn, uint64 nTimeIn) {
1557          if (nBlocks==0 || nHeightFirst > nHeightIn)
1558              nHeightFirst = nHeightIn;
1559          if (nBlocks==0 || nTimeFirst > nTimeIn)
1560              nTimeFirst = nTimeIn;
1561          nBlocks++;
1562          if (nHeightIn > nHeightFirst)
1563              nHeightLast = nHeightIn;
1564          if (nTimeIn > nTimeLast)
1565              nTimeLast = nTimeIn;
1566      }
1567 };
1568
1569 extern CCriticalSection cs_LastBlockFile;
1570 extern CBlockFileInfo infoLastBlockFile;
1571 extern int nLastBlockFile;
1572
1573 enum BlockStatus {
1574     BLOCK_VALID_UNKNOWN      =    0,
1575     BLOCK_VALID_HEADER       =    1, // parsed, version ok, hash satisfies claimed PoW, 1 <= vtx count <= max, timestamp not in future
1576     BLOCK_VALID_TREE         =    2, // parent found, difficulty matches, timestamp >= median previous, checkpoint
1577     BLOCK_VALID_TRANSACTIONS =    3, // only first tx is coinbase, 2 <= coinbase input script length <= 100, transactions valid, no duplicate txids, sigops, size, merkle root
1578     BLOCK_VALID_CHAIN        =    4, // outputs do not overspend inputs, no double spends, coinbase output ok, immature coinbase spends, BIP30
1579     BLOCK_VALID_SCRIPTS      =    5, // scripts/signatures ok
1580     BLOCK_VALID_MASK         =    7,
1581
1582     BLOCK_HAVE_DATA          =    8, // full block available in blk*.dat
1583     BLOCK_HAVE_UNDO          =   16, // undo data available in rev*.dat
1584     BLOCK_HAVE_MASK          =   24,
1585
1586     BLOCK_FAILED_VALID       =   32, // stage after last reached validness failed
1587     BLOCK_FAILED_CHILD       =   64, // descends from failed block
1588     BLOCK_FAILED_MASK        =   96
1589 };
1590
1591 /** The block chain is a tree shaped structure starting with the
1592  * genesis block at the root, with each block potentially having multiple
1593  * candidates to be the next block.  pprev and pnext link a path through the
1594  * main/longest chain.  A blockindex may have multiple pprev pointing back
1595  * to it, but pnext will only point forward to the longest branch, or will
1596  * be null if the block is not part of the longest chain.
1597  */
1598 class CBlockIndex
1599 {
1600 public:
1601     // pointer to the hash of the block, if any. memory is owned by this CBlockIndex
1602     const uint256* phashBlock;
1603
1604     // pointer to the index of the predecessor of this block
1605     CBlockIndex* pprev;
1606
1607     // (memory only) pointer to the index of the *active* successor of this block
1608     CBlockIndex* pnext;
1609
1610     // height of the entry in the chain. The genesis block has height 0
1611     int nHeight;
1612
1613     // Which # file this block is stored in (blk?????.dat)
1614     int nFile;
1615
1616     // Byte offset within blk?????.dat where this block's data is stored
1617     unsigned int nDataPos;
1618
1619     // Byte offset within rev?????.dat where this block's undo data is stored
1620     unsigned int nUndoPos;
1621
1622     // (memory only) Total amount of work (expected number of hashes) in the chain up to and including this block
1623     CBigNum bnChainWork;
1624
1625     // Number of transactions in this block.
1626     // Note: in a potential headers-first mode, this number cannot be relied upon
1627     unsigned int nTx;
1628
1629     // (memory only) Number of transactions in the chain up to and including this block
1630     unsigned int nChainTx; // change to 64-bit type when necessary; won't happen before 2030
1631
1632     // Verification status of this block. See enum BlockStatus
1633     unsigned int nStatus;
1634
1635     // block header
1636     int nVersion;
1637     uint256 hashMerkleRoot;
1638     unsigned int nTime;
1639     unsigned int nBits;
1640     unsigned int nNonce;
1641
1642
1643     CBlockIndex()
1644     {
1645         phashBlock = NULL;
1646         pprev = NULL;
1647         pnext = NULL;
1648         nHeight = 0;
1649         nFile = 0;
1650         nDataPos = 0;
1651         nUndoPos = 0;
1652         bnChainWork = 0;
1653         nTx = 0;
1654         nChainTx = 0;
1655         nStatus = 0;
1656
1657         nVersion       = 0;
1658         hashMerkleRoot = 0;
1659         nTime          = 0;
1660         nBits          = 0;
1661         nNonce         = 0;
1662     }
1663
1664     CBlockIndex(CBlockHeader& block)
1665     {
1666         phashBlock = NULL;
1667         pprev = NULL;
1668         pnext = NULL;
1669         nHeight = 0;
1670         nFile = 0;
1671         nDataPos = 0;
1672         nUndoPos = 0;
1673         bnChainWork = 0;
1674         nTx = 0;
1675         nChainTx = 0;
1676         nStatus = 0;
1677
1678         nVersion       = block.nVersion;
1679         hashMerkleRoot = block.hashMerkleRoot;
1680         nTime          = block.nTime;
1681         nBits          = block.nBits;
1682         nNonce         = block.nNonce;
1683     }
1684
1685     CDiskBlockPos GetBlockPos() const {
1686         CDiskBlockPos ret;
1687         if (nStatus & BLOCK_HAVE_DATA) {
1688             ret.nFile = nFile;
1689             ret.nPos  = nDataPos;
1690         }
1691         return ret;
1692     }
1693
1694     CDiskBlockPos GetUndoPos() const {
1695         CDiskBlockPos ret;
1696         if (nStatus & BLOCK_HAVE_UNDO) {
1697             ret.nFile = nFile;
1698             ret.nPos  = nUndoPos;
1699         }
1700         return ret;
1701     }
1702
1703     CBlockHeader GetBlockHeader() const
1704     {
1705         CBlockHeader block;
1706         block.nVersion       = nVersion;
1707         if (pprev)
1708             block.hashPrevBlock = pprev->GetBlockHash();
1709         block.hashMerkleRoot = hashMerkleRoot;
1710         block.nTime          = nTime;
1711         block.nBits          = nBits;
1712         block.nNonce         = nNonce;
1713         return block;
1714     }
1715
1716     uint256 GetBlockHash() const
1717     {
1718         return *phashBlock;
1719     }
1720
1721     int64 GetBlockTime() const
1722     {
1723         return (int64)nTime;
1724     }
1725
1726     CBigNum GetBlockWork() const
1727     {
1728         CBigNum bnTarget;
1729         bnTarget.SetCompact(nBits);
1730         if (bnTarget <= 0)
1731             return 0;
1732         return (CBigNum(1)<<256) / (bnTarget+1);
1733     }
1734
1735     bool IsInMainChain() const
1736     {
1737         return (pnext || this == pindexBest);
1738     }
1739
1740     bool CheckIndex() const
1741     {
1742         return CheckProofOfWork(GetBlockHash(), nBits);
1743     }
1744
1745     enum { nMedianTimeSpan=11 };
1746
1747     int64 GetMedianTimePast() const
1748     {
1749         int64 pmedian[nMedianTimeSpan];
1750         int64* pbegin = &pmedian[nMedianTimeSpan];
1751         int64* pend = &pmedian[nMedianTimeSpan];
1752
1753         const CBlockIndex* pindex = this;
1754         for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev)
1755             *(--pbegin) = pindex->GetBlockTime();
1756
1757         std::sort(pbegin, pend);
1758         return pbegin[(pend - pbegin)/2];
1759     }
1760
1761     int64 GetMedianTime() const
1762     {
1763         const CBlockIndex* pindex = this;
1764         for (int i = 0; i < nMedianTimeSpan/2; i++)
1765         {
1766             if (!pindex->pnext)
1767                 return GetBlockTime();
1768             pindex = pindex->pnext;
1769         }
1770         return pindex->GetMedianTimePast();
1771     }
1772
1773     /**
1774      * Returns true if there are nRequired or more blocks of minVersion or above
1775      * in the last nToCheck blocks, starting at pstart and going backwards.
1776      */
1777     static bool IsSuperMajority(int minVersion, const CBlockIndex* pstart,
1778                                 unsigned int nRequired, unsigned int nToCheck);
1779
1780     std::string ToString() const
1781     {
1782         return strprintf("CBlockIndex(pprev=%p, pnext=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
1783             pprev, pnext, nHeight,
1784             hashMerkleRoot.ToString().substr(0,10).c_str(),
1785             BlockHashStr(GetBlockHash()).c_str());
1786     }
1787
1788     void print() const
1789     {
1790         printf("%s\n", ToString().c_str());
1791     }
1792 };
1793
1794 struct CBlockIndexWorkComparator
1795 {
1796     bool operator()(CBlockIndex *pa, CBlockIndex *pb) {
1797         if (pa->bnChainWork > pb->bnChainWork) return false;
1798         if (pa->bnChainWork < pb->bnChainWork) return true;
1799
1800         if (pa->GetBlockHash() < pb->GetBlockHash()) return false;
1801         if (pa->GetBlockHash() > pb->GetBlockHash()) return true;
1802
1803         return false; // identical blocks
1804     }
1805 };
1806
1807
1808
1809 /** Used to marshal pointers into hashes for db storage. */
1810 class CDiskBlockIndex : public CBlockIndex
1811 {
1812 public:
1813     uint256 hashPrev;
1814
1815     CDiskBlockIndex() {
1816         hashPrev = 0;
1817     }
1818
1819     explicit CDiskBlockIndex(CBlockIndex* pindex) : CBlockIndex(*pindex) {
1820         hashPrev = (pprev ? pprev->GetBlockHash() : 0);
1821     }
1822
1823     IMPLEMENT_SERIALIZE
1824     (
1825         if (!(nType & SER_GETHASH))
1826             READWRITE(VARINT(nVersion));
1827
1828         READWRITE(VARINT(nHeight));
1829         READWRITE(VARINT(nStatus));
1830         READWRITE(VARINT(nTx));
1831         if (nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO))
1832             READWRITE(VARINT(nFile));
1833         if (nStatus & BLOCK_HAVE_DATA)
1834             READWRITE(VARINT(nDataPos));
1835         if (nStatus & BLOCK_HAVE_UNDO)
1836             READWRITE(VARINT(nUndoPos));
1837
1838         // block header
1839         READWRITE(this->nVersion);
1840         READWRITE(hashPrev);
1841         READWRITE(hashMerkleRoot);
1842         READWRITE(nTime);
1843         READWRITE(nBits);
1844         READWRITE(nNonce);
1845     )
1846
1847     uint256 GetBlockHash() const
1848     {
1849         CBlockHeader block;
1850         block.nVersion        = nVersion;
1851         block.hashPrevBlock   = hashPrev;
1852         block.hashMerkleRoot  = hashMerkleRoot;
1853         block.nTime           = nTime;
1854         block.nBits           = nBits;
1855         block.nNonce          = nNonce;
1856         return block.GetHash();
1857     }
1858
1859
1860     std::string ToString() const
1861     {
1862         std::string str = "CDiskBlockIndex(";
1863         str += CBlockIndex::ToString();
1864         str += strprintf("\n                hashBlock=%s, hashPrev=%s)",
1865             GetBlockHash().ToString().c_str(),
1866             BlockHashStr(hashPrev).c_str());
1867         return str;
1868     }
1869
1870     void print() const
1871     {
1872         printf("%s\n", ToString().c_str());
1873     }
1874 };
1875
1876 /** Capture information about block/transaction validation */
1877 class CValidationState {
1878 private:
1879     enum mode_state {
1880         MODE_VALID,   // everything ok
1881         MODE_INVALID, // network rule violation (DoS value may be set)
1882         MODE_ERROR,   // run-time error
1883     } mode;
1884     int nDoS;
1885 public:
1886     CValidationState() : mode(MODE_VALID), nDoS(0) {}
1887     bool DoS(int level, bool ret = false) {
1888         if (mode == MODE_ERROR)
1889             return ret;
1890         nDoS += level;
1891         mode = MODE_INVALID;
1892         return ret;
1893     }
1894     bool Invalid(bool ret = false) {
1895         return DoS(0, ret);
1896     }
1897     bool Error() {
1898         mode = MODE_ERROR;
1899         return false;
1900     }
1901     bool Abort(const std::string &msg) {
1902         AbortNode(msg);
1903         return Error();
1904     }
1905     bool IsValid() {
1906         return mode == MODE_VALID;
1907     }
1908     bool IsInvalid() {
1909         return mode == MODE_INVALID;
1910     }
1911     bool IsError() {
1912         return mode == MODE_ERROR;
1913     }
1914     bool IsInvalid(int &nDoSOut) {
1915         if (IsInvalid()) {
1916             nDoSOut = nDoS;
1917             return true;
1918         }
1919         return false;
1920     }
1921 };
1922
1923
1924
1925
1926
1927
1928
1929 /** Describes a place in the block chain to another node such that if the
1930  * other node doesn't have the same branch, it can find a recent common trunk.
1931  * The further back it is, the further before the fork it may be.
1932  */
1933 class CBlockLocator
1934 {
1935 protected:
1936     std::vector<uint256> vHave;
1937 public:
1938
1939     CBlockLocator()
1940     {
1941     }
1942
1943     explicit CBlockLocator(const CBlockIndex* pindex)
1944     {
1945         Set(pindex);
1946     }
1947
1948     explicit CBlockLocator(uint256 hashBlock)
1949     {
1950         std::map<uint256, CBlockIndex*>::iterator mi = mapBlockIndex.find(hashBlock);
1951         if (mi != mapBlockIndex.end())
1952             Set((*mi).second);
1953     }
1954
1955     CBlockLocator(const std::vector<uint256>& vHaveIn)
1956     {
1957         vHave = vHaveIn;
1958     }
1959
1960     IMPLEMENT_SERIALIZE
1961     (
1962         if (!(nType & SER_GETHASH))
1963             READWRITE(nVersion);
1964         READWRITE(vHave);
1965     )
1966
1967     void SetNull()
1968     {
1969         vHave.clear();
1970     }
1971
1972     bool IsNull()
1973     {
1974         return vHave.empty();
1975     }
1976
1977     void Set(const CBlockIndex* pindex)
1978     {
1979         vHave.clear();
1980         int nStep = 1;
1981         while (pindex)
1982         {
1983             vHave.push_back(pindex->GetBlockHash());
1984
1985             // Exponentially larger steps back
1986             for (int i = 0; pindex && i < nStep; i++)
1987                 pindex = pindex->pprev;
1988             if (vHave.size() > 10)
1989                 nStep *= 2;
1990         }
1991         vHave.push_back(hashGenesisBlock);
1992     }
1993
1994     int GetDistanceBack()
1995     {
1996         // Retrace how far back it was in the sender's branch
1997         int nDistance = 0;
1998         int nStep = 1;
1999         BOOST_FOREACH(const uint256& hash, vHave)
2000         {
2001             std::map<uint256, CBlockIndex*>::iterator mi = mapBlockIndex.find(hash);
2002             if (mi != mapBlockIndex.end())
2003             {
2004                 CBlockIndex* pindex = (*mi).second;
2005                 if (pindex->IsInMainChain())
2006                     return nDistance;
2007             }
2008             nDistance += nStep;
2009             if (nDistance > 10)
2010                 nStep *= 2;
2011         }
2012         return nDistance;
2013     }
2014
2015     CBlockIndex* GetBlockIndex()
2016     {
2017         // Find the first block the caller has in the main chain
2018         BOOST_FOREACH(const uint256& hash, vHave)
2019         {
2020             std::map<uint256, CBlockIndex*>::iterator mi = mapBlockIndex.find(hash);
2021             if (mi != mapBlockIndex.end())
2022             {
2023                 CBlockIndex* pindex = (*mi).second;
2024                 if (pindex->IsInMainChain())
2025                     return pindex;
2026             }
2027         }
2028         return pindexGenesisBlock;
2029     }
2030
2031     uint256 GetBlockHash()
2032     {
2033         // Find the first block the caller has in the main chain
2034         BOOST_FOREACH(const uint256& hash, vHave)
2035         {
2036             std::map<uint256, CBlockIndex*>::iterator mi = mapBlockIndex.find(hash);
2037             if (mi != mapBlockIndex.end())
2038             {
2039                 CBlockIndex* pindex = (*mi).second;
2040                 if (pindex->IsInMainChain())
2041                     return hash;
2042             }
2043         }
2044         return hashGenesisBlock;
2045     }
2046
2047     int GetHeight()
2048     {
2049         CBlockIndex* pindex = GetBlockIndex();
2050         if (!pindex)
2051             return 0;
2052         return pindex->nHeight;
2053     }
2054 };
2055
2056
2057
2058
2059
2060
2061
2062
2063 class CTxMemPool
2064 {
2065 public:
2066     mutable CCriticalSection cs;
2067     std::map<uint256, CTransaction> mapTx;
2068     std::map<COutPoint, CInPoint> mapNextTx;
2069
2070     bool accept(CValidationState &state, CTransaction &tx, bool fCheckInputs, bool fLimitFree, bool* pfMissingInputs);
2071     bool addUnchecked(const uint256& hash, CTransaction &tx);
2072     bool remove(const CTransaction &tx, bool fRecursive = false);
2073     bool removeConflicts(const CTransaction &tx);
2074     void clear();
2075     void queryHashes(std::vector<uint256>& vtxid);
2076     void pruneSpent(const uint256& hash, CCoins &coins);
2077
2078     unsigned long size()
2079     {
2080         LOCK(cs);
2081         return mapTx.size();
2082     }
2083
2084     bool exists(uint256 hash)
2085     {
2086         return (mapTx.count(hash) != 0);
2087     }
2088
2089     CTransaction& lookup(uint256 hash)
2090     {
2091         return mapTx[hash];
2092     }
2093 };
2094
2095 extern CTxMemPool mempool;
2096
2097 struct CCoinsStats
2098 {
2099     int nHeight;
2100     uint64 nTransactions;
2101     uint64 nTransactionOutputs;
2102     uint64 nSerializedSize;
2103
2104     CCoinsStats() : nHeight(0), nTransactions(0), nTransactionOutputs(0), nSerializedSize(0) {}
2105 };
2106
2107 /** Abstract view on the open txout dataset. */
2108 class CCoinsView
2109 {
2110 public:
2111     // Retrieve the CCoins (unspent transaction outputs) for a given txid
2112     virtual bool GetCoins(uint256 txid, CCoins &coins);
2113
2114     // Modify the CCoins for a given txid
2115     virtual bool SetCoins(uint256 txid, const CCoins &coins);
2116
2117     // Just check whether we have data for a given txid.
2118     // This may (but cannot always) return true for fully spent transactions
2119     virtual bool HaveCoins(uint256 txid);
2120
2121     // Retrieve the block index whose state this CCoinsView currently represents
2122     virtual CBlockIndex *GetBestBlock();
2123
2124     // Modify the currently active block index
2125     virtual bool SetBestBlock(CBlockIndex *pindex);
2126
2127     // Do a bulk modification (multiple SetCoins + one SetBestBlock)
2128     virtual bool BatchWrite(const std::map<uint256, CCoins> &mapCoins, CBlockIndex *pindex);
2129
2130     // Calculate statistics about the unspent transaction output set
2131     virtual bool GetStats(CCoinsStats &stats);
2132
2133     // As we use CCoinsViews polymorphically, have a virtual destructor
2134     virtual ~CCoinsView() {}
2135 };
2136
2137 /** CCoinsView backed by another CCoinsView */
2138 class CCoinsViewBacked : public CCoinsView
2139 {
2140 protected:
2141     CCoinsView *base;
2142
2143 public:
2144     CCoinsViewBacked(CCoinsView &viewIn);
2145     bool GetCoins(uint256 txid, CCoins &coins);
2146     bool SetCoins(uint256 txid, const CCoins &coins);
2147     bool HaveCoins(uint256 txid);
2148     CBlockIndex *GetBestBlock();
2149     bool SetBestBlock(CBlockIndex *pindex);
2150     void SetBackend(CCoinsView &viewIn);
2151     bool BatchWrite(const std::map<uint256, CCoins> &mapCoins, CBlockIndex *pindex);
2152     bool GetStats(CCoinsStats &stats);
2153 };
2154
2155 /** CCoinsView that adds a memory cache for transactions to another CCoinsView */
2156 class CCoinsViewCache : public CCoinsViewBacked
2157 {
2158 protected:
2159     CBlockIndex *pindexTip;
2160     std::map<uint256,CCoins> cacheCoins;
2161
2162 public:
2163     CCoinsViewCache(CCoinsView &baseIn, bool fDummy = false);
2164
2165     // Standard CCoinsView methods
2166     bool GetCoins(uint256 txid, CCoins &coins);
2167     bool SetCoins(uint256 txid, const CCoins &coins);
2168     bool HaveCoins(uint256 txid);
2169     CBlockIndex *GetBestBlock();
2170     bool SetBestBlock(CBlockIndex *pindex);
2171     bool BatchWrite(const std::map<uint256, CCoins> &mapCoins, CBlockIndex *pindex);
2172
2173     // Return a modifiable reference to a CCoins. Check HaveCoins first.
2174     // Many methods explicitly require a CCoinsViewCache because of this method, to reduce
2175     // copying.
2176     CCoins &GetCoins(uint256 txid);
2177
2178     // Push the modifications applied to this cache to its base.
2179     // Failure to call this method before destruction will cause the changes to be forgotten.
2180     bool Flush();
2181
2182     // Calculate the size of the cache (in number of transactions)
2183     unsigned int GetCacheSize();
2184
2185 private:
2186     std::map<uint256,CCoins>::iterator FetchCoins(uint256 txid);
2187 };
2188
2189 /** CCoinsView that brings transactions from a memorypool into view.
2190     It does not check for spendings by memory pool transactions. */
2191 class CCoinsViewMemPool : public CCoinsViewBacked
2192 {
2193 protected:
2194     CTxMemPool &mempool;
2195
2196 public:
2197     CCoinsViewMemPool(CCoinsView &baseIn, CTxMemPool &mempoolIn);
2198     bool GetCoins(uint256 txid, CCoins &coins);
2199     bool HaveCoins(uint256 txid);
2200 };
2201
2202 /** Global variable that points to the active CCoinsView (protected by cs_main) */
2203 extern CCoinsViewCache *pcoinsTip;
2204
2205 /** Global variable that points to the active block tree (protected by cs_main) */
2206 extern CBlockTreeDB *pblocktree;
2207
2208 struct CBlockTemplate
2209 {
2210     CBlock block;
2211     std::vector<int64_t> vTxFees;
2212     std::vector<int64_t> vTxSigOps;
2213 };
2214
2215
2216
2217
2218
2219
2220 /** Used to relay blocks as header + vector<merkle branch>
2221  * to filtered nodes.
2222  */
2223 class CMerkleBlock
2224 {
2225 public:
2226     // Public only for unit testing
2227     CBlockHeader header;
2228     CPartialMerkleTree txn;
2229
2230 public:
2231     // Public only for unit testing and relay testing
2232     // (not relayed)
2233     std::vector<std::pair<unsigned int, uint256> > vMatchedTxn;
2234
2235     // Create from a CBlock, filtering transactions according to filter
2236     // Note that this will call IsRelevantAndUpdate on the filter for each transaction,
2237     // thus the filter will likely be modified.
2238     CMerkleBlock(const CBlock& block, CBloomFilter& filter);
2239
2240     IMPLEMENT_SERIALIZE
2241     (
2242         READWRITE(header);
2243         READWRITE(txn);
2244     )
2245 };
2246
2247 #endif