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