1 // Copyright (c) The Limenka 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/fuzz.h>
10 #include <test/fuzz/FuzzedDataProvider.h>
11 #include <test/util/cluster_linearize.h>
12 #include <util/bitset.h>
13 #include <util/feefrac.h>
14 15 #include <algorithm>
16 #include <stdint.h>
17 #include <vector>
18 #include <utility>
19 20 using namespace cluster_linearize;
21 22 namespace {
23 24 /** A simple finder class for candidate sets.
25 *
26 * This class matches SearchCandidateFinder in interface and behavior, though with fewer
27 * optimizations.
28 */
29 template<typename SetType>
30 class SimpleCandidateFinder
31 {
32 /** Internal dependency graph. */
33 const DepGraph<SetType>& m_depgraph;
34 /** Which transaction are left to include. */
35 SetType m_todo;
36 37 public:
38 /** Construct an SimpleCandidateFinder for a given graph. */
39 SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
40 m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
41 42 /** Remove a set of transactions from the set of to-be-linearized ones. */
43 void MarkDone(SetType select) noexcept { m_todo -= select; }
44 45 /** Determine whether unlinearized transactions remain. */
46 bool AllDone() const noexcept { return m_todo.None(); }
47 48 /** Find a candidate set using at most max_iterations iterations, and the number of iterations
49 * actually performed. If that number is less than max_iterations, then the result is optimal.
50 *
51 * Complexity: O(N * M), where M is the number of connected topological subsets of the cluster.
52 * That number is bounded by M <= 2^(N-1).
53 */
54 std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations) const noexcept
55 {
56 uint64_t iterations_left = max_iterations;
57 // Queue of work units. Each consists of:
58 // - inc: set of transactions definitely included
59 // - und: set of transactions that can be added to inc still
60 std::vector<std::pair<SetType, SetType>> queue;
61 // Initially we have just one queue element, with the entire graph in und.
62 queue.emplace_back(SetType{}, m_todo);
63 // Best solution so far.
64 SetInfo best(m_depgraph, m_todo);
65 // Process the queue.
66 while (!queue.empty() && iterations_left) {
67 --iterations_left;
68 // Pop top element of the queue.
69 auto [inc, und] = queue.back();
70 queue.pop_back();
71 // Look for a transaction to consider adding/removing.
72 bool inc_none = inc.None();
73 for (auto split : und) {
74 // If inc is empty, consider any split transaction. Otherwise only consider
75 // transactions that share ancestry with inc so far (which means only connected
76 // sets will be considered).
77 if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) {
78 // Add a queue entry with split included.
79 SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split)));
80 queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
81 // Add a queue entry with split excluded.
82 queue.emplace_back(inc, und - m_depgraph.Descendants(split));
83 // Update statistics to account for the candidate new_inc.
84 if (new_inc.feerate > best.feerate) best = new_inc;
85 break;
86 }
87 }
88 }
89 return {std::move(best), max_iterations - iterations_left};
90 }
91 };
92 93 /** A very simple finder class for optimal candidate sets, which tries every subset.
94 *
95 * It is even simpler than SimpleCandidateFinder, and is primarily included here to test the
96 * correctness of SimpleCandidateFinder, which is then used to test the correctness of
97 * SearchCandidateFinder.
98 */
99 template<typename SetType>
100 class ExhaustiveCandidateFinder
101 {
102 /** Internal dependency graph. */
103 const DepGraph<SetType>& m_depgraph;
104 /** Which transaction are left to include. */
105 SetType m_todo;
106 107 public:
108 /** Construct an ExhaustiveCandidateFinder for a given graph. */
109 ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
110 m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
111 112 /** Remove a set of transactions from the set of to-be-linearized ones. */
113 void MarkDone(SetType select) noexcept { m_todo -= select; }
114 115 /** Determine whether unlinearized transactions remain. */
116 bool AllDone() const noexcept { return m_todo.None(); }
117 118 /** Find the optimal remaining candidate set.
119 *
120 * Complexity: O(N * 2^N).
121 */
122 SetInfo<SetType> FindCandidateSet() const noexcept
123 {
124 // Best solution so far.
125 SetInfo<SetType> best{m_todo, m_depgraph.FeeRate(m_todo)};
126 // The number of combinations to try.
127 uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1;
128 // Try the transitive closure of every non-empty subset of m_todo.
129 for (uint64_t x = 1; x < limit; ++x) {
130 // If bit number b is set in x, then the remaining ancestors of the b'th remaining
131 // transaction in m_todo are included.
132 SetType txn;
133 auto x_shifted{x};
134 for (auto i : m_todo) {
135 if (x_shifted & 1) txn |= m_depgraph.Ancestors(i);
136 x_shifted >>= 1;
137 }
138 SetInfo cur(m_depgraph, txn & m_todo);
139 if (cur.feerate > best.feerate) best = cur;
140 }
141 return best;
142 }
143 };
144 145 /** A simple linearization algorithm.
146 *
147 * This matches Linearize() in interface and behavior, though with fewer optimizations, lacking
148 * the ability to pass in an existing linearization, and using just SimpleCandidateFinder rather
149 * than AncestorCandidateFinder and SearchCandidateFinder.
150 */
151 template<typename SetType>
152 std::pair<std::vector<ClusterIndex>, bool> SimpleLinearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations)
153 {
154 std::vector<ClusterIndex> linearization;
155 SimpleCandidateFinder finder(depgraph);
156 SetType todo = depgraph.Positions();
157 bool optimal = true;
158 while (todo.Any()) {
159 auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
160 if (iterations_done == max_iterations) optimal = false;
161 depgraph.AppendTopo(linearization, candidate.transactions);
162 todo -= candidate.transactions;
163 finder.MarkDone(candidate.transactions);
164 max_iterations -= iterations_done;
165 }
166 return {std::move(linearization), optimal};
167 }
168 169 /** Stitch connected components together in a DepGraph, guaranteeing its corresponding cluster is connected. */
170 template<typename BS>
171 void MakeConnected(DepGraph<BS>& depgraph)
172 {
173 auto todo = depgraph.Positions();
174 auto comp = depgraph.FindConnectedComponent(todo);
175 Assume(depgraph.IsConnected(comp));
176 todo -= comp;
177 while (todo.Any()) {
178 auto nextcomp = depgraph.FindConnectedComponent(todo);
179 Assume(depgraph.IsConnected(nextcomp));
180 depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
181 todo -= nextcomp;
182 comp = nextcomp;
183 }
184 }
185 186 /** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */
187 template<typename SetType>
188 SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& todo, SpanReader& reader)
189 {
190 uint64_t mask{0};
191 try {
192 reader >> VARINT(mask);
193 } catch(const std::ios_base::failure&) {}
194 SetType ret;
195 for (auto i : todo) {
196 if (!ret[i]) {
197 if (mask & 1) ret |= depgraph.Ancestors(i);
198 mask >>= 1;
199 }
200 }
201 return ret & todo;
202 }
203 204 /** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */
205 template<typename BS>
206 std::vector<ClusterIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader)
207 {
208 std::vector<ClusterIndex> linearization;
209 TestBitSet todo = depgraph.Positions();
210 // In every iteration one topologically-valid transaction is appended to linearization.
211 while (todo.Any()) {
212 // Compute the set of transactions with no not-yet-included ancestors.
213 TestBitSet potential_next;
214 for (auto j : todo) {
215 if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
216 potential_next.Set(j);
217 }
218 }
219 // There must always be one (otherwise there is a cycle in the graph).
220 assert(potential_next.Any());
221 // Read a number from reader, and interpret it as index into potential_next.
222 uint64_t idx{0};
223 try {
224 reader >> VARINT(idx);
225 } catch (const std::ios_base::failure&) {}
226 idx %= potential_next.Count();
227 // Find out which transaction that corresponds to.
228 for (auto j : potential_next) {
229 if (idx == 0) {
230 // When found, add it to linearization and remove it from todo.
231 linearization.push_back(j);
232 assert(todo[j]);
233 todo.Reset(j);
234 break;
235 }
236 --idx;
237 }
238 }
239 return linearization;
240 }
241 242 } // namespace
243 244 FUZZ_TARGET(clusterlin_depgraph_sim)
245 {
246 // Simulation test to verify the full behavior of DepGraph.
247 248 FuzzedDataProvider provider(buffer.data(), buffer.size());
249 250 /** Real DepGraph being tested. */
251 DepGraph<TestBitSet> real;
252 /** Simulated DepGraph (sim[i] is std::nullopt if position i does not exist; otherwise,
253 * sim[i]->first is its individual feerate, and sim[i]->second is its set of ancestors. */
254 std::array<std::optional<std::pair<FeeFrac, TestBitSet>>, TestBitSet::Size()> sim;
255 /** The number of non-nullopt position in sim. */
256 ClusterIndex num_tx_sim{0};
257 258 /** Read a valid index of a transaction from the provider. */
259 auto idx_fn = [&]() {
260 auto offset = provider.ConsumeIntegralInRange<ClusterIndex>(0, num_tx_sim - 1);
261 for (ClusterIndex i = 0; i < sim.size(); ++i) {
262 if (!sim[i].has_value()) continue;
263 if (offset == 0) return i;
264 --offset;
265 }
266 assert(false);
267 return ClusterIndex(-1);
268 };
269 270 /** Read a valid subset of the transactions from the provider. */
271 auto subset_fn = [&]() {
272 auto range = (uint64_t{1} << num_tx_sim) - 1;
273 const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
274 auto mask_shifted = mask;
275 TestBitSet subset;
276 for (ClusterIndex i = 0; i < sim.size(); ++i) {
277 if (!sim[i].has_value()) continue;
278 if (mask_shifted & 1) {
279 subset.Set(i);
280 }
281 mask_shifted >>= 1;
282 }
283 assert(mask_shifted == 0);
284 return subset;
285 };
286 287 /** Read any set of transactions from the provider (including unused positions). */
288 auto set_fn = [&]() {
289 auto range = (uint64_t{1} << sim.size()) - 1;
290 const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
291 TestBitSet set;
292 for (ClusterIndex i = 0; i < sim.size(); ++i) {
293 if ((mask >> i) & 1) {
294 set.Set(i);
295 }
296 }
297 return set;
298 };
299 300 /** Propagate ancestor information in sim. */
301 auto anc_update_fn = [&]() {
302 while (true) {
303 bool updates{false};
304 for (ClusterIndex chl = 0; chl < sim.size(); ++chl) {
305 if (!sim[chl].has_value()) continue;
306 for (auto par : sim[chl]->second) {
307 if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) {
308 sim[chl]->second |= sim[par]->second;
309 updates = true;
310 }
311 }
312 }
313 if (!updates) break;
314 }
315 };
316 317 /** Compare the state of transaction i in the simulation with the real one. */
318 auto check_fn = [&](ClusterIndex i) {
319 // Compare used positions.
320 assert(real.Positions()[i] == sim[i].has_value());
321 if (sim[i].has_value()) {
322 // Compare feerate.
323 assert(real.FeeRate(i) == sim[i]->first);
324 // Compare ancestors (note that SanityCheck verifies correspondence between ancestors
325 // and descendants, so we can restrict ourselves to ancestors here).
326 assert(real.Ancestors(i) == sim[i]->second);
327 }
328 };
329 330 LIMITED_WHILE(provider.remaining_bytes() > 0, 1000) {
331 uint8_t command = provider.ConsumeIntegral<uint8_t>();
332 if (num_tx_sim == 0 || ((command % 3) <= 0 && num_tx_sim < TestBitSet::Size())) {
333 // AddTransaction.
334 auto fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
335 auto size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
336 FeeFrac feerate{fee, size};
337 // Apply to DepGraph.
338 auto idx = real.AddTransaction(feerate);
339 // Verify that the returned index is correct.
340 assert(!sim[idx].has_value());
341 for (ClusterIndex i = 0; i < TestBitSet::Size(); ++i) {
342 if (!sim[i].has_value()) {
343 assert(idx == i);
344 break;
345 }
346 }
347 // Update sim.
348 sim[idx] = {feerate, TestBitSet::Singleton(idx)};
349 ++num_tx_sim;
350 continue;
351 }
352 if ((command % 3) <= 1 && num_tx_sim > 0) {
353 // AddDependencies.
354 ClusterIndex child = idx_fn();
355 auto parents = subset_fn();
356 // Apply to DepGraph.
357 real.AddDependencies(parents, child);
358 // Apply to sim.
359 sim[child]->second |= parents;
360 continue;
361 }
362 if (num_tx_sim > 0) {
363 // Remove transactions.
364 auto del = set_fn();
365 // Propagate all ancestry information before deleting anything in the simulation (as
366 // intermediary transactions may be deleted which impact connectivity).
367 anc_update_fn();
368 // Compare the state of the transactions being deleted.
369 for (auto i : del) check_fn(i);
370 // Apply to DepGraph.
371 real.RemoveTransactions(del);
372 // Apply to sim.
373 for (ClusterIndex i = 0; i < sim.size(); ++i) {
374 if (sim[i].has_value()) {
375 if (del[i]) {
376 --num_tx_sim;
377 sim[i] = std::nullopt;
378 } else {
379 sim[i]->second -= del;
380 }
381 }
382 }
383 continue;
384 }
385 // This should be unreachable (one of the 3 above actions should always be possible).
386 assert(false);
387 }
388 389 // Compare the real obtained depgraph against the simulation.
390 anc_update_fn();
391 for (ClusterIndex i = 0; i < sim.size(); ++i) check_fn(i);
392 assert(real.TxCount() == num_tx_sim);
393 // Sanity check the result (which includes round-tripping serialization, if applicable).
394 SanityCheck(real);
395 }
396 397 FUZZ_TARGET(clusterlin_depgraph_serialization)
398 {
399 // Verify that any deserialized depgraph is acyclic and roundtrips to an identical depgraph.
400 401 // Construct a graph by deserializing.
402 SpanReader reader(buffer);
403 DepGraph<TestBitSet> depgraph;
404 try {
405 reader >> Using<DepGraphFormatter>(depgraph);
406 } catch (const std::ios_base::failure&) {}
407 SanityCheck(depgraph);
408 409 // Verify the graph is a DAG.
410 assert(IsAcyclic(depgraph));
411 }
412 413 FUZZ_TARGET(clusterlin_components)
414 {
415 // Verify the behavior of DepGraphs's FindConnectedComponent and IsConnected functions.
416 417 // Construct a depgraph.
418 SpanReader reader(buffer);
419 DepGraph<TestBitSet> depgraph;
420 try {
421 reader >> Using<DepGraphFormatter>(depgraph);
422 } catch (const std::ios_base::failure&) {}
423 424 TestBitSet todo = depgraph.Positions();
425 while (todo.Any()) {
426 // Find a connected component inside todo.
427 auto component = depgraph.FindConnectedComponent(todo);
428 429 // The component must be a subset of todo and non-empty.
430 assert(component.IsSubsetOf(todo));
431 assert(component.Any());
432 433 // If todo is the entire graph, and the entire graph is connected, then the component must
434 // be the entire graph.
435 if (todo == depgraph.Positions()) {
436 assert((component == todo) == depgraph.IsConnected());
437 }
438 439 // If subset is connected, then component must match subset.
440 assert((component == todo) == depgraph.IsConnected(todo));
441 442 // The component cannot have any ancestors or descendants outside of component but in todo.
443 for (auto i : component) {
444 assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component));
445 assert((depgraph.Descendants(i) & todo).IsSubsetOf(component));
446 }
447 448 // Starting from any component element, we must be able to reach every element.
449 for (auto i : component) {
450 // Start with just i as reachable.
451 TestBitSet reachable = TestBitSet::Singleton(i);
452 // Add in-todo descendants and ancestors to reachable until it does not change anymore.
453 while (true) {
454 TestBitSet new_reachable = reachable;
455 for (auto j : new_reachable) {
456 new_reachable |= depgraph.Ancestors(j) & todo;
457 new_reachable |= depgraph.Descendants(j) & todo;
458 }
459 if (new_reachable == reachable) break;
460 reachable = new_reachable;
461 }
462 // Verify that the result is the entire component.
463 assert(component == reachable);
464 }
465 466 // Construct an arbitrary subset of todo.
467 uint64_t subset_bits{0};
468 try {
469 reader >> VARINT(subset_bits);
470 } catch (const std::ios_base::failure&) {}
471 TestBitSet subset;
472 for (ClusterIndex i : depgraph.Positions()) {
473 if (todo[i]) {
474 if (subset_bits & 1) subset.Set(i);
475 subset_bits >>= 1;
476 }
477 }
478 // Which must be non-empty.
479 if (subset.None()) subset = TestBitSet::Singleton(todo.First());
480 // Remove it from todo.
481 todo -= subset;
482 }
483 484 // No components can be found in an empty subset.
485 assert(depgraph.FindConnectedComponent(todo).None());
486 }
487 488 FUZZ_TARGET(clusterlin_make_connected)
489 {
490 // Verify that MakeConnected makes graphs connected.
491 492 SpanReader reader(buffer);
493 DepGraph<TestBitSet> depgraph;
494 try {
495 reader >> Using<DepGraphFormatter>(depgraph);
496 } catch (const std::ios_base::failure&) {}
497 MakeConnected(depgraph);
498 SanityCheck(depgraph);
499 assert(depgraph.IsConnected());
500 }
501 502 FUZZ_TARGET(clusterlin_chunking)
503 {
504 // Verify the correctness of the ChunkLinearization function.
505 506 // Construct a graph by deserializing.
507 SpanReader reader(buffer);
508 DepGraph<TestBitSet> depgraph;
509 try {
510 reader >> Using<DepGraphFormatter>(depgraph);
511 } catch (const std::ios_base::failure&) {}
512 513 // Read a valid linearization for depgraph.
514 auto linearization = ReadLinearization(depgraph, reader);
515 516 // Invoke the chunking function.
517 auto chunking = ChunkLinearization(depgraph, linearization);
518 519 // Verify that chunk feerates are monotonically non-increasing.
520 for (size_t i = 1; i < chunking.size(); ++i) {
521 assert(!(chunking[i] >> chunking[i - 1]));
522 }
523 524 // Naively recompute the chunks (each is the highest-feerate prefix of what remains).
525 auto todo = depgraph.Positions();
526 for (const auto& chunk_feerate : chunking) {
527 assert(todo.Any());
528 SetInfo<TestBitSet> accumulator, best;
529 for (ClusterIndex idx : linearization) {
530 if (todo[idx]) {
531 accumulator.Set(depgraph, idx);
532 if (best.feerate.IsEmpty() || accumulator.feerate >> best.feerate) {
533 best = accumulator;
534 }
535 }
536 }
537 assert(chunk_feerate == best.feerate);
538 assert(best.transactions.IsSubsetOf(todo));
539 todo -= best.transactions;
540 }
541 assert(todo.None());
542 }
543 544 FUZZ_TARGET(clusterlin_ancestor_finder)
545 {
546 // Verify that AncestorCandidateFinder works as expected.
547 548 // Retrieve a depgraph from the fuzz input.
549 SpanReader reader(buffer);
550 DepGraph<TestBitSet> depgraph;
551 try {
552 reader >> Using<DepGraphFormatter>(depgraph);
553 } catch (const std::ios_base::failure&) {}
554 555 AncestorCandidateFinder anc_finder(depgraph);
556 auto todo = depgraph.Positions();
557 while (todo.Any()) {
558 // Call the ancestor finder's FindCandidateSet for what remains of the graph.
559 assert(!anc_finder.AllDone());
560 assert(todo.Count() == anc_finder.NumRemaining());
561 auto best_anc = anc_finder.FindCandidateSet();
562 // Sanity check the result.
563 assert(best_anc.transactions.Any());
564 assert(best_anc.transactions.IsSubsetOf(todo));
565 assert(depgraph.FeeRate(best_anc.transactions) == best_anc.feerate);
566 assert(depgraph.IsConnected(best_anc.transactions));
567 // Check that it is topologically valid.
568 for (auto i : best_anc.transactions) {
569 assert((depgraph.Ancestors(i) & todo).IsSubsetOf(best_anc.transactions));
570 }
571 572 // Compute all remaining ancestor sets.
573 std::optional<SetInfo<TestBitSet>> real_best_anc;
574 for (auto i : todo) {
575 SetInfo info(depgraph, todo & depgraph.Ancestors(i));
576 if (!real_best_anc.has_value() || info.feerate > real_best_anc->feerate) {
577 real_best_anc = info;
578 }
579 }
580 // The set returned by anc_finder must equal the real best ancestor sets.
581 assert(real_best_anc.has_value());
582 assert(*real_best_anc == best_anc);
583 584 // Find a topologically valid subset of transactions to remove from the graph.
585 auto del_set = ReadTopologicalSet(depgraph, todo, reader);
586 // If we did not find anything, use best_anc itself, because we should remove something.
587 if (del_set.None()) del_set = best_anc.transactions;
588 todo -= del_set;
589 anc_finder.MarkDone(del_set);
590 }
591 assert(anc_finder.AllDone());
592 assert(anc_finder.NumRemaining() == 0);
593 }
594 595 static constexpr auto MAX_SIMPLE_ITERATIONS = 300000;
596 597 FUZZ_TARGET(clusterlin_search_finder)
598 {
599 // Verify that SearchCandidateFinder works as expected by sanity checking the results
600 // and comparing with the results from SimpleCandidateFinder, ExhaustiveCandidateFinder, and
601 // AncestorCandidateFinder.
602 603 // Retrieve an RNG seed, a depgraph, and whether to make it connected, from the fuzz input.
604 SpanReader reader(buffer);
605 DepGraph<TestBitSet> depgraph;
606 uint64_t rng_seed{0};
607 uint8_t make_connected{1};
608 try {
609 reader >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
610 } catch (const std::ios_base::failure&) {}
611 // The most complicated graphs are connected ones (other ones just split up). Optionally force
612 // the graph to be connected.
613 if (make_connected) MakeConnected(depgraph);
614 615 // Instantiate ALL the candidate finders.
616 SearchCandidateFinder src_finder(depgraph, rng_seed);
617 SimpleCandidateFinder smp_finder(depgraph);
618 ExhaustiveCandidateFinder exh_finder(depgraph);
619 AncestorCandidateFinder anc_finder(depgraph);
620 621 auto todo = depgraph.Positions();
622 while (todo.Any()) {
623 assert(!src_finder.AllDone());
624 assert(!smp_finder.AllDone());
625 assert(!exh_finder.AllDone());
626 assert(!anc_finder.AllDone());
627 assert(anc_finder.NumRemaining() == todo.Count());
628 629 // For each iteration, read an iteration count limit from the fuzz input.
630 uint64_t max_iterations = 1;
631 try {
632 reader >> VARINT(max_iterations);
633 } catch (const std::ios_base::failure&) {}
634 max_iterations &= 0xfffff;
635 636 // Read an initial subset from the fuzz input.
637 SetInfo init_best(depgraph, ReadTopologicalSet(depgraph, todo, reader));
638 639 // Call the search finder's FindCandidateSet for what remains of the graph.
640 auto [found, iterations_done] = src_finder.FindCandidateSet(max_iterations, init_best);
641 642 // Sanity check the result.
643 assert(iterations_done <= max_iterations);
644 assert(found.transactions.Any());
645 assert(found.transactions.IsSubsetOf(todo));
646 assert(depgraph.FeeRate(found.transactions) == found.feerate);
647 if (!init_best.feerate.IsEmpty()) assert(found.feerate >= init_best.feerate);
648 // Check that it is topologically valid.
649 for (auto i : found.transactions) {
650 assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo));
651 }
652 653 // At most 2^(N-1) iterations can be required: the maximum number of non-empty topological
654 // subsets a (connected) cluster with N transactions can have. Even when the cluster is no
655 // longer connected after removing certain transactions, this holds, because the connected
656 // components are searched separately.
657 assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
658 // Additionally, test that no more than sqrt(2^N)+1 iterations are required. This is just
659 // an empirical bound that seems to hold, without proof. Still, add a test for it so we
660 // can learn about counterexamples if they exist.
661 if (iterations_done >= 1 && todo.Count() <= 63) {
662 Assume((iterations_done - 1) * (iterations_done - 1) <= uint64_t{1} << todo.Count());
663 }
664 665 // Perform quality checks only if SearchCandidateFinder claims an optimal result.
666 if (iterations_done < max_iterations) {
667 // Optimal sets are always connected.
668 assert(depgraph.IsConnected(found.transactions));
669 670 // Compare with SimpleCandidateFinder.
671 auto [simple, simple_iters] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
672 assert(found.feerate >= simple.feerate);
673 if (simple_iters < MAX_SIMPLE_ITERATIONS) {
674 assert(found.feerate == simple.feerate);
675 }
676 677 // Compare with AncestorCandidateFinder;
678 auto anc = anc_finder.FindCandidateSet();
679 assert(found.feerate >= anc.feerate);
680 681 // Compare with ExhaustiveCandidateFinder. This quickly gets computationally expensive
682 // for large clusters (O(2^n)), so only do it for sufficiently small ones.
683 if (todo.Count() <= 12) {
684 auto exhaustive = exh_finder.FindCandidateSet();
685 assert(exhaustive.feerate == found.feerate);
686 // Also compare ExhaustiveCandidateFinder with SimpleCandidateFinder (this is
687 // primarily a test for SimpleCandidateFinder's correctness).
688 assert(exhaustive.feerate >= simple.feerate);
689 if (simple_iters < MAX_SIMPLE_ITERATIONS) {
690 assert(exhaustive.feerate == simple.feerate);
691 }
692 }
693 }
694 695 // Find a topologically valid subset of transactions to remove from the graph.
696 auto del_set = ReadTopologicalSet(depgraph, todo, reader);
697 // If we did not find anything, use found itself, because we should remove something.
698 if (del_set.None()) del_set = found.transactions;
699 todo -= del_set;
700 src_finder.MarkDone(del_set);
701 smp_finder.MarkDone(del_set);
702 exh_finder.MarkDone(del_set);
703 anc_finder.MarkDone(del_set);
704 }
705 706 assert(src_finder.AllDone());
707 assert(smp_finder.AllDone());
708 assert(exh_finder.AllDone());
709 assert(anc_finder.AllDone());
710 assert(anc_finder.NumRemaining() == 0);
711 }
712 713 FUZZ_TARGET(clusterlin_linearization_chunking)
714 {
715 // Verify the behavior of LinearizationChunking.
716 717 // Retrieve a depgraph from the fuzz input.
718 SpanReader reader(buffer);
719 DepGraph<TestBitSet> depgraph;
720 try {
721 reader >> Using<DepGraphFormatter>(depgraph);
722 } catch (const std::ios_base::failure&) {}
723 724 // Retrieve a topologically-valid subset of depgraph.
725 auto todo = depgraph.Positions();
726 auto subset = SetInfo(depgraph, ReadTopologicalSet(depgraph, todo, reader));
727 728 // Retrieve a valid linearization for depgraph.
729 auto linearization = ReadLinearization(depgraph, reader);
730 731 // Construct a LinearizationChunking object, initially for the whole linearization.
732 LinearizationChunking chunking(depgraph, linearization);
733 734 // Incrementally remove transactions from the chunking object, and check various properties at
735 // every step.
736 while (todo.Any()) {
737 assert(chunking.NumChunksLeft() > 0);
738 739 // Construct linearization with just todo.
740 std::vector<ClusterIndex> linearization_left;
741 for (auto i : linearization) {
742 if (todo[i]) linearization_left.push_back(i);
743 }
744 745 // Compute the chunking for linearization_left.
746 auto chunking_left = ChunkLinearization(depgraph, linearization_left);
747 748 // Verify that it matches the feerates of the chunks of chunking.
749 assert(chunking.NumChunksLeft() == chunking_left.size());
750 for (ClusterIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
751 assert(chunking.GetChunk(i).feerate == chunking_left[i]);
752 }
753 754 // Check consistency of chunking.
755 TestBitSet combined;
756 for (ClusterIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
757 const auto& chunk_info = chunking.GetChunk(i);
758 // Chunks must be non-empty.
759 assert(chunk_info.transactions.Any());
760 // Chunk feerates must be monotonically non-increasing.
761 if (i > 0) assert(!(chunk_info.feerate >> chunking.GetChunk(i - 1).feerate));
762 // Chunks must be a subset of what is left of the linearization.
763 assert(chunk_info.transactions.IsSubsetOf(todo));
764 // Chunks' claimed feerates must match their transactions' aggregate feerate.
765 assert(depgraph.FeeRate(chunk_info.transactions) == chunk_info.feerate);
766 // Chunks must be the highest-feerate remaining prefix.
767 SetInfo<TestBitSet> accumulator, best;
768 for (auto j : linearization) {
769 if (todo[j] && !combined[j]) {
770 accumulator.Set(depgraph, j);
771 if (best.feerate.IsEmpty() || accumulator.feerate > best.feerate) {
772 best = accumulator;
773 }
774 }
775 }
776 assert(best.transactions == chunk_info.transactions);
777 assert(best.feerate == chunk_info.feerate);
778 // Chunks cannot overlap.
779 assert(!chunk_info.transactions.Overlaps(combined));
780 combined |= chunk_info.transactions;
781 // Chunks must be topological.
782 for (auto idx : chunk_info.transactions) {
783 assert((depgraph.Ancestors(idx) & todo).IsSubsetOf(combined));
784 }
785 }
786 assert(combined == todo);
787 788 // Verify the expected properties of LinearizationChunking::IntersectPrefixes:
789 auto intersect = chunking.IntersectPrefixes(subset);
790 // - Intersecting again doesn't change the result.
791 assert(chunking.IntersectPrefixes(intersect) == intersect);
792 // - The intersection is topological.
793 TestBitSet intersect_anc;
794 for (auto idx : intersect.transactions) {
795 intersect_anc |= (depgraph.Ancestors(idx) & todo);
796 }
797 assert(intersect.transactions == intersect_anc);
798 // - The claimed intersection feerate matches its transactions.
799 assert(intersect.feerate == depgraph.FeeRate(intersect.transactions));
800 // - The intersection may only be empty if its input is empty.
801 assert(intersect.transactions.Any() == subset.transactions.Any());
802 // - The intersection feerate must be as high as the input.
803 assert(intersect.feerate >= subset.feerate);
804 // - No non-empty intersection between the intersection and a prefix of the chunks of the
805 // remainder of the linearization may be better than the intersection.
806 TestBitSet prefix;
807 for (ClusterIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
808 prefix |= chunking.GetChunk(i).transactions;
809 auto reintersect = SetInfo(depgraph, prefix & intersect.transactions);
810 if (!reintersect.feerate.IsEmpty()) {
811 assert(reintersect.feerate <= intersect.feerate);
812 }
813 }
814 815 // Find a subset to remove from linearization.
816 auto done = ReadTopologicalSet(depgraph, todo, reader);
817 if (done.None()) {
818 // We need to remove a non-empty subset, so fall back to the unlinearized ancestors of
819 // the first transaction in todo if done is empty.
820 done = depgraph.Ancestors(todo.First()) & todo;
821 }
822 todo -= done;
823 chunking.MarkDone(done);
824 subset = SetInfo(depgraph, subset.transactions - done);
825 }
826 827 assert(chunking.NumChunksLeft() == 0);
828 }
829 830 FUZZ_TARGET(clusterlin_linearize)
831 {
832 // Verify the behavior of Linearize().
833 834 // Retrieve an RNG seed, an iteration count, a depgraph, and whether to make it connected from
835 // the fuzz input.
836 SpanReader reader(buffer);
837 DepGraph<TestBitSet> depgraph;
838 uint64_t rng_seed{0};
839 uint64_t iter_count{0};
840 uint8_t make_connected{1};
841 try {
842 reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
843 } catch (const std::ios_base::failure&) {}
844 // The most complicated graphs are connected ones (other ones just split up). Optionally force
845 // the graph to be connected.
846 if (make_connected) MakeConnected(depgraph);
847 848 // Optionally construct an old linearization for it.
849 std::vector<ClusterIndex> old_linearization;
850 {
851 uint8_t have_old_linearization{0};
852 try {
853 reader >> have_old_linearization;
854 } catch(const std::ios_base::failure&) {}
855 if (have_old_linearization & 1) {
856 old_linearization = ReadLinearization(depgraph, reader);
857 SanityCheck(depgraph, old_linearization);
858 }
859 }
860 861 // Invoke Linearize().
862 iter_count &= 0x7ffff;
863 auto [linearization, optimal] = Linearize(depgraph, iter_count, rng_seed, old_linearization);
864 SanityCheck(depgraph, linearization);
865 auto chunking = ChunkLinearization(depgraph, linearization);
866 867 // Linearization must always be as good as the old one, if provided.
868 if (!old_linearization.empty()) {
869 auto old_chunking = ChunkLinearization(depgraph, old_linearization);
870 auto cmp = CompareChunks(chunking, old_chunking);
871 assert(cmp >= 0);
872 }
873 874 // If the iteration count is sufficiently high, an optimal linearization must be found.
875 // Each linearization step can use up to 2^(k-1) iterations, with steps k=1..n. That sum is
876 // 2^n - 1.
877 const uint64_t n = depgraph.TxCount();
878 if (n <= 19 && iter_count > (uint64_t{1} << n)) {
879 assert(optimal);
880 }
881 // Additionally, if the assumption of sqrt(2^k)+1 iterations per step holds, plus ceil(k/4)
882 // start-up cost per step, plus ceil(n^2/64) start-up cost overall, we can compute the upper
883 // bound for a whole linearization (summing for k=1..n) using the Python expression
884 // [sum((k+3)//4 + int(math.sqrt(2**k)) + 1 for k in range(1, n + 1)) + (n**2 + 63) // 64 for n in range(0, 35)]:
885 static constexpr uint64_t MAX_OPTIMAL_ITERS[] = {
886 0, 4, 8, 12, 18, 26, 37, 51, 70, 97, 133, 182, 251, 346, 480, 666, 927, 1296, 1815, 2545,
887 3576, 5031, 7087, 9991, 14094, 19895, 28096, 39690, 56083, 79263, 112041, 158391, 223936,
888 316629, 447712
889 };
890 if (n < std::size(MAX_OPTIMAL_ITERS) && iter_count >= MAX_OPTIMAL_ITERS[n]) {
891 Assume(optimal);
892 }
893 894 // If Linearize claims optimal result, run quality tests.
895 if (optimal) {
896 // It must be as good as SimpleLinearize.
897 auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS);
898 SanityCheck(depgraph, simple_linearization);
899 auto simple_chunking = ChunkLinearization(depgraph, simple_linearization);
900 auto cmp = CompareChunks(chunking, simple_chunking);
901 assert(cmp >= 0);
902 // If SimpleLinearize finds the optimal result too, they must be equal (if not,
903 // SimpleLinearize is broken).
904 if (simple_optimal) assert(cmp == 0);
905 906 // Only for very small clusters, test every topologically-valid permutation.
907 if (depgraph.TxCount() <= 7) {
908 std::vector<ClusterIndex> perm_linearization;
909 for (ClusterIndex i : depgraph.Positions()) perm_linearization.push_back(i);
910 // Iterate over all valid permutations.
911 do {
912 // Determine whether perm_linearization is topological.
913 TestBitSet perm_done;
914 bool perm_is_topo{true};
915 for (auto i : perm_linearization) {
916 perm_done.Set(i);
917 if (!depgraph.Ancestors(i).IsSubsetOf(perm_done)) {
918 perm_is_topo = false;
919 break;
920 }
921 }
922 // If so, verify that the obtained linearization is as good as the permutation.
923 if (perm_is_topo) {
924 auto perm_chunking = ChunkLinearization(depgraph, perm_linearization);
925 auto cmp = CompareChunks(chunking, perm_chunking);
926 assert(cmp >= 0);
927 }
928 } while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
929 }
930 }
931 }
932 933 FUZZ_TARGET(clusterlin_postlinearize)
934 {
935 // Verify expected properties of PostLinearize() on arbitrary linearizations.
936 937 // Retrieve a depgraph from the fuzz input.
938 SpanReader reader(buffer);
939 DepGraph<TestBitSet> depgraph;
940 try {
941 reader >> Using<DepGraphFormatter>(depgraph);
942 } catch (const std::ios_base::failure&) {}
943 944 // Retrieve a linearization from the fuzz input.
945 std::vector<ClusterIndex> linearization;
946 linearization = ReadLinearization(depgraph, reader);
947 SanityCheck(depgraph, linearization);
948 949 // Produce a post-processed version.
950 auto post_linearization = linearization;
951 PostLinearize(depgraph, post_linearization);
952 SanityCheck(depgraph, post_linearization);
953 954 // Compare diagrams: post-linearization cannot worsen anywhere.
955 auto chunking = ChunkLinearization(depgraph, linearization);
956 auto post_chunking = ChunkLinearization(depgraph, post_linearization);
957 auto cmp = CompareChunks(post_chunking, chunking);
958 assert(cmp >= 0);
959 960 // Run again, things can keep improving (and never get worse)
961 auto post_post_linearization = post_linearization;
962 PostLinearize(depgraph, post_post_linearization);
963 SanityCheck(depgraph, post_post_linearization);
964 auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization);
965 cmp = CompareChunks(post_post_chunking, post_chunking);
966 assert(cmp >= 0);
967 968 // The chunks that come out of postlinearizing are always connected.
969 LinearizationChunking linchunking(depgraph, post_linearization);
970 while (linchunking.NumChunksLeft()) {
971 assert(depgraph.IsConnected(linchunking.GetChunk(0).transactions));
972 linchunking.MarkDone(linchunking.GetChunk(0).transactions);
973 }
974 }
975 976 FUZZ_TARGET(clusterlin_postlinearize_tree)
977 {
978 // Verify expected properties of PostLinearize() on linearizations of graphs that form either
979 // an upright or reverse tree structure.
980 981 // Construct a direction, RNG seed, and an arbitrary graph from the fuzz input.
982 SpanReader reader(buffer);
983 uint64_t rng_seed{0};
984 DepGraph<TestBitSet> depgraph_gen;
985 uint8_t direction{0};
986 try {
987 reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen);
988 } catch (const std::ios_base::failure&) {}
989 990 // Now construct a new graph, copying the nodes, but leaving only the first parent (even
991 // direction) or the first child (odd direction).
992 DepGraph<TestBitSet> depgraph_tree;
993 for (ClusterIndex i = 0; i < depgraph_gen.PositionRange(); ++i) {
994 if (depgraph_gen.Positions()[i]) {
995 depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i));
996 } else {
997 // For holes, add a dummy transaction which is deleted below, so that non-hole
998 // transactions retain their position.
999 depgraph_tree.AddTransaction(FeeFrac{});
1000 }
1001 }
1002 depgraph_tree.RemoveTransactions(TestBitSet::Fill(depgraph_gen.PositionRange()) - depgraph_gen.Positions());
1003 1004 if (direction & 1) {
1005 for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1006 auto children = depgraph_gen.GetReducedChildren(i);
1007 if (children.Any()) {
1008 depgraph_tree.AddDependencies(TestBitSet::Singleton(i), children.First());
1009 }
1010 }
1011 } else {
1012 for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1013 auto parents = depgraph_gen.GetReducedParents(i);
1014 if (parents.Any()) {
1015 depgraph_tree.AddDependencies(TestBitSet::Singleton(parents.First()), i);
1016 }
1017 }
1018 }
1019 1020 // Retrieve a linearization from the fuzz input.
1021 std::vector<ClusterIndex> linearization;
1022 linearization = ReadLinearization(depgraph_tree, reader);
1023 SanityCheck(depgraph_tree, linearization);
1024 1025 // Produce a postlinearized version.
1026 auto post_linearization = linearization;
1027 PostLinearize(depgraph_tree, post_linearization);
1028 SanityCheck(depgraph_tree, post_linearization);
1029 1030 // Compare diagrams.
1031 auto chunking = ChunkLinearization(depgraph_tree, linearization);
1032 auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization);
1033 auto cmp = CompareChunks(post_chunking, chunking);
1034 assert(cmp >= 0);
1035 1036 // Verify that post-linearizing again does not change the diagram. The result must be identical
1037 // as post_linearization ought to be optimal already with a tree-structured graph.
1038 auto post_post_linearization = post_linearization;
1039 PostLinearize(depgraph_tree, post_linearization);
1040 SanityCheck(depgraph_tree, post_linearization);
1041 auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization);
1042 auto cmp_post = CompareChunks(post_post_chunking, post_chunking);
1043 assert(cmp_post == 0);
1044 1045 // Try to find an even better linearization directly. This must not change the diagram for the
1046 // same reason.
1047 auto [opt_linearization, _optimal] = Linearize(depgraph_tree, 100000, rng_seed, post_linearization);
1048 auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization);
1049 auto cmp_opt = CompareChunks(opt_chunking, post_chunking);
1050 assert(cmp_opt == 0);
1051 }
1052 1053 FUZZ_TARGET(clusterlin_postlinearize_moved_leaf)
1054 {
1055 // Verify that taking an existing linearization, and moving a leaf to the back, potentially
1056 // increasing its fee, and then post-linearizing, results in something as good as the
1057 // original. This guarantees that in an RBF that replaces a transaction with one of the same
1058 // size but higher fee, applying the "remove conflicts, append new transaction, postlinearize"
1059 // process will never worsen linearization quality.
1060 1061 // Construct an arbitrary graph and a fee from the fuzz input.
1062 SpanReader reader(buffer);
1063 DepGraph<TestBitSet> depgraph;
1064 int32_t fee_inc{0};
1065 try {
1066 uint64_t fee_inc_code;
1067 reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(fee_inc_code);
1068 fee_inc = fee_inc_code & 0x3ffff;
1069 } catch (const std::ios_base::failure&) {}
1070 if (depgraph.TxCount() == 0) return;
1071 1072 // Retrieve two linearizations from the fuzz input.
1073 auto lin = ReadLinearization(depgraph, reader);
1074 auto lin_leaf = ReadLinearization(depgraph, reader);
1075 1076 // Construct a linearization identical to lin, but with the tail end of lin_leaf moved to the
1077 // back.
1078 std::vector<ClusterIndex> lin_moved;
1079 for (auto i : lin) {
1080 if (i != lin_leaf.back()) lin_moved.push_back(i);
1081 }
1082 lin_moved.push_back(lin_leaf.back());
1083 1084 // Postlinearize lin_moved.
1085 PostLinearize(depgraph, lin_moved);
1086 SanityCheck(depgraph, lin_moved);
1087 1088 // Compare diagrams (applying the fee delta after computing the old one).
1089 auto old_chunking = ChunkLinearization(depgraph, lin);
1090 depgraph.FeeRate(lin_leaf.back()).fee += fee_inc;
1091 auto new_chunking = ChunkLinearization(depgraph, lin_moved);
1092 auto cmp = CompareChunks(new_chunking, old_chunking);
1093 assert(cmp >= 0);
1094 }
1095 1096 FUZZ_TARGET(clusterlin_merge)
1097 {
1098 // Construct an arbitrary graph from the fuzz input.
1099 SpanReader reader(buffer);
1100 DepGraph<TestBitSet> depgraph;
1101 try {
1102 reader >> Using<DepGraphFormatter>(depgraph);
1103 } catch (const std::ios_base::failure&) {}
1104 1105 // Retrieve two linearizations from the fuzz input.
1106 auto lin1 = ReadLinearization(depgraph, reader);
1107 auto lin2 = ReadLinearization(depgraph, reader);
1108 1109 // Merge the two.
1110 auto lin_merged = MergeLinearizations(depgraph, lin1, lin2);
1111 1112 // Compute chunkings and compare.
1113 auto chunking1 = ChunkLinearization(depgraph, lin1);
1114 auto chunking2 = ChunkLinearization(depgraph, lin2);
1115 auto chunking_merged = ChunkLinearization(depgraph, lin_merged);
1116 auto cmp1 = CompareChunks(chunking_merged, chunking1);
1117 assert(cmp1 >= 0);
1118 auto cmp2 = CompareChunks(chunking_merged, chunking2);
1119 assert(cmp2 >= 0);
1120 }
1121