Repository: bitcoin/bitcoin
File: src/test/fuzz/cluster_linearize.cpp (C++)

Code before:
        assert(anc_finder.NumRemaining() == todo.Count());

        // Call SimpleCandidateFinder.
        auto [found, iterations_done] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS);
        bool optimal = (iterations_done != MAX_SIMPLE_ITERATIONS);

        // Sanity check the result.
        assert(iterations_done <= MAX_SIMPLE_ITERATIONS);
        assert(found.transactions.Any());
        assert(found.transactions.IsSubsetOf(todo));
        assert(depgraph.FeeRate(found.transactions) == found.feerate);
        // Check that it is topologically valid.
        for (auto i : found.transactions) {
            assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo));
        }

        // At most 2^(N-1) iterations can be required: the number of non-empty connected subsets a
        // graph with N transactions can have. If MAX_SIMPLE_ITERATIONS exceeds this number, the
        // result is necessarily optimal.
        assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
        if (MAX_SIMPLE_ITERATIONS > (uint64_t{1} << (todo.Count() - 1))) assert(optimal);

        // Perform quality checks only if SimpleCandidateFinder claims an optimal result.
        if (optimal) {
            // Optimal sets are always connected.
            assert(depgraph.IsConnected(found.transactions));

            // Compare with AncestorCandidateFinder.
            auto anc = anc_finder.FindCandidateSet();
            assert(anc.feerate <= found.feerate);

            if (todo.Count() <= 12) {
                // Compare with ExhaustiveCandidateFinder. This quickly gets computationally
                // expensive for large clusters (O(2^n)), so only do it for sufficiently small ones.
                auto exhaustive = exh_finder.FindCandidateSet();
                assert(exhaustive.feerate == found.feerate);
            }
        }

        // Find a topologically valid subset of transactions to remove from the graph.
        auto del_set = ReadTopologicalSet(depgraph, todo, reader);
        // If we did not find anything, use found itself, because we should remove something.
        if (del_set.None()) del_set = found.transactions;
        todo -= del_set;
        smp_finder.MarkDone(del_set);
        exh_finder.MarkDone(del_set);
        anc_finder.MarkDone(del_set);
    }

    assert(smp_finder.AllDone());
    assert(exh_finder.AllDone());

Review comment (bug):
IIUC `FindCandidateSet` only adds connected sets and there is is comment in line 74-75 that explains that.
so even when not optimal this assertion will hold.

I've been running a version of this commit with the assertion above if optimal and no crash after a long time.

Code after:
    }

    // No components can be found in an empty subset.
    assert(depgraph.FindConnectedComponent(todo).None());
}

FUZZ_TARGET(clusterlin_make_connected)
{
    // Verify that MakeConnected makes graphs connected.

    SpanReader reader(buffer);
    DepGraph<TestBitSet> depgraph;
    try {
        reader >> Using<DepGraphFormatter>(depgraph);
    } catch (const std::ios_base::failure&) {}
    MakeConnected(depgraph);
    SanityCheck(depgraph);
    assert(depgraph.IsConnected());
}

FUZZ_TARGET(clusterlin_chunking)
{
    // Verify the correctness of the ChunkLinearization function.

    // Construct a graph by deserializing.
    SpanReader reader(buffer);
    DepGraph<TestBitSet> depgraph;
    try {
        reader >> Using<DepGraphFormatter>(depgraph);
    } catch (const std::ios_base::failure&) {}

    // Read a valid linearization for depgraph.
    auto linearization = ReadLinearization(depgraph, reader);

    // Invoke the chunking function.
    auto chunking = ChunkLinearization(depgraph, linearization);

    // Verify that chunk feerates are monotonically non-increasing.
    for (size_t i = 1; i < chunking.size(); ++i) {
        assert(!(chunking[i] >> chunking[i - 1]));
    }

    // Naively recompute the chunks (each is the highest-feerate prefix of what remains).
    auto todo = depgraph.Positions();
    for (const auto& chunk_feerate : chunking) {
        assert(todo.Any());
        SetInfo<TestBitSet> accumulator, best;
        for (DepGraphIndex idx : linearization) {
            if (todo[idx]) {
                accumulator.Set(depgraph, idx);
                if (best.feerate.IsEmpty() || accumulator.feerate >> best.feerate) {