Inside Bitcoin

1// Copyright (c) The Bitcoin Core developers
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5#include <cluster_linearize.h>
6#include <test/util/cluster_linearize.h>
7#include <test/util/setup_common.h>
8#include <util/bitset.h>
9#include <util/strencodings.h>
10
11#include <vector>
12
13#include <boost/test/unit_test.hpp>
14
15BOOST_FIXTURE_TEST_SUITE(cluster_linearize_tests, BasicTestingSetup)
16
17using namespace cluster_linearize;
18using namespace util::hex_literals;
19
20namespace {
21
22/** Special magic value that indicates to TestDepGraphSerialization that a cluster entry represents
23 *  a hole. */
24constexpr std::pair<FeeFrac, TestBitSet> HOLE{FeeFrac{0, 0x3FFFFF}, {}};
25
26template<typename SetType>
27void TestDepGraphSerialization(const std::vector<std::pair<FeeFrac, SetType>>& cluster, const std::string& hexenc)
28{
29    // Construct DepGraph from cluster argument.
30    DepGraph<SetType> depgraph;
31    SetType holes;
32    for (DepGraphIndex i = 0; i < cluster.size(); ++i) {
33        depgraph.AddTransaction(cluster[i].first);
34        if (cluster[i] == HOLE) holes.Set(i);
35    }
36    for (DepGraphIndex i = 0; i < cluster.size(); ++i) {
37        depgraph.AddDependencies(cluster[i].second, i);
38    }
39    depgraph.RemoveTransactions(holes);
40    SanityCheck(depgraph);
41
42    // There may be multiple serializations of the same graph, but DepGraphFormatter's serializer
43    // only produces one of those. Verify that hexenc matches that canonical serialization.
44    std::vector<unsigned char> encoding;
45    VectorWriter writer(encoding, 0);
46    writer << Using<DepGraphFormatter>(depgraph);
47    BOOST_CHECK_EQUAL(HexStr(encoding), hexenc);
48
49    // Test that deserializing that encoding yields depgraph. This is effectively already implied
50    // by the round-trip test above (if depgraph is acyclic), but verify it explicitly again here.
51    SpanReader reader(encoding);
52    DepGraph<SetType> depgraph_read;
53    reader >> Using<DepGraphFormatter>(depgraph_read);
54    BOOST_CHECK(depgraph == depgraph_read);
55}
56
57void TestOptimalLinearization(std::span<const uint8_t> enc, std::initializer_list<DepGraphIndex> optimal_linearization)
58{
59    DepGraphIndex tx_count = 0;
60    FastRandomContext rng;
61
62    auto test_fn = [&]<typename SetType>() {
63        DepGraph<SetType> depgraph;
64        SpanReader reader(enc);
65        reader >> Using<DepGraphFormatter>(depgraph);
66        SanityCheck(depgraph);
67        std::vector<DepGraphIndex> lin;
68        for (int iter = 0; iter < 200; ++iter) {
69            bool opt;
70            uint64_t cost{0};
71            bool is_topological{true};
72            switch (rng.randrange(4)) {
73            case 0:
74                // Use empty input linearization.
75                lin.clear();
76                break;
77            case 1:
78                // Reuse previous optimal linearization as input.
79                break;
80            case 2:
81                // Construct random valid input linearization.
82                std::shuffle(lin.begin(), lin.end(), rng);
83                std::sort(lin.begin(), lin.end(), [&](auto a, auto b) { return depgraph.Ancestors(a).Count() < depgraph.Ancestors(b).Count(); });
84                break;
85            case 3:
86                // Construct random potentially invalid input linearization.
87                std::shuffle(lin.begin(), lin.end(), rng);
88                is_topological = false;
89                break;
90            }
91            std::tie(lin, opt, cost) = Linearize(
92                /*depgraph=*/depgraph,
93                /*max_cost=*/1000000000000,
94                /*rng_seed=*/rng.rand64(),
95                /*fallback_order=*/IndexTxOrder{},
96                /*old_linearization=*/lin,
97                /*is_topological=*/is_topological);
98            BOOST_CHECK(opt);
99            BOOST_CHECK(cost <= MaxOptimalLinearizationCost(depgraph.TxCount()));
100            SanityCheck(depgraph, lin);
101            BOOST_CHECK(std::ranges::equal(lin, optimal_linearization));
102        }
103        tx_count = depgraph.PositionRange();
104    };
105
106    // Always run with 64-bit set types
107    // - The native one that will be used on this platform.
108    test_fn.template operator()<BitSet<64>>();
109    // - The one used on 32-bit platforms.
110    test_fn.template operator()<bitset_detail::MultiIntBitSet<uint32_t, 2>>();
111    // - An 8-bit one, which is maximally different in terms of bitset behavior.
112    test_fn.template operator()<bitset_detail::MultiIntBitSet<uint8_t, 8>>();
113
114    // Also run with 32-bit set types if the cluster doesn't use indexes above 31.
115    if (tx_count <= 32) {
116        // - The native one that will be used on this platform.
117        test_fn.template operator()<BitSet<32>>();
118        // - An 8-bit one, which is maximally different in terms of bitset behavior.
119        test_fn.template operator()<bitset_detail::MultiIntBitSet<uint8_t, 4>>();
120    }
121}
122
123} // namespace
124
125BOOST_AUTO_TEST_CASE(depgraph_ser_tests)
126{
127    // Empty cluster.
128    TestDepGraphSerialization<TestBitSet>(
129        {},
130        "00" /* end of graph */);
131
132    // Transactions: A(fee=0,size=1).
133    TestDepGraphSerialization<TestBitSet>(
134        {{{0, 1}, {}}},
135        "01" /* A size */
136        "00" /* A fee */
137        "00" /* A insertion position (no skips): A */
138        "00" /* end of graph */);
139
140    // Transactions: A(fee=42,size=11), B(fee=-13,size=7), B depends on A.
141    TestDepGraphSerialization<TestBitSet>(
142        {{{42, 11}, {}}, {{-13, 7}, {0}}},
143        "0b" /* A size */
144        "54" /* A fee */
145        "00" /* A insertion position (no skips): A */
146        "07" /* B size */
147        "19" /* B fee */
148        "00" /* B->A dependency (no skips) */
149        "00" /* B insertion position (no skips): A,B */
150        "00" /* end of graph */);
151
152    // Transactions: A(64,128), B(128,256), C(1,1), C depends on A and B.
153    TestDepGraphSerialization<TestBitSet>(
154        {{{64, 128}, {}}, {{128, 256}, {}}, {{1, 1}, {0, 1}}},
155        "8000" /* A size */
156        "8000" /* A fee */
157        "00"   /* A insertion position (no skips): A */
158        "8100" /* B size */
159        "8100" /* B fee */
160        "01"   /* B insertion position (skip B->A dependency): A,B */
161        "01"   /* C size */
162        "02"   /* C fee */
163        "00"   /* C->B dependency (no skips) */
164        "00"   /* C->A dependency (no skips) */
165        "00"   /* C insertion position (no skips): A,B,C */
166        "00"   /* end of graph */);
167
168    // Transactions: A(-57,113), B(57,114), C(-58,115), D(58,116). Deps: B->A, C->A, D->C, in order
169    // [B,A,C,D]. This exercises non-topological ordering (internally serialized as A,B,C,D).
170    TestDepGraphSerialization<TestBitSet>(
171        {{{57, 114}, {1}}, {{-57, 113}, {}}, {{-58, 115}, {1}}, {{58, 116}, {2}}},
172        "71" /* A size */
173        "71" /* A fee */
174        "00" /* A insertion position (no skips): A */
175        "72" /* B size */
176        "72" /* B fee */
177        "00" /* B->A dependency (no skips) */
178        "01" /* B insertion position (skip A): B,A */
179        "73" /* C size */
180        "73" /* C fee */
181        "01" /* C->A dependency (skip C->B dependency) */
182        "00" /* C insertion position (no skips): B,A,C */
183        "74" /* D size */
184        "74" /* D fee */
185        "00" /* D->C dependency (no skips) */
186        "01" /* D insertion position (skip D->B dependency, D->A is implied): B,A,C,D */
187        "00" /* end of graph */);
188
189    // Transactions: A(1,2), B(3,1), C(2,1), D(1,3), E(1,1). Deps: C->A, D->A, D->B, E->D.
190    // In order: [D,A,B,E,C]. Internally serialized in order A,B,C,D,E.
191    TestDepGraphSerialization<TestBitSet>(
192        {{{1, 3}, {1, 2}}, {{1, 2}, {}}, {{3, 1}, {}}, {{1, 1}, {0}}, {{2, 1}, {1}}},
193        "02" /* A size */
194        "02" /* A fee */
195        "00" /* A insertion position (no skips): A */
196        "01" /* B size */
197        "06" /* B fee */
198        "01" /* B insertion position (skip B->A dependency): A,B */
199        "01" /* C size */
200        "04" /* C fee */
201        "01" /* C->A dependency (skip C->B dependency) */
202        "00" /* C insertion position (no skips): A,B,C */
203        "03" /* D size */
204        "02" /* D fee */
205        "01" /* D->B dependency (skip D->C dependency) */
206        "00" /* D->A dependency (no skips) */
207        "03" /* D insertion position (skip C,B,A): D,A,B,C */
208        "01" /* E size */
209        "02" /* E fee */
210        "00" /* E->D dependency (no skips) */
211        "02" /* E insertion position (skip E->C dependency, E->B and E->A are implied,
212                skip insertion C): D,A,B,E,C */
213        "00" /* end of graph */
214    );
215
216    // Transactions: A(1,2), B(3,1), C(2,1), D(1,3), E(1,1). Deps: C->A, D->A, D->B, E->D.
217    // In order: [_, D, _, _, A, _, B, _, _, _, E, _, _, C] (_ being holes). Internally serialized
218    // in order A,B,C,D,E.
219    TestDepGraphSerialization<TestBitSet>(
220        {HOLE, {{1, 3}, {4, 6}}, HOLE, HOLE, {{1, 2}, {}}, HOLE, {{3, 1}, {}}, HOLE, HOLE, HOLE, {{1, 1}, {1}}, HOLE, HOLE, {{2, 1}, {4}}},
221        "02" /* A size */
222        "02" /* A fee */
223        "03" /* A insertion position (3 holes): _, _, _, A */
224        "01" /* B size */
225        "06" /* B fee */
226        "06" /* B insertion position (skip B->A dependency, skip 4 inserts, add 1 hole): _, _, _, A, _, B */
227        "01" /* C size */
228        "04" /* C fee */
229        "01" /* C->A dependency (skip C->B dependency) */
230        "0b" /* C insertion position (skip 6 inserts, add 5 holes): _, _, _, A, _, B, _, _, _, _, _, C */
231        "03" /* D size */
232        "02" /* D fee */
233        "01" /* D->B dependency (skip D->C dependency) */
234        "00" /* D->A dependency (no skips) */
235        "0b" /* D insertion position (skip 11 inserts): _, D, _, _, A, _, B, _, _, _, _, _, C */
236        "01" /* E size */
237        "02" /* E fee */
238        "00" /* E->D dependency (no skips) */
239        "04" /* E insertion position (skip E->C dependency, E->B and E->A are implied, skip 3
240                inserts): _, D, _, _, A, _, B, _, _, _, E, _, _, C */
241        "00" /* end of graph */
242    );
243}
244
245BOOST_AUTO_TEST_CASE(depgraph_optimal_tests)
246{
247    // Compare linearizations with known-optimal chunk feerate diagrams.
248
249    // Hard clusters (according to various metrics) that appeared in replayed 2023 mempool data, ranging from 2 to 64 transactions.
250    TestOptimalLinearization("9276fa3a009c3b80cd4001a21680d85c02927bfa5403934280845404a04c80cf0805c75b82c22206a46880f532079c7e80b85608965780916a09a04a80cf080a9823809b3e0bb27b81ec0c0c8540c60e0c0c993e80c86a0d0b8540c2020c0c9352809f780c09972f80f84a080c85449900080c875da164080c875081ae54070c8335af4c071f9c6781a72a13010f99108190160e000e85419f2c07168332903c05158540819e54041216ba5183907a140000001182428d080024a25c83c11201040400010609b6668487240004060000000000"_hex_u8, {3, 0, 1, 2, 4, 28, 29, 5, 16, 10, 12, 22, 24, 9, 14, 11, 13, 17, 19, 18, 27, 6, 7, 8, 20, 30, 21, 15, 25, 23, 26});