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() = default; 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. 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::m_chain_tx_count 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 uint64_t m_chain_tx_count{0}; 177 178 //! Verification status of this block. See enum BlockStatus 179 //! 180 //! Note: this value is modified to show BLOCK_OPT_WITNESS during UTXO snapshot 181 //! load to avoid a spurious startup failure requiring -reindex. 182 //! @sa NeedsRedownload 183 //! @sa ActivateSnapshot 184 uint32_t nStatus GUARDED_BY(::cs_main){0}; 185 186 //! block header 187 int32_t nVersion{0}; 188 uint256 hashMerkleRoot{}; 189 uint32_t nTime{0}; 190 uint32_t nBits{0}; 191 uint32_t nNonce{0}; 192 193 //! (memory only) Sequential id assigned to distinguish order in which blocks are received. 194 int32_t nSequenceId{0}; 195 196 //! (memory only) Maximum nTime in the chain up to and including this block. 197 unsigned int nTimeMax{0}; 198 199 explicit CBlockIndex(const CBlockHeader& block) 200 : nVersion{block.nVersion}, 201 hashMerkleRoot{block.hashMerkleRoot}, 202 nTime{block.nTime}, 203 nBits{block.nBits}, 204 nNonce{block.nNonce} 205 { 206 } 207 208 FlatFilePos GetBlockPos() const EXCLUSIVE_LOCKS_REQUIRED(::cs_main) 209 { 210 AssertLockHeld(::cs_main); 211 FlatFilePos ret; 212 if (nStatus & BLOCK_HAVE_DATA) { 213 ret.nFile = nFile; 214 ret.nPos = nDataPos; 215 } 216 return ret; 217 } 218 219 FlatFilePos GetUndoPos() const EXCLUSIVE_LOCKS_REQUIRED(::cs_main) 220 { 221 AssertLockHeld(::cs_main); 222 FlatFilePos ret; 223 if (nStatus & BLOCK_HAVE_UNDO) { 224 ret.nFile = nFile; 225 ret.nPos = nUndoPos; 226 } 227 return ret; 228 } 229 230 CBlockHeader GetBlockHeader() const 231 { 232 CBlockHeader block; 233 block.nVersion = nVersion; 234 if (pprev) 235 block.hashPrevBlock = pprev->GetBlockHash(); 236 block.hashMerkleRoot = hashMerkleRoot; 237 block.nTime = nTime; 238 block.nBits = nBits; 239 block.nNonce = nNonce; 240 return block; 241 } 242 243 uint256 GetBlockHash() const 244 { 245 assert(phashBlock != nullptr); 246 return *phashBlock; 247 } 248 249 /** 250 * Check whether this block and all previous blocks back to the genesis block or an assumeutxo snapshot block have 251 * reached VALID_TRANSACTIONS and had transactions downloaded (and stored to disk) at some point. 252 * 253 * Does not imply the transactions are consensus-valid (ConnectTip might fail) 254 * Does not imply the transactions are still stored on disk. (IsBlockPruned might return true) 255 * 256 * Note that this will be true for the snapshot base block, if one is loaded, since its m_chain_tx_count value will have 257 * been set manually based on the related AssumeutxoData entry. 258 */ 259 bool HaveNumChainTxs() const { return m_chain_tx_count != 0; } 260 261 NodeSeconds Time() const 262 { 263 return NodeSeconds{std::chrono::seconds{nTime}}; 264 } 265 266 int64_t GetBlockTime() const 267 { 268 return (int64_t)nTime; 269 } 270 271 int64_t GetBlockTimeMax() const 272 { 273 return (int64_t)nTimeMax; 274 } 275 276 static constexpr int nMedianTimeSpan = 11; 277 278 int64_t GetMedianTimePast() const 279 { 280 int64_t pmedian[nMedianTimeSpan]; 281 int64_t* pbegin = &pmedian[nMedianTimeSpan]; 282 int64_t* pend = &pmedian[nMedianTimeSpan]; 283 284 const CBlockIndex* pindex = this; 285 for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev) 286 *(--pbegin) = pindex->GetBlockTime(); 287 288 std::sort(pbegin, pend); 289 return pbegin[(pend - pbegin) / 2]; 290 } 291 292 std::string ToString() const; 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 EXCLUSIVE_LOCKS_REQUIRED(::cs_main) 297 { 298 AssertLockHeld(::cs_main); 299 assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed. 300 if (nStatus & BLOCK_FAILED_MASK) 301 return false; 302 return ((nStatus & BLOCK_VALID_MASK) >= nUpTo); 303 } 304 305 //! Raise the validity level of this block index entry. 306 //! Returns true if the validity was changed. 307 bool RaiseValidity(enum BlockStatus nUpTo) EXCLUSIVE_LOCKS_REQUIRED(::cs_main) 308 { 309 AssertLockHeld(::cs_main); 310 assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed. 311 if (nStatus & BLOCK_FAILED_MASK) return false; 312 313 if ((nStatus & BLOCK_VALID_MASK) < nUpTo) { 314 nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo; 315 return true; 316 } 317 return false; 318 } 319 320 //! Build the skiplist pointer for this entry. 321 void BuildSkip(); 322 323 //! Efficiently find an ancestor of this block. 324 CBlockIndex* GetAncestor(int height); 325 const CBlockIndex* GetAncestor(int height) const; 326 327 CBlockIndex() = default; 328 ~CBlockIndex() = default; 329 330 protected: 331 //! CBlockIndex should not allow public copy construction because equality 332 //! comparison via pointer is very common throughout the codebase, making 333 //! use of copy a footgun. Also, use of copies do not have the benefit 334 //! of simplifying lifetime considerations due to attributes like pprev and 335 //! pskip, which are at risk of becoming dangling pointers in a copied 336 //! instance. 337 //! 338 //! We declare these protected instead of simply deleting them so that 339 //! CDiskBlockIndex can reuse copy construction. 340 CBlockIndex(const CBlockIndex&) = default; 341 CBlockIndex& operator=(const CBlockIndex&) = delete; 342 CBlockIndex(CBlockIndex&&) = delete; 343 CBlockIndex& operator=(CBlockIndex&&) = delete; 344 }; 345 346 arith_uint256 GetBlockProof(const CBlockIndex& block); 347 /** 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. */ 348 int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params&); 349 /** Find the forking point between two chain tips. */ 350 const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb); 351 352 353 /** Used to marshal pointers into hashes for db storage. */ 354 class CDiskBlockIndex : public CBlockIndex 355 { 356 /** Historically CBlockLocator's version field has been written to disk 357 * streams as the client version, but the value has never been used. 358 * 359 * Hard-code to the highest client version ever written. 360 * SerParams can be used if the field requires any meaning in the future. 361 **/ 362 static constexpr int DUMMY_VERSION = 259900; 363 364 public: 365 uint256 hashPrev; 366 367 CDiskBlockIndex() 368 { 369 hashPrev = uint256(); 370 } 371 372 explicit CDiskBlockIndex(const CBlockIndex* pindex) : CBlockIndex(*pindex) 373 { 374 hashPrev = (pprev ? pprev->GetBlockHash() : uint256()); 375 } 376 377 SERIALIZE_METHODS(CDiskBlockIndex, obj) 378 { 379 LOCK(::cs_main); 380 int _nVersion = DUMMY_VERSION; 381 READWRITE(VARINT_MODE(_nVersion, VarIntMode::NONNEGATIVE_SIGNED)); 382 383 READWRITE(VARINT_MODE(obj.nHeight, VarIntMode::NONNEGATIVE_SIGNED)); 384 READWRITE(VARINT(obj.nStatus)); 385 READWRITE(VARINT(obj.nTx)); 386 if (obj.nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO)) READWRITE(VARINT_MODE(obj.nFile, VarIntMode::NONNEGATIVE_SIGNED)); 387 if (obj.nStatus & BLOCK_HAVE_DATA) READWRITE(VARINT(obj.nDataPos)); 388 if (obj.nStatus & BLOCK_HAVE_UNDO) READWRITE(VARINT(obj.nUndoPos)); 389 390 // block header 391 READWRITE(obj.nVersion); 392 READWRITE(obj.hashPrev); 393 READWRITE(obj.hashMerkleRoot); 394 READWRITE(obj.nTime); 395 READWRITE(obj.nBits); 396 READWRITE(obj.nNonce); 397 } 398 399 uint256 ConstructBlockHash() const 400 { 401 CBlockHeader block; 402 block.nVersion = nVersion; 403 block.hashPrevBlock = hashPrev; 404 block.hashMerkleRoot = hashMerkleRoot; 405 block.nTime = nTime; 406 block.nBits = nBits; 407 block.nNonce = nNonce; 408 return block.GetHash(); 409 } 410 411 uint256 GetBlockHash() = delete; 412 std::string ToString() = delete; 413 }; 414 415 /** An in-memory indexed chain of blocks. */ 416 class CChain 417 { 418 private: 419 std::vector<CBlockIndex*> vChain; 420 421 public: 422 CChain() = default; 423 CChain(const CChain&) = delete; 424 CChain& operator=(const CChain&) = delete; 425 426 /** Returns the index entry for the genesis block of this chain, or nullptr if none. */ 427 CBlockIndex* Genesis() const 428 { 429 return vChain.size() > 0 ? vChain[0] : nullptr; 430 } 431 432 /** Returns the index entry for the tip of this chain, or nullptr if none. */ 433 CBlockIndex* Tip() const 434 { 435 return vChain.size() > 0 ? vChain[vChain.size() - 1] : nullptr; 436 } 437 438 /** Returns the index entry at a particular height in this chain, or nullptr if no such height exists. */ 439 CBlockIndex* operator[](int nHeight) const 440 { 441 if (nHeight < 0 || nHeight >= (int)vChain.size()) 442 return nullptr; 443 return vChain[nHeight]; 444 } 445 446 /** Efficiently check whether a block is present in this chain. */ 447 bool Contains(const CBlockIndex* pindex) const 448 { 449 return (*this)[pindex->nHeight] == pindex; 450 } 451 452 /** Find the successor of a block in this chain, or nullptr if the given index is not found or is the tip. */ 453 CBlockIndex* Next(const CBlockIndex* pindex) const 454 { 455 if (Contains(pindex)) 456 return (*this)[pindex->nHeight + 1]; 457 else 458 return nullptr; 459 } 460 461 /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->nHeight : -1. */ 462 int Height() const 463 { 464 return int(vChain.size()) - 1; 465 } 466 467 /** Set/initialize a chain with a given tip. */ 468 void SetTip(CBlockIndex& block); 469 470 /** Return a CBlockLocator that refers to the tip in of this chain. */ 471 CBlockLocator GetLocator() const; 472 473 /** Find the last common block between this chain and a block index entry. */ 474 const CBlockIndex* FindFork(const CBlockIndex* pindex) const; 475 476 /** Find the earliest block with timestamp equal or greater than the given time and height equal or greater than the given height. */ 477 CBlockIndex* FindEarliestAtLeast(int64_t nTime, int height) const; 478 }; 479 480 /** Get a locator for a block index entry. */ 481 CBlockLocator GetLocator(const CBlockIndex* index); 482 483 /** Construct a list of hash entries to put in a locator. */ 484 std::vector<uint256> LocatorEntries(const CBlockIndex* index); 485 486 #endif // BITCOIN_CHAIN_H