Branch data Line data Source code
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 <timedata.h>
9 : : #include <util/check.h>
10 : : #include <util/vector.h>
11 : :
12 : : // The two constants below are computed using the simulation script on
13 : : // https://gist.github.com/sipa/016ae445c132cdf65a2791534dfb7ae1
14 : :
15 : : //! Store a commitment to a header every HEADER_COMMITMENT_PERIOD blocks.
16 : : constexpr size_t HEADER_COMMITMENT_PERIOD{584};
17 [ + - ]: 173 :
18 [ + - ]: 173 : //! 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{13959}; // 13959/584 = ~23.9 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 [ + - + - : 264 : HeadersSyncState::HeadersSyncState(NodeId id, const Consensus::Params& consensus_params,
+ - + - ]
27 : : const CBlockIndex* chain_start, const arith_uint256& minimum_required_work) :
28 : 132 : m_commit_offset(GetRand<unsigned>(HEADER_COMMITMENT_PERIOD)),
29 : 132 : m_id(id), m_consensus_params(consensus_params),
30 : 132 : m_chain_start(chain_start),
31 : 132 : m_minimum_required_work(minimum_required_work),
32 : 132 : m_current_chain_work(chain_start->nChainWork),
33 [ + - ]: 132 : m_last_header_received(m_chain_start->GetBlockHeader()),
34 : 132 : 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 [ + - + - : 132 : m_max_commitments = 6*(Ticks<std::chrono::seconds>(GetAdjustedTime() - NodeSeconds{std::chrono::seconds{chain_start->GetMedianTimePast()}}) + MAX_FUTURE_BLOCK_TIME) / HEADER_COMMITMENT_PERIOD;
+ - + - +
- + - ]
45 : :
46 [ + - + - : 132 : 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 : 132 : }
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 : 72 : void HeadersSyncState::Finalize()
53 : : {
54 : 72 : Assume(m_download_state != State::FINAL);
55 : 72 : ClearShrink(m_header_commitments);
56 : 72 : m_last_header_received.SetNull();
57 : 72 : ClearShrink(m_redownloaded_headers);
58 : 72 : m_redownload_buffer_last_hash.SetNull();
59 : 72 : m_redownload_buffer_first_prev_hash.SetNull();
60 : 72 : m_process_all_remaining_headers = false;
61 : 72 : m_current_height = 0;
62 : :
63 : 72 : m_download_state = State::FINAL;
64 : 72 : }
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 : 55147 : HeadersSyncState::ProcessingResult HeadersSyncState::ProcessNextHeaders(const
70 : : std::vector<CBlockHeader>& received_headers, const bool full_headers_message)
71 : : {
72 : 55147 : ProcessingResult ret;
73 : :
74 [ + - ]: 55320 : Assume(!received_headers.empty());
75 [ + - ]: 55147 : if (received_headers.empty()) return ret;
76 : :
77 [ + - ]: 55147 : Assume(m_download_state != State::FINAL);
78 [ - + ]: 55147 : if (m_download_state == State::FINAL) return ret;
79 : :
80 [ + + ]: 55147 : 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 [ + - ]: 173 : // threshold (at which point m_download_state is updated to REDOWNLOAD).
84 [ + - ]: 55073 : ret.success = ValidateAndStoreHeadersCommitments(received_headers);
85 [ + + ]: 55073 : if (ret.success) {
86 [ + + + + ]: 55035 : 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 : 55029 : ret.request_more = true;
91 : 55029 : } else {
92 [ + - ]: 6 : 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 [ + - + - : 6 : 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 : 55035 : }
99 [ - + ]: 55147 : } 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 : 74 : ret.success = true;
105 [ + + ]: 1011 : for (const auto& hdr : received_headers) {
106 [ + - + + ]: 940 : 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 : 3 : ret.success = false;
111 : 3 : break;
112 : : }
113 : : }
114 : :
115 [ + + ]: 74 : if (ret.success) {
116 : : // Return any headers that are ready for acceptance.
117 [ + - ]: 71 : 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 [ + + - + ]: 71 : if (m_redownloaded_headers.empty() && m_process_all_remaining_headers) {
122 [ + - + - : 17 : 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 [ + + ]: 71 : } else if (full_headers_message) {
124 : : // If the headers message is full, we need to request more.
125 : 46 : ret.request_more = true;
126 : 46 : } 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 [ + - + - : 8 : 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 : 71 : }
134 : 74 : }
135 : :
136 [ + + + + : 55147 : if (!(ret.success && ret.request_more)) Finalize();
+ - ]
137 : 55147 : return ret;
138 [ + - ]: 55147 : }
139 : :
140 : 55073 : bool HeadersSyncState::ValidateAndStoreHeadersCommitments(const std::vector<CBlockHeader>& headers)
141 : : {
142 : : // The caller should not give us an empty set of headers.
143 : 55073 : Assume(headers.size() > 0);
144 [ + - ]: 55073 : if (headers.size() == 0) return true;
145 : :
146 : 55073 : Assume(m_download_state == State::PRESYNC);
147 [ - + ]: 55073 : if (m_download_state != State::PRESYNC) return false;
148 : :
149 [ + + ]: 55073 : 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 [ + - # # : 19 : 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 : 19 : return false;
156 : : }
157 : :
158 : : // If it does connect, (minimally) validate and occasionally store
159 : : // commitments.
160 [ + + ]: 113689 : for (const auto& hdr : headers) {
161 [ + + ]: 58654 : if (!ValidateAndProcessSingleHeader(hdr)) {
162 : 19 : return false;
163 : : }
164 : : }
165 : :
166 [ + + ]: 55035 : if (m_current_chain_work >= m_minimum_required_work) {
167 : 32 : m_redownloaded_headers.clear();
168 : 32 : m_redownload_buffer_last_height = m_chain_start->nHeight;
169 : 32 : m_redownload_buffer_first_prev_hash = m_chain_start->GetBlockHash();
170 : 32 : m_redownload_buffer_last_hash = m_chain_start->GetBlockHash();
171 : 32 : m_redownload_chain_work = m_chain_start->nChainWork;
172 : 32 : m_download_state = State::REDOWNLOAD;
173 [ + - # # : 32 : 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 : 32 : }
175 : 55035 : return true;
176 : 55073 : }
177 : :
178 : 58654 : bool HeadersSyncState::ValidateAndProcessSingleHeader(const CBlockHeader& current)
179 : : {
180 : 58654 : Assume(m_download_state == State::PRESYNC);
181 [ - + ]: 58654 : if (m_download_state != State::PRESYNC) return false;
182 : :
183 : 58654 : 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 [ + + + + ]: 117308 : if (!PermittedDifficultyTransition(m_consensus_params, next_height,
191 : 58654 : m_last_header_received.nBits, current.nBits)) {
192 [ + - # # : 19 : LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: invalid difficulty transition at height=%i (presync phase)\n", m_id, next_height);
# # # # ]
193 : 19 : return false;
194 : : }
195 : :
196 [ + + ]: 58635 : if (next_height % HEADER_COMMITMENT_PERIOD == m_commit_offset) {
197 : : // Add a commitment.
198 : 107 : m_header_commitments.push_back(m_hasher(current.GetHash()) & 1);
199 [ - + ]: 107 : 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 [ # # # # : 0 : LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: exceeded max commitments at height=%i (presync phase)\n", m_id, next_height);
# # # # ]
205 : 0 : return false;
206 : : }
207 : 107 : }
208 : :
209 : 58635 : m_current_chain_work += GetBlockProof(CBlockIndex(current));
210 : 58635 : m_last_header_received = current;
211 : 58635 : m_current_height = next_height;
212 : :
213 : 58635 : return true;
214 : 58654 : }
215 : :
216 : 940 : bool HeadersSyncState::ValidateAndStoreRedownloadedHeader(const CBlockHeader& header)
217 : : {
218 : 940 : Assume(m_download_state == State::REDOWNLOAD);
219 [ - + ]: 940 : if (m_download_state != State::REDOWNLOAD) return false;
220 : :
221 : 940 : 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 [ + + ]: 940 : if (header.hashPrevBlock != m_redownload_buffer_last_hash) {
226 [ + - # # : 1 : LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: non-continuous headers at height=%i (redownload phase)\n", m_id, next_height);
# # # # ]
227 : 1 : return false;
228 : : }
229 : :
230 : : // Check that the difficulty adjustments are within our tolerance:
231 : 939 : uint32_t previous_nBits{0};
232 [ + + ]: 939 : if (!m_redownloaded_headers.empty()) {
233 : 908 : previous_nBits = m_redownloaded_headers.back().nBits;
234 : 908 : } else {
235 : 31 : previous_nBits = m_chain_start->nBits;
236 : : }
237 : 132 :
238 [ + + + + ]: 1878 : if (!PermittedDifficultyTransition(m_consensus_params, next_height,
239 : 939 : previous_nBits, header.nBits)) {
240 [ + - # # : 1 : LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: invalid difficulty transition at height=%i (redownload phase)\n", m_id, next_height);
# # # # ]
241 : 1 : return false;
242 : : }
243 : :
244 : : // Track work on the redownloaded chain
245 : 938 : m_redownload_chain_work += GetBlockProof(CBlockIndex(header));
246 : :
247 [ + + ]: 938 : if (m_redownload_chain_work >= m_minimum_required_work) {
248 : 21 : m_process_all_remaining_headers = true;
249 : 21 : }
250 : :
251 : 132 : // 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 [ + + + + ]: 938 : if (!m_process_all_remaining_headers && next_height % HEADER_COMMITMENT_PERIOD == m_commit_offset) {
258 [ + - ]: 8 : if (m_header_commitments.size() == 0) {
259 [ # # # # : 0 : 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 : 0 : return false;
263 : : }
264 : 8 : bool commitment = m_hasher(header.GetHash()) & 1;
265 : 8 : bool expected_commitment = m_header_commitments.front();
266 : 8 : m_header_commitments.pop_front();
267 [ + + ]: 8 : if (commitment != expected_commitment) {
268 [ + - # # : 1 : LogPrint(BCLog::NET, "Initial headers sync aborted with peer=%d: commitment mismatch at height=%i (redownload phase)\n", m_id, next_height);
# # # # ]
269 : 1 : return false;
270 : : }
271 : 7 : }
272 : 132 :
273 : : // Store this header for later processing.
274 : 937 : m_redownloaded_headers.push_back(header);
275 : 1069 : m_redownload_buffer_last_height = next_height;
276 : 937 : m_redownload_buffer_last_hash = header.GetHash();
277 : :
278 : 937 : return true;
279 : 940 : }
280 : :
281 : 71 : std::vector<CBlockHeader> HeadersSyncState::PopHeadersReadyForAcceptance()
282 : : {
283 : 71 : std::vector<CBlockHeader> ret;
284 : :
285 [ + - ]: 71 : Assume(m_download_state == State::REDOWNLOAD);
286 [ - + ]: 71 : if (m_download_state != State::REDOWNLOAD) return ret;
287 : :
288 [ - + + + ]: 1200 : while (m_redownloaded_headers.size() > REDOWNLOAD_BUFFER_SIZE ||
289 [ + + ]: 600 : (m_redownloaded_headers.size() > 0 && m_process_all_remaining_headers)) {
290 [ + - + - ]: 529 : ret.emplace_back(m_redownloaded_headers.front().GetFullHeader(m_redownload_buffer_first_prev_hash));
291 : 529 : m_redownloaded_headers.pop_front();
292 [ + - ]: 529 : m_redownload_buffer_first_prev_hash = ret.back().GetHash();
293 : : }
294 : 71 : return ret;
295 [ + - ]: 71 : }
296 : :
297 : 55075 : CBlockLocator HeadersSyncState::NextHeadersRequestLocator() const
298 : : {
299 : 55075 : Assume(m_download_state != State::FINAL);
300 [ - + ]: 55075 : if (m_download_state == State::FINAL) return {};
301 : :
302 : 55075 : auto chain_start_locator = LocatorEntries(m_chain_start);
303 : 55075 : std::vector<uint256> locator;
304 : :
305 [ + + ]: 55075 : if (m_download_state == State::PRESYNC) {
306 : : // During pre-synchronization, we continue from the last header received.
307 [ + - + - ]: 54997 : locator.push_back(m_last_header_received.GetHash());
308 : 54997 : }
309 : :
310 [ + + ]: 55075 : if (m_download_state == State::REDOWNLOAD) {
311 : : // During redownload, we will download from the last received header that we stored.
312 [ + - ]: 78 : locator.push_back(m_redownload_buffer_last_hash);
313 : 78 : }
314 : :
315 [ + - ]: 55075 : locator.insert(locator.end(), chain_start_locator.begin(), chain_start_locator.end());
316 : :
317 [ + - ]: 55075 : return CBlockLocator{std::move(locator)};
318 : 55075 : }
|
