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 upto and including this block.
 220     unsigned int nTimeMax;
 221
 222     void SetNull()
 223     {
 224         phashBlock = NULL;
 225         pprev = NULL;
 226         pskip = NULL;
 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     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
 366 /** Used to marshal pointers into hashes for db storage. */
 367 class CDiskBlockIndex : public CBlockIndex
 368 {
 369 public:
 370     uint256 hashPrev;
 371
 372     CDiskBlockIndex() {
 373         hashPrev = uint256();
 374     }
 375
 376     explicit CDiskBlockIndex(const CBlockIndex* pindex) : CBlockIndex(*pindex) {
 377         hashPrev = (pprev ? pprev->GetBlockHash() : uint256());
 378     }
 379
 380     ADD_SERIALIZE_METHODS;
 381
 382     template <typename Stream, typename Operation>
 383     inline void SerializationOp(Stream& s, Operation ser_action) {
 384         int _nVersion = s.GetVersion();
 385         if (!(s.GetType() & SER_GETHASH))
 386             READWRITE(VARINT(_nVersion));
 387
 388         READWRITE(VARINT(nHeight));
 389         READWRITE(VARINT(nStatus));
 390         READWRITE(VARINT(nTx));
 391         if (nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO))
 392             READWRITE(VARINT(nFile));
 393         if (nStatus & BLOCK_HAVE_DATA)
 394             READWRITE(VARINT(nDataPos));
 395         if (nStatus & BLOCK_HAVE_UNDO)
 396             READWRITE(VARINT(nUndoPos));
 397
 398         // block header
 399         READWRITE(this->nVersion);
 400         READWRITE(hashPrev);
 401         READWRITE(hashMerkleRoot);
 402         READWRITE(nTime);
 403         READWRITE(nBits);
 404         READWRITE(nNonce);
 405     }
 406
 407     uint256 GetBlockHash() const
 408     {
 409         CBlockHeader block;
 410         block.nVersion        = nVersion;
 411         block.hashPrevBlock   = hashPrev;
 412         block.hashMerkleRoot  = hashMerkleRoot;
 413         block.nTime           = nTime;
 414         block.nBits           = nBits;
 415         block.nNonce          = nNonce;
 416         return block.GetHash();
 417     }
 418
 419
 420     std::string ToString() const
 421     {
 422         std::string str = "CDiskBlockIndex(";
 423         str += CBlockIndex::ToString();
 424         str += strprintf("\n                hashBlock=%s, hashPrev=%s)",
 425             GetBlockHash().ToString(),
 426             hashPrev.ToString());
 427         return str;
 428     }
 429 };
 430
 431 /** An in-memory indexed chain of blocks. */
 432 class CChain {
 433 private:
 434     std::vector<CBlockIndex*> vChain;
 435
 436 public:
 437     /** Returns the index entry for the genesis block of this chain, or NULL if none. */
 438     CBlockIndex *Genesis() const {
 439         return vChain.size() > 0 ? vChain[0] : NULL;
 440     }
 441
 442     /** Returns the index entry for the tip of this chain, or NULL if none. */
 443     CBlockIndex *Tip() const {
 444         return vChain.size() > 0 ? vChain[vChain.size() - 1] : NULL;
 445     }
 446
 447     /** Returns the index entry at a particular height in this chain, or NULL if no such height exists. */
 448     CBlockIndex *operator[](int nHeight) const {
 449         if (nHeight < 0 || nHeight >= (int)vChain.size())
 450             return NULL;
 451         return vChain[nHeight];
 452     }
 453
 454     /** Compare two chains efficiently. */
 455     friend bool operator==(const CChain &a, const CChain &b) {
 456         return a.vChain.size() == b.vChain.size() &&
 457                a.vChain[a.vChain.size() - 1] == b.vChain[b.vChain.size() - 1];
 458     }
 459
 460     /** Efficiently check whether a block is present in this chain. */
 461     bool Contains(const CBlockIndex *pindex) const {
 462         return (*this)[pindex->nHeight] == pindex;
 463     }
 464
 465     /** Find the successor of a block in this chain, or NULL if the given index is not found or is the tip. */
 466     CBlockIndex *Next(const CBlockIndex *pindex) const {
 467         if (Contains(pindex))
 468             return (*this)[pindex->nHeight + 1];
 469         else
 470             return NULL;
 471     }
 472
 473     /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->nHeight : -1. */
 474     int Height() const {
 475         return vChain.size() - 1;
 476     }
 477
 478     /** Set/initialize a chain with a given tip. */
 479     void SetTip(CBlockIndex *pindex);
 480
 481     /** Return a CBlockLocator that refers to a block in this chain (by default the tip). */
 482     CBlockLocator GetLocator(const CBlockIndex *pindex = NULL) const;
 483
 484     /** Find the last common block between this chain and a block index entry. */
 485     const CBlockIndex *FindFork(const CBlockIndex *pindex) const;
 486
 487     /** Find the earliest block with timestamp equal or greater than the given. */
 488     CBlockIndex* FindEarliestAtLeast(int64_t nTime) const;
 489 };
 490
 491 #endif // BITCOIN_CHAIN_H