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