Back to home page

Bitcoin sources

 
 

    


File indexing completed on 2020-06-26 04:55:46

0001 // Copyright (c) 2009-2010 Satoshi Nakamoto
0002 // Copyright (c) 2009-2014 The Bitcoin developers
0003 // Distributed under the MIT software license, see the accompanying
0004 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
0005 
0006 #ifndef BITCOIN_CHAIN_H
0007 #define BITCOIN_CHAIN_H
0008 
0009 #include "primitives/block.h"
0010 #include "pow.h"
0011 #include "tinyformat.h"
0012 #include "uint256.h"
0013 
0014 #include <vector>
0015 
0016 #include <boost/foreach.hpp>
0017 
0018 struct CDiskBlockPos
0019 {
0020     int nFile;
0021     unsigned int nPos;
0022 
0023     ADD_SERIALIZE_METHODS;
0024 
0025     template <typename Stream, typename Operation>
0026     inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
0027         READWRITE(VARINT(nFile));
0028         READWRITE(VARINT(nPos));
0029     }
0030 
0031     CDiskBlockPos() {
0032         SetNull();
0033     }
0034 
0035     CDiskBlockPos(int nFileIn, unsigned int nPosIn) {
0036         nFile = nFileIn;
0037         nPos = nPosIn;
0038     }
0039 
0040     friend bool operator==(const CDiskBlockPos &a, const CDiskBlockPos &b) {
0041         return (a.nFile == b.nFile && a.nPos == b.nPos);
0042     }
0043 
0044     friend bool operator!=(const CDiskBlockPos &a, const CDiskBlockPos &b) {
0045         return !(a == b);
0046     }
0047 
0048     void SetNull() { nFile = -1; nPos = 0; }
0049     bool IsNull() const { return (nFile == -1); }
0050 };
0051 
0052 enum BlockStatus {
0053     //! Unused.
0054     BLOCK_VALID_UNKNOWN      =    0,
0055 
0056     //! Parsed, version ok, hash satisfies claimed PoW, 1 <= vtx count <= max, timestamp not in future
0057     BLOCK_VALID_HEADER       =    1,
0058 
0059     //! All parent headers found, difficulty matches, timestamp >= median previous, checkpoint. Implies all parents
0060     //! are also at least TREE.
0061     BLOCK_VALID_TREE         =    2,
0062 
0063     /**
0064      * Only first tx is coinbase, 2 <= coinbase input script length <= 100, transactions valid, no duplicate txids,
0065      * sigops, size, merkle root. Implies all parents are at least TREE but not necessarily TRANSACTIONS. When all
0066      * parent blocks also have TRANSACTIONS, CBlockIndex::nChainTx will be set.
0067      */
0068     BLOCK_VALID_TRANSACTIONS =    3,
0069 
0070     //! Outputs do not overspend inputs, no double spends, coinbase output ok, immature coinbase spends, BIP30.
0071     //! Implies all parents are also at least CHAIN.
0072     BLOCK_VALID_CHAIN        =    4,
0073 
0074     //! Scripts & signatures ok. Implies all parents are also at least SCRIPTS.
0075     BLOCK_VALID_SCRIPTS      =    5,
0076 
0077     //! All validity bits.
0078     BLOCK_VALID_MASK         =   BLOCK_VALID_HEADER | BLOCK_VALID_TREE | BLOCK_VALID_TRANSACTIONS |
0079                                  BLOCK_VALID_CHAIN | BLOCK_VALID_SCRIPTS,
0080 
0081     BLOCK_HAVE_DATA          =    8, //! full block available in blk*.dat
0082     BLOCK_HAVE_UNDO          =   16, //! undo data available in rev*.dat
0083     BLOCK_HAVE_MASK          =   BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO,
0084 
0085     BLOCK_FAILED_VALID       =   32, //! stage after last reached validness failed
0086     BLOCK_FAILED_CHILD       =   64, //! descends from failed block
0087     BLOCK_FAILED_MASK        =   BLOCK_FAILED_VALID | BLOCK_FAILED_CHILD,
0088 };
0089 
0090 /** The block chain is a tree shaped structure starting with the
0091  * genesis block at the root, with each block potentially having multiple
0092  * candidates to be the next block. A blockindex may have multiple pprev pointing
0093  * to it, but at most one of them can be part of the currently active branch.
0094  */
0095 class CBlockIndex
0096 {
0097 public:
0098     //! pointer to the hash of the block, if any. memory is owned by this CBlockIndex
0099     const uint256* phashBlock;
0100 
0101     //! pointer to the index of the predecessor of this block
0102     CBlockIndex* pprev;
0103 
0104     //! pointer to the index of some further predecessor of this block
0105     CBlockIndex* pskip;
0106 
0107     //! height of the entry in the chain. The genesis block has height 0
0108     int nHeight;
0109 
0110     //! Which # file this block is stored in (blk?????.dat)
0111     int nFile;
0112 
0113     //! Byte offset within blk?????.dat where this block's data is stored
0114     unsigned int nDataPos;
0115 
0116     //! Byte offset within rev?????.dat where this block's undo data is stored
0117     unsigned int nUndoPos;
0118 
0119     //! (memory only) Total amount of work (expected number of hashes) in the chain up to and including this block
0120     uint256 nChainWork;
0121 
0122     //! Number of transactions in this block.
0123     //! Note: in a potential headers-first mode, this number cannot be relied upon
0124     unsigned int nTx;
0125 
0126     //! (memory only) Number of transactions in the chain up to and including this block.
0127     //! This value will be non-zero only if and only if transactions for this block and all its parents are available.
0128     //! Change to 64-bit type when necessary; won't happen before 2030
0129     unsigned int nChainTx;
0130 
0131     //! Verification status of this block. See enum BlockStatus
0132     unsigned int nStatus;
0133 
0134     //! block header
0135     int nVersion;
0136     uint256 hashMerkleRoot;
0137     unsigned int nTime;
0138     unsigned int nBits;
0139     unsigned int nNonce;
0140 
0141     //! (memory only) Sequential id assigned to distinguish order in which blocks are received.
0142     uint32_t nSequenceId;
0143 
0144     void SetNull()
0145     {
0146         phashBlock = NULL;
0147         pprev = NULL;
0148         pskip = NULL;
0149         nHeight = 0;
0150         nFile = 0;
0151         nDataPos = 0;
0152         nUndoPos = 0;
0153         nChainWork = 0;
0154         nTx = 0;
0155         nChainTx = 0;
0156         nStatus = 0;
0157         nSequenceId = 0;
0158 
0159         nVersion       = 0;
0160         hashMerkleRoot = 0;
0161         nTime          = 0;
0162         nBits          = 0;
0163         nNonce         = 0;
0164     }
0165 
0166     CBlockIndex()
0167     {
0168         SetNull();
0169     }
0170 
0171     CBlockIndex(const CBlockHeader& block)
0172     {
0173         SetNull();
0174 
0175         nVersion       = block.nVersion;
0176         hashMerkleRoot = block.hashMerkleRoot;
0177         nTime          = block.nTime;
0178         nBits          = block.nBits;
0179         nNonce         = block.nNonce;
0180     }
0181 
0182     CDiskBlockPos GetBlockPos() const {
0183         CDiskBlockPos ret;
0184         if (nStatus & BLOCK_HAVE_DATA) {
0185             ret.nFile = nFile;
0186             ret.nPos  = nDataPos;
0187         }
0188         return ret;
0189     }
0190 
0191     CDiskBlockPos GetUndoPos() const {
0192         CDiskBlockPos ret;
0193         if (nStatus & BLOCK_HAVE_UNDO) {
0194             ret.nFile = nFile;
0195             ret.nPos  = nUndoPos;
0196         }
0197         return ret;
0198     }
0199 
0200     CBlockHeader GetBlockHeader() const
0201     {
0202         CBlockHeader block;
0203         block.nVersion       = nVersion;
0204         if (pprev)
0205             block.hashPrevBlock = pprev->GetBlockHash();
0206         block.hashMerkleRoot = hashMerkleRoot;
0207         block.nTime          = nTime;
0208         block.nBits          = nBits;
0209         block.nNonce         = nNonce;
0210         return block;
0211     }
0212 
0213     uint256 GetBlockHash() const
0214     {
0215         return *phashBlock;
0216     }
0217 
0218     int64_t GetBlockTime() const
0219     {
0220         return (int64_t)nTime;
0221     }
0222 
0223     enum { nMedianTimeSpan=11 };
0224 
0225     int64_t GetMedianTimePast() const
0226     {
0227         int64_t pmedian[nMedianTimeSpan];
0228         int64_t* pbegin = &pmedian[nMedianTimeSpan];
0229         int64_t* pend = &pmedian[nMedianTimeSpan];
0230 
0231         const CBlockIndex* pindex = this;
0232         for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev)
0233             *(--pbegin) = pindex->GetBlockTime();
0234 
0235         std::sort(pbegin, pend);
0236         return pbegin[(pend - pbegin)/2];
0237     }
0238 
0239     /**
0240      * Returns true if there are nRequired or more blocks of minVersion or above
0241      * in the last Params().ToCheckBlockUpgradeMajority() blocks, starting at pstart 
0242      * and going backwards.
0243      */
0244     static bool IsSuperMajority(int minVersion, const CBlockIndex* pstart,
0245                                 unsigned int nRequired);
0246 
0247     std::string ToString() const
0248     {
0249         return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
0250             pprev, nHeight,
0251             hashMerkleRoot.ToString(),
0252             GetBlockHash().ToString());
0253     }
0254 
0255     //! Check whether this block index entry is valid up to the passed validity level.
0256     bool IsValid(enum BlockStatus nUpTo = BLOCK_VALID_TRANSACTIONS) const
0257     {
0258         assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
0259         if (nStatus & BLOCK_FAILED_MASK)
0260             return false;
0261         return ((nStatus & BLOCK_VALID_MASK) >= nUpTo);
0262     }
0263 
0264     //! Raise the validity level of this block index entry.
0265     //! Returns true if the validity was changed.
0266     bool RaiseValidity(enum BlockStatus nUpTo)
0267     {
0268         assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
0269         if (nStatus & BLOCK_FAILED_MASK)
0270             return false;
0271         if ((nStatus & BLOCK_VALID_MASK) < nUpTo) {
0272             nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo;
0273             return true;
0274         }
0275         return false;
0276     }
0277 
0278     //! Build the skiplist pointer for this entry.
0279     void BuildSkip();
0280 
0281     //! Efficiently find an ancestor of this block.
0282     CBlockIndex* GetAncestor(int height);
0283     const CBlockIndex* GetAncestor(int height) const;
0284 };
0285 
0286 /** Used to marshal pointers into hashes for db storage. */
0287 class CDiskBlockIndex : public CBlockIndex
0288 {
0289 public:
0290     uint256 hashPrev;
0291 
0292     CDiskBlockIndex() {
0293         hashPrev = 0;
0294     }
0295 
0296     explicit CDiskBlockIndex(CBlockIndex* pindex) : CBlockIndex(*pindex) {
0297         hashPrev = (pprev ? pprev->GetBlockHash() : 0);
0298     }
0299 
0300     ADD_SERIALIZE_METHODS;
0301 
0302     template <typename Stream, typename Operation>
0303     inline void SerializationOp(Stream& s, Operation ser_action, int nType, int nVersion) {
0304         if (!(nType & SER_GETHASH))
0305             READWRITE(VARINT(nVersion));
0306 
0307         READWRITE(VARINT(nHeight));
0308         READWRITE(VARINT(nStatus));
0309         READWRITE(VARINT(nTx));
0310         if (nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO))
0311             READWRITE(VARINT(nFile));
0312         if (nStatus & BLOCK_HAVE_DATA)
0313             READWRITE(VARINT(nDataPos));
0314         if (nStatus & BLOCK_HAVE_UNDO)
0315             READWRITE(VARINT(nUndoPos));
0316 
0317         // block header
0318         READWRITE(this->nVersion);
0319         READWRITE(hashPrev);
0320         READWRITE(hashMerkleRoot);
0321         READWRITE(nTime);
0322         READWRITE(nBits);
0323         READWRITE(nNonce);
0324     }
0325 
0326     uint256 GetBlockHash() const
0327     {
0328         CBlockHeader block;
0329         block.nVersion        = nVersion;
0330         block.hashPrevBlock   = hashPrev;
0331         block.hashMerkleRoot  = hashMerkleRoot;
0332         block.nTime           = nTime;
0333         block.nBits           = nBits;
0334         block.nNonce          = nNonce;
0335         return block.GetHash();
0336     }
0337 
0338 
0339     std::string ToString() const
0340     {
0341         std::string str = "CDiskBlockIndex(";
0342         str += CBlockIndex::ToString();
0343         str += strprintf("\n                hashBlock=%s, hashPrev=%s)",
0344             GetBlockHash().ToString(),
0345             hashPrev.ToString());
0346         return str;
0347     }
0348 };
0349 
0350 /** An in-memory indexed chain of blocks. */
0351 class CChain {
0352 private:
0353     std::vector<CBlockIndex*> vChain;
0354 
0355 public:
0356     /** Returns the index entry for the genesis block of this chain, or NULL if none. */
0357     CBlockIndex *Genesis() const {
0358         return vChain.size() > 0 ? vChain[0] : NULL;
0359     }
0360 
0361     /** Returns the index entry for the tip of this chain, or NULL if none. */
0362     CBlockIndex *Tip() const {
0363         return vChain.size() > 0 ? vChain[vChain.size() - 1] : NULL;
0364     }
0365 
0366     /** Returns the index entry at a particular height in this chain, or NULL if no such height exists. */
0367     CBlockIndex *operator[](int nHeight) const {
0368         if (nHeight < 0 || nHeight >= (int)vChain.size())
0369             return NULL;
0370         return vChain[nHeight];
0371     }
0372 
0373     /** Compare two chains efficiently. */
0374     friend bool operator==(const CChain &a, const CChain &b) {
0375         return a.vChain.size() == b.vChain.size() &&
0376                a.vChain[a.vChain.size() - 1] == b.vChain[b.vChain.size() - 1];
0377     }
0378 
0379     /** Efficiently check whether a block is present in this chain. */
0380     bool Contains(const CBlockIndex *pindex) const {
0381         return (*this)[pindex->nHeight] == pindex;
0382     }
0383 
0384     /** Find the successor of a block in this chain, or NULL if the given index is not found or is the tip. */
0385     CBlockIndex *Next(const CBlockIndex *pindex) const {
0386         if (Contains(pindex))
0387             return (*this)[pindex->nHeight + 1];
0388         else
0389             return NULL;
0390     }
0391 
0392     /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->nHeight : -1. */
0393     int Height() const {
0394         return vChain.size() - 1;
0395     }
0396 
0397     /** Set/initialize a chain with a given tip. */
0398     void SetTip(CBlockIndex *pindex);
0399 
0400     /** Return a CBlockLocator that refers to a block in this chain (by default the tip). */
0401     CBlockLocator GetLocator(const CBlockIndex *pindex = NULL) const;
0402 
0403     /** Find the last common block between this chain and a block index entry. */
0404     const CBlockIndex *FindFork(const CBlockIndex *pindex) const;
0405 };
0406 
0407 #endif // BITCOIN_CHAIN_H