txrequest.cpp
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 }