txrequest.cpp raw
1 // Copyright (c) 2020-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 #include <crypto/common.h>
6 #include <crypto/sha256.h>
7 #include <crypto/siphash.h>
8 #include <primitives/transaction.h>
9 #include <test/fuzz/fuzz.h>
10 #include <txrequest.h>
11
12 #include <bitset>
13 #include <cstdint>
14 #include <queue>
15 #include <vector>
16
17 namespace {
18
19 constexpr int MAX_TXHASHES = 16;
20 constexpr int MAX_PEERS = 16;
21
22 //! Randomly generated txhashes used in this test (length is MAX_TXHASHES).
23 uint256 TXHASHES[MAX_TXHASHES];
24
25 //! Precomputed random durations (positive and negative, each ~exponentially distributed).
26 std::chrono::microseconds DELAYS[256];
27
28 struct Initializer
29 {
30 Initializer()
31 {
32 for (uint8_t txhash = 0; txhash < MAX_TXHASHES; txhash += 1) {
33 CSHA256().Write(&txhash, 1).Finalize(TXHASHES[txhash].begin());
34 }
35 int i = 0;
36 // DELAYS[N] for N=0..15 is just N microseconds.
37 for (; i < 16; ++i) {
38 DELAYS[i] = std::chrono::microseconds{i};
39 }
40 // DELAYS[N] for N=16..127 has randomly-looking but roughly exponentially increasing values up to
41 // 198.416453 seconds.
42 for (; i < 128; ++i) {
43 int diff_bits = ((i - 10) * 2) / 9;
44 uint64_t diff = 1 + (CSipHasher(0, 0).Write(i).Finalize() >> (64 - diff_bits));
45 DELAYS[i] = DELAYS[i - 1] + std::chrono::microseconds{diff};
46 }
47 // DELAYS[N] for N=128..255 are negative delays with the same magnitude as N=0..127.
48 for (; i < 256; ++i) {
49 DELAYS[i] = -DELAYS[255 - i];
50 }
51 }
52 } g_initializer;
53
54 /** Tester class for TxRequestTracker
55 *
56 * It includes a naive reimplementation of its behavior, for a limited set
57 * of MAX_TXHASHES distinct txids, and MAX_PEERS peer identifiers.
58 *
59 * All of the public member functions perform the same operation on
60 * an actual TxRequestTracker and on the state of the reimplementation.
61 * The output of GetRequestable is compared with the expected value
62 * as well.
63 *
64 * Check() calls the TxRequestTracker's sanity check, plus compares the
65 * output of the constant accessors (Size(), CountLoad(), CountTracked())
66 * with expected values.
67 */
68 class Tester
69 {
70 //! TxRequestTracker object being tested.
71 TxRequestTracker m_tracker;
72
73 //! States for txid/peer combinations in the naive data structure.
74 enum class State {
75 NOTHING, //!< Absence of this txid/peer combination
76
77 // Note that this implementation does not distinguish between DELAYED/READY/BEST variants of CANDIDATE.
78 CANDIDATE,
79 REQUESTED,
80 COMPLETED,
81 };
82
83 //! Sequence numbers, incremented whenever a new CANDIDATE is added.
84 uint64_t m_current_sequence{0};
85
86 //! List of future 'events' (all inserted reqtimes/exptimes). This is used to implement AdvanceToEvent.
87 std::priority_queue<std::chrono::microseconds, std::vector<std::chrono::microseconds>,
88 std::greater<std::chrono::microseconds>> m_events;
89
90 //! Information about a txhash/peer combination.
91 struct Announcement
92 {
93 std::chrono::microseconds m_time;
94 uint64_t m_sequence;
95 State m_state{State::NOTHING};
96 bool m_preferred;
97 bool m_is_wtxid;
98 uint64_t m_priority; //!< Precomputed priority.
99 };
100
101 //! Information about all txhash/peer combination.
102 Announcement m_announcements[MAX_TXHASHES][MAX_PEERS];
103
104 //! The current time; can move forward and backward.
105 std::chrono::microseconds m_now{244466666};
106
107 //! Delete txhashes whose only announcements are COMPLETED.
108 void Cleanup(int txhash)
109 {
110 bool all_nothing = true;
111 for (int peer = 0; peer < MAX_PEERS; ++peer) {
112 const Announcement& ann = m_announcements[txhash][peer];
113 if (ann.m_state != State::NOTHING) {
114 if (ann.m_state != State::COMPLETED) return;
115 all_nothing = false;
116 }
117 }
118 if (all_nothing) return;
119 for (int peer = 0; peer < MAX_PEERS; ++peer) {
120 m_announcements[txhash][peer].m_state = State::NOTHING;
121 }
122 }
123
124 //! Find the current best peer to request from for a txhash (or -1 if none).
125 int GetSelected(int txhash) const
126 {
127 int ret = -1;
128 uint64_t ret_priority = 0;
129 for (int peer = 0; peer < MAX_PEERS; ++peer) {
130 const Announcement& ann = m_announcements[txhash][peer];
131 // Return -1 if there already is a (non-expired) in-flight request.
132 if (ann.m_state == State::REQUESTED) return -1;
133 // If it's a viable candidate, see if it has lower priority than the best one so far.
134 if (ann.m_state == State::CANDIDATE && ann.m_time <= m_now) {
135 if (ret == -1 || ann.m_priority > ret_priority) {
136 std::tie(ret, ret_priority) = std::tie(peer, ann.m_priority);
137 }
138 }
139 }
140 return ret;
141 }
142
143 public:
144 Tester() : m_tracker(true) {}
145
146 std::chrono::microseconds Now() const { return m_now; }
147
148 void AdvanceTime(std::chrono::microseconds offset)
149 {
150 m_now += offset;
151 while (!m_events.empty() && m_events.top() <= m_now) m_events.pop();
152 }
153
154 void AdvanceToEvent()
155 {
156 while (!m_events.empty() && m_events.top() <= m_now) m_events.pop();
157 if (!m_events.empty()) {
158 m_now = m_events.top();
159 m_events.pop();
160 }
161 }
162
163 void DisconnectedPeer(int peer)
164 {
165 // Apply to naive structure: all announcements for that peer are wiped.
166 for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) {
167 if (m_announcements[txhash][peer].m_state != State::NOTHING) {
168 m_announcements[txhash][peer].m_state = State::NOTHING;
169 Cleanup(txhash);
170 }
171 }
172
173 // Call TxRequestTracker's implementation.
174 m_tracker.DisconnectedPeer(peer);
175 }
176
177 void ForgetTxHash(int txhash)
178 {
179 // Apply to naive structure: all announcements for that txhash are wiped.
180 for (int peer = 0; peer < MAX_PEERS; ++peer) {
181 m_announcements[txhash][peer].m_state = State::NOTHING;
182 }
183 Cleanup(txhash);
184
185 // Call TxRequestTracker's implementation.
186 m_tracker.ForgetTxHash(TXHASHES[txhash]);
187 }
188
189 void ReceivedInv(int peer, int txhash, bool is_wtxid, bool preferred, std::chrono::microseconds reqtime)
190 {
191 // Apply to naive structure: if no announcement for txidnum/peer combination
192 // already, create a new CANDIDATE; otherwise do nothing.
193 Announcement& ann = m_announcements[txhash][peer];
194 if (ann.m_state == State::NOTHING) {
195 ann.m_preferred = preferred;
196 ann.m_state = State::CANDIDATE;
197 ann.m_time = reqtime;
198 ann.m_is_wtxid = is_wtxid;
199 ann.m_sequence = m_current_sequence++;
200 ann.m_priority = m_tracker.ComputePriority(TXHASHES[txhash], peer, ann.m_preferred);
201
202 // Add event so that AdvanceToEvent can quickly jump to the point where its reqtime passes.
203 if (reqtime > m_now) m_events.push(reqtime);
204 }
205
206 // Call TxRequestTracker's implementation.
207 auto gtxid = is_wtxid ? GenTxid{Wtxid::FromUint256(TXHASHES[txhash])} : GenTxid{Txid::FromUint256(TXHASHES[txhash])};
208 m_tracker.ReceivedInv(peer, gtxid, preferred, reqtime);
209 }
210
211 void RequestedTx(int peer, int txhash, std::chrono::microseconds exptime)
212 {
213 // Apply to naive structure: if a CANDIDATE announcement exists for peer/txhash,
214 // convert it to REQUESTED, and change any existing REQUESTED announcement for the same txhash to COMPLETED.
215 if (m_announcements[txhash][peer].m_state == State::CANDIDATE) {
216 for (int peer2 = 0; peer2 < MAX_PEERS; ++peer2) {
217 if (m_announcements[txhash][peer2].m_state == State::REQUESTED) {
218 m_announcements[txhash][peer2].m_state = State::COMPLETED;
219 }
220 }
221 m_announcements[txhash][peer].m_state = State::REQUESTED;
222 m_announcements[txhash][peer].m_time = exptime;
223 }
224
225 // Add event so that AdvanceToEvent can quickly jump to the point where its exptime passes.
226 if (exptime > m_now) m_events.push(exptime);
227
228 // Call TxRequestTracker's implementation.
229 m_tracker.RequestedTx(peer, TXHASHES[txhash], exptime);
230 }
231
232 void ReceivedResponse(int peer, int txhash)
233 {
234 // Apply to naive structure: convert anything to COMPLETED.
235 if (m_announcements[txhash][peer].m_state != State::NOTHING) {
236 m_announcements[txhash][peer].m_state = State::COMPLETED;
237 Cleanup(txhash);
238 }
239
240 // Call TxRequestTracker's implementation.
241 m_tracker.ReceivedResponse(peer, TXHASHES[txhash]);
242 }
243
244 void GetRequestable(int peer)
245 {
246 // Implement using naive structure:
247
248 //! list of (sequence number, txhash, is_wtxid) tuples.
249 std::vector<std::tuple<uint64_t, int, bool>> result;
250 std::vector<std::pair<NodeId, GenTxid>> expected_expired;
251 for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) {
252 // Mark any expired REQUESTED announcements as COMPLETED.
253 for (int peer2 = 0; peer2 < MAX_PEERS; ++peer2) {
254 Announcement& ann2 = m_announcements[txhash][peer2];
255 if (ann2.m_state == State::REQUESTED && ann2.m_time <= m_now) {
256 auto gtxid = ann2.m_is_wtxid ? GenTxid{Wtxid::FromUint256(TXHASHES[txhash])} : GenTxid{Txid::FromUint256(TXHASHES[txhash])};
257 expected_expired.emplace_back(peer2, gtxid);
258 ann2.m_state = State::COMPLETED;
259 break;
260 }
261 }
262 // And delete txids with only COMPLETED announcements left.
263 Cleanup(txhash);
264 // CANDIDATEs for which this announcement has the highest priority get returned.
265 const Announcement& ann = m_announcements[txhash][peer];
266 if (ann.m_state == State::CANDIDATE && GetSelected(txhash) == peer) {
267 result.emplace_back(ann.m_sequence, txhash, ann.m_is_wtxid);
268 }
269 }
270 // Sort the results by sequence number.
271 std::sort(result.begin(), result.end());
272 std::sort(expected_expired.begin(), expected_expired.end());
273
274 // Compare with TxRequestTracker's implementation.
275 std::vector<std::pair<NodeId, GenTxid>> expired;
276 const auto actual = m_tracker.GetRequestable(peer, m_now, &expired);
277 std::sort(expired.begin(), expired.end());
278 assert(expired == expected_expired);
279
280 m_tracker.PostGetRequestableSanityCheck(m_now);
281 assert(result.size() == actual.size());
282 for (size_t pos = 0; pos < actual.size(); ++pos) {
283 assert(TXHASHES[std::get<1>(result[pos])] == actual[pos].ToUint256());
284 assert(std::get<2>(result[pos]) == actual[pos].IsWtxid());
285 }
286 }
287
288 void Check()
289 {
290 // Compare CountTracked and CountLoad with naive structure.
291 size_t total = 0;
292 for (int peer = 0; peer < MAX_PEERS; ++peer) {
293 size_t tracked = 0;
294 size_t inflight = 0;
295 size_t candidates = 0;
296 for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) {
297 tracked += m_announcements[txhash][peer].m_state != State::NOTHING;
298 inflight += m_announcements[txhash][peer].m_state == State::REQUESTED;
299 candidates += m_announcements[txhash][peer].m_state == State::CANDIDATE;
300
301 std::bitset<MAX_PEERS> expected_announcers;
302 for (int peer = 0; peer < MAX_PEERS; ++peer) {
303 if (m_announcements[txhash][peer].m_state == State::CANDIDATE || m_announcements[txhash][peer].m_state == State::REQUESTED) {
304 expected_announcers[peer] = true;
305 }
306 }
307 std::vector<NodeId> candidate_peers;
308 m_tracker.GetCandidatePeers(TXHASHES[txhash], candidate_peers);
309 assert(expected_announcers.count() == candidate_peers.size());
310 for (const auto& peer : candidate_peers) {
311 assert(expected_announcers[peer]);
312 }
313 }
314 assert(m_tracker.Count(peer) == tracked);
315 assert(m_tracker.CountInFlight(peer) == inflight);
316 assert(m_tracker.CountCandidates(peer) == candidates);
317 total += tracked;
318 }
319 // Compare Size.
320 assert(m_tracker.Size() == total);
321
322 // Invoke internal consistency check of TxRequestTracker object.
323 m_tracker.SanityCheck();
324 }
325 };
326 } // namespace
327
328 FUZZ_TARGET(txrequest)
329 {
330 // Tester object (which encapsulates a TxRequestTracker).
331 Tester tester;
332
333 // Decode the input as a sequence of instructions with parameters
334 auto it = buffer.begin();
335 while (it != buffer.end()) {
336 int cmd = *(it++) % 11;
337 int peer, txidnum, delaynum;
338 switch (cmd) {
339 case 0: // Make time jump to the next event (m_time of CANDIDATE or REQUESTED)
340 tester.AdvanceToEvent();
341 break;
342 case 1: // Change time
343 delaynum = it == buffer.end() ? 0 : *(it++);
344 tester.AdvanceTime(DELAYS[delaynum]);
345 break;
346 case 2: // Query for requestable txs
347 peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
348 tester.GetRequestable(peer);
349 break;
350 case 3: // Peer went offline
351 peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
352 tester.DisconnectedPeer(peer);
353 break;
354 case 4: // No longer need tx
355 txidnum = it == buffer.end() ? 0 : *(it++);
356 tester.ForgetTxHash(txidnum % MAX_TXHASHES);
357 break;
358 case 5: // Received immediate preferred inv
359 case 6: // Same, but non-preferred.
360 peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
361 txidnum = it == buffer.end() ? 0 : *(it++);
362 tester.ReceivedInv(peer, txidnum % MAX_TXHASHES, (txidnum / MAX_TXHASHES) & 1, cmd & 1,
363 std::chrono::microseconds::min());
364 break;
365 case 7: // Received delayed preferred inv
366 case 8: // Same, but non-preferred.
367 peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
368 txidnum = it == buffer.end() ? 0 : *(it++);
369 delaynum = it == buffer.end() ? 0 : *(it++);
370 tester.ReceivedInv(peer, txidnum % MAX_TXHASHES, (txidnum / MAX_TXHASHES) & 1, cmd & 1,
371 tester.Now() + DELAYS[delaynum]);
372 break;
373 case 9: // Requested tx from peer
374 peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
375 txidnum = it == buffer.end() ? 0 : *(it++);
376 delaynum = it == buffer.end() ? 0 : *(it++);
377 tester.RequestedTx(peer, txidnum % MAX_TXHASHES, tester.Now() + DELAYS[delaynum]);
378 break;
379 case 10: // Received response
380 peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
381 txidnum = it == buffer.end() ? 0 : *(it++);
382 tester.ReceivedResponse(peer, txidnum % MAX_TXHASHES);
383 break;
384 default:
385 assert(false);
386 }
387 }
388 tester.Check();
389 }
390