diff options
author | Andrew Chow <achow101-github@achow101.com> | 2020-11-16 14:31:45 -0500 |
---|---|---|
committer | Andrew Chow <achow101-github@achow101.com> | 2021-12-05 13:39:51 -0500 |
commit | 60d2ca72e3f4c56433c63b929a88e7a2def06399 (patch) | |
tree | 80ff962de3f9f1e99ee14d6261b38aaf218dcaa6 /src | |
parent | a339add471717623915cd1a846ade4dab2c89deb (diff) | |
download | bitcoin-60d2ca72e3f4c56433c63b929a88e7a2def06399.tar.xz |
Return SelectionResult from SelectCoinsBnB
Removes coins_out and value_ret has SelectCoinsBnB return a
std::optional<SelectionResult>
Diffstat (limited to 'src')
-rw-r--r-- | src/bench/coin_selection.cpp | 5 | ||||
-rw-r--r-- | src/wallet/coinselection.cpp | 20 | ||||
-rw-r--r-- | src/wallet/coinselection.h | 2 | ||||
-rw-r--r-- | src/wallet/spend.cpp | 8 | ||||
-rw-r--r-- | src/wallet/test/coinselector_tests.cpp | 95 |
5 files changed, 60 insertions, 70 deletions
diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp index fd5145950b..0ac8fc6b34 100644 --- a/src/bench/coin_selection.cpp +++ b/src/bench/coin_selection.cpp @@ -92,17 +92,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 bfe3074944..4d90eefbfe 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,19 +153,17 @@ 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) @@ -421,6 +416,7 @@ void SelectionResult::Clear() 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 diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index 2c9a517485..3e42ed2aa2 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -234,7 +234,7 @@ public: bool operator<(SelectionResult other) const; }; -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); /** Select coins by Single Random Draw. OutputGroups are selected randomly from the eligible * outputs until the target is satisfied diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index 5470177440..022420c57d 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -385,11 +385,9 @@ bool AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const // 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.emplace_back(std::make_tuple(bnb_result->GetWaste(), bnb_result->GetInputSet(), bnb_result->GetSelectedValue())); } // 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. diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index d0d7a927b0..8bb2105242 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> @@ -95,20 +96,22 @@ static void add_coin(std::vector<COutput>& coins, CWallet& wallet, const CAmount coins.push_back(output); } -static bool equivalent_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) { + for (const auto& coin : a.GetInputSet()) { a_amts.push_back(coin.txout.nValue); } - for (const auto& coin : b) { + 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 = mismatch(a_amts.begin(), a_amts.end(), b_amts.begin()); + 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(); } @@ -168,17 +171,14 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) { // Setup std::vector<CInputCoin> utxo_pool; - CoinSet selection; SelectionResult expected_result(CAmount(0)); - CAmount value_ret = 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); @@ -188,78 +188,77 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) // Select 1 Cent add_coin(1 * CENT, 1, expected_result); - BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret)); - BOOST_CHECK(equivalent_sets(selection, expected_result.GetInputSet())); - BOOST_CHECK_EQUAL(value_ret, 1 * CENT); + 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(); - selection.clear(); // Select 2 Cent add_coin(2 * CENT, 2, expected_result); - BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 2 * CENT, 0.5 * CENT, selection, value_ret)); - BOOST_CHECK(equivalent_sets(selection, expected_result.GetInputSet())); - BOOST_CHECK_EQUAL(value_ret, 2 * CENT); + 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(); - selection.clear(); // Select 5 Cent add_coin(4 * CENT, 4, expected_result); add_coin(1 * CENT, 1, expected_result); - BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 5 * CENT, 0.5 * CENT, selection, value_ret)); - BOOST_CHECK(equivalent_sets(selection, expected_result.GetInputSet())); - BOOST_CHECK_EQUAL(value_ret, 5 * CENT); + 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(); - selection.clear(); // Select 11 Cent, not possible - BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 11 * CENT, 0.5 * CENT, selection, value_ret)); + BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 11 * CENT, 0.5 * CENT)); expected_result.Clear(); - selection.clear(); // Cost of change is greater than the difference between target value and utxo sum add_coin(1 * CENT, 1, expected_result); - BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0.5 * CENT, selection, value_ret)); - BOOST_CHECK_EQUAL(value_ret, 1 * CENT); - BOOST_CHECK(equivalent_sets(selection, expected_result.GetInputSet())); + 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(); - selection.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)); + BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0)); expected_result.Clear(); - selection.clear(); // Select 10 Cent add_coin(5 * CENT, 5, utxo_pool); add_coin(5 * CENT, 5, expected_result); add_coin(4 * CENT, 4, expected_result); add_coin(1 * CENT, 1, expected_result); - BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 0.5 * CENT, selection, value_ret)); - BOOST_CHECK(equivalent_sets(selection, expected_result.GetInputSet())); - BOOST_CHECK_EQUAL(value_ret, 10 * CENT); + 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(); - selection.clear(); // Negative effective value // Select 10 Cent but have 1 Cent not be possible because too small add_coin(5 * CENT, 5, expected_result); add_coin(3 * CENT, 3, expected_result); add_coin(2 * CENT, 2, expected_result); - BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 5000, selection, value_ret)); - BOOST_CHECK_EQUAL(value_ret, 10 * CENT); + 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(equivalent_sets(selection, expected_result.GetInputSet())); + // 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)); + BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.25 * CENT, 0.5 * CENT)); expected_result.Clear(); - selection.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(); @@ -276,9 +275,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(equivalent_sets(selection, expected_result.GetInputSet())); + 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 // @@ -290,7 +290,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 @@ -306,20 +306,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); } { |