chain.h
1 // Copyright (c) 2009-2010 Satoshi Nakamoto 2 // Copyright (c) 2009-2022 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 <kernel/cs_main.h> 13 #include <primitives/block.h> 14 #include <serialize.h> 15 #include <sync.h> 16 #include <uint256.h> 17 #include <util/time.h> 18 19 #include <algorithm> 20 #include <cassert> 21 #include <cstdint> 22 #include <string> 23 #include <vector> 24 25 /** 26 * Maximum amount of time that a block timestamp is allowed to exceed the 27 * current time before the block will be accepted. 28 */ 29 static constexpr int64_t MAX_FUTURE_BLOCK_TIME = 2 * 60 * 60; 30 31 /** 32 * Timestamp window used as a grace period by code that compares external 33 * timestamps (such as timestamps passed to RPCs, or wallet key creation times) 34 * to block timestamps. This should be set at least as high as 35 * MAX_FUTURE_BLOCK_TIME. 36 */ 37 static constexpr int64_t TIMESTAMP_WINDOW = MAX_FUTURE_BLOCK_TIME; 38 39 /** 40 * Maximum gap between node time and block time used 41 * for the "Catching up..." mode in GUI. 42 * 43 * Ref: https://github.com/bitcoin/bitcoin/pull/1026 44 */ 45 static constexpr int64_t MAX_BLOCK_TIME_GAP = 90 * 60; 46 47 class CBlockFileInfo 48 { 49 public: 50 unsigned int nBlocks{}; //!< number of blocks stored in file 51 unsigned int nSize{}; //!< number of used bytes of block file 52 unsigned int nUndoSize{}; //!< number of used bytes in the undo file 53 unsigned int nHeightFirst{}; //!< lowest height of block in file 54 unsigned int nHeightLast{}; //!< highest height of block in file 55 uint64_t nTimeFirst{}; //!< earliest time of block in file 56 uint64_t nTimeLast{}; //!< latest time of block in file 57 58 SERIALIZE_METHODS(CBlockFileInfo, obj) 59 { 60 READWRITE(VARINT(obj.nBlocks)); 61 READWRITE(VARINT(obj.nSize)); 62 READWRITE(VARINT(obj.nUndoSize)); 63 READWRITE(VARINT(obj.nHeightFirst)); 64 READWRITE(VARINT(obj.nHeightLast)); 65 READWRITE(VARINT(obj.nTimeFirst)); 66 READWRITE(VARINT(obj.nTimeLast)); 67 } 68 69 CBlockFileInfo() {} 70 71 std::string ToString() const; 72 73 /** update statistics (does not update nSize) */ 74 void AddBlock(unsigned int nHeightIn, uint64_t nTimeIn) 75 { 76 if (nBlocks == 0 || nHeightFirst > nHeightIn) 77 nHeightFirst = nHeightIn; 78 if (nBlocks == 0 || nTimeFirst > nTimeIn) 79 nTimeFirst = nTimeIn; 80 nBlocks++; 81 if (nHeightIn > nHeightLast) 82 nHeightLast = nHeightIn; 83 if (nTimeIn > nTimeLast) 84 nTimeLast = nTimeIn; 85 } 86 }; 87 88 enum BlockStatus : uint32_t { 89 //! Unused. 90 BLOCK_VALID_UNKNOWN = 0, 91 92 //! Reserved (was BLOCK_VALID_HEADER). 93 BLOCK_VALID_RESERVED = 1, 94 95 //! All parent headers found, difficulty matches, timestamp >= median previous, checkpoint. Implies all parents 96 //! are also at least TREE. 97 BLOCK_VALID_TREE = 2, 98 99 /** 100 * Only first tx is coinbase, 2 <= coinbase input script length <= 100, transactions valid, no duplicate txids, 101 * sigops, size, merkle root. Implies all parents are at least TREE but not necessarily TRANSACTIONS. 102 * 103 * If a block's validity is at least VALID_TRANSACTIONS, CBlockIndex::nTx will be set. If a block and all previous 104 * blocks back to the genesis block or an assumeutxo snapshot block are at least VALID_TRANSACTIONS, 105 * CBlockIndex::nChainTx will be set. 106 */ 107 BLOCK_VALID_TRANSACTIONS = 3, 108 109 //! Outputs do not overspend inputs, no double spends, coinbase output ok, no immature coinbase spends, BIP30. 110 //! Implies all previous blocks back to the genesis block or an assumeutxo snapshot block are at least VALID_CHAIN. 111 BLOCK_VALID_CHAIN = 4, 112 113 //! Scripts & signatures ok. Implies all previous blocks back to the genesis block or an assumeutxo snapshot block 114 //! are at least VALID_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*.dat was received with a witness-enforcing client 130 131 BLOCK_STATUS_RESERVED = 256, //!< Unused flag that was previously set on assumeutxo snapshot blocks and their 132 //!< ancestors before they were validated, and unset when they were validated. 133 }; 134 135 /** The block chain is a tree shaped structure starting with the 136 * genesis block at the root, with each block potentially having multiple 137 * candidates to be the next block. A blockindex may have multiple pprev pointing 138 * to it, but at most one of them can be part of the currently active branch. 139 */ 140 class CBlockIndex 141 { 142 public: 143 //! pointer to the hash of the block, if any. Memory is owned by this CBlockIndex 144 const uint256* phashBlock{nullptr}; 145 146 //! pointer to the index of the predecessor of this block 147 CBlockIndex* pprev{nullptr}; 148 149 //! pointer to the index of some further predecessor of this block 150 CBlockIndex* pskip{nullptr}; 151 152 //! height of the entry in the chain. The genesis block has height 0 153 int nHeight{0}; 154 155 //! Which # file this block is stored in (blk?????.dat) 156 int nFile GUARDED_BY(::cs_main){0}; 157 158 //! Byte offset within blk?????.dat where this block's data is stored 159 unsigned int nDataPos GUARDED_BY(::cs_main){0}; 160 161 //! Byte offset within rev?????.dat where this block's undo data is stored 162 unsigned int nUndoPos GUARDED_BY(::cs_main){0}; 163 164 //! (memory only) Total amount of work (expected number of hashes) in the chain up to and including this block 165 arith_uint256 nChainWork{}; 166 167 //! Number of transactions in this block. This will be nonzero if the block 168 //! reached the VALID_TRANSACTIONS level, and zero otherwise. 169 //! Note: in a potential headers-first mode, this number cannot be relied upon 170 unsigned int nTx{0}; 171 172 //! (memory only) Number of transactions in the chain up to and including this block. 173 //! This value will be non-zero if this block and all previous blocks back 174 //! to the genesis block or an assumeutxo snapshot block have reached the 175 //! VALID_TRANSACTIONS level. 176 //! Change to 64-bit type before 2024 (assuming worst case of 60 byte transactions). 177 unsigned int nChainTx{0}; 178 179 //! Verification status of this block. See enum BlockStatus 180 //! 181 //! Note: this value is modified to show BLOCK_OPT_WITNESS during UTXO snapshot 182 //! load to avoid the block index being spuriously rewound. 183 //! @sa NeedsRedownload 184 //! @sa ActivateSnapshot 185 uint32_t nStatus GUARDED_BY(::cs_main){0}; 186 187 //! block header 188 int32_t nVersion{0}; 189 uint256 hashMerkleRoot{}; 190 uint32_t nTime{0}; 191 uint32_t nBits{0}; 192 uint32_t nNonce{0}; 193 194 //! (memory only) Sequential id assigned to distinguish order in which blocks are received. 195 int32_t nSequenceId{0}; 196 197 //! (memory only) Maximum nTime in the chain up to and including this block. 198 unsigned int nTimeMax{0}; 199 200 explicit CBlockIndex(const CBlockHeader& block) 201 : nVersion{block.nVersion}, 202 hashMerkleRoot{block.hashMerkleRoot}, 203 nTime{block.nTime}, 204 nBits{block.nBits}, 205 nNonce{block.nNonce} 206 { 207 } 208 209 FlatFilePos GetBlockPos() const EXCLUSIVE_LOCKS_REQUIRED(::cs_main) 210 { 211 AssertLockHeld(::cs_main); 212 FlatFilePos ret; 213 if (nStatus & BLOCK_HAVE_DATA) { 214 ret.nFile = nFile; 215 ret.nPos = nDataPos; 216 } 217 return ret; 218 } 219 220 FlatFilePos GetUndoPos() const EXCLUSIVE_LOCKS_REQUIRED(::cs_main) 221 { 222 AssertLockHeld(::cs_main); 223 FlatFilePos ret; 224 if (nStatus & BLOCK_HAVE_UNDO) { 225 ret.nFile = nFile; 226 ret.nPos = nUndoPos; 227 } 228 return ret; 229 } 230 231 CBlockHeader GetBlockHeader() const 232 { 233 CBlockHeader block; 234 block.nVersion = nVersion; 235 if (pprev) 236 block.hashPrevBlock = pprev->GetBlockHash(); 237 block.hashMerkleRoot = hashMerkleRoot; 238 block.nTime = nTime; 239 block.nBits = nBits; 240 block.nNonce = nNonce; 241 return block; 242 } 243 244 uint256 GetBlockHash() const 245 { 246 assert(phashBlock != nullptr); 247 return *phashBlock; 248 } 249 250 /** 251 * Check whether this block and all previous blocks back to the genesis block or an assumeutxo snapshot block have 252 * reached VALID_TRANSACTIONS and had transactions downloaded (and stored to disk) at some point. 253 * 254 * Does not imply the transactions are consensus-valid (ConnectTip might fail) 255 * Does not imply the transactions are still stored on disk. (IsBlockPruned might return true) 256 * 257 * Note that this will be true for the snapshot base block, if one is loaded, since its nChainTx value will have 258 * been set manually based on the related AssumeutxoData entry. 259 */ 260 bool HaveNumChainTxs() const { return nChainTx != 0; } 261 262 NodeSeconds Time() const 263 { 264 return NodeSeconds{std::chrono::seconds{nTime}}; 265 } 266 267 int64_t GetBlockTime() const 268 { 269 return (int64_t)nTime; 270 } 271 272 int64_t GetBlockTimeMax() const 273 { 274 return (int64_t)nTimeMax; 275 } 276 277 static constexpr int nMedianTimeSpan = 11; 278 279 int64_t GetMedianTimePast() const 280 { 281 int64_t pmedian[nMedianTimeSpan]; 282 int64_t* pbegin = &pmedian[nMedianTimeSpan]; 283 int64_t* pend = &pmedian[nMedianTimeSpan]; 284 285 const CBlockIndex* pindex = this; 286 for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev) 287 *(--pbegin) = pindex->GetBlockTime(); 288 289 std::sort(pbegin, pend); 290 return pbegin[(pend - pbegin) / 2]; 291 } 292 293 std::string ToString() const; 294 295 //! Check whether this block index entry is valid up to the passed validity level. 296 bool IsValid(enum BlockStatus nUpTo = BLOCK_VALID_TRANSACTIONS) const 297 EXCLUSIVE_LOCKS_REQUIRED(::cs_main) 298 { 299 AssertLockHeld(::cs_main); 300 assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed. 301 if (nStatus & BLOCK_FAILED_MASK) 302 return false; 303 return ((nStatus & BLOCK_VALID_MASK) >= nUpTo); 304 } 305 306 //! Raise the validity level of this block index entry. 307 //! Returns true if the validity was changed. 308 bool RaiseValidity(enum BlockStatus nUpTo) EXCLUSIVE_LOCKS_REQUIRED(::cs_main) 309 { 310 AssertLockHeld(::cs_main); 311 assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed. 312 if (nStatus & BLOCK_FAILED_MASK) return false; 313 314 if ((nStatus & BLOCK_VALID_MASK) < nUpTo) { 315 nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo; 316 return true; 317 } 318 return false; 319 } 320 321 //! Build the skiplist pointer for this entry. 322 void BuildSkip(); 323 324 //! Efficiently find an ancestor of this block. 325 CBlockIndex* GetAncestor(int height); 326 const CBlockIndex* GetAncestor(int height) const; 327 328 CBlockIndex() = default; 329 ~CBlockIndex() = default; 330 331 protected: 332 //! CBlockIndex should not allow public copy construction because equality 333 //! comparison via pointer is very common throughout the codebase, making 334 //! use of copy a footgun. Also, use of copies do not have the benefit 335 //! of simplifying lifetime considerations due to attributes like pprev and 336 //! pskip, which are at risk of becoming dangling pointers in a copied 337 //! instance. 338 //! 339 //! We declare these protected instead of simply deleting them so that 340 //! CDiskBlockIndex can reuse copy construction. 341 CBlockIndex(const CBlockIndex&) = default; 342 CBlockIndex& operator=(const CBlockIndex&) = delete; 343 CBlockIndex(CBlockIndex&&) = delete; 344 CBlockIndex& operator=(CBlockIndex&&) = delete; 345 }; 346 347 arith_uint256 GetBlockProof(const CBlockIndex& block); 348 /** 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. */ 349 int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params&); 350 /** Find the forking point between two chain tips. */ 351 const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb); 352 353 354 /** Used to marshal pointers into hashes for db storage. */ 355 class CDiskBlockIndex : public CBlockIndex 356 { 357 /** Historically CBlockLocator's version field has been written to disk 358 * streams as the client version, but the value has never been used. 359 * 360 * Hard-code to the highest client version ever written. 361 * SerParams can be used if the field requires any meaning in the future. 362 **/ 363 static constexpr int DUMMY_VERSION = 259900; 364 365 public: 366 uint256 hashPrev; 367 368 CDiskBlockIndex() 369 { 370 hashPrev = uint256(); 371 } 372 373 explicit CDiskBlockIndex(const CBlockIndex* pindex) : CBlockIndex(*pindex) 374 { 375 hashPrev = (pprev ? pprev->GetBlockHash() : uint256()); 376 } 377 378 SERIALIZE_METHODS(CDiskBlockIndex, obj) 379 { 380 LOCK(::cs_main); 381 int _nVersion = DUMMY_VERSION; 382 READWRITE(VARINT_MODE(_nVersion, VarIntMode::NONNEGATIVE_SIGNED)); 383 384 READWRITE(VARINT_MODE(obj.nHeight, VarIntMode::NONNEGATIVE_SIGNED)); 385 READWRITE(VARINT(obj.nStatus)); 386 READWRITE(VARINT(obj.nTx)); 387 if (obj.nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO)) READWRITE(VARINT_MODE(obj.nFile, VarIntMode::NONNEGATIVE_SIGNED)); 388 if (obj.nStatus & BLOCK_HAVE_DATA) READWRITE(VARINT(obj.nDataPos)); 389 if (obj.nStatus & BLOCK_HAVE_UNDO) READWRITE(VARINT(obj.nUndoPos)); 390 391 // block header 392 READWRITE(obj.nVersion); 393 READWRITE(obj.hashPrev); 394 READWRITE(obj.hashMerkleRoot); 395 READWRITE(obj.nTime); 396 READWRITE(obj.nBits); 397 READWRITE(obj.nNonce); 398 } 399 400 uint256 ConstructBlockHash() const 401 { 402 CBlockHeader block; 403 block.nVersion = nVersion; 404 block.hashPrevBlock = hashPrev; 405 block.hashMerkleRoot = hashMerkleRoot; 406 block.nTime = nTime; 407 block.nBits = nBits; 408 block.nNonce = nNonce; 409 return block.GetHash(); 410 } 411 412 uint256 GetBlockHash() = delete; 413 std::string ToString() = delete; 414 }; 415 416 /** An in-memory indexed chain of blocks. */ 417 class CChain 418 { 419 private: 420 std::vector<CBlockIndex*> vChain; 421 422 public: 423 CChain() = default; 424 CChain(const CChain&) = delete; 425 CChain& operator=(const CChain&) = delete; 426 427 /** Returns the index entry for the genesis block of this chain, or nullptr if none. */ 428 CBlockIndex* Genesis() const 429 { 430 return vChain.size() > 0 ? vChain[0] : nullptr; 431 } 432 433 /** Returns the index entry for the tip of this chain, or nullptr if none. */ 434 CBlockIndex* Tip() const 435 { 436 return vChain.size() > 0 ? vChain[vChain.size() - 1] : nullptr; 437 } 438 439 /** Returns the index entry at a particular height in this chain, or nullptr if no such height exists. */ 440 CBlockIndex* operator[](int nHeight) const 441 { 442 if (nHeight < 0 || nHeight >= (int)vChain.size()) 443 return nullptr; 444 return vChain[nHeight]; 445 } 446 447 /** Efficiently check whether a block is present in this chain. */ 448 bool Contains(const CBlockIndex* pindex) const 449 { 450 return (*this)[pindex->nHeight] == pindex; 451 } 452 453 /** Find the successor of a block in this chain, or nullptr if the given index is not found or is the tip. */ 454 CBlockIndex* Next(const CBlockIndex* pindex) const 455 { 456 if (Contains(pindex)) 457 return (*this)[pindex->nHeight + 1]; 458 else 459 return nullptr; 460 } 461 462 /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->nHeight : -1. */ 463 int Height() const 464 { 465 return int(vChain.size()) - 1; 466 } 467 468 /** Set/initialize a chain with a given tip. */ 469 void SetTip(CBlockIndex& block); 470 471 /** Return a CBlockLocator that refers to the tip in of this chain. */ 472 CBlockLocator GetLocator() const; 473 474 /** Find the last common block between this chain and a block index entry. */ 475 const CBlockIndex* FindFork(const CBlockIndex* pindex) const; 476 477 /** Find the earliest block with timestamp equal or greater than the given time and height equal or greater than the given height. */ 478 CBlockIndex* FindEarliestAtLeast(int64_t nTime, int height) const; 479 }; 480 481 /** Get a locator for a block index entry. */ 482 CBlockLocator GetLocator(const CBlockIndex* index); 483 484 /** Construct a list of hash entries to put in a locator. */ 485 std::vector<uint256> LocatorEntries(const CBlockIndex* index); 486 487 #endif // BITCOIN_CHAIN_H