Inside Bitcoin

751                    best = accumulator;
752                }
753            }
754        }
755        assert(chunk_feerate == best.feerate);
756        assert(chunk_set == best.transactions);
757        assert(best.transactions.IsSubsetOf(todo));
758        todo -= best.transactions;
759    }
760    assert(todo.None());
761}
762
763static constexpr auto MAX_SIMPLE_ITERATIONS = 300000;
764
765FUZZ_TARGET(clusterlin_simple_finder)
766{
767    // Verify that SimpleCandidateFinder works as expected by sanity checking the results
768    // and comparing them (if claimed to be optimal) against the sets found by
769    // ExhaustiveCandidateFinder.
770    //
771    // Note that SimpleCandidateFinder is only used in tests; the purpose of this fuzz test is to
772    // establish confidence in SimpleCandidateFinder, so that it can be used in SimpleLinearize,
773    // which is then used to test Linearize below.
774
775    // Retrieve a depgraph from the fuzz input.
776    SpanReader reader(buffer);
777    DepGraph<TestBitSet> depgraph;
778    try {
779        reader >> Using<DepGraphFormatter>(depgraph);
780    } catch (const std::ios_base::failure&) {}
781
782    // Instantiate the SimpleCandidateFinder to be tested, and the ExhaustiveCandidateFinder it is
783    // being tested against.
784    SimpleCandidateFinder smp_finder(depgraph);
785    ExhaustiveCandidateFinder exh_finder(depgraph);
786
787    auto todo = depgraph.Positions();
788    while (todo.Any()) {
789        assert(!smp_finder.AllDone());
790        assert(!exh_finder.AllDone());
791
792        // Call SimpleCandidateFinder.
793        auto [found, iterations_done] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
794        bool optimal = (iterations_done != MAX_SIMPLE_ITERATIONS);
795
796        // Sanity check the result.
797        assert(iterations_done <= MAX_SIMPLE_ITERATIONS);
798        assert(found.transactions.Any());
799        assert(found.transactions.IsSubsetOf(todo));
800        assert(depgraph.FeeRate(found.transactions) == found.feerate);
801        // Check that it is topologically valid.
802        for (auto i : found.transactions) {
803            assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo));
804        }
805
806        // At most 2^(N-1) iterations can be required: the number of non-empty connected subsets a
807        // graph with N transactions can have. If MAX_SIMPLE_ITERATIONS exceeds this number, the
808        // result is necessarily optimal.
809        assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
810        if (MAX_SIMPLE_ITERATIONS > (uint64_t{1} << (todo.Count() - 1))) assert(optimal);
811
812        // SimpleCandidateFinder only finds connected sets.
813        assert(depgraph.IsConnected(found.transactions));
814
815        // Perform further quality checks only if SimpleCandidateFinder claims an optimal result.
816        if (optimal) {
817            if (todo.Count() <= 12) {
818                // Compare with ExhaustiveCandidateFinder. This quickly gets computationally
819                // expensive for large clusters (O(2^n)), so only do it for sufficiently small ones.
820                auto exhaustive = exh_finder.FindCandidateSet();
821                assert(exhaustive.feerate == found.feerate);
822            }
823
824            // Compare with a non-empty topological set read from the fuzz input (comparing with an
825            // empty set is not interesting).
826            auto read_topo = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
827            assert(ByRatioNegSize{found.feerate} >= ByRatioNegSize{depgraph.FeeRate(read_topo)});
828        }
829
830        // Find a non-empty topologically valid subset of transactions to remove from the graph.
831        // Using an empty set would mean the next iteration is identical to the current one, and
832        // could cause an infinite loop.
833        auto del_set = ReadTopologicalSet(depgraph, todo, reader, /*non_empty=*/true);
834        todo -= del_set;
835        smp_finder.MarkDone(del_set);
836        exh_finder.MarkDone(del_set);
837    }
838
839    assert(smp_finder.AllDone());
840    assert(exh_finder.AllDone());
841}
842
843FUZZ_TARGET(clusterlin_simple_linearize)
844{
845    // Verify the behavior of SimpleLinearize(). Note that SimpleLinearize is only used in tests;
846    // the purpose of this fuzz test is to establish confidence in SimpleLinearize, so that it can
847    // be used to test the real Linearize function in the fuzz test below.
848
849    // Retrieve an iteration count and a depgraph from the fuzz input.
850    SpanReader reader(buffer);
851    uint64_t iter_count{0};
852    DepGraph<TestBitSet> depgraph;
853    try {
854        reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph);
855    } catch (const std::ios_base::failure&) {}
856    iter_count %= MAX_SIMPLE_ITERATIONS;
857
858    // Invoke SimpleLinearize().
859    auto [linearization, optimal] = SimpleLinearize(depgraph, iter_count);
860    SanityCheck(depgraph, linearization);
861    auto simple_chunking = ChunkLinearization(depgraph, linearization);
862
863    // If the iteration count is sufficiently high, an optimal linearization must be found.
864    // SimpleLinearize on k transactions can take up to 2^(k-1) iterations (one per non-empty
865    // connected topologically valid subset), which sums over k=1..n to (2^n)-1.
866    const uint64_t n = depgraph.TxCount();
867    if (n <= 63 && (iter_count >> n)) {
868        assert(optimal);
869    }
870
871    // If SimpleLinearize claims optimal result, and the cluster is sufficiently small (there are
872    // n! linearizations), test that the result is as good as every valid linearization.
873    if (optimal && depgraph.TxCount() <= 8) {
874        auto exh_linearization = ExhaustiveLinearize(depgraph);
875        auto exh_chunking = ChunkLinearization(depgraph, exh_linearization);
876        auto cmp = CompareChunks(simple_chunking, exh_chunking);
877        assert(cmp == 0);
878        assert(simple_chunking.size() == exh_chunking.size());
879    }
880
881    if (optimal) {
882        // Compare with a linearization read from the fuzz input.
883        auto read = ReadLinearization(depgraph, reader);
884        auto read_chunking = ChunkLinearization(depgraph, read);
885        auto cmp = CompareChunks(simple_chunking, read_chunking);
886        assert(cmp >= 0);
887    }
888}
889
890FUZZ_TARGET(clusterlin_sfl)
891{
892    // Verify the individual steps of the SFL algorithm.
893
894    SpanReader reader(buffer);
895    DepGraph<TestBitSet> depgraph;
896    uint8_t flags{1};
897    uint64_t rng_seed{0};
898    try {
899        reader >> rng_seed >> flags >> Using<DepGraphFormatter>(depgraph);
900    } catch (const std::ios_base::failure&) {}
901    if (depgraph.TxCount() <= 1) return;
902    InsecureRandomContext rng(rng_seed);
903    /** Whether to make the depgraph connected. */
904    const bool make_connected = flags & 1;
905    /** Whether to load some input linearization into the state. */
906    const bool load_linearization = flags & 2;
907    /** Whether that input linearization is topological. */
908    const bool load_topological = load_linearization && (flags & 4);
909
910    // Initialize SFL state.
911    if (make_connected) MakeConnected(depgraph);
912    SpanningForestState sfl(depgraph, rng.rand64());
913
914    // Function to test the state.
915    std::vector<FeeFrac> last_diagram;
916    bool was_optimal{false};
917    auto test_fn = [&](bool is_optimal = false, bool is_minimal = false) {
918        if (rng.randbits(4) == 0) {
919            // Perform sanity checks from time to time (too computationally expensive to do after
920            // every step).
921            sfl.SanityCheck();
922        }
923        auto diagram = sfl.GetDiagram();
924        if (rng.randbits(4) == 0) {
925            // Verify that the diagram of GetLinearization() is at least as good as GetDiagram(),
926            // from time to time.
927            auto lin = sfl.GetLinearization(IndexTxOrder{});
928            auto lin_diagram = ChunkLinearization(depgraph, lin);
929            auto cmp_lin = CompareChunks(lin_diagram, diagram);
930            assert(cmp_lin >= 0);
931            // If we're in an allegedly optimal state, they must match.
932            if (is_optimal) assert(cmp_lin == 0);
933            // If we're in an allegedly minimal state, they must also have the same number of
934            // segments.
935            if (is_minimal) assert(diagram.size() == lin_diagram.size());
936        }
937        // Verify that subsequent calls to GetDiagram() never get worse/incomparable.
938        if (!last_diagram.empty()) {
939            auto cmp = CompareChunks(diagram, last_diagram);
940            assert(cmp >= 0);
941            // If the last diagram was already optimal, the new one cannot be better.
942            if (was_optimal) assert(cmp == 0);
943            // Also, if the diagram was already optimal, the number of segments can only increase.
944            if (was_optimal) assert(diagram.size() >= last_diagram.size());
945        }
946        last_diagram = std::move(diagram);
947        was_optimal = is_optimal;
948    };
949
950    if (load_linearization) {
951        auto input_lin = ReadLinearization(depgraph, reader, load_topological);
952        sfl.LoadLinearization(input_lin);
953        if (load_topological) {
954            // The diagram of the loaded linearization forms an initial lower bound on future
955            // diagrams.
956            last_diagram = ChunkLinearization(depgraph, input_lin);
957        } else {
958            // The input linearization may have been non-topological, so invoke MakeTopological to
959            // fix it still.
960            sfl.MakeTopological();
961        }
962    } else {
963        // Invoke MakeTopological to create an initial from-scratch topological state.
964        sfl.MakeTopological();
965    }
966
967    // Loop until optimal.
968    test_fn();
969    sfl.StartOptimizing();
970    while (true) {
971        test_fn();
972        if (!sfl.OptimizeStep()) break;
973    }
974
975    // Loop until minimal.
976    test_fn(/*is_optimal=*/true);
977    sfl.StartMinimizing();
978    while (true) {
979        test_fn(/*is_optimal=*/true);
980        if (!sfl.MinimizeStep()) break;
981    }
982    test_fn(/*is_optimal=*/true, /*is_minimal=*/true);
983
984    // Verify that optimality is reached within an expected amount of work. This protects against
985    // hypothetical bugs that hugely increase the amount of work needed to reach optimality.
986    assert(sfl.GetCost() <= MaxOptimalLinearizationCost(depgraph.TxCount()));
987
988    // The result must be as good as SimpleLinearize.
989    auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS / 10);
990    auto simple_diagram = ChunkLinearization(depgraph, simple_linearization);
991    auto simple_cmp = CompareChunks(last_diagram, simple_diagram);
992    assert(simple_cmp >= 0);
993    if (simple_optimal) assert(simple_cmp == 0);
994    // If the diagram matches, we must also have at least as many segments (because the SFL state
995    // and its produced diagram are minimal);
996    if (simple_cmp == 0) assert(last_diagram.size() >= simple_diagram.size());
997
998    // We can compare with any arbitrary linearization, and the diagram must be at least as good as
999    // each.
1000    for (int i = 0; i < 10; ++i) {