src/chain.h

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