Branch data Line data Source code
# 1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto
# 2 : : // Copyright (c) 2009-2020 The Bitcoin Core developers
# 3 : : // Distributed under the MIT software license, see the accompanying
# 4 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
# 5 : :
# 6 : : #ifndef BITCOIN_CHAIN_H
# 7 : : #define BITCOIN_CHAIN_H
# 8 : :
# 9 : : #include <arith_uint256.h>
# 10 : : #include <consensus/params.h>
# 11 : : #include <flatfile.h>
# 12 : : #include <primitives/block.h>
# 13 : : #include <tinyformat.h>
# 14 : : #include <uint256.h>
# 15 : :
# 16 : : #include <vector>
# 17 : :
# 18 : : /**
# 19 : : * Maximum amount of time that a block timestamp is allowed to exceed the
# 20 : : * current network-adjusted time before the block will be accepted.
# 21 : : */
# 22 : : static constexpr int64_t MAX_FUTURE_BLOCK_TIME = 2 * 60 * 60;
# 23 : :
# 24 : : /**
# 25 : : * Timestamp window used as a grace period by code that compares external
# 26 : : * timestamps (such as timestamps passed to RPCs, or wallet key creation times)
# 27 : : * to block timestamps. This should be set at least as high as
# 28 : : * MAX_FUTURE_BLOCK_TIME.
# 29 : : */
# 30 : : static constexpr int64_t TIMESTAMP_WINDOW = MAX_FUTURE_BLOCK_TIME;
# 31 : :
# 32 : : /**
# 33 : : * Maximum gap between node time and block time used
# 34 : : * for the "Catching up..." mode in GUI.
# 35 : : *
# 36 : : * Ref: https://github.com/bitcoin/bitcoin/pull/1026
# 37 : : */
# 38 : : static constexpr int64_t MAX_BLOCK_TIME_GAP = 90 * 60;
# 39 : :
# 40 : : class CBlockFileInfo
# 41 : : {
# 42 : : public:
# 43 : : unsigned int nBlocks; //!< number of blocks stored in file
# 44 : : unsigned int nSize; //!< number of used bytes of block file
# 45 : : unsigned int nUndoSize; //!< number of used bytes in the undo file
# 46 : : unsigned int nHeightFirst; //!< lowest height of block in file
# 47 : : unsigned int nHeightLast; //!< highest height of block in file
# 48 : : uint64_t nTimeFirst; //!< earliest time of block in file
# 49 : : uint64_t nTimeLast; //!< latest time of block in file
# 50 : :
# 51 : : SERIALIZE_METHODS(CBlockFileInfo, obj)
# 52 : 871 : {
# 53 : 871 : READWRITE(VARINT(obj.nBlocks));
# 54 : 871 : READWRITE(VARINT(obj.nSize));
# 55 : 871 : READWRITE(VARINT(obj.nUndoSize));
# 56 : 871 : READWRITE(VARINT(obj.nHeightFirst));
# 57 : 871 : READWRITE(VARINT(obj.nHeightLast));
# 58 : 871 : READWRITE(VARINT(obj.nTimeFirst));
# 59 : 871 : READWRITE(VARINT(obj.nTimeLast));
# 60 : 871 : }
# 61 : :
# 62 : 1430 : void SetNull() {
# 63 : 1430 : nBlocks = 0;
# 64 : 1430 : nSize = 0;
# 65 : 1430 : nUndoSize = 0;
# 66 : 1430 : nHeightFirst = 0;
# 67 : 1430 : nHeightLast = 0;
# 68 : 1430 : nTimeFirst = 0;
# 69 : 1430 : nTimeLast = 0;
# 70 : 1430 : }
# 71 : :
# 72 : 1423 : CBlockFileInfo() {
# 73 : 1423 : SetNull();
# 74 : 1423 : }
# 75 : :
# 76 : : std::string ToString() const;
# 77 : :
# 78 : : /** update statistics (does not update nSize) */
# 79 : 69448 : void AddBlock(unsigned int nHeightIn, uint64_t nTimeIn) {
# 80 [ + + ][ + + ]: 69448 : if (nBlocks==0 || nHeightFirst > nHeightIn)
# 81 : 420 : nHeightFirst = nHeightIn;
# 82 [ + + ][ + + ]: 69448 : if (nBlocks==0 || nTimeFirst > nTimeIn)
# 83 : 420 : nTimeFirst = nTimeIn;
# 84 : 69448 : nBlocks++;
# 85 [ + + ]: 69448 : if (nHeightIn > nHeightLast)
# 86 : 62919 : nHeightLast = nHeightIn;
# 87 [ + + ]: 69448 : if (nTimeIn > nTimeLast)
# 88 : 22889 : nTimeLast = nTimeIn;
# 89 : 69448 : }
# 90 : : };
# 91 : :
# 92 : : enum BlockStatus: uint32_t {
# 93 : : //! Unused.
# 94 : : BLOCK_VALID_UNKNOWN = 0,
# 95 : :
# 96 : : //! Reserved (was BLOCK_VALID_HEADER).
# 97 : : BLOCK_VALID_RESERVED = 1,
# 98 : :
# 99 : : //! All parent headers found, difficulty matches, timestamp >= median previous, checkpoint. Implies all parents
# 100 : : //! are also at least TREE.
# 101 : : BLOCK_VALID_TREE = 2,
# 102 : :
# 103 : : /**
# 104 : : * Only first tx is coinbase, 2 <= coinbase input script length <= 100, transactions valid, no duplicate txids,
# 105 : : * sigops, size, merkle root. Implies all parents are at least TREE but not necessarily TRANSACTIONS. When all
# 106 : : * parent blocks also have TRANSACTIONS, CBlockIndex::nChainTx will be set.
# 107 : : */
# 108 : : BLOCK_VALID_TRANSACTIONS = 3,
# 109 : :
# 110 : : //! Outputs do not overspend inputs, no double spends, coinbase output ok, no immature coinbase spends, BIP30.
# 111 : : //! Implies all parents are also at least CHAIN.
# 112 : : BLOCK_VALID_CHAIN = 4,
# 113 : :
# 114 : : //! Scripts & signatures ok. Implies all parents are also at least SCRIPTS.
# 115 : : BLOCK_VALID_SCRIPTS = 5,
# 116 : :
# 117 : : //! All validity bits.
# 118 : : BLOCK_VALID_MASK = BLOCK_VALID_RESERVED | BLOCK_VALID_TREE | BLOCK_VALID_TRANSACTIONS |
# 119 : : BLOCK_VALID_CHAIN | BLOCK_VALID_SCRIPTS,
# 120 : :
# 121 : : BLOCK_HAVE_DATA = 8, //!< full block available in blk*.dat
# 122 : : BLOCK_HAVE_UNDO = 16, //!< undo data available in rev*.dat
# 123 : : BLOCK_HAVE_MASK = BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO,
# 124 : :
# 125 : : BLOCK_FAILED_VALID = 32, //!< stage after last reached validness failed
# 126 : : BLOCK_FAILED_CHILD = 64, //!< descends from failed block
# 127 : : BLOCK_FAILED_MASK = BLOCK_FAILED_VALID | BLOCK_FAILED_CHILD,
# 128 : :
# 129 : : BLOCK_OPT_WITNESS = 128, //!< block data in blk*.data was received with a witness-enforcing client
# 130 : : };
# 131 : :
# 132 : : /** The block chain is a tree shaped structure starting with the
# 133 : : * genesis block at the root, with each block potentially having multiple
# 134 : : * candidates to be the next block. A blockindex may have multiple pprev pointing
# 135 : : * to it, but at most one of them can be part of the currently active branch.
# 136 : : */
# 137 : : class CBlockIndex
# 138 : : {
# 139 : : public:
# 140 : : //! pointer to the hash of the block, if any. Memory is owned by this CBlockIndex
# 141 : : const uint256* phashBlock{nullptr};
# 142 : :
# 143 : : //! pointer to the index of the predecessor of this block
# 144 : : CBlockIndex* pprev{nullptr};
# 145 : :
# 146 : : //! pointer to the index of some further predecessor of this block
# 147 : : CBlockIndex* pskip{nullptr};
# 148 : :
# 149 : : //! height of the entry in the chain. The genesis block has height 0
# 150 : : int nHeight{0};
# 151 : :
# 152 : : //! Which # file this block is stored in (blk?????.dat)
# 153 : : int nFile{0};
# 154 : :
# 155 : : //! Byte offset within blk?????.dat where this block's data is stored
# 156 : : unsigned int nDataPos{0};
# 157 : :
# 158 : : //! Byte offset within rev?????.dat where this block's undo data is stored
# 159 : : unsigned int nUndoPos{0};
# 160 : :
# 161 : : //! (memory only) Total amount of work (expected number of hashes) in the chain up to and including this block
# 162 : : arith_uint256 nChainWork{};
# 163 : :
# 164 : : //! Number of transactions in this block.
# 165 : : //! Note: in a potential headers-first mode, this number cannot be relied upon
# 166 : : //! Note: this value is faked during UTXO snapshot load to ensure that
# 167 : : //! LoadBlockIndex() will load index entries for blocks that we lack data for.
# 168 : : //! @sa ActivateSnapshot
# 169 : : unsigned int nTx{0};
# 170 : :
# 171 : : //! (memory only) Number of transactions in the chain up to and including this block.
# 172 : : //! This value will be non-zero only if and only if transactions for this block and all its parents are available.
# 173 : : //! Change to 64-bit type when necessary; won't happen before 2030
# 174 : : //!
# 175 : : //! Note: this value is faked during use of a UTXO snapshot because we don't
# 176 : : //! have the underlying block data available during snapshot load.
# 177 : : //! @sa AssumeutxoData
# 178 : : //! @sa ActivateSnapshot
# 179 : : unsigned int nChainTx{0};
# 180 : :
# 181 : : //! Verification status of this block. See enum BlockStatus
# 182 : : //!
# 183 : : //! Note: this value is modified to show BLOCK_OPT_WITNESS during UTXO snapshot
# 184 : : //! load to avoid the block index being spuriously rewound.
# 185 : : //! @sa RewindBlockIndex
# 186 : : //! @sa ActivateSnapshot
# 187 : : uint32_t nStatus{0};
# 188 : :
# 189 : : //! block header
# 190 : : int32_t nVersion{0};
# 191 : : uint256 hashMerkleRoot{};
# 192 : : uint32_t nTime{0};
# 193 : : uint32_t nBits{0};
# 194 : : uint32_t nNonce{0};
# 195 : :
# 196 : : //! (memory only) Sequential id assigned to distinguish order in which blocks are received.
# 197 : : int32_t nSequenceId{0};
# 198 : :
# 199 : : //! (memory only) Maximum nTime in the chain up to and including this block.
# 200 : : unsigned int nTimeMax{0};
# 201 : :
# 202 : : CBlockIndex()
# 203 : 7958684 : {
# 204 : 7958684 : }
# 205 : :
# 206 : : explicit CBlockIndex(const CBlockHeader& block)
# 207 : : : nVersion{block.nVersion},
# 208 : : hashMerkleRoot{block.hashMerkleRoot},
# 209 : : nTime{block.nTime},
# 210 : : nBits{block.nBits},
# 211 : : nNonce{block.nNonce}
# 212 : 102289 : {
# 213 : 102289 : }
# 214 : :
# 215 : 119317 : FlatFilePos GetBlockPos() const {
# 216 : 119317 : FlatFilePos ret;
# 217 [ + + ]: 119317 : if (nStatus & BLOCK_HAVE_DATA) {
# 218 : 119206 : ret.nFile = nFile;
# 219 : 119206 : ret.nPos = nDataPos;
# 220 : 119206 : }
# 221 : 119317 : return ret;
# 222 : 119317 : }
# 223 : :
# 224 : 86516 : FlatFilePos GetUndoPos() const {
# 225 : 86516 : FlatFilePos ret;
# 226 [ + + ]: 86516 : if (nStatus & BLOCK_HAVE_UNDO) {
# 227 : 20298 : ret.nFile = nFile;
# 228 : 20298 : ret.nPos = nUndoPos;
# 229 : 20298 : }
# 230 : 86516 : return ret;
# 231 : 86516 : }
# 232 : :
# 233 : : CBlockHeader GetBlockHeader() const
# 234 : 18789 : {
# 235 : 18789 : CBlockHeader block;
# 236 : 18789 : block.nVersion = nVersion;
# 237 [ + - ]: 18789 : if (pprev)
# 238 : 18789 : block.hashPrevBlock = pprev->GetBlockHash();
# 239 : 18789 : block.hashMerkleRoot = hashMerkleRoot;
# 240 : 18789 : block.nTime = nTime;
# 241 : 18789 : block.nBits = nBits;
# 242 : 18789 : block.nNonce = nNonce;
# 243 : 18789 : return block;
# 244 : 18789 : }
# 245 : :
# 246 : : uint256 GetBlockHash() const
# 247 : 3355681 : {
# 248 : 3355681 : return *phashBlock;
# 249 : 3355681 : }
# 250 : :
# 251 : : /**
# 252 : : * Check whether this block's and all previous blocks' transactions have been
# 253 : : * downloaded (and stored to disk) at some point.
# 254 : : *
# 255 : : * Does not imply the transactions are consensus-valid (ConnectTip might fail)
# 256 : : * Does not imply the transactions are still stored on disk. (IsBlockPruned might return true)
# 257 : : */
# 258 : 439802616 : bool HaveTxsDownloaded() const { return nChainTx != 0; }
# 259 : :
# 260 : : int64_t GetBlockTime() const
# 261 : 7078354 : {
# 262 : 7078354 : return (int64_t)nTime;
# 263 : 7078354 : }
# 264 : :
# 265 : : int64_t GetBlockTimeMax() const
# 266 : 333125 : {
# 267 : 333125 : return (int64_t)nTimeMax;
# 268 : 333125 : }
# 269 : :
# 270 : : static constexpr int nMedianTimeSpan = 11;
# 271 : :
# 272 : : int64_t GetMedianTimePast() const
# 273 : 598864 : {
# 274 : 598864 : int64_t pmedian[nMedianTimeSpan];
# 275 : 598864 : int64_t* pbegin = &pmedian[nMedianTimeSpan];
# 276 : 598864 : int64_t* pend = &pmedian[nMedianTimeSpan];
# 277 : :
# 278 : 598864 : const CBlockIndex* pindex = this;
# 279 [ + + ][ + + ]: 7146344 : for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev)
# 280 : 6547480 : *(--pbegin) = pindex->GetBlockTime();
# 281 : :
# 282 : 598864 : std::sort(pbegin, pend);
# 283 : 598864 : return pbegin[(pend - pbegin)/2];
# 284 : 598864 : }
# 285 : :
# 286 : : std::string ToString() const
# 287 : 0 : {
# 288 : 0 : return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
# 289 : 0 : pprev, nHeight,
# 290 : 0 : hashMerkleRoot.ToString(),
# 291 : 0 : GetBlockHash().ToString());
# 292 : 0 : }
# 293 : :
# 294 : : //! Check whether this block index entry is valid up to the passed validity level.
# 295 : : bool IsValid(enum BlockStatus nUpTo = BLOCK_VALID_TRANSACTIONS) const
# 296 : 597395 : {
# 297 : 597395 : assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
# 298 [ + + ]: 597395 : if (nStatus & BLOCK_FAILED_MASK)
# 299 : 2136 : return false;
# 300 : 595259 : return ((nStatus & BLOCK_VALID_MASK) >= nUpTo);
# 301 : 595259 : }
# 302 : :
# 303 : : //! Raise the validity level of this block index entry.
# 304 : : //! Returns true if the validity was changed.
# 305 : : bool RaiseValidity(enum BlockStatus nUpTo)
# 306 : 207975 : {
# 307 : 207975 : assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
# 308 [ - + ]: 207975 : if (nStatus & BLOCK_FAILED_MASK)
# 309 : 0 : return false;
# 310 [ + - ]: 207975 : if ((nStatus & BLOCK_VALID_MASK) < nUpTo) {
# 311 : 207975 : nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo;
# 312 : 207975 : return true;
# 313 : 207975 : }
# 314 : 0 : return false;
# 315 : 0 : }
# 316 : :
# 317 : : //! Build the skiplist pointer for this entry.
# 318 : : void BuildSkip();
# 319 : :
# 320 : : //! Efficiently find an ancestor of this block.
# 321 : : CBlockIndex* GetAncestor(int height);
# 322 : : const CBlockIndex* GetAncestor(int height) const;
# 323 : : };
# 324 : :
# 325 : : arith_uint256 GetBlockProof(const CBlockIndex& block);
# 326 : : /** 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. */
# 327 : : int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params&);
# 328 : : /** Find the forking point between two chain tips. */
# 329 : : const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb);
# 330 : :
# 331 : :
# 332 : : /** Used to marshal pointers into hashes for db storage. */
# 333 : : class CDiskBlockIndex : public CBlockIndex
# 334 : : {
# 335 : : public:
# 336 : : uint256 hashPrev;
# 337 : :
# 338 : 62360 : CDiskBlockIndex() {
# 339 : 62360 : hashPrev = uint256();
# 340 : 62360 : }
# 341 : :
# 342 : 68391 : explicit CDiskBlockIndex(const CBlockIndex* pindex) : CBlockIndex(*pindex) {
# 343 [ + + ]: 68391 : hashPrev = (pprev ? pprev->GetBlockHash() : uint256());
# 344 : 68391 : }
# 345 : :
# 346 : : SERIALIZE_METHODS(CDiskBlockIndex, obj)
# 347 : 130751 : {
# 348 : 130751 : int _nVersion = s.GetVersion();
# 349 [ + - ][ + - ]: 130751 : if (!(s.GetType() & SER_GETHASH)) READWRITE(VARINT_MODE(_nVersion, VarIntMode::NONNEGATIVE_SIGNED));
# 350 : :
# 351 : 130751 : READWRITE(VARINT_MODE(obj.nHeight, VarIntMode::NONNEGATIVE_SIGNED));
# 352 : 130751 : READWRITE(VARINT(obj.nStatus));
# 353 : 130751 : READWRITE(VARINT(obj.nTx));
# 354 [ + + ][ + + ]: 130751 : if (obj.nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO)) READWRITE(VARINT_MODE(obj.nFile, VarIntMode::NONNEGATIVE_SIGNED));
# 355 [ + + ][ + + ]: 130751 : if (obj.nStatus & BLOCK_HAVE_DATA) READWRITE(VARINT(obj.nDataPos));
# 356 [ + + ][ + + ]: 130751 : if (obj.nStatus & BLOCK_HAVE_UNDO) READWRITE(VARINT(obj.nUndoPos));
# 357 : :
# 358 : : // block header
# 359 : 130751 : READWRITE(obj.nVersion);
# 360 : 130751 : READWRITE(obj.hashPrev);
# 361 : 130751 : READWRITE(obj.hashMerkleRoot);
# 362 : 130751 : READWRITE(obj.nTime);
# 363 : 130751 : READWRITE(obj.nBits);
# 364 : 130751 : READWRITE(obj.nNonce);
# 365 : 130751 : }
# 366 : :
# 367 : : uint256 GetBlockHash() const
# 368 : 62360 : {
# 369 : 62360 : CBlockHeader block;
# 370 : 62360 : block.nVersion = nVersion;
# 371 : 62360 : block.hashPrevBlock = hashPrev;
# 372 : 62360 : block.hashMerkleRoot = hashMerkleRoot;
# 373 : 62360 : block.nTime = nTime;
# 374 : 62360 : block.nBits = nBits;
# 375 : 62360 : block.nNonce = nNonce;
# 376 : 62360 : return block.GetHash();
# 377 : 62360 : }
# 378 : :
# 379 : :
# 380 : : std::string ToString() const
# 381 : 0 : {
# 382 : 0 : std::string str = "CDiskBlockIndex(";
# 383 : 0 : str += CBlockIndex::ToString();
# 384 : 0 : str += strprintf("\n hashBlock=%s, hashPrev=%s)",
# 385 : 0 : GetBlockHash().ToString(),
# 386 : 0 : hashPrev.ToString());
# 387 : 0 : return str;
# 388 : 0 : }
# 389 : : };
# 390 : :
# 391 : : /** An in-memory indexed chain of blocks. */
# 392 : : class CChain {
# 393 : : private:
# 394 : : std::vector<CBlockIndex*> vChain;
# 395 : :
# 396 : : public:
# 397 : : /** Returns the index entry for the genesis block of this chain, or nullptr if none. */
# 398 : 256716 : CBlockIndex *Genesis() const {
# 399 [ + + ]: 256716 : return vChain.size() > 0 ? vChain[0] : nullptr;
# 400 : 256716 : }
# 401 : :
# 402 : : /** Returns the index entry for the tip of this chain, or nullptr if none. */
# 403 : 158051853 : CBlockIndex *Tip() const {
# 404 [ + + ]: 158051853 : return vChain.size() > 0 ? vChain[vChain.size() - 1] : nullptr;
# 405 : 158051853 : }
# 406 : :
# 407 : : /** Returns the index entry at a particular height in this chain, or nullptr if no such height exists. */
# 408 : 1166439 : CBlockIndex *operator[](int nHeight) const {
# 409 [ - + ][ + + ]: 1166439 : if (nHeight < 0 || nHeight >= (int)vChain.size())
# 410 : 347470 : return nullptr;
# 411 : 818969 : return vChain[nHeight];
# 412 : 818969 : }
# 413 : :
# 414 : : /** Efficiently check whether a block is present in this chain. */
# 415 : 709058 : bool Contains(const CBlockIndex *pindex) const {
# 416 : 709058 : return (*this)[pindex->nHeight] == pindex;
# 417 : 709058 : }
# 418 : :
# 419 : : /** Find the successor of a block in this chain, or nullptr if the given index is not found or is the tip. */
# 420 : 11119 : CBlockIndex *Next(const CBlockIndex *pindex) const {
# 421 [ + - ]: 11119 : if (Contains(pindex))
# 422 : 11119 : return (*this)[pindex->nHeight + 1];
# 423 : 0 : else
# 424 : 0 : return nullptr;
# 425 : 11119 : }
# 426 : :
# 427 : : /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->nHeight : -1. */
# 428 : 710384 : int Height() const {
# 429 : 710384 : return vChain.size() - 1;
# 430 : 710384 : }
# 431 : :
# 432 : : /** Set/initialize a chain with a given tip. */
# 433 : : void SetTip(CBlockIndex *pindex);
# 434 : :
# 435 : : /** Return a CBlockLocator that refers to a block in this chain (by default the tip). */
# 436 : : CBlockLocator GetLocator(const CBlockIndex *pindex = nullptr) const;
# 437 : :
# 438 : : /** Find the last common block between this chain and a block index entry. */
# 439 : : const CBlockIndex *FindFork(const CBlockIndex *pindex) const;
# 440 : :
# 441 : : /** Find the earliest block with timestamp equal or greater than the given time and height equal or greater than the given height. */
# 442 : : CBlockIndex* FindEarliestAtLeast(int64_t nTime, int height) const;
# 443 : : };
# 444 : :
# 445 : : #endif // BITCOIN_CHAIN_H
|
