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.
1001auto read_lin = ReadLinearization(depgraph, reader);1002auto read_diagram = ChunkLinearization(depgraph, read_lin);1003auto cmp = CompareChunks(last_diagram, read_diagram);1004assert(cmp >= 0);1005if (cmp == 0) assert(last_diagram.size() >= read_diagram.size());1006}1007}1009FUZZ_TARGET(clusterlin_linearize)1010{1011// Verify the behavior of Linearize().1013// Retrieve an RNG seed, a maximum amount of work, a depgraph, and whether to make it connected1014// from the fuzz input.1015SpanReader reader(buffer);1016DepGraph<TestBitSet> depgraph;1017uint64_t rng_seed{0};1018uint64_t max_cost{0};1019uint8_t flags{7};1020try {1021reader >> VARINT(max_cost) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> flags;1022} catch (const std::ios_base::failure&) {}1023if (depgraph.TxCount() <= 1) return;1024bool make_connected = flags & 1;1025// The following 3 booleans have 4 combinations:1026// - (flags & 6) == 0: do not provide input linearization.1027// - (flags & 6) == 2: provide potentially non-topological input.1028// - (flags & 6) == 4: provide topological input linearization, but do not claim it is1029// topological.1030// - (flags & 6) == 6: provide topological input linearization, and claim it is topological.1031bool provide_input = flags & 6;1032bool provide_topological_input = flags & 4;1033bool claim_topological_input = (flags & 6) == 6;1034// The most complicated graphs are connected ones (other ones just split up). Optionally force1035// the graph to be connected.1036if (make_connected) MakeConnected(depgraph);1038// Optionally construct an old linearization for it.1039std::vector<DepGraphIndex> old_linearization;1040if (provide_input) {1041old_linearization = ReadLinearization(depgraph, reader, /*topological=*/provide_topological_input);1042if (provide_topological_input) SanityCheck(depgraph, old_linearization);1043}1045// Invoke Linearize().1046max_cost &= 0x3fffff;1047auto [linearization, optimal, cost] = Linearize(1048/*depgraph=*/depgraph,1049/*max_cost=*/max_cost,1050/*rng_seed=*/rng_seed,1051/*fallback_order=*/IndexTxOrder{},1052/*old_linearization=*/old_linearization,1053/*is_topological=*/claim_topological_input);1054SanityCheck(depgraph, linearization);1055auto chunking = ChunkLinearization(depgraph, linearization);1057// Linearization must always be as good as the old one, if provided and topological (even when1058// not claimed to be topological).1059if (provide_topological_input) {1060auto old_chunking = ChunkLinearization(depgraph, old_linearization);1061auto cmp = CompareChunks(chunking, old_chunking);1062assert(cmp >= 0);1063}1065// If the maximum amount of work is sufficiently high, an optimal linearization must be found.1066if (max_cost > MaxOptimalLinearizationCost(depgraph.TxCount())) {1067assert(optimal);1068}1070// If Linearize claims optimal result, run quality tests.1071if (optimal) {1072// It must be as good as SimpleLinearize.1073auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS);1074SanityCheck(depgraph, simple_linearization);1075auto simple_chunking = ChunkLinearization(depgraph, simple_linearization);1076auto cmp = CompareChunks(chunking, simple_chunking);1077assert(cmp >= 0);1078// If SimpleLinearize finds the optimal result too, they must be equal (if not,1079// SimpleLinearize is broken).1080if (simple_optimal) assert(cmp == 0);1082// If simple_chunking is diagram-optimal, it cannot have more chunks than chunking (as1083// chunking is claimed to be optimal, which implies minimal chunks).1084if (cmp == 0) assert(chunking.size() >= simple_chunking.size());1086// Compare with a linearization read from the fuzz input.1087auto read = ReadLinearization(depgraph, reader);1088auto read_chunking = ChunkLinearization(depgraph, read);1089auto cmp_read = CompareChunks(chunking, read_chunking);1090assert(cmp_read >= 0);1092// Verify that within every chunk, the transactions are in a valid order. For any pair of1093// transactions, it should not be possible to swap them; either due to a missing1094// dependency, or because the order would be inconsistent with decreasing feerate,1095// increasing size, and fallback order (just DepGraphIndex value here).1096auto chunking_info = ChunkLinearizationInfo(depgraph, linearization);1097/** The set of all transactions (strictly) before tx1 (see below), or (strictly) before1098* chunk1 (see even further below). */1099TestBitSet done;1100unsigned pos{0};1101for (const auto& chunk : chunking_info) {1102auto chunk_start = pos;1103auto chunk_end = pos + chunk.transactions.Count() - 1;1104// Go over all pairs of transactions. done is the set of transactions seen before pos1.1105for (unsigned pos1 = chunk_start; pos1 <= chunk_end; ++pos1) {1106auto tx1 = linearization[pos1];1107for (unsigned pos2 = pos1 + 1; pos2 <= chunk_end; ++pos2) {1108auto tx2 = linearization[pos2];1109// Check whether tx2 only depends on transactions that precede tx1.1110if ((depgraph.Ancestors(tx2) - done).Count() == 1) {1111// tx2 could take position pos1.1112// Verify that individual transaction feerate is decreasing (tie-breaking by1113// size).1114assert(ByRatioNegSize{depgraph.FeeRate(tx1)} >= ByRatioNegSize{depgraph.FeeRate(tx2)});1115// If feerate and size are equal, compare by DepGraphIndex.1116if (depgraph.FeeRate(tx1) == depgraph.FeeRate(tx2)) {1117assert(tx1 < tx2);1118}1119}1120}1121done.Set(tx1);1122}1123pos += chunk.transactions.Count();1124}1126// Verify that chunks themselves are in a valid order. For any pair of chunks, it should1127// not be possible to swap them; either due to a missing dependency, or because the order1128// would be inconsistent with decreasing chunk feerate, increasing chunk size, and order1129// of maximum fallback-ordered element (just maximum DepGraphIndex element here).1130done = {};1131// Go over all pairs of chunks. done is the set of transactions seen before chunk_num1.1132for (unsigned chunk_num1 = 0; chunk_num1 < chunking_info.size(); ++chunk_num1) {1133const auto& chunk1 = chunking_info[chunk_num1];1134for (unsigned chunk_num2 = chunk_num1 + 1; chunk_num2 < chunking_info.size(); ++chunk_num2) {1135const auto& chunk2 = chunking_info[chunk_num2];1136TestBitSet chunk2_ancestors;1137for (auto tx : chunk2.transactions) chunk2_ancestors |= depgraph.Ancestors(tx);1138// Check whether chunk2 only depends on transactions that precede chunk1.1139if ((chunk2_ancestors - done).IsSubsetOf(chunk2.transactions)) {1140// chunk2 could take position chunk_num1.1141// Verify that chunk feerate is decreasing (tie-breaking by size).1142assert(ByRatioNegSize{chunk1.feerate} >= ByRatioNegSize{chunk2.feerate});1143// If feerate and size are equal, compare by maximum DepGraphIndex element.1144if (chunk1.feerate == chunk2.feerate) {1145assert(chunk1.transactions.Last() < chunk2.transactions.Last());1146}1147}1148}1149done |= chunk1.transactions;1150}1152// Redo from scratch with a different rng_seed. The resulting linearization should be1153// deterministic, if both are optimal.1154auto [linearization2, optimal2, cost2] = Linearize(depgraph, MaxOptimalLinearizationCost(depgraph.TxCount()) + 1, rng_seed ^ 0x1337, IndexTxOrder{});1155assert(optimal2);1156assert(linearization2 == linearization);1157}1158}1160FUZZ_TARGET(clusterlin_postlinearize)1161{1162// Verify expected properties of PostLinearize() on arbitrary linearizations.1164// Retrieve a depgraph from the fuzz input.1165SpanReader reader(buffer);1166DepGraph<TestBitSet> depgraph;1167try {1168reader >> Using<DepGraphFormatter>(depgraph);1169} catch (const std::ios_base::failure&) {}1171// Retrieve a linearization from the fuzz input.1172std::vector<DepGraphIndex> linearization;1173linearization = ReadLinearization(depgraph, reader);1174SanityCheck(depgraph, linearization);1176// Produce a post-processed version.1177auto post_linearization = linearization;1178PostLinearize(depgraph, post_linearization);1179SanityCheck(depgraph, post_linearization);1181// Compare diagrams: post-linearization cannot worsen anywhere.1182auto chunking = ChunkLinearization(depgraph, linearization);1183auto post_chunking = ChunkLinearization(depgraph, post_linearization);1184auto cmp = CompareChunks(post_chunking, chunking);1185assert(cmp >= 0);1187// Run again, things can keep improving (and never get worse)1188auto post_post_linearization = post_linearization;1189PostLinearize(depgraph, post_post_linearization);1190SanityCheck(depgraph, post_post_linearization);1191auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization);1192cmp = CompareChunks(post_post_chunking, post_chunking);1193assert(cmp >= 0);1195// The chunks that come out of postlinearizing are always connected.1196auto linchunking = ChunkLinearizationInfo(depgraph, post_linearization);1197for (const auto& [chunk_set, _chunk_feerate] : linchunking) {1198assert(depgraph.IsConnected(chunk_set));1199}1200}1202FUZZ_TARGET(clusterlin_postlinearize_tree)1203{1204// Verify expected properties of PostLinearize() on linearizations of graphs that form either1205// an upright or reverse tree structure.1207// Construct a direction, RNG seed, and an arbitrary graph from the fuzz input.1208SpanReader reader(buffer);1209uint64_t rng_seed{0};1210DepGraph<TestBitSet> depgraph_gen;1211uint8_t direction{0};1212try {1213reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen);1214} catch (const std::ios_base::failure&) {}1216auto depgraph_tree = BuildTreeGraph(depgraph_gen, direction);1218// Retrieve a linearization from the fuzz input.1219std::vector<DepGraphIndex> linearization;1220linearization = ReadLinearization(depgraph_tree, reader);1221SanityCheck(depgraph_tree, linearization);1223// Produce a postlinearized version.1224auto post_linearization = linearization;1225PostLinearize(depgraph_tree, post_linearization);1226SanityCheck(depgraph_tree, post_linearization);1228// Compare diagrams.1229auto chunking = ChunkLinearization(depgraph_tree, linearization);1230auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization);1231auto cmp = CompareChunks(post_chunking, chunking);1232assert(cmp >= 0);1234// Verify that post-linearizing again does not change the diagram. The result must be identical1235// as post_linearization ought to be optimal already with a tree-structured graph.1236auto post_post_linearization = post_linearization;1237PostLinearize(depgraph_tree, post_post_linearization);1238SanityCheck(depgraph_tree, post_post_linearization);1239auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization);1240auto cmp_post = CompareChunks(post_post_chunking, post_chunking);1241assert(cmp_post == 0);1243// Try to find an even better linearization directly. This must not change the diagram for the1244// same reason.1245auto [opt_linearization, _optimal, _cost] = Linearize(depgraph_tree, 1000000, rng_seed, IndexTxOrder{}, post_linearization);1246auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization);1247auto cmp_opt = CompareChunks(opt_chunking, post_chunking);1248assert(cmp_opt == 0);1249}
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.