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