src/chain.h

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2016 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 "primitives/block.h"
  11 #include "pow.h"
  12 #include "tinyformat.h"
  13 #include "uint256.h"
  14
  15 #include <vector>
  16
  17 /**
  18  * Maximum amount of time that a block timestamp is allowed to exceed the
  19  * current network-adjusted time before the block will be accepted.
  20  */
  21 static const int64_t MAX_FUTURE_BLOCK_TIME = 2 * 60 * 60;
  22
  23 /**
  24  * Timestamp window used as a grace period by code that compares external
  25  * timestamps (such as timestamps passed to RPCs, or wallet key creation times)
  26  * to block timestamps. This should be set at least as high as
  27  * MAX_FUTURE_BLOCK_TIME.
  28  */
  29 static const int64_t TIMESTAMP_WINDOW = MAX_FUTURE_BLOCK_TIME;
  30
  31 class CBlockFileInfo
  32 {
  33 public:
  34     unsigned int nBlocks;      //!< number of blocks stored in file
  35     unsigned int nSize;        //!< number of used bytes of block file
  36     unsigned int nUndoSize;    //!< number of used bytes in the undo file
  37     unsigned int nHeightFirst; //!< lowest height of block in file
  38     unsigned int nHeightLast;  //!< highest height of block in file
  39     uint64_t nTimeFirst;       //!< earliest time of block in file
  40     uint64_t nTimeLast;        //!< latest time of block in file
  41
  42     ADD_SERIALIZE_METHODS;
  43
  44     template <typename Stream, typename Operation>
  45     inline void SerializationOp(Stream& s, Operation ser_action) {
  46         READWRITE(VARINT(nBlocks));
  47         READWRITE(VARINT(nSize));
  48         READWRITE(VARINT(nUndoSize));
  49         READWRITE(VARINT(nHeightFirst));
  50         READWRITE(VARINT(nHeightLast));
  51         READWRITE(VARINT(nTimeFirst));
  52         READWRITE(VARINT(nTimeLast));
  53     }
  54
  55      void SetNull() {
  56          nBlocks = 0;
  57          nSize = 0;
  58          nUndoSize = 0;
  59          nHeightFirst = 0;
  60          nHeightLast = 0;
  61          nTimeFirst = 0;
  62          nTimeLast = 0;
  63      }
  64
  65      CBlockFileInfo() {
  66          SetNull();
  67      }
  68
  69      std::string ToString() const;
  70
  71      /** update statistics (does not update nSize) */
  72      void AddBlock(unsigned int nHeightIn, uint64_t nTimeIn) {
  73          if (nBlocks==0 || nHeightFirst > nHeightIn)
  74              nHeightFirst = nHeightIn;
  75          if (nBlocks==0 || nTimeFirst > nTimeIn)
  76              nTimeFirst = nTimeIn;
  77          nBlocks++;
  78          if (nHeightIn > nHeightLast)
  79              nHeightLast = nHeightIn;
  80          if (nTimeIn > nTimeLast)
  81              nTimeLast = nTimeIn;
  82      }
  83 };
  84
  85 struct CDiskBlockPos
  86 {
  87     int nFile;
  88     unsigned int nPos;
  89
  90     ADD_SERIALIZE_METHODS;
  91
  92     template <typename Stream, typename Operation>
  93     inline void SerializationOp(Stream& s, Operation ser_action) {
  94         READWRITE(VARINT(nFile));
  95         READWRITE(VARINT(nPos));
  96     }
  97
  98     CDiskBlockPos() {
  99         SetNull();
 100     }
 101
 102     CDiskBlockPos(int nFileIn, unsigned int nPosIn) {
 103         nFile = nFileIn;
 104         nPos = nPosIn;
 105     }
 106
 107     friend bool operator==(const CDiskBlockPos &a, const CDiskBlockPos &b) {
 108         return (a.nFile == b.nFile && a.nPos == b.nPos);
 109     }
 110
 111     friend bool operator!=(const CDiskBlockPos &a, const CDiskBlockPos &b) {
 112         return !(a == b);
 113     }
 114
 115     void SetNull() { nFile = -1; nPos = 0; }
 116     bool IsNull() const { return (nFile == -1); }
 117
 118     std::string ToString() const
 119     {
 120         return strprintf("CBlockDiskPos(nFile=%i, nPos=%i)", nFile, nPos);
 121     }
 122
 123 };
 124
 125 enum BlockStatus: uint32_t {
 126     //! Unused.
 127     BLOCK_VALID_UNKNOWN      =    0,
 128
 129     //! Parsed, version ok, hash satisfies claimed PoW, 1 <= vtx count <= max, timestamp not in future
 130     BLOCK_VALID_HEADER       =    1,
 131
 132     //! All parent headers found, difficulty matches, timestamp >= median previous, checkpoint. Implies all parents
 133     //! are also at least TREE.
 134     BLOCK_VALID_TREE         =    2,
 135
 136     /**
 137      * Only first tx is coinbase, 2 <= coinbase input script length <= 100, transactions valid, no duplicate txids,
 138      * sigops, size, merkle root. Implies all parents are at least TREE but not necessarily TRANSACTIONS. When all
 139      * parent blocks also have TRANSACTIONS, CBlockIndex::nChainTx will be set.
 140      */
 141     BLOCK_VALID_TRANSACTIONS =    3,
 142
 143     //! Outputs do not overspend inputs, no double spends, coinbase output ok, no immature coinbase spends, BIP30.
 144     //! Implies all parents are also at least CHAIN.
 145     BLOCK_VALID_CHAIN        =    4,
 146
 147     //! Scripts & signatures ok. Implies all parents are also at least SCRIPTS.
 148     BLOCK_VALID_SCRIPTS      =    5,
 149
 150     //! All validity bits.
 151     BLOCK_VALID_MASK         =   BLOCK_VALID_HEADER | BLOCK_VALID_TREE | BLOCK_VALID_TRANSACTIONS |
 152                                  BLOCK_VALID_CHAIN | BLOCK_VALID_SCRIPTS,
 153
 154     BLOCK_HAVE_DATA          =    8, //!< full block available in blk*.dat
 155     BLOCK_HAVE_UNDO          =   16, //!< undo data available in rev*.dat
 156     BLOCK_HAVE_MASK          =   BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO,
 157
 158     BLOCK_FAILED_VALID       =   32, //!< stage after last reached validness failed
 159     BLOCK_FAILED_CHILD       =   64, //!< descends from failed block
 160     BLOCK_FAILED_MASK        =   BLOCK_FAILED_VALID | BLOCK_FAILED_CHILD,
 161
 162     BLOCK_OPT_WITNESS       =   128, //!< block data in blk*.data was received with a witness-enforcing client
 163 };
 164
 165 /** The block chain is a tree shaped structure starting with the
 166  * genesis block at the root, with each block potentially having multiple
 167  * candidates to be the next block. A blockindex may have multiple pprev pointing
 168  * to it, but at most one of them can be part of the currently active branch.
 169  */
 170 class CBlockIndex
 171 {
 172 public:
 173     //! pointer to the hash of the block, if any. Memory is owned by this CBlockIndex
 174     const uint256* phashBlock;
 175
 176     //! pointer to the index of the predecessor of this block
 177     CBlockIndex* pprev;
 178
 179     //! pointer to the index of some further predecessor of this block
 180     CBlockIndex* pskip;
 181
 182     //! height of the entry in the chain. The genesis block has height 0
 183     int nHeight;
 184
 185     //! Which # file this block is stored in (blk?????.dat)
 186     int nFile;
 187
 188     //! Byte offset within blk?????.dat where this block's data is stored
 189     unsigned int nDataPos;
 190
 191     //! Byte offset within rev?????.dat where this block's undo data is stored
 192     unsigned int nUndoPos;
 193
 194     //! (memory only) Total amount of work (expected number of hashes) in the chain up to and including this block
 195     arith_uint256 nChainWork;
 196
 197     //! Number of transactions in this block.
 198     //! Note: in a potential headers-first mode, this number cannot be relied upon
 199     unsigned int nTx;
 200
 201     //! (memory only) Number of transactions in the chain up to and including this block.
 202     //! This value will be non-zero only if and only if transactions for this block and all its parents are available.
 203     //! Change to 64-bit type when necessary; won't happen before 2030
 204     unsigned int nChainTx;
 205
 206     //! Verification status of this block. See enum BlockStatus
 207     unsigned int nStatus;
 208
 209     //! block header
 210     int nVersion;
 211     uint256 hashMerkleRoot;
 212     unsigned int nTime;
 213     unsigned int nBits;
 214     unsigned int nNonce;
 215
 216     //! (memory only) Sequential id assigned to distinguish order in which blocks are received.
 217     int32_t nSequenceId;
 218
 219     //! (memory only) Maximum nTime in the chain up to and including this block.
 220     unsigned int nTimeMax;
 221
 222     void SetNull()
 223     {
 224         phashBlock = nullptr;
 225         pprev = nullptr;
 226         pskip = nullptr;
 227         nHeight = 0;
 228         nFile = 0;
 229         nDataPos = 0;
 230         nUndoPos = 0;
 231         nChainWork = arith_uint256();
 232         nTx = 0;
 233         nChainTx = 0;
 234         nStatus = 0;
 235         nSequenceId = 0;
 236         nTimeMax = 0;
 237
 238         nVersion       = 0;
 239         hashMerkleRoot = uint256();
 240         nTime          = 0;
 241         nBits          = 0;
 242         nNonce         = 0;
 243     }
 244
 245     CBlockIndex()
 246     {
 247         SetNull();
 248     }
 249
 250     explicit CBlockIndex(const CBlockHeader& block)
 251     {
 252         SetNull();
 253
 254         nVersion       = block.nVersion;
 255         hashMerkleRoot = block.hashMerkleRoot;
 256         nTime          = block.nTime;
 257         nBits          = block.nBits;
 258         nNonce         = block.nNonce;
 259     }
 260
 261     CDiskBlockPos GetBlockPos() const {
 262         CDiskBlockPos ret;
 263         if (nStatus & BLOCK_HAVE_DATA) {
 264             ret.nFile = nFile;
 265             ret.nPos  = nDataPos;
 266         }
 267         return ret;
 268     }
 269
 270     CDiskBlockPos GetUndoPos() const {
 271         CDiskBlockPos ret;
 272         if (nStatus & BLOCK_HAVE_UNDO) {
 273             ret.nFile = nFile;
 274             ret.nPos  = nUndoPos;
 275         }
 276         return ret;
 277     }
 278
 279     CBlockHeader GetBlockHeader() const
 280     {
 281         CBlockHeader block;
 282         block.nVersion       = nVersion;
 283         if (pprev)
 284             block.hashPrevBlock = pprev->GetBlockHash();
 285         block.hashMerkleRoot = hashMerkleRoot;
 286         block.nTime          = nTime;
 287         block.nBits          = nBits;
 288         block.nNonce         = nNonce;
 289         return block;
 290     }
 291
 292     uint256 GetBlockHash() const
 293     {
 294         return *phashBlock;
 295     }
 296
 297     int64_t GetBlockTime() const
 298     {
 299         return (int64_t)nTime;
 300     }
 301
 302     int64_t GetBlockTimeMax() const
 303     {
 304         return (int64_t)nTimeMax;
 305     }
 306
 307     enum { nMedianTimeSpan=11 };
 308
 309     int64_t GetMedianTimePast() const
 310     {
 311         int64_t pmedian[nMedianTimeSpan];
 312         int64_t* pbegin = &pmedian[nMedianTimeSpan];
 313         int64_t* pend = &pmedian[nMedianTimeSpan];
 314
 315         const CBlockIndex* pindex = this;
 316         for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev)
 317             *(--pbegin) = pindex->GetBlockTime();
 318
 319         std::sort(pbegin, pend);
 320         return pbegin[(pend - pbegin)/2];
 321     }
 322
 323     std::string ToString() const
 324     {
 325         return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
 326             pprev, nHeight,
 327             hashMerkleRoot.ToString(),
 328             GetBlockHash().ToString());
 329     }
 330
 331     //! Check whether this block index entry is valid up to the passed validity level.
 332     bool IsValid(enum BlockStatus nUpTo = BLOCK_VALID_TRANSACTIONS) const
 333     {
 334         assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
 335         if (nStatus & BLOCK_FAILED_MASK)
 336             return false;
 337         return ((nStatus & BLOCK_VALID_MASK) >= nUpTo);
 338     }
 339
 340     //! Raise the validity level of this block index entry.
 341     //! Returns true if the validity was changed.
 342     bool RaiseValidity(enum BlockStatus nUpTo)
 343     {
 344         assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
 345         if (nStatus & BLOCK_FAILED_MASK)
 346             return false;
 347         if ((nStatus & BLOCK_VALID_MASK) < nUpTo) {
 348             nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo;
 349             return true;
 350         }
 351         return false;
 352     }
 353
 354     //! Build the skiplist pointer for this entry.
 355     void BuildSkip();
 356
 357     //! Efficiently find an ancestor of this block.
 358     CBlockIndex* GetAncestor(int height);
 359     const CBlockIndex* GetAncestor(int height) const;
 360 };
 361
 362 arith_uint256 GetBlockProof(const CBlockIndex& block);
 363 /** 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. */
 364 int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params&);
 365 /** Find the forking point between two chain tips. */
 366 const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb);
 367
 368
 369 /** Used to marshal pointers into hashes for db storage. */
 370 class CDiskBlockIndex : public CBlockIndex
 371 {
 372 public:
 373     uint256 hashPrev;
 374
 375     CDiskBlockIndex() {
 376         hashPrev = uint256();
 377     }
 378
 379     explicit CDiskBlockIndex(const CBlockIndex* pindex) : CBlockIndex(*pindex) {
 380         hashPrev = (pprev ? pprev->GetBlockHash() : uint256());
 381     }
 382
 383     ADD_SERIALIZE_METHODS;
 384
 385     template <typename Stream, typename Operation>
 386     inline void SerializationOp(Stream& s, Operation ser_action) {
 387         int _nVersion = s.GetVersion();
 388         if (!(s.GetType() & SER_GETHASH))
 389             READWRITE(VARINT(_nVersion));
 390
 391         READWRITE(VARINT(nHeight));
 392         READWRITE(VARINT(nStatus));
 393         READWRITE(VARINT(nTx));
 394         if (nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO))
 395             READWRITE(VARINT(nFile));
 396         if (nStatus & BLOCK_HAVE_DATA)
 397             READWRITE(VARINT(nDataPos));
 398         if (nStatus & BLOCK_HAVE_UNDO)
 399             READWRITE(VARINT(nUndoPos));
 400
 401         // block header
 402         READWRITE(this->nVersion);
 403         READWRITE(hashPrev);
 404         READWRITE(hashMerkleRoot);
 405         READWRITE(nTime);
 406         READWRITE(nBits);
 407         READWRITE(nNonce);
 408     }
 409
 410     uint256 GetBlockHash() const
 411     {
 412         CBlockHeader block;
 413         block.nVersion        = nVersion;
 414         block.hashPrevBlock   = hashPrev;
 415         block.hashMerkleRoot  = hashMerkleRoot;
 416         block.nTime           = nTime;
 417         block.nBits           = nBits;
 418         block.nNonce          = nNonce;
 419         return block.GetHash();
 420     }
 421
 422
 423     std::string ToString() const
 424     {
 425         std::string str = "CDiskBlockIndex(";
 426         str += CBlockIndex::ToString();
 427         str += strprintf("\n                hashBlock=%s, hashPrev=%s)",
 428             GetBlockHash().ToString(),
 429             hashPrev.ToString());
 430         return str;
 431     }
 432 };
 433
 434 /** An in-memory indexed chain of blocks. */
 435 class CChain {
 436 private:
 437     std::vector<CBlockIndex*> vChain;
 438
 439 public:
 440     /** Returns the index entry for the genesis block of this chain, or nullptr if none. */
 441     CBlockIndex *Genesis() const {
 442         return vChain.size() > 0 ? vChain[0] : nullptr;
 443     }
 444
 445     /** Returns the index entry for the tip of this chain, or nullptr if none. */
 446     CBlockIndex *Tip() const {
 447         return vChain.size() > 0 ? vChain[vChain.size() - 1] : nullptr;
 448     }
 449
 450     /** Returns the index entry at a particular height in this chain, or nullptr if no such height exists. */
 451     CBlockIndex *operator[](int nHeight) const {
 452         if (nHeight < 0 || nHeight >= (int)vChain.size())
 453             return nullptr;
 454         return vChain[nHeight];
 455     }
 456
 457     /** Compare two chains efficiently. */
 458     friend bool operator==(const CChain &a, const CChain &b) {
 459         return a.vChain.size() == b.vChain.size() &&
 460                a.vChain[a.vChain.size() - 1] == b.vChain[b.vChain.size() - 1];
 461     }
 462
 463     /** Efficiently check whether a block is present in this chain. */
 464     bool Contains(const CBlockIndex *pindex) const {
 465         return (*this)[pindex->nHeight] == pindex;
 466     }
 467
 468     /** Find the successor of a block in this chain, or nullptr if the given index is not found or is the tip. */
 469     CBlockIndex *Next(const CBlockIndex *pindex) const {
 470         if (Contains(pindex))
 471             return (*this)[pindex->nHeight + 1];
 472         else
 473             return nullptr;
 474     }
 475
 476     /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->nHeight : -1. */
 477     int Height() const {
 478         return vChain.size() - 1;
 479     }
 480
 481     /** Set/initialize a chain with a given tip. */
 482     void SetTip(CBlockIndex *pindex);
 483
 484     /** Return a CBlockLocator that refers to a block in this chain (by default the tip). */
 485     CBlockLocator GetLocator(const CBlockIndex *pindex = nullptr) const;
 486
 487     /** Find the last common block between this chain and a block index entry. */
 488     const CBlockIndex *FindFork(const CBlockIndex *pindex) const;
 489
 490     /** Find the earliest block with timestamp equal or greater than the given. */
 491     CBlockIndex* FindEarliestAtLeast(int64_t nTime) const;
 492 };
 493
 494 #endif // BITCOIN_CHAIN_H