1 // Copyright (c) 2022 The Limenka 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{632};
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{15009}; // 15009/632 = ~23.7 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 }
319