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 class CChainPower;
  10
  11 #include "arith_uint256.h"
  12 #include "primitives/block.h"
  13 #include "pow.h"
  14 #include "tinyformat.h"
  15 #include "uint256.h"
  16
  17 #include <vector>
  18
  19 #include <boost/foreach.hpp>
  20
  21 static const int SPROUT_VALUE_VERSION = 1001400;
  22 static const int SAPLING_VALUE_VERSION = 1010100;
  23
  24 struct CDiskBlockPos
  25 {
  26     int nFile;
  27     unsigned int nPos;
  28
  29     ADD_SERIALIZE_METHODS;
  30
  31     template <typename Stream, typename Operation>
  32     inline void SerializationOp(Stream& s, Operation ser_action) {
  33         READWRITE(VARINT(nFile));
  34         READWRITE(VARINT(nPos));
  35     }
  36
  37     CDiskBlockPos() {
  38         SetNull();
  39     }
  40
  41     CDiskBlockPos(int nFileIn, unsigned int nPosIn) {
  42         nFile = nFileIn;
  43         nPos = nPosIn;
  44     }
  45
  46     friend bool operator==(const CDiskBlockPos &a, const CDiskBlockPos &b) {
  47         return (a.nFile == b.nFile && a.nPos == b.nPos);
  48     }
  49
  50     friend bool operator!=(const CDiskBlockPos &a, const CDiskBlockPos &b) {
  51         return !(a == b);
  52     }
  53
  54     void SetNull() { nFile = -1; nPos = 0; }
  55     bool IsNull() const { return (nFile == -1); }
  56
  57     std::string ToString() const
  58     {
  59         return strprintf("CBlockDiskPos(nFile=%i, nPos=%i)", nFile, nPos);
  60     }
  61
  62 };
  63
  64 enum BlockStatus: uint32_t {
  65     //! Unused.
  66     BLOCK_VALID_UNKNOWN      =    0,
  67
  68     //! Parsed, version ok, hash satisfies claimed PoW, 1 <= vtx count <= max, timestamp not in future
  69     BLOCK_VALID_HEADER       =    1,
  70
  71     //! All parent headers found, difficulty matches, timestamp >= median previous, checkpoint. Implies all parents
  72     //! are also at least TREE.
  73     BLOCK_VALID_TREE         =    2,
  74
  75     /**
  76      * Only first tx is coinbase, 2 <= coinbase input script length <= 100, transactions valid, no duplicate txids,
  77      * sigops, size, merkle root. Implies all parents are at least TREE but not necessarily TRANSACTIONS. When all
  78      * parent blocks also have TRANSACTIONS, CBlockIndex::nChainTx will be set.
  79      */
  80     BLOCK_VALID_TRANSACTIONS =    3,
  81
  82     //! Outputs do not overspend inputs, no double spends, coinbase output ok, no immature coinbase spends, BIP30.
  83     //! Implies all parents are also at least CHAIN.
  84     BLOCK_VALID_CHAIN        =    4,
  85
  86     //! Scripts & signatures ok. Implies all parents are also at least SCRIPTS.
  87     BLOCK_VALID_SCRIPTS      =    5,
  88
  89     //! All validity bits.
  90     BLOCK_VALID_MASK         =   BLOCK_VALID_HEADER | BLOCK_VALID_TREE | BLOCK_VALID_TRANSACTIONS |
  91                                  BLOCK_VALID_CHAIN | BLOCK_VALID_SCRIPTS,
  92
  93     BLOCK_HAVE_DATA          =    8, //! full block available in blk*.dat
  94     BLOCK_HAVE_UNDO          =   16, //! undo data available in rev*.dat
  95     BLOCK_HAVE_MASK          =   BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO,
  96
  97     BLOCK_FAILED_VALID       =   32, //! stage after last reached validness failed
  98     BLOCK_FAILED_CHILD       =   64, //! descends from failed block
  99     BLOCK_FAILED_MASK        =   BLOCK_FAILED_VALID | BLOCK_FAILED_CHILD,
 100
 101     BLOCK_ACTIVATES_UPGRADE  =   128, //! block activates a network upgrade
 102 };
 103
 104 //! Short-hand for the highest consensus validity we implement.
 105 //! Blocks with this validity are assumed to satisfy all consensus rules.
 106 static const BlockStatus BLOCK_VALID_CONSENSUS = BLOCK_VALID_SCRIPTS;
 107
 108 class CBlockIndex;
 109
 110 // This class provides an accumulator for both the chainwork and the chainPOS value
 111 // CChainPower's can be compared, and the comparison ensures that work and proof of stake power
 112 // are both used equally to determine which chain has the most work. This makes an attack
 113 // that involves mining in secret completely ineffective, even before dPOW, unless a large part
 114 // of the staking supply is also controlled. It also enables a faster deterministic convergence,
 115 // aided by both POS and POW.
 116 class CChainPower
 117 {
 118     public:
 119         arith_uint256 chainWork;
 120         arith_uint256 chainStake;
 121         int32_t nHeight;
 122
 123         CChainPower() : nHeight(0), chainStake(0), chainWork(0) {}
 124         CChainPower(CBlockIndex *pblockIndex);
 125         CChainPower(CBlockIndex *pblockIndex, const arith_uint256 &stake, const arith_uint256 &work);
 126         CChainPower(int32_t height) : nHeight(height), chainStake(0), chainWork(0) {}
 127         CChainPower(int32_t height, const arith_uint256 &stake, const arith_uint256 &work) :
 128                     nHeight(height), chainStake(stake), chainWork(work) {}
 129
 130         CChainPower &operator=(const CChainPower &chainPower)
 131         {
 132             chainWork = chainPower.chainWork;
 133             chainStake = chainPower.chainStake;
 134             nHeight = chainPower.nHeight;
 135             return *this;
 136         }
 137
 138         CChainPower &operator+=(const CChainPower &chainPower)
 139         {
 140             this->chainWork += chainPower.chainWork;
 141             this->chainStake += chainPower.chainStake;
 142             return *this;
 143         }
 144
 145         friend CChainPower operator+(const CChainPower &chainPowerA, const CChainPower &chainPowerB)
 146         {
 147             CChainPower result = CChainPower(chainPowerA);
 148             result.chainWork += chainPowerB.chainWork;
 149             result.chainStake += chainPowerB.chainStake;
 150             return result;
 151         }
 152
 153         friend CChainPower operator-(const CChainPower &chainPowerA, const CChainPower &chainPowerB)
 154         {
 155             CChainPower result = CChainPower(chainPowerA);
 156             result.chainWork -= chainPowerB.chainWork;
 157             result.chainStake -= chainPowerB.chainStake;
 158             return result;
 159         }
 160
 161         friend CChainPower operator*(const CChainPower &chainPower, int32_t x)
 162         {
 163             CChainPower result = CChainPower(chainPower);
 164             result.chainWork *= x;
 165             result.chainStake *= x;
 166             return result;
 167         }
 168
 169         CChainPower &addStake(const arith_uint256 &nChainStake)
 170         {
 171             chainStake += nChainStake;
 172             return *this;
 173         }
 174
 175         CChainPower &addWork(const arith_uint256 &nChainWork)
 176         {
 177             chainWork += nChainWork;
 178             return *this;
 179         }
 180
 181         friend bool operator==(const CChainPower &p1, const CChainPower &p2);
 182
 183         friend bool operator!=(const CChainPower &p1, const CChainPower &p2)
 184         {
 185             return !(p1 == p2);
 186         }
 187
 188         friend bool operator<(const CChainPower &p1, const CChainPower &p2);
 189
 190         friend bool operator<=(const CChainPower &p1, const CChainPower &p2);
 191
 192         friend bool operator>(const CChainPower &p1, const CChainPower &p2)
 193         {
 194             return !(p1 <= p2);
 195         }
 196
 197         friend bool operator>=(const CChainPower &p1, const CChainPower &p2)
 198         {
 199             return !(p1 < p2);
 200         }
 201 };
 202
 203 /** The block chain is a tree shaped structure starting with the
 204  * genesis block at the root, with each block potentially having multiple
 205  * candidates to be the next block. A blockindex may have multiple pprev pointing
 206  * to it, but at most one of them can be part of the currently active branch.
 207  */
 208 class CBlockIndex
 209 {
 210 public:
 211     //! pointer to the hash of the block, if any. Memory is owned by this CBlockIndex
 212     const uint256* phashBlock;
 213
 214     //! pointer to the index of the predecessor of this block
 215     CBlockIndex* pprev;
 216
 217     //! pointer to the index of some further predecessor of this block
 218     CBlockIndex* pskip;
 219
 220     //! height of the entry in the chain. The genesis block has height 0
 221     int64_t newcoins,zfunds; int8_t segid; // jl777 fields
 222     //! Which # file this block is stored in (blk?????.dat)
 223     int nFile;
 224
 225     //! Byte offset within blk?????.dat where this block's data is stored
 226     unsigned int nDataPos;
 227
 228     //! Byte offset within rev?????.dat where this block's undo data is stored
 229     unsigned int nUndoPos;
 230
 231     //! (memory only) Total amount of work (expected number of hashes) in the chain up to and including this block
 232     CChainPower chainPower;
 233
 234     //! Number of transactions in this block.
 235     //! Note: in a potential headers-first mode, this number cannot be relied upon
 236     unsigned int nTx;
 237
 238     //! (memory only) Number of transactions in the chain up to and including this block.
 239     //! This value will be non-zero only if and only if transactions for this block and all its parents are available.
 240     //! Change to 64-bit type when necessary; won't happen before 2030
 241     unsigned int nChainTx;
 242
 243     //! Verification status of this block. See enum BlockStatus
 244     unsigned int nStatus;
 245
 246     //! Branch ID corresponding to the consensus rules used to validate this block.
 247     //! Only cached if block validity is BLOCK_VALID_CONSENSUS.
 248     //! Persisted at each activation height, memory-only for intervening blocks.
 249     boost::optional<uint32_t> nCachedBranchId;
 250
 251     //! The anchor for the tree state up to the start of this block
 252     uint256 hashSproutAnchor;
 253
 254     //! (memory only) The anchor for the tree state up to the end of this block
 255     uint256 hashFinalSproutRoot;
 256
 257     //! Change in value held by the Sprout circuit over this block.
 258     //! Will be boost::none for older blocks on old nodes until a reindex has taken place.
 259     boost::optional<CAmount> nSproutValue;
 260
 261     //! (memory only) Total value held by the Sprout circuit up to and including this block.
 262     //! Will be boost::none for on old nodes until a reindex has taken place.
 263     //! Will be boost::none if nChainTx is zero.
 264     boost::optional<CAmount> nChainSproutValue;
 265
 266     //! Change in value held by the Sapling circuit over this block.
 267     //! Not a boost::optional because this was added before Sapling activated, so we can
 268     //! rely on the invariant that every block before this was added had nSaplingValue = 0.
 269     CAmount nSaplingValue;
 270
 271     //! (memory only) Total value held by the Sapling circuit up to and including this block.
 272     //! Will be boost::none if nChainTx is zero.
 273     boost::optional<CAmount> nChainSaplingValue;
 274
 275     //! block header
 276     int nVersion;
 277     uint256 hashMerkleRoot;
 278     uint256 hashFinalSaplingRoot;
 279     unsigned int nTime;
 280     unsigned int nBits;
 281     uint256 nNonce;
 282     std::vector<unsigned char> nSolution;
 283
 284     //! (memory only) Sequential id assigned to distinguish order in which blocks are received.
 285     uint32_t nSequenceId;
 286
 287     void SetNull()
 288     {
 289         phashBlock = NULL;
 290         newcoins = zfunds = 0;
 291         segid = -2;
 292         pprev = NULL;
 293         pskip = NULL;
 294         nFile = 0;
 295         nDataPos = 0;
 296         nUndoPos = 0;
 297         chainPower = CChainPower();
 298         nTx = 0;
 299         nChainTx = 0;
 300         nStatus = 0;
 301         nCachedBranchId = boost::none;
 302         hashSproutAnchor = uint256();
 303         hashFinalSproutRoot = uint256();
 304         nSequenceId = 0;
 305         nSproutValue = boost::none;
 306         nChainSproutValue = boost::none;
 307         nSaplingValue = 0;
 308         nChainSaplingValue = boost::none;
 309
 310         nVersion       = 0;
 311         hashMerkleRoot = uint256();
 312         hashFinalSaplingRoot   = uint256();
 313         nTime          = 0;
 314         nBits          = 0;
 315         nNonce         = uint256();
 316         nSolution.clear();
 317     }
 318
 319     CBlockIndex()
 320     {
 321         SetNull();
 322     }
 323
 324     CBlockIndex(const CBlockHeader& block)
 325     {
 326         SetNull();
 327
 328         nVersion       = block.nVersion;
 329         hashMerkleRoot = block.hashMerkleRoot;
 330         hashFinalSaplingRoot   = block.hashFinalSaplingRoot;
 331         nTime          = block.nTime;
 332         nBits          = block.nBits;
 333         nNonce         = block.nNonce;
 334         nSolution      = block.nSolution;
 335     }
 336
 337     int32_t SetHeight(int32_t height)
 338     {
 339         this->chainPower.nHeight = height;
 340     }
 341
 342     inline int32_t GetHeight() const
 343     {
 344         return this->chainPower.nHeight;
 345     }
 346
 347     CDiskBlockPos GetBlockPos() const {
 348         CDiskBlockPos ret;
 349         if (nStatus & BLOCK_HAVE_DATA) {
 350             ret.nFile = nFile;
 351             ret.nPos  = nDataPos;
 352         }
 353         return ret;
 354     }
 355
 356     CDiskBlockPos GetUndoPos() const {
 357         CDiskBlockPos ret;
 358         if (nStatus & BLOCK_HAVE_UNDO) {
 359             ret.nFile = nFile;
 360             ret.nPos  = nUndoPos;
 361         }
 362         return ret;
 363     }
 364
 365     CBlockHeader GetBlockHeader() const
 366     {
 367         CBlockHeader block;
 368         block.nVersion       = nVersion;
 369         if (pprev)
 370             block.hashPrevBlock = pprev->GetBlockHash();
 371         block.hashMerkleRoot = hashMerkleRoot;
 372         block.hashFinalSaplingRoot   = hashFinalSaplingRoot;
 373         block.nTime          = nTime;
 374         block.nBits          = nBits;
 375         block.nNonce         = nNonce;
 376         block.nSolution      = nSolution;
 377         return block;
 378     }
 379
 380     uint256 GetBlockHash() const
 381     {
 382         return *phashBlock;
 383     }
 384
 385     int64_t GetBlockTime() const
 386     {
 387         return (int64_t)nTime;
 388     }
 389
 390     enum { nMedianTimeSpan=11 };
 391
 392     int64_t GetMedianTimePast() const
 393     {
 394         int64_t pmedian[nMedianTimeSpan];
 395         int64_t* pbegin = &pmedian[nMedianTimeSpan];
 396         int64_t* pend = &pmedian[nMedianTimeSpan];
 397
 398         const CBlockIndex* pindex = this;
 399         for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev)
 400             *(--pbegin) = pindex->GetBlockTime();
 401
 402         std::sort(pbegin, pend);
 403         return pbegin[(pend - pbegin)/2];
 404     }
 405
 406     std::string ToString() const
 407     {
 408         return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
 409             pprev, this->chainPower.nHeight,
 410             hashMerkleRoot.ToString(),
 411             GetBlockHash().ToString());
 412     }
 413
 414     //! Check whether this block index entry is valid up to the passed validity level.
 415     bool IsValid(enum BlockStatus nUpTo = BLOCK_VALID_TRANSACTIONS) const
 416     {
 417         assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
 418         if (nStatus & BLOCK_FAILED_MASK)
 419             return false;
 420         return ((nStatus & BLOCK_VALID_MASK) >= nUpTo);
 421     }
 422
 423     //! Raise the validity level of this block index entry.
 424     //! Returns true if the validity was changed.
 425     bool RaiseValidity(enum BlockStatus nUpTo)
 426     {
 427         assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
 428         if (nStatus & BLOCK_FAILED_MASK)
 429             return false;
 430         if ((nStatus & BLOCK_VALID_MASK) < nUpTo) {
 431             nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo;
 432             return true;
 433         }
 434         return false;
 435     }
 436
 437     //! Build the skiplist pointer for this entry.
 438     void BuildSkip();
 439
 440     //! Efficiently find an ancestor of this block.
 441     CBlockIndex* GetAncestor(int height);
 442     const CBlockIndex* GetAncestor(int height) const;
 443
 444     int32_t GetVerusPOSTarget() const
 445     {
 446         return GetBlockHeader().GetVerusPOSTarget();
 447     }
 448
 449     bool IsVerusPOSBlock() const
 450     {
 451         return GetBlockHeader().IsVerusPOSBlock();
 452     }
 453 };
 454
 455 /** Used to marshal pointers into hashes for db storage. */
 456 class CDiskBlockIndex : public CBlockIndex
 457 {
 458 public:
 459     uint256 hashPrev;
 460
 461     CDiskBlockIndex() : CBlockIndex() {
 462         hashPrev = uint256();
 463     }
 464
 465     explicit CDiskBlockIndex(const CBlockIndex* pindex) : CBlockIndex(*pindex) {
 466         hashPrev = (pprev ? pprev->GetBlockHash() : uint256());
 467     }
 468
 469     ADD_SERIALIZE_METHODS;
 470
 471     template <typename Stream, typename Operation>
 472     inline void SerializationOp(Stream& s, Operation ser_action) {
 473         int nVersion = s.GetVersion();
 474 #ifdef VERUSHASHDEBUG
 475         if (!ser_action.ForRead()) printf("Serializing block index %s, stream version: %x\n", ToString().c_str(), nVersion);
 476 #endif
 477         if (!(s.GetType() & SER_GETHASH))
 478             READWRITE(VARINT(nVersion));
 479
 480         if (ser_action.ForRead()) {
 481             chainPower = CChainPower();
 482         }
 483         READWRITE(VARINT(chainPower.nHeight));
 484         READWRITE(VARINT(nStatus));
 485         READWRITE(VARINT(nTx));
 486         if (nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO))
 487             READWRITE(VARINT(nFile));
 488         if (nStatus & BLOCK_HAVE_DATA)
 489             READWRITE(VARINT(nDataPos));
 490         if (nStatus & BLOCK_HAVE_UNDO)
 491             READWRITE(VARINT(nUndoPos));
 492         if (nStatus & BLOCK_ACTIVATES_UPGRADE) {
 493             if (ser_action.ForRead()) {
 494                 uint32_t branchId;
 495                 READWRITE(branchId);
 496                 nCachedBranchId = branchId;
 497             } else {
 498                 // nCachedBranchId must always be set if BLOCK_ACTIVATES_UPGRADE is set.
 499                 assert(nCachedBranchId);
 500                 uint32_t branchId = *nCachedBranchId;
 501                 READWRITE(branchId);
 502             }
 503         }
 504         READWRITE(hashSproutAnchor);
 505
 506         // block header
 507         READWRITE(this->nVersion);
 508         READWRITE(hashPrev);
 509         READWRITE(hashMerkleRoot);
 510         READWRITE(hashFinalSaplingRoot);
 511         READWRITE(nTime);
 512         READWRITE(nBits);
 513         READWRITE(nNonce);
 514         READWRITE(nSolution);
 515
 516         // Only read/write nSproutValue if the client version used to create
 517         // this index was storing them.
 518         if ((s.GetType() & SER_DISK) && (nVersion >= SPROUT_VALUE_VERSION)) {
 519             READWRITE(nSproutValue);
 520         }
 521
 522         // Only read/write nSaplingValue if the client version used to create
 523         // this index was storing them.
 524         if ((s.GetType() & SER_DISK) && (nVersion >= SAPLING_VALUE_VERSION)) {
 525             READWRITE(nSaplingValue);
 526         }
 527     }
 528
 529     uint256 GetBlockHash() const
 530     {
 531         CBlockHeader block;
 532         block.nVersion        = nVersion;
 533         block.hashPrevBlock   = hashPrev;
 534         block.hashMerkleRoot  = hashMerkleRoot;
 535         block.hashFinalSaplingRoot    = hashFinalSaplingRoot;
 536         block.nTime           = nTime;
 537         block.nBits           = nBits;
 538         block.nNonce          = nNonce;
 539         block.nSolution       = nSolution;
 540         return block.GetHash();
 541     }
 542
 543
 544     std::string ToString() const
 545     {
 546         std::string str = "CDiskBlockIndex(";
 547         str += strprintf("nVersion=%x, pprev=%p, nHeight=%d, merkle=%s\nhashBlock=%s, hashPrev=%s)\n",
 548             this->nVersion, pprev, this->chainPower.nHeight, hashMerkleRoot.ToString(), GetBlockHash().ToString(), hashPrev.ToString());
 549         return str;
 550     }
 551 };
 552
 553 /** An in-memory indexed chain of blocks. */
 554 class CChain {
 555 private:
 556     std::vector<CBlockIndex*> vChain;
 557     CBlockIndex *lastTip;
 558
 559 public:
 560     /** Returns the index entry for the genesis block of this chain, or NULL if none. */
 561     CBlockIndex *Genesis() const {
 562         return vChain.size() > 0 ? vChain[0] : NULL;
 563     }
 564
 565     /** Returns the index entry for the tip of this chain, or NULL if none. */
 566     CBlockIndex *Tip() const {
 567         return vChain.size() > 0 ? vChain[vChain.size() - 1] : NULL;
 568     }
 569
 570     /** Returns the last tip of the chain, or NULL if none. */
 571     CBlockIndex *LastTip() const {
 572         return vChain.size() > 0 ? lastTip : NULL;
 573     }
 574
 575     /** Returns the index entry at a particular height in this chain, or NULL if no such height exists. */
 576     CBlockIndex *operator[](int nHeight) const {
 577         if (nHeight < 0 || nHeight >= (int)vChain.size())
 578             return NULL;
 579         return vChain[nHeight];
 580     }
 581
 582     /** Compare two chains efficiently. */
 583     friend bool operator==(const CChain &a, const CChain &b) {
 584         return a.vChain.size() == b.vChain.size() &&
 585                a.vChain[a.vChain.size() - 1] == b.vChain[b.vChain.size() - 1];
 586     }
 587
 588     /** Efficiently check whether a block is present in this chain. */
 589     bool Contains(const CBlockIndex *pindex) const {
 590         return (*this)[pindex->GetHeight()] == pindex;
 591     }
 592
 593     /** Find the successor of a block in this chain, or NULL if the given index is not found or is the tip. */
 594     CBlockIndex *Next(const CBlockIndex *pindex) const {
 595         if (Contains(pindex))
 596             return (*this)[pindex->GetHeight() + 1];
 597         else
 598             return NULL;
 599     }
 600
 601     /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->GetHeight() : -1. */
 602     int Height() const {
 603         return vChain.size() - 1;
 604     }
 605
 606     /** Set/initialize a chain with a given tip. */
 607     void SetTip(CBlockIndex *pindex);
 608
 609     /** Return a CBlockLocator that refers to a block in this chain (by default the tip). */
 610     CBlockLocator GetLocator(const CBlockIndex *pindex = NULL) const;
 611
 612     /** Find the last common block between this chain and a block index entry. */
 613     const CBlockIndex *FindFork(const CBlockIndex *pindex) const;
 614 };
 615
 616 #endif // BITCOIN_CHAIN_H