cluster_linearize.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 <random.h> 7 #include <serialize.h> 8 #include <streams.h> 9 #include <test/fuzz/FuzzedDataProvider.h> 10 #include <test/fuzz/fuzz.h> 11 #include <test/util/cluster_linearize.h> 12 #include <util/bitset.h> 13 #include <util/feefrac.h> 14 15 #include <algorithm> 16 #include <cstdint> 17 #include <utility> 18 #include <vector> 19 20 /* 21 * The tests in this file primarily cover the candidate finder classes and linearization algorithms. 22 * 23 * <----: An implementation (at the start of the line --) is tested in the test marked with *, 24 * possibly by comparison with other implementations (at the end of the line ->). 25 * <<---: The right side is implemented using the left side. 26 * 27 * +---------------------+ +-----------+ 28 * | SpanningForestState | <<-------------------- | Linearize | 29 * +---------------------+ +-----------+ 30 * | | 31 * | | ^^ PRODUCTION CODE 32 * | | || 33 * ============================================================================================== 34 * | | || 35 * |-clusterlin_sfl* | vv TEST CODE 36 * | | 37 * \------------------------------------\ |-clusterlin_linearize* 38 * | | 39 * v v 40 * +-----------------------+ +-----------------+ 41 * | SimpleCandidateFinder | <<-------------------| SimpleLinearize | 42 * +-----------------------+ +-----------------+ 43 * | | 44 * |-clusterlin_simple_finder* |-clusterlin_simple_linearize* 45 * v v 46 * +---------------------------+ +---------------------+ 47 * | ExhaustiveCandidateFinder | | ExhaustiveLinearize | 48 * +---------------------------+ +---------------------+ 49 * 50 * More tests are included for lower-level and related functions and classes: 51 * - DepGraph tests: 52 * - clusterlin_depgraph_sim 53 * - clusterlin_depgraph_serialization 54 * - clusterlin_components 55 * - ChunkLinearization and ChunkLinearizationInfo tests: 56 * - clusterlin_chunking 57 * - PostLinearize tests: 58 * - clusterlin_postlinearize 59 * - clusterlin_postlinearize_tree 60 * - clusterlin_postlinearize_moved_leaf 61 * - MakeConnected tests (a test-only function): 62 * - clusterlin_make_connected 63 */ 64 65 using namespace cluster_linearize; 66 67 namespace { 68 69 /** A simple finder class for candidate sets (topologically-valid subsets with high feerate), only 70 * used by SimpleLinearize below. */ 71 template<typename SetType> 72 class SimpleCandidateFinder 73 { 74 /** Internal dependency graph. */ 75 const DepGraph<SetType>& m_depgraph; 76 /** Which transaction are left to include. */ 77 SetType m_todo; 78 79 public: 80 /** Construct an SimpleCandidateFinder for a given graph. */ 81 SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept : 82 m_depgraph(depgraph), m_todo{depgraph.Positions()} {} 83 84 /** Remove a set of transactions from the set of to-be-linearized ones. */ 85 void MarkDone(SetType select) noexcept { m_todo -= select; } 86 87 /** Determine whether unlinearized transactions remain. */ 88 bool AllDone() const noexcept { return m_todo.None(); } 89 90 /** Find a candidate set using at most max_iterations iterations, and the number of iterations 91 * actually performed. If that number is less than max_iterations, then the result is optimal. 92 * 93 * Always returns a connected set of transactions. 94 * 95 * Complexity: O(N * M), where M is the number of connected topological subsets of the cluster. 96 * That number is bounded by M <= 2^(N-1). 97 */ 98 std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations) const noexcept 99 { 100 uint64_t iterations_left = max_iterations; 101 // Queue of work units. Each consists of: 102 // - inc: set of transactions definitely included 103 // - und: set of transactions that can be added to inc still 104 std::vector<std::pair<SetType, SetType>> queue; 105 // Initially we have just one queue element, with the entire graph in und. 106 queue.emplace_back(SetType{}, m_todo); 107 // Best solution so far. Initialize with the remaining ancestors of the first remaining 108 // transaction. 109 SetInfo best(m_depgraph, m_depgraph.Ancestors(m_todo.First()) & m_todo); 110 // Process the queue. 111 while (!queue.empty() && iterations_left) { 112 // Pop top element of the queue. 113 auto [inc, und] = queue.back(); 114 queue.pop_back(); 115 // Look for a transaction to consider adding/removing. 116 bool inc_none = inc.None(); 117 for (auto split : und) { 118 // If inc is empty, consider any split transaction. Otherwise only consider 119 // transactions that share ancestry with inc so far (which means only connected 120 // sets will be considered). 121 if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) { 122 --iterations_left; 123 // Add a queue entry with split included. 124 SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split))); 125 queue.emplace_back(new_inc.transactions, und - new_inc.transactions); 126 // Add a queue entry with split excluded. 127 queue.emplace_back(inc, und - m_depgraph.Descendants(split)); 128 // Update statistics to account for the candidate new_inc. 129 if (ByRatioNegSize{new_inc.feerate} > ByRatioNegSize{best.feerate}) best = new_inc; 130 break; 131 } 132 } 133 } 134 return {std::move(best), max_iterations - iterations_left}; 135 } 136 }; 137 138 /** A very simple finder class for optimal candidate sets, which tries every subset. 139 * 140 * It is even simpler than SimpleCandidateFinder, and exists just to help test the correctness of 141 * SimpleCandidateFinder, so that it can be used in SimpleLinearize, which is then used to test the 142 * correctness of Linearize. 143 */ 144 template<typename SetType> 145 class ExhaustiveCandidateFinder 146 { 147 /** Internal dependency graph. */ 148 const DepGraph<SetType>& m_depgraph; 149 /** Which transaction are left to include. */ 150 SetType m_todo; 151 152 public: 153 /** Construct an ExhaustiveCandidateFinder for a given graph. */ 154 ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept : 155 m_depgraph(depgraph), m_todo{depgraph.Positions()} {} 156 157 /** Remove a set of transactions from the set of to-be-linearized ones. */ 158 void MarkDone(SetType select) noexcept { m_todo -= select; } 159 160 /** Determine whether unlinearized transactions remain. */ 161 bool AllDone() const noexcept { return m_todo.None(); } 162 163 /** Find the optimal remaining candidate set. 164 * 165 * Complexity: O(N * 2^N). 166 */ 167 SetInfo<SetType> FindCandidateSet() const noexcept 168 { 169 // Best solution so far. 170 SetInfo<SetType> best{m_todo, m_depgraph.FeeRate(m_todo)}; 171 // The number of combinations to try. 172 uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1; 173 // Try the transitive closure of every non-empty subset of m_todo. 174 for (uint64_t x = 1; x < limit; ++x) { 175 // If bit number b is set in x, then the remaining ancestors of the b'th remaining 176 // transaction in m_todo are included. 177 SetType txn; 178 auto x_shifted{x}; 179 for (auto i : m_todo) { 180 if (x_shifted & 1) txn |= m_depgraph.Ancestors(i); 181 x_shifted >>= 1; 182 } 183 SetInfo cur(m_depgraph, txn & m_todo); 184 if (ByRatioNegSize{cur.feerate} > ByRatioNegSize{best.feerate}) best = cur; 185 } 186 return best; 187 } 188 }; 189 190 /** A simple linearization algorithm. 191 * 192 * This matches Linearize() in interface and behavior, though with fewer optimizations, lacking 193 * the ability to pass in an existing linearization, and linearizing by simply finding the 194 * consecutive remaining highest-feerate topological subset using SimpleCandidateFinder. 195 */ 196 template<typename SetType> 197 std::pair<std::vector<DepGraphIndex>, bool> SimpleLinearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations) 198 { 199 std::vector<DepGraphIndex> linearization; 200 SimpleCandidateFinder finder(depgraph); 201 SetType todo = depgraph.Positions(); 202 bool optimal = true; 203 while (todo.Any()) { 204 auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations); 205 if (iterations_done == max_iterations) optimal = false; 206 depgraph.AppendTopo(linearization, candidate.transactions); 207 todo -= candidate.transactions; 208 finder.MarkDone(candidate.transactions); 209 max_iterations -= iterations_done; 210 } 211 return {std::move(linearization), optimal}; 212 } 213 214 /** An even simpler linearization algorithm that tries all permutations. 215 * 216 * This roughly matches SimpleLinearize() (and Linearize) in interface and behavior, but always 217 * tries all topologically-valid transaction orderings, has no way to bound how much work it does, 218 * and always finds the optimal. With an O(n!) complexity, it should only be used for small 219 * clusters. 220 */ 221 template<typename SetType> 222 std::vector<DepGraphIndex> ExhaustiveLinearize(const DepGraph<SetType>& depgraph) 223 { 224 // The best linearization so far, and its chunking. 225 std::vector<DepGraphIndex> linearization; 226 std::vector<FeeFrac> chunking; 227 228 std::vector<DepGraphIndex> perm_linearization; 229 // Initialize with the lexicographically-first linearization. 230 for (DepGraphIndex i : depgraph.Positions()) perm_linearization.push_back(i); 231 // Iterate over all valid permutations. 232 do { 233 /** What prefix of perm_linearization is topological. */ 234 DepGraphIndex topo_length{0}; 235 TestBitSet perm_done; 236 while (topo_length < perm_linearization.size()) { 237 auto i = perm_linearization[topo_length]; 238 perm_done.Set(i); 239 if (!depgraph.Ancestors(i).IsSubsetOf(perm_done)) break; 240 ++topo_length; 241 } 242 if (topo_length == perm_linearization.size()) { 243 // If all of perm_linearization is topological, check if it is perhaps our best 244 // linearization so far. 245 auto perm_chunking = ChunkLinearization(depgraph, perm_linearization); 246 auto cmp = CompareChunks(perm_chunking, chunking); 247 // If the diagram is better, or if it is equal but with more chunks (because we 248 // prefer minimal chunks), consider this better. 249 if (linearization.empty() || cmp > 0 || (cmp == 0 && perm_chunking.size() > chunking.size())) { 250 linearization = perm_linearization; 251 chunking = perm_chunking; 252 } 253 } else { 254 // Otherwise, fast forward to the last permutation with the same non-topological 255 // prefix. 256 auto first_non_topo = perm_linearization.begin() + topo_length; 257 assert(std::is_sorted(first_non_topo + 1, perm_linearization.end())); 258 std::reverse(first_non_topo + 1, perm_linearization.end()); 259 } 260 } while(std::next_permutation(perm_linearization.begin(), perm_linearization.end())); 261 262 return linearization; 263 } 264 265 266 /** Stitch connected components together in a DepGraph, guaranteeing its corresponding cluster is connected. */ 267 template<typename BS> 268 void MakeConnected(DepGraph<BS>& depgraph) 269 { 270 auto todo = depgraph.Positions(); 271 auto comp = depgraph.FindConnectedComponent(todo); 272 Assume(depgraph.IsConnected(comp)); 273 todo -= comp; 274 while (todo.Any()) { 275 auto nextcomp = depgraph.FindConnectedComponent(todo); 276 Assume(depgraph.IsConnected(nextcomp)); 277 depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First()); 278 todo -= nextcomp; 279 comp = nextcomp; 280 } 281 } 282 283 /** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */ 284 template<typename SetType> 285 SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& todo, SpanReader& reader, bool non_empty) 286 { 287 // Read a bitmask from the fuzzing input. Add 1 if non_empty, so the mask is definitely not 288 // zero in that case. 289 uint64_t mask{0}; 290 try { 291 reader >> VARINT(mask); 292 } catch(const std::ios_base::failure&) {} 293 if (mask != uint64_t(-1)) mask += non_empty; 294 295 SetType ret; 296 for (auto i : todo) { 297 if (!ret[i]) { 298 if (mask & 1) ret |= depgraph.Ancestors(i); 299 mask >>= 1; 300 } 301 } 302 ret &= todo; 303 304 // While mask starts off non-zero if non_empty is true, it is still possible that all its low 305 // bits are 0, and ret ends up being empty. As a last resort, use the in-todo ancestry of the 306 // first todo position. 307 if (non_empty && ret.None()) { 308 Assume(todo.Any()); 309 ret = depgraph.Ancestors(todo.First()) & todo; 310 Assume(ret.Any()); 311 } 312 return ret; 313 } 314 315 /** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */ 316 template<typename BS> 317 std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader, bool topological=true) 318 { 319 std::vector<DepGraphIndex> linearization; 320 TestBitSet todo = depgraph.Positions(); 321 // In every iteration one transaction is appended to linearization. 322 while (todo.Any()) { 323 // Compute the set of transactions to select from. 324 TestBitSet potential_next; 325 if (topological) { 326 // Find all transactions with no not-yet-included ancestors. 327 for (auto j : todo) { 328 if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) { 329 potential_next.Set(j); 330 } 331 } 332 } else { 333 // Allow any element to be selected next, regardless of topology. 334 potential_next = todo; 335 } 336 // There must always be one (otherwise there is a cycle in the graph). 337 assert(potential_next.Any()); 338 // Read a number from reader, and interpret it as index into potential_next. 339 uint64_t idx{0}; 340 try { 341 reader >> VARINT(idx); 342 } catch (const std::ios_base::failure&) {} 343 idx %= potential_next.Count(); 344 // Find out which transaction that corresponds to. 345 for (auto j : potential_next) { 346 if (idx == 0) { 347 // When found, add it to linearization and remove it from todo. 348 linearization.push_back(j); 349 assert(todo[j]); 350 todo.Reset(j); 351 break; 352 } 353 --idx; 354 } 355 } 356 return linearization; 357 } 358 359 /** Given a dependency graph, construct a tree-structured graph. 360 * 361 * Copies the nodes from the depgraph, but only keeps the first parent (even direction) 362 * or the first child (odd direction) for each transaction. 363 */ 364 template<typename BS> 365 DepGraph<BS> BuildTreeGraph(const DepGraph<BS>& depgraph, uint8_t direction) 366 { 367 DepGraph<BS> depgraph_tree; 368 for (DepGraphIndex i = 0; i < depgraph.PositionRange(); ++i) { 369 if (depgraph.Positions()[i]) { 370 depgraph_tree.AddTransaction(depgraph.FeeRate(i)); 371 } else { 372 // For holes, add a dummy transaction which is deleted below, so that non-hole 373 // transactions retain their position. 374 depgraph_tree.AddTransaction(FeeFrac{}); 375 } 376 } 377 depgraph_tree.RemoveTransactions(BS::Fill(depgraph.PositionRange()) - depgraph.Positions()); 378 379 if (direction & 1) { 380 for (DepGraphIndex i : depgraph.Positions()) { 381 auto children = depgraph.GetReducedChildren(i); 382 if (children.Any()) { 383 depgraph_tree.AddDependencies(BS::Singleton(i), children.First()); 384 } 385 } 386 } else { 387 for (DepGraphIndex i : depgraph.Positions()) { 388 auto parents = depgraph.GetReducedParents(i); 389 if (parents.Any()) { 390 depgraph_tree.AddDependencies(BS::Singleton(parents.First()), i); 391 } 392 } 393 } 394 395 return depgraph_tree; 396 } 397 398 } // namespace 399 400 FUZZ_TARGET(clusterlin_depgraph_sim) 401 { 402 // Simulation test to verify the full behavior of DepGraph. 403 404 FuzzedDataProvider provider(buffer.data(), buffer.size()); 405 406 /** Real DepGraph being tested. */ 407 DepGraph<TestBitSet> real; 408 /** Simulated DepGraph (sim[i] is std::nullopt if position i does not exist; otherwise, 409 * sim[i]->first is its individual feerate, and sim[i]->second is its set of ancestors. */ 410 std::array<std::optional<std::pair<FeeFrac, TestBitSet>>, TestBitSet::Size()> sim; 411 /** The number of non-nullopt position in sim. */ 412 DepGraphIndex num_tx_sim{0}; 413 414 /** Read a valid index of a transaction from the provider. */ 415 auto idx_fn = [&]() { 416 auto offset = provider.ConsumeIntegralInRange<DepGraphIndex>(0, num_tx_sim - 1); 417 for (DepGraphIndex i = 0; i < sim.size(); ++i) { 418 if (!sim[i].has_value()) continue; 419 if (offset == 0) return i; 420 --offset; 421 } 422 assert(false); 423 return DepGraphIndex(-1); 424 }; 425 426 /** Read a valid subset of the transactions from the provider. */ 427 auto subset_fn = [&]() { 428 auto range = (uint64_t{1} << num_tx_sim) - 1; 429 const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range); 430 auto mask_shifted = mask; 431 TestBitSet subset; 432 for (DepGraphIndex i = 0; i < sim.size(); ++i) { 433 if (!sim[i].has_value()) continue; 434 if (mask_shifted & 1) { 435 subset.Set(i); 436 } 437 mask_shifted >>= 1; 438 } 439 assert(mask_shifted == 0); 440 return subset; 441 }; 442 443 /** Read any set of transactions from the provider (including unused positions). */ 444 auto set_fn = [&]() { 445 auto range = (uint64_t{1} << sim.size()) - 1; 446 const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range); 447 TestBitSet set; 448 for (DepGraphIndex i = 0; i < sim.size(); ++i) { 449 if ((mask >> i) & 1) { 450 set.Set(i); 451 } 452 } 453 return set; 454 }; 455 456 /** Propagate ancestor information in sim. */ 457 auto anc_update_fn = [&]() { 458 while (true) { 459 bool updates{false}; 460 for (DepGraphIndex chl = 0; chl < sim.size(); ++chl) { 461 if (!sim[chl].has_value()) continue; 462 for (auto par : sim[chl]->second) { 463 if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) { 464 sim[chl]->second |= sim[par]->second; 465 updates = true; 466 } 467 } 468 } 469 if (!updates) break; 470 } 471 }; 472 473 /** Compare the state of transaction i in the simulation with the real one. */ 474 auto check_fn = [&](DepGraphIndex i) { 475 // Compare used positions. 476 assert(real.Positions()[i] == sim[i].has_value()); 477 if (sim[i].has_value()) { 478 // Compare feerate. 479 assert(real.FeeRate(i) == sim[i]->first); 480 // Compare ancestors (note that SanityCheck verifies correspondence between ancestors 481 // and descendants, so we can restrict ourselves to ancestors here). 482 assert(real.Ancestors(i) == sim[i]->second); 483 } 484 }; 485 486 auto last_compaction_pos{real.PositionRange()}; 487 488 LIMITED_WHILE(provider.remaining_bytes() > 0, 1000) { 489 int command = provider.ConsumeIntegral<uint8_t>() % 4; 490 while (true) { 491 // Iterate decreasing command until an applicable branch is found. 492 if (num_tx_sim < TestBitSet::Size() && command-- == 0) { 493 // AddTransaction. 494 auto fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff); 495 auto size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff); 496 FeeFrac feerate{fee, size}; 497 // Apply to DepGraph. 498 auto idx = real.AddTransaction(feerate); 499 // Verify that the returned index is correct. 500 assert(!sim[idx].has_value()); 501 for (DepGraphIndex i = 0; i < TestBitSet::Size(); ++i) { 502 if (!sim[i].has_value()) { 503 assert(idx == i); 504 break; 505 } 506 } 507 // Update sim. 508 sim[idx] = {feerate, TestBitSet::Singleton(idx)}; 509 ++num_tx_sim; 510 break; 511 } else if (num_tx_sim > 0 && command-- == 0) { 512 // AddDependencies. 513 DepGraphIndex child = idx_fn(); 514 auto parents = subset_fn(); 515 // Apply to DepGraph. 516 real.AddDependencies(parents, child); 517 // Apply to sim. 518 sim[child]->second |= parents; 519 break; 520 } else if (num_tx_sim > 0 && command-- == 0) { 521 // Remove transactions. 522 auto del = set_fn(); 523 // Propagate all ancestry information before deleting anything in the simulation (as 524 // intermediary transactions may be deleted which impact connectivity). 525 anc_update_fn(); 526 // Compare the state of the transactions being deleted. 527 for (auto i : del) check_fn(i); 528 // Apply to DepGraph. 529 real.RemoveTransactions(del); 530 // Apply to sim. 531 for (DepGraphIndex i = 0; i < sim.size(); ++i) { 532 if (sim[i].has_value()) { 533 if (del[i]) { 534 --num_tx_sim; 535 sim[i] = std::nullopt; 536 } else { 537 sim[i]->second -= del; 538 } 539 } 540 } 541 break; 542 } else if (command-- == 0) { 543 // Compact. 544 const size_t mem_before{real.DynamicMemoryUsage()}; 545 real.Compact(); 546 const size_t mem_after{real.DynamicMemoryUsage()}; 547 assert(real.PositionRange() < last_compaction_pos ? mem_after < mem_before : mem_after <= mem_before); 548 last_compaction_pos = real.PositionRange(); 549 break; 550 } 551 } 552 } 553 554 // Compare the real obtained depgraph against the simulation. 555 anc_update_fn(); 556 for (DepGraphIndex i = 0; i < sim.size(); ++i) check_fn(i); 557 assert(real.TxCount() == num_tx_sim); 558 // Sanity check the result (which includes round-tripping serialization, if applicable). 559 SanityCheck(real); 560 } 561 562 FUZZ_TARGET(clusterlin_depgraph_serialization) 563 { 564 // Verify that any deserialized depgraph is acyclic and roundtrips to an identical depgraph. 565 566 // Construct a graph by deserializing. 567 SpanReader reader(buffer); 568 DepGraph<TestBitSet> depgraph; 569 DepGraphIndex par_code{0}, chl_code{0}; 570 try { 571 reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(par_code) >> VARINT(chl_code); 572 } catch (const std::ios_base::failure&) {} 573 SanityCheck(depgraph); 574 575 // Verify the graph is a DAG. 576 assert(depgraph.IsAcyclic()); 577 578 // Introduce a cycle, and then test that IsAcyclic returns false. 579 if (depgraph.TxCount() < 2) return; 580 DepGraphIndex par(0), chl(0); 581 // Pick any transaction of depgraph as parent. 582 par_code %= depgraph.TxCount(); 583 for (auto i : depgraph.Positions()) { 584 if (par_code == 0) { 585 par = i; 586 break; 587 } 588 --par_code; 589 } 590 // Pick any ancestor of par (excluding itself) as child, if any. 591 auto ancestors = depgraph.Ancestors(par) - TestBitSet::Singleton(par); 592 if (ancestors.None()) return; 593 chl_code %= ancestors.Count(); 594 for (auto i : ancestors) { 595 if (chl_code == 0) { 596 chl = i; 597 break; 598 } 599 --chl_code; 600 } 601 // Add the cycle-introducing dependency. 602 depgraph.AddDependencies(TestBitSet::Singleton(par), chl); 603 // Check that we now detect a cycle. 604 assert(!depgraph.IsAcyclic()); 605 } 606 607 FUZZ_TARGET(clusterlin_components) 608 { 609 // Verify the behavior of DepGraphs's FindConnectedComponent and IsConnected functions. 610 611 // Construct a depgraph. 612 SpanReader reader(buffer); 613 DepGraph<TestBitSet> depgraph; 614 std::vector<DepGraphIndex> linearization; 615 try { 616 reader >> Using<DepGraphFormatter>(depgraph); 617 } catch (const std::ios_base::failure&) {} 618 619 TestBitSet todo = depgraph.Positions(); 620 while (todo.Any()) { 621 // Pick a transaction in todo, or nothing. 622 std::optional<DepGraphIndex> picked; 623 { 624 uint64_t picked_num{0}; 625 try { 626 reader >> VARINT(picked_num); 627 } catch (const std::ios_base::failure&) {} 628 if (picked_num < todo.Size() && todo[picked_num]) { 629 picked = picked_num; 630 } 631 } 632 633 // Find a connected component inside todo, including picked if any. 634 auto component = picked ? depgraph.GetConnectedComponent(todo, *picked) 635 : depgraph.FindConnectedComponent(todo); 636 637 // The component must be a subset of todo and non-empty. 638 assert(component.IsSubsetOf(todo)); 639 assert(component.Any()); 640 641 // If picked was provided, the component must include it. 642 if (picked) assert(component[*picked]); 643 644 // If todo is the entire graph, and the entire graph is connected, then the component must 645 // be the entire graph. 646 if (todo == depgraph.Positions()) { 647 assert((component == todo) == depgraph.IsConnected()); 648 } 649 650 // If subset is connected, then component must match subset. 651 assert((component == todo) == depgraph.IsConnected(todo)); 652 653 // The component cannot have any ancestors or descendants outside of component but in todo. 654 for (auto i : component) { 655 assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component)); 656 assert((depgraph.Descendants(i) & todo).IsSubsetOf(component)); 657 } 658 659 // Starting from any component element, we must be able to reach every element. 660 for (auto i : component) { 661 // Start with just i as reachable. 662 TestBitSet reachable = TestBitSet::Singleton(i); 663 // Add in-todo descendants and ancestors to reachable until it does not change anymore. 664 while (true) { 665 TestBitSet new_reachable = reachable; 666 for (auto j : new_reachable) { 667 new_reachable |= depgraph.Ancestors(j) & todo; 668 new_reachable |= depgraph.Descendants(j) & todo; 669 } 670 if (new_reachable == reachable) break; 671 reachable = new_reachable; 672 } 673 // Verify that the result is the entire component. 674 assert(component == reachable); 675 } 676 677 // Construct an arbitrary subset of todo. 678 uint64_t subset_bits{0}; 679 try { 680 reader >> VARINT(subset_bits); 681 } catch (const std::ios_base::failure&) {} 682 TestBitSet subset; 683 for (DepGraphIndex i : depgraph.Positions()) { 684 if (todo[i]) { 685 if (subset_bits & 1) subset.Set(i); 686 subset_bits >>= 1; 687 } 688 } 689 // Which must be non-empty. 690 if (subset.None()) subset = TestBitSet::Singleton(todo.First()); 691 // Remove it from todo. 692 todo -= subset; 693 } 694 695 // No components can be found in an empty subset. 696 assert(depgraph.FindConnectedComponent(todo).None()); 697 } 698 699 FUZZ_TARGET(clusterlin_make_connected) 700 { 701 // Verify that MakeConnected makes graphs connected. 702 703 SpanReader reader(buffer); 704 DepGraph<TestBitSet> depgraph; 705 try { 706 reader >> Using<DepGraphFormatter>(depgraph); 707 } catch (const std::ios_base::failure&) {} 708 MakeConnected(depgraph); 709 SanityCheck(depgraph); 710 assert(depgraph.IsConnected()); 711 } 712 713 FUZZ_TARGET(clusterlin_chunking) 714 { 715 // Verify the correctness of the ChunkLinearization function. 716 717 // Construct a graph by deserializing. 718 SpanReader reader(buffer); 719 DepGraph<TestBitSet> depgraph; 720 try { 721 reader >> Using<DepGraphFormatter>(depgraph); 722 } catch (const std::ios_base::failure&) {} 723 724 // Read a valid linearization for depgraph. 725 auto linearization = ReadLinearization(depgraph, reader); 726 727 // Invoke the chunking functions. 728 auto chunking = ChunkLinearization(depgraph, linearization); 729 auto chunking_info = ChunkLinearizationInfo(depgraph, linearization); 730 731 // Verify consistency between the two functions. 732 assert(chunking.size() == chunking_info.size()); 733 for (size_t i = 0; i < chunking.size(); ++i) { 734 assert(chunking[i] == chunking_info[i].feerate); 735 assert(SetInfo(depgraph, chunking_info[i].transactions) == chunking_info[i]); 736 } 737 738 // Verify that chunk feerates are monotonically non-increasing. 739 for (size_t i = 1; i < chunking.size(); ++i) { 740 assert(ByRatio{chunking[i]} <= ByRatio{chunking[i - 1]}); 741 } 742 743 // Naively recompute the chunks (each is the highest-feerate prefix of what remains). 744 auto todo = depgraph.Positions(); 745 for (const auto& [chunk_set, chunk_feerate] : chunking_info) { 746 assert(todo.Any()); 747 SetInfo<TestBitSet> accumulator, best; 748 for (DepGraphIndex idx : linearization) { 749 if (todo[idx]) { 750 accumulator.Set(depgraph, idx); 751 if (best.feerate.IsEmpty() || ByRatio{accumulator.feerate} > ByRatio{best.feerate}) { 752 best = accumulator; 753 } 754 } 755 } 756 assert(chunk_feerate == best.feerate); 757 assert(chunk_set == best.transactions); 758 assert(best.transactions.IsSubsetOf(todo)); 759 todo -= best.transactions; 760 } 761 assert(todo.None()); 762 } 763 764 static constexpr auto MAX_SIMPLE_ITERATIONS = 300000; 765 766 FUZZ_TARGET(clusterlin_simple_finder) 767 { 768 // Verify that SimpleCandidateFinder works as expected by sanity checking the results 769 // and comparing them (if claimed to be optimal) against the sets found by 770 // ExhaustiveCandidateFinder. 771 // 772 // Note that SimpleCandidateFinder is only used in tests; the purpose of this fuzz test is to 773 // establish confidence in SimpleCandidateFinder, so that it can be used in SimpleLinearize, 774 // which is then used to test Linearize below. 775 776 // Retrieve a depgraph from the fuzz input. 777 SpanReader reader(buffer); 778 DepGraph<TestBitSet> depgraph; 779 try { 780 reader >> Using<DepGraphFormatter>(depgraph); 781 } catch (const std::ios_base::failure&) {} 782 783 // Instantiate the SimpleCandidateFinder to be tested, and the ExhaustiveCandidateFinder it is 784 // being tested against. 785 SimpleCandidateFinder smp_finder(depgraph); 786 ExhaustiveCandidateFinder exh_finder(depgraph); 787 788 auto todo = depgraph.Positions(); 789 while (todo.Any()) { 790 assert(!smp_finder.AllDone()); 791 assert(!exh_finder.AllDone()); 792 793 // Call SimpleCandidateFinder. 794 auto [found, iterations_done] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS); 795 bool optimal = (iterations_done != MAX_SIMPLE_ITERATIONS); 796 797 // Sanity check the result. 798 assert(iterations_done <= MAX_SIMPLE_ITERATIONS); 799 assert(found.transactions.Any()); 800 assert(found.transactions.IsSubsetOf(todo)); 801 assert(depgraph.FeeRate(found.transactions) == found.feerate); 802 // Check that it is topologically valid. 803 for (auto i : found.transactions) { 804 assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo)); 805 } 806 807 // At most 2^(N-1) iterations can be required: the number of non-empty connected subsets a 808 // graph with N transactions can have. If MAX_SIMPLE_ITERATIONS exceeds this number, the 809 // result is necessarily optimal. 810 assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1))); 811 if (MAX_SIMPLE_ITERATIONS > (uint64_t{1} << (todo.Count() - 1))) assert(optimal); 812 813 // SimpleCandidateFinder only finds connected sets. 814 assert(depgraph.IsConnected(found.transactions)); 815 816 // Perform further quality checks only if SimpleCandidateFinder claims an optimal result. 817 if (optimal) { 818 if (todo.Count() <= 12) { 819 // Compare with ExhaustiveCandidateFinder. This quickly gets computationally 820 // expensive for large clusters (O(2^n)), so only do it for sufficiently small ones. 821 auto exhaustive = exh_finder.FindCandidateSet(); 822 assert(exhaustive.feerate == found.feerate); 823 } 824 825 // Compare with a non-empty topological set read from the fuzz input (comparing with an 826 // empty set is not interesting). 827 auto read_topo = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true); 828 assert(ByRatioNegSize{found.feerate} >= ByRatioNegSize{depgraph.FeeRate(read_topo)}); 829 } 830 831 // Find a non-empty topologically valid subset of transactions to remove from the graph. 832 // Using an empty set would mean the next iteration is identical to the current one, and 833 // could cause an infinite loop. 834 auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true); 835 todo -= del_set; 836 smp_finder.MarkDone(del_set); 837 exh_finder.MarkDone(del_set); 838 } 839 840 assert(smp_finder.AllDone()); 841 assert(exh_finder.AllDone()); 842 } 843 844 FUZZ_TARGET(clusterlin_simple_linearize) 845 { 846 // Verify the behavior of SimpleLinearize(). Note that SimpleLinearize is only used in tests; 847 // the purpose of this fuzz test is to establish confidence in SimpleLinearize, so that it can 848 // be used to test the real Linearize function in the fuzz test below. 849 850 // Retrieve an iteration count and a depgraph from the fuzz input. 851 SpanReader reader(buffer); 852 uint64_t iter_count{0}; 853 DepGraph<TestBitSet> depgraph; 854 try { 855 reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph); 856 } catch (const std::ios_base::failure&) {} 857 iter_count %= MAX_SIMPLE_ITERATIONS; 858 859 // Invoke SimpleLinearize(). 860 auto [linearization, optimal] = SimpleLinearize(depgraph, iter_count); 861 SanityCheck(depgraph, linearization); 862 auto simple_chunking = ChunkLinearization(depgraph, linearization); 863 864 // If the iteration count is sufficiently high, an optimal linearization must be found. 865 // SimpleLinearize on k transactions can take up to 2^(k-1) iterations (one per non-empty 866 // connected topologically valid subset), which sums over k=1..n to (2^n)-1. 867 const uint64_t n = depgraph.TxCount(); 868 if (n <= 63 && (iter_count >> n)) { 869 assert(optimal); 870 } 871 872 // If SimpleLinearize claims optimal result, and the cluster is sufficiently small (there are 873 // n! linearizations), test that the result is as good as every valid linearization. 874 if (optimal && depgraph.TxCount() <= 8) { 875 auto exh_linearization = ExhaustiveLinearize(depgraph); 876 auto exh_chunking = ChunkLinearization(depgraph, exh_linearization); 877 auto cmp = CompareChunks(simple_chunking, exh_chunking); 878 assert(cmp == 0); 879 assert(simple_chunking.size() == exh_chunking.size()); 880 } 881 882 if (optimal) { 883 // Compare with a linearization read from the fuzz input. 884 auto read = ReadLinearization(depgraph, reader); 885 auto read_chunking = ChunkLinearization(depgraph, read); 886 auto cmp = CompareChunks(simple_chunking, read_chunking); 887 assert(cmp >= 0); 888 } 889 } 890 891 FUZZ_TARGET(clusterlin_sfl) 892 { 893 // Verify the individual steps of the SFL algorithm. 894 895 SpanReader reader(buffer); 896 DepGraph<TestBitSet> depgraph; 897 uint8_t flags{1}; 898 uint64_t rng_seed{0}; 899 try { 900 reader >> rng_seed >> flags >> Using<DepGraphFormatter>(depgraph); 901 } catch (const std::ios_base::failure&) {} 902 if (depgraph.TxCount() <= 1) return; 903 InsecureRandomContext rng(rng_seed); 904 /** Whether to make the depgraph connected. */ 905 const bool make_connected = flags & 1; 906 /** Whether to load some input linearization into the state. */ 907 const bool load_linearization = flags & 2; 908 /** Whether that input linearization is topological. */ 909 const bool load_topological = load_linearization && (flags & 4); 910 911 // Initialize SFL state. 912 if (make_connected) MakeConnected(depgraph); 913 SpanningForestState sfl(depgraph, rng.rand64()); 914 915 // Function to test the state. 916 std::vector<FeeFrac> last_diagram; 917 bool was_optimal{false}; 918 auto test_fn = [&](bool is_optimal = false, bool is_minimal = false) { 919 if (rng.randbits(4) == 0) { 920 // Perform sanity checks from time to time (too computationally expensive to do after 921 // every step). 922 sfl.SanityCheck(); 923 } 924 auto diagram = sfl.GetDiagram(); 925 if (rng.randbits(4) == 0) { 926 // Verify that the diagram of GetLinearization() is at least as good as GetDiagram(), 927 // from time to time. 928 auto lin = sfl.GetLinearization(IndexTxOrder{}); 929 auto lin_diagram = ChunkLinearization(depgraph, lin); 930 auto cmp_lin = CompareChunks(lin_diagram, diagram); 931 assert(cmp_lin >= 0); 932 // If we're in an allegedly optimal state, they must match. 933 if (is_optimal) assert(cmp_lin == 0); 934 // If we're in an allegedly minimal state, they must also have the same number of 935 // segments. 936 if (is_minimal) assert(diagram.size() == lin_diagram.size()); 937 } 938 // Verify that subsequent calls to GetDiagram() never get worse/incomparable. 939 if (!last_diagram.empty()) { 940 auto cmp = CompareChunks(diagram, last_diagram); 941 assert(cmp >= 0); 942 // If the last diagram was already optimal, the new one cannot be better. 943 if (was_optimal) assert(cmp == 0); 944 // Also, if the diagram was already optimal, the number of segments can only increase. 945 if (was_optimal) assert(diagram.size() >= last_diagram.size()); 946 } 947 last_diagram = std::move(diagram); 948 was_optimal = is_optimal; 949 }; 950 951 if (load_linearization) { 952 auto input_lin = ReadLinearization(depgraph, reader, load_topological); 953 sfl.LoadLinearization(input_lin); 954 if (load_topological) { 955 // The diagram of the loaded linearization forms an initial lower bound on future 956 // diagrams. 957 last_diagram = ChunkLinearization(depgraph, input_lin); 958 } else { 959 // The input linearization may have been non-topological, so invoke MakeTopological to 960 // fix it still. 961 sfl.MakeTopological(); 962 } 963 } else { 964 // Invoke MakeTopological to create an initial from-scratch topological state. 965 sfl.MakeTopological(); 966 } 967 968 // Loop until optimal. 969 test_fn(); 970 sfl.StartOptimizing(); 971 while (true) { 972 test_fn(); 973 if (!sfl.OptimizeStep()) break; 974 } 975 976 // Loop until minimal. 977 test_fn(/*is_optimal=*/true); 978 sfl.StartMinimizing(); 979 while (true) { 980 test_fn(/*is_optimal=*/true); 981 if (!sfl.MinimizeStep()) break; 982 } 983 test_fn(/*is_optimal=*/true, /*is_minimal=*/true); 984 985 // Verify that optimality is reached within an expected amount of work. This protects against 986 // hypothetical bugs that hugely increase the amount of work needed to reach optimality. 987 assert(sfl.GetCost() <= MaxOptimalLinearizationCost(depgraph.TxCount())); 988 989 // The result must be as good as SimpleLinearize. 990 auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS / 10); 991 auto simple_diagram = ChunkLinearization(depgraph, simple_linearization); 992 auto simple_cmp = CompareChunks(last_diagram, simple_diagram); 993 assert(simple_cmp >= 0); 994 if (simple_optimal) assert(simple_cmp == 0); 995 // If the diagram matches, we must also have at least as many segments (because the SFL state 996 // and its produced diagram are minimal); 997 if (simple_cmp == 0) assert(last_diagram.size() >= simple_diagram.size()); 998 999 // We can compare with any arbitrary linearization, and the diagram must be at least as good as 1000 // each. 1001 for (int i = 0; i < 10; ++i) { 1002 auto read_lin = ReadLinearization(depgraph, reader); 1003 auto read_diagram = ChunkLinearization(depgraph, read_lin); 1004 auto cmp = CompareChunks(last_diagram, read_diagram); 1005 assert(cmp >= 0); 1006 if (cmp == 0) assert(last_diagram.size() >= read_diagram.size()); 1007 } 1008 } 1009 1010 FUZZ_TARGET(clusterlin_linearize) 1011 { 1012 // Verify the behavior of Linearize(). 1013 1014 // Retrieve an RNG seed, a maximum amount of work, a depgraph, and whether to make it connected 1015 // from the fuzz input. 1016 SpanReader reader(buffer); 1017 DepGraph<TestBitSet> depgraph; 1018 uint64_t rng_seed{0}; 1019 uint64_t max_cost{0}; 1020 uint8_t flags{7}; 1021 try { 1022 reader >> VARINT(max_cost) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> flags; 1023 } catch (const std::ios_base::failure&) {} 1024 if (depgraph.TxCount() <= 1) return; 1025 bool make_connected = flags & 1; 1026 // The following 3 booleans have 4 combinations: 1027 // - (flags & 6) == 0: do not provide input linearization. 1028 // - (flags & 6) == 2: provide potentially non-topological input. 1029 // - (flags & 6) == 4: provide topological input linearization, but do not claim it is 1030 // topological. 1031 // - (flags & 6) == 6: provide topological input linearization, and claim it is topological. 1032 bool provide_input = flags & 6; 1033 bool provide_topological_input = flags & 4; 1034 bool claim_topological_input = (flags & 6) == 6; 1035 // The most complicated graphs are connected ones (other ones just split up). Optionally force 1036 // the graph to be connected. 1037 if (make_connected) MakeConnected(depgraph); 1038 1039 // Optionally construct an old linearization for it. 1040 std::vector<DepGraphIndex> old_linearization; 1041 if (provide_input) { 1042 old_linearization = ReadLinearization(depgraph, reader, /*topological=*/provide_topological_input); 1043 if (provide_topological_input) SanityCheck(depgraph, old_linearization); 1044 } 1045 1046 // Invoke Linearize(). 1047 max_cost &= 0x3fffff; 1048 auto [linearization, optimal, cost] = Linearize( 1049 /*depgraph=*/depgraph, 1050 /*max_cost=*/max_cost, 1051 /*rng_seed=*/rng_seed, 1052 /*fallback_order=*/IndexTxOrder{}, 1053 /*old_linearization=*/old_linearization, 1054 /*is_topological=*/claim_topological_input); 1055 SanityCheck(depgraph, linearization); 1056 auto chunking = ChunkLinearization(depgraph, linearization); 1057 1058 // Linearization must always be as good as the old one, if provided and topological (even when 1059 // not claimed to be topological). 1060 if (provide_topological_input) { 1061 auto old_chunking = ChunkLinearization(depgraph, old_linearization); 1062 auto cmp = CompareChunks(chunking, old_chunking); 1063 assert(cmp >= 0); 1064 } 1065 1066 // If the maximum amount of work is sufficiently high, an optimal linearization must be found. 1067 if (max_cost > MaxOptimalLinearizationCost(depgraph.TxCount())) { 1068 assert(optimal); 1069 } 1070 1071 // If Linearize claims optimal result, run quality tests. 1072 if (optimal) { 1073 // It must be as good as SimpleLinearize. 1074 auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS); 1075 SanityCheck(depgraph, simple_linearization); 1076 auto simple_chunking = ChunkLinearization(depgraph, simple_linearization); 1077 auto cmp = CompareChunks(chunking, simple_chunking); 1078 assert(cmp >= 0); 1079 // If SimpleLinearize finds the optimal result too, they must be equal (if not, 1080 // SimpleLinearize is broken). 1081 if (simple_optimal) assert(cmp == 0); 1082 1083 // If simple_chunking is diagram-optimal, it cannot have more chunks than chunking (as 1084 // chunking is claimed to be optimal, which implies minimal chunks). 1085 if (cmp == 0) assert(chunking.size() >= simple_chunking.size()); 1086 1087 // Compare with a linearization read from the fuzz input. 1088 auto read = ReadLinearization(depgraph, reader); 1089 auto read_chunking = ChunkLinearization(depgraph, read); 1090 auto cmp_read = CompareChunks(chunking, read_chunking); 1091 assert(cmp_read >= 0); 1092 1093 // Verify that within every chunk, the transactions are in a valid order. For any pair of 1094 // transactions, it should not be possible to swap them; either due to a missing 1095 // dependency, or because the order would be inconsistent with decreasing feerate, 1096 // increasing size, and fallback order (just DepGraphIndex value here). 1097 auto chunking_info = ChunkLinearizationInfo(depgraph, linearization); 1098 /** The set of all transactions (strictly) before tx1 (see below), or (strictly) before 1099 * chunk1 (see even further below). */ 1100 TestBitSet done; 1101 unsigned pos{0}; 1102 for (const auto& chunk : chunking_info) { 1103 auto chunk_start = pos; 1104 auto chunk_end = pos + chunk.transactions.Count() - 1; 1105 // Go over all pairs of transactions. done is the set of transactions seen before pos1. 1106 for (unsigned pos1 = chunk_start; pos1 <= chunk_end; ++pos1) { 1107 auto tx1 = linearization[pos1]; 1108 for (unsigned pos2 = pos1 + 1; pos2 <= chunk_end; ++pos2) { 1109 auto tx2 = linearization[pos2]; 1110 // Check whether tx2 only depends on transactions that precede tx1. 1111 if ((depgraph.Ancestors(tx2) - done).Count() == 1) { 1112 // tx2 could take position pos1. 1113 // Verify that individual transaction feerate is decreasing (tie-breaking by 1114 // size). 1115 assert(ByRatioNegSize{depgraph.FeeRate(tx1)} >= ByRatioNegSize{depgraph.FeeRate(tx2)}); 1116 // If feerate and size are equal, compare by DepGraphIndex. 1117 if (depgraph.FeeRate(tx1) == depgraph.FeeRate(tx2)) { 1118 assert(tx1 < tx2); 1119 } 1120 } 1121 } 1122 done.Set(tx1); 1123 } 1124 pos += chunk.transactions.Count(); 1125 } 1126 1127 // Verify that chunks themselves are in a valid order. For any pair of chunks, it should 1128 // not be possible to swap them; either due to a missing dependency, or because the order 1129 // would be inconsistent with decreasing chunk feerate, increasing chunk size, and order 1130 // of maximum fallback-ordered element (just maximum DepGraphIndex element here). 1131 done = {}; 1132 // Go over all pairs of chunks. done is the set of transactions seen before chunk_num1. 1133 for (unsigned chunk_num1 = 0; chunk_num1 < chunking_info.size(); ++chunk_num1) { 1134 const auto& chunk1 = chunking_info[chunk_num1]; 1135 for (unsigned chunk_num2 = chunk_num1 + 1; chunk_num2 < chunking_info.size(); ++chunk_num2) { 1136 const auto& chunk2 = chunking_info[chunk_num2]; 1137 TestBitSet chunk2_ancestors; 1138 for (auto tx : chunk2.transactions) chunk2_ancestors |= depgraph.Ancestors(tx); 1139 // Check whether chunk2 only depends on transactions that precede chunk1. 1140 if ((chunk2_ancestors - done).IsSubsetOf(chunk2.transactions)) { 1141 // chunk2 could take position chunk_num1. 1142 // Verify that chunk feerate is decreasing (tie-breaking by size). 1143 assert(ByRatioNegSize{chunk1.feerate} >= ByRatioNegSize{chunk2.feerate}); 1144 // If feerate and size are equal, compare by maximum DepGraphIndex element. 1145 if (chunk1.feerate == chunk2.feerate) { 1146 assert(chunk1.transactions.Last() < chunk2.transactions.Last()); 1147 } 1148 } 1149 } 1150 done |= chunk1.transactions; 1151 } 1152 1153 // Redo from scratch with a different rng_seed. The resulting linearization should be 1154 // deterministic, if both are optimal. 1155 auto [linearization2, optimal2, cost2] = Linearize(depgraph, MaxOptimalLinearizationCost(depgraph.TxCount()) + 1, rng_seed ^ 0x1337, IndexTxOrder{}); 1156 assert(optimal2); 1157 assert(linearization2 == linearization); 1158 } 1159 } 1160 1161 FUZZ_TARGET(clusterlin_postlinearize) 1162 { 1163 // Verify expected properties of PostLinearize() on arbitrary linearizations. 1164 1165 // Retrieve a depgraph from the fuzz input. 1166 SpanReader reader(buffer); 1167 DepGraph<TestBitSet> depgraph; 1168 try { 1169 reader >> Using<DepGraphFormatter>(depgraph); 1170 } catch (const std::ios_base::failure&) {} 1171 1172 // Retrieve a linearization from the fuzz input. 1173 std::vector<DepGraphIndex> linearization; 1174 linearization = ReadLinearization(depgraph, reader); 1175 SanityCheck(depgraph, linearization); 1176 1177 // Produce a post-processed version. 1178 auto post_linearization = linearization; 1179 PostLinearize(depgraph, post_linearization); 1180 SanityCheck(depgraph, post_linearization); 1181 1182 // Compare diagrams: post-linearization cannot worsen anywhere. 1183 auto chunking = ChunkLinearization(depgraph, linearization); 1184 auto post_chunking = ChunkLinearization(depgraph, post_linearization); 1185 auto cmp = CompareChunks(post_chunking, chunking); 1186 assert(cmp >= 0); 1187 1188 // Run again, things can keep improving (and never get worse) 1189 auto post_post_linearization = post_linearization; 1190 PostLinearize(depgraph, post_post_linearization); 1191 SanityCheck(depgraph, post_post_linearization); 1192 auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization); 1193 cmp = CompareChunks(post_post_chunking, post_chunking); 1194 assert(cmp >= 0); 1195 1196 // The chunks that come out of postlinearizing are always connected. 1197 auto linchunking = ChunkLinearizationInfo(depgraph, post_linearization); 1198 for (const auto& [chunk_set, _chunk_feerate] : linchunking) { 1199 assert(depgraph.IsConnected(chunk_set)); 1200 } 1201 } 1202 1203 FUZZ_TARGET(clusterlin_postlinearize_tree) 1204 { 1205 // Verify expected properties of PostLinearize() on linearizations of graphs that form either 1206 // an upright or reverse tree structure. 1207 1208 // Construct a direction, RNG seed, and an arbitrary graph from the fuzz input. 1209 SpanReader reader(buffer); 1210 uint64_t rng_seed{0}; 1211 DepGraph<TestBitSet> depgraph_gen; 1212 uint8_t direction{0}; 1213 try { 1214 reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen); 1215 } catch (const std::ios_base::failure&) {} 1216 1217 auto depgraph_tree = BuildTreeGraph(depgraph_gen, direction); 1218 1219 // Retrieve a linearization from the fuzz input. 1220 std::vector<DepGraphIndex> linearization; 1221 linearization = ReadLinearization(depgraph_tree, reader); 1222 SanityCheck(depgraph_tree, linearization); 1223 1224 // Produce a postlinearized version. 1225 auto post_linearization = linearization; 1226 PostLinearize(depgraph_tree, post_linearization); 1227 SanityCheck(depgraph_tree, post_linearization); 1228 1229 // Compare diagrams. 1230 auto chunking = ChunkLinearization(depgraph_tree, linearization); 1231 auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization); 1232 auto cmp = CompareChunks(post_chunking, chunking); 1233 assert(cmp >= 0); 1234 1235 // Verify that post-linearizing again does not change the diagram. The result must be identical 1236 // as post_linearization ought to be optimal already with a tree-structured graph. 1237 auto post_post_linearization = post_linearization; 1238 PostLinearize(depgraph_tree, post_post_linearization); 1239 SanityCheck(depgraph_tree, post_post_linearization); 1240 auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization); 1241 auto cmp_post = CompareChunks(post_post_chunking, post_chunking); 1242 assert(cmp_post == 0); 1243 1244 // Try to find an even better linearization directly. This must not change the diagram for the 1245 // same reason. 1246 auto [opt_linearization, _optimal, _cost] = Linearize(depgraph_tree, 1000000, rng_seed, IndexTxOrder{}, post_linearization); 1247 auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization); 1248 auto cmp_opt = CompareChunks(opt_chunking, post_chunking); 1249 assert(cmp_opt == 0); 1250 } 1251 1252 FUZZ_TARGET(clusterlin_postlinearize_moved_leaf) 1253 { 1254 // Verify that taking an existing linearization, and moving a leaf to the back, potentially 1255 // increasing its fee, and then post-linearizing, results in something as good as the 1256 // original. This guarantees that in an RBF that replaces a transaction with one of the same 1257 // size but higher fee, applying the "remove conflicts, append new transaction, postlinearize" 1258 // process will never worsen linearization quality. 1259 1260 // Construct an arbitrary graph and a fee from the fuzz input. 1261 SpanReader reader(buffer); 1262 DepGraph<TestBitSet> depgraph; 1263 int32_t fee_inc{0}; 1264 try { 1265 uint64_t fee_inc_code; 1266 reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(fee_inc_code); 1267 fee_inc = fee_inc_code & 0x3ffff; 1268 } catch (const std::ios_base::failure&) {} 1269 if (depgraph.TxCount() == 0) return; 1270 1271 // Retrieve two linearizations from the fuzz input. 1272 auto lin = ReadLinearization(depgraph, reader); 1273 auto lin_leaf = ReadLinearization(depgraph, reader); 1274 1275 // Construct a linearization identical to lin, but with the tail end of lin_leaf moved to the 1276 // back. 1277 std::vector<DepGraphIndex> lin_moved; 1278 for (auto i : lin) { 1279 if (i != lin_leaf.back()) lin_moved.push_back(i); 1280 } 1281 lin_moved.push_back(lin_leaf.back()); 1282 1283 // Postlinearize lin_moved. 1284 PostLinearize(depgraph, lin_moved); 1285 SanityCheck(depgraph, lin_moved); 1286 1287 // Compare diagrams (applying the fee delta after computing the old one). 1288 auto old_chunking = ChunkLinearization(depgraph, lin); 1289 depgraph.FeeRate(lin_leaf.back()).fee += fee_inc; 1290 auto new_chunking = ChunkLinearization(depgraph, lin_moved); 1291 auto cmp = CompareChunks(new_chunking, old_chunking); 1292 assert(cmp >= 0); 1293 }