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