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