txrequest.cpp
1 // Copyright (c) 2020-2021 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 GenTxids 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 m_tracker.ReceivedInv(peer, is_wtxid ? GenTxid::Wtxid(TXHASHES[txhash]) : GenTxid::Txid(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 247 //! list of (sequence number, txhash, is_wtxid) tuples. 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, ann2.m_is_wtxid ? GenTxid::Wtxid(TXHASHES[txhash]) : GenTxid::Txid(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 }