Bitcoin Core 30.99.0
P2P Digital Currency
cluster_linearize.cpp
Go to the documentation of this file.
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>
10#include <test/fuzz/fuzz.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 * | SearchCandidateFinder | <<---------------------\
29 * +-----------------------+ |
30 * | +-----------+
31 * | | Linearize |
32 * | +-----------+
33 * | +-------------------------+ | |
34 * | | AncestorCandidateFinder | <<--------/ |
35 * | +-------------------------+ |
36 * | | ^ | ^^ PRODUCTION CODE
37 * | | | | ||
38 * ==============================================================================================
39 * | | | | ||
40 * | clusterlin_ancestor_finder* | | vv TEST CODE
41 * | | |
42 * |-clusterlin_search_finder* | |-clusterlin_linearize*
43 * | | |
44 * v | v
45 * +-----------------------+ | +-----------------+
46 * | SimpleCandidateFinder | <<-------------------| SimpleLinearize |
47 * +-----------------------+ | +-----------------+
48 * | | |
49 * +-------------------/ |
50 * | |
51 * |-clusterlin_simple_finder* |-clusterlin_simple_linearize*
52 * v v
53 * +---------------------------+ +---------------------+
54 * | ExhaustiveCandidateFinder | | ExhaustiveLinearize |
55 * +---------------------------+ +---------------------+
56 *
57 * More tests are included for lower-level and related functions and classes:
58 * - DepGraph tests:
59 * - clusterlin_depgraph_sim
60 * - clusterlin_depgraph_serialization
61 * - clusterlin_components
62 * - ChunkLinearization and LinearizationChunking tests:
63 * - clusterlin_chunking
64 * - clusterlin_linearization_chunking
65 * - PostLinearize tests:
66 * - clusterlin_postlinearize
67 * - clusterlin_postlinearize_tree
68 * - clusterlin_postlinearize_moved_leaf
69 * - MergeLinearization tests:
70 * - clusterlin_merge
71 * - FixLinearization tests:
72 * - clusterlin_fix_linearization
73 * - MakeConnected tests (a test-only function):
74 * - clusterlin_make_connected
75 */
76
77using namespace cluster_linearize;
78
79namespace {
80
86template<typename SetType>
87class SimpleCandidateFinder
88{
90 const DepGraph<SetType>& m_depgraph;
92 SetType m_todo;
93
94public:
96 SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
97 m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
98
100 void MarkDone(SetType select) noexcept { m_todo -= select; }
101
103 bool AllDone() const noexcept { return m_todo.None(); }
104
113 std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations) const noexcept
114 {
115 uint64_t iterations_left = max_iterations;
116 // Queue of work units. Each consists of:
117 // - inc: set of transactions definitely included
118 // - und: set of transactions that can be added to inc still
119 std::vector<std::pair<SetType, SetType>> queue;
120 // Initially we have just one queue element, with the entire graph in und.
121 queue.emplace_back(SetType{}, m_todo);
122 // Best solution so far. Initialize with the remaining ancestors of the first remaining
123 // transaction.
124 SetInfo best(m_depgraph, m_depgraph.Ancestors(m_todo.First()) & m_todo);
125 // Process the queue.
126 while (!queue.empty() && iterations_left) {
127 // Pop top element of the queue.
128 auto [inc, und] = queue.back();
129 queue.pop_back();
130 // Look for a transaction to consider adding/removing.
131 bool inc_none = inc.None();
132 for (auto split : und) {
133 // If inc is empty, consider any split transaction. Otherwise only consider
134 // transactions that share ancestry with inc so far (which means only connected
135 // sets will be considered).
136 if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) {
137 --iterations_left;
138 // Add a queue entry with split included.
139 SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split)));
140 queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
141 // Add a queue entry with split excluded.
142 queue.emplace_back(inc, und - m_depgraph.Descendants(split));
143 // Update statistics to account for the candidate new_inc.
144 if (new_inc.feerate > best.feerate) best = new_inc;
145 break;
146 }
147 }
148 }
149 return {std::move(best), max_iterations - iterations_left};
150 }
151};
152
158template<typename SetType>
159class ExhaustiveCandidateFinder
160{
162 const DepGraph<SetType>& m_depgraph;
164 SetType m_todo;
165
166public:
168 ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
169 m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
170
172 void MarkDone(SetType select) noexcept { m_todo -= select; }
173
175 bool AllDone() const noexcept { return m_todo.None(); }
176
181 SetInfo<SetType> FindCandidateSet() const noexcept
182 {
183 // Best solution so far.
184 SetInfo<SetType> best{m_todo, m_depgraph.FeeRate(m_todo)};
185 // The number of combinations to try.
186 uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1;
187 // Try the transitive closure of every non-empty subset of m_todo.
188 for (uint64_t x = 1; x < limit; ++x) {
189 // If bit number b is set in x, then the remaining ancestors of the b'th remaining
190 // transaction in m_todo are included.
191 SetType txn;
192 auto x_shifted{x};
193 for (auto i : m_todo) {
194 if (x_shifted & 1) txn |= m_depgraph.Ancestors(i);
195 x_shifted >>= 1;
196 }
197 SetInfo cur(m_depgraph, txn & m_todo);
198 if (cur.feerate > best.feerate) best = cur;
199 }
200 return best;
201 }
202};
203
210template<typename SetType>
211std::pair<std::vector<DepGraphIndex>, bool> SimpleLinearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations)
212{
213 std::vector<DepGraphIndex> linearization;
214 SimpleCandidateFinder finder(depgraph);
215 SetType todo = depgraph.Positions();
216 bool optimal = true;
217 while (todo.Any()) {
218 auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
219 if (iterations_done == max_iterations) optimal = false;
220 depgraph.AppendTopo(linearization, candidate.transactions);
221 todo -= candidate.transactions;
222 finder.MarkDone(candidate.transactions);
223 max_iterations -= iterations_done;
224 }
225 return {std::move(linearization), optimal};
226}
227
235template<typename SetType>
236std::vector<DepGraphIndex> ExhaustiveLinearize(const DepGraph<SetType>& depgraph)
237{
238 // The best linearization so far, and its chunking.
239 std::vector<DepGraphIndex> linearization;
240 std::vector<FeeFrac> chunking;
241
242 std::vector<DepGraphIndex> perm_linearization;
243 // Initialize with the lexicographically-first linearization.
244 for (DepGraphIndex i : depgraph.Positions()) perm_linearization.push_back(i);
245 // Iterate over all valid permutations.
246 do {
248 DepGraphIndex topo_length{0};
249 TestBitSet perm_done;
250 while (topo_length < perm_linearization.size()) {
251 auto i = perm_linearization[topo_length];
252 perm_done.Set(i);
253 if (!depgraph.Ancestors(i).IsSubsetOf(perm_done)) break;
254 ++topo_length;
255 }
256 if (topo_length == perm_linearization.size()) {
257 // If all of perm_linearization is topological, check if it is perhaps our best
258 // linearization so far.
259 auto perm_chunking = ChunkLinearization(depgraph, perm_linearization);
260 auto cmp = CompareChunks(perm_chunking, chunking);
261 // If the diagram is better, or if it is equal but with more chunks (because we
262 // prefer minimal chunks), consider this better.
263 if (linearization.empty() || cmp > 0 || (cmp == 0 && perm_chunking.size() > chunking.size())) {
264 linearization = perm_linearization;
265 chunking = perm_chunking;
266 }
267 } else {
268 // Otherwise, fast forward to the last permutation with the same non-topological
269 // prefix.
270 auto first_non_topo = perm_linearization.begin() + topo_length;
271 assert(std::is_sorted(first_non_topo + 1, perm_linearization.end()));
272 std::reverse(first_non_topo + 1, perm_linearization.end());
273 }
274 } while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
275
276 return linearization;
277}
278
279
281template<typename BS>
282void MakeConnected(DepGraph<BS>& depgraph)
283{
284 auto todo = depgraph.Positions();
285 auto comp = depgraph.FindConnectedComponent(todo);
286 Assume(depgraph.IsConnected(comp));
287 todo -= comp;
288 while (todo.Any()) {
289 auto nextcomp = depgraph.FindConnectedComponent(todo);
290 Assume(depgraph.IsConnected(nextcomp));
291 depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
292 todo -= nextcomp;
293 comp = nextcomp;
294 }
295}
296
298template<typename SetType>
299SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& todo, SpanReader& reader, bool non_empty)
300{
301 // Read a bitmask from the fuzzing input. Add 1 if non_empty, so the mask is definitely not
302 // zero in that case.
303 uint64_t mask{0};
304 try {
305 reader >> VARINT(mask);
306 } catch(const std::ios_base::failure&) {}
307 if (mask != uint64_t(-1)) mask += non_empty;
308
309 SetType ret;
310 for (auto i : todo) {
311 if (!ret[i]) {
312 if (mask & 1) ret |= depgraph.Ancestors(i);
313 mask >>= 1;
314 }
315 }
316 ret &= todo;
317
318 // While mask starts off non-zero if non_empty is true, it is still possible that all its low
319 // bits are 0, and ret ends up being empty. As a last resort, use the in-todo ancestry of the
320 // first todo position.
321 if (non_empty && ret.None()) {
322 Assume(todo.Any());
323 ret = depgraph.Ancestors(todo.First()) & todo;
324 Assume(ret.Any());
325 }
326 return ret;
327}
328
330template<typename BS>
331std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader)
332{
333 std::vector<DepGraphIndex> linearization;
334 TestBitSet todo = depgraph.Positions();
335 // In every iteration one topologically-valid transaction is appended to linearization.
336 while (todo.Any()) {
337 // Compute the set of transactions with no not-yet-included ancestors.
338 TestBitSet potential_next;
339 for (auto j : todo) {
340 if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
341 potential_next.Set(j);
342 }
343 }
344 // There must always be one (otherwise there is a cycle in the graph).
345 assert(potential_next.Any());
346 // Read a number from reader, and interpret it as index into potential_next.
347 uint64_t idx{0};
348 try {
349 reader >> VARINT(idx);
350 } catch (const std::ios_base::failure&) {}
351 idx %= potential_next.Count();
352 // Find out which transaction that corresponds to.
353 for (auto j : potential_next) {
354 if (idx == 0) {
355 // When found, add it to linearization and remove it from todo.
356 linearization.push_back(j);
357 assert(todo[j]);
358 todo.Reset(j);
359 break;
360 }
361 --idx;
362 }
363 }
364 return linearization;
365}
366
367} // namespace
368
369FUZZ_TARGET(clusterlin_depgraph_sim)
370{
371 // Simulation test to verify the full behavior of DepGraph.
372
373 FuzzedDataProvider provider(buffer.data(), buffer.size());
374
379 std::array<std::optional<std::pair<FeeFrac, TestBitSet>>, TestBitSet::Size()> sim;
381 DepGraphIndex num_tx_sim{0};
382
384 auto idx_fn = [&]() {
385 auto offset = provider.ConsumeIntegralInRange<DepGraphIndex>(0, num_tx_sim - 1);
386 for (DepGraphIndex i = 0; i < sim.size(); ++i) {
387 if (!sim[i].has_value()) continue;
388 if (offset == 0) return i;
389 --offset;
390 }
391 assert(false);
392 return DepGraphIndex(-1);
393 };
394
396 auto subset_fn = [&]() {
397 auto range = (uint64_t{1} << num_tx_sim) - 1;
398 const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
399 auto mask_shifted = mask;
400 TestBitSet subset;
401 for (DepGraphIndex i = 0; i < sim.size(); ++i) {
402 if (!sim[i].has_value()) continue;
403 if (mask_shifted & 1) {
404 subset.Set(i);
405 }
406 mask_shifted >>= 1;
407 }
408 assert(mask_shifted == 0);
409 return subset;
410 };
411
413 auto set_fn = [&]() {
414 auto range = (uint64_t{1} << sim.size()) - 1;
415 const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range);
416 TestBitSet set;
417 for (DepGraphIndex i = 0; i < sim.size(); ++i) {
418 if ((mask >> i) & 1) {
419 set.Set(i);
420 }
421 }
422 return set;
423 };
424
426 auto anc_update_fn = [&]() {
427 while (true) {
428 bool updates{false};
429 for (DepGraphIndex chl = 0; chl < sim.size(); ++chl) {
430 if (!sim[chl].has_value()) continue;
431 for (auto par : sim[chl]->second) {
432 if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) {
433 sim[chl]->second |= sim[par]->second;
434 updates = true;
435 }
436 }
437 }
438 if (!updates) break;
439 }
440 };
441
443 auto check_fn = [&](DepGraphIndex i) {
444 // Compare used positions.
445 assert(real.Positions()[i] == sim[i].has_value());
446 if (sim[i].has_value()) {
447 // Compare feerate.
448 assert(real.FeeRate(i) == sim[i]->first);
449 // Compare ancestors (note that SanityCheck verifies correspondence between ancestors
450 // and descendants, so we can restrict ourselves to ancestors here).
451 assert(real.Ancestors(i) == sim[i]->second);
452 }
453 };
454
455 auto last_compaction_pos{real.PositionRange()};
456
457 LIMITED_WHILE(provider.remaining_bytes() > 0, 1000) {
458 int command = provider.ConsumeIntegral<uint8_t>() % 4;
459 while (true) {
460 // Iterate decreasing command until an applicable branch is found.
461 if (num_tx_sim < TestBitSet::Size() && command-- == 0) {
462 // AddTransaction.
463 auto fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
464 auto size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
465 FeeFrac feerate{fee, size};
466 // Apply to DepGraph.
467 auto idx = real.AddTransaction(feerate);
468 // Verify that the returned index is correct.
469 assert(!sim[idx].has_value());
470 for (DepGraphIndex i = 0; i < TestBitSet::Size(); ++i) {
471 if (!sim[i].has_value()) {
472 assert(idx == i);
473 break;
474 }
475 }
476 // Update sim.
477 sim[idx] = {feerate, TestBitSet::Singleton(idx)};
478 ++num_tx_sim;
479 break;
480 } else if (num_tx_sim > 0 && command-- == 0) {
481 // AddDependencies.
482 DepGraphIndex child = idx_fn();
483 auto parents = subset_fn();
484 // Apply to DepGraph.
485 real.AddDependencies(parents, child);
486 // Apply to sim.
487 sim[child]->second |= parents;
488 break;
489 } else if (num_tx_sim > 0 && command-- == 0) {
490 // Remove transactions.
491 auto del = set_fn();
492 // Propagate all ancestry information before deleting anything in the simulation (as
493 // intermediary transactions may be deleted which impact connectivity).
494 anc_update_fn();
495 // Compare the state of the transactions being deleted.
496 for (auto i : del) check_fn(i);
497 // Apply to DepGraph.
498 real.RemoveTransactions(del);
499 // Apply to sim.
500 for (DepGraphIndex i = 0; i < sim.size(); ++i) {
501 if (sim[i].has_value()) {
502 if (del[i]) {
503 --num_tx_sim;
504 sim[i] = std::nullopt;
505 } else {
506 sim[i]->second -= del;
507 }
508 }
509 }
510 break;
511 } else if (command-- == 0) {
512 // Compact.
513 const size_t mem_before{real.DynamicMemoryUsage()};
514 real.Compact();
515 const size_t mem_after{real.DynamicMemoryUsage()};
516 assert(real.PositionRange() < last_compaction_pos ? mem_after < mem_before : mem_after <= mem_before);
517 last_compaction_pos = real.PositionRange();
518 break;
519 }
520 }
521 }
522
523 // Compare the real obtained depgraph against the simulation.
524 anc_update_fn();
525 for (DepGraphIndex i = 0; i < sim.size(); ++i) check_fn(i);
526 assert(real.TxCount() == num_tx_sim);
527 // Sanity check the result (which includes round-tripping serialization, if applicable).
528 SanityCheck(real);
529}
530
531FUZZ_TARGET(clusterlin_depgraph_serialization)
532{
533 // Verify that any deserialized depgraph is acyclic and roundtrips to an identical depgraph.
534
535 // Construct a graph by deserializing.
536 SpanReader reader(buffer);
537 DepGraph<TestBitSet> depgraph;
538 DepGraphIndex par_code{0}, chl_code{0};
539 try {
540 reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(par_code) >> VARINT(chl_code);
541 } catch (const std::ios_base::failure&) {}
542 SanityCheck(depgraph);
543
544 // Verify the graph is a DAG.
545 assert(depgraph.IsAcyclic());
546
547 // Introduce a cycle, and then test that IsAcyclic returns false.
548 if (depgraph.TxCount() < 2) return;
549 DepGraphIndex par(0), chl(0);
550 // Pick any transaction of depgraph as parent.
551 par_code %= depgraph.TxCount();
552 for (auto i : depgraph.Positions()) {
553 if (par_code == 0) {
554 par = i;
555 break;
556 }
557 --par_code;
558 }
559 // Pick any ancestor of par (excluding itself) as child, if any.
560 auto ancestors = depgraph.Ancestors(par) - TestBitSet::Singleton(par);
561 if (ancestors.None()) return;
562 chl_code %= ancestors.Count();
563 for (auto i : ancestors) {
564 if (chl_code == 0) {
565 chl = i;
566 break;
567 }
568 --chl_code;
569 }
570 // Add the cycle-introducing dependency.
571 depgraph.AddDependencies(TestBitSet::Singleton(par), chl);
572 // Check that we now detect a cycle.
573 assert(!depgraph.IsAcyclic());
574}
575
576FUZZ_TARGET(clusterlin_components)
577{
578 // Verify the behavior of DepGraphs's FindConnectedComponent and IsConnected functions.
579
580 // Construct a depgraph.
581 SpanReader reader(buffer);
582 DepGraph<TestBitSet> depgraph;
583 std::vector<DepGraphIndex> linearization;
584 try {
585 reader >> Using<DepGraphFormatter>(depgraph);
586 } catch (const std::ios_base::failure&) {}
587
588 TestBitSet todo = depgraph.Positions();
589 while (todo.Any()) {
590 // Pick a transaction in todo, or nothing.
591 std::optional<DepGraphIndex> picked;
592 {
593 uint64_t picked_num{0};
594 try {
595 reader >> VARINT(picked_num);
596 } catch (const std::ios_base::failure&) {}
597 if (picked_num < todo.Size() && todo[picked_num]) {
598 picked = picked_num;
599 }
600 }
601
602 // Find a connected component inside todo, including picked if any.
603 auto component = picked ? depgraph.GetConnectedComponent(todo, *picked)
604 : depgraph.FindConnectedComponent(todo);
605
606 // The component must be a subset of todo and non-empty.
607 assert(component.IsSubsetOf(todo));
608 assert(component.Any());
609
610 // If picked was provided, the component must include it.
611 if (picked) assert(component[*picked]);
612
613 // If todo is the entire graph, and the entire graph is connected, then the component must
614 // be the entire graph.
615 if (todo == depgraph.Positions()) {
616 assert((component == todo) == depgraph.IsConnected());
617 }
618
619 // If subset is connected, then component must match subset.
620 assert((component == todo) == depgraph.IsConnected(todo));
621
622 // The component cannot have any ancestors or descendants outside of component but in todo.
623 for (auto i : component) {
624 assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component));
625 assert((depgraph.Descendants(i) & todo).IsSubsetOf(component));
626 }
627
628 // Starting from any component element, we must be able to reach every element.
629 for (auto i : component) {
630 // Start with just i as reachable.
631 TestBitSet reachable = TestBitSet::Singleton(i);
632 // Add in-todo descendants and ancestors to reachable until it does not change anymore.
633 while (true) {
634 TestBitSet new_reachable = reachable;
635 for (auto j : new_reachable) {
636 new_reachable |= depgraph.Ancestors(j) & todo;
637 new_reachable |= depgraph.Descendants(j) & todo;
638 }
639 if (new_reachable == reachable) break;
640 reachable = new_reachable;
641 }
642 // Verify that the result is the entire component.
643 assert(component == reachable);
644 }
645
646 // Construct an arbitrary subset of todo.
647 uint64_t subset_bits{0};
648 try {
649 reader >> VARINT(subset_bits);
650 } catch (const std::ios_base::failure&) {}
651 TestBitSet subset;
652 for (DepGraphIndex i : depgraph.Positions()) {
653 if (todo[i]) {
654 if (subset_bits & 1) subset.Set(i);
655 subset_bits >>= 1;
656 }
657 }
658 // Which must be non-empty.
659 if (subset.None()) subset = TestBitSet::Singleton(todo.First());
660 // Remove it from todo.
661 todo -= subset;
662 }
663
664 // No components can be found in an empty subset.
665 assert(depgraph.FindConnectedComponent(todo).None());
666}
667
668FUZZ_TARGET(clusterlin_make_connected)
669{
670 // Verify that MakeConnected makes graphs connected.
671
672 SpanReader reader(buffer);
673 DepGraph<TestBitSet> depgraph;
674 try {
675 reader >> Using<DepGraphFormatter>(depgraph);
676 } catch (const std::ios_base::failure&) {}
677 MakeConnected(depgraph);
678 SanityCheck(depgraph);
679 assert(depgraph.IsConnected());
680}
681
682FUZZ_TARGET(clusterlin_chunking)
683{
684 // Verify the correctness of the ChunkLinearization function.
685
686 // Construct a graph by deserializing.
687 SpanReader reader(buffer);
688 DepGraph<TestBitSet> depgraph;
689 try {
690 reader >> Using<DepGraphFormatter>(depgraph);
691 } catch (const std::ios_base::failure&) {}
692
693 // Read a valid linearization for depgraph.
694 auto linearization = ReadLinearization(depgraph, reader);
695
696 // Invoke the chunking function.
697 auto chunking = ChunkLinearization(depgraph, linearization);
698
699 // Verify that chunk feerates are monotonically non-increasing.
700 for (size_t i = 1; i < chunking.size(); ++i) {
701 assert(!(chunking[i] >> chunking[i - 1]));
702 }
703
704 // Naively recompute the chunks (each is the highest-feerate prefix of what remains).
705 auto todo = depgraph.Positions();
706 for (const auto& chunk_feerate : chunking) {
707 assert(todo.Any());
708 SetInfo<TestBitSet> accumulator, best;
709 for (DepGraphIndex idx : linearization) {
710 if (todo[idx]) {
711 accumulator.Set(depgraph, idx);
712 if (best.feerate.IsEmpty() || accumulator.feerate >> best.feerate) {
713 best = accumulator;
714 }
715 }
716 }
717 assert(chunk_feerate == best.feerate);
718 assert(best.transactions.IsSubsetOf(todo));
719 todo -= best.transactions;
720 }
721 assert(todo.None());
722}
723
724FUZZ_TARGET(clusterlin_ancestor_finder)
725{
726 // Verify that AncestorCandidateFinder works as expected.
727
728 // Retrieve a depgraph from the fuzz input.
729 SpanReader reader(buffer);
730 DepGraph<TestBitSet> depgraph;
731 try {
732 reader >> Using<DepGraphFormatter>(depgraph);
733 } catch (const std::ios_base::failure&) {}
734
735 AncestorCandidateFinder anc_finder(depgraph);
736 auto todo = depgraph.Positions();
737 while (todo.Any()) {
738 // Call the ancestor finder's FindCandidateSet for what remains of the graph.
739 assert(!anc_finder.AllDone());
740 assert(todo.Count() == anc_finder.NumRemaining());
741 auto best_anc = anc_finder.FindCandidateSet();
742 // Sanity check the result.
743 assert(best_anc.transactions.Any());
744 assert(best_anc.transactions.IsSubsetOf(todo));
745 assert(depgraph.FeeRate(best_anc.transactions) == best_anc.feerate);
746 assert(depgraph.IsConnected(best_anc.transactions));
747 // Check that it is topologically valid.
748 for (auto i : best_anc.transactions) {
749 assert((depgraph.Ancestors(i) & todo).IsSubsetOf(best_anc.transactions));
750 }
751
752 // Compute all remaining ancestor sets.
753 std::optional<SetInfo<TestBitSet>> real_best_anc;
754 for (auto i : todo) {
755 SetInfo info(depgraph, todo & depgraph.Ancestors(i));
756 if (!real_best_anc.has_value() || info.feerate > real_best_anc->feerate) {
757 real_best_anc = info;
758 }
759 }
760 // The set returned by anc_finder must equal the real best ancestor sets.
761 assert(real_best_anc.has_value());
762 assert(*real_best_anc == best_anc);
763
764 // Find a non-empty topologically valid subset of transactions to remove from the graph.
765 // Using an empty set would mean the next iteration is identical to the current one, and
766 // could cause an infinite loop.
767 auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
768 todo -= del_set;
769 anc_finder.MarkDone(del_set);
770 }
771 assert(anc_finder.AllDone());
772 assert(anc_finder.NumRemaining() == 0);
773}
774
775static constexpr auto MAX_SIMPLE_ITERATIONS = 300000;
776
777FUZZ_TARGET(clusterlin_simple_finder)
778{
779 // Verify that SimpleCandidateFinder works as expected by sanity checking the results
780 // and comparing them (if claimed to be optimal) against the sets found by
781 // ExhaustiveCandidateFinder and AncestorCandidateFinder.
782 //
783 // Note that SimpleCandidateFinder is only used in tests; the purpose of this fuzz test is to
784 // establish confidence in SimpleCandidateFinder, so that it can be used to test
785 // SearchCandidateFinder below.
786
787 // Retrieve a depgraph from the fuzz input.
788 SpanReader reader(buffer);
789 DepGraph<TestBitSet> depgraph;
790 try {
791 reader >> Using<DepGraphFormatter>(depgraph);
792 } catch (const std::ios_base::failure&) {}
793
794 // Instantiate the SimpleCandidateFinder to be tested, and the ExhaustiveCandidateFinder and
795 // AncestorCandidateFinder it is being tested against.
796 SimpleCandidateFinder smp_finder(depgraph);
797 ExhaustiveCandidateFinder exh_finder(depgraph);
798 AncestorCandidateFinder anc_finder(depgraph);
799
800 auto todo = depgraph.Positions();
801 while (todo.Any()) {
802 assert(!smp_finder.AllDone());
803 assert(!exh_finder.AllDone());
804 assert(!anc_finder.AllDone());
805 assert(anc_finder.NumRemaining() == todo.Count());
806
807 // Call SimpleCandidateFinder.
808 auto [found, iterations_done] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
809 bool optimal = (iterations_done != MAX_SIMPLE_ITERATIONS);
810
811 // Sanity check the result.
812 assert(iterations_done <= MAX_SIMPLE_ITERATIONS);
813 assert(found.transactions.Any());
814 assert(found.transactions.IsSubsetOf(todo));
815 assert(depgraph.FeeRate(found.transactions) == found.feerate);
816 // Check that it is topologically valid.
817 for (auto i : found.transactions) {
818 assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo));
819 }
820
821 // At most 2^(N-1) iterations can be required: the number of non-empty connected subsets a
822 // graph with N transactions can have. If MAX_SIMPLE_ITERATIONS exceeds this number, the
823 // result is necessarily optimal.
824 assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
825 if (MAX_SIMPLE_ITERATIONS > (uint64_t{1} << (todo.Count() - 1))) assert(optimal);
826
827 // SimpleCandidateFinder only finds connected sets.
828 assert(depgraph.IsConnected(found.transactions));
829
830 // Perform further quality checks only if SimpleCandidateFinder claims an optimal result.
831 if (optimal) {
832 // Compare with AncestorCandidateFinder.
833 auto anc = anc_finder.FindCandidateSet();
834 assert(anc.feerate <= found.feerate);
835
836 if (todo.Count() <= 12) {
837 // Compare with ExhaustiveCandidateFinder. This quickly gets computationally
838 // expensive for large clusters (O(2^n)), so only do it for sufficiently small ones.
839 auto exhaustive = exh_finder.FindCandidateSet();
840 assert(exhaustive.feerate == found.feerate);
841 }
842
843 // Compare with a non-empty topological set read from the fuzz input (comparing with an
844 // empty set is not interesting).
845 auto read_topo = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
846 assert(found.feerate >= depgraph.FeeRate(read_topo));
847 }
848
849 // Find a non-empty topologically valid subset of transactions to remove from the graph.
850 // Using an empty set would mean the next iteration is identical to the current one, and
851 // could cause an infinite loop.
852 auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
853 todo -= del_set;
854 smp_finder.MarkDone(del_set);
855 exh_finder.MarkDone(del_set);
856 anc_finder.MarkDone(del_set);
857 }
858
859 assert(smp_finder.AllDone());
860 assert(exh_finder.AllDone());
861 assert(anc_finder.AllDone());
862 assert(anc_finder.NumRemaining() == 0);
863}
864
865FUZZ_TARGET(clusterlin_search_finder)
866{
867 // Verify that SearchCandidateFinder works as expected by sanity checking the results
868 // and comparing with the results from SimpleCandidateFinder and AncestorCandidateFinder,
869 // if the result is claimed to be optimal.
870
871 // Retrieve an RNG seed, a depgraph, and whether to make it connected, from the fuzz input.
872 SpanReader reader(buffer);
873 DepGraph<TestBitSet> depgraph;
874 uint64_t rng_seed{0};
875 uint8_t make_connected{1};
876 try {
877 reader >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
878 } catch (const std::ios_base::failure&) {}
879 // The most complicated graphs are connected ones (other ones just split up). Optionally force
880 // the graph to be connected.
881 if (make_connected) MakeConnected(depgraph);
882
883 // Instantiate the candidate finders.
884 SearchCandidateFinder src_finder(depgraph, rng_seed);
885 SimpleCandidateFinder smp_finder(depgraph);
886 AncestorCandidateFinder anc_finder(depgraph);
887
888 auto todo = depgraph.Positions();
889 while (todo.Any()) {
890 assert(!src_finder.AllDone());
891 assert(!smp_finder.AllDone());
892 assert(!anc_finder.AllDone());
893 assert(anc_finder.NumRemaining() == todo.Count());
894
895 // For each iteration, read an iteration count limit from the fuzz input.
896 uint64_t max_iterations = 1;
897 try {
898 reader >> VARINT(max_iterations);
899 } catch (const std::ios_base::failure&) {}
900 max_iterations &= 0xfffff;
901
902 // Read an initial subset from the fuzz input (allowed to be empty).
903 auto init_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/false);
904 SetInfo init_best(depgraph, init_set);
905
906 // Call the search finder's FindCandidateSet for what remains of the graph.
907 auto [found, iterations_done] = src_finder.FindCandidateSet(max_iterations, init_best);
908 bool optimal = iterations_done < max_iterations;
909
910 // Sanity check the result.
911 assert(iterations_done <= max_iterations);
912 assert(found.transactions.Any());
913 assert(found.transactions.IsSubsetOf(todo));
914 assert(depgraph.FeeRate(found.transactions) == found.feerate);
915 if (!init_best.feerate.IsEmpty()) assert(found.feerate >= init_best.feerate);
916 // Check that it is topologically valid.
917 for (auto i : found.transactions) {
918 assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo));
919 }
920
921 // At most 2^(N-1) iterations can be required: the maximum number of non-empty topological
922 // subsets a (connected) cluster with N transactions can have. Even when the cluster is no
923 // longer connected after removing certain transactions, this holds, because the connected
924 // components are searched separately.
925 assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
926 // Additionally, test that no more than sqrt(2^N)+1 iterations are required. This is just
927 // an empirical bound that seems to hold, without proof. Still, add a test for it so we
928 // can learn about counterexamples if they exist.
929 if (iterations_done >= 1 && todo.Count() <= 63) {
930 Assume((iterations_done - 1) * (iterations_done - 1) <= uint64_t{1} << todo.Count());
931 }
932
933 // Perform quality checks only if SearchCandidateFinder claims an optimal result.
934 if (optimal) {
935 // Optimal sets are always connected.
936 assert(depgraph.IsConnected(found.transactions));
937
938 // Compare with SimpleCandidateFinder.
939 auto [simple, simple_iters] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
940 assert(found.feerate >= simple.feerate);
941 if (simple_iters < MAX_SIMPLE_ITERATIONS) {
942 assert(found.feerate == simple.feerate);
943 }
944
945 // Compare with AncestorCandidateFinder;
946 auto anc = anc_finder.FindCandidateSet();
947 assert(found.feerate >= anc.feerate);
948
949 // Compare with a non-empty topological set read from the fuzz input (comparing with an
950 // empty set is not interesting).
951 auto read_topo = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
952 assert(found.feerate >= depgraph.FeeRate(read_topo));
953 }
954
955 // Find a non-empty topologically valid subset of transactions to remove from the graph.
956 // Using an empty set would mean the next iteration is identical to the current one, and
957 // could cause an infinite loop.
958 auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
959 todo -= del_set;
960 src_finder.MarkDone(del_set);
961 smp_finder.MarkDone(del_set);
962 anc_finder.MarkDone(del_set);
963 }
964
965 assert(src_finder.AllDone());
966 assert(smp_finder.AllDone());
967 assert(anc_finder.AllDone());
968 assert(anc_finder.NumRemaining() == 0);
969}
970
971FUZZ_TARGET(clusterlin_linearization_chunking)
972{
973 // Verify the behavior of LinearizationChunking.
974
975 // Retrieve a depgraph from the fuzz input.
976 SpanReader reader(buffer);
977 DepGraph<TestBitSet> depgraph;
978 try {
979 reader >> Using<DepGraphFormatter>(depgraph);
980 } catch (const std::ios_base::failure&) {}
981
982 // Retrieve a topologically-valid subset of depgraph (allowed to be empty, because the argument
983 // to LinearizationChunking::Intersect is allowed to be empty).
984 auto todo = depgraph.Positions();
985 auto subset = SetInfo(depgraph, ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/false));
986
987 // Retrieve a valid linearization for depgraph.
988 auto linearization = ReadLinearization(depgraph, reader);
989
990 // Construct a LinearizationChunking object, initially for the whole linearization.
991 LinearizationChunking chunking(depgraph, linearization);
992
993 // Incrementally remove transactions from the chunking object, and check various properties at
994 // every step.
995 while (todo.Any()) {
996 assert(chunking.NumChunksLeft() > 0);
997
998 // Construct linearization with just todo.
999 std::vector<DepGraphIndex> linearization_left;
1000 for (auto i : linearization) {
1001 if (todo[i]) linearization_left.push_back(i);
1002 }
1003
1004 // Compute the chunking for linearization_left.
1005 auto chunking_left = ChunkLinearization(depgraph, linearization_left);
1006
1007 // Verify that it matches the feerates of the chunks of chunking.
1008 assert(chunking.NumChunksLeft() == chunking_left.size());
1009 for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
1010 assert(chunking.GetChunk(i).feerate == chunking_left[i]);
1011 }
1012
1013 // Check consistency of chunking.
1014 TestBitSet combined;
1015 for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
1016 const auto& chunk_info = chunking.GetChunk(i);
1017 // Chunks must be non-empty.
1018 assert(chunk_info.transactions.Any());
1019 // Chunk feerates must be monotonically non-increasing.
1020 if (i > 0) assert(!(chunk_info.feerate >> chunking.GetChunk(i - 1).feerate));
1021 // Chunks must be a subset of what is left of the linearization.
1022 assert(chunk_info.transactions.IsSubsetOf(todo));
1023 // Chunks' claimed feerates must match their transactions' aggregate feerate.
1024 assert(depgraph.FeeRate(chunk_info.transactions) == chunk_info.feerate);
1025 // Chunks must be the highest-feerate remaining prefix.
1026 SetInfo<TestBitSet> accumulator, best;
1027 for (auto j : linearization) {
1028 if (todo[j] && !combined[j]) {
1029 accumulator.Set(depgraph, j);
1030 if (best.feerate.IsEmpty() || accumulator.feerate > best.feerate) {
1031 best = accumulator;
1032 }
1033 }
1034 }
1035 assert(best.transactions == chunk_info.transactions);
1036 assert(best.feerate == chunk_info.feerate);
1037 // Chunks cannot overlap.
1038 assert(!chunk_info.transactions.Overlaps(combined));
1039 combined |= chunk_info.transactions;
1040 // Chunks must be topological.
1041 for (auto idx : chunk_info.transactions) {
1042 assert((depgraph.Ancestors(idx) & todo).IsSubsetOf(combined));
1043 }
1044 }
1045 assert(combined == todo);
1046
1047 // Verify the expected properties of LinearizationChunking::IntersectPrefixes:
1048 auto intersect = chunking.IntersectPrefixes(subset);
1049 // - Intersecting again doesn't change the result.
1050 assert(chunking.IntersectPrefixes(intersect) == intersect);
1051 // - The intersection is topological.
1052 TestBitSet intersect_anc;
1053 for (auto idx : intersect.transactions) {
1054 intersect_anc |= (depgraph.Ancestors(idx) & todo);
1055 }
1056 assert(intersect.transactions == intersect_anc);
1057 // - The claimed intersection feerate matches its transactions.
1058 assert(intersect.feerate == depgraph.FeeRate(intersect.transactions));
1059 // - The intersection may only be empty if its input is empty.
1060 assert(intersect.transactions.Any() == subset.transactions.Any());
1061 // - The intersection feerate must be as high as the input.
1062 assert(intersect.feerate >= subset.feerate);
1063 // - No non-empty intersection between the intersection and a prefix of the chunks of the
1064 // remainder of the linearization may be better than the intersection.
1065 TestBitSet prefix;
1066 for (DepGraphIndex i = 0; i < chunking.NumChunksLeft(); ++i) {
1067 prefix |= chunking.GetChunk(i).transactions;
1068 auto reintersect = SetInfo(depgraph, prefix & intersect.transactions);
1069 if (!reintersect.feerate.IsEmpty()) {
1070 assert(reintersect.feerate <= intersect.feerate);
1071 }
1072 }
1073
1074 // Find a non-empty topologically valid subset of transactions to remove from the graph.
1075 // Using an empty set would mean the next iteration is identical to the current one, and
1076 // could cause an infinite loop.
1077 auto done = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
1078 todo -= done;
1079 chunking.MarkDone(done);
1080 subset = SetInfo(depgraph, subset.transactions - done);
1081 }
1082
1083 assert(chunking.NumChunksLeft() == 0);
1084}
1085
1086FUZZ_TARGET(clusterlin_simple_linearize)
1087{
1088 // Verify the behavior of SimpleLinearize(). Note that SimpleLinearize is only used in tests;
1089 // the purpose of this fuzz test is to establish confidence in SimpleLinearize, so that it can
1090 // be used to test the real Linearize function in the fuzz test below.
1091
1092 // Retrieve an iteration count and a depgraph from the fuzz input.
1093 SpanReader reader(buffer);
1094 uint64_t iter_count{0};
1095 DepGraph<TestBitSet> depgraph;
1096 try {
1097 reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph);
1098 } catch (const std::ios_base::failure&) {}
1099 iter_count %= MAX_SIMPLE_ITERATIONS;
1100
1101 // Invoke SimpleLinearize().
1102 auto [linearization, optimal] = SimpleLinearize(depgraph, iter_count);
1103 SanityCheck(depgraph, linearization);
1104 auto simple_chunking = ChunkLinearization(depgraph, linearization);
1105
1106 // If the iteration count is sufficiently high, an optimal linearization must be found.
1107 // SimpleLinearize on k transactions can take up to 2^(k-1) iterations (one per non-empty
1108 // connected topologically valid subset), which sums over k=1..n to (2^n)-1.
1109 const uint64_t n = depgraph.TxCount();
1110 if (n <= 63 && (iter_count >> n)) {
1111 assert(optimal);
1112 }
1113
1114 // If SimpleLinearize claims optimal result, and the cluster is sufficiently small (there are
1115 // n! linearizations), test that the result is as good as every valid linearization.
1116 if (optimal && depgraph.TxCount() <= 8) {
1117 auto exh_linearization = ExhaustiveLinearize(depgraph);
1118 auto exh_chunking = ChunkLinearization(depgraph, exh_linearization);
1119 auto cmp = CompareChunks(simple_chunking, exh_chunking);
1120 assert(cmp == 0);
1121 assert(simple_chunking.size() == exh_chunking.size());
1122 }
1123
1124 if (optimal) {
1125 // Compare with a linearization read from the fuzz input.
1126 auto read = ReadLinearization(depgraph, reader);
1127 auto read_chunking = ChunkLinearization(depgraph, read);
1128 auto cmp = CompareChunks(simple_chunking, read_chunking);
1129 assert(cmp >= 0);
1130 }
1131}
1132
1133FUZZ_TARGET(clusterlin_linearize)
1134{
1135 // Verify the behavior of Linearize().
1136
1137 // Retrieve an RNG seed, an iteration count, a depgraph, and whether to make it connected from
1138 // the fuzz input.
1139 SpanReader reader(buffer);
1140 DepGraph<TestBitSet> depgraph;
1141 uint64_t rng_seed{0};
1142 uint64_t iter_count{0};
1143 uint8_t make_connected{1};
1144 try {
1145 reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
1146 } catch (const std::ios_base::failure&) {}
1147 // The most complicated graphs are connected ones (other ones just split up). Optionally force
1148 // the graph to be connected.
1149 if (make_connected) MakeConnected(depgraph);
1150
1151 // Optionally construct an old linearization for it.
1152 std::vector<DepGraphIndex> old_linearization;
1153 {
1154 uint8_t have_old_linearization{0};
1155 try {
1156 reader >> have_old_linearization;
1157 } catch(const std::ios_base::failure&) {}
1158 if (have_old_linearization & 1) {
1159 old_linearization = ReadLinearization(depgraph, reader);
1160 SanityCheck(depgraph, old_linearization);
1161 }
1162 }
1163
1164 // Invoke Linearize().
1165 iter_count &= 0x7ffff;
1166 auto [linearization, optimal, cost] = Linearize(depgraph, iter_count, rng_seed, old_linearization);
1167 assert(cost <= iter_count);
1168 SanityCheck(depgraph, linearization);
1169 auto chunking = ChunkLinearization(depgraph, linearization);
1170
1171 // Linearization must always be as good as the old one, if provided.
1172 if (!old_linearization.empty()) {
1173 auto old_chunking = ChunkLinearization(depgraph, old_linearization);
1174 auto cmp = CompareChunks(chunking, old_chunking);
1175 assert(cmp >= 0);
1176 }
1177
1178 // If the iteration count is sufficiently high, an optimal linearization must be found.
1179 if (iter_count >= MaxOptimalLinearizationIters(depgraph.TxCount())) {
1180 assert(optimal);
1181 }
1182
1183 // If Linearize claims optimal result, run quality tests.
1184 if (optimal) {
1185 // It must be as good as SimpleLinearize.
1186 auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS);
1187 SanityCheck(depgraph, simple_linearization);
1188 auto simple_chunking = ChunkLinearization(depgraph, simple_linearization);
1189 auto cmp = CompareChunks(chunking, simple_chunking);
1190 assert(cmp >= 0);
1191 // If SimpleLinearize finds the optimal result too, they must be equal (if not,
1192 // SimpleLinearize is broken).
1193 if (simple_optimal) assert(cmp == 0);
1194 // If simple_chunking is diagram-optimal, it cannot have more chunks than chunking (as
1195 // chunking is claimed to be optimal, which implies minimal chunks).
1196 if (cmp == 0) assert(chunking.size() >= simple_chunking.size());
1197
1198 // Compare with a linearization read from the fuzz input.
1199 auto read = ReadLinearization(depgraph, reader);
1200 auto read_chunking = ChunkLinearization(depgraph, read);
1201 auto cmp_read = CompareChunks(chunking, read_chunking);
1202 assert(cmp_read >= 0);
1203 }
1204}
1205
1206FUZZ_TARGET(clusterlin_postlinearize)
1207{
1208 // Verify expected properties of PostLinearize() on arbitrary linearizations.
1209
1210 // Retrieve a depgraph from the fuzz input.
1211 SpanReader reader(buffer);
1212 DepGraph<TestBitSet> depgraph;
1213 try {
1214 reader >> Using<DepGraphFormatter>(depgraph);
1215 } catch (const std::ios_base::failure&) {}
1216
1217 // Retrieve a linearization from the fuzz input.
1218 std::vector<DepGraphIndex> linearization;
1219 linearization = ReadLinearization(depgraph, reader);
1220 SanityCheck(depgraph, linearization);
1221
1222 // Produce a post-processed version.
1223 auto post_linearization = linearization;
1224 PostLinearize(depgraph, post_linearization);
1225 SanityCheck(depgraph, post_linearization);
1226
1227 // Compare diagrams: post-linearization cannot worsen anywhere.
1228 auto chunking = ChunkLinearization(depgraph, linearization);
1229 auto post_chunking = ChunkLinearization(depgraph, post_linearization);
1230 auto cmp = CompareChunks(post_chunking, chunking);
1231 assert(cmp >= 0);
1232
1233 // Run again, things can keep improving (and never get worse)
1234 auto post_post_linearization = post_linearization;
1235 PostLinearize(depgraph, post_post_linearization);
1236 SanityCheck(depgraph, post_post_linearization);
1237 auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization);
1238 cmp = CompareChunks(post_post_chunking, post_chunking);
1239 assert(cmp >= 0);
1240
1241 // The chunks that come out of postlinearizing are always connected.
1242 LinearizationChunking linchunking(depgraph, post_linearization);
1243 while (linchunking.NumChunksLeft()) {
1244 assert(depgraph.IsConnected(linchunking.GetChunk(0).transactions));
1245 linchunking.MarkDone(linchunking.GetChunk(0).transactions);
1246 }
1247}
1248
1249FUZZ_TARGET(clusterlin_postlinearize_tree)
1250{
1251 // Verify expected properties of PostLinearize() on linearizations of graphs that form either
1252 // an upright or reverse tree structure.
1253
1254 // Construct a direction, RNG seed, and an arbitrary graph from the fuzz input.
1255 SpanReader reader(buffer);
1256 uint64_t rng_seed{0};
1257 DepGraph<TestBitSet> depgraph_gen;
1258 uint8_t direction{0};
1259 try {
1260 reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen);
1261 } catch (const std::ios_base::failure&) {}
1262
1263 // Now construct a new graph, copying the nodes, but leaving only the first parent (even
1264 // direction) or the first child (odd direction).
1265 DepGraph<TestBitSet> depgraph_tree;
1266 for (DepGraphIndex i = 0; i < depgraph_gen.PositionRange(); ++i) {
1267 if (depgraph_gen.Positions()[i]) {
1268 depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i));
1269 } else {
1270 // For holes, add a dummy transaction which is deleted below, so that non-hole
1271 // transactions retain their position.
1272 depgraph_tree.AddTransaction(FeeFrac{});
1273 }
1274 }
1275 depgraph_tree.RemoveTransactions(TestBitSet::Fill(depgraph_gen.PositionRange()) - depgraph_gen.Positions());
1276
1277 if (direction & 1) {
1278 for (DepGraphIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1279 auto children = depgraph_gen.GetReducedChildren(i);
1280 if (children.Any()) {
1281 depgraph_tree.AddDependencies(TestBitSet::Singleton(i), children.First());
1282 }
1283 }
1284 } else {
1285 for (DepGraphIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
1286 auto parents = depgraph_gen.GetReducedParents(i);
1287 if (parents.Any()) {
1288 depgraph_tree.AddDependencies(TestBitSet::Singleton(parents.First()), i);
1289 }
1290 }
1291 }
1292
1293 // Retrieve a linearization from the fuzz input.
1294 std::vector<DepGraphIndex> linearization;
1295 linearization = ReadLinearization(depgraph_tree, reader);
1296 SanityCheck(depgraph_tree, linearization);
1297
1298 // Produce a postlinearized version.
1299 auto post_linearization = linearization;
1300 PostLinearize(depgraph_tree, post_linearization);
1301 SanityCheck(depgraph_tree, post_linearization);
1302
1303 // Compare diagrams.
1304 auto chunking = ChunkLinearization(depgraph_tree, linearization);
1305 auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization);
1306 auto cmp = CompareChunks(post_chunking, chunking);
1307 assert(cmp >= 0);
1308
1309 // Verify that post-linearizing again does not change the diagram. The result must be identical
1310 // as post_linearization ought to be optimal already with a tree-structured graph.
1311 auto post_post_linearization = post_linearization;
1312 PostLinearize(depgraph_tree, post_linearization);
1313 SanityCheck(depgraph_tree, post_linearization);
1314 auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization);
1315 auto cmp_post = CompareChunks(post_post_chunking, post_chunking);
1316 assert(cmp_post == 0);
1317
1318 // Try to find an even better linearization directly. This must not change the diagram for the
1319 // same reason.
1320 auto [opt_linearization, _optimal, _cost] = Linearize(depgraph_tree, 100000, rng_seed, post_linearization);
1321 auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization);
1322 auto cmp_opt = CompareChunks(opt_chunking, post_chunking);
1323 assert(cmp_opt == 0);
1324}
1325
1326FUZZ_TARGET(clusterlin_postlinearize_moved_leaf)
1327{
1328 // Verify that taking an existing linearization, and moving a leaf to the back, potentially
1329 // increasing its fee, and then post-linearizing, results in something as good as the
1330 // original. This guarantees that in an RBF that replaces a transaction with one of the same
1331 // size but higher fee, applying the "remove conflicts, append new transaction, postlinearize"
1332 // process will never worsen linearization quality.
1333
1334 // Construct an arbitrary graph and a fee from the fuzz input.
1335 SpanReader reader(buffer);
1336 DepGraph<TestBitSet> depgraph;
1337 int32_t fee_inc{0};
1338 try {
1339 uint64_t fee_inc_code;
1340 reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(fee_inc_code);
1341 fee_inc = fee_inc_code & 0x3ffff;
1342 } catch (const std::ios_base::failure&) {}
1343 if (depgraph.TxCount() == 0) return;
1344
1345 // Retrieve two linearizations from the fuzz input.
1346 auto lin = ReadLinearization(depgraph, reader);
1347 auto lin_leaf = ReadLinearization(depgraph, reader);
1348
1349 // Construct a linearization identical to lin, but with the tail end of lin_leaf moved to the
1350 // back.
1351 std::vector<DepGraphIndex> lin_moved;
1352 for (auto i : lin) {
1353 if (i != lin_leaf.back()) lin_moved.push_back(i);
1354 }
1355 lin_moved.push_back(lin_leaf.back());
1356
1357 // Postlinearize lin_moved.
1358 PostLinearize(depgraph, lin_moved);
1359 SanityCheck(depgraph, lin_moved);
1360
1361 // Compare diagrams (applying the fee delta after computing the old one).
1362 auto old_chunking = ChunkLinearization(depgraph, lin);
1363 depgraph.FeeRate(lin_leaf.back()).fee += fee_inc;
1364 auto new_chunking = ChunkLinearization(depgraph, lin_moved);
1365 auto cmp = CompareChunks(new_chunking, old_chunking);
1366 assert(cmp >= 0);
1367}
1368
1369FUZZ_TARGET(clusterlin_merge)
1370{
1371 // Construct an arbitrary graph from the fuzz input.
1372 SpanReader reader(buffer);
1373 DepGraph<TestBitSet> depgraph;
1374 try {
1375 reader >> Using<DepGraphFormatter>(depgraph);
1376 } catch (const std::ios_base::failure&) {}
1377
1378 // Retrieve two linearizations from the fuzz input.
1379 auto lin1 = ReadLinearization(depgraph, reader);
1380 auto lin2 = ReadLinearization(depgraph, reader);
1381
1382 // Merge the two.
1383 auto lin_merged = MergeLinearizations(depgraph, lin1, lin2);
1384
1385 // Compute chunkings and compare.
1386 auto chunking1 = ChunkLinearization(depgraph, lin1);
1387 auto chunking2 = ChunkLinearization(depgraph, lin2);
1388 auto chunking_merged = ChunkLinearization(depgraph, lin_merged);
1389 auto cmp1 = CompareChunks(chunking_merged, chunking1);
1390 assert(cmp1 >= 0);
1391 auto cmp2 = CompareChunks(chunking_merged, chunking2);
1392 assert(cmp2 >= 0);
1393}
1394
1395FUZZ_TARGET(clusterlin_fix_linearization)
1396{
1397 // Verify expected properties of FixLinearization() on arbitrary linearizations.
1398
1399 // Retrieve a depgraph from the fuzz input.
1400 SpanReader reader(buffer);
1401 DepGraph<TestBitSet> depgraph;
1402 try {
1403 reader >> Using<DepGraphFormatter>(depgraph);
1404 } catch (const std::ios_base::failure&) {}
1405
1406 // Construct an arbitrary linearization (not necessarily topological for depgraph).
1407 std::vector<DepGraphIndex> linearization;
1409 TestBitSet todo = depgraph.Positions();
1410 while (todo.Any()) {
1411 // Read a number from the fuzz input in range [0, todo.Count()).
1412 uint64_t val{0};
1413 try {
1414 reader >> VARINT(val);
1415 } catch (const std::ios_base::failure&) {}
1416 val %= todo.Count();
1417 // Find the val'th element in todo, remove it from todo, and append it to linearization.
1418 for (auto idx : todo) {
1419 if (val == 0) {
1420 linearization.push_back(idx);
1421 todo.Reset(idx);
1422 break;
1423 }
1424 --val;
1425 }
1426 }
1427 assert(linearization.size() == depgraph.TxCount());
1428
1429 // Determine what prefix of linearization is topological, i.e., the position of the first entry
1430 // in linearization which corresponds to a transaction that is not preceded by all its
1431 // ancestors.
1432 size_t topo_prefix = 0;
1433 todo = depgraph.Positions();
1434 while (topo_prefix < linearization.size()) {
1435 DepGraphIndex idx = linearization[topo_prefix];
1436 todo.Reset(idx);
1437 if (todo.Overlaps(depgraph.Ancestors(idx))) break;
1438 ++topo_prefix;
1439 }
1440
1441 // Then make a fixed copy of linearization.
1442 auto linearization_fixed = linearization;
1443 FixLinearization(depgraph, linearization_fixed);
1444 // Sanity check it (which includes testing whether it is topological).
1445 SanityCheck(depgraph, linearization_fixed);
1446
1447 // FixLinearization does not modify the topological prefix of linearization.
1448 assert(std::equal(linearization.begin(), linearization.begin() + topo_prefix,
1449 linearization_fixed.begin()));
1450 // This also means that if linearization was entirely topological, FixLinearization cannot have
1451 // modified it. This is implied by the assertion above already, but repeat it explicitly.
1452 if (topo_prefix == linearization.size()) {
1453 assert(linearization == linearization_fixed);
1454 }
1455}
#define LIFETIMEBOUND
Definition: attributes.h:16
int ret
const auto command
#define Assume(val)
Assume is the identity function.
Definition: check.h:118
T ConsumeIntegralInRange(T min, T max)
Minimal stream for reading from an existing byte array by std::span.
Definition: streams.h:83
Class encapsulating the state needed to find the best remaining ancestor set.
void MarkDone(SetType select) noexcept
Remove a set of transactions from the set of to-be-linearized ones.
DepGraphIndex NumRemaining() const noexcept
Count the number of remaining unlinearized transactions.
SetInfo< SetType > FindCandidateSet() const noexcept
Find the best (highest-feerate, smallest among those in case of a tie) ancestor set among the remaini...
bool AllDone() const noexcept
Check whether any unlinearized transactions remain.
Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors,...
const SetType & Ancestors(DepGraphIndex i) const noexcept
Get the ancestors of a given transaction i.
SetType GetReducedChildren(DepGraphIndex i) const noexcept
Compute the (reduced) set of children of node i in this graph.
SetType GetReducedParents(DepGraphIndex i) const noexcept
Compute the (reduced) set of parents of node i in this graph.
void AppendTopo(std::vector< DepGraphIndex > &list, const SetType &select) const noexcept
Append the entries of select to list in a topologically valid order.
const FeeFrac & FeeRate(DepGraphIndex i) const noexcept
Get the feerate of a given transaction i.
SetType GetConnectedComponent(const SetType &todo, DepGraphIndex tx) const noexcept
Get the connected component within the subset "todo" that contains tx (which must be in todo).
bool IsConnected(const SetType &subset) const noexcept
Determine if a subset is connected.
DepGraphIndex PositionRange() const noexcept
Get the range of positions in this DepGraph.
SetType FindConnectedComponent(const SetType &todo) const noexcept
Find some connected component within the subset "todo" of this graph.
DepGraphIndex AddTransaction(const FeeFrac &feefrac) noexcept
Add a new unconnected transaction to this transaction graph (in the first available position),...
void RemoveTransactions(const SetType &del) noexcept
Remove the specified positions from this DepGraph.
auto TxCount() const noexcept
Get the number of transactions in the graph.
const SetType & Descendants(DepGraphIndex i) const noexcept
Get the descendants of a given transaction i.
size_t DynamicMemoryUsage() const noexcept
const SetType & Positions() const noexcept
Get the set of transactions positions in use.
void Compact() noexcept
Reduce memory usage if possible.
void AddDependencies(const SetType &parents, DepGraphIndex child) noexcept
Modify this transaction graph, adding multiple parents to a specified child.
bool IsAcyclic() const noexcept
Check if this graph is acyclic.
Data structure encapsulating the chunking of a linearization, permitting removal of subsets.
DepGraphIndex NumChunksLeft() const noexcept
Determine how many chunks remain in the linearization.
const SetInfo< SetType > & GetChunk(DepGraphIndex n) const noexcept
Access a chunk.
SetInfo< SetType > IntersectPrefixes(const SetInfo< SetType > &subset) const noexcept
Find the shortest intersection between subset and the prefixes of remaining chunks of the linearizati...
void MarkDone(SetType subset) noexcept
Remove some subset of transactions from the linearization.
Class encapsulating the state needed to perform search for good candidate sets.
bool AllDone() const noexcept
Check whether any unlinearized transactions remain.
void MarkDone(const SetType &done) noexcept
Remove a subset of transactions from the cluster being linearized.
std::pair< SetInfo< SetType >, uint64_t > FindCandidateSet(uint64_t max_iterations, SetInfo< SetType > best) noexcept
Find a high-feerate topologically-valid subset of what remains of the cluster.
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Definition: fuzz.h:22
uint64_t fee
std::vector< FeeFrac > ChunkLinearization(const DepGraph< SetType > &depgraph, std::span< const DepGraphIndex > linearization) noexcept
Compute the feerates of the chunks of linearization.
std::tuple< std::vector< DepGraphIndex >, bool, uint64_t > Linearize(const DepGraph< SetType > &depgraph, uint64_t max_iterations, uint64_t rng_seed, std::span< const DepGraphIndex > old_linearization={}) noexcept
Find or improve a linearization for a cluster.
void FixLinearization(const DepGraph< SetType > &depgraph, std::span< DepGraphIndex > linearization) noexcept
Make linearization topological, retaining its ordering where possible.
std::vector< DepGraphIndex > MergeLinearizations(const DepGraph< SetType > &depgraph, std::span< const DepGraphIndex > lin1, std::span< const DepGraphIndex > lin2)
Merge two linearizations for the same cluster into one that is as good as both.
uint32_t DepGraphIndex
Data type to represent transaction indices in DepGraphs and the clusters they represent.
void PostLinearize(const DepGraph< SetType > &depgraph, std::span< DepGraphIndex > linearization)
Improve a given linearization.
static std::vector< std::string > split(const std::string &str, const std::string &delims=" \t")
Definition: subprocess.h:315
const char * prefix
Definition: rest.cpp:1117
#define VARINT(obj)
Definition: serialize.h:491
Data structure storing a fee and size, ordered by increasing fee/size.
Definition: feefrac.h:40
int64_t fee
Definition: feefrac.h:107
bool IsEmpty() const noexcept
Check if this is empty (size and fee are 0).
Definition: feefrac.h:120
A set of transactions together with their aggregate feerate.
FeeFrac feerate
Their combined fee and size.
void Set(const DepGraph< SetType > &depgraph, DepGraphIndex pos) noexcept
Add a transaction to this SetInfo (which must not yet be in it).
SetType transactions
The transactions in the set.
FUZZ_TARGET(clusterlin_depgraph_sim)
static constexpr auto MAX_SIMPLE_ITERATIONS
std::partial_ordering CompareChunks(std::span< const FeeFrac > chunks0, std::span< const FeeFrac > chunks1)
Compare the feerate diagrams implied by the provided sorted chunks data.
Definition: feefrac.cpp:10
assert(!tx.IsCoinBase())