src/chain.h

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