Bitcoin Core 29.99.0
P2P Digital Currency
chain.cpp
Go to the documentation of this file.
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/time.h>
9
10std::string CBlockFileInfo::ToString() const
11{
12 return strprintf("CBlockFileInfo(blocks=%u, size=%u, heights=%u...%u, time=%s...%s)", nBlocks, nSize, nHeightFirst, nHeightLast, FormatISO8601Date(nTimeFirst), FormatISO8601Date(nTimeLast));
13}
14
15std::string CBlockIndex::ToString() const
16{
17 return strprintf("CBlockIndex(pprev=%p, nHeight=%d, merkle=%s, hashBlock=%s)",
19}
20
22{
23 CBlockIndex* pindex = &block;
24 vChain.resize(pindex->nHeight + 1);
25 while (pindex && vChain[pindex->nHeight] != pindex) {
26 vChain[pindex->nHeight] = pindex;
27 pindex = pindex->pprev;
28 }
29}
30
31std::vector<uint256> LocatorEntries(const CBlockIndex* index)
32{
33 int step = 1;
34 std::vector<uint256> have;
35 if (index == nullptr) return have;
36
37 have.reserve(32);
38 while (index) {
39 have.emplace_back(index->GetBlockHash());
40 if (index->nHeight == 0) break;
41 // Exponentially larger steps back, plus the genesis block.
42 int height = std::max(index->nHeight - step, 0);
43 // Use skiplist.
44 index = index->GetAncestor(height);
45 if (have.size() > 10) step *= 2;
46 }
47 return have;
48}
49
51{
52 return CBlockLocator{LocatorEntries(index)};
53}
54
55const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const {
56 if (pindex == nullptr) {
57 return nullptr;
58 }
59 if (pindex->nHeight > Height())
60 pindex = pindex->GetAncestor(Height());
61 while (pindex && !Contains(pindex))
62 pindex = pindex->pprev;
63 return pindex;
64}
65
66CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
67{
68 std::pair<int64_t, int> blockparams = std::make_pair(nTime, height);
69 std::vector<CBlockIndex*>::const_iterator lower = std::lower_bound(vChain.begin(), vChain.end(), blockparams,
70 [](CBlockIndex* pBlock, const std::pair<int64_t, int>& blockparams) -> bool { return pBlock->GetBlockTimeMax() < blockparams.first || pBlock->nHeight < blockparams.second; });
71 return (lower == vChain.end() ? nullptr : *lower);
72}
73
75int static inline InvertLowestOne(int n) { return n & (n - 1); }
76
78int static inline GetSkipHeight(int height) {
79 if (height < 2)
80 return 0;
81
82 // Determine which height to jump back to. Any number strictly lower than height is acceptable,
83 // but the following expression seems to perform well in simulations (max 110 steps to go back
84 // up to 2**18 blocks).
85 return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
86}
87
88const CBlockIndex* CBlockIndex::GetAncestor(int height) const
89{
90 if (height > nHeight || height < 0) {
91 return nullptr;
92 }
93
94 const CBlockIndex* pindexWalk = this;
95 int heightWalk = nHeight;
96 while (heightWalk > height) {
97 int heightSkip = GetSkipHeight(heightWalk);
98 int heightSkipPrev = GetSkipHeight(heightWalk - 1);
99 if (pindexWalk->pskip != nullptr &&
100 (heightSkip == height ||
101 (heightSkip > height && !(heightSkipPrev < heightSkip - 2 &&
102 heightSkipPrev >= height)))) {
103 // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
104 pindexWalk = pindexWalk->pskip;
105 heightWalk = heightSkip;
106 } else {
107 assert(pindexWalk->pprev);
108 pindexWalk = pindexWalk->pprev;
109 heightWalk--;
110 }
111 }
112 return pindexWalk;
113}
114
116{
117 return const_cast<CBlockIndex*>(static_cast<const CBlockIndex*>(this)->GetAncestor(height));
118}
119
121{
122 if (pprev)
124}
125
127{
128 arith_uint256 bnTarget;
129 bool fNegative;
130 bool fOverflow;
131 bnTarget.SetCompact(block.nBits, &fNegative, &fOverflow);
132 if (fNegative || fOverflow || bnTarget == 0)
133 return 0;
134 // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
135 // as it's too large for an arith_uint256. However, as 2**256 is at least as large
136 // as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1,
137 // or ~bnTarget / (bnTarget+1) + 1.
138 return (~bnTarget / (bnTarget + 1)) + 1;
139}
140
141int64_t GetBlockProofEquivalentTime(const CBlockIndex& to, const CBlockIndex& from, const CBlockIndex& tip, const Consensus::Params& params)
142{
144 int sign = 1;
145 if (to.nChainWork > from.nChainWork) {
146 r = to.nChainWork - from.nChainWork;
147 } else {
148 r = from.nChainWork - to.nChainWork;
149 sign = -1;
150 }
151 r = r * arith_uint256(params.nPowTargetSpacing) / GetBlockProof(tip);
152 if (r.bits() > 63) {
153 return sign * std::numeric_limits<int64_t>::max();
154 }
155 return sign * int64_t(r.GetLow64());
156}
157
161 if (pa->nHeight > pb->nHeight) {
162 pa = pa->GetAncestor(pb->nHeight);
163 } else if (pb->nHeight > pa->nHeight) {
164 pb = pb->GetAncestor(pa->nHeight);
165 }
166
167 while (pa != pb && pa && pb) {
168 pa = pa->pprev;
169 pb = pb->pprev;
170 }
171
172 // Eventually all chain branches meet at the genesis block.
173 assert(pa == pb);
174 return pa;
175}
arith_uint256 GetBlockProof(const CBlockIndex &block)
Definition: chain.cpp:126
std::vector< uint256 > LocatorEntries(const CBlockIndex *index)
Construct a list of hash entries to put in a locator.
Definition: chain.cpp:31
CBlockLocator GetLocator(const CBlockIndex *index)
Get a locator for a block index entry.
Definition: chain.cpp:50
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:141
static int GetSkipHeight(int height)
Compute what height to jump back to with the CBlockIndex::pskip pointer.
Definition: chain.cpp:78
const CBlockIndex * LastCommonAncestor(const CBlockIndex *pa, const CBlockIndex *pb)
Find the last common ancestor two blocks have.
Definition: chain.cpp:160
static int InvertLowestOne(int n)
Turn the lowest '1' bit in the binary representation of a number into a '0'.
Definition: chain.cpp:75
uint64_t nTimeFirst
earliest time of block in file
Definition: chain.h:55
uint64_t nTimeLast
latest time of block in file
Definition: chain.h:56
std::string ToString() const
Definition: chain.cpp:10
unsigned int nHeightFirst
lowest height of block in file
Definition: chain.h:53
unsigned int nHeightLast
highest height of block in file
Definition: chain.h:54
unsigned int nBlocks
number of blocks stored in file
Definition: chain.h:50
unsigned int nSize
number of used bytes of block file
Definition: chain.h:51
The block chain is a tree shaped structure starting with the genesis block at the root,...
Definition: chain.h:141
uint256 hashMerkleRoot
Definition: chain.h:188
std::string ToString() const
Definition: chain.cpp:15
CBlockIndex * pprev
pointer to the index of the predecessor of this block
Definition: chain.h:147
void BuildSkip()
Build the skiplist pointer for this entry.
Definition: chain.cpp:120
arith_uint256 nChainWork
(memory only) Total amount of work (expected number of hashes) in the chain up to and including this ...
Definition: chain.h:165
uint256 GetBlockHash() const
Definition: chain.h:243
uint32_t nBits
Definition: chain.h:190
CBlockIndex * pskip
pointer to the index of some further predecessor of this block
Definition: chain.h:150
CBlockIndex * GetAncestor(int height)
Efficiently find an ancestor of this block.
Definition: chain.cpp:115
int nHeight
height of the entry in the chain. The genesis block has height 0
Definition: chain.h:153
void SetTip(CBlockIndex &block)
Set/initialize a chain with a given tip.
Definition: chain.cpp:21
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:462
const CBlockIndex * FindFork(const CBlockIndex *pindex) const
Find the last common block between this chain and a block index entry.
Definition: chain.cpp:55
std::vector< CBlockIndex * > vChain
Definition: chain.h:419
bool Contains(const CBlockIndex *pindex) const
Efficiently check whether a block is present in this chain.
Definition: chain.h:447
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...
std::string ToString() const
Definition: uint256.cpp:21
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.
static int sign(const secp256k1_context *ctx, struct signer_secrets *signer_secrets, struct signer *signer, const secp256k1_musig_keyagg_cache *cache, const unsigned char *msg32, unsigned char *sig64)
Definition: musig.c:106
Describes a place in the block chain to another node such that if the other node doesn't have the sam...
Definition: block.h:124
Parameters that influence chain consensus.
Definition: params.h:83
int64_t nPowTargetSpacing
Definition: params.h:119
#define strprintf
Format arguments and return the string or write to given std::ostream (see tinyformat::format doc for...
Definition: tinyformat.h:1172
std::string FormatISO8601Date(int64_t nTime)
Definition: time.cpp:88
assert(!tx.IsCoinBase())