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