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 <bench/bench.h>
6 #include <consensus/consensus.h>
7 #include <consensus/validation.h>
8 #include <net.h>
9 #include <policy/policy.h>
10 #include <primitives/block.h>
11 #include <primitives/transaction.h>
12 #include <node/txorphanage.h>
13 #include <random.h>
14 #include <test/util/transaction_utils.h>
15 #include <threadsafety.h>
16 #include <util/check.h>
17 18 #include <algorithm>
19 #include <cstddef>
20 #include <cstdint>
21 #include <memory>
22 #include <numeric>
23 #include <vector>
24 25 static constexpr node::TxOrphanage::Usage TINY_TX_WEIGHT{240};
26 static constexpr int64_t APPROX_WEIGHT_PER_INPUT{200};
27 28 // Creates a transaction with num_inputs inputs and 1 output, padded to target_weight. Use this function to maximize m_outpoint_to_orphan_it operations.
29 // If num_inputs is 0, we maximize the number of inputs.
30 static CTransactionRef MakeTransactionBulkedTo(unsigned int num_inputs, int64_t target_weight, FastRandomContext& det_rand)
31 {
32 CMutableTransaction tx;
33 assert(target_weight >= 40 + APPROX_WEIGHT_PER_INPUT);
34 if (!num_inputs) num_inputs = (target_weight - 40) / APPROX_WEIGHT_PER_INPUT;
35 for (unsigned int i = 0; i < num_inputs; ++i) {
36 tx.vin.emplace_back(Txid::FromUint256(det_rand.rand256()), 0);
37 }
38 assert(GetTransactionWeight(*MakeTransactionRef(tx)) <= target_weight);
39 40 tx.vout.resize(1);
41 42 // If necessary, pad the transaction to the target weight.
43 if (GetTransactionWeight(*MakeTransactionRef(tx)) < target_weight - 4) {
44 BulkTransaction(tx, target_weight);
45 }
46 return MakeTransactionRef(tx);
47 }
48 49 // Constructs a transaction using a subset of inputs[start_input : start_input + num_inputs] up to the weight_limit.
50 static CTransactionRef MakeTransactionSpendingUpTo(const std::vector<CTxIn>& inputs, unsigned int start_input, unsigned int num_inputs, int64_t weight_limit)
51 {
52 CMutableTransaction tx;
53 for (unsigned int i{start_input}; i < start_input + num_inputs; ++i) {
54 if (GetTransactionWeight(*MakeTransactionRef(tx)) + APPROX_WEIGHT_PER_INPUT >= weight_limit) break;
55 tx.vin.emplace_back(inputs.at(i % inputs.size()));
56 }
57 assert(tx.vin.size() > 0);
58 return MakeTransactionRef(tx);
59 }
60 static void OrphanageSinglePeerEviction(benchmark::Bench& bench)
61 {
62 FastRandomContext det_rand{true};
63 64 // Fill up announcements slots with tiny txns, followed by a single large one
65 unsigned int NUM_TINY_TRANSACTIONS((node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE));
66 67 // Construct transactions to submit to orphanage: 1-in-1-out tiny transactions
68 std::vector<CTransactionRef> tiny_txs;
69 tiny_txs.reserve(NUM_TINY_TRANSACTIONS);
70 for (unsigned int i{0}; i < NUM_TINY_TRANSACTIONS; ++i) {
71 tiny_txs.emplace_back(MakeTransactionBulkedTo(1, TINY_TX_WEIGHT, det_rand));
72 }
73 auto large_tx = MakeTransactionBulkedTo(1, MAX_STANDARD_TX_WEIGHT, det_rand);
74 assert(GetTransactionWeight(*large_tx) <= MAX_STANDARD_TX_WEIGHT);
75 76 const auto orphanage{node::MakeTxOrphanage(/*max_global_latency_score=*/node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE, /*reserved_peer_usage=*/node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER)};
77 78 // Populate the orphanage. To maximize the number of evictions, first fill up with tiny transactions, then add a huge one.
79 NodeId peer{0};
80 // Add tiny transactions until we are just about to hit the memory limit, up to the max number of announcements.
81 // We use the same tiny transactions for all peers to minimize their contribution to the usage limit.
82 int64_t total_weight_to_add{0};
83 for (unsigned int txindex{0}; txindex < NUM_TINY_TRANSACTIONS; ++txindex) {
84 const auto& tx{tiny_txs.at(txindex)};
85 86 total_weight_to_add += GetTransactionWeight(*tx);
87 if (total_weight_to_add > orphanage->MaxGlobalUsage()) break;
88 89 assert(orphanage->AddTx(tx, peer));
90 91 // Sanity check: we should always be exiting at the point of hitting the weight limit.
92 assert(txindex < NUM_TINY_TRANSACTIONS - 1);
93 }
94 95 // In the real world, we always trim after each new tx.
96 // If we need to trim already, that means the benchmark is not representative of what LimitOrphans may do in a single call.
97 assert(orphanage->TotalOrphanUsage() <= orphanage->MaxGlobalUsage());
98 assert(orphanage->TotalLatencyScore() <= orphanage->MaxGlobalLatencyScore());
99 assert(orphanage->TotalOrphanUsage() + TINY_TX_WEIGHT > orphanage->MaxGlobalUsage());
100 101 bench.epochs(1).epochIterations(1).run([&]() NO_THREAD_SAFETY_ANALYSIS {
102 // Lastly, add the large transaction.
103 const auto num_announcements_before_trim{orphanage->CountAnnouncements()};
104 assert(orphanage->AddTx(large_tx, peer));
105 106 // If there are multiple peers, note that they all have the same DoS score. We will evict only 1 item at a time for each new DoSiest peer.
107 const auto num_announcements_after_trim{orphanage->CountAnnouncements()};
108 const auto num_evicted{num_announcements_before_trim - num_announcements_after_trim};
109 110 // The number of evictions is the same regardless of the number of peers. In both cases, we can exceed the
111 // usage limit using 1 maximally-sized transaction.
112 assert(num_evicted == MAX_STANDARD_TX_WEIGHT / TINY_TX_WEIGHT);
113 });
114 }
115 static void OrphanageMultiPeerEviction(benchmark::Bench& bench)
116 {
117 // Best number is just below sqrt(DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE)
118 static constexpr unsigned int NUM_PEERS{39};
119 // All peers will have the same transactions. We want to be just under the weight limit, so divide the max usage limit by the number of unique transactions.
120 static constexpr node::TxOrphanage::Count NUM_UNIQUE_TXNS{node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE / NUM_PEERS};
121 static constexpr node::TxOrphanage::Usage TOTAL_USAGE_LIMIT{node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER * NUM_PEERS};
122 // Subtract 4 because BulkTransaction rounds up and we must avoid going over the weight limit early.
123 static constexpr node::TxOrphanage::Usage LARGE_TX_WEIGHT{TOTAL_USAGE_LIMIT / NUM_UNIQUE_TXNS - 4};
124 static_assert(LARGE_TX_WEIGHT >= TINY_TX_WEIGHT * 2, "Tx is too small, increase NUM_PEERS");
125 // The orphanage does not permit any transactions larger than 400'000, so this test will not work if the large tx is much larger.
126 static_assert(LARGE_TX_WEIGHT <= MAX_STANDARD_TX_WEIGHT, "Tx is too large, decrease NUM_PEERS");
127 128 FastRandomContext det_rand{true};
129 // Construct large transactions
130 std::vector<CTransactionRef> shared_txs;
131 shared_txs.reserve(NUM_UNIQUE_TXNS);
132 for (unsigned int i{0}; i < NUM_UNIQUE_TXNS; ++i) {
133 shared_txs.emplace_back(MakeTransactionBulkedTo(9, LARGE_TX_WEIGHT, det_rand));
134 }
135 std::vector<size_t> indexes;
136 indexes.resize(NUM_UNIQUE_TXNS);
137 std::iota(indexes.begin(), indexes.end(), 0);
138 139 const auto orphanage{node::MakeTxOrphanage(/*max_global_latency_score=*/node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE, /*reserved_peer_usage=*/node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER)};
140 // Every peer sends the same transactions, all from shared_txs.
141 // Each peer has 1 or 2 assigned transactions, which they must place as the last and second-to-last positions.
142 // The assignments ensure that every transaction is in some peer's last 2 transactions, and is thus remains in the orphanage until the end of LimitOrphans.
143 static_assert(NUM_UNIQUE_TXNS <= NUM_PEERS * 2);
144 145 // We need each peer to send some transactions so that the global limit (which is a function of the number of peers providing at least 1 announcement) rises.
146 for (unsigned int i{0}; i < NUM_UNIQUE_TXNS; ++i) {
147 for (NodeId peer{0}; peer < NUM_PEERS; ++peer) {
148 const CTransactionRef& reserved_last_tx{shared_txs.at(peer)};
149 CTransactionRef reserved_second_to_last_tx{peer < NUM_UNIQUE_TXNS - NUM_PEERS ? shared_txs.at(peer + NUM_PEERS) : nullptr};
150 151 const auto& tx{shared_txs.at(indexes.at(i))};
152 if (tx == reserved_last_tx) {
153 // Skip
154 } else if (reserved_second_to_last_tx && tx == reserved_second_to_last_tx) {
155 // Skip
156 } else {
157 orphanage->AddTx(tx, peer);
158 }
159 }
160 }
161 162 // Now add the final reserved transactions.
163 for (NodeId peer{0}; peer < NUM_PEERS; ++peer) {
164 const CTransactionRef& reserved_last_tx{shared_txs.at(peer)};
165 CTransactionRef reserved_second_to_last_tx{peer < NUM_UNIQUE_TXNS - NUM_PEERS ? shared_txs.at(peer + NUM_PEERS) : nullptr};
166 // Add the final reserved transactions.
167 if (reserved_second_to_last_tx) {
168 orphanage->AddTx(reserved_second_to_last_tx, peer);
169 }
170 orphanage->AddTx(reserved_last_tx, peer);
171 }
172 173 assert(orphanage->CountAnnouncements() == NUM_PEERS * NUM_UNIQUE_TXNS);
174 const auto total_usage{orphanage->TotalOrphanUsage()};
175 const auto max_usage{orphanage->MaxGlobalUsage()};
176 assert(max_usage - total_usage <= LARGE_TX_WEIGHT);
177 assert(orphanage->TotalLatencyScore() <= orphanage->MaxGlobalLatencyScore());
178 179 auto last_tx = MakeTransactionBulkedTo(0, max_usage - total_usage + 1, det_rand);
180 181 bench.epochs(1).epochIterations(1).run([&]() NO_THREAD_SAFETY_ANALYSIS {
182 const auto num_announcements_before_trim{orphanage->CountAnnouncements()};
183 // There is a small gap between the total usage and the max usage. Add a transaction to fill it.
184 assert(orphanage->AddTx(last_tx, 0));
185 186 // If there are multiple peers, note that they all have the same DoS score. We will evict only 1 item at a time for each new DoSiest peer.
187 const auto num_evicted{num_announcements_before_trim - orphanage->CountAnnouncements() + 1};
188 // The trimming happens as a round robin. In the first NUM_UNIQUE_TXNS - 2 rounds for each peer, only duplicates are evicted.
189 // Once each peer has 2 transactions left, it's possible to select a peer whose oldest transaction is unique.
190 assert(num_evicted >= (NUM_UNIQUE_TXNS - 2) * NUM_PEERS);
191 });
192 }
193 194 static void OrphanageEraseAll(benchmark::Bench& bench, bool block_or_disconnect)
195 {
196 FastRandomContext det_rand{true};
197 const auto orphanage{node::MakeTxOrphanage(/*max_global_latency_score=*/node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE, /*reserved_peer_usage=*/node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER)};
198 // This is an unrealistically large number of inputs for a block, as there is almost no room given to witness data,
199 // outputs, and overhead for individual transactions. The entire block is 1 transaction with 20,000 inputs.
200 constexpr unsigned int NUM_BLOCK_INPUTS{MAX_BLOCK_WEIGHT / APPROX_WEIGHT_PER_INPUT};
201 const auto block_tx{MakeTransactionBulkedTo(NUM_BLOCK_INPUTS, MAX_BLOCK_WEIGHT - 4000, det_rand)};
202 CBlock block;
203 block.vtx.push_back(block_tx);
204 205 // Transactions with 9 inputs maximize the computation / LatencyScore ratio.
206 constexpr unsigned int INPUTS_PER_TX{9};
207 constexpr unsigned int NUM_PEERS{125};
208 constexpr unsigned int NUM_TXNS_PER_PEER = node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE / NUM_PEERS;
209 210 // Divide the block's inputs evenly among the peers.
211 constexpr unsigned int INPUTS_PER_PEER = NUM_BLOCK_INPUTS / NUM_PEERS;
212 static_assert(INPUTS_PER_PEER > 0);
213 // All the block inputs are spent by the orphanage transactions. Each peer is assigned 76 of them.
214 // Each peer has 24 transactions spending 9 inputs each, so jumping by 3 ensures we cover all of the inputs.
215 static_assert(7 * NUM_TXNS_PER_PEER + INPUTS_PER_TX - 1 >= INPUTS_PER_PEER);
216 217 for (NodeId peer{0}; peer < NUM_PEERS; ++peer) {
218 int64_t weight_left_for_peer{node::DEFAULT_RESERVED_ORPHAN_WEIGHT_PER_PEER};
219 for (unsigned int txnum{0}; txnum < node::DEFAULT_MAX_ORPHANAGE_LATENCY_SCORE / NUM_PEERS; ++txnum) {
220 // Transactions must be unique since they use different (though overlapping) inputs.
221 const unsigned int start_input = peer * INPUTS_PER_PEER + txnum * 7;
222 223 // Note that we shouldn't be able to hit the weight limit with these small transactions.
224 const int64_t weight_limit{std::min<int64_t>(weight_left_for_peer, MAX_STANDARD_TX_WEIGHT)};
225 auto ptx = MakeTransactionSpendingUpTo(block_tx->vin, /*start_input=*/start_input, /*num_inputs=*/INPUTS_PER_TX, /*weight_limit=*/weight_limit);
226 227 assert(GetTransactionWeight(*ptx) <= MAX_STANDARD_TX_WEIGHT);
228 assert(!orphanage->HaveTx(ptx->GetWitnessHash()));
229 assert(orphanage->AddTx(ptx, peer));
230 231 weight_left_for_peer -= GetTransactionWeight(*ptx);
232 if (weight_left_for_peer < TINY_TX_WEIGHT * 2) break;
233 }
234 }
235 236 // If these fail, it means this benchmark is not realistic because the orphanage would have been trimmed already.
237 assert(orphanage->TotalLatencyScore() <= orphanage->MaxGlobalLatencyScore());
238 assert(orphanage->TotalOrphanUsage() <= orphanage->MaxGlobalUsage());
239 240 // 3000 announcements (and unique transactions) in the orphanage.
241 // They spend a total of 27,000 inputs (20,000 unique ones)
242 assert(orphanage->CountAnnouncements() == NUM_PEERS * NUM_TXNS_PER_PEER);
243 assert(orphanage->TotalLatencyScore() == orphanage->CountAnnouncements());
244 245 bench.epochs(1).epochIterations(1).run([&]() NO_THREAD_SAFETY_ANALYSIS {
246 if (block_or_disconnect) {
247 // Erase everything through EraseForBlock.
248 // Every tx conflicts with this block.
249 orphanage->EraseForBlock(block);
250 assert(orphanage->CountAnnouncements() == 0);
251 } else {
252 // Erase everything through EraseForPeer.
253 for (NodeId peer{0}; peer < NUM_PEERS; ++peer) {
254 orphanage->EraseForPeer(peer);
255 }
256 assert(orphanage->CountAnnouncements() == 0);
257 }
258 });
259 }
260 261 static void OrphanageEraseForBlock(benchmark::Bench& bench)
262 {
263 OrphanageEraseAll(bench, /*block_or_disconnect=*/true);
264 }
265 static void OrphanageEraseForPeer(benchmark::Bench& bench)
266 {
267 OrphanageEraseAll(bench, /*block_or_disconnect=*/false);
268 }
269 270 BENCHMARK(OrphanageSinglePeerEviction);
271 BENCHMARK(OrphanageMultiPeerEviction);
272 BENCHMARK(OrphanageEraseForBlock);
273 BENCHMARK(OrphanageEraseForPeer);
274