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 */
SetTip(CBlockIndex * pindex)11 void CChain::SetTip(CBlockIndex *pindex) {
12 if (pindex == nullptr) {
13 vChain.clear();
14 return;
15 }
16 vChain.resize(pindex->nHeight + 1);
17 while (pindex && vChain[pindex->nHeight] != pindex) {
18 vChain[pindex->nHeight] = pindex;
19 pindex = pindex->pprev;
20 }
21 }
22
GetLocator(const CBlockIndex * pindex) const23 CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const {
24 int nStep = 1;
25 std::vector<uint256> vHave;
26 vHave.reserve(32);
27
28 if (!pindex)
29 pindex = Tip();
30 while (pindex) {
31 vHave.push_back(pindex->GetBlockHash());
32 // Stop when we have added the genesis block.
33 if (pindex->nHeight == 0)
34 break;
35 // Exponentially larger steps back, plus the genesis block.
36 int nHeight = std::max(pindex->nHeight - nStep, 0);
37 if (Contains(pindex)) {
38 // Use O(1) CChain index if possible.
39 pindex = (*this)[nHeight];
40 } else {
41 // Otherwise, use O(log n) skiplist.
42 pindex = pindex->GetAncestor(nHeight);
43 }
44 if (vHave.size() > 10)
45 nStep *= 2;
46 }
47
48 return CBlockLocator(vHave);
49 }
50
FindFork(const CBlockIndex * pindex) const51 const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
52 if (pindex == nullptr) {
53 return nullptr;
54 }
55 if (pindex->nHeight > Height())
56 pindex = pindex->GetAncestor(Height());
57 while (pindex && !Contains(pindex))
58 pindex = pindex->pprev;
59 return pindex;
60 }
61
FindEarliestAtLeast(int64_t nTime,int height) const62 CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
63 {
64 std::pair<int64_t, int> blockparams = std::make_pair(nTime, height);
65 std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams,
66 [](CBlockIndex* pBlock, const std::pair<int64_t, int>& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first || pBlock->nHeight < blockparams.second; });
67 return (lower == vChain.end() ? nullptr : *lower);
68 }
69
70 /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
InvertLowestOne(int n)71 int static inline InvertLowestOne(int n) { return n & (n - 1); }
72
73 /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
GetSkipHeight(int height)74 int static inline GetSkipHeight(int height) {
75 if (height < 2)
76 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 return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
82 }
83
GetAncestor(int height) const84 const CBlockIndex* CBlockIndex::GetAncestor(int height) const
85 {
86 if (height > nHeight || height < 0) {
87 return nullptr;
88 }
89
90 const CBlockIndex* pindexWalk = this;
91 int heightWalk = nHeight;
92 while (heightWalk > height) {
93 int heightSkip = GetSkipHeight(heightWalk);
94 int heightSkipPrev = GetSkipHeight(heightWalk - 1);
95 if (pindexWalk->pskip != nullptr &&
96 (heightSkip == height ||
97 (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
98 heightSkipPrev >= height)))) {
99 // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
100 pindexWalk = pindexWalk->pskip;
101 heightWalk = heightSkip;
102 } else {
103 assert(pindexWalk->pprev);
104 pindexWalk = pindexWalk->pprev;
105 heightWalk--;
106 }
107 }
108 return pindexWalk;
109 }
110
GetAncestor(int height)111 CBlockIndex* CBlockIndex::GetAncestor(int height)
112 {
113 return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height));
114 }
115
BuildSkip()116 void CBlockIndex::BuildSkip()
117 {
118 if (pprev)
119 pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
120 }
121
GetBlockProof(const CBlockIndex & block)122 arith_uint256 GetBlockProof(const CBlockIndex& block)
123 {
124 arith_uint256 bnTarget;
125 bool fNegative;
126 bool fOverflow;
127 bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
128 if (fNegative || fOverflow || bnTarget == 0)
129 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 return (~bnTarget / (bnTarget + 1)) + 1;
135 }
136
GetBlockProofEquivalentTime(const CBlockIndex & to,const CBlockIndex & from,const CBlockIndex & tip,const Consensus::Params & params)137 int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
138 {
139 arith_uint256 r;
140 int sign = 1;
141 if (to.nChainWork > from.nChainWork) {
142 r = to.nChainWork - from.nChainWork;
143 } else {
144 r = from.nChainWork - to.nChainWork;
145 sign = -1;
146 }
147 r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
148 if (r.bits() > 63) {
149 return sign * std::numeric_limits<int64_t>::max();
150 }
151 return sign * r.GetLow64();
152 }
153
154 /** Find the last common ancestor two blocks have.
155 * Both pa and pb must be non-nullptr. */
LastCommonAncestor(const CBlockIndex * pa,const CBlockIndex * pb)156 const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) {
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
163 while (pa != pb && pa && pb) {
164 pa = pa->pprev;
165 pb = pb->pprev;
166 }
167
168 // Eventually all chain branches meet at the genesis block.
169 assert(pa == pb);
170 return pa;
171 }
172