txgraph.cpp
1 // Copyright (c) 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 <cluster_linearize.h> 6 #include <test/fuzz/FuzzedDataProvider.h> 7 #include <test/fuzz/fuzz.h> 8 #include <test/util/cluster_linearize.h> 9 #include <test/util/random.h> 10 #include <txgraph.h> 11 #include <util/bitset.h> 12 #include <util/feefrac.h> 13 14 #include <algorithm> 15 #include <cstdint> 16 #include <iterator> 17 #include <map> 18 #include <memory> 19 #include <ranges> 20 #include <set> 21 #include <utility> 22 23 using namespace cluster_linearize; 24 25 namespace { 26 27 struct SimTxObject : public TxGraph::Ref 28 { 29 // Use random uint64_t as txids for this simulation (0 = empty object). 30 const uint64_t m_txid{0}; 31 SimTxObject() noexcept = default; 32 explicit SimTxObject(uint64_t txid) noexcept : m_txid(txid) {} 33 }; 34 35 /** Data type representing a naive simulated TxGraph, keeping all transactions (even from 36 * disconnected components) in a single DepGraph. Unlike the real TxGraph, this only models 37 * a single graph, and multiple instances are used to simulate main/staging. */ 38 struct SimTxGraph 39 { 40 /** Maximum number of transactions to support simultaneously. Set this higher than txgraph's 41 * cluster count, so we can exercise situations with more transactions than fit in one 42 * cluster. */ 43 static constexpr unsigned MAX_TRANSACTIONS = MAX_CLUSTER_COUNT_LIMIT * 2; 44 /** Set type to use in the simulation. */ 45 using SetType = BitSet<MAX_TRANSACTIONS>; 46 /** Data type for representing positions within SimTxGraph::graph. */ 47 using Pos = DepGraphIndex; 48 /** Constant to mean "missing in this graph". */ 49 static constexpr auto MISSING = Pos(-1); 50 51 /** The dependency graph (for all transactions in the simulation, regardless of 52 * connectivity/clustering). */ 53 DepGraph<SetType> graph; 54 /** For each position in graph, which SimTxObject it corresponds with (if any). Use shared_ptr 55 * so that a SimTxGraph can be copied to create a staging one, while sharing Refs with 56 * the main graph. */ 57 std::array<std::shared_ptr<SimTxObject>, MAX_TRANSACTIONS> simmap; 58 /** For each TxGraph::Ref in graph, the position it corresponds with. */ 59 std::map<const TxGraph::Ref*, Pos> simrevmap; 60 /** The set of SimTxObject entries that have been removed, but not yet destroyed. */ 61 std::vector<std::shared_ptr<SimTxObject>> removed; 62 /** Whether the graph is oversized (true = yes, false = no, std::nullopt = unknown). */ 63 std::optional<bool> oversized; 64 /** The configured maximum number of transactions per cluster. */ 65 DepGraphIndex max_cluster_count; 66 /** Which transactions have been modified in the graph since creation, either directly or by 67 * being in a cluster which includes modifications. Only relevant for the staging graph. */ 68 SetType modified; 69 /** The configured maximum total size of transactions per cluster. */ 70 uint64_t max_cluster_size; 71 /** Whether the corresponding real graph is known to be optimally linearized. */ 72 bool real_is_optimal{false}; 73 74 /** Construct a new SimTxGraph with the specified maximum cluster count and size. */ 75 explicit SimTxGraph(DepGraphIndex cluster_count, uint64_t cluster_size) : 76 max_cluster_count(cluster_count), max_cluster_size(cluster_size) {} 77 78 // Permit copying and moving. 79 SimTxGraph(const SimTxGraph&) noexcept = default; 80 SimTxGraph& operator=(const SimTxGraph&) noexcept = default; 81 SimTxGraph(SimTxGraph&&) noexcept = default; 82 SimTxGraph& operator=(SimTxGraph&&) noexcept = default; 83 84 /** Get the connected components within this simulated transaction graph. */ 85 std::vector<SetType> GetComponents() 86 { 87 auto todo = graph.Positions(); 88 std::vector<SetType> ret; 89 // Iterate over all connected components of the graph. 90 while (todo.Any()) { 91 auto component = graph.FindConnectedComponent(todo); 92 ret.push_back(component); 93 todo -= component; 94 } 95 return ret; 96 } 97 98 /** Check whether this graph is oversized (contains a connected component whose number of 99 * transactions exceeds max_cluster_count. */ 100 bool IsOversized() 101 { 102 if (!oversized.has_value()) { 103 // Only recompute when oversized isn't already known. 104 oversized = false; 105 for (auto component : GetComponents()) { 106 if (component.Count() > max_cluster_count) oversized = true; 107 uint64_t component_size{0}; 108 for (auto i : component) component_size += graph.FeeRate(i).size; 109 if (component_size > max_cluster_size) oversized = true; 110 } 111 } 112 return *oversized; 113 } 114 115 void MakeModified(DepGraphIndex index) 116 { 117 modified |= graph.GetConnectedComponent(graph.Positions(), index); 118 } 119 120 /** Determine the number of (non-removed) transactions in the graph. */ 121 DepGraphIndex GetTransactionCount() const { return graph.TxCount(); } 122 123 /** Get the sum of all fees/sizes in the graph. */ 124 FeePerWeight SumAll() const 125 { 126 FeePerWeight ret; 127 for (auto i : graph.Positions()) { 128 ret += graph.FeeRate(i); 129 } 130 return ret; 131 } 132 133 /** Get the position where ref occurs in this simulated graph, or -1 if it does not. */ 134 Pos Find(const TxGraph::Ref* ref) const 135 { 136 auto it = simrevmap.find(ref); 137 if (it != simrevmap.end()) return it->second; 138 return MISSING; 139 } 140 141 /** Given a position in this simulated graph, get the corresponding SimTxObject. */ 142 SimTxObject* GetRef(Pos pos) 143 { 144 assert(graph.Positions()[pos]); 145 assert(simmap[pos]); 146 return simmap[pos].get(); 147 } 148 149 /** Add a new transaction to the simulation and the specified real graph. */ 150 void AddTransaction(TxGraph& txgraph, const FeePerWeight& feerate, uint64_t txid) 151 { 152 assert(graph.TxCount() < MAX_TRANSACTIONS); 153 auto simpos = graph.AddTransaction(feerate); 154 real_is_optimal = false; 155 MakeModified(simpos); 156 assert(graph.Positions()[simpos]); 157 simmap[simpos] = std::make_shared<SimTxObject>(txid); 158 txgraph.AddTransaction(*simmap[simpos], feerate); 159 auto ptr = simmap[simpos].get(); 160 simrevmap[ptr] = simpos; 161 // This may invalidate our cached oversized value. 162 if (oversized.has_value() && !*oversized) oversized = std::nullopt; 163 } 164 165 /** Add a dependency between two positions in this graph. */ 166 void AddDependency(TxGraph::Ref* parent, TxGraph::Ref* child) 167 { 168 auto par_pos = Find(parent); 169 if (par_pos == MISSING) return; 170 auto chl_pos = Find(child); 171 if (chl_pos == MISSING) return; 172 graph.AddDependencies(SetType::Singleton(par_pos), chl_pos); 173 MakeModified(par_pos); 174 real_is_optimal = false; 175 // This may invalidate our cached oversized value. 176 if (oversized.has_value() && !*oversized) oversized = std::nullopt; 177 } 178 179 /** Modify the transaction fee of a ref, if it exists. */ 180 void SetTransactionFee(TxGraph::Ref* ref, int64_t fee) 181 { 182 auto pos = Find(ref); 183 if (pos == MISSING) return; 184 // No need to invoke MakeModified, because this equally affects main and staging. 185 real_is_optimal = false; 186 graph.FeeRate(pos).fee = fee; 187 } 188 189 /** Remove the transaction in the specified position from the graph. */ 190 void RemoveTransaction(TxGraph::Ref* ref) 191 { 192 auto pos = Find(ref); 193 if (pos == MISSING) return; 194 MakeModified(pos); 195 real_is_optimal = false; 196 graph.RemoveTransactions(SetType::Singleton(pos)); 197 simrevmap.erase(simmap[pos].get()); 198 // Retain the TxGraph::Ref corresponding to this position, so the Ref destruction isn't 199 // invoked until the simulation explicitly decided to do so. 200 removed.push_back(std::move(simmap[pos])); 201 simmap[pos].reset(); 202 // This may invalidate our cached oversized value. 203 if (oversized.has_value() && *oversized) oversized = std::nullopt; 204 } 205 206 /** Destroy the transaction from the graph, including from the removed set. This will 207 * trigger TxGraph::Ref::~Ref. reset_oversize controls whether the cached oversized 208 * value is cleared (destroying does not clear oversizedness in TxGraph of the main 209 * graph while staging exists). */ 210 void DestroyTransaction(TxGraph::Ref* ref, bool reset_oversize) 211 { 212 auto pos = Find(ref); 213 if (pos == MISSING) { 214 // Wipe the ref, if it exists, from the removed vector. Use std::partition rather 215 // than std::erase because we don't care about the order of the entries that 216 // remain. 217 auto remove = std::partition(removed.begin(), removed.end(), [&](auto& arg) { return arg.get() != ref; }); 218 removed.erase(remove, removed.end()); 219 } else { 220 MakeModified(pos); 221 graph.RemoveTransactions(SetType::Singleton(pos)); 222 real_is_optimal = false; 223 simrevmap.erase(simmap[pos].get()); 224 simmap[pos].reset(); 225 // This may invalidate our cached oversized value. 226 if (reset_oversize && oversized.has_value() && *oversized) { 227 oversized = std::nullopt; 228 } 229 } 230 } 231 232 /** Construct the set with all positions in this graph corresponding to the specified 233 * TxGraph::Refs. All of them must occur in this graph and not be removed. */ 234 SetType MakeSet(std::span<TxGraph::Ref* const> arg) 235 { 236 SetType ret; 237 for (TxGraph::Ref* ptr : arg) { 238 auto pos = Find(ptr); 239 assert(pos != Pos(-1)); 240 ret.Set(pos); 241 } 242 return ret; 243 } 244 245 /** Get the set of ancestors (desc=false) or descendants (desc=true) in this graph. */ 246 SetType GetAncDesc(TxGraph::Ref* arg, bool desc) 247 { 248 auto pos = Find(arg); 249 if (pos == MISSING) return {}; 250 return desc ? graph.Descendants(pos) : graph.Ancestors(pos); 251 } 252 253 /** Given a set of Refs (given as a vector of pointers), expand the set to include all its 254 * ancestors (desc=false) or all its descendants (desc=true) in this graph. */ 255 void IncludeAncDesc(std::vector<TxGraph::Ref*>& arg, bool desc) 256 { 257 std::vector<TxGraph::Ref*> ret; 258 for (auto ptr : arg) { 259 auto simpos = Find(ptr); 260 if (simpos != MISSING) { 261 for (auto i : desc ? graph.Descendants(simpos) : graph.Ancestors(simpos)) { 262 ret.push_back(simmap[i].get()); 263 } 264 } else { 265 ret.push_back(ptr); 266 } 267 } 268 // Construct deduplicated version in input (do not use std::sort/std::unique for 269 // deduplication as it'd rely on non-deterministic pointer comparison). 270 arg.clear(); 271 for (auto ptr : ret) { 272 if (std::find(arg.begin(), arg.end(), ptr) == arg.end()) { 273 arg.push_back(ptr); 274 } 275 } 276 } 277 278 279 /** Verify that set contains transactions from every oversized cluster, and nothing from 280 * non-oversized ones. */ 281 bool MatchesOversizedClusters(const SetType& set) 282 { 283 if (set.Any() && !IsOversized()) return false; 284 285 auto todo = graph.Positions(); 286 if (!set.IsSubsetOf(todo)) return false; 287 288 // Walk all clusters, and make sure all of set doesn't come from non-oversized clusters 289 while (todo.Any()) { 290 auto component = graph.FindConnectedComponent(todo); 291 // Determine whether component is oversized, due to either the size or count limit. 292 bool is_oversized = component.Count() > max_cluster_count; 293 uint64_t component_size{0}; 294 for (auto i : component) component_size += graph.FeeRate(i).size; 295 is_oversized |= component_size > max_cluster_size; 296 // Check whether overlap with set matches is_oversized. 297 if (is_oversized != set.Overlaps(component)) return false; 298 todo -= component; 299 } 300 return true; 301 } 302 }; 303 304 } // namespace 305 306 FUZZ_TARGET(txgraph) 307 { 308 // This is a big simulation test for TxGraph, which performs a fuzz-derived sequence of valid 309 // operations on a TxGraph instance, as well as on a simpler (mostly) reimplementation (see 310 // SimTxGraph above), comparing the outcome of functions that return a result, and finally 311 // performing a full comparison between the two. 312 313 SeedRandomStateForTest(SeedRand::ZEROS); 314 FuzzedDataProvider provider(buffer.data(), buffer.size()); 315 316 /** Internal test RNG, used only for decisions which would require significant amount of data 317 * to be read from the provider, without realistically impacting test sensitivity, and for 318 * specialized test cases that are hard to perform more generically. */ 319 InsecureRandomContext rng(provider.ConsumeIntegral<uint64_t>()); 320 321 /** Variable used whenever an empty SimTxObject is needed. */ 322 SimTxObject empty_ref; 323 324 /** The maximum number of transactions per (non-oversized) cluster we will use in this 325 * simulation. */ 326 auto max_cluster_count = provider.ConsumeIntegralInRange<DepGraphIndex>(1, MAX_CLUSTER_COUNT_LIMIT); 327 /** The maximum total size of transactions in a (non-oversized) cluster. */ 328 auto max_cluster_size = provider.ConsumeIntegralInRange<uint64_t>(1, 0x3fffff * MAX_CLUSTER_COUNT_LIMIT); 329 /** The amount of work to consider a cluster acceptably linearized. */ 330 auto acceptable_cost = provider.ConsumeIntegralInRange<uint64_t>(0, 10000); 331 332 /** The set of uint64_t "txid"s that have been assigned before. */ 333 std::set<uint64_t> assigned_txids; 334 335 // Construct a real graph, and a vector of simulated graphs (main, and possibly staging). 336 auto fallback_order = [&](const TxGraph::Ref& a, const TxGraph::Ref& b) noexcept { 337 uint64_t txid_a = static_cast<const SimTxObject&>(a).m_txid; 338 uint64_t txid_b = static_cast<const SimTxObject&>(b).m_txid; 339 assert(assigned_txids.contains(txid_a)); 340 assert(assigned_txids.contains(txid_b)); 341 return txid_a <=> txid_b; 342 }; 343 auto real = MakeTxGraph( 344 /*max_cluster_count=*/max_cluster_count, 345 /*max_cluster_size=*/max_cluster_size, 346 /*acceptable_cost=*/acceptable_cost, 347 /*fallback_order=*/fallback_order); 348 349 std::vector<SimTxGraph> sims; 350 sims.reserve(2); 351 sims.emplace_back(max_cluster_count, max_cluster_size); 352 353 /** Struct encapsulating information about a BlockBuilder that's currently live. */ 354 struct BlockBuilderData 355 { 356 /** BlockBuilder object from real. */ 357 std::unique_ptr<TxGraph::BlockBuilder> builder; 358 /** The set of transactions marked as included in *builder. */ 359 SimTxGraph::SetType included; 360 /** The set of transactions marked as included or skipped in *builder. */ 361 SimTxGraph::SetType done; 362 /** The last chunk feerate returned by *builder. IsEmpty() if none yet. */ 363 FeePerWeight last_feerate; 364 365 BlockBuilderData(std::unique_ptr<TxGraph::BlockBuilder> builder_in) : builder(std::move(builder_in)) {} 366 }; 367 368 /** Currently active block builders. */ 369 std::vector<BlockBuilderData> block_builders; 370 371 /** Function to pick any SimTxObject (for either sim in sims: from sim.simmap or sim.removed, or the 372 * empty one). */ 373 auto pick_fn = [&]() noexcept -> SimTxObject* { 374 size_t tx_count[2] = {sims[0].GetTransactionCount(), 0}; 375 /** The number of possible choices. */ 376 size_t choices = tx_count[0] + sims[0].removed.size() + 1; 377 if (sims.size() == 2) { 378 tx_count[1] = sims[1].GetTransactionCount(); 379 choices += tx_count[1] + sims[1].removed.size(); 380 } 381 /** Pick one of them. */ 382 auto choice = provider.ConsumeIntegralInRange<size_t>(0, choices - 1); 383 // Consider both main and (if it exists) staging. 384 for (size_t level = 0; level < sims.size(); ++level) { 385 auto& sim = sims[level]; 386 if (choice < tx_count[level]) { 387 // Return from graph. 388 for (auto i : sim.graph.Positions()) { 389 if (choice == 0) return sim.GetRef(i); 390 --choice; 391 } 392 assert(false); 393 } else { 394 choice -= tx_count[level]; 395 } 396 if (choice < sim.removed.size()) { 397 // Return from removed. 398 return sim.removed[choice].get(); 399 } else { 400 choice -= sim.removed.size(); 401 } 402 } 403 // Return empty. 404 assert(choice == 0); 405 return &empty_ref; 406 }; 407 408 /** Function to construct the correct fee-size diagram a real graph has based on its graph 409 * order (as reported by GetCluster(), so it works for both main and staging). */ 410 auto get_diagram_fn = [&](TxGraph::Level level_select) -> std::vector<FeeFrac> { 411 int level = level_select == TxGraph::Level::MAIN ? 0 : sims.size() - 1; 412 auto& sim = sims[level]; 413 // For every transaction in the graph, request its cluster, and throw them into a set. 414 std::set<std::vector<TxGraph::Ref*>> clusters; 415 for (auto i : sim.graph.Positions()) { 416 auto ref = sim.GetRef(i); 417 clusters.insert(real->GetCluster(*ref, level_select)); 418 } 419 // Compute the chunkings of each (deduplicated) cluster. 420 size_t num_tx{0}; 421 std::vector<FeeFrac> chunk_feerates; 422 for (const auto& cluster : clusters) { 423 num_tx += cluster.size(); 424 std::vector<SimTxGraph::Pos> linearization; 425 linearization.reserve(cluster.size()); 426 for (auto refptr : cluster) linearization.push_back(sim.Find(refptr)); 427 for (const FeeFrac& chunk_feerate : ChunkLinearization(sim.graph, linearization)) { 428 chunk_feerates.push_back(chunk_feerate); 429 } 430 } 431 // Verify the number of transactions after deduplicating clusters. This implicitly verifies 432 // that GetCluster on each element of a cluster reports the cluster transactions in the same 433 // order. 434 assert(num_tx == sim.GetTransactionCount()); 435 // Sort by feerate only, since violating topological constraints within same-feerate 436 // chunks won't affect diagram comparisons. 437 std::ranges::sort(chunk_feerates, std::greater<ByRatioNegSize<FeeFrac>>{}); 438 return chunk_feerates; 439 }; 440 441 LIMITED_WHILE(provider.remaining_bytes() > 0, 200) { 442 // Read a one-byte command. 443 int command = provider.ConsumeIntegral<uint8_t>(); 444 int orig_command = command; 445 446 // Treat the lowest bit of a command as a flag (which selects a variant of some of the 447 // operations), and the second-lowest bit as a way of selecting main vs. staging, and leave 448 // the rest of the bits in command. 449 bool alt = command & 1; 450 TxGraph::Level level_select = (command & 2) ? TxGraph::Level::MAIN : TxGraph::Level::TOP; 451 command >>= 2; 452 453 /** Use the bottom 2 bits of command to select an entry in the block_builders vector (if 454 * any). These use the same bits as alt/level_select, so don't use those in actions below 455 * where builder_idx is used as well. */ 456 int builder_idx = block_builders.empty() ? -1 : int((orig_command & 3) % block_builders.size()); 457 458 // Provide convenient aliases for the top simulated graph (main, or staging if it exists), 459 // one for the simulated graph selected based on level_select (for operations that can operate 460 // on both graphs), and one that always refers to the main graph. 461 auto& top_sim = sims.back(); 462 auto& sel_sim = level_select == TxGraph::Level::MAIN ? sims[0] : top_sim; 463 auto& main_sim = sims[0]; 464 465 // Keep decrementing command for each applicable operation, until one is hit. Multiple 466 // iterations may be necessary. 467 while (true) { 468 if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() < SimTxGraph::MAX_TRANSACTIONS && command-- == 0) { 469 // AddTransaction. 470 int64_t fee; 471 int32_t size; 472 if (alt) { 473 // If alt is true, pick fee and size from the entire range. 474 fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff); 475 size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff); 476 } else { 477 // Otherwise, use smaller range which consume fewer fuzz input bytes, as just 478 // these are likely sufficient to trigger all interesting code paths already. 479 fee = provider.ConsumeIntegral<uint8_t>(); 480 size = provider.ConsumeIntegralInRange<uint32_t>(1, 0xff); 481 } 482 FeePerWeight feerate{fee, size}; 483 // Pick a novel txid (and not 0, which is reserved for empty_ref). 484 uint64_t txid; 485 do { 486 txid = rng.rand64(); 487 } while (txid == 0 || assigned_txids.contains(txid)); 488 assigned_txids.insert(txid); 489 // Create the transaction in the simulation and the real graph. 490 top_sim.AddTransaction(*real, feerate, txid); 491 break; 492 } else if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() + top_sim.removed.size() > 1 && command-- == 0) { 493 // AddDependency. 494 auto par = pick_fn(); 495 auto chl = pick_fn(); 496 auto pos_par = top_sim.Find(par); 497 auto pos_chl = top_sim.Find(chl); 498 if (pos_par != SimTxGraph::MISSING && pos_chl != SimTxGraph::MISSING) { 499 // Determine if adding this would introduce a cycle (not allowed by TxGraph), 500 // and if so, skip. 501 if (top_sim.graph.Ancestors(pos_par)[pos_chl]) break; 502 } 503 top_sim.AddDependency(par, chl); 504 top_sim.real_is_optimal = false; 505 real->AddDependency(*par, *chl); 506 break; 507 } else if ((block_builders.empty() || sims.size() > 1) && top_sim.removed.size() < 100 && command-- == 0) { 508 // RemoveTransaction. Either all its ancestors or all its descendants are also 509 // removed (if any), to make sure TxGraph's reordering of removals and dependencies 510 // has no effect. 511 std::vector<TxGraph::Ref*> to_remove; 512 to_remove.push_back(pick_fn()); 513 top_sim.IncludeAncDesc(to_remove, alt); 514 // The order in which these ancestors/descendants are removed should not matter; 515 // randomly shuffle them. 516 std::shuffle(to_remove.begin(), to_remove.end(), rng); 517 for (TxGraph::Ref* ptr : to_remove) { 518 real->RemoveTransaction(*ptr); 519 top_sim.RemoveTransaction(ptr); 520 } 521 break; 522 } else if (sel_sim.removed.size() > 0 && command-- == 0) { 523 // ~Ref (of an already-removed transaction). Destroying a TxGraph::Ref has an 524 // observable effect on the TxGraph it refers to, so this simulation permits doing 525 // so separately from other actions on TxGraph. 526 527 // Pick a Ref of sel_sim.removed to destroy. Note that the same Ref may still occur 528 // in the other graph, and thus not actually trigger ~Ref yet (which is exactly 529 // what we want, as destroying Refs is only allowed when it does not refer to an 530 // existing transaction in either graph). 531 auto removed_pos = provider.ConsumeIntegralInRange<size_t>(0, sel_sim.removed.size() - 1); 532 if (removed_pos != sel_sim.removed.size() - 1) { 533 std::swap(sel_sim.removed[removed_pos], sel_sim.removed.back()); 534 } 535 sel_sim.removed.pop_back(); 536 break; 537 } else if (block_builders.empty() && command-- == 0) { 538 // ~Ref (of any transaction). 539 std::vector<TxGraph::Ref*> to_destroy; 540 to_destroy.push_back(pick_fn()); 541 while (true) { 542 // Keep adding either the ancestors or descendants the already picked 543 // transactions have in both graphs (main and staging) combined. Destroying 544 // will trigger deletions in both, so to have consistent TxGraph behavior, the 545 // set must be closed under ancestors, or descendants, in both graphs. 546 auto old_size = to_destroy.size(); 547 for (auto& sim : sims) sim.IncludeAncDesc(to_destroy, alt); 548 if (to_destroy.size() == old_size) break; 549 } 550 // The order in which these ancestors/descendants are destroyed should not matter; 551 // randomly shuffle them. 552 std::shuffle(to_destroy.begin(), to_destroy.end(), rng); 553 for (TxGraph::Ref* ptr : to_destroy) { 554 for (size_t level = 0; level < sims.size(); ++level) { 555 sims[level].DestroyTransaction(ptr, level == sims.size() - 1); 556 } 557 } 558 break; 559 } else if (block_builders.empty() && command-- == 0) { 560 // SetTransactionFee. 561 int64_t fee; 562 if (alt) { 563 fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff); 564 } else { 565 fee = provider.ConsumeIntegral<uint8_t>(); 566 } 567 auto ref = pick_fn(); 568 real->SetTransactionFee(*ref, fee); 569 for (auto& sim : sims) { 570 sim.SetTransactionFee(ref, fee); 571 } 572 break; 573 } else if (command-- == 0) { 574 // GetTransactionCount. 575 assert(real->GetTransactionCount(level_select) == sel_sim.GetTransactionCount()); 576 break; 577 } else if (command-- == 0) { 578 // Exists. 579 auto ref = pick_fn(); 580 bool exists = real->Exists(*ref, level_select); 581 bool should_exist = sel_sim.Find(ref) != SimTxGraph::MISSING; 582 assert(exists == should_exist); 583 break; 584 } else if (command-- == 0) { 585 // IsOversized. 586 assert(sel_sim.IsOversized() == real->IsOversized(level_select)); 587 break; 588 } else if (command-- == 0) { 589 // GetIndividualFeerate. 590 auto ref = pick_fn(); 591 auto feerate = real->GetIndividualFeerate(*ref); 592 bool found{false}; 593 for (auto& sim : sims) { 594 auto simpos = sim.Find(ref); 595 if (simpos != SimTxGraph::MISSING) { 596 found = true; 597 assert(feerate == sim.graph.FeeRate(simpos)); 598 } 599 } 600 if (!found) assert(feerate.IsEmpty()); 601 break; 602 } else if (!main_sim.IsOversized() && command-- == 0) { 603 // GetMainChunkFeerate. 604 auto ref = pick_fn(); 605 auto feerate = real->GetMainChunkFeerate(*ref); 606 auto simpos = main_sim.Find(ref); 607 if (simpos == SimTxGraph::MISSING) { 608 assert(feerate.IsEmpty()); 609 } else { 610 // Just do some quick checks that the reported value is in range. A full 611 // recomputation of expected chunk feerates is done at the end. 612 assert(feerate.size >= main_sim.graph.FeeRate(simpos).size); 613 assert(feerate.size <= main_sim.SumAll().size); 614 } 615 break; 616 } else if (!sel_sim.IsOversized() && command-- == 0) { 617 // GetAncestors/GetDescendants. 618 auto ref = pick_fn(); 619 auto result = alt ? real->GetDescendants(*ref, level_select) 620 : real->GetAncestors(*ref, level_select); 621 assert(result.size() <= max_cluster_count); 622 auto result_set = sel_sim.MakeSet(result); 623 assert(result.size() == result_set.Count()); 624 auto expect_set = sel_sim.GetAncDesc(ref, alt); 625 assert(result_set == expect_set); 626 break; 627 } else if (!sel_sim.IsOversized() && command-- == 0) { 628 // GetAncestorsUnion/GetDescendantsUnion. 629 std::vector<TxGraph::Ref*> refs; 630 // Gather a list of up to 15 Ref pointers. 631 auto count = provider.ConsumeIntegralInRange<size_t>(0, 15); 632 refs.resize(count); 633 for (size_t i = 0; i < count; ++i) { 634 refs[i] = pick_fn(); 635 } 636 // Their order should not matter, shuffle them. 637 std::shuffle(refs.begin(), refs.end(), rng); 638 // Invoke the real function, and convert to SimPos set. 639 auto result = alt ? real->GetDescendantsUnion(refs, level_select) 640 : real->GetAncestorsUnion(refs, level_select); 641 auto result_set = sel_sim.MakeSet(result); 642 assert(result.size() == result_set.Count()); 643 // Compute the expected result. 644 SimTxGraph::SetType expect_set; 645 for (TxGraph::Ref* ref : refs) expect_set |= sel_sim.GetAncDesc(ref, alt); 646 // Compare. 647 assert(result_set == expect_set); 648 break; 649 } else if (!sel_sim.IsOversized() && command-- == 0) { 650 // GetCluster. 651 auto ref = pick_fn(); 652 auto result = real->GetCluster(*ref, level_select); 653 // Check cluster count limit. 654 assert(result.size() <= max_cluster_count); 655 // Require the result to be topologically valid and not contain duplicates. 656 auto left = sel_sim.graph.Positions(); 657 uint64_t total_size{0}; 658 for (auto refptr : result) { 659 auto simpos = sel_sim.Find(refptr); 660 total_size += sel_sim.graph.FeeRate(simpos).size; 661 assert(simpos != SimTxGraph::MISSING); 662 assert(left[simpos]); 663 left.Reset(simpos); 664 assert(!sel_sim.graph.Ancestors(simpos).Overlaps(left)); 665 } 666 // Check cluster size limit. 667 assert(total_size <= max_cluster_size); 668 // Require the set to be connected. 669 auto result_set = sel_sim.MakeSet(result); 670 assert(sel_sim.graph.IsConnected(result_set)); 671 // If ref exists, the result must contain it. If not, it must be empty. 672 auto simpos = sel_sim.Find(ref); 673 if (simpos != SimTxGraph::MISSING) { 674 assert(result_set[simpos]); 675 } else { 676 assert(result_set.None()); 677 } 678 // Require the set not to have ancestors or descendants outside of it. 679 for (auto i : result_set) { 680 assert(sel_sim.graph.Ancestors(i).IsSubsetOf(result_set)); 681 assert(sel_sim.graph.Descendants(i).IsSubsetOf(result_set)); 682 } 683 break; 684 } else if (command-- == 0) { 685 // HaveStaging. 686 assert((sims.size() == 2) == real->HaveStaging()); 687 break; 688 } else if (sims.size() < 2 && command-- == 0) { 689 // StartStaging. 690 sims.emplace_back(sims.back()); 691 sims.back().modified = SimTxGraph::SetType{}; 692 real->StartStaging(); 693 break; 694 } else if (block_builders.empty() && sims.size() > 1 && command-- == 0) { 695 // CommitStaging. 696 real->CommitStaging(); 697 // Resulting main level is only guaranteed to be optimal if all levels are 698 const bool main_optimal = std::all_of(sims.cbegin(), sims.cend(), [](const auto &sim) { return sim.real_is_optimal; }); 699 sims.erase(sims.begin()); 700 sims.front().real_is_optimal = main_optimal; 701 break; 702 } else if (sims.size() > 1 && command-- == 0) { 703 // AbortStaging. 704 real->AbortStaging(); 705 sims.pop_back(); 706 // Reset the cached oversized value (if TxGraph::Ref destructions triggered 707 // removals of main transactions while staging was active, then aborting will 708 // cause it to be re-evaluated in TxGraph). 709 sims.back().oversized = std::nullopt; 710 break; 711 } else if (!main_sim.IsOversized() && command-- == 0) { 712 // CompareMainOrder. 713 auto ref_a = pick_fn(); 714 auto ref_b = pick_fn(); 715 auto sim_a = main_sim.Find(ref_a); 716 auto sim_b = main_sim.Find(ref_b); 717 // Both transactions must exist in the main graph. 718 if (sim_a == SimTxGraph::MISSING || sim_b == SimTxGraph::MISSING) break; 719 auto cmp = real->CompareMainOrder(*ref_a, *ref_b); 720 // Distinct transactions have distinct places. 721 if (sim_a != sim_b) assert(cmp != 0); 722 // Ancestors go before descendants. 723 if (main_sim.graph.Ancestors(sim_a)[sim_b]) assert(cmp >= 0); 724 if (main_sim.graph.Descendants(sim_a)[sim_b]) assert(cmp <= 0); 725 // Do not verify consistency with chunk feerates, as we cannot easily determine 726 // these here without making more calls to real, which could affect its internal 727 // state. A full comparison is done at the end. 728 break; 729 } else if (!sel_sim.IsOversized() && command-- == 0) { 730 // CountDistinctClusters. 731 std::vector<TxGraph::Ref*> refs; 732 // Gather a list of up to 15 (or up to 255) Ref pointers. 733 auto count = provider.ConsumeIntegralInRange<size_t>(0, alt ? 255 : 15); 734 refs.resize(count); 735 for (size_t i = 0; i < count; ++i) { 736 refs[i] = pick_fn(); 737 } 738 // Their order should not matter, shuffle them. 739 std::shuffle(refs.begin(), refs.end(), rng); 740 // Invoke the real function. 741 auto result = real->CountDistinctClusters(refs, level_select); 742 // Build a set with representatives of the clusters the Refs occur in the 743 // simulated graph. For each, remember the lowest-index transaction SimPos in the 744 // cluster. 745 SimTxGraph::SetType sim_reps; 746 for (auto ref : refs) { 747 // Skip Refs that do not occur in the simulated graph. 748 auto simpos = sel_sim.Find(ref); 749 if (simpos == SimTxGraph::MISSING) continue; 750 // Find the component that includes ref. 751 auto component = sel_sim.graph.GetConnectedComponent(sel_sim.graph.Positions(), simpos); 752 // Remember the lowest-index SimPos in component, as a representative for it. 753 assert(component.Any()); 754 sim_reps.Set(component.First()); 755 } 756 // Compare the number of deduplicated representatives with the value returned by 757 // the real function. 758 assert(result == sim_reps.Count()); 759 break; 760 } else if (command-- == 0) { 761 // DoWork. 762 uint64_t max_cost = provider.ConsumeIntegralInRange<uint64_t>(0, alt ? 10000 : 255); 763 bool ret = real->DoWork(max_cost); 764 uint64_t cost_for_optimal{0}; 765 for (unsigned level = 0; level < sims.size(); ++level) { 766 // DoWork() will not optimize oversized levels, or the main level if a builder 767 // is present. Note that this impacts the DoWork() return value, as true means 768 // that non-optimal clusters may remain within such oversized or builder-having 769 // levels. 770 if (sims[level].IsOversized()) continue; 771 if (level == 0 && !block_builders.empty()) continue; 772 // If neither of the two above conditions holds, and DoWork() returned true, 773 // then the level is optimal. 774 if (ret) { 775 sims[level].real_is_optimal = true; 776 } 777 // Compute how much work would be needed to make everything optimal. 778 for (auto component : sims[level].GetComponents()) { 779 auto cost_opt_this_cluster = MaxOptimalLinearizationCost(component.Count()); 780 if (cost_opt_this_cluster > acceptable_cost) { 781 // If the amount of work required to linearize this cluster 782 // optimally exceeds acceptable_cost, DoWork() may process it in two 783 // stages: once to acceptable, and once to optimal. 784 cost_for_optimal += cost_opt_this_cluster + acceptable_cost; 785 } else { 786 cost_for_optimal += cost_opt_this_cluster; 787 } 788 } 789 } 790 if (!ret) { 791 // DoWork can only have more work left if the requested amount of work 792 // was insufficient to linearize everything optimally within the levels it is 793 // allowed to touch. 794 assert(max_cost <= cost_for_optimal); 795 } 796 break; 797 } else if (sims.size() == 2 && !sims[0].IsOversized() && !sims[1].IsOversized() && command-- == 0) { 798 // GetMainStagingDiagrams() 799 auto [real_main_diagram, real_staged_diagram] = real->GetMainStagingDiagrams(); 800 auto real_sum_main = std::accumulate(real_main_diagram.begin(), real_main_diagram.end(), FeeFrac{}); 801 auto real_sum_staged = std::accumulate(real_staged_diagram.begin(), real_staged_diagram.end(), FeeFrac{}); 802 auto real_gain = real_sum_staged - real_sum_main; 803 auto sim_gain = sims[1].SumAll() - sims[0].SumAll(); 804 // Just check that the total fee gained/lost and size gained/lost according to the 805 // diagram matches the difference in these values in the simulated graph. A more 806 // complete check of the GetMainStagingDiagrams result is performed at the end. 807 assert(sim_gain == real_gain); 808 // Check that the feerates in each diagram are monotonically decreasing. 809 for (size_t i = 1; i < real_main_diagram.size(); ++i) { 810 assert(ByRatio{real_main_diagram[i]} <= ByRatio{real_main_diagram[i - 1]}); 811 } 812 for (size_t i = 1; i < real_staged_diagram.size(); ++i) { 813 assert(ByRatio{real_staged_diagram[i]} <= ByRatio{real_staged_diagram[i - 1]}); 814 } 815 break; 816 } else if (block_builders.size() < 4 && !main_sim.IsOversized() && command-- == 0) { 817 // GetBlockBuilder. 818 block_builders.emplace_back(real->GetBlockBuilder()); 819 break; 820 } else if (!block_builders.empty() && command-- == 0) { 821 // ~BlockBuilder. 822 block_builders.erase(block_builders.begin() + builder_idx); 823 break; 824 } else if (!block_builders.empty() && command-- == 0) { 825 // BlockBuilder::GetCurrentChunk, followed by Include/Skip. 826 auto& builder_data = block_builders[builder_idx]; 827 auto new_included = builder_data.included; 828 auto new_done = builder_data.done; 829 auto chunk = builder_data.builder->GetCurrentChunk(); 830 if (chunk) { 831 // Chunk feerates must be monotonously decreasing. 832 if (!builder_data.last_feerate.IsEmpty()) { 833 assert(ByRatio{chunk->second} <= ByRatio{builder_data.last_feerate}); 834 } 835 builder_data.last_feerate = chunk->second; 836 // Verify the contents of GetCurrentChunk. 837 FeePerWeight sum_feerate; 838 for (TxGraph::Ref* ref : chunk->first) { 839 // Each transaction in the chunk must exist in the main graph. 840 auto simpos = main_sim.Find(ref); 841 assert(simpos != SimTxGraph::MISSING); 842 // Verify the claimed chunk feerate. 843 sum_feerate += main_sim.graph.FeeRate(simpos); 844 // Make sure no transaction is reported twice. 845 assert(!new_done[simpos]); 846 new_done.Set(simpos); 847 // The concatenation of all included transactions must be topologically valid. 848 new_included.Set(simpos); 849 assert(main_sim.graph.Ancestors(simpos).IsSubsetOf(new_included)); 850 } 851 assert(sum_feerate == chunk->second); 852 } else { 853 // When we reach the end, if nothing was skipped, the entire graph should have 854 // been reported. 855 if (builder_data.done == builder_data.included) { 856 assert(builder_data.done.Count() == main_sim.GetTransactionCount()); 857 } 858 } 859 // Possibly invoke GetCurrentChunk() again, which should give the same result. 860 if ((orig_command % 7) >= 5) { 861 auto chunk2 = builder_data.builder->GetCurrentChunk(); 862 assert(chunk == chunk2); 863 } 864 // Skip or include. 865 if ((orig_command % 5) >= 3) { 866 // Skip. 867 builder_data.builder->Skip(); 868 } else { 869 // Include. 870 builder_data.builder->Include(); 871 builder_data.included = new_included; 872 } 873 builder_data.done = new_done; 874 break; 875 } else if (!main_sim.IsOversized() && command-- == 0) { 876 // GetWorstMainChunk. 877 auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk(); 878 // Just do some sanity checks here. Consistency with GetBlockBuilder is checked 879 // below. 880 if (main_sim.GetTransactionCount() == 0) { 881 assert(worst_chunk.empty()); 882 assert(worst_chunk_feerate.IsEmpty()); 883 } else { 884 assert(!worst_chunk.empty()); 885 SimTxGraph::SetType done; 886 FeePerWeight sum; 887 for (TxGraph::Ref* ref : worst_chunk) { 888 // Each transaction in the chunk must exist in the main graph. 889 auto simpos = main_sim.Find(ref); 890 assert(simpos != SimTxGraph::MISSING); 891 sum += main_sim.graph.FeeRate(simpos); 892 // Make sure the chunk contains no duplicate transactions. 893 assert(!done[simpos]); 894 done.Set(simpos); 895 // All elements are preceded by all their descendants. 896 assert(main_sim.graph.Descendants(simpos).IsSubsetOf(done)); 897 } 898 assert(sum == worst_chunk_feerate); 899 } 900 break; 901 } else if ((block_builders.empty() || sims.size() > 1) && command-- == 0) { 902 // Trim. 903 bool was_oversized = top_sim.IsOversized(); 904 auto removed = real->Trim(); 905 // Verify that something was removed if and only if there was an oversized cluster. 906 assert(was_oversized == !removed.empty()); 907 if (!was_oversized) break; 908 auto removed_set = top_sim.MakeSet(removed); 909 // The removed set must contain all its own descendants. 910 for (auto simpos : removed_set) { 911 assert(top_sim.graph.Descendants(simpos).IsSubsetOf(removed_set)); 912 } 913 // Something from every oversized cluster should have been removed, and nothing 914 // else. 915 assert(top_sim.MatchesOversizedClusters(removed_set)); 916 917 // Apply all removals to the simulation, and verify the result is no longer 918 // oversized. Don't query the real graph for oversizedness; it is compared 919 // against the simulation anyway later. 920 for (auto simpos : removed_set) { 921 top_sim.RemoveTransaction(top_sim.GetRef(simpos)); 922 } 923 assert(!top_sim.IsOversized()); 924 break; 925 } else if ((block_builders.empty() || sims.size() > 1) && 926 top_sim.GetTransactionCount() > max_cluster_count && !top_sim.IsOversized() && command-- == 0) { 927 // Trim (special case which avoids apparent cycles in the implicit approximate 928 // dependency graph constructed inside the Trim() implementation). This is worth 929 // testing separately, because such cycles cannot occur in realistic scenarios, 930 // but this is hard to replicate in general in this fuzz test. 931 932 // First, we need to have dependencies applied and linearizations fixed to avoid 933 // circular dependencies in implied graph; trigger it via whatever means. 934 real->CountDistinctClusters({}, TxGraph::Level::TOP); 935 936 // Gather the current clusters. 937 auto clusters = top_sim.GetComponents(); 938 939 // Merge clusters randomly until at least one oversized one appears. 940 bool made_oversized = false; 941 auto merges_left = clusters.size() - 1; 942 while (merges_left > 0) { 943 --merges_left; 944 // Find positions of clusters in the clusters vector to merge together. 945 auto par_cl = rng.randrange(clusters.size()); 946 auto chl_cl = rng.randrange(clusters.size() - 1); 947 chl_cl += (chl_cl >= par_cl); 948 Assume(chl_cl != par_cl); 949 // Add between 1 and 3 dependencies between them. As all are in the same 950 // direction (from the child cluster to parent cluster), no cycles are possible, 951 // regardless of what internal topology Trim() uses as approximation within the 952 // clusters. 953 int num_deps = rng.randrange(3) + 1; 954 for (int i = 0; i < num_deps; ++i) { 955 // Find a parent transaction in the parent cluster. 956 auto par_idx = rng.randrange(clusters[par_cl].Count()); 957 SimTxGraph::Pos par_pos = 0; 958 for (auto j : clusters[par_cl]) { 959 if (par_idx == 0) { 960 par_pos = j; 961 break; 962 } 963 --par_idx; 964 } 965 // Find a child transaction in the child cluster. 966 auto chl_idx = rng.randrange(clusters[chl_cl].Count()); 967 SimTxGraph::Pos chl_pos = 0; 968 for (auto j : clusters[chl_cl]) { 969 if (chl_idx == 0) { 970 chl_pos = j; 971 break; 972 } 973 --chl_idx; 974 } 975 // Add dependency to both simulation and real TxGraph. 976 auto par_ref = top_sim.GetRef(par_pos); 977 auto chl_ref = top_sim.GetRef(chl_pos); 978 top_sim.AddDependency(par_ref, chl_ref); 979 real->AddDependency(*par_ref, *chl_ref); 980 } 981 // Compute the combined cluster. 982 auto par_cluster = clusters[par_cl]; 983 auto chl_cluster = clusters[chl_cl]; 984 auto new_cluster = par_cluster | chl_cluster; 985 // Remove the parent and child cluster from clusters. 986 std::erase_if(clusters, [&](const auto& cl) noexcept { return cl == par_cluster || cl == chl_cluster; }); 987 // Add the combined cluster. 988 clusters.push_back(new_cluster); 989 // If this is the first merge that causes an oversized cluster to appear, pick 990 // a random number of further merges to appear. 991 if (!made_oversized) { 992 made_oversized = new_cluster.Count() > max_cluster_count; 993 if (!made_oversized) { 994 FeeFrac total; 995 for (auto i : new_cluster) total += top_sim.graph.FeeRate(i); 996 if (uint32_t(total.size) > max_cluster_size) made_oversized = true; 997 } 998 if (made_oversized) merges_left = rng.randrange(clusters.size()); 999 } 1000 } 1001 1002 // Determine an upper bound on how many transactions are removed. 1003 uint32_t max_removed = 0; 1004 for (auto& cluster : clusters) { 1005 // Gather all transaction sizes in the to-be-combined cluster. 1006 std::vector<uint32_t> sizes; 1007 for (auto i : cluster) sizes.push_back(top_sim.graph.FeeRate(i).size); 1008 auto sum_sizes = std::accumulate(sizes.begin(), sizes.end(), uint64_t{0}); 1009 // Sort from large to small. 1010 std::ranges::sort(sizes, std::greater{}); 1011 // In the worst case, only the smallest transactions are removed. 1012 while (sizes.size() > max_cluster_count || sum_sizes > max_cluster_size) { 1013 sum_sizes -= sizes.back(); 1014 sizes.pop_back(); 1015 ++max_removed; 1016 } 1017 } 1018 1019 // Invoke Trim now on the definitely-oversized txgraph. 1020 auto removed = real->Trim(); 1021 // Verify that the number of removals is within range. 1022 assert(removed.size() >= 1); 1023 assert(removed.size() <= max_removed); 1024 // The removed set must contain all its own descendants. 1025 auto removed_set = top_sim.MakeSet(removed); 1026 for (auto simpos : removed_set) { 1027 assert(top_sim.graph.Descendants(simpos).IsSubsetOf(removed_set)); 1028 } 1029 // Something from every oversized cluster should have been removed, and nothing 1030 // else. 1031 assert(top_sim.MatchesOversizedClusters(removed_set)); 1032 1033 // Apply all removals to the simulation, and verify the result is no longer 1034 // oversized. Don't query the real graph for oversizedness; it is compared 1035 // against the simulation anyway later. 1036 for (auto simpos : removed_set) { 1037 top_sim.RemoveTransaction(top_sim.GetRef(simpos)); 1038 } 1039 assert(!top_sim.IsOversized()); 1040 break; 1041 } else if (command-- == 0) { 1042 // GetMainMemoryUsage(). 1043 auto usage = real->GetMainMemoryUsage(); 1044 // Test stability. 1045 if (alt) { 1046 auto usage2 = real->GetMainMemoryUsage(); 1047 assert(usage == usage2); 1048 } 1049 // Only empty graphs have 0 memory usage. 1050 if (main_sim.GetTransactionCount() == 0) { 1051 assert(usage == 0); 1052 } else { 1053 assert(usage > 0); 1054 } 1055 break; 1056 } 1057 } 1058 } 1059 1060 // After running all modifications, perform an internal sanity check (before invoking 1061 // inspectors that may modify the internal state). 1062 real->SanityCheck(); 1063 1064 if (!sims[0].IsOversized()) { 1065 // If the main graph is not oversized, verify the total ordering implied by 1066 // CompareMainOrder. 1067 // First construct two distinct randomized permutations of the positions in sims[0]. 1068 std::vector<SimTxGraph::Pos> vec1; 1069 for (auto i : sims[0].graph.Positions()) vec1.push_back(i); 1070 std::shuffle(vec1.begin(), vec1.end(), rng); 1071 auto vec2 = vec1; 1072 std::shuffle(vec2.begin(), vec2.end(), rng); 1073 if (vec1 == vec2) std::next_permutation(vec2.begin(), vec2.end()); 1074 // Sort both according to CompareMainOrder. By having randomized starting points, the order 1075 // of CompareMainOrder invocations is somewhat randomized as well. 1076 auto cmp = [&](SimTxGraph::Pos a, SimTxGraph::Pos b) noexcept { 1077 return real->CompareMainOrder(*sims[0].GetRef(a), *sims[0].GetRef(b)) < 0; 1078 }; 1079 std::ranges::sort(vec1, cmp); 1080 std::ranges::sort(vec2, cmp); 1081 1082 // Verify the resulting orderings are identical. This could only fail if the ordering was 1083 // not total. 1084 assert(vec1 == vec2); 1085 1086 // Verify that the ordering is topological. 1087 auto todo = sims[0].graph.Positions(); 1088 for (auto i : vec1) { 1089 todo.Reset(i); 1090 assert(!sims[0].graph.Ancestors(i).Overlaps(todo)); 1091 } 1092 assert(todo.None()); 1093 1094 // If the real graph claims to be optimal (the last DoWork() call returned true), verify 1095 // that calling Linearize on it does not improve it further. 1096 if (sims[0].real_is_optimal) { 1097 auto real_diagram = ChunkLinearization(sims[0].graph, vec1); 1098 auto fallback_order_sim = [&](DepGraphIndex a, DepGraphIndex b) noexcept { 1099 auto txid_a = sims[0].GetRef(a)->m_txid; 1100 auto txid_b = sims[0].GetRef(b)->m_txid; 1101 return txid_a <=> txid_b; 1102 }; 1103 auto [sim_lin, sim_optimal, _cost] = Linearize(sims[0].graph, 300000, rng.rand64(), fallback_order_sim, vec1); 1104 PostLinearize(sims[0].graph, sim_lin); 1105 auto sim_diagram = ChunkLinearization(sims[0].graph, sim_lin); 1106 auto cmp = CompareChunks(real_diagram, sim_diagram); 1107 assert(cmp == 0); 1108 1109 // Verify consistency of cross-cluster chunk ordering with tie-break (equal-feerate 1110 // prefix size). 1111 auto real_chunking = ChunkLinearizationInfo(sims[0].graph, vec1); 1112 /** Map with one entry per component of the sim main graph. Key is the first Pos of the 1113 * component. Value is the sum of all chunk sizes from that component seen 1114 * already, at the current chunk feerate. */ 1115 std::map<SimTxGraph::Pos, int32_t> comp_prefix_sizes; 1116 /** Current chunk feerate. */ 1117 FeeFrac last_chunk_feerate; 1118 /** Largest seen (equal-feerate chunk prefix size, max txid). */ 1119 std::pair<int32_t, uint64_t> max_chunk_tiebreak{0, 0}; 1120 for (const auto& chunk : real_chunking) { 1121 // If this is the first chunk with a strictly lower feerate, reset. 1122 if (ByRatio{chunk.feerate} < ByRatio{last_chunk_feerate}) { 1123 comp_prefix_sizes.clear(); 1124 max_chunk_tiebreak = {0, 0}; 1125 } 1126 last_chunk_feerate = chunk.feerate; 1127 // Find which sim component this chunk belongs to. 1128 auto component = sims[0].graph.GetConnectedComponent(sims[0].graph.Positions(), chunk.transactions.First()); 1129 assert(chunk.transactions.IsSubsetOf(component)); 1130 auto comp_key = component.First(); 1131 auto& comp_prefix_size = comp_prefix_sizes[comp_key]; 1132 comp_prefix_size += chunk.feerate.size; 1133 // Determine the chunk's max txid. 1134 uint64_t chunk_max_txid{0}; 1135 for (auto tx : chunk.transactions) { 1136 auto txid = sims[0].GetRef(tx)->m_txid; 1137 chunk_max_txid = std::max(txid, chunk_max_txid); 1138 } 1139 // Verify consistency: within each group of equal-feerate chunks, the 1140 // (equal-feerate chunk prefix size, max txid) must be increasing. 1141 std::pair<int32_t, uint64_t> chunk_tiebreak{comp_prefix_size, chunk_max_txid}; 1142 assert(chunk_tiebreak > max_chunk_tiebreak); 1143 max_chunk_tiebreak = chunk_tiebreak; 1144 } 1145 1146 // Verify that within each cluster, the internal ordering matches that of the 1147 // simulation if that is optimal too, since per-cluster optimal orderings are 1148 // deterministic. Note that both have been PostLinearize()'ed. 1149 if (sim_optimal) { 1150 for (const auto& component : sims[0].GetComponents()) { 1151 std::vector<DepGraphIndex> sim_chunk_lin, real_chunk_lin; 1152 for (auto i : sim_lin) { 1153 if (component[i]) sim_chunk_lin.push_back(i); 1154 } 1155 for (auto i : vec1) { 1156 if (component[i]) real_chunk_lin.push_back(i); 1157 } 1158 assert(sim_chunk_lin == real_chunk_lin); 1159 } 1160 } 1161 1162 // Verify that a fresh TxGraph, with the same transactions and txids, but constructed 1163 // in a different order, and with a different RNG state, recreates the exact same 1164 // ordering, showing that for optimal graphs, the full mempool ordering is 1165 // deterministic. 1166 auto real_redo = MakeTxGraph( 1167 /*max_cluster_count=*/max_cluster_count, 1168 /*max_cluster_size=*/max_cluster_size, 1169 /*acceptable_cost=*/acceptable_cost, 1170 /*fallback_order=*/fallback_order); 1171 /** Vector (indexed by SimTxGraph::Pos) of TxObjects in real_redo). */ 1172 std::vector<std::optional<SimTxObject>> txobjects_redo; 1173 txobjects_redo.resize(sims[0].graph.PositionRange()); 1174 // Recreate the graph's transactions with same feerate and txid. 1175 std::vector<DepGraphIndex> positions; 1176 for (auto i : sims[0].graph.Positions()) positions.push_back(i); 1177 std::shuffle(positions.begin(), positions.end(), rng); 1178 for (auto i : positions) { 1179 txobjects_redo[i].emplace(sims[0].GetRef(i)->m_txid); 1180 real_redo->AddTransaction(*txobjects_redo[i], FeePerWeight::FromFeeFrac(sims[0].graph.FeeRate(i))); 1181 } 1182 // Recreate the graph's dependencies. 1183 std::vector<std::pair<DepGraphIndex, DepGraphIndex>> deps; 1184 for (auto i : sims[0].graph.Positions()) { 1185 for (auto j : sims[0].graph.GetReducedParents(i)) { 1186 deps.emplace_back(j, i); 1187 } 1188 } 1189 std::shuffle(deps.begin(), deps.end(), rng); 1190 for (auto [parent, child] : deps) { 1191 real_redo->AddDependency(*txobjects_redo[parent], *txobjects_redo[child]); 1192 } 1193 // Do work to reach optimality. 1194 if (real_redo->DoWork(300000)) { 1195 // Start from a random permutation. 1196 auto vec_redo = vec1; 1197 std::shuffle(vec_redo.begin(), vec_redo.end(), rng); 1198 if (vec_redo == vec1) std::next_permutation(vec_redo.begin(), vec_redo.end()); 1199 // Sort it according to the main graph order in real_redo. 1200 auto cmp_redo = [&](SimTxGraph::Pos a, SimTxGraph::Pos b) noexcept { 1201 return real_redo->CompareMainOrder(*txobjects_redo[a], *txobjects_redo[b]) < 0; 1202 }; 1203 std::ranges::sort(vec_redo, cmp_redo); 1204 // Compare with the ordering we got from real. 1205 assert(vec1 == vec_redo); 1206 } 1207 } 1208 1209 // For every transaction in the total ordering, find a random one before it and after it, 1210 // and compare their chunk feerates, which must be consistent with the ordering. 1211 for (size_t pos = 0; pos < vec1.size(); ++pos) { 1212 auto pos_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[pos])); 1213 if (pos > 0) { 1214 size_t before = rng.randrange<size_t>(pos); 1215 auto before_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[before])); 1216 assert(ByRatio{before_feerate} >= ByRatio{pos_feerate}); 1217 } 1218 if (pos + 1 < vec1.size()) { 1219 size_t after = pos + 1 + rng.randrange<size_t>(vec1.size() - 1 - pos); 1220 auto after_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[after])); 1221 assert(ByRatio{after_feerate} <= ByRatio{pos_feerate}); 1222 } 1223 } 1224 1225 // The same order should be obtained through a BlockBuilder as implied by CompareMainOrder, 1226 // if nothing is skipped. 1227 auto builder = real->GetBlockBuilder(); 1228 std::vector<SimTxGraph::Pos> vec_builder; 1229 std::vector<TxGraph::Ref*> last_chunk; 1230 FeePerWeight last_chunk_feerate; 1231 while (auto chunk = builder->GetCurrentChunk()) { 1232 FeePerWeight sum; 1233 for (TxGraph::Ref* ref : chunk->first) { 1234 // The reported chunk feerate must match the chunk feerate obtained by asking 1235 // it for each of the chunk's transactions individually. 1236 assert(real->GetMainChunkFeerate(*ref) == chunk->second); 1237 // Verify the chunk feerate matches the sum of the reported individual feerates. 1238 sum += real->GetIndividualFeerate(*ref); 1239 // Chunks must contain transactions that exist in the graph. 1240 auto simpos = sims[0].Find(ref); 1241 assert(simpos != SimTxGraph::MISSING); 1242 vec_builder.push_back(simpos); 1243 } 1244 assert(sum == chunk->second); 1245 last_chunk = std::move(chunk->first); 1246 last_chunk_feerate = chunk->second; 1247 builder->Include(); 1248 } 1249 assert(vec_builder == vec1); 1250 1251 // The last chunk returned by the BlockBuilder must match GetWorstMainChunk, in reverse. 1252 std::reverse(last_chunk.begin(), last_chunk.end()); 1253 auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk(); 1254 assert(last_chunk == worst_chunk); 1255 assert(last_chunk_feerate == worst_chunk_feerate); 1256 1257 // Check that the implied ordering gives rise to a combined diagram that matches the 1258 // diagram constructed from the individual cluster linearization chunkings. 1259 auto main_real_diagram = get_diagram_fn(TxGraph::Level::MAIN); 1260 auto main_implied_diagram = ChunkLinearization(sims[0].graph, vec1); 1261 assert(CompareChunks(main_real_diagram, main_implied_diagram) == 0); 1262 1263 if (sims.size() >= 2 && !sims[1].IsOversized()) { 1264 // When the staging graph is not oversized as well, call GetMainStagingDiagrams, and 1265 // fully verify the result. 1266 auto [main_cmp_diagram, stage_cmp_diagram] = real->GetMainStagingDiagrams(); 1267 // Check that the feerates in each diagram are monotonically decreasing. 1268 for (size_t i = 1; i < main_cmp_diagram.size(); ++i) { 1269 assert(ByRatio{main_cmp_diagram[i]} <= ByRatio{main_cmp_diagram[i - 1]}); 1270 } 1271 for (size_t i = 1; i < stage_cmp_diagram.size(); ++i) { 1272 assert(ByRatio{stage_cmp_diagram[i]} <= ByRatio{stage_cmp_diagram[i - 1]}); 1273 } 1274 // Treat the diagrams as sets of chunk feerates, and sort them in the same way so that 1275 // std::set_difference can be used on them below. The exact ordering does not matter 1276 // here, but it has to be consistent with the one used in main_real_diagram and 1277 // stage_real_diagram). 1278 std::ranges::sort(main_cmp_diagram, std::greater<ByRatioNegSize<FeeFrac>>{}); 1279 std::ranges::sort(stage_cmp_diagram, std::greater<ByRatioNegSize<FeeFrac>>{}); 1280 // Find the chunks that appear in main_diagram but are missing from main_cmp_diagram. 1281 // This is allowed, because GetMainStagingDiagrams omits clusters in main unaffected 1282 // by staging. 1283 std::vector<FeeFrac> missing_main_cmp; 1284 std::set_difference(main_real_diagram.begin(), main_real_diagram.end(), 1285 main_cmp_diagram.begin(), main_cmp_diagram.end(), 1286 std::inserter(missing_main_cmp, missing_main_cmp.end()), 1287 std::greater<ByRatioNegSize<FeeFrac>>{}); 1288 assert(main_cmp_diagram.size() + missing_main_cmp.size() == main_real_diagram.size()); 1289 // Do the same for chunks in stage_diagram missing from stage_cmp_diagram. 1290 auto stage_real_diagram = get_diagram_fn(TxGraph::Level::TOP); 1291 std::vector<FeeFrac> missing_stage_cmp; 1292 std::set_difference(stage_real_diagram.begin(), stage_real_diagram.end(), 1293 stage_cmp_diagram.begin(), stage_cmp_diagram.end(), 1294 std::inserter(missing_stage_cmp, missing_stage_cmp.end()), 1295 std::greater<ByRatioNegSize<FeeFrac>>{}); 1296 assert(stage_cmp_diagram.size() + missing_stage_cmp.size() == stage_real_diagram.size()); 1297 // The missing chunks must be equal across main & staging (otherwise they couldn't have 1298 // been omitted). 1299 assert(missing_main_cmp == missing_stage_cmp); 1300 1301 // The missing part must include at least all transactions in staging which have not been 1302 // modified, or been in a cluster together with modified transactions, since they were 1303 // copied from main. Note that due to the reordering of removals w.r.t. dependency 1304 // additions, it is possible that the real implementation found more unaffected things. 1305 FeeFrac missing_real; 1306 for (const auto& feerate : missing_main_cmp) missing_real += feerate; 1307 FeeFrac missing_expected = sims[1].graph.FeeRate(sims[1].graph.Positions() - sims[1].modified); 1308 // Note that missing_real.fee < missing_expected.fee is possible to due the presence of 1309 // negative-fee transactions. 1310 assert(missing_real.size >= missing_expected.size); 1311 } 1312 } 1313 1314 assert(real->HaveStaging() == (sims.size() > 1)); 1315 1316 // Try to run a full comparison, for both TxGraph::Level::MAIN and TxGraph::Level::TOP in 1317 // TxGraph inspector functions that support both. 1318 for (auto level : {TxGraph::Level::TOP, TxGraph::Level::MAIN}) { 1319 auto& sim = level == TxGraph::Level::TOP ? sims.back() : sims.front(); 1320 // Compare simple properties of the graph with the simulation. 1321 assert(real->IsOversized(level) == sim.IsOversized()); 1322 assert(real->GetTransactionCount(level) == sim.GetTransactionCount()); 1323 // If the graph (and the simulation) are not oversized, perform a full comparison. 1324 if (!sim.IsOversized()) { 1325 auto todo = sim.graph.Positions(); 1326 // Iterate over all connected components of the resulting (simulated) graph, each of which 1327 // should correspond to a cluster in the real one. 1328 while (todo.Any()) { 1329 auto component = sim.graph.FindConnectedComponent(todo); 1330 todo -= component; 1331 // Iterate over the transactions in that component. 1332 for (auto i : component) { 1333 // Check its individual feerate against simulation. 1334 assert(sim.graph.FeeRate(i) == real->GetIndividualFeerate(*sim.GetRef(i))); 1335 // Check its ancestors against simulation. 1336 auto expect_anc = sim.graph.Ancestors(i); 1337 auto anc = sim.MakeSet(real->GetAncestors(*sim.GetRef(i), level)); 1338 assert(anc.Count() <= max_cluster_count); 1339 assert(anc == expect_anc); 1340 // Check its descendants against simulation. 1341 auto expect_desc = sim.graph.Descendants(i); 1342 auto desc = sim.MakeSet(real->GetDescendants(*sim.GetRef(i), level)); 1343 assert(desc.Count() <= max_cluster_count); 1344 assert(desc == expect_desc); 1345 // Check the cluster the transaction is part of. 1346 auto cluster = real->GetCluster(*sim.GetRef(i), level); 1347 assert(cluster.size() <= max_cluster_count); 1348 assert(sim.MakeSet(cluster) == component); 1349 // Check that the cluster is reported in a valid topological order (its 1350 // linearization). 1351 std::vector<DepGraphIndex> simlin; 1352 SimTxGraph::SetType done; 1353 uint64_t total_size{0}; 1354 for (TxGraph::Ref* ptr : cluster) { 1355 auto simpos = sim.Find(ptr); 1356 assert(sim.graph.Descendants(simpos).IsSubsetOf(component - done)); 1357 done.Set(simpos); 1358 assert(sim.graph.Ancestors(simpos).IsSubsetOf(done)); 1359 simlin.push_back(simpos); 1360 total_size += sim.graph.FeeRate(simpos).size; 1361 } 1362 // Check cluster size. 1363 assert(total_size <= max_cluster_size); 1364 // Construct a chunking object for the simulated graph, using the reported cluster 1365 // linearization as ordering, and compare it against the reported chunk feerates. 1366 if (sims.size() == 1 || level == TxGraph::Level::MAIN) { 1367 auto simlinchunk = ChunkLinearizationInfo(sim.graph, simlin); 1368 DepGraphIndex idx{0}; 1369 for (auto& chunk : simlinchunk) { 1370 // Require that the chunks of cluster linearizations are connected (this must 1371 // be the case as all linearizations inside are PostLinearized). 1372 assert(sim.graph.IsConnected(chunk.transactions)); 1373 // Check the chunk feerates of all transactions in the cluster. 1374 while (chunk.transactions.Any()) { 1375 assert(chunk.transactions[simlin[idx]]); 1376 chunk.transactions.Reset(simlin[idx]); 1377 assert(chunk.feerate == real->GetMainChunkFeerate(*cluster[idx])); 1378 ++idx; 1379 } 1380 } 1381 } 1382 } 1383 } 1384 } 1385 } 1386 1387 // Sanity check again (because invoking inspectors may modify internal unobservable state). 1388 real->SanityCheck(); 1389 1390 // Kill the block builders. 1391 block_builders.clear(); 1392 // Kill the TxGraph object. 1393 real.reset(); 1394 // Kill the simulated graphs, with all remaining Refs in it. If any, this verifies that Refs 1395 // can outlive the TxGraph that created them. 1396 sims.clear(); 1397 }