diff options
author | glozow <gloriajzhao@gmail.com> | 2024-08-05 09:34:44 +0100 |
---|---|---|
committer | glozow <gloriajzhao@gmail.com> | 2024-08-05 09:42:22 +0100 |
commit | bba01ba18d07f5bc7bf195319dc1229a88c4c220 (patch) | |
tree | d7f1e6d84c3fce72d061ba77b8e8e5d01615a878 /src/test/fuzz | |
parent | 1a7d20509f46f0cd38302da78dba9a0c9bb24226 (diff) | |
parent | bbcee5a0d67db46526ba29a1a4a7c590d303de03 (diff) |
Merge bitcoin/bitcoin#30285: cluster mempool: merging & postprocessing of linearizations
bbcee5a0d67db46526ba29a1a4a7c590d303de03 clusterlin: improve rechunking in LinearizationChunking (optimization) (Pieter Wuille)
04d7a04ea426dd0a69b61e3b887867b0277d84d1 clusterlin: add MergeLinearizations function + fuzz test + benchmark (Pieter Wuille)
4f8958d7563ae2d0d359ec1e6885f8cb5e40a5e0 clusterlin: add PostLinearize + benchmarks + fuzz tests (Pieter Wuille)
0e2812d2938b933debffba5b873637fa1d348b81 clusterlin: add algorithms for connectedness/connected components (Pieter Wuille)
0e52728a2d6ccafcfecfefbb5a0432a9881d8e0d clusterlin: rename Intersect -> IntersectPrefixes (Pieter Wuille)
Pull request description:
Part of cluster mempool: #30289
Depends on #30126, and was split off from it. #28676 depends on this.
This adds the algorithms for merging & postprocessing linearizations.
The `PostLinearize(depgraph, linearization)` function performs an in-place improvement of `linearization`, using two iterations of the [Linearization post-processing](https://delvingbitcoin.org/t/linearization-post-processing-o-n-2-fancy-chunking/201/8) algorithm. The first running from back to front, the second from front to back.
The `MergeLinearizations(depgraph, linearization1, linearization2)` function computes a new linearization for the provided cluster, given two existing linearizations for that cluster, which is at least as good as both inputs. The algorithm is described at a high level in [merging incomparable linearizations](https://delvingbitcoin.org/t/merging-incomparable-linearizations/209).
For background and references, see [Introduction to cluster linearization](https://delvingbitcoin.org/t/introduction-to-cluster-linearization/1032).
ACKs for top commit:
sdaftuar:
ACK bbcee5a0d67db46526ba29a1a4a7c590d303de03
glozow:
code review ACK bbcee5a0d67
instagibbs:
ACK https://github.com/bitcoin/bitcoin/pull/30285/commits/bbcee5a0d67db46526ba29a1a4a7c590d303de03
Tree-SHA512: d2b5a3f132d1ef22ddf9c56421ab8b397efe45b3c4c705548dda56f5b39fe4b8f57a0d2a4c65b338462d80bb5b9b84a9a39efa1b4f390420a8005ce31817774e
Diffstat (limited to 'src/test/fuzz')
-rw-r--r-- | src/test/fuzz/cluster_linearize.cpp | 274 |
1 files changed, 271 insertions, 3 deletions
diff --git a/src/test/fuzz/cluster_linearize.cpp b/src/test/fuzz/cluster_linearize.cpp index 031cb04559..2dfdfbb41d 100644 --- a/src/test/fuzz/cluster_linearize.cpp +++ b/src/test/fuzz/cluster_linearize.cpp @@ -294,6 +294,81 @@ FUZZ_TARGET(clusterlin_depgraph_serialization) assert(IsAcyclic(depgraph)); } +FUZZ_TARGET(clusterlin_components) +{ + // Verify the behavior of DepGraphs's FindConnectedComponent and IsConnected functions. + + // Construct a depgraph. + SpanReader reader(buffer); + DepGraph<TestBitSet> depgraph; + try { + reader >> Using<DepGraphFormatter>(depgraph); + } catch (const std::ios_base::failure&) {} + + TestBitSet todo = TestBitSet::Fill(depgraph.TxCount()); + while (todo.Any()) { + // Find a connected component inside todo. + auto component = depgraph.FindConnectedComponent(todo); + + // The component must be a subset of todo and non-empty. + assert(component.IsSubsetOf(todo)); + assert(component.Any()); + + // If todo is the entire graph, and the entire graph is connected, then the component must + // be the entire graph. + if (todo == TestBitSet::Fill(depgraph.TxCount())) { + assert((component == todo) == depgraph.IsConnected()); + } + + // If subset is connected, then component must match subset. + assert((component == todo) == depgraph.IsConnected(todo)); + + // The component cannot have any ancestors or descendants outside of component but in todo. + for (auto i : component) { + assert((depgraph.Ancestors(i) & todo).IsSubsetOf(component)); + assert((depgraph.Descendants(i) & todo).IsSubsetOf(component)); + } + + // Starting from any component element, we must be able to reach every element. + for (auto i : component) { + // Start with just i as reachable. + TestBitSet reachable = TestBitSet::Singleton(i); + // Add in-todo descendants and ancestors to reachable until it does not change anymore. + while (true) { + TestBitSet new_reachable = reachable; + for (auto j : new_reachable) { + new_reachable |= depgraph.Ancestors(j) & todo; + new_reachable |= depgraph.Descendants(j) & todo; + } + if (new_reachable == reachable) break; + reachable = new_reachable; + } + // Verify that the result is the entire component. + assert(component == reachable); + } + + // Construct an arbitrary subset of todo. + uint64_t subset_bits{0}; + try { + reader >> VARINT(subset_bits); + } catch (const std::ios_base::failure&) {} + TestBitSet subset; + for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) { + if (todo[i]) { + if (subset_bits & 1) subset.Set(i); + subset_bits >>= 1; + } + } + // Which must be non-empty. + if (subset.None()) subset = TestBitSet::Singleton(todo.First()); + // Remove it from todo. + todo -= subset; + } + + // No components can be found in an empty subset. + assert(depgraph.FindConnectedComponent(todo).None()); +} + FUZZ_TARGET(clusterlin_chunking) { // Verify the correctness of the ChunkLinearization function. @@ -357,6 +432,7 @@ FUZZ_TARGET(clusterlin_ancestor_finder) assert(best_anc.transactions.Any()); assert(best_anc.transactions.IsSubsetOf(todo)); assert(depgraph.FeeRate(best_anc.transactions) == best_anc.feerate); + assert(depgraph.IsConnected(best_anc.transactions)); // Check that it is topologically valid. for (auto i : best_anc.transactions) { assert((depgraph.Ancestors(i) & todo).IsSubsetOf(best_anc.transactions)); @@ -443,6 +519,9 @@ FUZZ_TARGET(clusterlin_search_finder) // Perform quality checks only if SearchCandidateFinder claims an optimal result. if (iterations_done < max_iterations) { + // Optimal sets are always connected. + assert(depgraph.IsConnected(found.transactions)); + // Compare with SimpleCandidateFinder. auto [simple, simple_iters] = smp_finder.FindCandidateSet(MAX_SIMPLE_ITERATIONS); assert(found.feerate >= simple.feerate); @@ -560,10 +639,10 @@ FUZZ_TARGET(clusterlin_linearization_chunking) } assert(combined == todo); - // Verify the expected properties of LinearizationChunking::Intersect: - auto intersect = chunking.Intersect(subset); + // Verify the expected properties of LinearizationChunking::IntersectPrefixes: + auto intersect = chunking.IntersectPrefixes(subset); // - Intersecting again doesn't change the result. - assert(chunking.Intersect(intersect) == intersect); + assert(chunking.IntersectPrefixes(intersect) == intersect); // - The intersection is topological. TestBitSet intersect_anc; for (auto idx : intersect.transactions) { @@ -687,3 +766,192 @@ FUZZ_TARGET(clusterlin_linearize) } } } + +FUZZ_TARGET(clusterlin_postlinearize) +{ + // Verify expected properties of PostLinearize() on arbitrary linearizations. + + // Retrieve a depgraph from the fuzz input. + SpanReader reader(buffer); + DepGraph<TestBitSet> depgraph; + try { + reader >> Using<DepGraphFormatter>(depgraph); + } catch (const std::ios_base::failure&) {} + + // Retrieve a linearization from the fuzz input. + std::vector<ClusterIndex> linearization; + linearization = ReadLinearization(depgraph, reader); + SanityCheck(depgraph, linearization); + + // Produce a post-processed version. + auto post_linearization = linearization; + PostLinearize(depgraph, post_linearization); + SanityCheck(depgraph, post_linearization); + + // Compare diagrams: post-linearization cannot worsen anywhere. + auto chunking = ChunkLinearization(depgraph, linearization); + auto post_chunking = ChunkLinearization(depgraph, post_linearization); + auto cmp = CompareChunks(post_chunking, chunking); + assert(cmp >= 0); + + // Run again, things can keep improving (and never get worse) + auto post_post_linearization = post_linearization; + PostLinearize(depgraph, post_post_linearization); + SanityCheck(depgraph, post_post_linearization); + auto post_post_chunking = ChunkLinearization(depgraph, post_post_linearization); + cmp = CompareChunks(post_post_chunking, post_chunking); + assert(cmp >= 0); + + // The chunks that come out of postlinearizing are always connected. + LinearizationChunking linchunking(depgraph, post_linearization); + while (linchunking.NumChunksLeft()) { + assert(depgraph.IsConnected(linchunking.GetChunk(0).transactions)); + linchunking.MarkDone(linchunking.GetChunk(0).transactions); + } +} + +FUZZ_TARGET(clusterlin_postlinearize_tree) +{ + // Verify expected properties of PostLinearize() on linearizations of graphs that form either + // an upright or reverse tree structure. + + // Construct a direction, RNG seed, and an arbitrary graph from the fuzz input. + SpanReader reader(buffer); + uint64_t rng_seed{0}; + DepGraph<TestBitSet> depgraph_gen; + uint8_t direction{0}; + try { + reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen); + } catch (const std::ios_base::failure&) {} + + // Now construct a new graph, copying the nodes, but leaving only the first parent (even + // direction) or the first child (odd direction). + DepGraph<TestBitSet> depgraph_tree; + for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) { + depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i)); + } + if (direction & 1) { + for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) { + auto children = depgraph_gen.Descendants(i) - TestBitSet::Singleton(i); + // Remove descendants that are children of other descendants. + for (auto j : children) { + if (!children[j]) continue; + children -= depgraph_gen.Descendants(j); + children.Set(j); + } + if (children.Any()) depgraph_tree.AddDependency(i, children.First()); + } + } else { + for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) { + auto parents = depgraph_gen.Ancestors(i) - TestBitSet::Singleton(i); + // Remove ancestors that are parents of other ancestors. + for (auto j : parents) { + if (!parents[j]) continue; + parents -= depgraph_gen.Ancestors(j); + parents.Set(j); + } + if (parents.Any()) depgraph_tree.AddDependency(parents.First(), i); + } + } + + // Retrieve a linearization from the fuzz input. + std::vector<ClusterIndex> linearization; + linearization = ReadLinearization(depgraph_tree, reader); + SanityCheck(depgraph_tree, linearization); + + // Produce a postlinearized version. + auto post_linearization = linearization; + PostLinearize(depgraph_tree, post_linearization); + SanityCheck(depgraph_tree, post_linearization); + + // Compare diagrams. + auto chunking = ChunkLinearization(depgraph_tree, linearization); + auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization); + auto cmp = CompareChunks(post_chunking, chunking); + assert(cmp >= 0); + + // Verify that post-linearizing again does not change the diagram. The result must be identical + // as post_linearization ought to be optimal already with a tree-structured graph. + auto post_post_linearization = post_linearization; + PostLinearize(depgraph_tree, post_linearization); + SanityCheck(depgraph_tree, post_linearization); + auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization); + auto cmp_post = CompareChunks(post_post_chunking, post_chunking); + assert(cmp_post == 0); + + // Try to find an even better linearization directly. This must not change the diagram for the + // same reason. + auto [opt_linearization, _optimal] = Linearize(depgraph_tree, 100000, rng_seed, post_linearization); + auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization); + auto cmp_opt = CompareChunks(opt_chunking, post_chunking); + assert(cmp_opt == 0); +} + +FUZZ_TARGET(clusterlin_postlinearize_moved_leaf) +{ + // Verify that taking an existing linearization, and moving a leaf to the back, potentially + // increasing its fee, and then post-linearizing, results in something as good as the + // original. This guarantees that in an RBF that replaces a transaction with one of the same + // size but higher fee, applying the "remove conflicts, append new transaction, postlinearize" + // process will never worsen linearization quality. + + // Construct an arbitrary graph and a fee from the fuzz input. + SpanReader reader(buffer); + DepGraph<TestBitSet> depgraph; + int32_t fee_inc{0}; + try { + uint64_t fee_inc_code; + reader >> Using<DepGraphFormatter>(depgraph) >> VARINT(fee_inc_code); + fee_inc = fee_inc_code & 0x3ffff; + } catch (const std::ios_base::failure&) {} + if (depgraph.TxCount() == 0) return; + + // Retrieve two linearizations from the fuzz input. + auto lin = ReadLinearization(depgraph, reader); + auto lin_leaf = ReadLinearization(depgraph, reader); + + // Construct a linearization identical to lin, but with the tail end of lin_leaf moved to the + // back. + std::vector<ClusterIndex> lin_moved; + for (auto i : lin) { + if (i != lin_leaf.back()) lin_moved.push_back(i); + } + lin_moved.push_back(lin_leaf.back()); + + // Postlinearize lin_moved. + PostLinearize(depgraph, lin_moved); + SanityCheck(depgraph, lin_moved); + + // Compare diagrams (applying the fee delta after computing the old one). + auto old_chunking = ChunkLinearization(depgraph, lin); + depgraph.FeeRate(lin_leaf.back()).fee += fee_inc; + auto new_chunking = ChunkLinearization(depgraph, lin_moved); + auto cmp = CompareChunks(new_chunking, old_chunking); + assert(cmp >= 0); +} + +FUZZ_TARGET(clusterlin_merge) +{ + // Construct an arbitrary graph from the fuzz input. + SpanReader reader(buffer); + DepGraph<TestBitSet> depgraph; + try { + reader >> Using<DepGraphFormatter>(depgraph); + } catch (const std::ios_base::failure&) {} + + // Retrieve two linearizations from the fuzz input. + auto lin1 = ReadLinearization(depgraph, reader); + auto lin2 = ReadLinearization(depgraph, reader); + + // Merge the two. + auto lin_merged = MergeLinearizations(depgraph, lin1, lin2); + + // Compute chunkings and compare. + auto chunking1 = ChunkLinearization(depgraph, lin1); + auto chunking2 = ChunkLinearization(depgraph, lin2); + auto chunking_merged = ChunkLinearization(depgraph, lin_merged); + auto cmp1 = CompareChunks(chunking_merged, chunking1); + assert(cmp1 >= 0); + auto cmp2 = CompareChunks(chunking_merged, chunking2); + assert(cmp2 >= 0); +} |