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