diff --git a/src/chain.h b/src/chain.h index 05df59a35..af65387d4 100644 --- a/src/chain.h +++ b/src/chain.h @@ -1,415 +1,411 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_CHAIN_H #define BITCOIN_CHAIN_H #include "arith_uint256.h" #include "blockstatus.h" #include "blockvalidity.h" #include "consensus/params.h" #include "diskblockpos.h" #include "pow.h" #include "primitives/block.h" #include "tinyformat.h" #include "uint256.h" #include #include /** * Maximum amount of time that a block timestamp is allowed to exceed the * current network-adjusted time before the block will be accepted. */ static const int64_t MAX_FUTURE_BLOCK_TIME = 2 * 60 * 60; /** * Timestamp window used as a grace period by code that compares external * timestamps (such as timestamps passed to RPCs, or wallet key creation times) * to block timestamps. This should be set at least as high as * MAX_FUTURE_BLOCK_TIME. */ static const int64_t TIMESTAMP_WINDOW = MAX_FUTURE_BLOCK_TIME; /** * The block chain is a tree shaped structure starting with the genesis block at * the root, with each block potentially having multiple candidates to be the * next block. A blockindex may have multiple pprev pointing to it, but at most * one of them can be part of the currently active branch. */ class CBlockIndex { public: //! pointer to the hash of the block, if any. Memory is owned by this //! CBlockIndex const uint256 *phashBlock; //! pointer to the index of the predecessor of this block CBlockIndex *pprev; //! pointer to the index of some further predecessor of this block CBlockIndex *pskip; //! height of the entry in the chain. The genesis block has height 0 int nHeight; //! Which # file this block is stored in (blk?????.dat) int nFile; //! Byte offset within blk?????.dat where this block's data is stored unsigned int nDataPos; //! Byte offset within rev?????.dat where this block's undo data is stored unsigned int nUndoPos; //! (memory only) Total amount of work (expected number of hashes) in the //! chain up to and including this block arith_uint256 nChainWork; //! Number of transactions in this block. //! Note: in a potential headers-first mode, this number cannot be relied //! upon unsigned int nTx; //! (memory only) Number of transactions in the chain up to and including //! this block. //! This value will be non-zero only if and only if transactions for this //! block and all its parents are available. Change to 64-bit type when //! necessary; won't happen before 2030 unsigned int nChainTx; //! Verification status of this block. See enum BlockStatus BlockStatus nStatus; //! block header int32_t nVersion; uint256 hashMerkleRoot; uint32_t nTime; uint32_t nBits; uint32_t nNonce; //! (memory only) Sequential id assigned to distinguish order in which //! blocks are received. int32_t nSequenceId; //! (memory only) block header metadata uint64_t nTimeReceived; //! (memory only) Maximum nTime in the chain upto and including this block. unsigned int nTimeMax; void SetNull() { phashBlock = nullptr; pprev = nullptr; pskip = nullptr; nHeight = 0; nFile = 0; nDataPos = 0; nUndoPos = 0; nChainWork = arith_uint256(); nTx = 0; nChainTx = 0; nStatus = BlockStatus(); nSequenceId = 0; nTimeMax = 0; nVersion = 0; hashMerkleRoot = uint256(); nTime = 0; nTimeReceived = 0; nBits = 0; nNonce = 0; } CBlockIndex() { SetNull(); } CBlockIndex(const CBlockHeader &block) { SetNull(); nVersion = block.nVersion; hashMerkleRoot = block.hashMerkleRoot; nTime = block.nTime; - // Default to block time if nTimeReceived is never set, which - // in effect assumes that this block is honestly mined. - // Note that nTimeReceived isn't written to disk, so blocks read from - // disk will be assumed to be honestly mined. - nTimeReceived = block.nTime; + nTimeReceived = 0; nBits = block.nBits; nNonce = block.nNonce; } CDiskBlockPos GetBlockPos() const { CDiskBlockPos ret; if (nStatus.hasData()) { ret.nFile = nFile; ret.nPos = nDataPos; } return ret; } CDiskBlockPos GetUndoPos() const { CDiskBlockPos ret; if (nStatus.hasUndo()) { ret.nFile = nFile; ret.nPos = nUndoPos; } return ret; } CBlockHeader GetBlockHeader() const { CBlockHeader block; block.nVersion = nVersion; if (pprev) { block.hashPrevBlock = pprev->GetBlockHash(); } block.hashMerkleRoot = hashMerkleRoot; block.nTime = nTime; block.nBits = nBits; block.nNonce = nNonce; return block; } uint256 GetBlockHash() const { return *phashBlock; } int64_t GetBlockTime() const { return int64_t(nTime); } int64_t GetBlockTimeMax() const { return int64_t(nTimeMax); } int64_t GetHeaderReceivedTime() const { return nTimeReceived; } int64_t GetReceivedTimeDiff() const { return GetHeaderReceivedTime() - GetBlockTime(); } enum { nMedianTimeSpan = 11 }; int64_t GetMedianTimePast() const { int64_t pmedian[nMedianTimeSpan]; int64_t *pbegin = &pmedian[nMedianTimeSpan]; int64_t *pend = &pmedian[nMedianTimeSpan]; const CBlockIndex *pindex = this; for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev) { *(--pbegin) = pindex->GetBlockTime(); } std::sort(pbegin, pend); return pbegin[(pend - pbegin) / 2]; } std::string ToString() const { return strprintf( "CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)", pprev, nHeight, hashMerkleRoot.ToString(), GetBlockHash().ToString()); } //! Check whether this block index entry is valid up to the passed validity //! level. bool IsValid(enum BlockValidity nUpTo = BlockValidity::TRANSACTIONS) const { return nStatus.isValid(nUpTo); } //! Raise the validity level of this block index entry. //! Returns true if the validity was changed. bool RaiseValidity(enum BlockValidity nUpTo) { // Only validity flags allowed. if (nStatus.isInvalid()) { return false; } if (nStatus.getValidity() >= nUpTo) { return false; } nStatus = nStatus.withValidity(nUpTo); return true; } //! Build the skiplist pointer for this entry. void BuildSkip(); //! Efficiently find an ancestor of this block. CBlockIndex *GetAncestor(int height); const CBlockIndex *GetAncestor(int height) const; }; /** * Maintain a map of CBlockIndex for all known headers. */ struct BlockHasher { size_t operator()(const uint256 &hash) const { return hash.GetCheapHash(); } }; typedef std::unordered_map BlockMap; extern BlockMap mapBlockIndex; arith_uint256 GetBlockProof(const CBlockIndex &block); /** * Return the time it would take to redo the work difference between from and * to, assuming the current hashrate corresponds to the difficulty at tip, in * seconds. */ int64_t GetBlockProofEquivalentTime(const CBlockIndex &to, const CBlockIndex &from, const CBlockIndex &tip, const Consensus::Params &); /** * Find the forking point between two chain tips. */ const CBlockIndex *LastCommonAncestor(const CBlockIndex *pa, const CBlockIndex *pb); /** * Check if two block index are on the same fork. */ bool AreOnTheSameFork(const CBlockIndex *pa, const CBlockIndex *pb); /** Used to marshal pointers into hashes for db storage. */ class CDiskBlockIndex : public CBlockIndex { public: uint256 hashPrev; CDiskBlockIndex() { hashPrev = uint256(); } explicit CDiskBlockIndex(const CBlockIndex *pindex) : CBlockIndex(*pindex) { hashPrev = (pprev ? pprev->GetBlockHash() : uint256()); } ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { int _nVersion = s.GetVersion(); if (!(s.GetType() & SER_GETHASH)) { READWRITE(VARINT(_nVersion)); } READWRITE(VARINT(nHeight)); READWRITE(nStatus); READWRITE(VARINT(nTx)); if (nStatus.hasData() || nStatus.hasUndo()) { READWRITE(VARINT(nFile)); } if (nStatus.hasData()) { READWRITE(VARINT(nDataPos)); } if (nStatus.hasUndo()) { READWRITE(VARINT(nUndoPos)); } // block header READWRITE(this->nVersion); READWRITE(hashPrev); READWRITE(hashMerkleRoot); READWRITE(nTime); READWRITE(nBits); READWRITE(nNonce); } uint256 GetBlockHash() const { CBlockHeader block; block.nVersion = nVersion; block.hashPrevBlock = hashPrev; block.hashMerkleRoot = hashMerkleRoot; block.nTime = nTime; block.nBits = nBits; block.nNonce = nNonce; return block.GetHash(); } std::string ToString() const { std::string str = "CDiskBlockIndex("; str += CBlockIndex::ToString(); str += strprintf("\n hashBlock=%s, hashPrev=%s)", GetBlockHash().ToString(), hashPrev.ToString()); return str; } }; /** * An in-memory indexed chain of blocks. */ class CChain { private: std::vector vChain; public: /** * Returns the index entry for the genesis block of this chain, or nullptr * if none. */ CBlockIndex *Genesis() const { return vChain.size() > 0 ? vChain[0] : nullptr; } /** * Returns the index entry for the tip of this chain, or nullptr if none. */ CBlockIndex *Tip() const { return vChain.size() > 0 ? vChain[vChain.size() - 1] : nullptr; } /** * Returns the index entry at a particular height in this chain, or nullptr * if no such height exists. */ CBlockIndex *operator[](int nHeight) const { if (nHeight < 0 || nHeight >= (int)vChain.size()) { return nullptr; } return vChain[nHeight]; } /** Compare two chains efficiently. */ friend bool operator==(const CChain &a, const CChain &b) { return a.vChain.size() == b.vChain.size() && a.vChain[a.vChain.size() - 1] == b.vChain[b.vChain.size() - 1]; } /** Efficiently check whether a block is present in this chain. */ bool Contains(const CBlockIndex *pindex) const { return (*this)[pindex->nHeight] == pindex; } /** * Find the successor of a block in this chain, or nullptr if the given * index is not found or is the tip. */ CBlockIndex *Next(const CBlockIndex *pindex) const { if (!Contains(pindex)) { return nullptr; } return (*this)[pindex->nHeight + 1]; } /** * Return the maximal height in the chain. Is equal to chain.Tip() ? * chain.Tip()->nHeight : -1. */ int Height() const { return vChain.size() - 1; } /** Set/initialize a chain with a given tip. */ void SetTip(CBlockIndex *pindex); /** * Return a CBlockLocator that refers to a block in this chain (by default * the tip). */ CBlockLocator GetLocator(const CBlockIndex *pindex = nullptr) const; /** * Find the last common block between this chain and a block index entry. */ const CBlockIndex *FindFork(const CBlockIndex *pindex) const; /** * Find the earliest block with timestamp equal or greater than the given. */ CBlockIndex *FindEarliestAtLeast(int64_t nTime) const; }; #endif // BITCOIN_CHAIN_H diff --git a/src/test/blockindex_tests.cpp b/src/test/blockindex_tests.cpp index 640f84e69..fd144926b 100644 --- a/src/test/blockindex_tests.cpp +++ b/src/test/blockindex_tests.cpp @@ -1,424 +1,424 @@ // Copyright (c) 2018 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "blockvalidity.h" #include "chain.h" #include "diskblockpos.h" #include "uint256.h" #include "test/test_bitcoin.h" #include #include BOOST_FIXTURE_TEST_SUITE(blockindex_tests, BasicTestingSetup) BOOST_AUTO_TEST_CASE(get_block_header) { const int32_t expectedVersion = 4; const uint256 expectedMerkleRoot = uint256(); const uint32_t expectedBlockTime = 123; const uint32_t expectedDifficultyBits = 234; const uint32_t expectedNonce = 345; CBlockHeader header; header.nVersion = expectedVersion; header.hashMerkleRoot = expectedMerkleRoot; header.nTime = expectedBlockTime; header.nBits = expectedDifficultyBits; header.nNonce = expectedNonce; CBlockIndex index = CBlockIndex(header); CBlockHeader checkHeader = index.GetBlockHeader(); BOOST_CHECK(checkHeader.nVersion == expectedVersion); BOOST_CHECK(checkHeader.hashMerkleRoot == expectedMerkleRoot); BOOST_CHECK(checkHeader.nTime == expectedBlockTime); BOOST_CHECK(checkHeader.nBits == expectedDifficultyBits); BOOST_CHECK(checkHeader.nNonce == expectedNonce); } BOOST_AUTO_TEST_CASE(get_disk_positions) { // Test against all validity values std::set validityValues{ BlockValidity::UNKNOWN, BlockValidity::HEADER, BlockValidity::TREE, BlockValidity::TRANSACTIONS, BlockValidity::CHAIN, BlockValidity::SCRIPTS}; for (BlockValidity validity : validityValues) { // Test against all combinations of data and undo flags for (int flags = 0; flags <= 0x03; flags++) { // Generate some values to test against const int expectedFile = flags * 123; const unsigned int expectedDataPosition = flags * 234; const unsigned int expectedUndoPosition = flags * 345; CBlockIndex index; index.nStatus = index.nStatus.withValidity(BlockValidity(validity)); // All combinations of data and undo if (flags & 0x01) { index.nStatus = index.nStatus.withData(); index.nFile = expectedFile; index.nDataPos = expectedDataPosition; } if (flags & 0x02) { index.nStatus = index.nStatus.withUndo(); index.nFile = expectedFile; index.nUndoPos = expectedUndoPosition; } // Data and undo positions should be unmodified CDiskBlockPos dataPosition = index.GetBlockPos(); if (flags & 0x01) { BOOST_CHECK(dataPosition.nFile == expectedFile); BOOST_CHECK(dataPosition.nPos == expectedDataPosition); } else { BOOST_CHECK(dataPosition == CDiskBlockPos()); } CDiskBlockPos undoPosition = index.GetUndoPos(); if (flags & 0x02) { BOOST_CHECK(undoPosition.nFile == expectedFile); BOOST_CHECK(undoPosition.nPos == expectedUndoPosition); } else { BOOST_CHECK(undoPosition == CDiskBlockPos()); } } } } BOOST_AUTO_TEST_CASE(get_block_hash) { CBlockIndex index = CBlockIndex(); /* Test with all 0 hash */ const uint256 zeroHash = uint256(); index.phashBlock = &zeroHash; uint256 hash = index.GetBlockHash(); BOOST_CHECK(hash == zeroHash); /* Test with a random hash */ std::vector hashBytes(32); std::generate(hashBytes.begin(), hashBytes.end(), []() { return uint8_t(rand() % 255); }); const uint256 randomHash = uint256(hashBytes); index.phashBlock = &randomHash; hash = index.GetBlockHash(); BOOST_CHECK(hash == randomHash); } BOOST_AUTO_TEST_CASE(received_time) { // Set to UINT32_MAX because that's the maximum value header.nTime can hold const int64_t expectedBlockTime = std::numeric_limits::max(); CBlockHeader header; header.nTime = uint32_t(expectedBlockTime); CBlockIndex index = CBlockIndex(header); - // nTimeReceived defaults to block time - BOOST_CHECK(index.nTimeReceived == expectedBlockTime); + // nTimeReceived defaults to 0 + BOOST_CHECK_EQUAL(index.nTimeReceived, 0); // nTimeReceived can be updated to the actual received time, which may // be before or after the miner's time. for (int64_t receivedTime = expectedBlockTime - 10; // Make sure that receivedTime is tested beyond 32-bit values. receivedTime <= expectedBlockTime + 10; receivedTime++) { index.nTimeReceived = receivedTime; - BOOST_CHECK(index.GetBlockTime() == expectedBlockTime); - BOOST_CHECK(index.GetHeaderReceivedTime() == receivedTime); - BOOST_CHECK(index.GetReceivedTimeDiff() == - receivedTime - expectedBlockTime); + BOOST_CHECK_EQUAL(index.GetBlockTime(), expectedBlockTime); + BOOST_CHECK_EQUAL(index.GetHeaderReceivedTime(), receivedTime); + BOOST_CHECK_EQUAL(index.GetReceivedTimeDiff(), + receivedTime - expectedBlockTime); } } BOOST_AUTO_TEST_CASE(median_time_past) { std::array indices; // times in this test are pairs of // Check that MTP is correctly calculated for all cases when block times // are consecutive and greater than previous block times: // 1) All cases where the number of blocks is < 11 // 2) The case where the number of blocks is exactly 11 // 3) The case where the number of blocks is > 11 (but only 11 are used to // calculate MTP. std::array, 12> times = {{{0, 0}, {1, 1}, {2, 1}, {4, 2}, {4, 2}, {5, 4}, {7, 4}, {10, 4}, {12, 4}, {14, 5}, {17, 5}, {20, 7}}}; for (size_t i = 0; i < indices.size(); i++) { indices[i].nTime = times[i].first; if (i > 0) { indices[i].pprev = &indices[i - 1]; } BOOST_CHECK(indices[i].GetMedianTimePast() == times[i].second); } // Test against non-consecutive block times std::array, 12> times2 = {{{0, 0}, {0, 0}, {1, 0}, {3, 1}, {2, 1}, {3, 2}, {4, 2}, {5, 3}, {6, 3}, {7, 3}, {8, 3}, {9, 4}}}; for (size_t i = 0; i < indices.size(); i++) { indices[i].nTime = times2[i].first; BOOST_CHECK(indices[i].GetMedianTimePast() == times2[i].second); } } BOOST_AUTO_TEST_CASE(to_string) { CBlockHeader header = CBlockHeader(); header.hashMerkleRoot = uint256(); CBlockIndex index = CBlockIndex(header); const uint256 hashBlock = uint256(); index.phashBlock = &hashBlock; index.nHeight = 123; CBlockIndex indexPrev = CBlockIndex(); std::string expectedString = ""; std::string indexString = ""; /* CASE 1 : pprev is null */ expectedString = strprintf( "CBlockIndex(pprev=%p, nHeight=123, " "merkle=" "0000000000000000000000000000000000000000000000000000000000000000, " "hashBlock=" "0000000000000000000000000000000000000000000000000000000000000000)", (void *)(nullptr)); index.pprev = nullptr; indexString = index.ToString(); BOOST_CHECK_EQUAL(indexString, expectedString); /* CASE 2 : pprev is indexPrev */ expectedString = strprintf( "CBlockIndex(pprev=%p, nHeight=123, " "merkle=" "0000000000000000000000000000000000000000000000000000000000000000, " "hashBlock=" "0000000000000000000000000000000000000000000000000000000000000000)", &indexPrev); index.pprev = &indexPrev; indexString = index.ToString(); BOOST_CHECK_EQUAL(indexString, expectedString); /* CASE 3 : height is max(int) */ expectedString = strprintf( "CBlockIndex(pprev=%p, nHeight=2147483647, " "merkle=" "0000000000000000000000000000000000000000000000000000000000000000, " "hashBlock=" "0000000000000000000000000000000000000000000000000000000000000000)", &indexPrev); index.nHeight = INT32_MAX; indexString = index.ToString(); BOOST_CHECK_EQUAL(indexString, expectedString); /* CASE 4 : set some Merkle root hash */ expectedString = strprintf( "CBlockIndex(pprev=%p, nHeight=2147483647, " "merkle=" "0000000000000000000000000000000000000000000000000123456789abcdef, " "hashBlock=" "0000000000000000000000000000000000000000000000000000000000000000)", &indexPrev); index.hashMerkleRoot = uint256S("0123456789ABCDEF"); indexString = index.ToString(); BOOST_CHECK_EQUAL(indexString, expectedString); /* CASE 5 : set some block hash */ expectedString = strprintf( "CBlockIndex(pprev=%p, nHeight=2147483647, " "merkle=" "0000000000000000000000000000000000000000000000000123456789abcdef, " "hashBlock=" "000000000000000000000000000000000000000000000000fedcba9876543210)", &indexPrev); const uint256 emptyHashBlock = uint256S("FEDCBA9876543210"); index.phashBlock = &emptyHashBlock; indexString = index.ToString(); BOOST_CHECK_EQUAL(indexString, expectedString); } BOOST_AUTO_TEST_CASE(index_validity_tests) { CBlockIndex index; // Test against all validity values std::set validityValues{ BlockValidity::UNKNOWN, BlockValidity::HEADER, BlockValidity::TREE, BlockValidity::TRANSACTIONS, BlockValidity::CHAIN, BlockValidity::SCRIPTS}; std::set boolValues = {false, true}; for (BlockValidity validity : validityValues) { for (bool withFailed : boolValues) { for (bool withFailedParent : boolValues) { index.nStatus = BlockStatus() .withValidity(validity) .withFailed(withFailed) .withFailedParent(withFailedParent); for (BlockValidity validUpTo : validityValues) { // Test isValidity() bool isValid = index.IsValid(validUpTo); if (validUpTo <= validity && !withFailed && !withFailedParent) { BOOST_CHECK(isValid); } else { BOOST_CHECK(!isValid); } // Test RaiseValidity() CBlockIndex indexRaiseValidity; for (BlockValidity validFrom : validityValues) { indexRaiseValidity.nStatus = BlockStatus() .withValidity(validFrom) .withFailed(withFailed) .withFailedParent(withFailedParent); bool raisedValidity = indexRaiseValidity.RaiseValidity(validUpTo); if (validFrom < validUpTo && !withFailed && !withFailedParent) { BOOST_CHECK(raisedValidity); BOOST_CHECK( indexRaiseValidity.nStatus.getValidity() == validUpTo); } else { BOOST_CHECK(!raisedValidity); BOOST_CHECK( indexRaiseValidity.nStatus.getValidity() == validFrom); } } } } } } } BOOST_AUTO_TEST_CASE(index_ancestors) { std::array indexes; /* Check the skip pointer don't build when there is no precedence */ for (size_t i = 0; i < indexes.size(); i++) { indexes[i] = CBlockIndex(); indexes[i].nHeight = i; indexes[i].pprev = nullptr; indexes[i].pskip = nullptr; indexes[i].BuildSkip(); /* Check that skip not rebuilt if there is no preceding index */ BOOST_CHECK(indexes[i].pskip == nullptr); } for (size_t i = 0; i < indexes.size(); i++) { if (i > 0) { indexes[i].pprev = &indexes[i - 1]; indexes[i].BuildSkip(); /* Check that skip is built */ BOOST_CHECK(indexes[i].pskip != nullptr); /* * Starting from height 2, pskip should be more efficient that * pprev. * Ensure pskip.nHeight < pprev.nHeight */ if (i > 1) { BOOST_CHECK(indexes[i].pskip->nHeight < indexes[i].pprev->nHeight); } /* Find an ancestor 16 indexes behind */ if (i > 16) { CBlockIndex *ancestor = indexes[i].GetAncestor(indexes[i].nHeight - 16); BOOST_CHECK(ancestor != nullptr); BOOST_CHECK(ancestor->nHeight == (indexes[i].nHeight - 16)); } } } /* * Reorder these indexes to setup multiple branches: * * (248)->(...)->(255) * / * (128)->(...)->(191)->(...)->(247) * / * (0)->(...)->(63)->(...)->(127) */ for (size_t i = 0; i < indexes.size(); i++) { /* Build the tree */ indexes[i].pskip = nullptr; if (i > 0) { indexes[i].pprev = &indexes[i - 1]; } if (i < 128) { indexes[i].nHeight = i; } else if (i < 248) { /* Branch at 128 */ if (i == 128) { indexes[i].pprev = &indexes[63]; } indexes[i].nHeight = i - 64; } else { /* Branch at 248 */ if (i == 248) { indexes[i].pprev = &indexes[191]; } indexes[i].nHeight = i - 128 + 8; } /* Build and test skip pointer */ if (i > 0) { indexes[i].BuildSkip(); /* Check that skip is built */ BOOST_CHECK(indexes[i].pskip != nullptr); /* * Starting from height 2, pskip should be more efficient that * pprev. * Ensure pskip.nHeight < pprev.nHeight */ if (i > 1) { BOOST_CHECK(indexes[i].pskip->nHeight < indexes[i].pprev->nHeight); } } /* Find an ancestor 37 indexes behind */ if (i > 37) { CBlockIndex *ancestor = indexes[i].GetAncestor(indexes[i].nHeight - 37); BOOST_CHECK(ancestor != nullptr); BOOST_CHECK(ancestor->nHeight == (indexes[i].nHeight - 37)); } } } BOOST_AUTO_TEST_SUITE_END()