Bitcoin Core  22.99.0
P2P Digital Currency
txrequest.cpp
Go to the documentation of this file.
1 // Copyright (c) 2020 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>
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 
23 uint256 TXHASHES[MAX_TXHASHES];
24 
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 
68 class Tester
69 {
71  TxRequestTracker m_tracker;
72 
74  enum class State {
75  NOTHING,
76 
77  // Note that this implementation does not distinguish between DELAYED/READY/BEST variants of CANDIDATE.
78  CANDIDATE,
79  REQUESTED,
80  COMPLETED,
81  };
82 
84  uint64_t m_current_sequence{0};
85 
87  std::priority_queue<std::chrono::microseconds, std::vector<std::chrono::microseconds>,
88  std::greater<std::chrono::microseconds>> m_events;
89 
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;
99  };
100 
102  Announcement m_announcements[MAX_TXHASHES][MAX_PEERS];
103 
105  std::chrono::microseconds m_now{244466666};
106 
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 
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  m_tracker.ReceivedInv(peer, GenTxid{is_wtxid, TXHASHES[txhash]}, preferred, reqtime);
208  }
209 
210  void RequestedTx(int peer, int txhash, std::chrono::microseconds exptime)
211  {
212  // Apply to naive structure: if a CANDIDATE announcement exists for peer/txhash,
213  // convert it to REQUESTED, and change any existing REQUESTED announcement for the same txhash to COMPLETED.
214  if (m_announcements[txhash][peer].m_state == State::CANDIDATE) {
215  for (int peer2 = 0; peer2 < MAX_PEERS; ++peer2) {
216  if (m_announcements[txhash][peer2].m_state == State::REQUESTED) {
217  m_announcements[txhash][peer2].m_state = State::COMPLETED;
218  }
219  }
220  m_announcements[txhash][peer].m_state = State::REQUESTED;
221  m_announcements[txhash][peer].m_time = exptime;
222  }
223 
224  // Add event so that AdvanceToEvent can quickly jump to the point where its exptime passes.
225  if (exptime > m_now) m_events.push(exptime);
226 
227  // Call TxRequestTracker's implementation.
228  m_tracker.RequestedTx(peer, TXHASHES[txhash], exptime);
229  }
230 
231  void ReceivedResponse(int peer, int txhash)
232  {
233  // Apply to naive structure: convert anything to COMPLETED.
234  if (m_announcements[txhash][peer].m_state != State::NOTHING) {
235  m_announcements[txhash][peer].m_state = State::COMPLETED;
236  Cleanup(txhash);
237  }
238 
239  // Call TxRequestTracker's implementation.
240  m_tracker.ReceivedResponse(peer, TXHASHES[txhash]);
241  }
242 
243  void GetRequestable(int peer)
244  {
245  // Implement using naive structure:
246 
248  std::vector<std::tuple<uint64_t, int, bool>> result;
249  std::vector<std::pair<NodeId, GenTxid>> expected_expired;
250  for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) {
251  // Mark any expired REQUESTED announcements as COMPLETED.
252  for (int peer2 = 0; peer2 < MAX_PEERS; ++peer2) {
253  Announcement& ann2 = m_announcements[txhash][peer2];
254  if (ann2.m_state == State::REQUESTED && ann2.m_time <= m_now) {
255  expected_expired.emplace_back(peer2, GenTxid{ann2.m_is_wtxid, TXHASHES[txhash]});
256  ann2.m_state = State::COMPLETED;
257  break;
258  }
259  }
260  // And delete txids with only COMPLETED announcements left.
261  Cleanup(txhash);
262  // CANDIDATEs for which this announcement has the highest priority get returned.
263  const Announcement& ann = m_announcements[txhash][peer];
264  if (ann.m_state == State::CANDIDATE && GetSelected(txhash) == peer) {
265  result.emplace_back(ann.m_sequence, txhash, ann.m_is_wtxid);
266  }
267  }
268  // Sort the results by sequence number.
269  std::sort(result.begin(), result.end());
270  std::sort(expected_expired.begin(), expected_expired.end());
271 
272  // Compare with TxRequestTracker's implementation.
273  std::vector<std::pair<NodeId, GenTxid>> expired;
274  const auto actual = m_tracker.GetRequestable(peer, m_now, &expired);
275  std::sort(expired.begin(), expired.end());
276  assert(expired == expected_expired);
277 
278  m_tracker.PostGetRequestableSanityCheck(m_now);
279  assert(result.size() == actual.size());
280  for (size_t pos = 0; pos < actual.size(); ++pos) {
281  assert(TXHASHES[std::get<1>(result[pos])] == actual[pos].GetHash());
282  assert(std::get<2>(result[pos]) == actual[pos].IsWtxid());
283  }
284  }
285 
286  void Check()
287  {
288  // Compare CountTracked and CountLoad with naive structure.
289  size_t total = 0;
290  for (int peer = 0; peer < MAX_PEERS; ++peer) {
291  size_t tracked = 0;
292  size_t inflight = 0;
293  size_t candidates = 0;
294  for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) {
295  tracked += m_announcements[txhash][peer].m_state != State::NOTHING;
296  inflight += m_announcements[txhash][peer].m_state == State::REQUESTED;
297  candidates += m_announcements[txhash][peer].m_state == State::CANDIDATE;
298  }
299  assert(m_tracker.Count(peer) == tracked);
300  assert(m_tracker.CountInFlight(peer) == inflight);
301  assert(m_tracker.CountCandidates(peer) == candidates);
302  total += tracked;
303  }
304  // Compare Size.
305  assert(m_tracker.Size() == total);
306 
307  // Invoke internal consistency check of TxRequestTracker object.
308  m_tracker.SanityCheck();
309  }
310 };
311 } // namespace
312 
313 FUZZ_TARGET(txrequest)
314 {
315  // Tester object (which encapsulates a TxRequestTracker).
316  Tester tester;
317 
318  // Decode the input as a sequence of instructions with parameters
319  auto it = buffer.begin();
320  while (it != buffer.end()) {
321  int cmd = *(it++) % 11;
322  int peer, txidnum, delaynum;
323  switch (cmd) {
324  case 0: // Make time jump to the next event (m_time of CANDIDATE or REQUESTED)
325  tester.AdvanceToEvent();
326  break;
327  case 1: // Change time
328  delaynum = it == buffer.end() ? 0 : *(it++);
329  tester.AdvanceTime(DELAYS[delaynum]);
330  break;
331  case 2: // Query for requestable txs
332  peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
333  tester.GetRequestable(peer);
334  break;
335  case 3: // Peer went offline
336  peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
337  tester.DisconnectedPeer(peer);
338  break;
339  case 4: // No longer need tx
340  txidnum = it == buffer.end() ? 0 : *(it++);
341  tester.ForgetTxHash(txidnum % MAX_TXHASHES);
342  break;
343  case 5: // Received immediate preferred inv
344  case 6: // Same, but non-preferred.
345  peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
346  txidnum = it == buffer.end() ? 0 : *(it++);
347  tester.ReceivedInv(peer, txidnum % MAX_TXHASHES, (txidnum / MAX_TXHASHES) & 1, cmd & 1,
348  std::chrono::microseconds::min());
349  break;
350  case 7: // Received delayed preferred inv
351  case 8: // Same, but non-preferred.
352  peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
353  txidnum = it == buffer.end() ? 0 : *(it++);
354  delaynum = it == buffer.end() ? 0 : *(it++);
355  tester.ReceivedInv(peer, txidnum % MAX_TXHASHES, (txidnum / MAX_TXHASHES) & 1, cmd & 1,
356  tester.Now() + DELAYS[delaynum]);
357  break;
358  case 9: // Requested tx from peer
359  peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
360  txidnum = it == buffer.end() ? 0 : *(it++);
361  delaynum = it == buffer.end() ? 0 : *(it++);
362  tester.RequestedTx(peer, txidnum % MAX_TXHASHES, tester.Now() + DELAYS[delaynum]);
363  break;
364  case 10: // Received response
365  peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
366  txidnum = it == buffer.end() ? 0 : *(it++);
367  tester.ReceivedResponse(peer, txidnum % MAX_TXHASHES);
368  break;
369  default:
370  assert(false);
371  }
372  }
373  tester.Check();
374 }
TxRequestTracker::CountInFlight
size_t CountInFlight(NodeId peer) const
Count how many REQUESTED announcements a peer has.
Definition: txrequest.cpp:719
assert
assert(!tx.IsCoinBase())
CSHA256::Write
CSHA256 & Write(const unsigned char *data, size_t len)
Definition: sha256.cpp:637
GenTxid
A generic txid reference (txid or wtxid).
Definition: transaction.h:390
transaction.h
TxRequestTracker::Size
size_t Size() const
Count how many announcements are being tracked in total across all peers and transaction hashes.
Definition: txrequest.cpp:722
txrequest.h
TxRequestTracker::Count
size_t Count(NodeId peer) const
Count how many announcements a peer has (REQUESTED, CANDIDATE, and COMPLETED combined).
Definition: txrequest.cpp:721
common.h
CSipHasher
SipHash-2-4.
Definition: siphash.h:13
siphash.h
TxRequestTracker::ForgetTxHash
void ForgetTxHash(const uint256 &txhash)
Deletes all announcements for a given txhash (both txid and wtxid ones).
Definition: txrequest.cpp:717
CSipHasher::Finalize
uint64_t Finalize() const
Compute the 64-bit SipHash-2-4 of the data written so far.
Definition: siphash.cpp:76
TxRequestTracker::CountCandidates
size_t CountCandidates(NodeId peer) const
Count how many CANDIDATE announcements a peer has.
Definition: txrequest.cpp:720
TxRequestTracker::RequestedTx
void RequestedTx(NodeId peer, const uint256 &txhash, std::chrono::microseconds expiry)
Marks a transaction as requested, with a specified expiry.
Definition: txrequest.cpp:736
uint256
256-bit opaque blob.
Definition: uint256.h:124
CSHA256::Finalize
void Finalize(unsigned char hash[OUTPUT_SIZE])
Definition: sha256.cpp:663
FUZZ_TARGET
FUZZ_TARGET(txrequest)
Definition: txrequest.cpp:313
TxRequestTracker::GetRequestable
std::vector< GenTxid > GetRequestable(NodeId peer, std::chrono::microseconds now, std::vector< std::pair< NodeId, GenTxid >> *expired=nullptr)
Find the txids to request now from peer.
Definition: txrequest.cpp:746
TxRequestTracker
Data structure to keep track of, and schedule, transaction downloads from peers.
Definition: txrequest.h:96
sha256.h
TxRequestTracker::PostGetRequestableSanityCheck
void PostGetRequestableSanityCheck(std::chrono::microseconds now) const
Run a time-dependent internal consistency check (testing only).
Definition: txrequest.cpp:725
fuzz.h
TxRequestTracker::SanityCheck
void SanityCheck() const
Run internal consistency check (testing only).
Definition: txrequest.cpp:723
CSHA256
A hasher class for SHA-256.
Definition: sha256.h:13
TxRequestTracker::ReceivedInv
void ReceivedInv(NodeId peer, const GenTxid &gtxid, bool preferred, std::chrono::microseconds reqtime)
Adds a new CANDIDATE announcement.
Definition: txrequest.cpp:730
TxRequestTracker::DisconnectedPeer
void DisconnectedPeer(NodeId peer)
Deletes all announcements for a given peer.
Definition: txrequest.cpp:718
TxRequestTracker::ReceivedResponse
void ReceivedResponse(NodeId peer, const uint256 &txhash)
Converts a CANDIDATE or REQUESTED announcement to a COMPLETED one.
Definition: txrequest.cpp:741
TxRequestTracker::ComputePriority
uint64_t ComputePriority(const uint256 &txhash, NodeId peer, bool preferred) const
Access to the internal priority computation (testing only)
Definition: txrequest.cpp:752
CSipHasher::Write
CSipHasher & Write(uint64_t data)
Hash a 64-bit integer worth of data It is treated as if this was the little-endian interpretation of ...
Definition: siphash.cpp:28