coinselection.cpp raw
1 // Copyright (c) 2022 The Limenka 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 <policy/feerate.h>
6 #include <policy/policy.h>
7 #include <primitives/transaction.h>
8 #include <test/fuzz/FuzzedDataProvider.h>
9 #include <test/fuzz/fuzz.h>
10 #include <test/fuzz/util.h>
11 #include <test/util/setup_common.h>
12 #include <wallet/coinselection.h>
13
14 #include <numeric>
15 #include <vector>
16
17 namespace wallet {
18
19 static void AddCoin(const CAmount& value, int n_input, int n_input_bytes, int locktime, std::vector<COutput>& coins, CFeeRate fee_rate)
20 {
21 CMutableTransaction tx;
22 tx.vout.resize(n_input + 1);
23 tx.vout[n_input].nValue = value;
24 tx.nLockTime = locktime; // all transactions get different hashes
25 coins.emplace_back(COutPoint(tx.GetHash(), n_input), tx.vout.at(n_input), /*depth=*/0, n_input_bytes, /*spendable=*/true, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/true, fee_rate);
26 }
27
28 // Randomly distribute coins to instances of OutputGroup
29 static void GroupCoins(FuzzedDataProvider& fuzzed_data_provider, const std::vector<COutput>& coins, const CoinSelectionParams& coin_params, bool positive_only, std::vector<OutputGroup>& output_groups)
30 {
31 auto output_group = OutputGroup(coin_params);
32 bool valid_outputgroup{false};
33 for (auto& coin : coins) {
34 if (!positive_only || (positive_only && coin.GetEffectiveValue() > 0)) {
35 output_group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/0, /*descendants=*/0);
36 }
37 // If positive_only was specified, nothing was inserted, leading to an empty output group
38 // that would be invalid for the BnB algorithm
39 valid_outputgroup = !positive_only || output_group.GetSelectionAmount() > 0;
40 if (valid_outputgroup && fuzzed_data_provider.ConsumeBool()) {
41 output_groups.push_back(output_group);
42 output_group = OutputGroup(coin_params);
43 valid_outputgroup = false;
44 }
45 }
46 if (valid_outputgroup) output_groups.push_back(output_group);
47 }
48
49 static CAmount CreateCoins(FuzzedDataProvider& fuzzed_data_provider, std::vector<COutput>& utxo_pool, CoinSelectionParams& coin_params, int& next_locktime)
50 {
51 CAmount total_balance{0};
52 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
53 {
54 const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
55 const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)};
56 const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
57 if (total_balance + amount >= MAX_MONEY) {
58 break;
59 }
60 AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate);
61 total_balance += amount;
62 }
63
64 return total_balance;
65 }
66
67 static SelectionResult ManualSelection(std::vector<COutput>& utxos, const CAmount& total_amount, const bool& subtract_fee_outputs)
68 {
69 SelectionResult result(total_amount, SelectionAlgorithm::MANUAL);
70 std::set<std::shared_ptr<COutput>> utxo_pool;
71 for (const auto& utxo : utxos) {
72 utxo_pool.insert(std::make_shared<COutput>(utxo));
73 }
74 result.AddInputs(utxo_pool, subtract_fee_outputs);
75 return result;
76 }
77
78 // Returns true if the result contains an error and the message is not empty
79 static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
80
81 FUZZ_TARGET(coin_grinder)
82 {
83 FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
84 std::vector<COutput> utxo_pool;
85
86 const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
87
88 FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
89 CoinSelectionParams coin_params{fast_random_context};
90 coin_params.m_subtract_fee_outputs = fuzzed_data_provider.ConsumeBool();
91 coin_params.m_long_term_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
92 coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
93 coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
94 coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
95 coin_params.m_cost_of_change= coin_params.m_effective_feerate.GetFee(coin_params.change_output_size) + coin_params.m_long_term_feerate.GetFee(coin_params.change_spend_size);
96 coin_params.m_change_fee = coin_params.m_effective_feerate.GetFee(coin_params.change_output_size);
97 // For other results to be comparable to SRD, we must align the change_target with SRD’s hardcoded behavior
98 coin_params.m_min_change_target = CHANGE_LOWER + coin_params.m_change_fee;
99
100 // Create some coins
101 CAmount total_balance{0};
102 CAmount max_spendable{0};
103 int next_locktime{0};
104 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
105 {
106 const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
107 const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)};
108 const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
109 if (total_balance + amount >= MAX_MONEY) {
110 break;
111 }
112 AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate);
113 total_balance += amount;
114 CAmount eff_value = amount - coin_params.m_effective_feerate.GetFee(n_input_bytes);
115 max_spendable += eff_value;
116 }
117
118 std::vector<OutputGroup> group_pos;
119 GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
120
121 // Run coinselection algorithms
122 auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, MAX_STANDARD_TX_WEIGHT);
123 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 assert(result_cg);
125 if (!result_cg->GetAlgoCompleted()) return; // Bail out if CoinGrinder solution is not optimal
126
127 auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, MAX_STANDARD_TX_WEIGHT);
128 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 assert(result_srd->GetWeight() >= result_cg->GetWeight());
130 }
131
132 auto result_knapsack = KnapsackSolver(group_pos, target, coin_params.m_min_change_target, fast_random_context, MAX_STANDARD_TX_WEIGHT);
133 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 assert(result_knapsack->GetWeight() >= result_cg->GetWeight());
135 }
136 }
137
138 FUZZ_TARGET(coin_grinder_is_optimal)
139 {
140 FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
141
142 FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
143 CoinSelectionParams coin_params{fast_random_context};
144 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 coin_params.m_effective_feerate = CFeeRate{ConsumeMoney(fuzzed_data_provider, MAX_MONEY), 1'000'000};
147 coin_params.m_min_change_target = ConsumeMoney(fuzzed_data_provider);
148
149 // Create some coins
150 CAmount max_spendable{0};
151 int next_locktime{0};
152 static constexpr unsigned max_output_groups{16};
153 std::vector<OutputGroup> group_pos;
154 LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), max_output_groups)
155 {
156 // With maximum m_effective_feerate and n_input_bytes = 1'000'000, input_fee <= MAX_MONEY.
157 const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(1, 1'000'000)};
158 // Only make UTXOs with positive effective value
159 const CAmount input_fee = coin_params.m_effective_feerate.GetFee(n_input_bytes);
160 // Ensure that each UTXO has at least an effective value of 1 sat
161 const CAmount eff_value{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY + group_pos.size() - max_spendable - max_output_groups)};
162 const CAmount amount{eff_value + input_fee};
163 std::vector<COutput> temp_utxo_pool;
164
165 AddCoin(amount, /*n_input=*/0, n_input_bytes, ++next_locktime, temp_utxo_pool, coin_params.m_effective_feerate);
166 max_spendable += eff_value;
167
168 auto output_group = OutputGroup(coin_params);
169 output_group.Insert(std::make_shared<COutput>(temp_utxo_pool.at(0)), /*ancestors=*/0, /*descendants=*/0);
170 group_pos.push_back(output_group);
171 }
172 size_t num_groups = group_pos.size();
173 assert(num_groups <= max_output_groups);
174
175 // Only choose targets below max_spendable
176 const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, std::max(CAmount{1}, max_spendable - coin_params.m_min_change_target))};
177
178 // Brute force optimal solution
179 CAmount best_amount{MAX_MONEY};
180 int best_weight{std::numeric_limits<int>::max()};
181 for (uint32_t pattern = 1; (pattern >> num_groups) == 0; ++pattern) {
182 CAmount subset_amount{0};
183 int subset_weight{0};
184 for (unsigned i = 0; i < num_groups; ++i) {
185 if ((pattern >> i) & 1) {
186 subset_amount += group_pos[i].GetSelectionAmount();
187 subset_weight += group_pos[i].m_weight;
188 }
189 }
190 if ((subset_amount >= target + coin_params.m_min_change_target) && (subset_weight < best_weight || (subset_weight == best_weight && subset_amount < best_amount))) {
191 best_weight = subset_weight;
192 best_amount = subset_amount;
193 }
194 }
195
196 if (best_weight < std::numeric_limits<int>::max()) {
197 // Sufficient funds and acceptable weight: CoinGrinder should find at least one solution
198 int high_max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(best_weight, std::numeric_limits<int>::max());
199
200 auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, high_max_selection_weight);
201 assert(result_cg);
202 assert(result_cg->GetWeight() <= high_max_selection_weight);
203 assert(result_cg->GetSelectedEffectiveValue() >= target + coin_params.m_min_change_target);
204 assert(best_weight < result_cg->GetWeight() || (best_weight == result_cg->GetWeight() && best_amount <= result_cg->GetSelectedEffectiveValue()));
205 if (result_cg->GetAlgoCompleted()) {
206 // If CoinGrinder exhausted the search space, it must return the optimal solution
207 assert(best_weight == result_cg->GetWeight());
208 assert(best_amount == result_cg->GetSelectedEffectiveValue());
209 }
210 }
211
212 // CoinGrinder cannot ever find a better solution than the brute-forced best, or there is none in the first place
213 int low_max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, best_weight - 1);
214 auto result_cg = CoinGrinder(group_pos, target, coin_params.m_min_change_target, low_max_selection_weight);
215 // Max_weight should have been exceeded, or there were insufficient funds
216 assert(!result_cg);
217 }
218
219 FUZZ_TARGET(coinselection)
220 {
221 SeedRandomStateForTest(SeedRand::ZEROS);
222 FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
223 std::vector<COutput> utxo_pool;
224
225 const CFeeRate long_term_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
226 const CFeeRate effective_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
227 // Discard feerate must be at least dust relay feerate
228 const CFeeRate discard_fee_rate{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(DUST_RELAY_TX_FEE, COIN)};
229 const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
230 const bool subtract_fee_outputs{fuzzed_data_provider.ConsumeBool()};
231
232 FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
233 CoinSelectionParams coin_params{fast_random_context};
234 coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
235 coin_params.m_long_term_feerate = long_term_fee_rate;
236 coin_params.m_effective_feerate = effective_fee_rate;
237 coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange(1, MAX_SCRIPT_SIZE);
238 coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
239 coin_params.m_discard_feerate = discard_fee_rate;
240 coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
241 const auto change_spend_fee{coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size)};
242 coin_params.m_cost_of_change = coin_params.m_change_fee + change_spend_fee;
243 CScript change_out_script = CScript() << std::vector<unsigned char>(coin_params.change_output_size, OP_TRUE);
244 const auto dust{GetDustThreshold(CTxOut{/*nValueIn=*/0, change_out_script}, coin_params.m_discard_feerate)};
245 coin_params.min_viable_change = std::max(change_spend_fee + 1, dust);
246
247 int next_locktime{0};
248 CAmount total_balance{CreateCoins(fuzzed_data_provider, utxo_pool, coin_params, next_locktime)};
249
250 std::vector<OutputGroup> group_pos;
251 GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
252 std::vector<OutputGroup> group_all;
253 GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all);
254
255 for (const OutputGroup& group : group_all) {
256 const CoinEligibilityFilter filter{fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<uint64_t>()};
257 (void)group.EligibleForSpending(filter);
258 }
259
260 int max_selection_weight = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, std::numeric_limits<int>::max());
261
262 // Run coinselection algorithms
263 auto result_bnb = coin_params.m_subtract_fee_outputs ? util::Error{Untranslated("BnB disabled when SFFO is enabled")} :
264 SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, max_selection_weight);
265 if (result_bnb) {
266 assert(result_bnb->GetChange(coin_params.min_viable_change, coin_params.m_change_fee) == 0);
267 assert(result_bnb->GetSelectedValue() >= target);
268 assert(result_bnb->GetWeight() <= max_selection_weight);
269 (void)result_bnb->GetShuffledInputVector();
270 (void)result_bnb->GetInputSet();
271 }
272
273 auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, max_selection_weight);
274 if (result_srd) {
275 assert(result_srd->GetSelectedValue() >= target);
276 assert(result_srd->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0); // Demonstrate that SRD creates change of at least CHANGE_LOWER
277 assert(result_srd->GetWeight() <= max_selection_weight);
278 result_srd->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
279 (void)result_srd->GetShuffledInputVector();
280 (void)result_srd->GetInputSet();
281 }
282
283 CAmount change_target{GenerateChangeTarget(target, coin_params.m_change_fee, fast_random_context)};
284 auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context, max_selection_weight);
285 if (result_knapsack) {
286 assert(result_knapsack->GetSelectedValue() >= target);
287 assert(result_knapsack->GetWeight() <= max_selection_weight);
288 result_knapsack->RecalculateWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
289 (void)result_knapsack->GetShuffledInputVector();
290 (void)result_knapsack->GetInputSet();
291 }
292
293 // If the total balance is sufficient for the target and we are not using
294 // effective values, Knapsack should always find a solution (unless the selection exceeded the max tx weight).
295 if (total_balance >= target && subtract_fee_outputs && !HasErrorMsg(result_knapsack)) {
296 assert(result_knapsack);
297 }
298
299 std::vector<COutput> utxos;
300 std::vector<util::Result<SelectionResult>> results;
301 results.emplace_back(std::move(result_srd));
302 results.emplace_back(std::move(result_knapsack));
303 results.emplace_back(std::move(result_bnb));
304 CAmount new_total_balance{CreateCoins(fuzzed_data_provider, utxos, coin_params, next_locktime)};
305 if (new_total_balance > 0) {
306 std::set<std::shared_ptr<COutput>> new_utxo_pool;
307 for (const auto& utxo : utxos) {
308 new_utxo_pool.insert(std::make_shared<COutput>(utxo));
309 }
310 for (auto& result : results) {
311 if (!result) continue;
312 const auto weight{result->GetWeight()};
313 result->AddInputs(new_utxo_pool, subtract_fee_outputs);
314 assert(result->GetWeight() > weight);
315 }
316 }
317
318 std::vector<COutput> manual_inputs;
319 CAmount manual_balance{CreateCoins(fuzzed_data_provider, manual_inputs, coin_params, next_locktime)};
320 if (manual_balance == 0) return;
321 auto manual_selection{ManualSelection(manual_inputs, manual_balance, coin_params.m_subtract_fee_outputs)};
322 for (auto& result : results) {
323 if (!result) continue;
324 const CAmount old_target{result->GetTarget()};
325 const std::set<std::shared_ptr<COutput>> input_set{result->GetInputSet()};
326 const int old_weight{result->GetWeight()};
327 result->Merge(manual_selection);
328 assert(result->GetInputSet().size() == input_set.size() + manual_inputs.size());
329 assert(result->GetTarget() == old_target + manual_selection.GetTarget());
330 assert(result->GetWeight() == old_weight + manual_selection.GetWeight());
331 }
332 }
333
334 } // namespace wallet
335