Line data    Source code

       1             : // Copyright (c) 2009-2010 Satoshi Nakamoto
       2             : // Copyright (c) 2009-2014 The Bitcoin developers
       3             : // Copyright (c) 2016-2021 The PIVX Core developers
       4             : // Distributed under the MIT software license, see the accompanying
       5             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       6             : 
       7             : #include "chain.h"
       8             : #include "legacy/stakemodifier.h"  // for ComputeNextStakeModifier
       9             : 
      10             : 
      11             : /**
      12             :  * CChain implementation
      13             :  */
      14       42550 : void CChain::SetTip(CBlockIndex* pindex)
      15             : {
      16       42550 :     if (pindex == nullptr) {
      17         483 :         vChain.clear();
      18         483 :         return;
      19             :     }
      20       42067 :     vChain.resize(pindex->nHeight + 1);
      21      316325 :     while (pindex && vChain[pindex->nHeight] != pindex) {
      22      274258 :         vChain[pindex->nHeight] = pindex;
      23      274258 :         pindex = pindex->pprev;
      24             :     }
      25             : }
      26             : 
      27        1682 : CBlockLocator CChain::GetLocator(const CBlockIndex* pindex) const
      28             : {
      29        1682 :     int nStep = 1;
      30        1682 :     std::vector<uint256> vHave;
      31        1682 :     vHave.reserve(32);
      32             : 
      33        1682 :     if (!pindex)
      34         355 :         pindex = Tip();
      35       16162 :     while (pindex) {
      36       15978 :         vHave.push_back(pindex->GetBlockHash());
      37             :         // Stop when we have added the genesis block.
      38       15978 :         if (pindex->nHeight == 0)
      39             :             break;
      40             :         // Exponentially larger steps back, plus the genesis block.
      41       14480 :         int nHeight = std::max(pindex->nHeight - nStep, 0);
      42       28960 :         if (Contains(pindex)) {
      43             :             // Use O(1) CChain index if possible.
      44       13544 :             pindex = (*this)[nHeight];
      45             :         } else {
      46             :             // Otherwise, use O(log n) skiplist.
      47         936 :             pindex = pindex->GetAncestor(nHeight);
      48             :         }
      49       14480 :         if (vHave.size() > 10)
      50        6260 :             nStep *= 2;
      51             :     }
      52             : 
      53        3364 :     return CBlockLocator(vHave);
      54             : }
      55             : 
      56       83043 : const CBlockIndex* CChain::FindFork(const CBlockIndex* pindex) const
      57             : {
      58       83043 :     if (pindex == nullptr)
      59             :         return nullptr;
      60       82725 :     if (pindex->nHeight > Height())
      61       41521 :         pindex = pindex->GetAncestor(Height());
      62      165508 :     while (pindex && !Contains(pindex))
      63         188 :         pindex = pindex->pprev;
      64             :     return pindex;
      65             : }
      66             : 
      67       10040 : CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime) const
      68             : {
      69       10040 :     std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), nTime,
      70      178720 :         [](CBlockIndex* pBlock, const int64_t& time) -> bool { return pBlock->GetBlockTimeMax() < time; });
      71       10040 :     return (lower == vChain.end() ? nullptr : *lower);
      72             : }
      73             : 
      74             : /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
      75     6306870 : int static inline InvertLowestOne(int n) { return n & (n - 1); }
      76             : 
      77             : /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
      78     6314050 : int static inline GetSkipHeight(int height)
      79             : {
      80     6314050 :     if (height < 2)
      81             :         return 0;
      82             :     // Determine which height to jump back to. Any number strictly lower than height is acceptable,
      83             :     // but the following expression seems to perform well in simulations (max 110 steps to go back
      84             :     // up to 2**18 blocks).
      85     6306870 :     return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
      86             : }
      87             : 
      88      808997 : const CBlockIndex* CBlockIndex::GetAncestor(int height) const
      89             : {
      90      808997 :     if (height > nHeight || height < 0) {
      91             :         return nullptr;
      92             :     }
      93             : 
      94             :     const CBlockIndex* pindexWalk = this;
      95             :     int heightWalk = nHeight;
      96     3653532 :     while (heightWalk > height) {
      97     2845113 :         int heightSkip = GetSkipHeight(heightWalk);
      98     2845113 :         int heightSkipPrev = GetSkipHeight(heightWalk - 1);
      99     2845113 :         if (heightSkip == height ||
     100     1235680 :             (heightSkip > height && !(heightSkipPrev < heightSkip - 2 && heightSkipPrev >= height))) {
     101             :             // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
     102     1507244 :             pindexWalk = pindexWalk->pskip;
     103     1507244 :             heightWalk = heightSkip;
     104             :         } else {
     105     1337869 :             assert(pindexWalk->pprev);
     106             :             pindexWalk = pindexWalk->pprev;
     107             :             heightWalk--;
     108             :         }
     109             :     }
     110             :     return pindexWalk;
     111             : }
     112             : 
     113      683357 : CBlockIndex* CBlockIndex::GetAncestor(int height)
     114             : {
     115      683357 :     return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height));
     116             : }
     117             : 
     118      623828 : void CBlockIndex::BuildSkip()
     119             : {
     120      623828 :     if (pprev)
     121     1247330 :         pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
     122      623828 : }
     123             : 
     124       56668 : CBlockIndex::CBlockIndex(const CBlock& block):
     125       56668 :         nVersion{block.nVersion},
     126             :         hashMerkleRoot{block.hashMerkleRoot},
     127             :         hashFinalSaplingRoot(block.hashFinalSaplingRoot),
     128       56668 :         nTime{block.nTime},
     129       56668 :         nBits{block.nBits},
     130      113336 :         nNonce{block.nNonce}
     131             : {
     132       56668 :     if(block.nVersion > 3 && block.nVersion < 7)
     133        5397 :         nAccumulatorCheckpoint = block.nAccumulatorCheckpoint;
     134       56668 :     if (block.IsProofOfStake())
     135        8589 :         SetProofOfStake();
     136       56668 : }
     137             : 
     138           0 : std::string CBlockIndex::ToString() const
     139             : {
     140           0 :     return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
     141           0 :         pprev, nHeight,
     142           0 :         hashMerkleRoot.ToString(),
     143           0 :         GetBlockHash().ToString());
     144             : }
     145             : 
     146      221886 : FlatFilePos CBlockIndex::GetBlockPos() const
     147             : {
     148      221886 :     FlatFilePos ret;
     149      221886 :     if (nStatus & BLOCK_HAVE_DATA) {
     150      206732 :         ret.nFile = nFile;
     151      206732 :         ret.nPos = nDataPos;
     152             :     }
     153      221886 :     return ret;
     154             : }
     155             : 
     156       84902 : FlatFilePos CBlockIndex::GetUndoPos() const
     157             : {
     158       84902 :     FlatFilePos ret;
     159       84902 :     if (nStatus & BLOCK_HAVE_UNDO) {
     160        2772 :         ret.nFile = nFile;
     161        2772 :         ret.nPos = nUndoPos;
     162             :     }
     163       84902 :     return ret;
     164             : }
     165             : 
     166           8 : CBlockHeader CBlockIndex::GetBlockHeader() const
     167             : {
     168           8 :     CBlockHeader block;
     169           8 :     block.nVersion = nVersion;
     170           8 :     if (pprev) block.hashPrevBlock = pprev->GetBlockHash();
     171           8 :     block.hashMerkleRoot = hashMerkleRoot;
     172           8 :     block.nTime = nTime;
     173           8 :     block.nBits = nBits;
     174           8 :     block.nNonce = nNonce;
     175           8 :     if (nVersion > 3 && nVersion < 7) block.nAccumulatorCheckpoint = nAccumulatorCheckpoint;
     176           8 :     if (nVersion >= 8) block.hashFinalSaplingRoot = hashFinalSaplingRoot;
     177           8 :     return block;
     178             : }
     179             : 
     180           0 : int64_t CBlockIndex::MaxFutureBlockTime() const
     181             : {
     182           0 :     return GetAdjustedTime() + Params().GetConsensus().FutureBlockTimeDrift(nHeight+1);
     183             : }
     184             : 
     185           0 : int64_t CBlockIndex::MinPastBlockTime() const
     186             : {
     187           0 :     const Consensus::Params& consensus = Params().GetConsensus();
     188             :     // Time Protocol v1: pindexPrev->MedianTimePast + 1
     189           0 :     if (!consensus.IsTimeProtocolV2(nHeight+1))
     190           0 :         return GetMedianTimePast();
     191             : 
     192             :     // on the transition from Time Protocol v1 to v2
     193             :     // pindexPrev->nTime might be in the future (up to the allowed drift)
     194             :     // so we allow the nBlockTimeProtocolV2 (PIVX v4.0) to be at most (180-14) seconds earlier than previous block
     195           0 :     if (nHeight + 1 == consensus.vUpgrades[Consensus::UPGRADE_V4_0].nActivationHeight)
     196           0 :         return GetBlockTime() - consensus.FutureBlockTimeDrift(nHeight) + consensus.FutureBlockTimeDrift(nHeight + 1);
     197             : 
     198             :     // Time Protocol v2: pindexPrev->nTime
     199           0 :     return GetBlockTime();
     200             : }
     201             : 
     202             : enum { nMedianTimeSpan = 11 };
     203             : 
     204      352189 : int64_t CBlockIndex::GetMedianTimePast() const
     205             : {
     206      352189 :     int64_t pmedian[nMedianTimeSpan];
     207      352189 :     int64_t* pbegin = &pmedian[nMedianTimeSpan];
     208      352189 :     int64_t* pend = &pmedian[nMedianTimeSpan];
     209             : 
     210      352189 :     const CBlockIndex* pindex = this;
     211     4220290 :     for (int i = 0; i < nMedianTimeSpan && pindex; i++, pindex = pindex->pprev)
     212     3868090 :         *(--pbegin) = pindex->GetBlockTime();
     213             : 
     214      352189 :     std::sort(pbegin, pend);
     215      352189 :     return pbegin[(pend - pbegin) / 2];
     216             : }
     217             : 
     218      175180 : unsigned int CBlockIndex::GetStakeEntropyBit() const
     219             : {
     220      175180 :     unsigned int nEntropyBit = ((GetBlockHash().GetCheapHash()) & 1);
     221      175180 :     return nEntropyBit;
     222             : }
     223             : 
     224       34522 : bool CBlockIndex::SetStakeEntropyBit(unsigned int nEntropyBit)
     225             : {
     226       34522 :     if (nEntropyBit > 1)
     227             :         return false;
     228       34522 :     nFlags |= (nEntropyBit ? BLOCK_STAKE_ENTROPY : 0);
     229       34522 :     return true;
     230             : }
     231             : 
     232             : // Sets V1 stake modifier (uint64_t)
     233       34522 : void CBlockIndex::SetStakeModifier(const uint64_t nStakeModifier, bool fGeneratedStakeModifier)
     234             : {
     235       34522 :     vStakeModifier.clear();
     236       34522 :     const size_t modSize = sizeof(nStakeModifier);
     237       34522 :     vStakeModifier.resize(modSize);
     238       34522 :     std::memcpy(vStakeModifier.data(), &nStakeModifier, modSize);
     239       34522 :     if (fGeneratedStakeModifier)
     240        4358 :         nFlags |= BLOCK_STAKE_MODIFIER;
     241             : 
     242       34522 : }
     243             : 
     244             : // Generates and sets new V1 stake modifier
     245       34522 : void CBlockIndex::SetNewStakeModifier()
     246             : {
     247             :     // compute stake entropy bit for stake modifier
     248       34522 :     if (!SetStakeEntropyBit(GetStakeEntropyBit()))
     249           0 :         LogPrintf("%s : SetStakeEntropyBit() failed\n", __func__);
     250       34522 :     uint64_t nStakeModifier = 0;
     251       34522 :     bool fGeneratedStakeModifier = false;
     252       34522 :     if (!ComputeNextStakeModifier(pprev, nStakeModifier, fGeneratedStakeModifier))
     253           0 :         LogPrintf("%s : ComputeNextStakeModifier() failed \n",  __func__);
     254       34522 :     return SetStakeModifier(nStakeModifier, fGeneratedStakeModifier);
     255             : }
     256             : 
     257             : // Sets V2 stake modifiers (uint256)
     258        6659 : void CBlockIndex::SetStakeModifier(const uint256& nStakeModifier)
     259             : {
     260        6659 :     vStakeModifier.clear();
     261        6659 :     vStakeModifier.insert(vStakeModifier.begin(), nStakeModifier.begin(), nStakeModifier.end());
     262        6659 : }
     263             : 
     264             : // Generates and sets new V2 stake modifier
     265        6659 : void CBlockIndex::SetNewStakeModifier(const uint256& prevoutId)
     266             : {
     267             :     // Shouldn't be called on V1 modifier's blocks (or before setting pprev)
     268        6659 :     if (!Params().GetConsensus().NetworkUpgradeActive(nHeight, Consensus::UPGRADE_V3_4)) return;
     269        6659 :     if (!pprev) throw std::runtime_error(strprintf("%s : ERROR: null pprev", __func__));
     270             : 
     271             :     // Generate Hash(prevoutId | prevModifier) - switch with genesis modifier (0) on upgrade block
     272        6659 :     CHashWriter ss(SER_GETHASH, 0);
     273        6659 :     ss << prevoutId;
     274        6659 :     ss << pprev->GetStakeModifierV2();
     275       13318 :     SetStakeModifier(ss.GetHash());
     276             : }
     277             : 
     278             : // Returns V1 stake modifier (uint64_t)
     279       34587 : uint64_t CBlockIndex::GetStakeModifierV1() const
     280             : {
     281       34587 :     if (vStakeModifier.empty() || Params().GetConsensus().NetworkUpgradeActive(nHeight, Consensus::UPGRADE_V3_4))
     282           0 :         return 0;
     283       34587 :     uint64_t nStakeModifier;
     284       34587 :     std::memcpy(&nStakeModifier, vStakeModifier.data(), vStakeModifier.size());
     285       34587 :     return nStakeModifier;
     286             : }
     287             : 
     288             : // Returns V2 stake modifier (uint256)
     289       25948 : uint256 CBlockIndex::GetStakeModifierV2() const
     290             : {
     291       25948 :     if (vStakeModifier.empty() || !Params().GetConsensus().NetworkUpgradeActive(nHeight, Consensus::UPGRADE_V3_4))
     292         219 :         return UINT256_ZERO;
     293       25729 :     uint256 nStakeModifier;
     294       25729 :     std::memcpy(nStakeModifier.begin(), vStakeModifier.data(), vStakeModifier.size());
     295       25729 :     return nStakeModifier;
     296             : }
     297             : 
     298       41476 : void CBlockIndex::SetChainSaplingValue()
     299             : {
     300             :     // Sapling, update chain value
     301       41476 :     if (pprev) {
     302       41160 :         if (pprev->nChainSaplingValue) {
     303       41160 :             nChainSaplingValue = *pprev->nChainSaplingValue + nSaplingValue;
     304             :         } else {
     305           0 :             nChainSaplingValue = nullopt;
     306             :         }
     307             :     } else {
     308         316 :         nChainSaplingValue = nSaplingValue;
     309             :     }
     310       41476 : }
     311             : 
     312             : //! Check whether this block index entry is valid up to the passed validity level.
     313      184111 : bool CBlockIndex::IsValid(enum BlockStatus nUpTo) const
     314             : {
     315      184111 :     assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
     316      184111 :     if (nStatus & BLOCK_FAILED_MASK)
     317             :         return false;
     318      183628 :     return ((nStatus & BLOCK_VALID_MASK) >= nUpTo);
     319             : }
     320             : 
     321             : //! Raise the validity level of this block index entry.
     322             : //! Returns true if the validity was changed.
     323      124038 : bool CBlockIndex::RaiseValidity(enum BlockStatus nUpTo)
     324             : {
     325      124038 :     assert(!(nUpTo & ~BLOCK_VALID_MASK)); // Only validity flags allowed.
     326      124038 :     if (nStatus & BLOCK_FAILED_MASK)
     327             :         return false;
     328      124038 :     if ((nStatus & BLOCK_VALID_MASK) < nUpTo) {
     329      124038 :         nStatus = (nStatus & ~BLOCK_VALID_MASK) | nUpTo;
     330      124038 :         return true;
     331             :     }
     332             :     return false;
     333             : }
     334             : 
     335             : /** Find the last common ancestor two blocks have.
     336             :  *  Both pa and pb must be non-nullptr. */
     337      703077 : const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb)
     338             : {
     339      703077 :     if (pa->nHeight > pb->nHeight) {
     340           0 :         pa = pa->GetAncestor(pb->nHeight);
     341      703077 :     } else if (pb->nHeight > pa->nHeight) {
     342       30699 :         pb = pb->GetAncestor(pa->nHeight);
     343             :     }
     344             : 
     345      703147 :     while (pa != pb && pa && pb) {
     346          70 :         pa = pa->pprev;
     347          70 :         pb = pb->pprev;
     348             :     }
     349             : 
     350             :     // Eventually all chain branches meet at the genesis block.
     351      703077 :     assert(pa == pb);
     352      703077 :     return pa;
     353             : }
     354             : 
     355             :