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 }
1294