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