1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2014 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.
9 #if defined(HAVE_CONFIG_H)
10 #include "config/bitcoin-config.h"
14 #include "chainparams.h"
19 #include "script/script.h"
20 #include "script/sigcache.h"
21 #include "script/standard.h"
23 #include "txmempool.h"
35 #include <boost/unordered_map.hpp>
41 /** The maximum allowed size for a serialized block, in bytes (network rule) */
42 static const unsigned int MAX_BLOCK_SIZE = 1000000;
43 /** Default for -blockmaxsize and -blockminsize, which control the range of sizes the mining code will create **/
44 static const unsigned int DEFAULT_BLOCK_MAX_SIZE = 750000;
45 static const unsigned int DEFAULT_BLOCK_MIN_SIZE = 0;
46 /** Default for -blockprioritysize, maximum space for zero/low-fee transactions **/
47 static const unsigned int DEFAULT_BLOCK_PRIORITY_SIZE = 50000;
48 /** The maximum size for transactions we're willing to relay/mine */
49 static const unsigned int MAX_STANDARD_TX_SIZE = 100000;
50 /** The maximum allowed number of signature check operations in a block (network rule) */
51 static const unsigned int MAX_BLOCK_SIGOPS = MAX_BLOCK_SIZE/50;
52 /** Maxiumum number of signature check operations in an IsStandard() P2SH script */
53 static const unsigned int MAX_P2SH_SIGOPS = 15;
54 /** The maximum number of sigops we're willing to relay/mine in a single tx */
55 static const unsigned int MAX_TX_SIGOPS = MAX_BLOCK_SIGOPS/5;
56 /** Default for -maxorphantx, maximum number of orphan transactions kept in memory */
57 static const unsigned int DEFAULT_MAX_ORPHAN_TRANSACTIONS = 100;
58 /** Default for -maxorphanblocks, maximum number of orphan blocks kept in memory */
59 static const unsigned int DEFAULT_MAX_ORPHAN_BLOCKS = 750;
60 /** The maximum size of a blk?????.dat file (since 0.8) */
61 static const unsigned int MAX_BLOCKFILE_SIZE = 0x8000000; // 128 MiB
62 /** The pre-allocation chunk size for blk?????.dat files (since 0.8) */
63 static const unsigned int BLOCKFILE_CHUNK_SIZE = 0x1000000; // 16 MiB
64 /** The pre-allocation chunk size for rev?????.dat files (since 0.8) */
65 static const unsigned int UNDOFILE_CHUNK_SIZE = 0x100000; // 1 MiB
66 /** Coinbase transaction outputs can only be spent after this number of new blocks (network rule) */
67 static const int COINBASE_MATURITY = 100;
68 /** Threshold for nLockTime: below this value it is interpreted as block number, otherwise as UNIX timestamp. */
69 static const unsigned int LOCKTIME_THRESHOLD = 500000000; // Tue Nov 5 00:53:20 1985 UTC
70 /** Maximum number of script-checking threads allowed */
71 static const int MAX_SCRIPTCHECK_THREADS = 16;
72 /** -par default (number of script-checking threads, 0 = auto) */
73 static const int DEFAULT_SCRIPTCHECK_THREADS = 0;
74 /** Number of blocks that can be requested at any given time from a single peer. */
75 static const int MAX_BLOCKS_IN_TRANSIT_PER_PEER = 128;
76 /** Timeout in seconds before considering a block download peer unresponsive. */
77 static const unsigned int BLOCK_DOWNLOAD_TIMEOUT = 60;
79 /** "reject" message codes **/
80 static const unsigned char REJECT_MALFORMED = 0x01;
81 static const unsigned char REJECT_INVALID = 0x10;
82 static const unsigned char REJECT_OBSOLETE = 0x11;
83 static const unsigned char REJECT_DUPLICATE = 0x12;
84 static const unsigned char REJECT_NONSTANDARD = 0x40;
85 static const unsigned char REJECT_DUST = 0x41;
86 static const unsigned char REJECT_INSUFFICIENTFEE = 0x42;
87 static const unsigned char REJECT_CHECKPOINT = 0x43;
91 size_t operator()(const uint256& hash) const { return hash.GetLow64(); }
94 extern CScript COINBASE_FLAGS;
95 extern CCriticalSection cs_main;
96 extern CTxMemPool mempool;
97 typedef boost::unordered_map<uint256, CBlockIndex*, BlockHasher> BlockMap;
98 extern BlockMap mapBlockIndex;
99 extern uint64_t nLastBlockTx;
100 extern uint64_t nLastBlockSize;
101 extern const std::string strMessageMagic;
102 extern int64_t nTimeBestReceived;
103 extern CWaitableCriticalSection csBestBlock;
104 extern CConditionVariable cvBlockChange;
105 extern bool fImporting;
106 extern bool fReindex;
107 extern int nScriptCheckThreads;
108 extern bool fTxIndex;
109 extern bool fIsBareMultisigStd;
110 extern unsigned int nCoinCacheSize;
111 extern CFeeRate minRelayTxFee;
113 // Minimum disk space required - used in CheckDiskSpace()
114 static const uint64_t nMinDiskSpace = 52428800;
120 class CValidationState;
121 class CWalletInterface;
122 struct CNodeStateStats;
124 struct CBlockTemplate;
126 /** Register a wallet to receive updates from core */
127 void RegisterWallet(CWalletInterface* pwalletIn);
128 /** Unregister a wallet from core */
129 void UnregisterWallet(CWalletInterface* pwalletIn);
130 /** Unregister all wallets from core */
131 void UnregisterAllWallets();
132 /** Push an updated transaction to all registered wallets */
133 void SyncWithWallets(const CTransaction& tx, const CBlock* pblock = NULL);
135 /** Register with a network node to receive its signals */
136 void RegisterNodeSignals(CNodeSignals& nodeSignals);
137 /** Unregister a network node */
138 void UnregisterNodeSignals(CNodeSignals& nodeSignals);
140 void PushGetBlocks(CNode* pnode, CBlockIndex* pindexBegin, uint256 hashEnd);
142 /** Process an incoming block */
143 bool ProcessBlock(CValidationState &state, CNode* pfrom, CBlock* pblock, CDiskBlockPos *dbp = NULL);
144 /** Check whether enough disk space is available for an incoming block */
145 bool CheckDiskSpace(uint64_t nAdditionalBytes = 0);
146 /** Open a block file (blk?????.dat) */
147 FILE* OpenBlockFile(const CDiskBlockPos &pos, bool fReadOnly = false);
148 /** Open an undo file (rev?????.dat) */
149 FILE* OpenUndoFile(const CDiskBlockPos &pos, bool fReadOnly = false);
150 /** Translation to a filesystem path */
151 boost::filesystem::path GetBlockPosFilename(const CDiskBlockPos &pos, const char *prefix);
152 /** Import blocks from an external file */
153 bool LoadExternalBlockFile(FILE* fileIn, CDiskBlockPos *dbp = NULL);
154 /** Initialize a new block tree database + block data on disk */
155 bool InitBlockIndex();
156 /** Load the block tree and coins database from disk */
157 bool LoadBlockIndex();
158 /** Unload database information */
159 void UnloadBlockIndex();
160 /** Print the loaded block tree */
161 void PrintBlockTree();
162 /** Process protocol messages received from a given node */
163 bool ProcessMessages(CNode* pfrom);
164 /** Send queued protocol messages to be sent to a give node */
165 bool SendMessages(CNode* pto, bool fSendTrickle);
166 /** Run an instance of the script checking thread */
167 void ThreadScriptCheck();
168 /** Check whether we are doing an initial block download (synchronizing from disk or network) */
169 bool IsInitialBlockDownload();
170 /** Format a string that describes several potential problems detected by the core */
171 std::string GetWarnings(std::string strFor);
172 /** Retrieve a transaction (from memory pool, or from disk, if possible) */
173 bool GetTransaction(const uint256 &hash, CTransaction &tx, uint256 &hashBlock, bool fAllowSlow = false);
174 /** Find the best known block, and make it the tip of the block chain */
175 bool ActivateBestChain(CValidationState &state, CBlock *pblock = NULL);
176 CAmount GetBlockValue(int nHeight, const CAmount& nFees);
178 /** Create a new block index entry for a given block hash */
179 CBlockIndex * InsertBlockIndex(uint256 hash);
180 /** Abort with a message */
181 bool AbortNode(const std::string &msg, const std::string &userMessage="");
182 /** Get statistics from node state */
183 bool GetNodeStateStats(NodeId nodeid, CNodeStateStats &stats);
184 /** Increase a node's misbehavior score. */
185 void Misbehaving(NodeId nodeid, int howmuch);
188 /** (try to) add transaction to memory pool **/
189 bool AcceptToMemoryPool(CTxMemPool& pool, CValidationState &state, const CTransaction &tx, bool fLimitFree,
190 bool* pfMissingInputs, bool fRejectInsaneFee=false);
193 struct CNodeStateStats {
198 struct CDiskTxPos : public CDiskBlockPos
200 unsigned int nTxOffset; // after header
202 ADD_SERIALIZE_METHODS;
204 template <typename Stream, typename Operation>
205 inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
206 READWRITE(*(CDiskBlockPos*)this);
207 READWRITE(VARINT(nTxOffset));
210 CDiskTxPos(const CDiskBlockPos &blockIn, unsigned int nTxOffsetIn) : CDiskBlockPos(blockIn.nFile, blockIn.nPos), nTxOffset(nTxOffsetIn) {
218 CDiskBlockPos::SetNull();
224 CAmount GetMinRelayFee(const CTransaction& tx, unsigned int nBytes, bool fAllowFree);
227 // Check transaction inputs, and make sure any
228 // pay-to-script-hash transactions are evaluating IsStandard scripts
230 // Why bother? To avoid denial-of-service attacks; an attacker
231 // can submit a standard HASH... OP_EQUAL transaction,
232 // which will get accepted into blocks. The redemption
233 // script can be anything; an attacker could use a very
234 // expensive-to-check-upon-redemption script like:
235 // DUP CHECKSIG DROP ... repeated 100 times... OP_1
238 /** Check for standard transaction types
239 @param[in] mapInputs Map of previous transactions that have outputs we're spending
240 @return True if all inputs (scriptSigs) use only standard transaction forms
242 bool AreInputsStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs);
244 /** Count ECDSA signature operations the old-fashioned (pre-0.6) way
245 @return number of sigops this transaction's outputs will produce when spent
246 @see CTransaction::FetchInputs
248 unsigned int GetLegacySigOpCount(const CTransaction& tx);
250 /** Count ECDSA signature operations in pay-to-script-hash inputs.
252 @param[in] mapInputs Map of previous transactions that have outputs we're spending
253 @return maximum number of sigops required to validate this transaction's inputs
254 @see CTransaction::FetchInputs
256 unsigned int GetP2SHSigOpCount(const CTransaction& tx, const CCoinsViewCache& mapInputs);
259 // Check whether all inputs of this transaction are valid (no double spends, scripts & sigs, amounts)
260 // This does not modify the UTXO set. If pvChecks is not NULL, script checks are pushed onto it
261 // instead of being performed inline.
262 bool CheckInputs(const CTransaction& tx, CValidationState &state, const CCoinsViewCache &view, bool fScriptChecks,
263 unsigned int flags, bool cacheStore, std::vector<CScriptCheck> *pvChecks = NULL);
265 // Apply the effects of this transaction on the UTXO set represented by view
266 void UpdateCoins(const CTransaction& tx, CValidationState &state, CCoinsViewCache &inputs, CTxUndo &txundo, int nHeight);
268 // Context-independent validity checks
269 bool CheckTransaction(const CTransaction& tx, CValidationState& state);
271 /** Check for standard transaction types
272 @return True if all outputs (scriptPubKeys) use only standard transaction forms
274 bool IsStandardTx(const CTransaction& tx, std::string& reason);
276 bool IsFinalTx(const CTransaction &tx, int nBlockHeight = 0, int64_t nBlockTime = 0);
278 /** Undo information for a CBlock */
282 std::vector<CTxUndo> vtxundo; // for all but the coinbase
284 ADD_SERIALIZE_METHODS;
286 template <typename Stream, typename Operation>
287 inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
291 bool WriteToDisk(CDiskBlockPos &pos, const uint256 &hashBlock);
292 bool ReadFromDisk(const CDiskBlockPos &pos, const uint256 &hashBlock);
296 /** Closure representing one script verification
297 * Note that this stores references to the spending transaction */
301 CScript scriptPubKey;
302 const CTransaction *ptxTo;
308 CScriptCheck(): ptxTo(0), nIn(0), nFlags(0), cacheStore(false) {}
309 CScriptCheck(const CCoins& txFromIn, const CTransaction& txToIn, unsigned int nInIn, unsigned int nFlagsIn, bool cacheIn) :
310 scriptPubKey(txFromIn.vout[txToIn.vin[nInIn].prevout.n].scriptPubKey),
311 ptxTo(&txToIn), nIn(nInIn), nFlags(nFlagsIn), cacheStore(cacheIn) { }
313 bool operator()() const;
315 void swap(CScriptCheck &check) {
316 scriptPubKey.swap(check.scriptPubKey);
317 std::swap(ptxTo, check.ptxTo);
318 std::swap(nIn, check.nIn);
319 std::swap(nFlags, check.nFlags);
320 std::swap(cacheStore, check.cacheStore);
324 /** Data structure that represents a partial merkle tree.
326 * It respresents a subset of the txid's of a known block, in a way that
327 * allows recovery of the list of txid's and the merkle root, in an
330 * The encoding works as follows: we traverse the tree in depth-first order,
331 * storing a bit for each traversed node, signifying whether the node is the
332 * parent of at least one matched leaf txid (or a matched txid itself). In
333 * case we are at the leaf level, or this bit is 0, its merkle node hash is
334 * stored, and its children are not explorer further. Otherwise, no hash is
335 * stored, but we recurse into both (or the only) child branch. During
336 * decoding, the same depth-first traversal is performed, consuming bits and
337 * hashes as they written during encoding.
339 * The serialization is fixed and provides a hard guarantee about the
342 * SIZE <= 10 + ceil(32.25*N)
344 * Where N represents the number of leaf nodes of the partial tree. N itself
347 * N <= total_transactions
348 * N <= 1 + matched_transactions*tree_height
350 * The serialization format:
351 * - uint32 total_transactions (4 bytes)
352 * - varint number of hashes (1-3 bytes)
353 * - uint256[] hashes in depth-first order (<= 32*N bytes)
354 * - varint number of bytes of flag bits (1-3 bytes)
355 * - byte[] flag bits, packed per 8 in a byte, least significant bit first (<= 2*N-1 bits)
356 * The size constraints follow from this.
358 class CPartialMerkleTree
361 // the total number of transactions in the block
362 unsigned int nTransactions;
364 // node-is-parent-of-matched-txid bits
365 std::vector<bool> vBits;
367 // txids and internal hashes
368 std::vector<uint256> vHash;
370 // flag set when encountering invalid data
373 // helper function to efficiently calculate the number of nodes at given height in the merkle tree
374 unsigned int CalcTreeWidth(int height) {
375 return (nTransactions+(1 << height)-1) >> height;
378 // calculate the hash of a node in the merkle tree (at leaf level: the txid's themself)
379 uint256 CalcHash(int height, unsigned int pos, const std::vector<uint256> &vTxid);
381 // recursive function that traverses tree nodes, storing the data as bits and hashes
382 void TraverseAndBuild(int height, unsigned int pos, const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch);
384 // recursive function that traverses tree nodes, consuming the bits and hashes produced by TraverseAndBuild.
385 // it returns the hash of the respective node.
386 uint256 TraverseAndExtract(int height, unsigned int pos, unsigned int &nBitsUsed, unsigned int &nHashUsed, std::vector<uint256> &vMatch);
390 // serialization implementation
391 ADD_SERIALIZE_METHODS;
393 template <typename Stream, typename Operation>
394 inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
395 READWRITE(nTransactions);
397 std::vector<unsigned char> vBytes;
398 if (ser_action.ForRead()) {
400 CPartialMerkleTree &us = *(const_cast<CPartialMerkleTree*>(this));
401 us.vBits.resize(vBytes.size() * 8);
402 for (unsigned int p = 0; p < us.vBits.size(); p++)
403 us.vBits[p] = (vBytes[p / 8] & (1 << (p % 8))) != 0;
406 vBytes.resize((vBits.size()+7)/8);
407 for (unsigned int p = 0; p < vBits.size(); p++)
408 vBytes[p / 8] |= vBits[p] << (p % 8);
413 // Construct a partial merkle tree from a list of transaction id's, and a mask that selects a subset of them
414 CPartialMerkleTree(const std::vector<uint256> &vTxid, const std::vector<bool> &vMatch);
416 CPartialMerkleTree();
418 // extract the matching txid's represented by this partial merkle tree.
419 // returns the merkle root, or 0 in case of failure
420 uint256 ExtractMatches(std::vector<uint256> &vMatch);
425 /** Functions for disk access for blocks */
426 bool WriteBlockToDisk(CBlock& block, CDiskBlockPos& pos);
427 bool ReadBlockFromDisk(CBlock& block, const CDiskBlockPos& pos);
428 bool ReadBlockFromDisk(CBlock& block, const CBlockIndex* pindex);
431 /** Functions for validating blocks and updating the block tree */
433 /** Undo the effects of this block (with given index) on the UTXO set represented by coins.
434 * In case pfClean is provided, operation will try to be tolerant about errors, and *pfClean
435 * will be true if no problems were found. Otherwise, the return value will be false in case
436 * of problems. Note that in any case, coins may be modified. */
437 bool DisconnectBlock(CBlock& block, CValidationState& state, CBlockIndex* pindex, CCoinsViewCache& coins, bool* pfClean = NULL);
439 // Apply the effects of this block (with given index) on the UTXO set represented by coins
440 bool ConnectBlock(CBlock& block, CValidationState& state, CBlockIndex* pindex, CCoinsViewCache& coins, bool fJustCheck = false);
442 // Add this block to the block index, and if necessary, switch the active block chain to this
443 bool AddToBlockIndex(CBlock& block, CValidationState& state, const CDiskBlockPos& pos);
445 // Context-independent validity checks
446 bool CheckBlockHeader(const CBlockHeader& block, CValidationState& state, bool fCheckPOW = true);
447 bool CheckBlock(const CBlock& block, CValidationState& state, bool fCheckPOW = true, bool fCheckMerkleRoot = true);
449 // Store block on disk
450 // if dbp is provided, the file is known to already reside on disk
451 bool AcceptBlock(CBlock& block, CValidationState& state, CBlockIndex **pindex, CDiskBlockPos* dbp = NULL);
452 bool AcceptBlockHeader(CBlockHeader& block, CValidationState& state, CBlockIndex **ppindex= NULL);
459 unsigned int nBlocks; // number of blocks stored in file
460 unsigned int nSize; // number of used bytes of block file
461 unsigned int nUndoSize; // number of used bytes in the undo file
462 unsigned int nHeightFirst; // lowest height of block in file
463 unsigned int nHeightLast; // highest height of block in file
464 uint64_t nTimeFirst; // earliest time of block in file
465 uint64_t nTimeLast; // latest time of block in file
467 ADD_SERIALIZE_METHODS;
469 template <typename Stream, typename Operation>
470 inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
471 READWRITE(VARINT(nBlocks));
472 READWRITE(VARINT(nSize));
473 READWRITE(VARINT(nUndoSize));
474 READWRITE(VARINT(nHeightFirst));
475 READWRITE(VARINT(nHeightLast));
476 READWRITE(VARINT(nTimeFirst));
477 READWRITE(VARINT(nTimeLast));
494 std::string ToString() const;
496 // update statistics (does not update nSize)
497 void AddBlock(unsigned int nHeightIn, uint64_t nTimeIn) {
498 if (nBlocks==0 || nHeightFirst > nHeightIn)
499 nHeightFirst = nHeightIn;
500 if (nBlocks==0 || nTimeFirst > nTimeIn)
501 nTimeFirst = nTimeIn;
503 if (nHeightIn > nHeightLast)
504 nHeightLast = nHeightIn;
505 if (nTimeIn > nTimeLast)
510 /** Capture information about block/transaction validation */
511 class CValidationState {
514 MODE_VALID, // everything ok
515 MODE_INVALID, // network rule violation (DoS value may be set)
516 MODE_ERROR, // run-time error
519 std::string strRejectReason;
520 unsigned char chRejectCode;
521 bool corruptionPossible;
523 CValidationState() : mode(MODE_VALID), nDoS(0), chRejectCode(0), corruptionPossible(false) {}
524 bool DoS(int level, bool ret = false,
525 unsigned char chRejectCodeIn=0, std::string strRejectReasonIn="",
526 bool corruptionIn=false) {
527 chRejectCode = chRejectCodeIn;
528 strRejectReason = strRejectReasonIn;
529 corruptionPossible = corruptionIn;
530 if (mode == MODE_ERROR)
536 bool Invalid(bool ret = false,
537 unsigned char _chRejectCode=0, std::string _strRejectReason="") {
538 return DoS(0, ret, _chRejectCode, _strRejectReason);
540 bool Error(std::string strRejectReasonIn="") {
541 if (mode == MODE_VALID)
542 strRejectReason = strRejectReasonIn;
546 bool Abort(const std::string &msg) {
550 bool IsValid() const {
551 return mode == MODE_VALID;
553 bool IsInvalid() const {
554 return mode == MODE_INVALID;
556 bool IsError() const {
557 return mode == MODE_ERROR;
559 bool IsInvalid(int &nDoSOut) const {
566 bool CorruptionPossible() const {
567 return corruptionPossible;
569 unsigned char GetRejectCode() const { return chRejectCode; }
570 std::string GetRejectReason() const { return strRejectReason; }
573 /** RAII wrapper for VerifyDB: Verify consistency of the block and coin databases */
578 bool VerifyDB(CCoinsView *coinsview, int nCheckLevel, int nCheckDepth);
581 /** Find the last common block between the parameter chain and a locator. */
582 CBlockIndex* FindForkInGlobalIndex(const CChain& chain, const CBlockLocator& locator);
584 /** The currently-connected chain of blocks. */
585 extern CChain chainActive;
587 /** Global variable that points to the active CCoinsView (protected by cs_main) */
588 extern CCoinsViewCache *pcoinsTip;
590 /** Global variable that points to the active block tree (protected by cs_main) */
591 extern CBlockTreeDB *pblocktree;
593 struct CBlockTemplate
596 std::vector<CAmount> vTxFees;
597 std::vector<int64_t> vTxSigOps;
605 /** Used to relay blocks as header + vector<merkle branch>
611 // Public only for unit testing
613 CPartialMerkleTree txn;
616 // Public only for unit testing and relay testing
618 std::vector<std::pair<unsigned int, uint256> > vMatchedTxn;
620 // Create from a CBlock, filtering transactions according to filter
621 // Note that this will call IsRelevantAndUpdate on the filter for each transaction,
622 // thus the filter will likely be modified.
623 CMerkleBlock(const CBlock& block, CBloomFilter& filter);
625 ADD_SERIALIZE_METHODS;
627 template <typename Stream, typename Operation>
628 inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
635 class CWalletInterface {
637 virtual void SyncTransaction(const CTransaction &tx, const CBlock *pblock) =0;
638 virtual void EraseFromWallet(const uint256 &hash) =0;
639 virtual void SetBestChain(const CBlockLocator &locator) =0;
640 virtual void UpdatedTransaction(const uint256 &hash) =0;
641 virtual void Inventory(const uint256 &hash) =0;
642 virtual void ResendWalletTransactions() =0;
643 friend void ::RegisterWallet(CWalletInterface*);
644 friend void ::UnregisterWallet(CWalletInterface*);
645 friend void ::UnregisterAllWallets();
648 #endif // BITCOIN_MAIN_H