Inside Bitcoin

251    }
252
253    /** Given a set of Refs (given as a vector of pointers), expand the set to include all its
254     *  ancestors (desc=false) or all its descendants (desc=true) in this graph. */
255    void IncludeAncDesc(std::vector<TxGraph::Ref*>& arg, bool desc)
256    {
257        std::vector<TxGraph::Ref*> ret;
258        for (auto ptr : arg) {
259            auto simpos = Find(ptr);
260            if (simpos != MISSING) {
261                for (auto i : desc ? graph.Descendants(simpos) : graph.Ancestors(simpos)) {
262                    ret.push_back(simmap[i].get());
263                }
264            } else {
265                ret.push_back(ptr);
266            }
267        }
268        // Construct deduplicated version in input (do not use std::sort/std::unique for
269        // deduplication as it'd rely on non-deterministic pointer comparison).
270        arg.clear();
271        for (auto ptr : ret) {
272            if (std::find(arg.begin(), arg.end(), ptr) == arg.end()) {
273                arg.push_back(ptr);
274            }
275        }
276    }
277
278
279    /** Verify that set contains transactions from every oversized cluster, and nothing from
280     *  non-oversized ones. */
281    bool MatchesOversizedClusters(const SetType& set)
282    {
283        if (set.Any() && !IsOversized()) return false;
284
285        auto todo = graph.Positions();
286        if (!set.IsSubsetOf(todo)) return false;
287
288        // Walk all clusters, and make sure all of set doesn't come from non-oversized clusters
289        while (todo.Any()) {
290            auto component = graph.FindConnectedComponent(todo);
291            // Determine whether component is oversized, due to either the size or count limit.
292            bool is_oversized = component.Count() > max_cluster_count;
293            uint64_t component_size{0};
294            for (auto i : component) component_size += graph.FeeRate(i).size;
295            is_oversized |= component_size > max_cluster_size;
296            // Check whether overlap with set matches is_oversized.
297            if (is_oversized != set.Overlaps(component)) return false;
298            todo -= component;
299        }
300        return true;
301    }
302};
303
304} // namespace
305
306FUZZ_TARGET(txgraph)
307{
308    // This is a big simulation test for TxGraph, which performs a fuzz-derived sequence of valid
309    // operations on a TxGraph instance, as well as on a simpler (mostly) reimplementation (see
310    // SimTxGraph above), comparing the outcome of functions that return a result, and finally
311    // performing a full comparison between the two.
312
313    SeedRandomStateForTest(SeedRand::ZEROS);
314    FuzzedDataProvider provider(buffer.data(), buffer.size());
315
316    /** Internal test RNG, used only for decisions which would require significant amount of data
317     *  to be read from the provider, without realistically impacting test sensitivity, and for
318     *  specialized test cases that are hard to perform more generically. */
319    InsecureRandomContext rng(provider.ConsumeIntegral<uint64_t>());
320
321    /** Variable used whenever an empty SimTxObject is needed. */
322    SimTxObject empty_ref;
323
324    /** The maximum number of transactions per (non-oversized) cluster we will use in this
325     *  simulation. */
326    auto max_cluster_count = provider.ConsumeIntegralInRange<DepGraphIndex>(1, MAX_CLUSTER_COUNT_LIMIT);
327    /** The maximum total size of transactions in a (non-oversized) cluster. */
328    auto max_cluster_size = provider.ConsumeIntegralInRange<uint64_t>(1, 0x3fffff * MAX_CLUSTER_COUNT_LIMIT);
329    /** The amount of work to consider a cluster acceptably linearized. */
330    auto acceptable_cost = provider.ConsumeIntegralInRange<uint64_t>(0, 10000);
331
332    /** The set of uint64_t "txid"s that have been assigned before. */
333    std::set<uint64_t> assigned_txids;
334
335    // Construct a real graph, and a vector of simulated graphs (main, and possibly staging).
336    auto fallback_order = [&](const TxGraph::Ref& a, const TxGraph::Ref& b) noexcept {
337        uint64_t txid_a = static_cast<const SimTxObject&>(a).m_txid;
338        uint64_t txid_b = static_cast<const SimTxObject&>(b).m_txid;
339        assert(assigned_txids.contains(txid_a));
340        assert(assigned_txids.contains(txid_b));
341        return txid_a <=> txid_b;
342    };
343    auto real = MakeTxGraph(
344        /*max_cluster_count=*/max_cluster_count,
345        /*max_cluster_size=*/max_cluster_size,
346        /*acceptable_cost=*/acceptable_cost,
347        /*fallback_order=*/fallback_order);
348
349    std::vector<SimTxGraph> sims;
350    sims.reserve(2);
351    sims.emplace_back(max_cluster_count, max_cluster_size);
352
353    /** Struct encapsulating information about a BlockBuilder that's currently live. */
354    struct BlockBuilderData
355    {
356        /** BlockBuilder object from real. */
357        std::unique_ptr<TxGraph::BlockBuilder> builder;
358        /** The set of transactions marked as included in *builder. */
359        SimTxGraph::SetType included;
360        /** The set of transactions marked as included or skipped in *builder. */
361        SimTxGraph::SetType done;
362        /** The last chunk feerate returned by *builder. IsEmpty() if none yet. */
363        FeePerWeight last_feerate;
364
365        BlockBuilderData(std::unique_ptr<TxGraph::BlockBuilder> builder_in) : builder(std::move(builder_in)) {}
366    };
367
368    /** Currently active block builders. */
369    std::vector<BlockBuilderData> block_builders;
370
371    /** Function to pick any SimTxObject (for either sim in sims: from sim.simmap or sim.removed, or the
372     *  empty one). */
373    auto pick_fn = [&]() noexcept -> SimTxObject* {
374        size_t tx_count[2] = {sims[0].GetTransactionCount(), 0};
375        /** The number of possible choices. */
376        size_t choices = tx_count[0] + sims[0].removed.size() + 1;
377        if (sims.size() == 2) {
378            tx_count[1] = sims[1].GetTransactionCount();
379            choices += tx_count[1] + sims[1].removed.size();
380        }
381        /** Pick one of them. */
382        auto choice = provider.ConsumeIntegralInRange<size_t>(0, choices - 1);
383        // Consider both main and (if it exists) staging.
384        for (size_t level = 0; level < sims.size(); ++level) {
385            auto& sim = sims[level];
386            if (choice < tx_count[level]) {
387                // Return from graph.
388                for (auto i : sim.graph.Positions()) {
389                    if (choice == 0) return sim.GetRef(i);
390                    --choice;
391                }
392                assert(false);
393            } else {
394                choice -= tx_count[level];
395            }
396            if (choice < sim.removed.size()) {
397                // Return from removed.
398                return sim.removed[choice].get();
399            } else {
400                choice -= sim.removed.size();
401            }
402        }
403        // Return empty.
404        assert(choice == 0);
405        return &empty_ref;
406    };
407
408    /** Function to construct the correct fee-size diagram a real graph has based on its graph
409     *  order (as reported by GetCluster(), so it works for both main and staging). */
410    auto get_diagram_fn = [&](TxGraph::Level level_select) -> std::vector<FeeFrac> {
411        int level = level_select == TxGraph::Level::MAIN ? 0 : sims.size() - 1;
412        auto& sim = sims[level];
413        // For every transaction in the graph, request its cluster, and throw them into a set.
414        std::set<std::vector<TxGraph::Ref*>> clusters;
415        for (auto i : sim.graph.Positions()) {
416            auto ref = sim.GetRef(i);
417            clusters.insert(real->GetCluster(*ref, level_select));
418        }
419        // Compute the chunkings of each (deduplicated) cluster.
420        size_t num_tx{0};
421        std::vector<FeeFrac> chunk_feerates;
422        for (const auto& cluster : clusters) {
423            num_tx += cluster.size();
424            std::vector<SimTxGraph::Pos> linearization;
425            linearization.reserve(cluster.size());
426            for (auto refptr : cluster) linearization.push_back(sim.Find(refptr));
427            for (const FeeFrac& chunk_feerate : ChunkLinearization(sim.graph, linearization)) {
428                chunk_feerates.push_back(chunk_feerate);
429            }
430        }
431        // Verify the number of transactions after deduplicating clusters. This implicitly verifies
432        // that GetCluster on each element of a cluster reports the cluster transactions in the same
433        // order.
434        assert(num_tx == sim.GetTransactionCount());
435        // Sort by feerate only, since violating topological constraints within same-feerate
436        // chunks won't affect diagram comparisons.
437        std::ranges::sort(chunk_feerates, std::greater<ByRatioNegSize<FeeFrac>>{});
438        return chunk_feerates;
439    };
440
441    LIMITED_WHILE (provider.remaining_bytes() > 0, 200) {
442        // Read a one-byte command.
443        int command = provider.ConsumeIntegral<uint8_t>();
444        int orig_command = command;
445
446        // Treat the lowest bit of a command as a flag (which selects a variant of some of the
447        // operations), and the second-lowest bit as a way of selecting main vs. staging, and leave
448        // the rest of the bits in command.
449        bool alt = command & 1;
450        TxGraph::Level level_select = (command & 2) ? TxGraph::Level::MAIN : TxGraph::Level::TOP;
451        command >>= 2;
452
453        /** Use the bottom 2 bits of command to select an entry in the block_builders vector (if
454         *  any). These use the same bits as alt/level_select, so don't use those in actions below
455         *  where builder_idx is used as well. */
456        int builder_idx = block_builders.empty() ? -1 : int((orig_command & 3) % block_builders.size());
457
458        // Provide convenient aliases for the top simulated graph (main, or staging if it exists),
459        // one for the simulated graph selected based on level_select (for operations that can operate
460        // on both graphs), and one that always refers to the main graph.
461        auto& top_sim = sims.back();
462        auto& sel_sim = level_select == TxGraph::Level::MAIN ? sims[0] : top_sim;
463        auto& main_sim = sims[0];
464
465        // Keep decrementing command for each applicable operation, until one is hit. Multiple
466        // iterations may be necessary.
467        while (true) {
468            if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() < SimTxGraph::MAX_TRANSACTIONS && command-- == 0) {
469                // AddTransaction.
470                int64_t fee;
471                int32_t size;
472                if (alt) {
473                    // If alt is true, pick fee and size from the entire range.
474                    fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff);
475                    size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff);
476                } else {
477                    // Otherwise, use smaller range which consume fewer fuzz input bytes, as just
478                    // these are likely sufficient to trigger all interesting code paths already.
479                    fee = provider.ConsumeIntegral<uint8_t>();
480                    size = provider.ConsumeIntegralInRange<uint32_t>(1, 0xff);
481                }
482                FeePerWeight feerate{fee, size};
483                // Pick a novel txid (and not 0, which is reserved for empty_ref).
484                uint64_t txid;
485                do {
486                    txid = rng.rand64();
487                } while (txid == 0 || assigned_txids.contains(txid));
488                assigned_txids.insert(txid);
489                // Create the transaction in the simulation and the real graph.
490                top_sim.AddTransaction(*real, feerate, txid);
491                break;
492            } else if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() + top_sim.removed.size() > 1 && command-- == 0) {
493                // AddDependency.
494                auto par = pick_fn();
495                auto chl = pick_fn();
496                auto pos_par = top_sim.Find(par);
497                auto pos_chl = top_sim.Find(chl);
498                if (pos_par != SimTxGraph::MISSING && pos_chl != SimTxGraph::MISSING) {
499                    // Determine if adding this would introduce a cycle (not allowed by TxGraph),
500                    // and if so, skip.