diff options
author | Pieter Wuille <pieter.wuille@gmail.com> | 2015-03-13 09:25:34 -0700 |
---|---|---|
committer | Pieter Wuille <pieter.wuille@gmail.com> | 2015-03-27 17:24:07 -0700 |
commit | a1f425b48bb3c2c2e8b3ee00c1020bc18dc70a26 (patch) | |
tree | cc56057330297065648d132cd862aceccfd5f5aa /src | |
parent | 4635a4c4e7b706f4fab35a06cf2782d55a11b1b8 (diff) | |
download | bitcoin-a1f425b48bb3c2c2e8b3ee00c1020bc18dc70a26.tar.xz |
Add a consistency check for the block chain data structures
This adds a -checkblockindex (defaulting to true for regtest), which occasionally
does a full consistency check for mapBlockIndex, setBlockIndexCandidates, chainActive, and
mapBlocksUnlinked.
Diffstat (limited to 'src')
-rw-r--r-- | src/chainparams.cpp | 10 | ||||
-rw-r--r-- | src/chainparams.h | 8 | ||||
-rw-r--r-- | src/init.cpp | 5 | ||||
-rw-r--r-- | src/main.cpp | 147 | ||||
-rw-r--r-- | src/main.h | 1 | ||||
-rw-r--r-- | src/test/test_bitcoin.cpp | 1 |
6 files changed, 157 insertions, 15 deletions
diff --git a/src/chainparams.cpp b/src/chainparams.cpp index 0291fd9864..ffcbaceb0a 100644 --- a/src/chainparams.cpp +++ b/src/chainparams.cpp @@ -168,8 +168,8 @@ public: fRequireRPCPassword = true; fMiningRequiresPeers = true; - fDefaultCheckMemPool = false; fAllowMinDifficultyBlocks = false; + fDefaultConsistencyChecks = false; fRequireStandard = true; fMineBlocksOnDemand = false; fSkipProofOfWorkCheck = false; @@ -227,8 +227,8 @@ public: fRequireRPCPassword = true; fMiningRequiresPeers = true; - fDefaultCheckMemPool = false; fAllowMinDifficultyBlocks = true; + fDefaultConsistencyChecks = false; fRequireStandard = false; fMineBlocksOnDemand = false; fTestnetToBeDeprecatedFieldRPC = true; @@ -272,8 +272,8 @@ public: fRequireRPCPassword = false; fMiningRequiresPeers = false; - fDefaultCheckMemPool = true; fAllowMinDifficultyBlocks = true; + fDefaultConsistencyChecks = true; fRequireStandard = false; fMineBlocksOnDemand = true; fTestnetToBeDeprecatedFieldRPC = false; @@ -299,7 +299,7 @@ public: fRequireRPCPassword = false; fMiningRequiresPeers = false; - fDefaultCheckMemPool = true; + fDefaultConsistencyChecks = true; fAllowMinDifficultyBlocks = false; fMineBlocksOnDemand = true; } @@ -315,7 +315,7 @@ public: virtual void setEnforceBlockUpgradeMajority(int anEnforceBlockUpgradeMajority) { nEnforceBlockUpgradeMajority=anEnforceBlockUpgradeMajority; } virtual void setRejectBlockOutdatedMajority(int anRejectBlockOutdatedMajority) { nRejectBlockOutdatedMajority=anRejectBlockOutdatedMajority; } virtual void setToCheckBlockUpgradeMajority(int anToCheckBlockUpgradeMajority) { nToCheckBlockUpgradeMajority=anToCheckBlockUpgradeMajority; } - virtual void setDefaultCheckMemPool(bool afDefaultCheckMemPool) { fDefaultCheckMemPool=afDefaultCheckMemPool; } + virtual void setDefaultConsistencyChecks(bool afDefaultConsistencyChecks) { fDefaultConsistencyChecks=afDefaultConsistencyChecks; } virtual void setAllowMinDifficultyBlocks(bool afAllowMinDifficultyBlocks) { fAllowMinDifficultyBlocks=afAllowMinDifficultyBlocks; } virtual void setSkipProofOfWorkCheck(bool afSkipProofOfWorkCheck) { fSkipProofOfWorkCheck = afSkipProofOfWorkCheck; } }; diff --git a/src/chainparams.h b/src/chainparams.h index 5d1ee1d3c6..ef20a88558 100644 --- a/src/chainparams.h +++ b/src/chainparams.h @@ -58,8 +58,8 @@ public: bool RequireRPCPassword() const { return fRequireRPCPassword; } /** Make miner wait to have peers to avoid wasting work */ bool MiningRequiresPeers() const { return fMiningRequiresPeers; } - /** Default value for -checkmempool argument */ - bool DefaultCheckMemPool() const { return fDefaultCheckMemPool; } + /** Default value for -checkmempool and -checkblockindex argument */ + bool DefaultConsistencyChecks() const { return fDefaultConsistencyChecks; } /** Allow mining of a min-difficulty block */ bool AllowMinDifficultyBlocks() const { return fAllowMinDifficultyBlocks; } /** Skip proof-of-work check: allow mining of any difficulty block */ @@ -103,8 +103,8 @@ protected: std::vector<CAddress> vFixedSeeds; bool fRequireRPCPassword; bool fMiningRequiresPeers; - bool fDefaultCheckMemPool; bool fAllowMinDifficultyBlocks; + bool fDefaultConsistencyChecks; bool fRequireStandard; bool fMineBlocksOnDemand; bool fSkipProofOfWorkCheck; @@ -124,7 +124,7 @@ public: virtual void setEnforceBlockUpgradeMajority(int anEnforceBlockUpgradeMajority)=0; virtual void setRejectBlockOutdatedMajority(int anRejectBlockOutdatedMajority)=0; virtual void setToCheckBlockUpgradeMajority(int anToCheckBlockUpgradeMajority)=0; - virtual void setDefaultCheckMemPool(bool aDefaultCheckMemPool)=0; + virtual void setDefaultConsistencyChecks(bool aDefaultConsistencyChecks)=0; virtual void setAllowMinDifficultyBlocks(bool aAllowMinDifficultyBlocks)=0; virtual void setSkipProofOfWorkCheck(bool aSkipProofOfWorkCheck)=0; }; diff --git a/src/init.cpp b/src/init.cpp index df199ae487..9ff87ad1e6 100644 --- a/src/init.cpp +++ b/src/init.cpp @@ -656,8 +656,9 @@ bool AppInit2(boost::thread_group& threadGroup) if (GetBoolArg("-benchmark", false)) InitWarning(_("Warning: Unsupported argument -benchmark ignored, use -debug=bench.")); - // Checkmempool defaults to true in regtest mode - mempool.setSanityCheck(GetBoolArg("-checkmempool", Params().DefaultCheckMemPool())); + // Checkmempool and checkblockindex default to true in regtest mode + mempool.setSanityCheck(GetBoolArg("-checkmempool", Params().DefaultConsistencyChecks())); + fCheckBlockIndex = GetBoolArg("-checkblockindex", Params().DefaultConsistencyChecks()); Checkpoints::fEnabled = GetBoolArg("-checkpoints", true); // -par=0 means autodetect, but nScriptCheckThreads==0 means no concurrency diff --git a/src/main.cpp b/src/main.cpp index 6418590462..dc6f37c220 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -51,6 +51,7 @@ bool fImporting = false; bool fReindex = false; bool fTxIndex = false; bool fIsBareMultisigStd = true; +bool fCheckBlockIndex = false; unsigned int nCoinCacheSize = 5000; @@ -67,6 +68,8 @@ map<uint256, COrphanTx> mapOrphanTransactions; map<uint256, set<uint256> > mapOrphanTransactionsByPrev; void EraseOrphansFor(NodeId peer); +static void CheckBlockIndex(); + /** Constant stuff for coinbase transactions we create: */ CScript COINBASE_FLAGS; @@ -77,7 +80,7 @@ namespace { struct CBlockIndexWorkComparator { - bool operator()(CBlockIndex *pa, CBlockIndex *pb) { + bool operator()(CBlockIndex *pa, CBlockIndex *pb) const { // First sort by most total work, ... if (pa->nChainWork > pb->nChainWork) return false; if (pa->nChainWork < pb->nChainWork) return true; @@ -99,8 +102,8 @@ namespace { CBlockIndex *pindexBestInvalid; /** - * The set of all CBlockIndex entries with BLOCK_VALID_TRANSACTIONS or better that are at least - * as good as our current tip. Entries may be failed, though. + * The set of all CBlockIndex entries with BLOCK_VALID_TRANSACTIONS (for itself and all ancestors) and + * as good as our current tip or better. Entries may be failed, though. */ set<CBlockIndex*, CBlockIndexWorkComparator> setBlockIndexCandidates; /** Number of nodes with fSyncStarted. */ @@ -2195,6 +2198,7 @@ bool ActivateBestChain(CValidationState &state, CBlock *pblock) { uiInterface.NotifyBlockTip(hashNewTip); } } while(pindexMostWork != chainActive.Tip()); + CheckBlockIndex(); // Write changes periodically to disk, after relay. if (!FlushStateToDisk(state, FLUSH_STATE_PERIODIC)) { @@ -2331,7 +2335,9 @@ bool ReceivedBlockTransactions(const CBlock &block, CValidationState& state, CBl CBlockIndex *pindex = queue.front(); queue.pop_front(); pindex->nChainTx = (pindex->pprev ? pindex->pprev->nChainTx : 0) + pindex->nTx; - setBlockIndexCandidates.insert(pindex); + if (chainActive.Tip() == NULL || !setBlockIndexCandidates.value_comp()(pindex, chainActive.Tip())) { + setBlockIndexCandidates.insert(pindex); + } std::pair<std::multimap<CBlockIndex*, CBlockIndex*>::iterator, std::multimap<CBlockIndex*, CBlockIndex*>::iterator> range = mapBlocksUnlinked.equal_range(pindex); while (range.first != range.second) { std::multimap<CBlockIndex*, CBlockIndex*>::iterator it = range.first; @@ -2745,6 +2751,7 @@ bool ProcessNewBlock(CValidationState &state, CNode* pfrom, CBlock* pblock, CDis if (pindex && pfrom) { mapBlockSource[pindex->GetBlockHash()] = pfrom->GetId(); } + CheckBlockIndex(); if (!ret) return error("%s : AcceptBlock FAILED", __func__); } @@ -3212,6 +3219,136 @@ bool LoadExternalBlockFile(FILE* fileIn, CDiskBlockPos *dbp) return nLoaded > 0; } +void static CheckBlockIndex() +{ + if (!fCheckBlockIndex) { + return; + } + + LOCK(cs_main); + + // Build forward-pointing map of the entire block tree. + std::multimap<CBlockIndex*,CBlockIndex*> forward; + for (BlockMap::iterator it = mapBlockIndex.begin(); it != mapBlockIndex.end(); it++) { + forward.insert(std::make_pair(it->second->pprev, it->second)); + } + + assert(forward.size() == mapBlockIndex.size()); + + std::pair<std::multimap<CBlockIndex*,CBlockIndex*>::iterator,std::multimap<CBlockIndex*,CBlockIndex*>::iterator> rangeGenesis = forward.equal_range(NULL); + CBlockIndex *pindex = rangeGenesis.first->second; + rangeGenesis.first++; + assert(rangeGenesis.first == rangeGenesis.second); // There is only one index entry with parent NULL. + + // Iterate over the entire block tree, using depth-first search. + // Along the way, remember whether there are blocks on the path from genesis + // block being explored which are the first to have certain properties. + size_t nNodes = 0; + int nHeight = 0; + CBlockIndex* pindexFirstInvalid = NULL; // Oldest ancestor of pindex which is invalid. + CBlockIndex* pindexFirstMissing = NULL; // Oldest ancestor of pindex which does not have BLOCK_HAVE_DATA. + CBlockIndex* pindexFirstNotTreeValid = NULL; // Oldest ancestor of pindex which does not have BLOCK_VALID_TREE (regardless of being valid or not). + CBlockIndex* pindexFirstNotChainValid = NULL; // Oldest ancestor of pindex which does not have BLOCK_VALID_CHAIN (regardless of being valid or not). + CBlockIndex* pindexFirstNotScriptsValid = NULL; // Oldest ancestor of pindex which does not have BLOCK_VALID_SCRIPTS (regardless of being valid or not). + while (pindex != NULL) { + nNodes++; + if (pindexFirstInvalid == NULL && pindex->nStatus & BLOCK_FAILED_VALID) pindexFirstInvalid = pindex; + if (pindexFirstMissing == NULL && !(pindex->nStatus & BLOCK_HAVE_DATA)) pindexFirstMissing = pindex; + if (pindex->pprev != NULL && pindexFirstNotTreeValid == NULL && (pindex->nStatus & BLOCK_VALID_MASK) < BLOCK_VALID_TREE) pindexFirstNotTreeValid = pindex; + if (pindex->pprev != NULL && pindexFirstNotChainValid == NULL && (pindex->nStatus & BLOCK_VALID_MASK) < BLOCK_VALID_CHAIN) pindexFirstNotChainValid = pindex; + if (pindex->pprev != NULL && pindexFirstNotScriptsValid == NULL && (pindex->nStatus & BLOCK_VALID_MASK) < BLOCK_VALID_SCRIPTS) pindexFirstNotScriptsValid = pindex; + + // Begin: actual consistency checks. + if (pindex->pprev == NULL) { + // Genesis block checks. + assert(pindex->GetBlockHash() == Params().HashGenesisBlock()); // Genesis block's hash must match. + assert(pindex == chainActive.Genesis()); // The current active chain's genesis block must be this block. + } + assert((pindexFirstMissing != NULL) == (pindex->nChainTx == 0)); // nChainTx == 0 is used to signal that all parent block's transaction data is available. + assert(pindex->nHeight == nHeight); // nHeight must be consistent. + assert(pindex->pprev == NULL || pindex->nChainWork >= pindex->pprev->nChainWork); // For every block except the genesis block, the chainwork must be larger than the parent's. + assert(nHeight < 2 || (pindex->pskip && (pindex->pskip->nHeight < nHeight))); // The pskip pointer must point back for all but the first 2 blocks. + assert(pindexFirstNotTreeValid == NULL); // All mapBlockIndex entries must at least be TREE valid + if ((pindex->nStatus & BLOCK_VALID_MASK) >= BLOCK_VALID_TREE) assert(pindexFirstNotTreeValid == NULL); // TREE valid implies all parents are TREE valid + if ((pindex->nStatus & BLOCK_VALID_MASK) >= BLOCK_VALID_CHAIN) assert(pindexFirstNotChainValid == NULL); // CHAIN valid implies all parents are CHAIN valid + if ((pindex->nStatus & BLOCK_VALID_MASK) >= BLOCK_VALID_SCRIPTS) assert(pindexFirstNotScriptsValid == NULL); // SCRIPTS valid implies all parents are SCRIPTS valid + if (pindexFirstInvalid == NULL) { + // Checks for not-invalid blocks. + assert((pindex->nStatus & BLOCK_FAILED_MASK) == 0); // The failed mask cannot be set for blocks without invalid parents. + } + if (!CBlockIndexWorkComparator()(pindex, chainActive.Tip()) && pindexFirstMissing == NULL) { + if (pindexFirstInvalid == NULL) { // If this block sorts at least as good as the current tip and is valid, it must be in setBlockIndexCandidates. + assert(setBlockIndexCandidates.count(pindex)); + } + } else { // If this block sorts worse than the current tip, it cannot be in setBlockIndexCandidates. + assert(setBlockIndexCandidates.count(pindex) == 0); + } + // Check whether this block is in mapBlocksUnlinked. + std::pair<std::multimap<CBlockIndex*,CBlockIndex*>::iterator,std::multimap<CBlockIndex*,CBlockIndex*>::iterator> rangeUnlinked = mapBlocksUnlinked.equal_range(pindex->pprev); + bool foundInUnlinked = false; + while (rangeUnlinked.first != rangeUnlinked.second) { + assert(rangeUnlinked.first->first == pindex->pprev); + if (rangeUnlinked.first->second == pindex) { + foundInUnlinked = true; + break; + } + rangeUnlinked.first++; + } + if (pindex->pprev && pindex->nStatus & BLOCK_HAVE_DATA && pindexFirstMissing != NULL) { + if (pindexFirstInvalid == NULL) { // If this block has block data available, some parent doesn't, and has no invalid parents, it must be in mapBlocksUnlinked. + assert(foundInUnlinked); + } + } else { // If this block does not have block data available, or all parents do, it cannot be in mapBlocksUnlinked. + assert(!foundInUnlinked); + } + // assert(pindex->GetBlockHash() == pindex->GetBlockHeader().GetHash()); // Perhaps too slow + // End: actual consistency checks. + + // Try descending into the first subnode. + std::pair<std::multimap<CBlockIndex*,CBlockIndex*>::iterator,std::multimap<CBlockIndex*,CBlockIndex*>::iterator> range = forward.equal_range(pindex); + if (range.first != range.second) { + // A subnode was found. + pindex = range.first->second; + nHeight++; + continue; + } + // This is a leaf node. + // Move upwards until we reach a node of which we have not yet visited the last child. + while (pindex) { + // We are going to either move to a parent or a sibling of pindex. + // If pindex was the first with a certain property, unset the corresponding variable. + if (pindex == pindexFirstInvalid) pindexFirstInvalid = NULL; + if (pindex == pindexFirstMissing) pindexFirstMissing = NULL; + if (pindex == pindexFirstNotTreeValid) pindexFirstNotTreeValid = NULL; + if (pindex == pindexFirstNotChainValid) pindexFirstNotChainValid = NULL; + if (pindex == pindexFirstNotScriptsValid) pindexFirstNotScriptsValid = NULL; + // Find our parent. + CBlockIndex* pindexPar = pindex->pprev; + // Find which child we just visited. + std::pair<std::multimap<CBlockIndex*,CBlockIndex*>::iterator,std::multimap<CBlockIndex*,CBlockIndex*>::iterator> rangePar = forward.equal_range(pindexPar); + while (rangePar.first->second != pindex) { + assert(rangePar.first != rangePar.second); // Our parent must have at least the node we're coming from as child. + rangePar.first++; + } + // Proceed to the next one. + rangePar.first++; + if (rangePar.first != rangePar.second) { + // Move to the sibling. + pindex = rangePar.first->second; + break; + } else { + // Move up further. + pindex = pindexPar; + nHeight--; + continue; + } + } + } + + // Check that we actually traversed the entire map. + assert(nNodes == forward.size()); +} + ////////////////////////////////////////////////////////////////////////////// // // CAlert @@ -3968,6 +4105,8 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, LogPrint("net", "more getheaders (%d) to end to peer=%d (startheight:%d)\n", pindexLast->nHeight, pfrom->id, pfrom->nStartingHeight); pfrom->PushMessage("getheaders", chainActive.GetLocator(pindexLast), uint256(0)); } + + CheckBlockIndex(); } else if (strCommand == "block" && !fImporting && !fReindex) // Ignore blocks received while importing diff --git a/src/main.h b/src/main.h index e4096e9612..71f21716d0 100644 --- a/src/main.h +++ b/src/main.h @@ -126,6 +126,7 @@ extern bool fReindex; extern int nScriptCheckThreads; extern bool fTxIndex; extern bool fIsBareMultisigStd; +extern bool fCheckBlockIndex; extern unsigned int nCoinCacheSize; extern CFeeRate minRelayTxFee; diff --git a/src/test/test_bitcoin.cpp b/src/test/test_bitcoin.cpp index e50218d8ef..5269e3bda7 100644 --- a/src/test/test_bitcoin.cpp +++ b/src/test/test_bitcoin.cpp @@ -31,6 +31,7 @@ struct TestingSetup { TestingSetup() { fPrintToDebugLog = false; // don't want to write to debug.log file + fCheckBlockIndex = true; SelectParams(CBaseChainParams::UNITTEST); noui_connect(); #ifdef ENABLE_WALLET |