Branch data Line data Source code
1 : : // Copyright (c) 2022-present 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 : : #ifndef BITCOIN_HEADERSSYNC_H
6 : : #define BITCOIN_HEADERSSYNC_H
7 : :
8 : : #include <arith_uint256.h>
9 : : #include <chain.h>
10 : : #include <consensus/params.h>
11 : : #include <net.h>
12 : : #include <primitives/block.h>
13 : : #include <uint256.h>
14 : : #include <util/bitdeque.h>
15 : : #include <util/hasher.h>
16 : :
17 : : #include <deque>
18 : : #include <stdexcept>
19 : : #include <vector>
20 : :
21 : : // A compressed CBlockHeader, which leaves out the prevhash
22 : : struct CompressedHeader {
23 : : // header
24 : : int32_t nVersion{0};
25 : : uint256 hashMerkleRoot;
26 : : uint32_t nTime{0};
27 : : uint32_t nBits{0};
28 : : uint32_t nNonce{0};
29 : :
30 : : CompressedHeader()
31 : : {
32 : : hashMerkleRoot.SetNull();
33 : : }
34 : :
35 : 6191 : explicit CompressedHeader(const CBlockHeader& header)
36 : 6191 : : nVersion{header.nVersion},
37 : 6191 : hashMerkleRoot{header.hashMerkleRoot},
38 : 6191 : nTime{header.nTime},
39 : 6191 : nBits{header.nBits},
40 : 5601 : nNonce{header.nNonce}
41 : : {
42 : : }
43 : :
44 : 3175 : CBlockHeader GetFullHeader(const uint256& hash_prev_block) const
45 : : {
46 : 3175 : CBlockHeader ret;
47 : 3175 : ret.nVersion = nVersion;
48 : 3175 : ret.hashPrevBlock = hash_prev_block;
49 : 3175 : ret.hashMerkleRoot = hashMerkleRoot;
50 : 3175 : ret.nTime = nTime;
51 : 3175 : ret.nBits = nBits;
52 : 3175 : ret.nNonce = nNonce;
53 [ + - ]: 3175 : return ret;
54 : : };
55 : : };
56 : :
57 : : /** HeadersSyncState:
58 : : *
59 : : * We wish to download a peer's headers chain in a DoS-resistant way.
60 : : *
61 : : * The Bitcoin protocol does not offer an easy way to determine the work on a
62 : : * peer's chain. Currently, we can query a peer's headers by using a GETHEADERS
63 : : * message, and our peer can return a set of up to 2000 headers that connect to
64 : : * something we know. If a peer's chain has more than 2000 blocks, then we need
65 : : * a way to verify that the chain actually has enough work on it to be useful to
66 : : * us -- by being above our anti-DoS minimum-chain-work threshold -- before we
67 : : * commit to storing those headers in memory. Otherwise, it would be cheap for
68 : : * an attacker to waste all our memory by serving us low-work headers
69 : : * (particularly for a new node coming online for the first time).
70 : : *
71 : : * To prevent memory-DoS with low-work headers, while still always being
72 : : * able to reorg to whatever the most-work chain is, we require that a chain
73 : : * meet a work threshold before committing it to memory. We can do this by
74 : : * downloading a peer's headers twice, whenever we are not sure that the chain
75 : : * has sufficient work:
76 : : *
77 : : * - In the first download phase, called pre-synchronization, we can calculate
78 : : * the work on the chain as we go (just by checking the nBits value on each
79 : : * header, and validating the proof-of-work).
80 : : *
81 : : * - Once we have reached a header where the cumulative chain work is
82 : : * sufficient, we switch to downloading the headers a second time, this time
83 : : * processing them fully, and possibly storing them in memory.
84 : : *
85 : : * To prevent an attacker from using (eg) the honest chain to convince us that
86 : : * they have a high-work chain, but then feeding us an alternate set of
87 : : * low-difficulty headers in the second phase, we store commitments to the
88 : : * chain we see in the first download phase that we check in the second phase,
89 : : * as follows:
90 : : *
91 : : * - In phase 1 (presync), store 1 bit (using a salted hash function) for every
92 : : * N headers that we see. With a reasonable choice of N, this uses relatively
93 : : * little memory even for a very long chain.
94 : : *
95 : : * - In phase 2 (redownload), keep a lookahead buffer and only accept headers
96 : : * from that buffer into the block index (permanent memory usage) once they
97 : : * have some target number of verified commitments on top of them. With this
98 : : * parametrization, we can achieve a given security target for potential
99 : : * permanent memory usage, while choosing N to minimize memory use during the
100 : : * sync (temporary, per-peer storage).
101 : : */
102 : :
103 : : class HeadersSyncState
104 : : {
105 : : public:
106 : : struct SystemClockError : std::runtime_error {
107 [ # # ]: 0 : using std::runtime_error::runtime_error;
108 : : };
109 : :
110 : 687 : ~HeadersSyncState() = default;
111 : :
112 : : enum class State {
113 : : /** PRESYNC means the peer has not yet demonstrated their chain has
114 : : * sufficient work and we're only building commitments to the chain they
115 : : * serve us. */
116 : : PRESYNC,
117 : : /** REDOWNLOAD means the peer has given us a high-enough-work chain,
118 : : * and now we're redownloading the headers we saw before and trying to
119 : : * accept them */
120 : : REDOWNLOAD,
121 : : /** We're done syncing with this peer and can discard any remaining state */
122 : : FINAL
123 : : };
124 : :
125 : : /** Return the current state of our download */
126 [ + + ]: 229701 : State GetState() const { return m_download_state; }
127 : :
128 : : /** Return the height reached during the PRESYNC phase */
129 : 4336 : int64_t GetPresyncHeight() const { return m_current_height; }
130 : :
131 : : /** Return the block timestamp of the last header received during the PRESYNC phase. */
132 : 4336 : uint32_t GetPresyncTime() const { return m_last_header_received.nTime; }
133 : :
134 : : /** Return the amount of work in the chain received during the PRESYNC phase. */
135 [ + - ]: 4336 : arith_uint256 GetPresyncWork() const { return m_current_chain_work; }
136 : :
137 : : /** Construct a HeadersSyncState object representing a headers sync via this
138 : : * download-twice mechanism).
139 : : *
140 : : * id: node id (for logging)
141 : : * consensus_params: parameters needed for difficulty adjustment validation
142 : : * chain_start: best known fork point that the peer's headers branch from
143 : : * minimum_required_work: amount of chain work required to accept the chain
144 : : *
145 : : * @throws SystemClockError if system clock is too far behind chain_start MTP.
146 : : */
147 : : HeadersSyncState(NodeId id, const Consensus::Params& consensus_params,
148 : : const HeadersSyncParams& params, const CBlockIndex& chain_start,
149 : : const arith_uint256& minimum_required_work);
150 : :
151 : : /** Result data structure for ProcessNextHeaders. */
152 : 230039 : struct ProcessingResult {
153 : : std::vector<CBlockHeader> pow_validated_headers;
154 : : bool success{false};
155 : : bool request_more{false};
156 : : };
157 : :
158 : : /** Process a batch of headers, once a sync via this mechanism has started
159 : : *
160 : : * received_headers: headers that were received over the network for processing.
161 : : * Assumes the caller has already verified the headers
162 : : * are continuous, and has checked that each header
163 : : * satisfies the proof-of-work target included in the
164 : : * header (but not necessarily verified that the
165 : : * proof-of-work target is correct and passes consensus
166 : : * rules).
167 : : * full_headers_message: true if the message was at max capacity,
168 : : * indicating more headers may be available
169 : : * ProcessingResult.pow_validated_headers: will be filled in with any
170 : : * headers that the caller can fully process and
171 : : * validate now (because these returned headers are
172 : : * on a chain with sufficient work)
173 : : * ProcessingResult.success: set to false if an error is detected and the sync is
174 : : * aborted; true otherwise.
175 : : * ProcessingResult.request_more: if true, the caller is suggested to call
176 : : * NextHeadersRequestLocator and send a getheaders message using it.
177 : : */
178 : : ProcessingResult ProcessNextHeaders(std::span<const CBlockHeader>
179 : : received_headers, bool full_headers_message);
180 : :
181 : : /** Issue the next GETHEADERS message to our peer.
182 : : *
183 : : * This will return a locator appropriate for the current sync object, to continue the
184 : : * synchronization phase it is in.
185 : : */
186 : : CBlockLocator NextHeadersRequestLocator() const;
187 : :
188 : : protected:
189 : : /** The (secret) offset on the heights for which to create commitments.
190 : : *
191 : : * m_header_commitments entries are created at any height h for which
192 : : * (h % m_params.commitment_period) == m_commit_offset. */
193 : : const size_t m_commit_offset;
194 : :
195 : : private:
196 : : /** Clear out all download state that might be in progress (freeing any used
197 : : * memory), and mark this object as no longer usable.
198 : : */
199 : : void Finalize();
200 : :
201 : : /**
202 : : * Only called in PRESYNC.
203 : : * Validate the work on the headers we received from the network, and
204 : : * store commitments for later. Update overall state with successfully
205 : : * processed headers.
206 : : * On failure, this invokes Finalize() and returns false.
207 : : */
208 : : bool ValidateAndStoreHeadersCommitments(std::span<const CBlockHeader> headers);
209 : :
210 : : /** In PRESYNC, process and update state for a single header */
211 : : bool ValidateAndProcessSingleHeader(const CBlockHeader& current);
212 : :
213 : : /** In REDOWNLOAD, check a header's commitment (if applicable) and add to
214 : : * buffer for later processing */
215 : : bool ValidateAndStoreRedownloadedHeader(const CBlockHeader& header);
216 : :
217 : : /** Return a set of headers that satisfy our proof-of-work threshold */
218 : : std::vector<CBlockHeader> PopHeadersReadyForAcceptance();
219 : :
220 : : private:
221 : : /** NodeId of the peer (used for log messages) **/
222 : : const NodeId m_id;
223 : :
224 : : /** We use the consensus params in our anti-DoS calculations */
225 : : const Consensus::Params& m_consensus_params;
226 : :
227 : : /** Parameters that impact memory usage for a given chain, especially when attacked. */
228 : : const HeadersSyncParams m_params;
229 : :
230 : : /** Store the last block in our block index that the peer's chain builds from */
231 : : const CBlockIndex& m_chain_start;
232 : :
233 : : /** Minimum work that we're looking for on this chain. */
234 : : const arith_uint256 m_minimum_required_work;
235 : :
236 : : /** Work that we've seen so far on the peer's chain */
237 : : arith_uint256 m_current_chain_work;
238 : :
239 : : /** m_hasher is a salted hasher for making our 1-bit commitments to headers we've seen. */
240 : : const SaltedUint256Hasher m_hasher;
241 : :
242 : : /** A queue of commitment bits, created during the 1st phase, and verified during the 2nd. */
243 : : bitdeque<> m_header_commitments;
244 : :
245 : : /** m_max_commitments is a bound we calculate on how long an honest peer's chain could be,
246 : : * given the MTP rule.
247 : : *
248 : : * Any peer giving us more headers than this will have its sync aborted. This serves as a
249 : : * memory bound on m_header_commitments. */
250 : : uint64_t m_max_commitments{0};
251 : :
252 : : /** Store the latest header received while in PRESYNC (initialized to m_chain_start) */
253 : : CBlockHeader m_last_header_received;
254 : :
255 : : /** Height of m_last_header_received */
256 : : int64_t m_current_height{0};
257 : :
258 : : /** During phase 2 (REDOWNLOAD), we buffer redownloaded headers in memory
259 : : * until enough commitments have been verified; those are stored in
260 : : * m_redownloaded_headers */
261 : : std::deque<CompressedHeader> m_redownloaded_headers;
262 : :
263 : : /** Height of last header in m_redownloaded_headers */
264 : : int64_t m_redownload_buffer_last_height{0};
265 : :
266 : : /** Hash of last header in m_redownloaded_headers (initialized to
267 : : * m_chain_start). We have to cache it because we don't have hashPrevBlock
268 : : * available in a CompressedHeader.
269 : : */
270 : : uint256 m_redownload_buffer_last_hash;
271 : :
272 : : /** The hashPrevBlock entry for the first header in m_redownloaded_headers
273 : : * We need this to reconstruct the full header when it's time for
274 : : * processing.
275 : : */
276 : : uint256 m_redownload_buffer_first_prev_hash;
277 : :
278 : : /** The accumulated work on the redownloaded chain. */
279 : : arith_uint256 m_redownload_chain_work;
280 : :
281 : : /** Set this to true once we encounter the target blockheader during phase
282 : : * 2 (REDOWNLOAD). At this point, we can process and store all remaining
283 : : * headers still in m_redownloaded_headers.
284 : : */
285 : : bool m_process_all_remaining_headers{false};
286 : :
287 : : /** Current state of our headers sync. */
288 : : State m_download_state{State::PRESYNC};
289 : : };
290 : :
291 : : #endif // BITCOIN_HEADERSSYNC_H
|
