Inside Bitcoin
Opening the selected file…
Inside Bitcoin
Opening the selected file…
The code behind the network, with room to understand it.
Release published 2026-10-28 · Snapshot fetched 2026-11-01. Latest stable release at fetch time; development branches and Git history are excluded. Only the selected code window and visible folders load here.
751auto component = sel_sim.graph.GetConnectedComponent(sel_sim.graph.Positions(), simpos);752// Remember the lowest-index SimPos in component, as a representative for it.753assert(component.Any());754sim_reps.Set(component.First());755}756// Compare the number of deduplicated representatives with the value returned by757// the real function.758assert(result == sim_reps.Count());759break;760} else if (command-- == 0) {761// DoWork.762uint64_t max_cost = provider.ConsumeIntegralInRange<uint64_t>(0, alt ? 10000 : 255);763bool ret = real->DoWork(max_cost);764uint64_t cost_for_optimal{0};765for (unsigned level = 0; level < sims.size(); ++level) {766// DoWork() will not optimize oversized levels, or the main level if a builder767// is present. Note that this impacts the DoWork() return value, as true means768// that non-optimal clusters may remain within such oversized or builder-having769// levels.770if (sims[level].IsOversized()) continue;771if (level == 0 && !block_builders.empty()) continue;772// If neither of the two above conditions holds, and DoWork() returned true,773// then the level is optimal.774if (ret) {775sims[level].real_is_optimal = true;776}777// Compute how much work would be needed to make everything optimal.778for (auto component : sims[level].GetComponents()) {779auto cost_opt_this_cluster = MaxOptimalLinearizationCost(component.Count());780if (cost_opt_this_cluster > acceptable_cost) {781// If the amount of work required to linearize this cluster782// optimally exceeds acceptable_cost, DoWork() may process it in two783// stages: once to acceptable, and once to optimal.784cost_for_optimal += cost_opt_this_cluster + acceptable_cost;785} else {786cost_for_optimal += cost_opt_this_cluster;787}788}789}790if (!ret) {791// DoWork can only have more work left if the requested amount of work792// was insufficient to linearize everything optimally within the levels it is793// allowed to touch.794assert(max_cost <= cost_for_optimal);795}796break;797} else if (sims.size() == 2 && !sims[0].IsOversized() && !sims[1].IsOversized() && command-- == 0) {798// GetMainStagingDiagrams()799auto [real_main_diagram, real_staged_diagram] = real->GetMainStagingDiagrams();800auto real_sum_main = std::accumulate(real_main_diagram.begin(), real_main_diagram.end(), FeeFrac{});801auto real_sum_staged = std::accumulate(real_staged_diagram.begin(), real_staged_diagram.end(), FeeFrac{});802auto real_gain = real_sum_staged - real_sum_main;803auto sim_gain = sims[1].SumAll() - sims[0].SumAll();804// Just check that the total fee gained/lost and size gained/lost according to the805// diagram matches the difference in these values in the simulated graph. A more806// complete check of the GetMainStagingDiagrams result is performed at the end.807assert(sim_gain == real_gain);808// Check that the feerates in each diagram are monotonically decreasing.809for (size_t i = 1; i < real_main_diagram.size(); ++i) {810assert(ByRatio{real_main_diagram[i]} <= ByRatio{real_main_diagram[i - 1]});811}812for (size_t i = 1; i < real_staged_diagram.size(); ++i) {813assert(ByRatio{real_staged_diagram[i]} <= ByRatio{real_staged_diagram[i - 1]});814}815break;816} else if (block_builders.size() < 4 && !main_sim.IsOversized() && command-- == 0) {817// GetBlockBuilder.818block_builders.emplace_back(real->GetBlockBuilder());819break;820} else if (!block_builders.empty() && command-- == 0) {821// ~BlockBuilder.822block_builders.erase(block_builders.begin() + builder_idx);823break;824} else if (!block_builders.empty() && command-- == 0) {825// BlockBuilder::GetCurrentChunk, followed by Include/Skip.826auto& builder_data = block_builders[builder_idx];827auto new_included = builder_data.included;828auto new_done = builder_data.done;829auto chunk = builder_data.builder->GetCurrentChunk();830if (chunk) {831// Chunk feerates must be monotonously decreasing.832if (!builder_data.last_feerate.IsEmpty()) {833assert(ByRatio{chunk->second} <= ByRatio{builder_data.last_feerate});834}835builder_data.last_feerate = chunk->second;836// Verify the contents of GetCurrentChunk.837FeePerWeight sum_feerate;838for (TxGraph::Ref* ref : chunk->first) {839// Each transaction in the chunk must exist in the main graph.840auto simpos = main_sim.Find(ref);841assert(simpos != SimTxGraph::MISSING);842// Verify the claimed chunk feerate.843sum_feerate += main_sim.graph.FeeRate(simpos);844// Make sure no transaction is reported twice.845assert(!new_done[simpos]);846new_done.Set(simpos);847// The concatenation of all included transactions must be topologically valid.848new_included.Set(simpos);849assert(main_sim.graph.Ancestors(simpos).IsSubsetOf(new_included));850}851assert(sum_feerate == chunk->second);852} else {853// When we reach the end, if nothing was skipped, the entire graph should have854// been reported.855if (builder_data.done == builder_data.included) {856assert(builder_data.done.Count() == main_sim.GetTransactionCount());857}858}859// Possibly invoke GetCurrentChunk() again, which should give the same result.860if ((orig_command % 7) >= 5) {861auto chunk2 = builder_data.builder->GetCurrentChunk();862assert(chunk == chunk2);863}864// Skip or include.865if ((orig_command % 5) >= 3) {866// Skip.867builder_data.builder->Skip();868} else {869// Include.870builder_data.builder->Include();871builder_data.included = new_included;872}873builder_data.done = new_done;874break;875} else if (!main_sim.IsOversized() && command-- == 0) {876// GetWorstMainChunk.877auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();878// Just do some sanity checks here. Consistency with GetBlockBuilder is checked879// below.880if (main_sim.GetTransactionCount() == 0) {881assert(worst_chunk.empty());882assert(worst_chunk_feerate.IsEmpty());883} else {884assert(!worst_chunk.empty());885SimTxGraph::SetType done;886FeePerWeight sum;887for (TxGraph::Ref* ref : worst_chunk) {888// Each transaction in the chunk must exist in the main graph.889auto simpos = main_sim.Find(ref);890assert(simpos != SimTxGraph::MISSING);891sum += main_sim.graph.FeeRate(simpos);892// Make sure the chunk contains no duplicate transactions.893assert(!done[simpos]);894done.Set(simpos);895// All elements are preceded by all their descendants.896assert(main_sim.graph.Descendants(simpos).IsSubsetOf(done));897}898assert(sum == worst_chunk_feerate);899}900break;901} else if ((block_builders.empty() || sims.size() > 1) && command-- == 0) {902// Trim.903bool was_oversized = top_sim.IsOversized();904auto removed = real->Trim();905// Verify that something was removed if and only if there was an oversized cluster.906assert(was_oversized == !removed.empty());907if (!was_oversized) break;908auto removed_set = top_sim.MakeSet(removed);909// The removed set must contain all its own descendants.910for (auto simpos : removed_set) {911assert(top_sim.graph.Descendants(simpos).IsSubsetOf(removed_set));912}913// Something from every oversized cluster should have been removed, and nothing914// else.915assert(top_sim.MatchesOversizedClusters(removed_set));917// Apply all removals to the simulation, and verify the result is no longer918// oversized. Don't query the real graph for oversizedness; it is compared919// against the simulation anyway later.920for (auto simpos : removed_set) {921top_sim.RemoveTransaction(top_sim.GetRef(simpos));922}923assert(!top_sim.IsOversized());924break;925} else if ((block_builders.empty() || sims.size() > 1) &&926top_sim.GetTransactionCount() > max_cluster_count && !top_sim.IsOversized() && command-- == 0) {927// Trim (special case which avoids apparent cycles in the implicit approximate928// dependency graph constructed inside the Trim() implementation). This is worth929// testing separately, because such cycles cannot occur in realistic scenarios,930// but this is hard to replicate in general in this fuzz test.932// First, we need to have dependencies applied and linearizations fixed to avoid933// circular dependencies in implied graph; trigger it via whatever means.934real->CountDistinctClusters({}, TxGraph::Level::TOP);936// Gather the current clusters.937auto clusters = top_sim.GetComponents();939// Merge clusters randomly until at least one oversized one appears.940bool made_oversized = false;941auto merges_left = clusters.size() - 1;942while (merges_left > 0) {943--merges_left;944// Find positions of clusters in the clusters vector to merge together.945auto par_cl = rng.randrange(clusters.size());946auto chl_cl = rng.randrange(clusters.size() - 1);947chl_cl += (chl_cl >= par_cl);948Assume(chl_cl != par_cl);949// Add between 1 and 3 dependencies between them. As all are in the same950// direction (from the child cluster to parent cluster), no cycles are possible,951// regardless of what internal topology Trim() uses as approximation within the952// clusters.953int num_deps = rng.randrange(3) + 1;954for (int i = 0; i < num_deps; ++i) {955// Find a parent transaction in the parent cluster.956auto par_idx = rng.randrange(clusters[par_cl].Count());957SimTxGraph::Pos par_pos = 0;958for (auto j : clusters[par_cl]) {959if (par_idx == 0) {960par_pos = j;961break;962}963--par_idx;964}965// Find a child transaction in the child cluster.966auto chl_idx = rng.randrange(clusters[chl_cl].Count());967SimTxGraph::Pos chl_pos = 0;968for (auto j : clusters[chl_cl]) {969if (chl_idx == 0) {970chl_pos = j;971break;972}973--chl_idx;974}975// Add dependency to both simulation and real TxGraph.976auto par_ref = top_sim.GetRef(par_pos);977auto chl_ref = top_sim.GetRef(chl_pos);978top_sim.AddDependency(par_ref, chl_ref);979real->AddDependency(*par_ref, *chl_ref);980}981// Compute the combined cluster.982auto par_cluster = clusters[par_cl];983auto chl_cluster = clusters[chl_cl];984auto new_cluster = par_cluster | chl_cluster;985// Remove the parent and child cluster from clusters.986std::erase_if(clusters, [&](const auto& cl) noexcept { return cl == par_cluster || cl == chl_cluster; });987// Add the combined cluster.988clusters.push_back(new_cluster);989// If this is the first merge that causes an oversized cluster to appear, pick990// a random number of further merges to appear.991if (!made_oversized) {992made_oversized = new_cluster.Count() > max_cluster_count;993if (!made_oversized) {994FeeFrac total;995for (auto i : new_cluster) total += top_sim.graph.FeeRate(i);996if (uint32_t(total.size) > max_cluster_size) made_oversized = true;997}998if (made_oversized) merges_left = rng.randrange(clusters.size());999}1000}
Independent explanations by MyBitcoinExplorer. Not affiliated with or endorsed by Bitcoin Core. Guides are educational and do not replace the source or its tests.
Bitcoin Core source © its contributors, distributed under the MIT license. Original notices and bundled third-party licenses are retained in the source tree.