Line data    Source code

       1             : // Copyright (c) 2009-2010 Satoshi Nakamoto
       2             : // Copyright (c) 2009-2019 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             : #include <chain.h>
       7             : 
       8             : /**
       9             :  * CChain implementation
      10             :  */
      11      470516 : void CChain::SetTip(CBlockIndex *pindex) {
      12      470516 :     if (pindex == nullptr) {
      13         600 :         vChain.clear();
      14         600 :         return;
      15             :     }
      16      469916 :     vChain.resize(pindex->nHeight + 1);
      17      976128 :     while (pindex && vChain[pindex->nHeight] != pindex) {
      18      506212 :         vChain[pindex->nHeight] = pindex;
      19      506212 :         pindex = pindex->pprev;
      20             :     }
      21      470516 : }
      22             : 
      23        3701 : CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const {
      24             :     int nStep = 1;
      25        3701 :     std::vector<uint256> vHave;
      26        3701 :     vHave.reserve(32);
      27             : 
      28        3701 :     if (!pindex)
      29        1858 :         pindex = Tip();
      30       56657 :     while (pindex) {
      31       56631 :         vHave.push_back(pindex->GetBlockHash());
      32             :         // Stop when we have added the genesis block.
      33       56631 :         if (pindex->nHeight == 0)
      34             :             break;
      35             :         // Exponentially larger steps back, plus the genesis block.
      36       52956 :         int nHeight = std::max(pindex->nHeight - nStep, 0);
      37       52956 :         if (Contains(pindex)) {
      38             :             // Use O(1) CChain index if possible.
      39       38107 :             pindex = (*this)[nHeight];
      40       38107 :         } else {
      41             :             // Otherwise, use O(log n) skiplist.
      42       14849 :             pindex = pindex->GetAncestor(nHeight);
      43             :         }
      44       52956 :         if (vHave.size() > 10)
      45       23791 :             nStep *= 2;
      46           0 :     }
      47             : 
      48        3701 :     return CBlockLocator(vHave);
      49        3701 : }
      50             : 
      51       88098 : const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
      52       88098 :     if (pindex == nullptr) {
      53         293 :         return nullptr;
      54             :     }
      55       87805 :     if (pindex->nHeight > Height())
      56       44035 :         pindex = pindex->GetAncestor(Height());
      57       93261 :     while (pindex && !Contains(pindex))
      58        5456 :         pindex = pindex->pprev;
      59       87805 :     return pindex;
      60       88098 : }
      61             : 
      62       10651 : CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
      63             : {
      64       10651 :     std::pair<int64_t, int> blockparams = std::make_pair(nTime, height);
      65       10651 :     std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams,
      66      170897 :         [](CBlockIndex* pBlock, const std::pair<int64_t, int>& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first || pBlock->nHeight < blockparams.second; });
      67       10651 :     return (lower == vChain.end() ? nullptr : *lower);
      68       10651 : }
      69             : 
      70             : /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
      71   131527351 : int static inline InvertLowestOne(int n) { return n & (n - 1); }
      72             : 
      73             : /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
      74    87711312 : int static inline GetSkipHeight(int height) {
      75    87711312 :     if (height < 2)
      76       25915 :         return 0;
      77             : 
      78             :     // Determine which height to jump back to. Any number strictly lower than height is acceptable,
      79             :     // but the following expression seems to perform well in simulations (max 110 steps to go back
      80             :     // up to 2**18 blocks).
      81    87685397 :     return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
      82    87711312 : }
      83             : 
      84    10135985 : const CBlockIndex* CBlockIndex::GetAncestor(int height) const
      85             : {
      86    10135985 :     if (height > nHeight || height < 0) {
      87     2078801 :         return nullptr;
      88             :     }
      89             : 
      90             :     const CBlockIndex* pindexWalk = this;
      91             :     int heightWalk = nHeight;
      92    49491050 :     while (heightWalk > height) {
      93    41433866 :         int heightSkip = GetSkipHeight(heightWalk);
      94    41433866 :         int heightSkipPrev = GetSkipHeight(heightWalk - 1);
      95    44610113 :         if (pindexWalk->pskip != nullptr &&
      96    41433437 :             (heightSkip == height ||
      97    38754620 :              (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
      98     3176247 :                                        heightSkipPrev >= height)))) {
      99             :             // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
     100    20289839 :             pindexWalk = pindexWalk->pskip;
     101             :             heightWalk = heightSkip;
     102    20289839 :         } else {
     103    21144027 :             assert(pindexWalk->pprev);
     104             :             pindexWalk = pindexWalk->pprev;
     105    21144027 :             heightWalk--;
     106             :         }
     107             :     }
     108             :     return pindexWalk;
     109    10135985 : }
     110             : 
     111     5039108 : CBlockIndex* CBlockIndex::GetAncestor(int height)
     112             : {
     113     5039108 :     return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height));
     114             : }
     115             : 
     116     4843906 : void CBlockIndex::BuildSkip()
     117             : {
     118     4843906 :     if (pprev)
     119     4843580 :         pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
     120     4843906 : }
     121             : 
     122      112354 : arith_uint256 GetBlockProof(const CBlockIndex& block)
     123             : {
     124      112354 :     arith_uint256 bnTarget;
     125      112354 :     bool fNegative;
     126      112354 :     bool fOverflow;
     127      112354 :     bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
     128      112354 :     if (fNegative || fOverflow || bnTarget == 0)
     129           0 :         return 0;
     130             :     // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
     131             :     // as it's too large for an arith_uint256. However, as 2**256 is at least as large
     132             :     // as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1,
     133             :     // or ~bnTarget / (bnTarget+1) + 1.
     134      112354 :     return (~bnTarget / (bnTarget + 1)) + 1;
     135      112354 : }
     136             : 
     137        1209 : int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
     138             : {
     139        1209 :     arith_uint256 r;
     140             :     int sign = 1;
     141        1209 :     if (to.nChainWork > from.nChainWork) {
     142         714 :         r = to.nChainWork - from.nChainWork;
     143         714 :     } else {
     144         495 :         r = from.nChainWork - to.nChainWork;
     145             :         sign = -1;
     146             :     }
     147        1209 :     r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
     148        1209 :     if (r.bits() > 63) {
     149           0 :         return sign * std::numeric_limits<int64_t>::max();
     150             :     }
     151        1209 :     return sign * r.GetLow64();
     152        1209 : }
     153             : 
     154             : /** Find the last common ancestor two blocks have.
     155             :  *  Both pa and pb must be non-nullptr. */
     156      130505 : const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) {
     157      130505 :     if (pa->nHeight > pb->nHeight) {
     158           0 :         pa = pa->GetAncestor(pb->nHeight);
     159      130505 :     } else if (pb->nHeight > pa->nHeight) {
     160       31179 :         pb = pb->GetAncestor(pa->nHeight);
     161       31179 :     }
     162             : 
     163      132894 :     while (pa != pb && pa && pb) {
     164        2389 :         pa = pa->pprev;
     165        2389 :         pb = pb->pprev;
     166             :     }
     167             : 
     168             :     // Eventually all chain branches meet at the genesis block.
     169      130505 :     assert(pa == pb);
     170      130505 :     return pa;
     171             : }