aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/bench/coin_selection.cpp15
-rw-r--r--src/wallet/coinselection.cpp107
-rw-r--r--src/wallet/coinselection.h47
-rw-r--r--src/wallet/spend.cpp143
-rw-r--r--src/wallet/spend.h41
-rw-r--r--src/wallet/test/coinselector_tests.cpp390
6 files changed, 433 insertions, 310 deletions
diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp
index 3c24fee60f..f97bf8028a 100644
--- a/src/bench/coin_selection.cpp
+++ b/src/bench/coin_selection.cpp
@@ -54,12 +54,10 @@ static void CoinSelection(benchmark::Bench& bench)
/* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0),
/* tx_noinputs_size= */ 0, /* avoid_partial= */ false);
bench.run([&] {
- std::set<CInputCoin> setCoinsRet;
- CAmount nValueRet;
- bool success = AttemptSelection(wallet, 1003 * COIN, filter_standard, coins, setCoinsRet, nValueRet, coin_selection_params);
- assert(success);
- assert(nValueRet == 1003 * COIN);
- assert(setCoinsRet.size() == 2);
+ auto result = AttemptSelection(wallet, 1003 * COIN, filter_standard, coins, coin_selection_params);
+ assert(result);
+ assert(result->GetSelectedValue() == 1003 * COIN);
+ assert(result->GetInputSet().size() == 2);
});
}
@@ -92,17 +90,14 @@ static void BnBExhaustion(benchmark::Bench& bench)
{
// Setup
std::vector<OutputGroup> utxo_pool;
- CoinSet selection;
- CAmount value_ret = 0;
bench.run([&] {
// Benchmark
CAmount target = make_hard_case(17, utxo_pool);
- SelectCoinsBnB(utxo_pool, target, 0, selection, value_ret); // Should exhaust
+ SelectCoinsBnB(utxo_pool, target, 0); // Should exhaust
// Cleanup
utxo_pool.clear();
- selection.clear();
});
}
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index c0ca931364..ddf6a8b829 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -56,17 +56,14 @@ struct {
* bound of the range.
* @param const CAmount& cost_of_change This is the cost of creating and spending a change output.
* This plus selection_target is the upper bound of the range.
- * @param std::set<CInputCoin>& out_set -> This is an output parameter for the set of CInputCoins
- * that have been selected.
- * @param CAmount& value_ret -> This is an output parameter for the total value of the CInputCoins
- * that were selected.
+ * @returns The result of this coin selection algorithm, or std::nullopt
*/
static const size_t TOTAL_TRIES = 100000;
-bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret)
+std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change)
{
- out_set.clear();
+ SelectionResult result(selection_target);
CAmount curr_value = 0;
std::vector<bool> curr_selection; // select the utxo at this index
@@ -80,7 +77,7 @@ bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selectio
curr_available_value += utxo.GetSelectionAmount();
}
if (curr_available_value < selection_target) {
- return false;
+ return std::nullopt;
}
// Sort the utxo_pool
@@ -156,25 +153,22 @@ bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selectio
// Check for solution
if (best_selection.empty()) {
- return false;
+ return std::nullopt;
}
// Set output set
- value_ret = 0;
for (size_t i = 0; i < best_selection.size(); ++i) {
if (best_selection.at(i)) {
- util::insert(out_set, utxo_pool.at(i).m_outputs);
- value_ret += utxo_pool.at(i).m_value;
+ result.AddInput(utxo_pool.at(i));
}
}
- return true;
+ return result;
}
-std::optional<std::pair<std::set<CInputCoin>, CAmount>> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value)
+std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value)
{
- std::set<CInputCoin> out_set;
- CAmount value_ret = 0;
+ SelectionResult result(target_value);
std::vector<size_t> indexes;
indexes.resize(utxo_pool.size());
@@ -186,10 +180,9 @@ std::optional<std::pair<std::set<CInputCoin>, CAmount>> SelectCoinsSRD(const std
const OutputGroup& group = utxo_pool.at(i);
Assume(group.GetSelectionAmount() > 0);
selected_eff_value += group.GetSelectionAmount();
- value_ret += group.m_value;
- util::insert(out_set, group.m_outputs);
+ result.AddInput(group);
if (selected_eff_value >= target_value) {
- return std::make_pair(out_set, value_ret);
+ return result;
}
}
return std::nullopt;
@@ -241,10 +234,9 @@ static void ApproximateBestSubset(const std::vector<OutputGroup>& groups, const
}
}
-bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet)
+std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue)
{
- setCoinsRet.clear();
- nValueRet = 0;
+ SelectionResult result(nTargetValue);
// List of values less than target
std::optional<OutputGroup> lowest_larger;
@@ -255,9 +247,8 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
for (const OutputGroup& group : groups) {
if (group.GetSelectionAmount() == nTargetValue) {
- util::insert(setCoinsRet, group.m_outputs);
- nValueRet += group.m_value;
- return true;
+ result.AddInput(group);
+ return result;
} else if (group.GetSelectionAmount() < nTargetValue + MIN_CHANGE) {
applicable_groups.push_back(group);
nTotalLower += group.GetSelectionAmount();
@@ -268,17 +259,15 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
if (nTotalLower == nTargetValue) {
for (const auto& group : applicable_groups) {
- util::insert(setCoinsRet, group.m_outputs);
- nValueRet += group.m_value;
+ result.AddInput(group);
}
- return true;
+ return result;
}
if (nTotalLower < nTargetValue) {
- if (!lowest_larger) return false;
- util::insert(setCoinsRet, lowest_larger->m_outputs);
- nValueRet += lowest_larger->m_value;
- return true;
+ if (!lowest_larger) return std::nullopt;
+ result.AddInput(*lowest_larger);
+ return result;
}
// Solve subset sum by stochastic approximation
@@ -295,13 +284,11 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
// or the next bigger coin is closer), return the bigger coin
if (lowest_larger &&
((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->GetSelectionAmount() <= nBest)) {
- util::insert(setCoinsRet, lowest_larger->m_outputs);
- nValueRet += lowest_larger->m_value;
+ result.AddInput(*lowest_larger);
} else {
for (unsigned int i = 0; i < applicable_groups.size(); i++) {
if (vfBest[i]) {
- util::insert(setCoinsRet, applicable_groups[i].m_outputs);
- nValueRet += applicable_groups[i].m_value;
+ result.AddInput(applicable_groups[i]);
}
}
@@ -316,7 +303,7 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
}
}
- return true;
+ return result;
}
/******************************************************************************
@@ -395,3 +382,51 @@ CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cos
return waste;
}
+
+void SelectionResult::ComputeAndSetWaste(CAmount change_cost)
+{
+ m_waste = GetSelectionWaste(m_selected_inputs, change_cost, m_target, m_use_effective);
+}
+
+CAmount SelectionResult::GetWaste() const
+{
+ Assume(m_waste != std::nullopt);
+ return *m_waste;
+}
+
+CAmount SelectionResult::GetSelectedValue() const
+{
+ return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin.txout.nValue; });
+}
+
+void SelectionResult::Clear()
+{
+ m_selected_inputs.clear();
+ m_waste.reset();
+}
+
+void SelectionResult::AddInput(const OutputGroup& group)
+{
+ util::insert(m_selected_inputs, group.m_outputs);
+ m_use_effective = !group.m_subtract_fee_outputs;
+}
+
+const std::set<CInputCoin>& SelectionResult::GetInputSet() const
+{
+ return m_selected_inputs;
+}
+
+std::vector<CInputCoin> SelectionResult::GetShuffledInputVector() const
+{
+ std::vector<CInputCoin> coins(m_selected_inputs.begin(), m_selected_inputs.end());
+ Shuffle(coins.begin(), coins.end(), FastRandomContext());
+ return coins;
+}
+
+bool SelectionResult::operator<(SelectionResult other) const
+{
+ Assume(m_waste != std::nullopt);
+ Assume(other.m_waste != std::nullopt);
+ // As this operator is only used in std::min_element, we want the result that has more inputs when waste are equal.
+ return *m_waste < *other.m_waste || (*m_waste == *other.m_waste && m_selected_inputs.size() > other.m_selected_inputs.size());
+}
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index e7d467660f..637afcdb2b 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -187,6 +187,8 @@ struct OutputGroup
* where excess = selected_effective_value - target
* change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size
*
+ * Note this function is separate from SelectionResult for the tests.
+ *
* @param[in] inputs The selected inputs
* @param[in] change_cost The cost of creating change and spending it in the future.
* Only used if there is change, in which case it must be positive.
@@ -197,18 +199,55 @@ struct OutputGroup
*/
[[nodiscard]] CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true);
-bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret);
+struct SelectionResult
+{
+private:
+ /** Set of inputs selected by the algorithm to use in the transaction */
+ std::set<CInputCoin> m_selected_inputs;
+ /** The target the algorithm selected for. Note that this may not be equal to the recipient amount as it can include non-input fees */
+ const CAmount m_target;
+ /** Whether the input values for calculations should be the effective value (true) or normal value (false) */
+ bool m_use_effective{false};
+ /** The computed waste */
+ std::optional<CAmount> m_waste;
+
+public:
+ explicit SelectionResult(const CAmount target)
+ : m_target(target) {}
+
+ SelectionResult() = delete;
+
+ /** Get the sum of the input values */
+ [[nodiscard]] CAmount GetSelectedValue() const;
+
+ void Clear();
+
+ void AddInput(const OutputGroup& group);
+
+ /** Calculates and stores the waste for this selection via GetSelectionWaste */
+ void ComputeAndSetWaste(CAmount change_cost);
+ [[nodiscard]] CAmount GetWaste() const;
+
+ /** Get m_selected_inputs */
+ const std::set<CInputCoin>& GetInputSet() const;
+ /** Get the vector of CInputCoins that will be used to fill in a CTransaction's vin */
+ std::vector<CInputCoin> GetShuffledInputVector() const;
+
+ bool operator<(SelectionResult other) const;
+};
+
+std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change);
/** Select coins by Single Random Draw. OutputGroups are selected randomly from the eligible
* outputs until the target is satisfied
*
* @param[in] utxo_pool The positive effective value OutputGroups eligible for selection
* @param[in] target_value The target value to select for
- * @returns If successful, a pair of set of outputs and total selected value, otherwise, std::nullopt
+ * @returns If successful, a SelectionResult, otherwise, std::nullopt
*/
-std::optional<std::pair<std::set<CInputCoin>, CAmount>> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value);
+std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value);
// Original coin selection algorithm as a fallback
-bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet);
+std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue);
#endif // BITCOIN_WALLET_COINSELECTION_H
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index 5470177440..5d9cc7bf6b 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -373,81 +373,72 @@ std::vector<OutputGroup> GroupOutputs(const CWallet& wallet, const std::vector<C
return groups_out;
}
-bool AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins,
- std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params)
+std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins,
+ const CoinSelectionParams& coin_selection_params)
{
- setCoinsRet.clear();
- nValueRet = 0;
- // Vector of results for use with waste calculation
- // In order: calculated waste, selected inputs, selected input value (sum of input values)
- // TODO: Use a struct representing the selection result
- std::vector<std::tuple<CAmount, std::set<CInputCoin>, CAmount>> results;
+ // Vector of results. We will choose the best one based on waste.
+ std::vector<SelectionResult> results;
// Note that unlike KnapsackSolver, we do not include the fee for creating a change output as BnB will not create a change output.
std::vector<OutputGroup> positive_groups = GroupOutputs(wallet, coins, coin_selection_params, eligibility_filter, true /* positive_only */);
- std::set<CInputCoin> bnb_coins;
- CAmount bnb_value;
- if (SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, bnb_coins, bnb_value)) {
- const auto waste = GetSelectionWaste(bnb_coins, /* cost of change */ CAmount(0), nTargetValue, !coin_selection_params.m_subtract_fee_outputs);
- results.emplace_back(std::make_tuple(waste, std::move(bnb_coins), bnb_value));
+ if (auto bnb_result{SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change)}) {
+ bnb_result->ComputeAndSetWaste(CAmount(0));
+ results.push_back(*bnb_result);
}
// The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here.
std::vector<OutputGroup> all_groups = GroupOutputs(wallet, coins, coin_selection_params, eligibility_filter, false /* positive_only */);
// While nTargetValue includes the transaction fees for non-input things, it does not include the fee for creating a change output.
// So we need to include that for KnapsackSolver as well, as we are expecting to create a change output.
- std::set<CInputCoin> knapsack_coins;
- CAmount knapsack_value;
- if (KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, knapsack_coins, knapsack_value)) {
- const auto waste = GetSelectionWaste(knapsack_coins, coin_selection_params.m_cost_of_change, nTargetValue + coin_selection_params.m_change_fee, !coin_selection_params.m_subtract_fee_outputs);
- results.emplace_back(std::make_tuple(waste, std::move(knapsack_coins), knapsack_value));
+ if (auto knapsack_result{KnapsackSolver(all_groups, nTargetValue + coin_selection_params.m_change_fee)}) {
+ knapsack_result->ComputeAndSetWaste(coin_selection_params.m_cost_of_change);
+ results.push_back(*knapsack_result);
}
// We include the minimum final change for SRD as we do want to avoid making really small change.
// KnapsackSolver does not need this because it includes MIN_CHANGE internally.
const CAmount srd_target = nTargetValue + coin_selection_params.m_change_fee + MIN_FINAL_CHANGE;
- auto srd_result = SelectCoinsSRD(positive_groups, srd_target);
- if (srd_result != std::nullopt) {
- const auto waste = GetSelectionWaste(srd_result->first, coin_selection_params.m_cost_of_change, srd_target, !coin_selection_params.m_subtract_fee_outputs);
- results.emplace_back(std::make_tuple(waste, std::move(srd_result->first), srd_result->second));
+ if (auto srd_result{SelectCoinsSRD(positive_groups, srd_target)}) {
+ srd_result->ComputeAndSetWaste(coin_selection_params.m_cost_of_change);
+ results.push_back(*srd_result);
}
if (results.size() == 0) {
// No solution found
- return false;
+ return std::nullopt;
}
// Choose the result with the least waste
// If the waste is the same, choose the one which spends more inputs.
- const auto& best_result = std::min_element(results.begin(), results.end(), [](const auto& a, const auto& b) {
- return std::get<0>(a) < std::get<0>(b) || (std::get<0>(a) == std::get<0>(b) && std::get<1>(a).size() > std::get<1>(b).size());
- });
- setCoinsRet = std::get<1>(*best_result);
- nValueRet = std::get<2>(*best_result);
- return true;
+ auto& best_result = *std::min_element(results.begin(), results.end());
+ return best_result;
}
-bool SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params)
+std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, const CCoinControl& coin_control, const CoinSelectionParams& coin_selection_params)
{
std::vector<COutput> vCoins(vAvailableCoins);
CAmount value_to_select = nTargetValue;
+ OutputGroup preset_inputs(coin_selection_params);
+
// coin control -> return all selected outputs (we want all selected to go into the transaction for sure)
if (coin_control.HasSelected() && !coin_control.fAllowOtherInputs)
{
- for (const COutput& out : vCoins)
- {
- if (!out.fSpendable)
- continue;
- nValueRet += out.tx->tx->vout[out.i].nValue;
- setCoinsRet.insert(out.GetInputCoin());
+ for (const COutput& out : vCoins) {
+ if (!out.fSpendable) continue;
+ /* Set depth, from_me, ancestors, and descendants to 0 or false as these don't matter for preset inputs as no actual selection is being done.
+ * positive_only is set to false because we want to include all preset inputs, even if they are dust.
+ */
+ preset_inputs.Insert(out.GetInputCoin(), 0, false, 0, 0, false);
}
- return (nValueRet >= nTargetValue);
+ SelectionResult result(nTargetValue);
+ result.AddInput(preset_inputs);
+ if (result.GetSelectedValue() < nTargetValue) return std::nullopt;
+ return result;
}
// calculate value from preset inputs and store them
std::set<CInputCoin> setPresetCoins;
- CAmount nValueFromPresetInputs = 0;
std::vector<COutPoint> vPresetInputs;
coin_control.ListSelected(vPresetInputs);
@@ -459,7 +450,7 @@ bool SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCo
const CWalletTx& wtx = it->second;
// Clearly invalid input, fail
if (wtx.tx->vout.size() <= outpoint.n) {
- return false;
+ return std::nullopt;
}
input_bytes = GetTxSpendSize(wallet, wtx, outpoint.n, false);
txout = wtx.tx->vout.at(outpoint.n);
@@ -468,15 +459,14 @@ bool SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCo
// The input is external. We either did not find the tx in mapWallet, or we did but couldn't compute the input size with wallet data
if (!coin_control.GetExternalOutput(outpoint, txout)) {
// Not ours, and we don't have solving data.
- return false;
+ return std::nullopt;
}
input_bytes = CalculateMaximumSignedInputSize(txout, &coin_control.m_external_provider, /* use_max_sig */ true);
}
CInputCoin coin(outpoint, txout, input_bytes);
- nValueFromPresetInputs += coin.txout.nValue;
if (coin.m_input_bytes == -1) {
- return false; // Not solvable, can't estimate size for fee
+ return std::nullopt; // Not solvable, can't estimate size for fee
}
coin.effective_value = coin.txout.nValue - coin_selection_params.m_effective_feerate.GetFee(coin.m_input_bytes);
if (coin_selection_params.m_subtract_fee_outputs) {
@@ -485,6 +475,10 @@ bool SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCo
value_to_select -= coin.effective_value;
}
setPresetCoins.insert(coin);
+ /* Set depth, from_me, ancestors, and descendants to 0 or false as don't matter for preset inputs as no actual selection is being done.
+ * positive_only is set to false because we want to include all preset inputs, even if they are dust.
+ */
+ preset_inputs.Insert(coin, 0, false, 0, 0, false);
}
// remove preset inputs from vCoins so that Coin Selection doesn't pick them.
@@ -515,60 +509,62 @@ bool SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCo
// Coin Selection attempts to select inputs from a pool of eligible UTXOs to fund the
// transaction at a target feerate. If an attempt fails, more attempts may be made using a more
// permissive CoinEligibilityFilter.
- const bool res = [&] {
+ std::optional<SelectionResult> res = [&] {
// Pre-selected inputs already cover the target amount.
- if (value_to_select <= 0) return true;
+ if (value_to_select <= 0) return std::make_optional(SelectionResult(nTargetValue));
// If possible, fund the transaction with confirmed UTXOs only. Prefer at least six
// confirmations on outputs received from other wallets and only spend confirmed change.
- if (AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true;
- if (AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 1, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true;
+ if (auto r1{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, coin_selection_params)}) return r1;
+ if (auto r2{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 1, 0), vCoins, coin_selection_params)}) return r2;
// Fall back to using zero confirmation change (but with as few ancestors in the mempool as
// possible) if we cannot fund the transaction otherwise.
if (wallet.m_spend_zero_conf_change) {
- if (AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true;
- if (AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)),
- vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
- return true;
+ if (auto r3{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, coin_selection_params)}) return r3;
+ if (auto r4{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)),
+ vCoins, coin_selection_params)}) {
+ return r4;
}
- if (AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2),
- vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
- return true;
+ if (auto r5{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2),
+ vCoins, coin_selection_params)}) {
+ return r5;
}
// If partial groups are allowed, relax the requirement of spending OutputGroups (groups
// of UTXOs sent to the same address, which are obviously controlled by a single wallet)
// in their entirety.
- if (AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true /* include_partial_groups */),
- vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
- return true;
+ if (auto r6{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true /* include_partial_groups */),
+ vCoins, coin_selection_params)}) {
+ return r6;
}
// Try with unsafe inputs if they are allowed. This may spend unconfirmed outputs
// received from other wallets.
- if (coin_control.m_include_unsafe_inputs
- && AttemptSelection(wallet, value_to_select,
+ if (coin_control.m_include_unsafe_inputs) {
+ if (auto r7{AttemptSelection(wallet, value_to_select,
CoinEligibilityFilter(0 /* conf_mine */, 0 /* conf_theirs */, max_ancestors-1, max_descendants-1, true /* include_partial_groups */),
- vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
- return true;
+ vCoins, coin_selection_params)}) {
+ return r7;
+ }
}
// Try with unlimited ancestors/descendants. The transaction will still need to meet
// mempool ancestor/descendant policy to be accepted to mempool and broadcasted, but
// OutputGroups use heuristics that may overestimate ancestor/descendant counts.
- if (!fRejectLongChains && AttemptSelection(wallet, value_to_select,
+ if (!fRejectLongChains) {
+ if (auto r8{AttemptSelection(wallet, value_to_select,
CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max(), std::numeric_limits<uint64_t>::max(), true /* include_partial_groups */),
- vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
- return true;
+ vCoins, coin_selection_params)}) {
+ return r8;
+ }
}
}
// Coin Selection failed.
- return false;
+ return std::optional<SelectionResult>();
}();
- // AttemptSelection clears setCoinsRet, so add the preset inputs from coin_control to the coinset
- util::insert(setCoinsRet, setPresetCoins);
+ if (!res) return std::nullopt;
- // add preset inputs to the total value selected
- nValueRet += nValueFromPresetInputs;
+ // Add preset inputs to result
+ res->AddInput(preset_inputs);
return res;
}
@@ -766,17 +762,15 @@ static bool CreateTransactionInternal(
AvailableCoins(wallet, vAvailableCoins, &coin_control, 1, MAX_MONEY, MAX_MONEY, 0);
// Choose coins to use
- CAmount inputs_sum = 0;
- std::set<CInputCoin> setCoins;
- if (!SelectCoins(wallet, vAvailableCoins, /* nTargetValue */ selection_target, setCoins, inputs_sum, coin_control, coin_selection_params))
- {
+ std::optional<SelectionResult> result = SelectCoins(wallet, vAvailableCoins, /* nTargetValue */ selection_target, coin_control, coin_selection_params);
+ if (!result) {
error = _("Insufficient funds");
return false;
}
// Always make a change output
// We will reduce the fee from this change output later, and remove the output if it is too small.
- const CAmount change_and_fee = inputs_sum - recipients_sum;
+ const CAmount change_and_fee = result->GetSelectedValue() - recipients_sum;
assert(change_and_fee >= 0);
CTxOut newTxOut(change_and_fee, scriptChange);
@@ -795,8 +789,7 @@ static bool CreateTransactionInternal(
auto change_position = txNew.vout.insert(txNew.vout.begin() + nChangePosInOut, newTxOut);
// Shuffle selected coins and fill in final vin
- std::vector<CInputCoin> selected_coins(setCoins.begin(), setCoins.end());
- Shuffle(selected_coins.begin(), selected_coins.end(), FastRandomContext());
+ std::vector<CInputCoin> selected_coins = result->GetShuffledInputVector();
// Note how the sequence number is set to non-maxint so that
// the nLockTime set above actually works.
diff --git a/src/wallet/spend.h b/src/wallet/spend.h
index 7467dd9fa3..268bcfc033 100644
--- a/src/wallet/spend.h
+++ b/src/wallet/spend.h
@@ -101,29 +101,34 @@ std::map<CTxDestination, std::vector<COutput>> ListCoins(const CWallet& wallet)
std::vector<OutputGroup> GroupOutputs(const CWallet& wallet, const std::vector<COutput>& outputs, const CoinSelectionParams& coin_sel_params, const CoinEligibilityFilter& filter, bool positive_only);
/**
- * Shuffle and select coins until nTargetValue is reached while avoiding
- * small change; This method is stochastic for some inputs and upon
- * completion the coin set and corresponding actual target value is
- * assembled
- * param@[in] coins Set of UTXOs to consider. These will be categorized into
- * OutputGroups and filtered using eligibility_filter before
- * selecting coins.
- * param@[out] setCoinsRet Populated with the coins selected if successful.
- * param@[out] nValueRet Used to return the total value of selected coins.
+ * Attempt to find a valid input set that meets the provided eligibility filter and target.
+ * Multiple coin selection algorithms will be run and the input set that produces the least waste
+ * (according to the waste metric) will be chosen.
+ *
+ * param@[in] wallet The wallet which provides solving data for the coins
+ * param@[in] nTargetValue The target value
+ * param@[in] eligilibity_filter A filter containing rules for which coins are allowed to be included in this selection
+ * param@[in] coins The vector of coins available for selection prior to filtering
+ * param@[in] coin_selection_params Parameters for the coin selection
+ * returns If successful, a SelectionResult containing the input set
+ * If failed, a nullopt
*/
-bool AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins,
- std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params);
+std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins,
+ const CoinSelectionParams& coin_selection_params);
/**
- * Select a set of coins such that nValueRet >= nTargetValue and at least
+ * Select a set of coins such that nTargetValue is met and at least
* all coins from coin_control are selected; never select unconfirmed coins if they are not ours
- * param@[out] setCoinsRet Populated with inputs including pre-selected inputs from
- * coin_control and Coin Selection if successful.
- * param@[out] nValueRet Total value of selected coins including pre-selected ones
- * from coin_control and Coin Selection if successful.
+ * param@[in] wallet The wallet which provides data necessary to spend the selected coins
+ * param@[in] vAvailableCoins The vector of coins available to be spent
+ * param@[in] nTargetValue The target value
+ * param@[in] coin_selection_params Parameters for this coin selection such as feerates, whether to avoid partial spends,
+ * and whether to subtract the fee from the outputs.
+ * returns If successful, a SelectionResult containing the selected coins
+ * If failed, a nullopt.
*/
-bool SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet,
- const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params) EXCLUSIVE_LOCKS_REQUIRED(wallet.cs_wallet);
+std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, const CCoinControl& coin_control,
+ const CoinSelectionParams& coin_selection_params) EXCLUSIVE_LOCKS_REQUIRED(wallet.cs_wallet);
/**
* Create a new transaction paying the recipients with a set of coins
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index 0acd8a811f..a1fa871ccb 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -14,6 +14,7 @@
#include <wallet/test/wallet_test_fixture.h>
#include <wallet/wallet.h>
+#include <algorithm>
#include <boost/test/unit_test.hpp>
#include <random>
@@ -31,20 +32,35 @@ typedef std::set<CInputCoin> CoinSet;
static const CoinEligibilityFilter filter_standard(1, 6, 0);
static const CoinEligibilityFilter filter_confirmed(1, 1, 0);
static const CoinEligibilityFilter filter_standard_extra(6, 6, 0);
+static int nextLockTime = 0;
static void add_coin(const CAmount& nValue, int nInput, std::vector<CInputCoin>& set)
{
CMutableTransaction tx;
tx.vout.resize(nInput + 1);
tx.vout[nInput].nValue = nValue;
+ tx.nLockTime = nextLockTime++; // so all transactions get different hashes
set.emplace_back(MakeTransactionRef(tx), nInput);
}
+static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result)
+{
+ CMutableTransaction tx;
+ tx.vout.resize(nInput + 1);
+ tx.vout[nInput].nValue = nValue;
+ tx.nLockTime = nextLockTime++; // so all transactions get different hashes
+ CInputCoin coin(MakeTransactionRef(tx), nInput);
+ OutputGroup group;
+ group.Insert(coin, 1, false, 0, 0, true);
+ result.AddInput(group);
+}
+
static void add_coin(const CAmount& nValue, int nInput, CoinSet& set, CAmount fee = 0, CAmount long_term_fee = 0)
{
CMutableTransaction tx;
tx.vout.resize(nInput + 1);
tx.vout[nInput].nValue = nValue;
+ tx.nLockTime = nextLockTime++; // so all transactions get different hashes
CInputCoin coin(MakeTransactionRef(tx), nInput);
coin.effective_value = nValue - fee;
coin.m_fee = fee;
@@ -54,7 +70,6 @@ static void add_coin(const CAmount& nValue, int nInput, CoinSet& set, CAmount fe
static void add_coin(std::vector<COutput>& coins, CWallet& wallet, const CAmount& nValue, int nAge = 6*24, bool fIsFromMe = false, int nInput=0, bool spendable = false)
{
- static int nextLockTime = 0;
CMutableTransaction tx;
tx.nLockTime = nextLockTime++; // so all transactions get different hashes
tx.vout.resize(nInput + 1);
@@ -86,10 +101,30 @@ static void add_coin(std::vector<COutput>& coins, CWallet& wallet, const CAmount
coins.push_back(output);
}
-static bool equal_sets(CoinSet a, CoinSet b)
+/** Check if SelectionResult a is equivalent to SelectionResult b.
+ * Equivalent means same input values, but maybe different inputs (i.e. same value, different prevout) */
+static bool EquivalentResult(const SelectionResult& a, const SelectionResult& b)
+{
+ std::vector<CAmount> a_amts;
+ std::vector<CAmount> b_amts;
+ for (const auto& coin : a.GetInputSet()) {
+ a_amts.push_back(coin.txout.nValue);
+ }
+ for (const auto& coin : b.GetInputSet()) {
+ b_amts.push_back(coin.txout.nValue);
+ }
+ std::sort(a_amts.begin(), a_amts.end());
+ std::sort(b_amts.begin(), b_amts.end());
+
+ std::pair<std::vector<CAmount>::iterator, std::vector<CAmount>::iterator> ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin());
+ return ret.first == a_amts.end() && ret.second == b_amts.end();
+}
+
+/** Check if this selection is equal to another one. Equal means same inputs (i.e same value and prevout) */
+static bool EqualResult(const SelectionResult& a, const SelectionResult& b)
{
- std::pair<CoinSet::iterator, CoinSet::iterator> ret = mismatch(a.begin(), a.end(), b.begin());
- return ret.first == a.end() && ret.second == b.end();
+ std::pair<CoinSet::iterator, CoinSet::iterator> ret = std::mismatch(a.GetInputSet().begin(), a.GetInputSet().end(), b.GetInputSet().begin());
+ return ret.first == a.GetInputSet().end() && ret.second == b.GetInputSet().end();
}
static CAmount make_hard_case(int utxos, std::vector<CInputCoin>& utxo_pool)
@@ -142,17 +177,14 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
{
// Setup
std::vector<CInputCoin> utxo_pool;
- CoinSet selection;
- CoinSet actual_selection;
- CAmount value_ret = 0;
+ SelectionResult expected_result(CAmount(0));
/////////////////////////
// Known Outcome tests //
/////////////////////////
// Empty utxo pool
- BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret));
- selection.clear();
+ BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT));
// Add utxos
add_coin(1 * CENT, 1, utxo_pool);
@@ -161,87 +193,86 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
add_coin(4 * CENT, 4, utxo_pool);
// Select 1 Cent
- add_coin(1 * CENT, 1, actual_selection);
- BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret));
- BOOST_CHECK(equal_sets(selection, actual_selection));
- BOOST_CHECK_EQUAL(value_ret, 1 * CENT);
- actual_selection.clear();
- selection.clear();
+ add_coin(1 * CENT, 1, expected_result);
+ const auto result1 = SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT);
+ BOOST_CHECK(result1);
+ BOOST_CHECK(EquivalentResult(expected_result, *result1));
+ BOOST_CHECK_EQUAL(result1->GetSelectedValue(), 1 * CENT);
+ expected_result.Clear();
// Select 2 Cent
- add_coin(2 * CENT, 2, actual_selection);
- BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 2 * CENT, 0.5 * CENT, selection, value_ret));
- BOOST_CHECK(equal_sets(selection, actual_selection));
- BOOST_CHECK_EQUAL(value_ret, 2 * CENT);
- actual_selection.clear();
- selection.clear();
+ add_coin(2 * CENT, 2, expected_result);
+ const auto result2 = SelectCoinsBnB(GroupCoins(utxo_pool), 2 * CENT, 0.5 * CENT);
+ BOOST_CHECK(result2);
+ BOOST_CHECK(EquivalentResult(expected_result, *result2));
+ BOOST_CHECK_EQUAL(result2->GetSelectedValue(), 2 * CENT);
+ expected_result.Clear();
// Select 5 Cent
- add_coin(4 * CENT, 4, actual_selection);
- add_coin(1 * CENT, 1, actual_selection);
- BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 5 * CENT, 0.5 * CENT, selection, value_ret));
- BOOST_CHECK(equal_sets(selection, actual_selection));
- BOOST_CHECK_EQUAL(value_ret, 5 * CENT);
- actual_selection.clear();
- selection.clear();
+ add_coin(4 * CENT, 4, expected_result);
+ add_coin(1 * CENT, 1, expected_result);
+ const auto result3 = SelectCoinsBnB(GroupCoins(utxo_pool), 5 * CENT, 0.5 * CENT);
+ BOOST_CHECK(result3);
+ BOOST_CHECK(EquivalentResult(expected_result, *result3));
+ BOOST_CHECK_EQUAL(result3->GetSelectedValue(), 5 * CENT);
+ expected_result.Clear();
// Select 11 Cent, not possible
- BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 11 * CENT, 0.5 * CENT, selection, value_ret));
- actual_selection.clear();
- selection.clear();
+ BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 11 * CENT, 0.5 * CENT));
+ expected_result.Clear();
// Cost of change is greater than the difference between target value and utxo sum
- add_coin(1 * CENT, 1, actual_selection);
- BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0.5 * CENT, selection, value_ret));
- BOOST_CHECK_EQUAL(value_ret, 1 * CENT);
- BOOST_CHECK(equal_sets(selection, actual_selection));
- actual_selection.clear();
- selection.clear();
+ add_coin(1 * CENT, 1, expected_result);
+ const auto result4 = SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0.5 * CENT);
+ BOOST_CHECK(result4);
+ BOOST_CHECK_EQUAL(result4->GetSelectedValue(), 1 * CENT);
+ BOOST_CHECK(EquivalentResult(expected_result, *result4));
+ expected_result.Clear();
// Cost of change is less than the difference between target value and utxo sum
- BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0, selection, value_ret));
- actual_selection.clear();
- selection.clear();
+ BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0));
+ expected_result.Clear();
// Select 10 Cent
add_coin(5 * CENT, 5, utxo_pool);
- add_coin(5 * CENT, 5, actual_selection);
- add_coin(4 * CENT, 4, actual_selection);
- add_coin(1 * CENT, 1, actual_selection);
- BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 0.5 * CENT, selection, value_ret));
- BOOST_CHECK(equal_sets(selection, actual_selection));
- BOOST_CHECK_EQUAL(value_ret, 10 * CENT);
- actual_selection.clear();
- selection.clear();
+ add_coin(5 * CENT, 5, expected_result);
+ add_coin(4 * CENT, 4, expected_result);
+ add_coin(1 * CENT, 1, expected_result);
+ const auto result5 = SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 0.5 * CENT);
+ BOOST_CHECK(result5);
+ BOOST_CHECK(EquivalentResult(expected_result, *result5));
+ BOOST_CHECK_EQUAL(result5->GetSelectedValue(), 10 * CENT);
+ expected_result.Clear();
// Negative effective value
// Select 10 Cent but have 1 Cent not be possible because too small
- add_coin(5 * CENT, 5, actual_selection);
- add_coin(3 * CENT, 3, actual_selection);
- add_coin(2 * CENT, 2, actual_selection);
- BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 5000, selection, value_ret));
- BOOST_CHECK_EQUAL(value_ret, 10 * CENT);
+ add_coin(5 * CENT, 5, expected_result);
+ add_coin(3 * CENT, 3, expected_result);
+ add_coin(2 * CENT, 2, expected_result);
+ const auto result6 = SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 5000);
+ BOOST_CHECK(result6);
+ BOOST_CHECK_EQUAL(result6->GetSelectedValue(), 10 * CENT);
// FIXME: this test is redundant with the above, because 1 Cent is selected, not "too small"
- // BOOST_CHECK(equal_sets(selection, actual_selection));
+ // BOOST_CHECK(EquivalentResult(expected_result, *result));
// Select 0.25 Cent, not possible
- BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.25 * CENT, 0.5 * CENT, selection, value_ret));
- actual_selection.clear();
- selection.clear();
+ BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.25 * CENT, 0.5 * CENT));
+ expected_result.Clear();
// Iteration exhaustion test
CAmount target = make_hard_case(17, utxo_pool);
- BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), target, 0, selection, value_ret)); // Should exhaust
+ BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), target, 0)); // Should exhaust
target = make_hard_case(14, utxo_pool);
- BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), target, 0, selection, value_ret)); // Should not exhaust
+ const auto result7 = SelectCoinsBnB(GroupCoins(utxo_pool), target, 0); // Should not exhaust
+ BOOST_CHECK(result7);
// Test same value early bailout optimization
utxo_pool.clear();
- add_coin(7 * CENT, 7, actual_selection);
- add_coin(7 * CENT, 7, actual_selection);
- add_coin(7 * CENT, 7, actual_selection);
- add_coin(7 * CENT, 7, actual_selection);
- add_coin(2 * CENT, 7, actual_selection);
+ add_coin(7 * CENT, 7, expected_result);
+ add_coin(7 * CENT, 7, expected_result);
+ add_coin(7 * CENT, 7, expected_result);
+ add_coin(7 * CENT, 7, expected_result);
+ add_coin(2 * CENT, 7, expected_result);
add_coin(7 * CENT, 7, utxo_pool);
add_coin(7 * CENT, 7, utxo_pool);
add_coin(7 * CENT, 7, utxo_pool);
@@ -250,9 +281,10 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
for (int i = 0; i < 50000; ++i) {
add_coin(5 * CENT, 7, utxo_pool);
}
- BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 30 * CENT, 5000, selection, value_ret));
- BOOST_CHECK_EQUAL(value_ret, 30 * CENT);
- BOOST_CHECK(equal_sets(selection, actual_selection));
+ const auto result8 = SelectCoinsBnB(GroupCoins(utxo_pool), 30 * CENT, 5000);
+ BOOST_CHECK(result8);
+ BOOST_CHECK_EQUAL(result8->GetSelectedValue(), 30 * CENT);
+ BOOST_CHECK(EquivalentResult(expected_result, *result8));
////////////////////
// Behavior tests //
@@ -264,7 +296,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
}
// Run 100 times, to make sure it is never finding a solution
for (int i = 0; i < 100; ++i) {
- BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 2 * CENT, selection, value_ret));
+ BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 2 * CENT));
}
// Make sure that effective value is working in AttemptSelection when BnB is used
@@ -280,20 +312,19 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
wallet->SetupDescriptorScriptPubKeyMans();
std::vector<COutput> coins;
- CoinSet setCoinsRet;
- CAmount nValueRet;
add_coin(coins, *wallet, 1);
coins.at(0).nInputBytes = 40; // Make sure that it has a negative effective value. The next check should assert if this somehow got through. Otherwise it will fail
- BOOST_CHECK(!SelectCoinsBnB(GroupCoins(coins), 1 * CENT, coin_selection_params_bnb.m_cost_of_change, setCoinsRet, nValueRet));
+ BOOST_CHECK(!SelectCoinsBnB(GroupCoins(coins), 1 * CENT, coin_selection_params_bnb.m_cost_of_change));
// Test fees subtracted from output:
coins.clear();
add_coin(coins, *wallet, 1 * CENT);
coins.at(0).nInputBytes = 40;
coin_selection_params_bnb.m_subtract_fee_outputs = true;
- BOOST_CHECK(SelectCoinsBnB(GroupCoins(coins), 1 * CENT, coin_selection_params_bnb.m_cost_of_change, setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 1 * CENT);
+ const auto result9 = SelectCoinsBnB(GroupCoins(coins), 1 * CENT, coin_selection_params_bnb.m_cost_of_change);
+ BOOST_CHECK(result9);
+ BOOST_CHECK_EQUAL(result9->GetSelectedValue(), 1 * CENT);
}
{
@@ -304,8 +335,6 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
wallet->SetupDescriptorScriptPubKeyMans();
std::vector<COutput> coins;
- CoinSet setCoinsRet;
- CAmount nValueRet;
add_coin(coins, *wallet, 5 * CENT, 6 * 24, false, 0, true);
add_coin(coins, *wallet, 3 * CENT, 6 * 24, false, 0, true);
@@ -314,7 +343,8 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
coin_control.fAllowOtherInputs = true;
coin_control.Select(COutPoint(coins.at(0).tx->GetHash(), coins.at(0).i));
coin_selection_params_bnb.m_effective_feerate = CFeeRate(0);
- BOOST_CHECK(SelectCoins(*wallet, coins, 10 * CENT, setCoinsRet, nValueRet, coin_control, coin_selection_params_bnb));
+ const auto result10 = SelectCoins(*wallet, coins, 10 * CENT, coin_control, coin_selection_params_bnb);
+ BOOST_CHECK(result10);
}
}
@@ -326,8 +356,6 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
wallet->SetupDescriptorScriptPubKeyMans();
- CoinSet setCoinsRet, setCoinsRet2;
- CAmount nValueRet;
std::vector<COutput> coins;
// test multiple times to allow for differences in the shuffle order
@@ -336,25 +364,27 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
coins.clear();
// with an empty wallet we can't even pay one cent
- BOOST_CHECK(!KnapsackSolver(1 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_standard), setCoinsRet, nValueRet));
+ BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1 * CENT));
add_coin(coins, *wallet, 1*CENT, 4); // add a new 1 cent coin
// with a new 1 cent coin, we still can't find a mature 1 cent
- BOOST_CHECK(!KnapsackSolver(1 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_standard), setCoinsRet, nValueRet));
+ BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1 * CENT));
// but we can find a new 1 cent
- BOOST_CHECK(KnapsackSolver(1 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 1 * CENT);
+ const auto result1 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * CENT);
+ BOOST_CHECK(result1);
+ BOOST_CHECK_EQUAL(result1->GetSelectedValue(), 1 * CENT);
add_coin(coins, *wallet, 2*CENT); // add a mature 2 cent coin
// we can't make 3 cents of mature coins
- BOOST_CHECK(!KnapsackSolver(3 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_standard), setCoinsRet, nValueRet));
+ BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 3 * CENT));
// we can make 3 cents of new coins
- BOOST_CHECK(KnapsackSolver(3 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 3 * CENT);
+ const auto result2 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 3 * CENT);
+ BOOST_CHECK(result2);
+ BOOST_CHECK_EQUAL(result2->GetSelectedValue(), 3 * CENT);
add_coin(coins, *wallet, 5*CENT); // add a mature 5 cent coin,
add_coin(coins, *wallet, 10*CENT, 3, true); // a new 10 cent coin sent from one of our own addresses
@@ -363,35 +393,41 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
// now we have new: 1+10=11 (of which 10 was self-sent), and mature: 2+5+20=27. total = 38
// we can't make 38 cents only if we disallow new coins:
- BOOST_CHECK(!KnapsackSolver(38 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_standard), setCoinsRet, nValueRet));
+ BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 38 * CENT));
// we can't even make 37 cents if we don't allow new coins even if they're from us
- BOOST_CHECK(!KnapsackSolver(38 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_standard_extra), setCoinsRet, nValueRet));
+ BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard_extra), 38 * CENT));
// but we can make 37 cents if we accept new coins from ourself
- BOOST_CHECK(KnapsackSolver(37 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_standard), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 37 * CENT);
+ const auto result3 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 37 * CENT);
+ BOOST_CHECK(result3);
+ BOOST_CHECK_EQUAL(result3->GetSelectedValue(), 37 * CENT);
// and we can make 38 cents if we accept all new coins
- BOOST_CHECK(KnapsackSolver(38 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 38 * CENT);
+ const auto result4 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 38 * CENT);
+ BOOST_CHECK(result4);
+ BOOST_CHECK_EQUAL(result4->GetSelectedValue(), 38 * CENT);
// try making 34 cents from 1,2,5,10,20 - we can't do it exactly
- BOOST_CHECK(KnapsackSolver(34 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 35 * CENT); // but 35 cents is closest
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U); // the best should be 20+10+5. it's incredibly unlikely the 1 or 2 got included (but possible)
+ const auto result5 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 34 * CENT);
+ BOOST_CHECK(result5);
+ BOOST_CHECK_EQUAL(result5->GetSelectedValue(), 35 * CENT); // but 35 cents is closest
+ BOOST_CHECK_EQUAL(result5->GetInputSet().size(), 3U); // the best should be 20+10+5. it's incredibly unlikely the 1 or 2 got included (but possible)
// when we try making 7 cents, the smaller coins (1,2,5) are enough. We should see just 2+5
- BOOST_CHECK(KnapsackSolver(7 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 7 * CENT);
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
+ const auto result6 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 7 * CENT);
+ BOOST_CHECK(result6);
+ BOOST_CHECK_EQUAL(result6->GetSelectedValue(), 7 * CENT);
+ BOOST_CHECK_EQUAL(result6->GetInputSet().size(), 2U);
// when we try making 8 cents, the smaller coins (1,2,5) are exactly enough.
- BOOST_CHECK(KnapsackSolver(8 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK(nValueRet == 8 * CENT);
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
+ const auto result7 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 8 * CENT);
+ BOOST_CHECK(result7);
+ BOOST_CHECK(result7->GetSelectedValue() == 8 * CENT);
+ BOOST_CHECK_EQUAL(result7->GetInputSet().size(), 3U);
// when we try making 9 cents, no subset of smaller coins is enough, and we get the next bigger coin (10)
- BOOST_CHECK(KnapsackSolver(9 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 10 * CENT);
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
+ const auto result8 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 9 * CENT);
+ BOOST_CHECK(result8);
+ BOOST_CHECK_EQUAL(result8->GetSelectedValue(), 10 * CENT);
+ BOOST_CHECK_EQUAL(result8->GetInputSet().size(), 1U);
// now clear out the wallet and start again to test choosing between subsets of smaller coins and the next biggest coin
coins.clear();
@@ -403,45 +439,52 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
add_coin(coins, *wallet, 30*CENT); // now we have 6+7+8+20+30 = 71 cents total
// check that we have 71 and not 72
- BOOST_CHECK(KnapsackSolver(71 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK(!KnapsackSolver(72 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
+ const auto result9 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 71 * CENT);
+ BOOST_CHECK(result9);
+ BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 72 * CENT));
// now try making 16 cents. the best smaller coins can do is 6+7+8 = 21; not as good at the next biggest coin, 20
- BOOST_CHECK(KnapsackSolver(16 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 20 * CENT); // we should get 20 in one coin
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
+ const auto result10 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT);
+ BOOST_CHECK(result10);
+ BOOST_CHECK_EQUAL(result10->GetSelectedValue(), 20 * CENT); // we should get 20 in one coin
+ BOOST_CHECK_EQUAL(result10->GetInputSet().size(), 1U);
add_coin(coins, *wallet, 5*CENT); // now we have 5+6+7+8+20+30 = 75 cents total
// now if we try making 16 cents again, the smaller coins can make 5+6+7 = 18 cents, better than the next biggest coin, 20
- BOOST_CHECK(KnapsackSolver(16 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 18 * CENT); // we should get 18 in 3 coins
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
+ const auto result11 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT);
+ BOOST_CHECK(result11);
+ BOOST_CHECK_EQUAL(result11->GetSelectedValue(), 18 * CENT); // we should get 18 in 3 coins
+ BOOST_CHECK_EQUAL(result11->GetInputSet().size(), 3U);
add_coin(coins, *wallet, 18*CENT); // now we have 5+6+7+8+18+20+30
// and now if we try making 16 cents again, the smaller coins can make 5+6+7 = 18 cents, the same as the next biggest coin, 18
- BOOST_CHECK(KnapsackSolver(16 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 18 * CENT); // we should get 18 in 1 coin
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); // because in the event of a tie, the biggest coin wins
+ const auto result12 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT);
+ BOOST_CHECK(result12);
+ BOOST_CHECK_EQUAL(result12->GetSelectedValue(), 18 * CENT); // we should get 18 in 1 coin
+ BOOST_CHECK_EQUAL(result12->GetInputSet().size(), 1U); // because in the event of a tie, the biggest coin wins
// now try making 11 cents. we should get 5+6
- BOOST_CHECK(KnapsackSolver(11 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 11 * CENT);
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
+ const auto result13 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 11 * CENT);
+ BOOST_CHECK(result13);
+ BOOST_CHECK_EQUAL(result13->GetSelectedValue(), 11 * CENT);
+ BOOST_CHECK_EQUAL(result13->GetInputSet().size(), 2U);
// check that the smallest bigger coin is used
add_coin(coins, *wallet, 1*COIN);
add_coin(coins, *wallet, 2*COIN);
add_coin(coins, *wallet, 3*COIN);
add_coin(coins, *wallet, 4*COIN); // now we have 5+6+7+8+18+20+30+100+200+300+400 = 1094 cents
- BOOST_CHECK(KnapsackSolver(95 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 1 * COIN); // we should get 1 BTC in 1 coin
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
+ const auto result14 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 95 * CENT);
+ BOOST_CHECK(result14);
+ BOOST_CHECK_EQUAL(result14->GetSelectedValue(), 1 * COIN); // we should get 1 BTC in 1 coin
+ BOOST_CHECK_EQUAL(result14->GetInputSet().size(), 1U);
- BOOST_CHECK(KnapsackSolver(195 * CENT, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 2 * COIN); // we should get 2 BTC in 1 coin
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
+ const auto result15 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 195 * CENT);
+ BOOST_CHECK(result15);
+ BOOST_CHECK_EQUAL(result15->GetSelectedValue(), 2 * COIN); // we should get 2 BTC in 1 coin
+ BOOST_CHECK_EQUAL(result15->GetInputSet().size(), 1U);
// empty the wallet and start again, now with fractions of a cent, to test small change avoidance
@@ -454,23 +497,26 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
// try making 1 * MIN_CHANGE from the 1.5 * MIN_CHANGE
// we'll get change smaller than MIN_CHANGE whatever happens, so can expect MIN_CHANGE exactly
- BOOST_CHECK(KnapsackSolver(MIN_CHANGE, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE);
+ const auto result16 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), MIN_CHANGE);
+ BOOST_CHECK(result16);
+ BOOST_CHECK_EQUAL(result16->GetSelectedValue(), MIN_CHANGE);
// but if we add a bigger coin, small change is avoided
add_coin(coins, *wallet, 1111*MIN_CHANGE);
// try making 1 from 0.1 + 0.2 + 0.3 + 0.4 + 0.5 + 1111 = 1112.5
- BOOST_CHECK(KnapsackSolver(1 * MIN_CHANGE, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 1 * MIN_CHANGE); // we should get the exact amount
+ const auto result17 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * MIN_CHANGE);
+ BOOST_CHECK(result17);
+ BOOST_CHECK_EQUAL(result17->GetSelectedValue(), 1 * MIN_CHANGE); // we should get the exact amount
// if we add more small coins:
add_coin(coins, *wallet, MIN_CHANGE * 6 / 10);
add_coin(coins, *wallet, MIN_CHANGE * 7 / 10);
// and try again to make 1.0 * MIN_CHANGE
- BOOST_CHECK(KnapsackSolver(1 * MIN_CHANGE, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 1 * MIN_CHANGE); // we should get the exact amount
+ const auto result18 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * MIN_CHANGE);
+ BOOST_CHECK(result18);
+ BOOST_CHECK_EQUAL(result18->GetSelectedValue(), 1 * MIN_CHANGE); // we should get the exact amount
// run the 'mtgox' test (see https://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf)
// they tried to consolidate 10 50k coins into one 500k coin, and ended up with 50k in change
@@ -478,9 +524,10 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
for (int j = 0; j < 20; j++)
add_coin(coins, *wallet, 50000 * COIN);
- BOOST_CHECK(KnapsackSolver(500000 * COIN, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 500000 * COIN); // we should get the exact amount
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 10U); // in ten coins
+ const auto result19 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 500000 * COIN);
+ BOOST_CHECK(result19);
+ BOOST_CHECK_EQUAL(result19->GetSelectedValue(), 500000 * COIN); // we should get the exact amount
+ BOOST_CHECK_EQUAL(result19->GetInputSet().size(), 10U); // in ten coins
// if there's not enough in the smaller coins to make at least 1 * MIN_CHANGE change (0.5+0.6+0.7 < 1.0+1.0),
// we need to try finding an exact subset anyway
@@ -491,9 +538,10 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
add_coin(coins, *wallet, MIN_CHANGE * 6 / 10);
add_coin(coins, *wallet, MIN_CHANGE * 7 / 10);
add_coin(coins, *wallet, 1111 * MIN_CHANGE);
- BOOST_CHECK(KnapsackSolver(1 * MIN_CHANGE, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 1111 * MIN_CHANGE); // we get the bigger coin
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
+ const auto result20 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * MIN_CHANGE);
+ BOOST_CHECK(result20);
+ BOOST_CHECK_EQUAL(result20->GetSelectedValue(), 1111 * MIN_CHANGE); // we get the bigger coin
+ BOOST_CHECK_EQUAL(result20->GetInputSet().size(), 1U);
// but sometimes it's possible, and we use an exact subset (0.4 + 0.6 = 1.0)
coins.clear();
@@ -501,9 +549,10 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
add_coin(coins, *wallet, MIN_CHANGE * 6 / 10);
add_coin(coins, *wallet, MIN_CHANGE * 8 / 10);
add_coin(coins, *wallet, 1111 * MIN_CHANGE);
- BOOST_CHECK(KnapsackSolver(MIN_CHANGE, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE); // we should get the exact amount
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U); // in two coins 0.4+0.6
+ const auto result21 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), MIN_CHANGE);
+ BOOST_CHECK(result21);
+ BOOST_CHECK_EQUAL(result21->GetSelectedValue(), MIN_CHANGE); // we should get the exact amount
+ BOOST_CHECK_EQUAL(result21->GetInputSet().size(), 2U); // in two coins 0.4+0.6
// test avoiding small change
coins.clear();
@@ -512,14 +561,16 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
add_coin(coins, *wallet, MIN_CHANGE * 100);
// trying to make 100.01 from these three coins
- BOOST_CHECK(KnapsackSolver(MIN_CHANGE * 10001 / 100, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE * 10105 / 100); // we should get all coins
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
+ const auto result22 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), MIN_CHANGE * 10001 / 100);
+ BOOST_CHECK(result22);
+ BOOST_CHECK_EQUAL(result22->GetSelectedValue(), MIN_CHANGE * 10105 / 100); // we should get all coins
+ BOOST_CHECK_EQUAL(result22->GetInputSet().size(), 3U);
// but if we try to make 99.9, we should take the bigger of the two small coins to avoid small change
- BOOST_CHECK(KnapsackSolver(MIN_CHANGE * 9990 / 100, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 101 * MIN_CHANGE);
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
+ const auto result23 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), MIN_CHANGE * 9990 / 100);
+ BOOST_CHECK(result23);
+ BOOST_CHECK_EQUAL(result23->GetSelectedValue(), 101 * MIN_CHANGE);
+ BOOST_CHECK_EQUAL(result23->GetInputSet().size(), 2U);
}
// test with many inputs
@@ -531,18 +582,19 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
// We only create the wallet once to save time, but we still run the coin selection RUN_TESTS times.
for (int i = 0; i < RUN_TESTS; i++) {
- BOOST_CHECK(KnapsackSolver(2000, KnapsackGroupOutputs(coins, *wallet, filter_confirmed), setCoinsRet, nValueRet));
+ const auto result24 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 2000);
+ BOOST_CHECK(result24);
if (amt - 2000 < MIN_CHANGE) {
// needs more than one input:
uint16_t returnSize = std::ceil((2000.0 + MIN_CHANGE)/amt);
CAmount returnValue = amt * returnSize;
- BOOST_CHECK_EQUAL(nValueRet, returnValue);
- BOOST_CHECK_EQUAL(setCoinsRet.size(), returnSize);
+ BOOST_CHECK_EQUAL(result24->GetSelectedValue(), returnValue);
+ BOOST_CHECK_EQUAL(result24->GetInputSet().size(), returnSize);
} else {
// one input is sufficient:
- BOOST_CHECK_EQUAL(nValueRet, amt);
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
+ BOOST_CHECK_EQUAL(result24->GetSelectedValue(), amt);
+ BOOST_CHECK_EQUAL(result24->GetInputSet().size(), 1U);
}
}
}
@@ -557,9 +609,11 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
for (int i = 0; i < RUN_TESTS; i++) {
// picking 50 from 100 coins doesn't depend on the shuffle,
// but does depend on randomness in the stochastic approximation code
- BOOST_CHECK(KnapsackSolver(50 * COIN, GroupCoins(coins), setCoinsRet, nValueRet));
- BOOST_CHECK(KnapsackSolver(50 * COIN, GroupCoins(coins), setCoinsRet2, nValueRet));
- BOOST_CHECK(!equal_sets(setCoinsRet, setCoinsRet2));
+ const auto result25 = KnapsackSolver(GroupCoins(coins), 50 * COIN);
+ BOOST_CHECK(result25);
+ const auto result26 = KnapsackSolver(GroupCoins(coins), 50 * COIN);
+ BOOST_CHECK(result26);
+ BOOST_CHECK(!EqualResult(*result25, *result26));
int fails = 0;
for (int j = 0; j < RANDOM_REPEATS; j++)
@@ -568,9 +622,11 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
// When choosing 1 from 100 identical coins, 1% of the time, this test will choose the same coin twice
// which will cause it to fail.
// To avoid that issue, run the test RANDOM_REPEATS times and only complain if all of them fail
- BOOST_CHECK(KnapsackSolver(COIN, GroupCoins(coins), setCoinsRet, nValueRet));
- BOOST_CHECK(KnapsackSolver(COIN, GroupCoins(coins), setCoinsRet2, nValueRet));
- if (equal_sets(setCoinsRet, setCoinsRet2))
+ const auto result27 = KnapsackSolver(GroupCoins(coins), COIN);
+ BOOST_CHECK(result27);
+ const auto result28 = KnapsackSolver(GroupCoins(coins), COIN);
+ BOOST_CHECK(result28);
+ if (EqualResult(*result27, *result28))
fails++;
}
BOOST_CHECK_NE(fails, RANDOM_REPEATS);
@@ -589,9 +645,11 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
int fails = 0;
for (int j = 0; j < RANDOM_REPEATS; j++)
{
- BOOST_CHECK(KnapsackSolver(90*CENT, GroupCoins(coins), setCoinsRet, nValueRet));
- BOOST_CHECK(KnapsackSolver(90*CENT, GroupCoins(coins), setCoinsRet2, nValueRet));
- if (equal_sets(setCoinsRet, setCoinsRet2))
+ const auto result29 = KnapsackSolver(GroupCoins(coins), 90 * CENT);
+ BOOST_CHECK(result29);
+ const auto result30 = KnapsackSolver(GroupCoins(coins), 90 * CENT);
+ BOOST_CHECK(result30);
+ if (EqualResult(*result29, *result30))
fails++;
}
BOOST_CHECK_NE(fails, RANDOM_REPEATS);
@@ -607,8 +665,6 @@ BOOST_AUTO_TEST_CASE(ApproximateBestSubset)
wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
wallet->SetupDescriptorScriptPubKeyMans();
- CoinSet setCoinsRet;
- CAmount nValueRet;
std::vector<COutput> coins;
// Test vValue sort order
@@ -616,9 +672,10 @@ BOOST_AUTO_TEST_CASE(ApproximateBestSubset)
add_coin(coins, *wallet, 1000 * COIN);
add_coin(coins, *wallet, 3 * COIN);
- BOOST_CHECK(KnapsackSolver(1003 * COIN, KnapsackGroupOutputs(coins, *wallet, filter_standard), setCoinsRet, nValueRet));
- BOOST_CHECK_EQUAL(nValueRet, 1003 * COIN);
- BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
+ const auto result = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1003 * COIN);
+ BOOST_CHECK(result);
+ BOOST_CHECK_EQUAL(result->GetSelectedValue(), 1003 * COIN);
+ BOOST_CHECK_EQUAL(result->GetInputSet().size(), 2U);
}
// Tests that with the ideal conditions, the coin selector will always be able to find a solution that can pay the target value
@@ -660,11 +717,10 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test)
/* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0),
/* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0),
/* tx_noinputs_size= */ 0, /* avoid_partial= */ false);
- CoinSet out_set;
- CAmount out_value = 0;
CCoinControl cc;
- BOOST_CHECK(SelectCoins(*wallet, coins, target, out_set, out_value, cc, cs_params));
- BOOST_CHECK_GE(out_value, target);
+ const auto result = SelectCoins(*wallet, coins, target, cc, cs_params);
+ BOOST_CHECK(result);
+ BOOST_CHECK_GE(result->GetSelectedValue(), target);
}
}
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-05 23:38:07 +0000