src/chain.h

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