Bitcoin ABC  0.28.12
P2P Digital Currency
chain.cpp
Go to the documentation of this file.
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2016 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 void CChain::SetTip(CBlockIndex *pindex) {
9  if (pindex == nullptr) {
10  vChain.clear();
11  return;
12  }
13 
14  vChain.resize(pindex->nHeight + 1);
15  while (pindex && vChain[pindex->nHeight] != pindex) {
16  vChain[pindex->nHeight] = pindex;
17  pindex = pindex->pprev;
18  }
19 }
20 
21 std::vector<BlockHash> LocatorEntries(const CBlockIndex *index) {
22  int step = 1;
23  std::vector<BlockHash> have;
24  if (index == nullptr) {
25  return have;
26  }
27 
28  have.reserve(32);
29  while (index) {
30  have.emplace_back(index->GetBlockHash());
31  if (index->nHeight == 0) {
32  break;
33  }
34  // Exponentially larger steps back, plus the genesis block.
35  int height = std::max(index->nHeight - step, 0);
36  // Use skiplist.
37  index = index->GetAncestor(height);
38  if (have.size() > 10) {
39  step *= 2;
40  }
41  }
42  return have;
43 }
44 
46  return CBlockLocator{std::move(LocatorEntries(index))};
47 }
48 
51 }
52 
53 const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
54  if (pindex == nullptr) {
55  return nullptr;
56  }
57  if (pindex->nHeight > Height()) {
58  pindex = pindex->GetAncestor(Height());
59  }
60  while (pindex && !Contains(pindex)) {
61  pindex = pindex->pprev;
62  }
63  return pindex;
64 }
65 
66 CBlockIndex *CChain::FindEarliestAtLeast(int64_t nTime, int height) const {
67  std::pair<int64_t, int> blockparams = std::make_pair(nTime, height);
68  std::vector<CBlockIndex *>::const_iterator lower = std::lower_bound(
69  vChain.begin(), vChain.end(), blockparams,
70  [](CBlockIndex *pBlock,
71  const std::pair<int64_t, int> &_blockparams) -> bool {
72  return pBlock->GetBlockTimeMax() < _blockparams.first ||
73  pBlock->nHeight < _blockparams.second;
74  });
75  return (lower == vChain.end() ? nullptr : *lower);
76 }
77 
79  arith_uint256 bnTarget;
80  bool fNegative;
81  bool fOverflow;
82  bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
83  if (fNegative || fOverflow || bnTarget == 0) {
84  return 0;
85  }
86  // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
87  // as it's too large for an arith_uint256. However, as 2**256 is at least as
88  // large as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) /
89  // (bnTarget+1)) + 1, or ~bnTarget / (bnTarget+1) + 1.
90  return (~bnTarget / (bnTarget + 1)) + 1;
91 }
92 
94  const CBlockIndex &from,
95  const CBlockIndex &tip,
96  const Consensus::Params &params) {
97  arith_uint256 r;
98  int sign = 1;
99  if (to.nChainWork > from.nChainWork) {
100  r = to.nChainWork - from.nChainWork;
101  } else {
102  r = from.nChainWork - to.nChainWork;
103  sign = -1;
104  }
105  r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
106  if (r.bits() > 63) {
107  return sign * std::numeric_limits<int64_t>::max();
108  }
109  return sign * int64_t(r.GetLow64());
110 }
111 
117  const CBlockIndex *pb) {
118  if (pa->nHeight > pb->nHeight) {
119  pa = pa->GetAncestor(pb->nHeight);
120  } else if (pb->nHeight > pa->nHeight) {
121  pb = pb->GetAncestor(pa->nHeight);
122  }
123 
124  while (pa != pb && pa && pb) {
125  if (pa->pskip && pb->pskip && pa->pskip != pb->pskip) {
126  pa = pa->pskip;
127  pb = pb->pskip;
128  assert(pa->nHeight == pb->nHeight);
129  } else {
130  pa = pa->pprev;
131  pb = pb->pprev;
132  }
133  }
134 
135  // Eventually all chain branches meet at the genesis block.
136  assert(pa == pb);
137  return pa;
138 }
139 
140 bool AreOnTheSameFork(const CBlockIndex *pa, const CBlockIndex *pb) {
141  if (pa->nHeight > pb->nHeight) {
142  pa = pa->GetAncestor(pb->nHeight);
143  } else if (pb->nHeight > pa->nHeight) {
144  pb = pb->GetAncestor(pa->nHeight);
145  }
146  return pa == pb;
147 }
std::vector< BlockHash > LocatorEntries(const CBlockIndex *index)
Construct a list of hash entries to put in a locator.
Definition: chain.cpp:21
arith_uint256 GetBlockProof(const CBlockIndex &block)
Definition: chain.cpp:78
CBlockLocator GetLocator(const CBlockIndex *index)
Get a locator for a block index entry.
Definition: chain.cpp:45
const CBlockIndex * LastCommonAncestor(const CBlockIndex *pa, const CBlockIndex *pb)
Find the last common ancestor two blocks have.
Definition: chain.cpp:116
int64_t GetBlockProofEquivalentTime(const CBlockIndex &to, const CBlockIndex &from, const CBlockIndex &tip, const Consensus::Params &params)
Return the time it would take to redo the work difference between from and to, assuming the current h...
Definition: chain.cpp:93
bool AreOnTheSameFork(const CBlockIndex *pa, const CBlockIndex *pb)
Check if two block index are on the same fork.
Definition: chain.cpp:140
The block chain is a tree shaped structure starting with the genesis block at the root,...
Definition: blockindex.h:26
CBlockIndex * pprev
pointer to the index of the predecessor of this block
Definition: blockindex.h:33
arith_uint256 nChainWork
(memory only) Total amount of work (expected number of hashes) in the chain up to and including this ...
Definition: blockindex.h:52
uint32_t nBits
Definition: blockindex.h:94
CBlockIndex * pskip
pointer to the index of some further predecessor of this block
Definition: blockindex.h:36
CBlockIndex * GetAncestor(int height)
Efficiently find an ancestor of this block.
Definition: blockindex.cpp:71
BlockHash GetBlockHash() const
Definition: blockindex.h:147
int nHeight
height of the entry in the chain. The genesis block has height 0
Definition: blockindex.h:39
CBlockIndex * Tip() const
Returns the index entry for the tip of this chain, or nullptr if none.
Definition: chain.h:156
CBlockIndex * FindEarliestAtLeast(int64_t nTime, int height) const
Find the earliest block with timestamp equal or greater than the given time and height equal or great...
Definition: chain.cpp:66
int Height() const
Return the maximal height in the chain.
Definition: chain.h:192
const CBlockIndex * FindFork(const CBlockIndex *pindex) const
Find the last common block between this chain and a block index entry.
Definition: chain.cpp:53
void SetTip(CBlockIndex *pindex)
Set/initialize a chain with a given tip.
Definition: chain.cpp:8
std::vector< CBlockIndex * > vChain
Definition: chain.h:142
bool Contains(const CBlockIndex *pindex) const
Efficiently check whether a block is present in this chain.
Definition: chain.h:172
CBlockLocator GetLocator() const
Return a CBlockLocator that refers to the tip of this chain.
Definition: chain.cpp:49
256-bit unsigned big integer.
arith_uint256 & SetCompact(uint32_t nCompact, bool *pfNegative=nullptr, bool *pfOverflow=nullptr)
The "compact" format is a representation of a whole number N using an unsigned 32bit number similar t...
uint64_t GetLow64() const
unsigned int bits() const
Returns the position of the highest bit set plus one, or zero if the value is zero.
Describes a place in the block chain to another node such that if the other node doesn't have the sam...
Definition: block.h:105
Parameters that influence chain consensus.
Definition: params.h:34
int64_t nPowTargetSpacing
Definition: params.h:78
assert(!tx.IsCoinBase())