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         printf("New block Index from block. nVersion: %x, nTime: %d, nBits: %d, nNonce: %s\n", block.nVersion, block.nTime, block.nBits, block.nNonce.GetHex().c_str());
 327         SetNull();
 328
 329         nVersion       = block.nVersion;
 330         hashMerkleRoot = block.hashMerkleRoot;
 331         hashFinalSaplingRoot   = block.hashFinalSaplingRoot;
 332         nTime          = block.nTime;
 333         nBits          = block.nBits;
 334         nNonce         = block.nNonce;
 335         nSolution      = block.nSolution;
 336     }
 337
 338     int32_t SetHeight(int32_t height)
 339     {
 340         this->chainPower.nHeight = height;
 341     }
 342
 343     inline int32_t GetHeight() const
 344     {
 345         return this->chainPower.nHeight;
 346     }
 347
 348     CDiskBlockPos GetBlockPos() const {
 349         CDiskBlockPos ret;
 350         if (nStatus & BLOCK_HAVE_DATA) {
 351             ret.nFile = nFile;
 352             ret.nPos  = nDataPos;
 353         }
 354         return ret;
 355     }
 356
 357     CDiskBlockPos GetUndoPos() const {
 358         CDiskBlockPos ret;
 359         if (nStatus & BLOCK_HAVE_UNDO) {
 360             ret.nFile = nFile;
 361             ret.nPos  = nUndoPos;
 362         }
 363         return ret;
 364     }
 365
 366     CBlockHeader GetBlockHeader() const
 367     {
 368         CBlockHeader block;
 369         block.nVersion       = nVersion;
 370         if (pprev)
 371             block.hashPrevBlock = pprev->GetBlockHash();
 372         block.hashMerkleRoot = hashMerkleRoot;
 373         block.hashFinalSaplingRoot   = hashFinalSaplingRoot;
 374         block.nTime          = nTime;
 375         block.nBits          = nBits;
 376         block.nNonce         = nNonce;
 377         block.nSolution      = nSolution;
 378         return block;
 379     }
 380
 381     uint256 GetBlockHash() const
 382     {
 383         return *phashBlock;
 384     }
 385
 386     int64_t GetBlockTime() const
 387     {
 388         return (int64_t)nTime;
 389     }
 390
 391     enum { nMedianTimeSpan=11 };
 392
 393     int64_t GetMedianTimePast() const
 394     {
 395         int64_t pmedian[nMedianTimeSpan];
 396         int64_t* pbegin = &pmedian[nMedianTimeSpan];
 397         int64_t* pend = &pmedian[nMedianTimeSpan];
 398
 399         const CBlockIndex* pindex = this;
 400         for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev)
 401             *(--pbegin) = pindex->GetBlockTime();
 402
 403         std::sort(pbegin, pend);
 404         return pbegin[(pend - pbegin)/2];
 405     }
 406
 407     std::string ToString() const
 408     {
 409         return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
 410             pprev, this->chainPower.nHeight,
 411             hashMerkleRoot.ToString(),
 412             GetBlockHash().ToString());
 413     }
 414
 415     //! Check whether this block index entry is valid up to the passed validity level.
 416     bool IsValid(enum BlockStatus nUpTo = BLOCK_VALID_TRANSACTIONS) const
 417     {
 418         assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
 419         if (nStatus & BLOCK_FAILED_MASK)
 420             return false;
 421         return ((nStatus & BLOCK_VALID_MASK) >= nUpTo);
 422     }
 423
 424     //! Raise the validity level of this block index entry.
 425     //! Returns true if the validity was changed.
 426     bool RaiseValidity(enum BlockStatus nUpTo)
 427     {
 428         assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
 429         if (nStatus & BLOCK_FAILED_MASK)
 430             return false;
 431         if ((nStatus & BLOCK_VALID_MASK) < nUpTo) {
 432             nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo;
 433             return true;
 434         }
 435         return false;
 436     }
 437
 438     //! Build the skiplist pointer for this entry.
 439     void BuildSkip();
 440
 441     //! Efficiently find an ancestor of this block.
 442     CBlockIndex* GetAncestor(int height);
 443     const CBlockIndex* GetAncestor(int height) const;
 444
 445     int32_t GetVerusPOSTarget() const
 446     {
 447         return GetBlockHeader().GetVerusPOSTarget();
 448     }
 449
 450     bool IsVerusPOSBlock() const
 451     {
 452         return GetBlockHeader().IsVerusPOSBlock();
 453     }
 454 };
 455
 456 /** Used to marshal pointers into hashes for db storage. */
 457 class CDiskBlockIndex : public CBlockIndex
 458 {
 459 public:
 460     uint256 hashPrev;
 461
 462     CDiskBlockIndex() : CBlockIndex() {
 463         hashPrev = uint256();
 464     }
 465
 466     explicit CDiskBlockIndex(const CBlockIndex* pindex) : CBlockIndex(*pindex) {
 467         hashPrev = (pprev ? pprev->GetBlockHash() : uint256());
 468     }
 469
 470     ADD_SERIALIZE_METHODS;
 471
 472     template <typename Stream, typename Operation>
 473     inline void SerializationOp(Stream& s, Operation ser_action) {
 474         int nVersion = s.GetVersion(); if (!ser_action.ForRead()) printf("Serializing block index %s, stream version: %x\n", ToString().c_str(), nVersion);
 475         if (!(s.GetType() & SER_GETHASH))
 476             READWRITE(VARINT(nVersion));
 477
 478         if (ser_action.ForRead()) {
 479             chainPower = CChainPower();
 480         }
 481         READWRITE(VARINT(chainPower.nHeight));
 482         READWRITE(VARINT(nStatus));
 483         READWRITE(VARINT(nTx));
 484         if (nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO))
 485             READWRITE(VARINT(nFile));
 486         if (nStatus & BLOCK_HAVE_DATA)
 487             READWRITE(VARINT(nDataPos));
 488         if (nStatus & BLOCK_HAVE_UNDO)
 489             READWRITE(VARINT(nUndoPos));
 490         if (nStatus & BLOCK_ACTIVATES_UPGRADE) {
 491             if (ser_action.ForRead()) {
 492                 uint32_t branchId;
 493                 READWRITE(branchId);
 494                 nCachedBranchId = branchId;
 495             } else {
 496                 // nCachedBranchId must always be set if BLOCK_ACTIVATES_UPGRADE is set.
 497                 assert(nCachedBranchId);
 498                 uint32_t branchId = *nCachedBranchId;
 499                 READWRITE(branchId);
 500             }
 501         }
 502         READWRITE(hashSproutAnchor);
 503
 504         // block header
 505         READWRITE(this->nVersion);
 506         READWRITE(hashPrev);
 507         READWRITE(hashMerkleRoot);
 508         READWRITE(hashFinalSaplingRoot);
 509         READWRITE(nTime);
 510         READWRITE(nBits);
 511         READWRITE(nNonce);
 512         READWRITE(nSolution);
 513
 514         // Only read/write nSproutValue if the client version used to create
 515         // this index was storing them.
 516         if ((s.GetType() & SER_DISK) && (nVersion >= SPROUT_VALUE_VERSION)) {
 517             READWRITE(nSproutValue);
 518         }
 519
 520         // Only read/write nSaplingValue if the client version used to create
 521         // this index was storing them.
 522         if ((s.GetType() & SER_DISK) && (nVersion >= SAPLING_VALUE_VERSION)) {
 523             READWRITE(nSaplingValue);
 524         }
 525     }
 526
 527     uint256 GetBlockHash() const
 528     {
 529         if (nVersion == CBlockHeader::VERUS_V2)
 530         {
 531             printf("CBlockIndex(nVersion=%x, pprev=%p, nHeight=%d, merkle=%s, ", this->nVersion, pprev, this->chainPower.nHeight, hashMerkleRoot.ToString().c_str());
 532         }
 533         CBlockHeader block;
 534         block.nVersion        = nVersion;
 535         block.hashPrevBlock   = hashPrev;
 536         block.hashMerkleRoot  = hashMerkleRoot;
 537         block.hashFinalSaplingRoot    = hashFinalSaplingRoot;
 538         block.nTime           = nTime;
 539         block.nBits           = nBits;
 540         block.nNonce          = nNonce;
 541         block.nSolution       = nSolution;
 542         return block.GetHash();
 543     }
 544
 545
 546     std::string ToString() const
 547     {
 548         std::string str = "CDiskBlockIndex(";
 549         str += strprintf("CBlockIndex(nVersion=%x, pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s, hashPrev=%s)\n",
 550             this->nVersion, pprev, this->chainPower.nHeight, hashMerkleRoot.ToString(), GetBlockHash().ToString(), hashPrev.ToString());
 551         return str;
 552     }
 553 };
 554
 555 /** An in-memory indexed chain of blocks. */
 556 class CChain {
 557 private:
 558     std::vector<CBlockIndex*> vChain;
 559     CBlockIndex *lastTip;
 560
 561 public:
 562     /** Returns the index entry for the genesis block of this chain, or NULL if none. */
 563     CBlockIndex *Genesis() const {
 564         return vChain.size() > 0 ? vChain[0] : NULL;
 565     }
 566
 567     /** Returns the index entry for the tip of this chain, or NULL if none. */
 568     CBlockIndex *Tip() const {
 569         return vChain.size() > 0 ? vChain[vChain.size() - 1] : NULL;
 570     }
 571
 572     /** Returns the last tip of the chain, or NULL if none. */
 573     CBlockIndex *LastTip() const {
 574         return vChain.size() > 0 ? lastTip : NULL;
 575     }
 576
 577     /** Returns the index entry at a particular height in this chain, or NULL if no such height exists. */
 578     CBlockIndex *operator[](int nHeight) const {
 579         if (nHeight < 0 || nHeight >= (int)vChain.size())
 580             return NULL;
 581         return vChain[nHeight];
 582     }
 583
 584     /** Compare two chains efficiently. */
 585     friend bool operator==(const CChain &a, const CChain &b) {
 586         return a.vChain.size() == b.vChain.size() &&
 587                a.vChain[a.vChain.size() - 1] == b.vChain[b.vChain.size() - 1];
 588     }
 589
 590     /** Efficiently check whether a block is present in this chain. */
 591     bool Contains(const CBlockIndex *pindex) const {
 592         return (*this)[pindex->GetHeight()] == pindex;
 593     }
 594
 595     /** Find the successor of a block in this chain, or NULL if the given index is not found or is the tip. */
 596     CBlockIndex *Next(const CBlockIndex *pindex) const {
 597         if (Contains(pindex))
 598             return (*this)[pindex->GetHeight() + 1];
 599         else
 600             return NULL;
 601     }
 602
 603     /** Return the maximal height in the chain. Is equal to chain.Tip() ? chain.Tip()->GetHeight() : -1. */
 604     int Height() const {
 605         return vChain.size() - 1;
 606     }
 607
 608     /** Set/initialize a chain with a given tip. */
 609     void SetTip(CBlockIndex *pindex);
 610
 611     /** Return a CBlockLocator that refers to a block in this chain (by default the tip). */
 612     CBlockLocator GetLocator(const CBlockIndex *pindex = NULL) const;
 613
 614     /** Find the last common block between this chain and a block index entry. */
 615     const CBlockIndex *FindFork(const CBlockIndex *pindex) const;
 616 };
 617
 618 #endif // BITCOIN_CHAIN_H