1  // Copyright (c) 2009-2010 Satoshi Nakamoto
  2  // Copyright (c) 2009-2022 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  #include <tinyformat.h>
  8  #include <util/check.h>
  9  
 10  std::string CBlockIndex::ToString() const
 11  {
 12      return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
 13                       pprev, nHeight, hashMerkleRoot.ToString(), GetBlockHash().ToString());
 14  }
 15  
 16  void CChain::SetTip(CBlockIndex& block)
 17  {
 18      CBlockIndex* pindex = &block;
 19      vChain.resize(pindex->nHeight + 1);
 20      while (pindex && vChain[pindex->nHeight] != pindex) {
 21          vChain[pindex->nHeight] = pindex;
 22          pindex = pindex->pprev;
 23      }
 24  }
 25  
 26  std::vector<uint256> LocatorEntries(const CBlockIndex* index)
 27  {
 28      int step = 1;
 29      std::vector<uint256> have;
 30      if (index == nullptr) return have;
 31  
 32      have.reserve(32);
 33      while (index) {
 34          have.emplace_back(index->GetBlockHash());
 35          if (index->nHeight == 0) break;
 36          // Exponentially larger steps back, plus the genesis block.
 37          int height = std::max(index->nHeight - step, 0);
 38          // Use skiplist.
 39          index = index->GetAncestor(height);
 40          if (have.size() > 10) step *= 2;
 41      }
 42      return have;
 43  }
 44  
 45  CBlockLocator GetLocator(const CBlockIndex* index)
 46  {
 47      return CBlockLocator{LocatorEntries(index)};
 48  }
 49  
 50  const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
 51      if (pindex == nullptr) {
 52          return nullptr;
 53      }
 54      if (pindex->nHeight > Height())
 55          pindex = pindex->GetAncestor(Height());
 56      while (pindex && !Contains(pindex))
 57          pindex = pindex->pprev;
 58      return pindex;
 59  }
 60  
 61  CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
 62  {
 63      std::pair<int64_t, int> blockparams = std::make_pair(nTime, height);
 64      std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams,
 65          [](CBlockIndex* pBlock, const std::pair<int64_t, int>& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first || pBlock->nHeight < blockparams.second; });
 66      return (lower == vChain.end() ? nullptr : *lower);
 67  }
 68  
 69  /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
 70  int static inline InvertLowestOne(int n) { return n & (n - 1); }
 71  
 72  /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
 73  int static inline GetSkipHeight(int height) {
 74      if (height < 2)
 75          return 0;
 76  
 77      // Determine which height to jump back to. Any number strictly lower than height is acceptable,
 78      // but the following expression seems to perform well in simulations (max 110 steps to go back
 79      // up to 2**18 blocks).
 80      return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
 81  }
 82  
 83  const CBlockIndex* CBlockIndex::GetAncestor(int height) const
 84  {
 85      if (height > nHeight || height < 0) {
 86          return nullptr;
 87      }
 88  
 89      const CBlockIndex* pindexWalk = this;
 90      int heightWalk = nHeight;
 91      while (heightWalk > height) {
 92          int heightSkip = GetSkipHeight(heightWalk);
 93          int heightSkipPrev = GetSkipHeight(heightWalk - 1);
 94          if (pindexWalk->pskip != nullptr &&
 95              (heightSkip == height ||
 96               (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
 97                                         heightSkipPrev >= height)))) {
 98              // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
 99              pindexWalk = pindexWalk->pskip;
100              heightWalk = heightSkip;
101          } else {
102              assert(pindexWalk->pprev);
103              pindexWalk = pindexWalk->pprev;
104              heightWalk--;
105          }
106      }
107      return pindexWalk;
108  }
109  
110  CBlockIndex* CBlockIndex::GetAncestor(int height)
111  {
112      return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height));
113  }
114  
115  void CBlockIndex::BuildSkip()
116  {
117      if (pprev)
118          pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
119  }
120  
121  arith_uint256 GetBlockProof(const CBlockIndex& block)
122  {
123      arith_uint256 bnTarget;
124      bool fNegative;
125      bool fOverflow;
126      bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
127      if (fNegative || fOverflow || bnTarget == 0)
128          return 0;
129      // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
130      // as it's too large for an arith_uint256. However, as 2**256 is at least as large
131      // as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1,
132      // or ~bnTarget / (bnTarget+1) + 1.
133      return (~bnTarget / (bnTarget + 1)) + 1;
134  }
135  
136  int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
137  {
138      arith_uint256 r;
139      int sign = 1;
140      if (to.nChainWork > from.nChainWork) {
141          r = to.nChainWork - from.nChainWork;
142      } else {
143          r = from.nChainWork - to.nChainWork;
144          sign = -1;
145      }
146      r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
147      if (r.bits() > 63) {
148          return sign * std::numeric_limits<int64_t>::max();
149      }
150      return sign * int64_t(r.GetLow64());
151  }
152  
153  /** Find the last common ancestor two blocks have.
154   *  Both pa and pb must be non-nullptr. */
155  const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) {
156      // First rewind to the last common height (the forking point cannot be past one of the two).
157      if (pa->nHeight > pb->nHeight) {
158          pa = pa->GetAncestor(pb->nHeight);
159      } else if (pb->nHeight > pa->nHeight) {
160          pb = pb->GetAncestor(pa->nHeight);
161      }
162      while (pa != pb) {
163          // Jump back until pa and pb have a common "skip" ancestor.
164          while (pa->pskip != pb->pskip) {
165              // This logic relies on the property that equal-height blocks have equal-height skip
166              // pointers.
167              Assume(pa->nHeight == pb->nHeight);
168              Assume(pa->pskip->nHeight == pb->pskip->nHeight);
169              pa = pa->pskip;
170              pb = pb->pskip;
171          }
172          // At this point, pa and pb are different, but have equal pskip. The forking point lies in
173          // between pa/pb on the one end, and pa->pskip/pb->pskip on the other end.
174          pa = pa->pprev;
175          pb = pb->pprev;
176      }
177      return pa;
178  }