1 // Copyright (c) 2009-2010 Satoshi Nakamoto 2 // Copyright (c) 2009-2019 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 SERIALIZE_METHODS(CBlockFileInfo,obj)51 SERIALIZE_METHODS(CBlockFileInfo, obj) 52 { 53 READWRITE(VARINT(obj.nBlocks)); 54 READWRITE(VARINT(obj.nSize)); 55 READWRITE(VARINT(obj.nUndoSize)); 56 READWRITE(VARINT(obj.nHeightFirst)); 57 READWRITE(VARINT(obj.nHeightLast)); 58 READWRITE(VARINT(obj.nTimeFirst)); 59 READWRITE(VARINT(obj.nTimeLast)); 60 } 61 SetNull()62 void SetNull() { 63 nBlocks = 0; 64 nSize = 0; 65 nUndoSize = 0; 66 nHeightFirst = 0; 67 nHeightLast = 0; 68 nTimeFirst = 0; 69 nTimeLast = 0; 70 } 71 CBlockFileInfo()72 CBlockFileInfo() { 73 SetNull(); 74 } 75 76 std::string ToString() const; 77 78 /** update statistics (does not update nSize) */ AddBlock(unsigned int nHeightIn,uint64_t nTimeIn)79 void AddBlock(unsigned int nHeightIn, uint64_t nTimeIn) { 80 if (nBlocks==0 || nHeightFirst > nHeightIn) 81 nHeightFirst = nHeightIn; 82 if (nBlocks==0 || nTimeFirst > nTimeIn) 83 nTimeFirst = nTimeIn; 84 nBlocks++; 85 if (nHeightIn > nHeightLast) 86 nHeightLast = nHeightIn; 87 if (nTimeIn > nTimeLast) 88 nTimeLast = nTimeIn; 89 } 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 the successor of this block 147 CBlockIndex* pnext{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{0}; 157 158 //! Byte offset within blk?????.dat where this block's data is stored 159 unsigned int nDataPos{0}; 160 161 //! Byte offset within rev?????.dat where this block's undo data is stored 162 unsigned int nUndoPos{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. 168 //! Note: in a potential headers-first mode, this number cannot be relied upon 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 unsigned int nChainTx{0}; 175 176 //! Verification status of this block. See enum BlockStatus 177 uint32_t nStatus{0}; 178 179 //! block header 180 int32_t nVersion{0}; 181 uint256 hashMerkleRoot{}; 182 uint32_t nTime{0}; 183 uint32_t nBits{0}; 184 uint32_t nNonce{0}; 185 uint256 hashStateRoot{}; // qtum 186 uint256 hashUTXORoot{}; // qtum 187 // block signature - proof-of-stake protect the block by signing the block using a stake holder private key 188 std::vector<unsigned char> vchBlockSigDlgt{}; 189 uint256 nStakeModifier{}; 190 // proof-of-stake specific fields 191 COutPoint prevoutStake{}; 192 uint256 hashProof{}; // qtum 193 uint64_t nMoneySupply{0}; 194 195 //! (memory only) Sequential id assigned to distinguish order in which blocks are received. 196 int32_t nSequenceId{0}; 197 198 //! (memory only) Maximum nTime in the chain up to and including this block. 199 unsigned int nTimeMax{0}; 200 CBlockIndex()201 CBlockIndex() 202 { 203 } 204 CBlockIndex(const CBlockHeader & block)205 explicit CBlockIndex(const CBlockHeader& block) 206 : nVersion{block.nVersion}, 207 hashMerkleRoot{block.hashMerkleRoot}, 208 nTime{block.nTime}, 209 nBits{block.nBits}, 210 nNonce{block.nNonce}, 211 hashStateRoot{block.hashStateRoot}, 212 hashUTXORoot{block.hashUTXORoot}, 213 vchBlockSigDlgt{block.vchBlockSigDlgt}, 214 prevoutStake{block.prevoutStake} 215 { 216 } 217 GetBlockPos()218 FlatFilePos GetBlockPos() const { 219 FlatFilePos ret; 220 if (nStatus & BLOCK_HAVE_DATA) { 221 ret.nFile = nFile; 222 ret.nPos = nDataPos; 223 } 224 return ret; 225 } 226 GetUndoPos()227 FlatFilePos GetUndoPos() const { 228 FlatFilePos ret; 229 if (nStatus & BLOCK_HAVE_UNDO) { 230 ret.nFile = nFile; 231 ret.nPos = nUndoPos; 232 } 233 return ret; 234 } 235 GetBlockHeader()236 CBlockHeader GetBlockHeader() const 237 { 238 CBlockHeader block; 239 block.nVersion = nVersion; 240 if (pprev) 241 block.hashPrevBlock = pprev->GetBlockHash(); 242 block.hashMerkleRoot = hashMerkleRoot; 243 block.nTime = nTime; 244 block.nBits = nBits; 245 block.nNonce = nNonce; 246 block.hashStateRoot = hashStateRoot; // qtum 247 block.hashUTXORoot = hashUTXORoot; // qtum 248 block.vchBlockSigDlgt = vchBlockSigDlgt; 249 block.prevoutStake = prevoutStake; 250 return block; 251 } 252 GetBlockHash()253 uint256 GetBlockHash() const 254 { 255 return *phashBlock; 256 } 257 258 /** 259 * Check whether this block's and all previous blocks' transactions have been 260 * downloaded (and stored to disk) at some point. 261 * 262 * Does not imply the transactions are consensus-valid (ConnectTip might fail) 263 * Does not imply the transactions are still stored on disk. (IsBlockPruned might return true) 264 */ HaveTxsDownloaded()265 bool HaveTxsDownloaded() const { return nChainTx != 0; } 266 GetBlockTime()267 int64_t GetBlockTime() const 268 { 269 return (int64_t)nTime; 270 } 271 GetBlockTimeMax()272 int64_t GetBlockTimeMax() const 273 { 274 return (int64_t)nTimeMax; 275 } 276 277 static constexpr int nMedianTimeSpan = 11; 278 GetMedianTimePast()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 IsProofOfWork()293 bool IsProofOfWork() const // qtum 294 { 295 return !IsProofOfStake(); 296 } 297 IsProofOfStake()298 bool IsProofOfStake() const 299 { 300 return !prevoutStake.IsNull(); 301 } 302 303 std::vector<unsigned char> GetBlockSignature() const; 304 305 std::vector<unsigned char> GetProofOfDelegation() const; 306 307 bool HasProofOfDelegation() const; 308 ToString()309 std::string ToString() const 310 { 311 return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)", 312 pprev, nHeight, 313 hashMerkleRoot.ToString(), 314 GetBlockHash().ToString()); 315 } 316 317 //! Check whether this block index entry is valid up to the passed validity level. 318 bool IsValid(enum BlockStatus nUpTo = BLOCK_VALID_TRANSACTIONS) const 319 { 320 assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed. 321 if (nStatus & BLOCK_FAILED_MASK) 322 return false; 323 return ((nStatus & BLOCK_VALID_MASK) >= nUpTo); 324 } 325 326 //! Raise the validity level of this block index entry. 327 //! Returns true if the validity was changed. RaiseValidity(enum BlockStatus nUpTo)328 bool RaiseValidity(enum BlockStatus nUpTo) 329 { 330 assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed. 331 if (nStatus & BLOCK_FAILED_MASK) 332 return false; 333 if ((nStatus & BLOCK_VALID_MASK) < nUpTo) { 334 nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo; 335 return true; 336 } 337 return false; 338 } 339 340 //! Build the skiplist pointer for this entry. 341 void BuildSkip(); 342 343 //! Efficiently find an ancestor of this block. 344 CBlockIndex* GetAncestor(int height); 345 const CBlockIndex* GetAncestor(int height) const; 346 }; 347 348 arith_uint256 GetBlockProof(const CBlockIndex& block); 349 /** 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. */ 350 int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params&); 351 /** Find the forking point between two chain tips. */ 352 const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb); 353 354 355 /** Used to marshal pointers into hashes for db storage. */ 356 class CDiskBlockIndex : public CBlockIndex 357 { 358 public: 359 uint256 hashPrev; 360 CDiskBlockIndex()361 CDiskBlockIndex() { 362 hashPrev = uint256(); 363 } 364 CDiskBlockIndex(const CBlockIndex * pindex)365 explicit CDiskBlockIndex(const CBlockIndex* pindex) : CBlockIndex(*pindex) { 366 hashPrev = (pprev ? pprev->GetBlockHash() : uint256()); 367 } 368 SERIALIZE_METHODS(CDiskBlockIndex,obj)369 SERIALIZE_METHODS(CDiskBlockIndex, obj) 370 { 371 int _nVersion = s.GetVersion(); 372 if (!(s.GetType() & SER_GETHASH)) READWRITE(VARINT_MODE(_nVersion, VarIntMode::NONNEGATIVE_SIGNED)); 373 374 READWRITE(VARINT_MODE(obj.nHeight, VarIntMode::NONNEGATIVE_SIGNED)); 375 READWRITE(VARINT(obj.nStatus)); 376 READWRITE(VARINT(obj.nTx)); 377 if (obj.nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO)) READWRITE(VARINT_MODE(obj.nFile, VarIntMode::NONNEGATIVE_SIGNED)); 378 if (obj.nStatus & BLOCK_HAVE_DATA) READWRITE(VARINT(obj.nDataPos)); 379 if (obj.nStatus & BLOCK_HAVE_UNDO) READWRITE(VARINT(obj.nUndoPos)); 380 READWRITE(VARINT(obj.nMoneySupply)); 381 382 // block header 383 READWRITE(obj.nVersion); 384 READWRITE(obj.hashPrev); 385 READWRITE(obj.hashMerkleRoot); 386 READWRITE(obj.nTime); 387 READWRITE(obj.nBits); 388 READWRITE(obj.nNonce); 389 READWRITE(obj.hashStateRoot); // qtum 390 READWRITE(obj.hashUTXORoot); // qtum 391 READWRITE(obj.nStakeModifier); 392 READWRITE(obj.prevoutStake); 393 READWRITE(obj.hashProof); 394 READWRITE(obj.vchBlockSigDlgt); // qtum 395 } 396 GetBlockHash()397 uint256 GetBlockHash() const 398 { 399 CBlockHeader block; 400 block.nVersion = nVersion; 401 block.hashPrevBlock = hashPrev; 402 block.hashMerkleRoot = hashMerkleRoot; 403 block.nTime = nTime; 404 block.nBits = nBits; 405 block.nNonce = nNonce; 406 block.hashStateRoot = hashStateRoot; // qtum 407 block.hashUTXORoot = hashUTXORoot; // qtum 408 block.vchBlockSigDlgt = vchBlockSigDlgt; 409 block.prevoutStake = prevoutStake; 410 return block.GetHash(); 411 } 412 413 ToString()414 std::string ToString() const 415 { 416 std::string str = "CDiskBlockIndex("; 417 str += CBlockIndex::ToString(); 418 str += strprintf("\n hashBlock=%s, hashPrev=%s)", 419 GetBlockHash().ToString(), 420 hashPrev.ToString()); 421 return str; 422 } 423 }; 424 425 /** An in-memory indexed chain of blocks. */ 426 class CChain { 427 private: 428 std::vector<CBlockIndex*> vChain; 429 430 public: 431 /** Returns the index entry for the genesis block of this chain, or nullptr if none. */ Genesis()432 CBlockIndex *Genesis() const { 433 return vChain.size() > 0 ? vChain[0] : nullptr; 434 } 435 436 /** Returns the index entry for the tip of this chain, or nullptr if none. */ Tip()437 CBlockIndex *Tip() const { 438 return vChain.size() > 0 ? vChain[vChain.size() - 1] : nullptr; 439 } 440 441 /** Returns the index entry at a particular height in this chain, or nullptr if no such height exists. */ 442 CBlockIndex *operator[](int nHeight) const { 443 if (nHeight < 0 || nHeight >= (int)vChain.size()) 444 return nullptr; 445 return vChain[nHeight]; 446 } 447 448 /** Compare two chains efficiently. */ 449 friend bool operator==(const CChain &a, const CChain &b) { 450 return a.vChain.size() == b.vChain.size() && 451 a.vChain[a.vChain.size() - 1] == b.vChain[b.vChain.size() - 1]; 452 } 453 454 /** Efficiently check whether a block is present in this chain. */ Contains(const CBlockIndex * pindex)455 bool Contains(const CBlockIndex *pindex) const { 456 return (*this)[pindex->nHeight] == pindex; 457 } 458 459 /** Find the successor of a block in this chain, or nullptr if the given index is not found or is the tip. */ Next(const CBlockIndex * pindex)460 CBlockIndex *Next(const CBlockIndex *pindex) const { 461 if (Contains(pindex)) 462 return (*this)[pindex->nHeight + 1]; 463 else 464 return nullptr; 465 } 466 467 /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->nHeight : -1. */ Height()468 int Height() const { 469 return vChain.size() - 1; 470 } 471 472 /** Set/initialize a chain with a given tip. */ 473 void SetTip(CBlockIndex *pindex); 474 475 /** Return a CBlockLocator that refers to a block in this chain (by default the tip). */ 476 CBlockLocator GetLocator(const CBlockIndex *pindex = nullptr) const; 477 478 /** Find the last common block between this chain and a block index entry. */ 479 const CBlockIndex *FindFork(const CBlockIndex *pindex) const; 480 481 /** Find the earliest block with timestamp equal or greater than the given time and height equal or greater than the given height. */ 482 CBlockIndex* FindEarliestAtLeast(int64_t nTime, int height) const; 483 }; 484 485 #endif // BITCOIN_CHAIN_H 486