chain.cpp raw
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-present 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 = █
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& index) const
51 {
52 const auto* pindex{&index};
53 if (pindex->nHeight > Height())
54 pindex = pindex->GetAncestor(Height());
55 while (pindex && !Contains(*pindex))
56 pindex = pindex->pprev;
57 return pindex;
58 }
59
60 CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
61 {
62 std::pair<int64_t, int> blockparams = std::make_pair(nTime, height);
63 std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams,
64 [](CBlockIndex* pBlock, const std::pair<int64_t, int>& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first || pBlock->nHeight < blockparams.second; });
65 return (lower == vChain.end() ? nullptr : *lower);
66 }
67
68 /** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
69 int static inline InvertLowestOne(int n) { return n & (n - 1); }
70
71 /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
72 int static inline GetSkipHeight(int height) {
73 if (height < 2)
74 return 0;
75
76 // Determine which height to jump back to. Any number strictly lower than height is acceptable,
77 // but the following expression seems to perform well in simulations (max 110 steps to go back
78 // up to 2**18 blocks).
79 return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
80 }
81
82 const CBlockIndex* CBlockIndex::GetAncestor(int height) const
83 {
84 if (height > nHeight || height < 0) {
85 return nullptr;
86 }
87
88 const CBlockIndex* pindexWalk = this;
89 int heightWalk = nHeight;
90 while (heightWalk > height) {
91 int heightSkip = GetSkipHeight(heightWalk);
92 int heightSkipPrev = GetSkipHeight(heightWalk - 1);
93 if (pindexWalk->pskip != nullptr &&
94 (heightSkip == height ||
95 (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
96 heightSkipPrev >= height)))) {
97 // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
98 pindexWalk = pindexWalk->pskip;
99 heightWalk = heightSkip;
100 } else {
101 assert(pindexWalk->pprev);
102 pindexWalk = pindexWalk->pprev;
103 heightWalk--;
104 }
105 }
106 return pindexWalk;
107 }
108
109 CBlockIndex* CBlockIndex::GetAncestor(int height)
110 {
111 return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height));
112 }
113
114 void CBlockIndex::BuildSkip()
115 {
116 if (pprev)
117 pskip = pprev->GetAncestor(GetSkipHeight(nHeight));
118 }
119
120 arith_uint256 GetBitsProof(uint32_t bits)
121 {
122 arith_uint256 bnTarget;
123 bool fNegative;
124 bool fOverflow;
125 bnTarget.SetCompact(bits, &fNegative, &fOverflow);
126 if (fNegative || fOverflow || bnTarget == 0)
127 return 0;
128 // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
129 // as it's too large for an arith_uint256. However, as 2**256 is at least as large
130 // as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1,
131 // or ~bnTarget / (bnTarget+1) + 1.
132 return (~bnTarget / (bnTarget + 1)) + 1;
133 }
134
135 int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
136 {
137 arith_uint256 r;
138 int sign = 1;
139 if (to.nChainWork > from.nChainWork) {
140 r = to.nChainWork - from.nChainWork;
141 } else {
142 r = from.nChainWork - to.nChainWork;
143 sign = -1;
144 }
145 r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
146 if (r.bits() > 63) {
147 return sign * std::numeric_limits<int64_t>::max();
148 }
149 return sign * int64_t(r.GetLow64());
150 }
151
152 /** Find the last common ancestor two blocks have.
153 * Both pa and pb must be non-nullptr. */
154 const CBlockIndex* LastCommonAncestor(const CBlockIndex* pa, const CBlockIndex* pb) {
155 // First rewind to the last common height (the forking point cannot be past one of the two).
156 if (pa->nHeight > pb->nHeight) {
157 pa = pa->GetAncestor(pb->nHeight);
158 } else if (pb->nHeight > pa->nHeight) {
159 pb = pb->GetAncestor(pa->nHeight);
160 }
161 while (pa != pb) {
162 // Jump back until pa and pb have a common "skip" ancestor.
163 while (pa->pskip != pb->pskip) {
164 // This logic relies on the property that equal-height blocks have equal-height skip
165 // pointers.
166 Assume(pa->nHeight == pb->nHeight);
167 Assume(pa->pskip->nHeight == pb->pskip->nHeight);
168 pa = pa->pskip;
169 pb = pb->pskip;
170 }
171 // At this point, pa and pb are different, but have equal pskip. The forking point lies in
172 // between pa/pb on the one end, and pa->pskip/pb->pskip on the other end.
173 pa = pa->pprev;
174 pb = pb->pprev;
175 }
176 return pa;
177 }
178