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