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