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  
 15  //! Store one header commitment per HEADER_COMMITMENT_PERIOD blocks.
 16  constexpr size_t HEADER_COMMITMENT_PERIOD{624};
 17  
 18  //! Only feed headers to validation once this many headers on top have been
 19  //! received and validated against commitments.
 20  constexpr size_t REDOWNLOAD_BUFFER_SIZE{14827}; // 14827/624 = ~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  
 26  HeadersSyncState::HeadersSyncState(NodeId id, const Consensus::Params& consensus_params,
 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      LogDebug(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  
 49  /** Free any memory in use, and mark this object as no longer usable. This is
 50   * required to guarantee that we won't reuse this object with the same
 51   * SaltedTxidHasher for another sync. */
 52  void HeadersSyncState::Finalize()
 53  {
 54      Assume(m_download_state != State::FINAL);
 55      ClearShrink(m_header_commitments);
 56      m_last_header_received.SetNull();
 57      ClearShrink(m_redownloaded_headers);
 58      m_redownload_buffer_last_hash.SetNull();
 59      m_redownload_buffer_first_prev_hash.SetNull();
 60      m_process_all_remaining_headers = false;
 61      m_current_height = 0;
 62  
 63      m_download_state = State::FINAL;
 64  }
 65  
 66  /** Process the next batch of headers received from our peer.
 67   *  Validate and store commitments, and compare total chainwork to our target to
 68   *  see if we can switch to REDOWNLOAD mode.  */
 69  HeadersSyncState::ProcessingResult HeadersSyncState::ProcessNextHeaders(const
 70          std::vector<CBlockHeader>& received_headers, const bool full_headers_message)
 71  {
 72      ProcessingResult ret;
 73  
 74      Assume(!received_headers.empty());
 75      if (received_headers.empty()) return ret;
 76  
 77      Assume(m_download_state != State::FINAL);
 78      if (m_download_state == State::FINAL) return ret;
 79  
 80      if (m_download_state == State::PRESYNC) {
 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 {
 92                  Assume(m_download_state == State::PRESYNC);
 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                  LogDebug(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) {
106              if (!ValidateAndStoreRedownloadedHeader(hdr)) {
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.
121              if (m_redownloaded_headers.empty() && m_process_all_remaining_headers) {
122                  LogDebug(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                  LogDebug(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  
146      Assume(m_download_state == State::PRESYNC);
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          LogDebug(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  
166      if (m_current_chain_work >= m_minimum_required_work) {
167          m_redownloaded_headers.clear();
168          m_redownload_buffer_last_height = m_chain_start->nHeight;
169          m_redownload_buffer_first_prev_hash = m_chain_start->GetBlockHash();
170          m_redownload_buffer_last_hash = m_chain_start->GetBlockHash();
171          m_redownload_chain_work = m_chain_start->nChainWork;
172          m_download_state = State::REDOWNLOAD;
173          LogDebug(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  
178  bool HeadersSyncState::ValidateAndProcessSingleHeader(const CBlockHeader& current)
179  {
180      Assume(m_download_state == State::PRESYNC);
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.
190      if (!PermittedDifficultyTransition(m_consensus_params, next_height,
191                  m_last_header_received.nBits, current.nBits)) {
192          LogDebug(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.
198          m_header_commitments.push_back(m_hasher(current.GetHash()) & 1);
199          if (m_header_commitments.size() > m_max_commitments) {
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              LogDebug(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  
209      m_current_chain_work += GetBlockProof(CBlockIndex(current));
210      m_last_header_received = current;
211      m_current_height = next_height;
212  
213      return true;
214  }
215  
216  bool HeadersSyncState::ValidateAndStoreRedownloadedHeader(const CBlockHeader& header)
217  {
218      Assume(m_download_state == State::REDOWNLOAD);
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.
225      if (header.hashPrevBlock != m_redownload_buffer_last_hash) {
226          LogDebug(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  
238      if (!PermittedDifficultyTransition(m_consensus_params, next_height,
239                  previous_nBits, header.nBits)) {
240          LogDebug(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
245      m_redownload_chain_work += GetBlockProof(CBlockIndex(header));
246  
247      if (m_redownload_chain_work >= m_minimum_required_work) {
248          m_process_all_remaining_headers = true;
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.
257      if (!m_process_all_remaining_headers && next_height % HEADER_COMMITMENT_PERIOD == m_commit_offset) {
258          if (m_header_commitments.size() == 0) {
259              LogDebug(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();
266          m_header_commitments.pop_front();
267          if (commitment != expected_commitment) {
268              LogDebug(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;
276      m_redownload_buffer_last_hash = header.GetHash();
277  
278      return true;
279  }
280  
281  std::vector<CBlockHeader> HeadersSyncState::PopHeadersReadyForAcceptance()
282  {
283      std::vector<CBlockHeader> ret;
284  
285      Assume(m_download_state == State::REDOWNLOAD);
286      if (m_download_state != State::REDOWNLOAD) return ret;
287  
288      while (m_redownloaded_headers.size() > REDOWNLOAD_BUFFER_SIZE ||
289              (m_redownloaded_headers.size() > 0 && m_process_all_remaining_headers)) {
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  
297  CBlockLocator HeadersSyncState::NextHeadersRequestLocator() const
298  {
299      Assume(m_download_state != State::FINAL);
300      if (m_download_state == State::FINAL) return {};
301  
302      auto chain_start_locator = LocatorEntries(m_chain_start);
303      std::vector<uint256> locator;
304  
305      if (m_download_state == State::PRESYNC) {
306          // During pre-synchronization, we continue from the last header received.
307          locator.push_back(m_last_header_received.GetHash());
308      }
309  
310      if (m_download_state == State::REDOWNLOAD) {
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  }