From 70f31f1a81710aa59e95770de9a84bf58cbce1e8 Mon Sep 17 00:00:00 2001 From: Andrew Chow Date: Mon, 17 Jan 2022 17:18:31 -0500 Subject: coinselection: Use COutput instead of CInputCoin Also rename setPresetCoins to preset_coins --- src/bench/coin_selection.cpp | 4 ++-- src/wallet/coinselection.cpp | 36 ++++++++++++++-------------- src/wallet/coinselection.h | 26 ++++++++++++++------ src/wallet/spend.cpp | 44 +++++++++++++++++----------------- src/wallet/test/coinselector_tests.cpp | 33 +++++++++---------------- 5 files changed, 72 insertions(+), 71 deletions(-) (limited to 'src') diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp index 8ed0f6df2b..b332ef9c11 100644 --- a/src/bench/coin_selection.cpp +++ b/src/bench/coin_selection.cpp @@ -82,9 +82,9 @@ static void add_coin(const CAmount& nValue, int nInput, std::vector CMutableTransaction tx; tx.vout.resize(nInput + 1); tx.vout[nInput].nValue = nValue; - CInputCoin coin(MakeTransactionRef(tx), nInput); + COutput output(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 0, /*input_bytes=*/ -1, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ true); set.emplace_back(); - set.back().Insert(coin, 0, true, 0, 0, false); + set.back().Insert(output, /*ancestors=*/ 0, /*descendants=*/ 0, /*positive_only=*/ false); } // Copied from src/wallet/test/coinselector_tests.cpp static CAmount make_hard_case(int utxos, std::vector& utxo_pool) diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 08c36de38a..7347ad1d40 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -50,8 +50,8 @@ struct { * The Branch and Bound algorithm is described in detail in Murch's Master Thesis: * https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf * - * @param const std::vector& utxo_pool The set of UTXOs that we are choosing from. - * These UTXOs will be sorted in descending order by effective value and the CInputCoins' + * @param const std::vector& utxo_pool The set of UTXO groups that we are choosing from. + * These UTXO groups will be sorted in descending order by effective value and the OutputGroups' * values are their effective values. * @param const CAmount& selection_target This is the value that we want to select. It is the lower * bound of the range. @@ -315,29 +315,29 @@ std::optional KnapsackSolver(std::vector& groups, ******************************************************************************/ -void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only) { +void OutputGroup::Insert(const COutput& output, size_t ancestors, size_t descendants, bool positive_only) { // Compute the effective value first - const CAmount coin_fee = output.m_input_bytes < 0 ? 0 : m_effective_feerate.GetFee(output.m_input_bytes); + const CAmount coin_fee = output.input_bytes < 0 ? 0 : m_effective_feerate.GetFee(output.input_bytes); const CAmount ev = output.txout.nValue - coin_fee; // Filter for positive only here before adding the coin if (positive_only && ev <= 0) return; m_outputs.push_back(output); - CInputCoin& coin = m_outputs.back(); + COutput& coin = m_outputs.back(); - coin.m_fee = coin_fee; - fee += coin.m_fee; + coin.fee = coin_fee; + fee += coin.fee; - coin.m_long_term_fee = coin.m_input_bytes < 0 ? 0 : m_long_term_feerate.GetFee(coin.m_input_bytes); - long_term_fee += coin.m_long_term_fee; + coin.long_term_fee = coin.input_bytes < 0 ? 0 : m_long_term_feerate.GetFee(coin.input_bytes); + long_term_fee += coin.long_term_fee; coin.effective_value = ev; effective_value += coin.effective_value; - m_from_me &= from_me; - m_value += output.txout.nValue; - m_depth = std::min(m_depth, depth); + m_from_me &= coin.from_me; + m_value += coin.txout.nValue; + m_depth = std::min(m_depth, coin.depth); // ancestors here express the number of ancestors the new coin will end up having, which is // the sum, rather than the max; this will overestimate in the cases where multiple inputs // have common ancestors @@ -359,7 +359,7 @@ CAmount OutputGroup::GetSelectionAmount() const return m_subtract_fee_outputs ? m_value : effective_value; } -CAmount GetSelectionWaste(const std::set& inputs, CAmount change_cost, CAmount target, bool use_effective_value) +CAmount GetSelectionWaste(const std::set& inputs, CAmount change_cost, CAmount target, bool use_effective_value) { // This function should not be called with empty inputs as that would mean the selection failed assert(!inputs.empty()); @@ -367,8 +367,8 @@ CAmount GetSelectionWaste(const std::set& inputs, CAmount change_cos // Always consider the cost of spending an input now vs in the future. CAmount waste = 0; CAmount selected_effective_value = 0; - for (const CInputCoin& coin : inputs) { - waste += coin.m_fee - coin.m_long_term_fee; + for (const COutput& coin : inputs) { + waste += coin.fee - coin.long_term_fee; selected_effective_value += use_effective_value ? coin.effective_value : coin.txout.nValue; } @@ -413,14 +413,14 @@ void SelectionResult::AddInput(const OutputGroup& group) m_use_effective = !group.m_subtract_fee_outputs; } -const std::set& SelectionResult::GetInputSet() const +const std::set& SelectionResult::GetInputSet() const { return m_selected_inputs; } -std::vector SelectionResult::GetShuffledInputVector() const +std::vector SelectionResult::GetShuffledInputVector() const { - std::vector coins(m_selected_inputs.begin(), m_selected_inputs.end()); + std::vector coins(m_selected_inputs.begin(), m_selected_inputs.end()); Shuffle(coins.begin(), coins.end(), FastRandomContext()); return coins; } diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index 5dbb63310c..4d39be364c 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -138,6 +138,18 @@ public: { return CInputCoin(outpoint, txout, input_bytes); } + + bool operator<(const COutput& rhs) const { + return outpoint < rhs.outpoint; + } + + bool operator!=(const COutput& rhs) const { + return outpoint != rhs.outpoint; + } + + bool operator==(const COutput& rhs) const { + return outpoint == rhs.outpoint; + } }; /** Parameters for one iteration of Coin Selection. */ @@ -207,7 +219,7 @@ struct CoinEligibilityFilter struct OutputGroup { /** The list of UTXOs contained in this output group. */ - std::vector m_outputs; + std::vector m_outputs; /** Whether the UTXOs were sent by the wallet to itself. This is relevant because we may want at * least a certain number of confirmations on UTXOs received from outside wallets while trusting * our own UTXOs more. */ @@ -244,7 +256,7 @@ struct OutputGroup m_subtract_fee_outputs(params.m_subtract_fee_outputs) {} - void Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only); + void Insert(const COutput& output, size_t ancestors, size_t descendants, bool positive_only); bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const; CAmount GetSelectionAmount() const; }; @@ -266,13 +278,13 @@ struct OutputGroup * @param[in] use_effective_value Whether to use the input's effective value (when true) or the real value (when false). * @return The waste */ -[[nodiscard]] CAmount GetSelectionWaste(const std::set& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true); +[[nodiscard]] CAmount GetSelectionWaste(const std::set& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true); struct SelectionResult { private: /** Set of inputs selected by the algorithm to use in the transaction */ - std::set m_selected_inputs; + std::set 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) */ @@ -298,9 +310,9 @@ public: [[nodiscard]] CAmount GetWaste() const; /** Get m_selected_inputs */ - const std::set& GetInputSet() const; - /** Get the vector of CInputCoins that will be used to fill in a CTransaction's vin */ - std::vector GetShuffledInputVector() const; + const std::set& GetInputSet() const; + /** Get the vector of COutputs that will be used to fill in a CTransaction's vin */ + std::vector GetShuffledInputVector() const; bool operator<(SelectionResult other) const; }; diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index 356e2be80d..288282d3de 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -301,11 +301,10 @@ std::vector GroupOutputs(const CWallet& wallet, const std::vector GroupOutputs(const CWallet& wallet, const std::vector> spk_to_groups_map; for (const auto& output : outputs) { // Skip outputs we cannot spend @@ -327,8 +326,7 @@ std::vector GroupOutputs(const CWallet& wallet, const std::vector& groups = spk_to_groups_map[spk]; @@ -337,7 +335,7 @@ std::vector GroupOutputs(const CWallet& wallet, const std::vector GroupOutputs(const CWallet& wallet, const std::vectorInsert(input_coin, output.depth, output.from_me, ancestors, descendants, positive_only); + // Add the output to group + group->Insert(output, ancestors, descendants, positive_only); } // Now we go through the entire map and pull out the OutputGroups @@ -427,10 +425,10 @@ std::optional SelectCoins(const CWallet& wallet, const std::vec { for (const COutput& out : vCoins) { if (!out.spendable) 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. + /* Set ancestors and descendants to 0 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); + preset_inputs.Insert(out, /*ancestors=*/ 0, /*descendants=*/ 0, /*positive_only=*/ false); } SelectionResult result(nTargetValue); result.AddInput(preset_inputs); @@ -439,7 +437,7 @@ std::optional SelectCoins(const CWallet& wallet, const std::vec } // calculate value from preset inputs and store them - std::set setPresetCoins; + std::set preset_coins; std::vector vPresetInputs; coin_control.ListSelected(vPresetInputs); @@ -467,27 +465,29 @@ std::optional SelectCoins(const CWallet& wallet, const std::vec input_bytes = GetVirtualTransactionSize(coin_control.GetInputWeight(outpoint), 0, 0); } - CInputCoin coin(outpoint, txout, input_bytes); - if (coin.m_input_bytes == -1) { + if (input_bytes == -1) { 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); + + /* Set some defaults for depth, spendable, solvable, safe, time, and from_me as these don't matter for preset inputs since no selection is being done. */ + COutput output(outpoint, txout, /*depth=*/ 0, input_bytes, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false); + output.effective_value = output.txout.nValue - coin_selection_params.m_effective_feerate.GetFee(output.input_bytes); if (coin_selection_params.m_subtract_fee_outputs) { - value_to_select -= coin.txout.nValue; + value_to_select -= output.txout.nValue; } else { - value_to_select -= coin.effective_value; + value_to_select -= output.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. + preset_coins.insert(outpoint); + /* Set ancestors and descendants to 0 as they don't matter for preset inputs since 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); + preset_inputs.Insert(output, /*ancestors=*/ 0, /*descendants=*/ 0, /*positive_only=*/ false); } // remove preset inputs from vCoins so that Coin Selection doesn't pick them. for (std::vector::iterator it = vCoins.begin(); it != vCoins.end() && coin_control.HasSelected();) { - if (setPresetCoins.count(it->GetInputCoin())) + if (preset_coins.count(it->outpoint)) it = vCoins.erase(it); else ++it; @@ -802,7 +802,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 selected_coins = result->GetShuffledInputVector(); + std::vector selected_coins = result->GetShuffledInputVector(); // The sequence number is set to non-maxint so that DiscourageFeeSniping // works. diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index fb246a3377..bd5ed09ba4 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -28,20 +28,20 @@ BOOST_FIXTURE_TEST_SUITE(coinselector_tests, WalletTestingSetup) // we repeat those tests this many times and only complain if all iterations of the test fail #define RANDOM_REPEATS 5 -typedef std::set CoinSet; +typedef std::set 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& set) +static void add_coin(const CAmount& nValue, int nInput, std::vector& 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); + set.emplace_back(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ -1, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false); } static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result) @@ -50,9 +50,9 @@ static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result) tx.vout.resize(nInput + 1); tx.vout[nInput].nValue = nValue; tx.nLockTime = nextLockTime++; // so all transactions get different hashes - CInputCoin coin(MakeTransactionRef(tx), nInput); + COutput output(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ -1, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false); OutputGroup group; - group.Insert(coin, 1, false, 0, 0, true); + group.Insert(output, /*ancestors=*/ 0, /*descendants=*/ 0, /*positive_only=*/ true); result.AddInput(group); } @@ -62,10 +62,10 @@ static void add_coin(const CAmount& nValue, int nInput, CoinSet& set, CAmount fe tx.vout.resize(nInput + 1); tx.vout[nInput].nValue = nValue; tx.nLockTime = nextLockTime++; // so all transactions get different hashes - CInputCoin coin(MakeTransactionRef(tx), nInput); + COutput coin(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ -1, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false); coin.effective_value = nValue - fee; - coin.m_fee = fee; - coin.m_long_term_fee = long_term_fee; + coin.fee = fee; + coin.long_term_fee = long_term_fee; set.insert(coin); } @@ -117,7 +117,7 @@ static bool EqualResult(const SelectionResult& a, const SelectionResult& b) return ret.first == a.GetInputSet().end() && ret.second == b.GetInputSet().end(); } -static CAmount make_hard_case(int utxos, std::vector& utxo_pool) +static CAmount make_hard_case(int utxos, std::vector& utxo_pool) { utxo_pool.clear(); CAmount target = 0; @@ -129,24 +129,13 @@ static CAmount make_hard_case(int utxos, std::vector& utxo_pool) return target; } -inline std::vector& GroupCoins(const std::vector& coins) -{ - static std::vector static_groups; - static_groups.clear(); - for (auto& coin : coins) { - static_groups.emplace_back(); - static_groups.back().Insert(coin, 0, true, 0, 0, false); - } - return static_groups; -} - inline std::vector& GroupCoins(const std::vector& coins) { static std::vector static_groups; static_groups.clear(); for (auto& coin : coins) { static_groups.emplace_back(); - static_groups.back().Insert(coin.GetInputCoin(), coin.depth, coin.from_me, 0, 0, false); + static_groups.back().Insert(coin, /*ancestors=*/ 0, /*descendants=*/ 0, /*positive_only=*/ false); } return static_groups; } @@ -166,7 +155,7 @@ inline std::vector& KnapsackGroupOutputs(const std::vector BOOST_AUTO_TEST_CASE(bnb_search_test) { // Setup - std::vector utxo_pool; + std::vector utxo_pool; SelectionResult expected_result(CAmount(0)); ///////////////////////// -- cgit v1.2.3