Bitcoin Core  27.99.0
P2P Digital Currency
headerssync.cpp
Go to the documentation of this file.
1 // Copyright (c) 2022 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #include <headerssync.h>
6 #include <logging.h>
7 #include <pow.h>
8 #include <util/check.h>
9 #include <util/time.h>
10 #include <util/vector.h>
11 
12 // The two constants below are computed using the simulation script in
13 // contrib/devtools/headerssync-params.py.
14 
16 constexpr size_t HEADER_COMMITMENT_PERIOD{606};
17 
20 constexpr size_t REDOWNLOAD_BUFFER_SIZE{14441}; // 14441/606 = ~23.8 commitments
21 
22 // Our memory analysis assumes 48 bytes for a CompressedHeader (so we should
23 // re-calculate parameters if we compress further)
24 static_assert(sizeof(CompressedHeader) == 48);
25 
27  const CBlockIndex* chain_start, const arith_uint256& minimum_required_work) :
28  m_commit_offset(FastRandomContext().randrange<unsigned>(HEADER_COMMITMENT_PERIOD)),
29  m_id(id), m_consensus_params(consensus_params),
30  m_chain_start(chain_start),
31  m_minimum_required_work(minimum_required_work),
32  m_current_chain_work(chain_start->nChainWork),
33  m_last_header_received(m_chain_start->GetBlockHeader()),
34  m_current_height(chain_start->nHeight)
35 {
36  // Estimate the number of blocks that could possibly exist on the peer's
37  // chain *right now* using 6 blocks/second (fastest blockrate given the MTP
38  // rule) times the number of seconds from the last allowed block until
39  // today. This serves as a memory bound on how many commitments we might
40  // store from this peer, and we can safely give up syncing if the peer
41  // exceeds this bound, because it's not possible for a consensus-valid
42  // chain to be longer than this (at the current time -- in the future we
43  // could try again, if necessary, to sync a longer chain).
44  m_max_commitments = 6*(Ticks<std::chrono::seconds>(NodeClock::now() - NodeSeconds{std::chrono::seconds{chain_start->GetMedianTimePast()}}) + MAX_FUTURE_BLOCK_TIME) / HEADER_COMMITMENT_PERIOD;
45 
46  LogPrint(BCLog::NET, "Initial headers sync started with peer=%d: height=%i, max_commitments=%i, min_work=%s\n", m_id, m_current_height, m_max_commitments, m_minimum_required_work.ToString());
47 }
48 
53 {
61  m_current_height = 0;
62 
64 }
65 
70  std::vector<CBlockHeader>& received_headers, const bool full_headers_message)
71 {
73 
74  Assume(!received_headers.empty());
75  if (received_headers.empty()) return ret;
76 
78  if (m_download_state == State::FINAL) return ret;
79 
81  // During PRESYNC, we minimally validate block headers and
82  // occasionally add commitments to them, until we reach our work
83  // threshold (at which point m_download_state is updated to REDOWNLOAD).
84  ret.success = ValidateAndStoreHeadersCommitments(received_headers);
85  if (ret.success) {
86  if (full_headers_message || m_download_state == State::REDOWNLOAD) {
87  // A full headers message means the peer may have more to give us;
88  // also if we just switched to REDOWNLOAD then we need to re-request
89  // headers from the beginning.
90  ret.request_more = true;
91  } else {
93  // If we're in PRESYNC and we get a non-full headers
94  // message, then the peer's chain has ended and definitely doesn't
95  // have enough work, so we can stop our sync.
96  LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: incomplete headers message at height=%i (presync phase)\n", m_id, m_current_height);
97  }
98  }
99  } else if (m_download_state == State::REDOWNLOAD) {
100  // During REDOWNLOAD, we compare our stored commitments to what we
101  // receive, and add headers to our redownload buffer. When the buffer
102  // gets big enough (meaning that we've checked enough commitments),
103  // we'll return a batch of headers to the caller for processing.
104  ret.success = true;
105  for (const auto& hdr : received_headers) {
107  // Something went wrong -- the peer gave us an unexpected chain.
108  // We could consider looking at the reason for failure and
109  // punishing the peer, but for now just give up on sync.
110  ret.success = false;
111  break;
112  }
113  }
114 
115  if (ret.success) {
116  // Return any headers that are ready for acceptance.
117  ret.pow_validated_headers = PopHeadersReadyForAcceptance();
118 
119  // If we hit our target blockhash, then all remaining headers will be
120  // returned and we can clear any leftover internal state.
122  LogPrint(BCLog::NET, "Initial headers sync complete with peer=%d: releasing all at height=%i (redownload phase)\n", m_id, m_redownload_buffer_last_height);
123  } else if (full_headers_message) {
124  // If the headers message is full, we need to request more.
125  ret.request_more = true;
126  } else {
127  // For some reason our peer gave us a high-work chain, but is now
128  // declining to serve us that full chain again. Give up.
129  // Note that there's no more processing to be done with these
130  // headers, so we can still return success.
131  LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: incomplete headers message at height=%i (redownload phase)\n", m_id, m_redownload_buffer_last_height);
132  }
133  }
134  }
135 
136  if (!(ret.success && ret.request_more)) Finalize();
137  return ret;
138 }
139 
140 bool HeadersSyncState::ValidateAndStoreHeadersCommitments(const std::vector<CBlockHeader>& headers)
141 {
142  // The caller should not give us an empty set of headers.
143  Assume(headers.size() > 0);
144  if (headers.size() == 0) return true;
145 
147  if (m_download_state != State::PRESYNC) return false;
148 
149  if (headers[0].hashPrevBlock != m_last_header_received.GetHash()) {
150  // Somehow our peer gave us a header that doesn't connect.
151  // This might be benign -- perhaps our peer reorged away from the chain
152  // they were on. Give up on this sync for now (likely we will start a
153  // new sync with a new starting point).
154  LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: non-continuous headers at height=%i (presync phase)\n", m_id, m_current_height);
155  return false;
156  }
157 
158  // If it does connect, (minimally) validate and occasionally store
159  // commitments.
160  for (const auto& hdr : headers) {
161  if (!ValidateAndProcessSingleHeader(hdr)) {
162  return false;
163  }
164  }
165 
167  m_redownloaded_headers.clear();
173  LogPrint(BCLog::NET, "Initial headers sync transition with peer=%d: reached sufficient work at height=%i, redownloading from height=%i\n", m_id, m_current_height, m_redownload_buffer_last_height);
174  }
175  return true;
176 }
177 
179 {
181  if (m_download_state != State::PRESYNC) return false;
182 
183  int next_height = m_current_height + 1;
184 
185  // Verify that the difficulty isn't growing too fast; an adversary with
186  // limited hashing capability has a greater chance of producing a high
187  // work chain if they compress the work into as few blocks as possible,
188  // so don't let anyone give a chain that would violate the difficulty
189  // adjustment maximum.
191  m_last_header_received.nBits, current.nBits)) {
192  LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: invalid difficulty transition at height=%i (presync phase)\n", m_id, next_height);
193  return false;
194  }
195 
196  if (next_height % HEADER_COMMITMENT_PERIOD == m_commit_offset) {
197  // Add a commitment.
200  // The peer's chain is too long; give up.
201  // It's possible the chain grew since we started the sync; so
202  // potentially we could succeed in syncing the peer's chain if we
203  // try again later.
204  LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: exceeded max commitments at height=%i (presync phase)\n", m_id, next_height);
205  return false;
206  }
207  }
208 
210  m_last_header_received = current;
211  m_current_height = next_height;
212 
213  return true;
214 }
215 
217 {
219  if (m_download_state != State::REDOWNLOAD) return false;
220 
221  int64_t next_height = m_redownload_buffer_last_height + 1;
222 
223  // Ensure that we're working on a header that connects to the chain we're
224  // downloading.
226  LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: non-continuous headers at height=%i (redownload phase)\n", m_id, next_height);
227  return false;
228  }
229 
230  // Check that the difficulty adjustments are within our tolerance:
231  uint32_t previous_nBits{0};
232  if (!m_redownloaded_headers.empty()) {
233  previous_nBits = m_redownloaded_headers.back().nBits;
234  } else {
235  previous_nBits = m_chain_start->nBits;
236  }
237 
239  previous_nBits, header.nBits)) {
240  LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: invalid difficulty transition at height=%i (redownload phase)\n", m_id, next_height);
241  return false;
242  }
243 
244  // Track work on the redownloaded chain
246 
249  }
250 
251  // If we're at a header for which we previously stored a commitment, verify
252  // it is correct. Failure will result in aborting download.
253  // Also, don't check commitments once we've gotten to our target blockhash;
254  // it's possible our peer has extended its chain between our first sync and
255  // our second, and we don't want to return failure after we've seen our
256  // target blockhash just because we ran out of commitments.
258  if (m_header_commitments.size() == 0) {
259  LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: commitment overrun at height=%i (redownload phase)\n", m_id, next_height);
260  // Somehow our peer managed to feed us a different chain and
261  // we've run out of commitments.
262  return false;
263  }
264  bool commitment = m_hasher(header.GetHash()) & 1;
265  bool expected_commitment = m_header_commitments.front();
267  if (commitment != expected_commitment) {
268  LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: commitment mismatch at height=%i (redownload phase)\n", m_id, next_height);
269  return false;
270  }
271  }
272 
273  // Store this header for later processing.
274  m_redownloaded_headers.emplace_back(header);
275  m_redownload_buffer_last_height = next_height;
277 
278  return true;
279 }
280 
282 {
283  std::vector<CBlockHeader> ret;
284 
286  if (m_download_state != State::REDOWNLOAD) return ret;
287 
290  ret.emplace_back(m_redownloaded_headers.front().GetFullHeader(m_redownload_buffer_first_prev_hash));
291  m_redownloaded_headers.pop_front();
292  m_redownload_buffer_first_prev_hash = ret.back().GetHash();
293  }
294  return ret;
295 }
296 
298 {
300  if (m_download_state == State::FINAL) return {};
301 
302  auto chain_start_locator = LocatorEntries(m_chain_start);
303  std::vector<uint256> locator;
304 
306  // During pre-synchronization, we continue from the last header received.
307  locator.push_back(m_last_header_received.GetHash());
308  }
309 
311  // During redownload, we will download from the last received header that we stored.
312  locator.push_back(m_redownload_buffer_last_hash);
313  }
314 
315  locator.insert(locator.end(), chain_start_locator.begin(), chain_start_locator.end());
316 
317  return CBlockLocator{std::move(locator)};
318 }
int ret
arith_uint256 GetBlockProof(const CBlockIndex &block)
Definition: chain.cpp:131
std::vector< uint256 > LocatorEntries(const CBlockIndex *index)
Construct a list of hash entries to put in a locator.
Definition: chain.cpp:31
static constexpr int64_t MAX_FUTURE_BLOCK_TIME
Maximum amount of time that a block timestamp is allowed to exceed the current time before the block ...
Definition: chain.h:29
#define Assume(val)
Assume is the identity function.
Definition: check.h:89
Nodes collect new transactions into a block, hash them into a hash tree, and scan through nonce value...
Definition: block.h:22
uint32_t nBits
Definition: block.h:29
uint256 hashPrevBlock
Definition: block.h:26
void SetNull()
Definition: block.h:39
uint256 GetHash() const
Definition: block.cpp:11
The block chain is a tree shaped structure starting with the genesis block at the root,...
Definition: chain.h:141
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:244
int64_t GetMedianTimePast() const
Definition: chain.h:279
uint32_t nBits
Definition: chain.h:191
int nHeight
height of the entry in the chain. The genesis block has height 0
Definition: chain.h:153
Fast randomness source.
Definition: random.h:377
const SaltedTxidHasher m_hasher
m_hasher is a salted hasher for making our 1-bit commitments to headers we've seen.
Definition: headerssync.h:227
uint64_t m_max_commitments
m_max_commitments is a bound we calculate on how long an honest peer's chain could be,...
Definition: headerssync.h:237
HeadersSyncState(NodeId id, const Consensus::Params &consensus_params, const CBlockIndex *chain_start, const arith_uint256 &minimum_required_work)
Construct a HeadersSyncState object representing a headers sync via this download-twice mechanism).
Definition: headerssync.cpp:26
arith_uint256 m_redownload_chain_work
The accumulated work on the redownloaded chain.
Definition: headerssync.h:266
@ FINAL
We're done syncing with this peer and can discard any remaining state.
@ PRESYNC
PRESYNC means the peer has not yet demonstrated their chain has sufficient work and we're only buildi...
@ REDOWNLOAD
REDOWNLOAD means the peer has given us a high-enough-work chain, and now we're redownloading the head...
CBlockHeader m_last_header_received
Store the latest header received while in PRESYNC (initialized to m_chain_start)
Definition: headerssync.h:240
arith_uint256 m_current_chain_work
Work that we've seen so far on the peer's chain.
Definition: headerssync.h:224
int64_t m_current_height
Height of m_last_header_received.
Definition: headerssync.h:243
const unsigned m_commit_offset
The (secret) offset on the heights for which to create commitments.
Definition: headerssync.h:183
const arith_uint256 m_minimum_required_work
Minimum work that we're looking for on this chain.
Definition: headerssync.h:221
std::vector< CBlockHeader > PopHeadersReadyForAcceptance()
Return a set of headers that satisfy our proof-of-work threshold.
bool ValidateAndStoreHeadersCommitments(const std::vector< CBlockHeader > &headers)
Only called in PRESYNC.
const Consensus::Params & m_consensus_params
We use the consensus params in our anti-DoS calculations.
Definition: headerssync.h:215
bool ValidateAndProcessSingleHeader(const CBlockHeader &current)
In PRESYNC, process and update state for a single header.
State m_download_state
Current state of our headers sync.
Definition: headerssync.h:275
bool ValidateAndStoreRedownloadedHeader(const CBlockHeader &header)
In REDOWNLOAD, check a header's commitment (if applicable) and add to buffer for later processing.
bitdeque m_header_commitments
A queue of commitment bits, created during the 1st phase, and verified during the 2nd.
Definition: headerssync.h:230
const NodeId m_id
NodeId of the peer (used for log messages)
Definition: headerssync.h:212
int64_t m_redownload_buffer_last_height
Height of last header in m_redownloaded_headers.
Definition: headerssync.h:251
std::deque< CompressedHeader > m_redownloaded_headers
During phase 2 (REDOWNLOAD), we buffer redownloaded headers in memory until enough commitments have b...
Definition: headerssync.h:248
ProcessingResult ProcessNextHeaders(const std::vector< CBlockHeader > &received_headers, bool full_headers_message)
Process a batch of headers, once a sync via this mechanism has started.
Definition: headerssync.cpp:69
bool m_process_all_remaining_headers
Set this to true once we encounter the target blockheader during phase 2 (REDOWNLOAD).
Definition: headerssync.h:272
void Finalize()
Clear out all download state that might be in progress (freeing any used memory), and mark this objec...
Definition: headerssync.cpp:52
uint256 m_redownload_buffer_last_hash
Hash of last header in m_redownloaded_headers (initialized to m_chain_start).
Definition: headerssync.h:257
uint256 m_redownload_buffer_first_prev_hash
The hashPrevBlock entry for the first header in m_redownloaded_headers We need this to reconstruct th...
Definition: headerssync.h:263
const CBlockIndex * m_chain_start
Store the last block in our block index that the peer's chain builds from.
Definition: headerssync.h:218
CBlockLocator NextHeadersRequestLocator() const
Issue the next GETHEADERS message to our peer.
256-bit unsigned big integer.
constexpr void SetNull()
Definition: uint256.h:49
std::string ToString() const
size_type size() const noexcept
Count the number of bits in the container.
Definition: bitdeque.h:262
reference front()
Definition: bitdeque.h:332
void pop_front()
Definition: bitdeque.h:385
void push_back(bool val)
Definition: bitdeque.h:351
constexpr size_t REDOWNLOAD_BUFFER_SIZE
Only feed headers to validation once this many headers on top have been received and validated agains...
Definition: headerssync.cpp:20
constexpr size_t HEADER_COMMITMENT_PERIOD
Store one header commitment per HEADER_COMMITMENT_PERIOD blocks.
Definition: headerssync.cpp:16
#define LogPrint(category,...)
Definition: logging.h:263
unsigned int nHeight
@ NET
Definition: logging.h:41
int64_t NodeId
Definition: net.h:97
bool PermittedDifficultyTransition(const Consensus::Params &params, int64_t height, uint32_t old_nbits, uint32_t new_nbits)
Return false if the proof-of-work requirement specified by new_nbits at a given height is not possibl...
Definition: pow.cpp:76
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:74
Result data structure for ProcessNextHeaders.
Definition: headerssync.h:142
static time_point now() noexcept
Return current system time or mocked time, if set.
Definition: time.cpp:21
std::chrono::time_point< NodeClock, std::chrono::seconds > NodeSeconds
Definition: time.h:23
void ClearShrink(V &v) noexcept
Clear a vector (or std::deque) and release its allocated memory.
Definition: vector.h:56