Branch data Line data Source code
1 : : // Copyright (c) 2022-present 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 <wallet/coinselection.h>
6 : :
7 : : #include <policy/feerate.h>
8 : : #include <policy/policy.h>
9 : : #include <primitives/transaction.h>
10 : : #include <test/fuzz/FuzzedDataProvider.h>
11 : : #include <test/fuzz/fuzz.h>
12 : : #include <test/fuzz/util.h>
13 : : #include <test/util/setup_common.h>
14 : : #include <util/check.h>
15 : :
16 : : #include <numeric>
17 : : #include <span>
18 : : #include <vector>
19 : :
20 : : namespace wallet {
21 : :
22 : 1784791 : static void AddCoin(const CAmount& value, int n_input, int n_input_bytes, int locktime, std::vector<COutput>& coins, CFeeRate fee_rate)
23 : : {
24 : 1784791 : CMutableTransaction tx;
25 [ + - ]: 1784791 : tx.vout.resize(n_input + 1);
26 [ + - ]: 1784791 : tx.vout[n_input].nValue = value;
27 : 1784791 : tx.nLockTime = locktime; // all transactions get different hashes
28 [ + - + - : 1784791 : coins.emplace_back(COutPoint(tx.GetHash(), n_input), tx.vout.at(n_input), /*depth=*/0, n_input_bytes, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/true, fee_rate);
+ - ]
29 : 1784791 : }
30 : :
31 : : // Randomly distribute coins to instances of OutputGroup
32 : 2426 : static void GroupCoins(FuzzedDataProvider& fuzzed_data_provider, const std::vector<COutput>& coins, const CoinSelectionParams& coin_params, bool positive_only, std::vector<OutputGroup>& output_groups)
33 : : {
34 : 2426 : auto output_group = OutputGroup(coin_params);
35 : 2426 : bool valid_outputgroup{false};
36 [ + + ]: 1850735 : for (auto& coin : coins) {
37 [ + + + + ]: 1848309 : if (!positive_only || (positive_only && coin.GetEffectiveValue() > 0)) {
38 [ + - + - ]: 3482912 : output_group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/0, /*cluster_count=*/0);
39 : : }
40 : : // If positive_only was specified, nothing was inserted, leading to an empty output group
41 : : // that would be invalid for the BnB algorithm
42 [ + + + - : 1848309 : valid_outputgroup = !positive_only || output_group.GetSelectionAmount() > 0;
+ + ]
43 [ + + ]: 1744444 : if (valid_outputgroup && fuzzed_data_provider.ConsumeBool()) {
44 [ + - ]: 917227 : output_groups.push_back(output_group);
45 : 917227 : output_group = OutputGroup(coin_params);
46 : 917227 : valid_outputgroup = false;
47 : : }
48 : : }
49 [ + + + - ]: 2426 : if (valid_outputgroup) output_groups.push_back(output_group);
50 : 2426 : }
51 : :
52 : 3756 : static CAmount CreateCoins(FuzzedDataProvider& fuzzed_data_provider, std::vector<COutput>& utxo_pool, CoinSelectionParams& coin_params, int& next_locktime)
53 : : {
54 : 3756 : CAmount total_balance{0};
55 [ + + + + ]: 1364340 : LIMITED_WHILE (fuzzed_data_provider.ConsumeBool(), 10000) {
56 : 1361153 : const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
57 : 1361153 : const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)};
58 : 1361153 : const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
59 [ + + ]: 1361153 : if (total_balance + amount >= MAX_MONEY) {
60 : : break;
61 : : }
62 : 1360584 : AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate);
63 : 1360584 : total_balance += amount;
64 : : }
65 : :
66 : 3756 : return total_balance;
67 : : }
68 : :
69 : 312 : static SelectionResult ManualSelection(std::vector<COutput>& utxos, const CAmount& total_amount, const bool& subtract_fee_outputs)
70 : : {
71 : 312 : SelectionResult result(total_amount, SelectionAlgorithm::MANUAL);
72 : 312 : OutputSet utxo_pool;
73 [ + + ]: 161648 : for (const auto& utxo : utxos) {
74 [ + - + - ]: 322672 : utxo_pool.insert(std::make_shared<COutput>(utxo));
75 : : }
76 [ + - ]: 312 : result.AddInputs(utxo_pool, subtract_fee_outputs);
77 : 312 : return result;
78 : 312 : }
79 : :
80 : : // Returns true if the result contains an error and the message is not empty
81 : 880 : static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
82 : :
83 [ + - ]: 1157 : FUZZ_TARGET(coin_grinder)
84 : : {
85 : 681 : FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
86 : 681 : std::vector<COutput> utxo_pool;
87 : :
88 : 681 : const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
89 : :
90 : 681 : FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
91 : 681 : CoinSelectionParams coin_params{fast_random_context};
92 : 681 : coin_params.m_subtract_fee_outputs = fuzzed_data_provider.ConsumeBool();
93 : 681 : coin_params.m_long_term_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
94 : 681 : coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
95 : 681 : coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
96 : 681 : coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
97 [ + - ]: 681 : coin_params.m_change_fee = coin_params.m_effective_feerate.GetFee(coin_params.change_output_size);
98 : : // For other results to be comparable to SRD, we must align the change_target with SRD’s hardcoded behavior
99 : 681 : coin_params.m_min_change_target = CHANGE_LOWER + coin_params.m_change_fee;
100 : :
101 : : // Create some coins
102 : 681 : CAmount total_balance{0};
103 : 681 : CAmount max_spendable{0};
104 : 681 : int next_locktime{0};
105 [ + + + + ]: 420808 : LIMITED_WHILE (fuzzed_data_provider.ConsumeBool(), 10000) {
106 : 420400 : const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
107 : 420400 : const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)};
108 : 420400 : const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
109 [ + + ]: 420400 : if (total_balance + amount >= MAX_MONEY) {
110 : : break;
111 : : }
112 [ + - ]: 420127 : AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate);
113 : 420127 : total_balance += amount;
114 [ + - ]: 420127 : CAmount eff_value = amount - coin_params.m_effective_feerate.GetFee(n_input_bytes);
115 : 420127 : max_spendable += eff_value;
116 : : }
117 : :
118 : 681 : std::vector<OutputGroup> group_pos;
119 [ + - ]: 681 : GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
120 : :
121 : : // Run coinselection algorithms
122 [ + - ]: 681 : auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, MAX_STANDARD_TX_WEIGHT);
123 [ + + + - : 681 : if (target + coin_params.m_min_change_target > max_spendable || HasErrorMsg(result_cg)) return; // We only need to compare algorithms if CoinGrinder has a solution
+ + ]
124 [ - + ]: 629 : assert(result_cg);
125 [ + - + + ]: 629 : if (!result_cg->GetAlgoCompleted()) return; // Bail out if CoinGrinder solution is not optimal
126 : :
127 [ + - ]: 619 : auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, MAX_STANDARD_TX_WEIGHT);
128 [ + + + - : 1215 : if (result_srd && result_srd->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0) { // exclude any srd solutions that don’t have change, err on excluding
+ - ]
129 [ - + ]: 596 : assert(result_srd->GetWeight() >= result_cg->GetWeight());
130 : : }
131 : :
132 [ + - ]: 619 : auto result_knapsack = KnapsackSolver(group_pos, target, coin_params.m_min_change_target, fast_random_context, MAX_STANDARD_TX_WEIGHT);
133 [ + + + - : 1226 : if (result_knapsack && result_knapsack->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0) { // exclude any knapsack solutions that don’t have change, err on excluding
+ + ]
134 [ - + ]: 564 : assert(result_knapsack->GetWeight() >= result_cg->GetWeight());
135 : : }
136 : 681 : }
137 : :
138 [ + - ]: 707 : FUZZ_TARGET(coin_grinder_is_optimal)
139 : : {
140 : 231 : FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
141 : :
142 : 231 : FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
143 : 231 : CoinSelectionParams coin_params{fast_random_context};
144 : 231 : coin_params.m_subtract_fee_outputs = false;
145 : : // Set effective feerate up to MAX_MONEY sats per 1'000'000 vB (2'100'000'000 sat/vB = 21'000 BTC/kvB).
146 [ + - ]: 231 : coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, MAX_MONEY), 1'000'000};
147 : 231 : coin_params.m_min_change_target = ConsumeMoney(fuzzed_data_provider);
148 : :
149 : : // Create some coins
150 : 231 : CAmount max_spendable{0};
151 : 231 : int next_locktime{0};
152 : 231 : static constexpr unsigned max_output_groups{16};
153 : 231 : std::vector<OutputGroup> group_pos;
154 [ + + + + ]: 2490 : LIMITED_WHILE (fuzzed_data_provider.ConsumeBool(), max_output_groups) {
155 : : // With maximum m_effective_feerate and n_input_bytes = 1'000'000, input_fee <= MAX_MONEY.
156 : 2259 : const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(1, 1'000'000)};
157 : : // Only make UTXOs with positive effective value
158 [ + - ]: 2259 : const CAmount input_fee = coin_params.m_effective_feerate.GetFee(n_input_bytes);
159 : : // Ensure that each UTXO has at least an effective value of 1 sat
160 [ - + ]: 2259 : const CAmount eff_value{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY + group_pos.size() - max_spendable - max_output_groups)};
161 : 2259 : const CAmount amount{eff_value + input_fee};
162 : 2259 : std::vector<COutput> temp_utxo_pool;
163 : :
164 [ + - ]: 2259 : AddCoin(amount, /*n_input=*/0, n_input_bytes, ++next_locktime, temp_utxo_pool, coin_params.m_effective_feerate);
165 : 2259 : max_spendable += eff_value;
166 : :
167 [ + - ]: 2259 : auto output_group = OutputGroup(coin_params);
168 [ + - + - : 2259 : output_group.Insert(std::make_shared<COutput>(temp_utxo_pool.at(0)), /*ancestors=*/0, /*cluster_count=*/0);
+ - ]
169 [ + - ]: 2259 : group_pos.push_back(output_group);
170 : 2259 : }
171 [ - + ]: 231 : size_t num_groups = group_pos.size();
172 [ - + ]: 231 : assert(num_groups <= max_output_groups);
173 : :
174 : : // Only choose targets below max_spendable
175 [ + + ]: 280 : const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, std::max(CAmount{1}, max_spendable - coin_params.m_min_change_target))};
176 : :
177 : : // Brute force optimal solution
178 : 231 : CAmount best_amount{MAX_MONEY};
179 : 231 : int best_weight{std::numeric_limits<int>::max()};
180 [ + + ]: 5631457 : for (uint32_t pattern = 1; (pattern >> num_groups) == 0; ++pattern) {
181 : : CAmount subset_amount{0};
182 : : int subset_weight{0};
183 [ + + ]: 94856281 : for (unsigned i = 0; i < num_groups; ++i) {
184 [ + + ]: 89225055 : if ((pattern >> i) & 1) {
185 [ + - ]: 44613657 : subset_amount += group_pos[i].GetSelectionAmount();
186 : 44613657 : subset_weight += group_pos[i].m_weight;
187 : : }
188 : : }
189 [ + + + + : 5631226 : if ((subset_amount >= target + coin_params.m_min_change_target) && (subset_weight < best_weight || (subset_weight == best_weight && subset_amount < best_amount))) {
+ + ]
190 : 1343 : best_weight = subset_weight;
191 : 1343 : best_amount = subset_amount;
192 : : }
193 : : }
194 : :
195 [ + + ]: 231 : if (best_weight < std::numeric_limits<int>::max()) {
196 : : // Sufficient funds and acceptable weight: CoinGrinder should find at least one solution
197 : 193 : int high_max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(best_weight, std::numeric_limits<int>::max());
198 : :
199 [ + - ]: 193 : auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, high_max_selection_weight);
200 [ - + ]: 193 : assert(result_cg);
201 [ - + ]: 193 : assert(result_cg->GetWeight() <= high_max_selection_weight);
202 [ + - - + ]: 193 : assert(result_cg->GetSelectedEffectiveValue() >= target + coin_params.m_min_change_target);
203 [ + - + - : 193 : assert(best_weight < result_cg->GetWeight() || (best_weight == result_cg->GetWeight() && best_amount <= result_cg->GetSelectedEffectiveValue()));
+ - - + ]
204 [ + - + - ]: 193 : if (result_cg->GetAlgoCompleted()) {
205 : : // If CoinGrinder exhausted the search space, it must return the optimal solution
206 [ - + ]: 193 : assert(best_weight == result_cg->GetWeight());
207 [ + - - + ]: 193 : assert(best_amount == result_cg->GetSelectedEffectiveValue());
208 : : }
209 : 193 : }
210 : :
211 : : // CoinGrinder cannot ever find a better solution than the brute-forced best, or there is none in the first place
212 : 231 : int low_max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, best_weight - 1);
213 [ + - ]: 231 : auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, low_max_selection_weight);
214 : : // Max_weight should have been exceeded, or there were insufficient funds
215 [ - + ]: 231 : assert(!result_cg);
216 : 231 : }
217 : :
218 [ + - ]: 680 : FUZZ_TARGET(bnb_finds_min_waste)
219 : : {
220 : 204 : FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
221 : :
222 : 204 : FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
223 : 204 : CoinSelectionParams coin_params{fast_random_context};
224 : 204 : coin_params.m_subtract_fee_outputs = false;
225 : : // Set effective feerate up to 10'000'000 sats per kvB (10'000 sat/vB).
226 [ + - ]: 204 : coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, 10'000'000), 1'000};
227 [ + - ]: 204 : coin_params.m_long_term_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, 10'000'000), 1'000};
228 [ + - ]: 204 : coin_params.m_discard_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, 10'000'000), 1'000};
229 : 204 : coin_params.m_cost_of_change = ConsumeMoney(fuzzed_data_provider);
230 : :
231 : 204 : coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);
232 [ + - ]: 204 : coin_params.m_change_fee = coin_params.m_effective_feerate.GetFee(coin_params.change_output_size);
233 : 204 : coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
234 [ + - ]: 204 : const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
235 : 204 : coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
236 [ + - ]: 408 : CScript change_out_script = CScript() << std::vector<unsigned char>(coin_params.change_output_size, OP_TRUE);
237 [ + - + - ]: 204 : const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
238 [ + + ]: 204 : coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);
239 : :
240 : : // Create some coins
241 : 204 : CAmount max_spendable{0};
242 : 204 : int next_locktime{0};
243 : : // Too many output groups (>17?) would make it possible to generate UTXO
244 : : // pool and target combinations that cannot be completely searched by BnB
245 : : // before running into the attempt limit (see BnB "Exhaust..." test). The
246 : : // brute force search also gets exponentially more expensive with bigger
247 : : // UTXO pools.
248 : : // Choose 1–16 of 16 provides ample fuzzing space.
249 : 204 : static constexpr unsigned max_output_groups{16};
250 : 204 : std::vector<OutputGroup> group_pos;
251 [ + + + + ]: 2025 : LIMITED_WHILE (fuzzed_data_provider.ConsumeBool(), max_output_groups) {
252 : : // With maximum m_effective_feerate 10'000 s/vB and n_input_bytes = 20'000 B, input_fee <= MAX_MONEY.
253 : 1821 : const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(1, 20'000)};
254 [ + - ]: 1821 : const CAmount input_fee = coin_params.m_effective_feerate.GetFee(n_input_bytes);
255 : : // Ensure that each UTXO has at least an effective value of 1 sat
256 [ - + ]: 1821 : const CAmount eff_value{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY + group_pos.size() - max_spendable - max_output_groups)};
257 : 1821 : const CAmount amount{eff_value + input_fee};
258 : 1821 : std::vector<COutput> temp_utxo_pool;
259 : :
260 [ + - ]: 1821 : AddCoin(amount, /*n_input=*/0, n_input_bytes, ++next_locktime, temp_utxo_pool, coin_params.m_effective_feerate);
261 : 1821 : max_spendable += eff_value;
262 : :
263 [ + - ]: 1821 : auto output_group = OutputGroup(coin_params);
264 [ + - + - : 1821 : output_group.Insert(std::make_shared<COutput>(temp_utxo_pool.at(0)), /*ancestors=*/0, /*cluster_count=*/0);
+ - ]
265 [ + - ]: 1821 : group_pos.push_back(output_group);
266 : 1821 : }
267 [ - + ]: 204 : size_t num_groups = group_pos.size();
268 [ - + ]: 204 : assert(num_groups <= max_output_groups);
269 : :
270 : : // Only choose targets below max_spendable
271 [ + + ]: 237 : const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, std::max(CAmount{1}, max_spendable - coin_params.m_cost_of_change))};
272 : :
273 : : // Brute force optimal solution (lowest waste, but cannot be superset of another solution)
274 : 204 : std::vector<uint32_t> solutions;
275 : 204 : CAmount best_waste{std::numeric_limits<int64_t>::max()};
276 : 204 : int best_weight{std::numeric_limits<int>::max()};
277 [ + + ]: 3905302 : for (uint32_t pattern = 1; (pattern >> num_groups) == 0; ++pattern) {
278 : : // BnB does not permit adding more inputs to a solution, i.e. a superset of a solution cannot ever be a solution.
279 : : // The search pattern guarantees that any superset will only be visited after all its subsets have been traversed.
280 : 3905098 : bool is_superset = false;
281 [ + + ]: 277837448 : for (uint32_t sol : solutions) {
282 [ + + ]: 275624799 : if ((pattern & sol) == sol) {
283 : : is_superset = true;
284 : : break;
285 : : }
286 : : }
287 [ + + ]: 3905098 : if (is_superset) {
288 : 1692449 : continue;
289 : : }
290 : :
291 : : CAmount subset_amount{0};
292 : : CAmount subset_waste{0};
293 : : int subset_weight{0};
294 [ + + ]: 37215177 : for (unsigned i = 0; i < num_groups; ++i) {
295 [ + + ]: 35002528 : if ((pattern >> i) & 1) {
296 [ + - ]: 16541488 : subset_amount += group_pos[i].GetSelectionAmount();
297 : 16541488 : subset_waste += group_pos[i].fee - group_pos[i].long_term_fee;
298 : 16541488 : subset_weight += group_pos[i].m_weight;
299 : : }
300 : : }
301 [ + + + + ]: 2212649 : if (subset_amount >= target && subset_amount <= target + coin_params.m_cost_of_change) {
302 [ + - ]: 15138 : solutions.push_back(pattern);
303 : : // Add the excess (overselection that gets dropped to fees) to waste score
304 : 15138 : CAmount excess = subset_amount - target;
305 : 15138 : subset_waste += excess;
306 : 15138 : SelectionResult result_bf(target, SelectionAlgorithm::MANUAL);
307 : :
308 [ + + ]: 246721 : for (unsigned i = 0; i < num_groups; ++i) {
309 [ + + ]: 231583 : if ((pattern >> i) & 1) {
310 [ + - ]: 104881 : result_bf.AddInput(group_pos[i]);
311 : : }
312 : : }
313 [ + + ]: 15138 : if (subset_waste < best_waste) {
314 : 1205 : best_waste = subset_waste;
315 [ + - ]: 1205 : result_bf.RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
316 [ + - - + ]: 1205 : assert(result_bf.GetWaste() == best_waste);
317 : : best_weight = subset_weight;
318 : : }
319 : 15138 : }
320 : : }
321 : :
322 : 204 : int high_max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(best_weight, std::numeric_limits<int>::max());
323 [ + - ]: 204 : auto result_bnb = SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, high_max_selection_weight);
324 : :
325 [ - + + + : 204 : if (!solutions.size() || !result_bnb) {
+ - ]
326 : : // Either both BnB and Brute Force find a solution or neither does.
327 [ - + ]: 49 : assert(!result_bnb == !solutions.size());
328 : : } else {
329 : : // If brute forcing found a solution with an acceptable weight, BnB must find at least one solution with at most 16 output groups
330 : 155 : assert(result_bnb);
331 [ + - ]: 155 : result_bnb->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
332 [ - + ]: 155 : assert(result_bnb->GetWeight() <= high_max_selection_weight);
333 [ + - - + ]: 155 : assert(result_bnb->GetSelectedEffectiveValue() >= target);
334 [ + - - + ]: 155 : assert(result_bnb->GetSelectedEffectiveValue() <= target + coin_params.m_cost_of_change);
335 [ + - - + ]: 155 : assert(best_waste <= result_bnb->GetWaste());
336 [ + - + - ]: 155 : if (result_bnb->GetAlgoCompleted()) {
337 : : // If BnB exhausted the search space, it must return an optimal solution (tied on waste score)
338 [ + - - + ]: 155 : assert(best_waste == result_bnb->GetWaste());
339 : : }
340 : : }
341 : 204 : }
342 : :
343 : : enum class CoinSelectionAlgorithm {
344 : : BNB,
345 : : SRD,
346 : : KNAPSACK,
347 : : };
348 : :
349 : : template<CoinSelectionAlgorithm Algorithm>
350 : 1252 : void FuzzCoinSelectionAlgorithm(std::span<const uint8_t> buffer) {
351 : 1252 : SeedRandomStateForTest(SeedRand::ZEROS);
352 : 1252 : FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
353 : 1252 : std::vector<COutput> utxo_pool;
354 : :
355 : 1252 : const CFeeRate long_term_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
356 : 1252 : const CFeeRate effective_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
357 : : // Discard feerate must be at least dust relay feerate
358 : 1252 : const CFeeRate discard_fee_rate{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(DUST_RELAY_TX_FEE, COIN)};
359 : 1252 : const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
360 : 1252 : const bool subtract_fee_outputs{fuzzed_data_provider.ConsumeBool()};
361 : :
362 : 1252 : FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
363 : 1252 : CoinSelectionParams coin_params{fast_random_context};
364 : 1252 : coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
365 : 1252 : coin_params.m_long_term_feerate = long_term_fee_rate;
366 : 1252 : coin_params.m_effective_feerate = effective_fee_rate;
367 : 1252 : coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);
368 [ + - ][ + - ]: 1252 : coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
[ + - ]
369 : 1252 : coin_params.m_discard_feerate = discard_fee_rate;
370 : 1252 : coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
371 [ + - ][ + - ]: 1252 : const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
[ + - ]
372 : 1252 : coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
373 [ + - ][ + - ]: 2504 : CScript change_out_script = CScript() << std::vector<unsigned char>(coin_params.change_output_size, OP_TRUE);
[ + - ]
374 [ + - + - ]: 1252 : const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
[ + - + - ]
[ + - + - ]
375 [ + + ]: 1252 : coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);
376 : :
377 : 1252 : int next_locktime{0};
378 [ + - ][ + - ]: 1252 : CAmount total_balance{CreateCoins(fuzzed_data_provider, utxo_pool, coin_params, next_locktime)};
[ + - ]
379 : :
380 : 1252 : std::vector<OutputGroup> group_pos;
381 [ + - ][ + - ]: 1252 : GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
[ + - ]
382 : :
383 : 1252 : int max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, std::numeric_limits<int>::max());
384 : :
385 : 1252 : std::optional<SelectionResult> result;
386 : :
387 : : if constexpr (Algorithm == CoinSelectionAlgorithm::BNB) {
388 [ + + ]: 408 : if (!coin_params.m_subtract_fee_outputs) {
389 [ + - ]: 364 : auto result_bnb = SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, max_selection_weight);
390 [ + + ]: 364 : if (result_bnb) {
391 [ + - ]: 187 : result = *result_bnb;
392 [ + - - + ]: 187 : assert(result_bnb->GetChange(coin_params.min_viable_change, coin_params.m_change_fee) == 0);
393 [ + - - + ]: 187 : assert(result_bnb->GetSelectedValue() >= target);
394 [ - + ]: 187 : assert(result_bnb->GetWeight() <= max_selection_weight);
395 [ + - ]: 187 : (void)result_bnb->GetShuffledInputVector();
396 [ + - ]: 187 : (void)result_bnb->GetInputSet();
397 : : }
398 : 364 : }
399 : : }
400 : :
401 : : if constexpr (Algorithm == CoinSelectionAlgorithm::SRD) {
402 [ + - ]: 351 : auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, max_selection_weight);
403 [ + + ]: 351 : if (result_srd) {
404 [ + - ]: 179 : result = *result_srd;
405 [ + - - + ]: 179 : assert(result_srd->GetSelectedValue() >= target);
406 [ + - - + ]: 179 : assert(result_srd->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0);
407 [ - + ]: 179 : assert(result_srd->GetWeight() <= max_selection_weight);
408 [ + - ]: 179 : result_srd->SetBumpFeeDiscount(ConsumeMoney(fuzzed_data_provider));
409 [ + - ]: 179 : result_srd->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
410 [ + - ]: 179 : (void)result_srd->GetShuffledInputVector();
411 [ + - ]: 179 : (void)result_srd->GetInputSet();
412 : : }
413 : 0 : }
414 : :
415 : : if constexpr (Algorithm == CoinSelectionAlgorithm::KNAPSACK) {
416 : 493 : std::vector<OutputGroup> group_all;
417 [ + - ]: 493 : GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all);
418 : :
419 [ + + ]: 214067 : for (const OutputGroup& group : group_all) {
420 [ + - ]: 213574 : const CoinEligibilityFilter filter{fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<uint64_t>()};
421 [ + - ]: 213574 : (void)group.EligibleForSpending(filter);
422 : : }
423 : :
424 [ + - ]: 493 : CAmount change_target{GenerateChangeTarget(target, coin_params.m_change_fee, fast_random_context)};
425 [ + - ]: 493 : auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context, max_selection_weight);
426 : : // If the total balance is sufficient for the target and we are not using
427 : : // effective values, Knapsack should always find a solution (unless the selection exceeded the max tx weight).
428 [ + + + + : 493 : if (total_balance >= target && subtract_fee_outputs && !HasErrorMsg(result_knapsack)) {
+ - + + ]
429 [ - + ]: 218 : assert(result_knapsack);
430 : : }
431 [ + + ]: 493 : if (result_knapsack) {
432 [ + - ]: 392 : result = *result_knapsack;
433 [ + - - + ]: 392 : assert(result_knapsack->GetSelectedValue() >= target);
434 [ - + ]: 392 : assert(result_knapsack->GetWeight() <= max_selection_weight);
435 [ + - ]: 392 : result_knapsack->SetBumpFeeDiscount(ConsumeMoney(fuzzed_data_provider));
436 [ + - ]: 392 : result_knapsack->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
437 [ + - ]: 392 : (void)result_knapsack->GetShuffledInputVector();
438 [ + - ]: 392 : (void)result_knapsack->GetInputSet();
439 : : }
440 : 493 : }
441 : :
442 : 1252 : std::vector<COutput> utxos;
443 [ + - ][ + - ]: 1252 : CAmount new_total_balance{CreateCoins(fuzzed_data_provider, utxos, coin_params, next_locktime)};
[ + - ]
444 [ + + ][ + + ]: 1252 : if (new_total_balance > 0) {
[ + + ]
445 : 407 : OutputSet new_utxo_pool;
446 [ + - + + ]: 183763 : for (const auto& utxo : utxos) {
[ + - + + ]
[ + - + + ]
447 [ + - ][ + - ]: 366712 : new_utxo_pool.insert(std::make_shared<COutput>(utxo));
[ + - ]
448 : : }
449 [ + + ][ + + ]: 407 : if (result) {
[ + + ]
450 [ + - ][ + - ]: 289 : const auto weight{result->GetWeight()};
[ + - ]
451 [ + - ][ + - ]: 289 : result->AddInputs(new_utxo_pool, subtract_fee_outputs);
[ + - ]
452 [ - + ][ - + ]: 289 : assert(result->GetWeight() > weight);
[ - + ]
453 : : }
454 : 407 : }
455 : :
456 : 1252 : std::vector<COutput> manual_inputs;
457 [ + - ][ + - ]: 1252 : CAmount manual_balance{CreateCoins(fuzzed_data_provider, manual_inputs, coin_params, next_locktime)};
[ + - ]
458 [ + + ][ + + ]: 1252 : if (manual_balance == 0) return;
[ + + ]
459 [ + - ][ + - ]: 312 : auto manual_selection{ManualSelection(manual_inputs, manual_balance, coin_params.m_subtract_fee_outputs)};
[ + - ]
460 [ + + ][ + + ]: 312 : if (result) {
[ + + ]
461 [ + - ][ + - ]: 225 : const CAmount old_target{result->GetTarget()};
[ + - ]
462 [ + - + - : 225 : const OutputSet input_set{result->GetInputSet()};
+ - ][ + -
+ - + - ]
[ + - + -
+ - ]
463 [ + - ][ + - ]: 225 : const int old_weight{result->GetWeight()};
[ + - ]
464 [ + - ][ + - ]: 225 : result->Merge(manual_selection);
[ + - ]
465 [ + - - + : 225 : assert(result->GetInputSet().size() == input_set.size() + manual_inputs.size());
- + ][ + -
- + - + ]
[ + - - +
- + ]
466 [ - + ][ - + ]: 225 : assert(result->GetTarget() == old_target + manual_selection.GetTarget());
[ - + ]
467 [ - + ][ - + ]: 225 : assert(result->GetWeight() == old_weight + manual_selection.GetWeight());
[ - + ]
468 : 225 : }
469 : 1252 : }
470 : :
471 [ + - ]: 884 : FUZZ_TARGET(coinselection_bnb) {
472 : 408 : FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::BNB>(buffer);
473 : 408 : }
474 : :
475 [ + - ]: 827 : FUZZ_TARGET(coinselection_srd) {
476 : 351 : FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::SRD>(buffer);
477 : 351 : }
478 : :
479 [ + - ]: 969 : FUZZ_TARGET(coinselection_knapsack) {
480 : 493 : FuzzCoinSelectionAlgorithm<CoinSelectionAlgorithm::KNAPSACK>(buffer);
481 : 493 : }
482 : :
483 : : } // namespace wallet
|