diff options
author | MarcoFalke <falke.marco@gmail.com> | 2022-03-14 15:22:42 +0100 |
---|---|---|
committer | MarcoFalke <falke.marco@gmail.com> | 2022-03-14 15:17:04 +0100 |
commit | fa7deaa0464576a229b5a6ab13ad033c16d0dada (patch) | |
tree | 9bd5ff8033873f76291b69b2d21dfc16c3fe8ccd /src | |
parent | 77773b061cb13229a8afb46f6f3ab89fc70eabe3 (diff) | |
download | bitcoin-fa7deaa0464576a229b5a6ab13ad033c16d0dada.tar.xz |
wallet: Pass FastRandomContext& to coin selection
Diffstat (limited to 'src')
-rw-r--r-- | src/bench/coin_selection.cpp | 15 | ||||
-rw-r--r-- | src/wallet/coinselection.cpp | 16 | ||||
-rw-r--r-- | src/wallet/coinselection.h | 34 | ||||
-rw-r--r-- | src/wallet/spend.cpp | 8 | ||||
-rw-r--r-- | src/wallet/test/coinselector_tests.cpp | 50 |
5 files changed, 78 insertions, 45 deletions
diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp index 609c592d20..a9f05f05ea 100644 --- a/src/bench/coin_selection.cpp +++ b/src/bench/coin_selection.cpp @@ -62,10 +62,17 @@ static void CoinSelection(benchmark::Bench& bench) } const CoinEligibilityFilter filter_standard(1, 6, 0); - const CoinSelectionParams coin_selection_params(/* change_output_size= */ 34, - /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0), - /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0), - /* tx_noinputs_size= */ 0, /* avoid_partial= */ false); + FastRandomContext rand{}; + const CoinSelectionParams coin_selection_params{ + rand, + /* change_output_size= */ 34, + /* change_spend_size= */ 148, + /* effective_feerate= */ CFeeRate(0), + /* long_term_feerate= */ CFeeRate(0), + /* discard_feerate= */ CFeeRate(0), + /* tx_noinputs_size= */ 0, + /* avoid_partial= */ false, + }; bench.run([&] { auto result = AttemptSelection(wallet, 1003 * COIN, filter_standard, coins, coin_selection_params); assert(result); diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 513572da45..928d25b02c 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -169,14 +169,14 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo return result; } -std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value) +std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng) { SelectionResult result(target_value); std::vector<size_t> indexes; indexes.resize(utxo_pool.size()); std::iota(indexes.begin(), indexes.end(), 0); - Shuffle(indexes.begin(), indexes.end(), FastRandomContext()); + Shuffle(indexes.begin(), indexes.end(), rng); CAmount selected_eff_value = 0; for (const size_t i : indexes) { @@ -191,7 +191,7 @@ std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& ut return std::nullopt; } -static void ApproximateBestSubset(const std::vector<OutputGroup>& groups, const CAmount& nTotalLower, const CAmount& nTargetValue, +static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::vector<OutputGroup>& groups, const CAmount& nTotalLower, const CAmount& nTargetValue, std::vector<char>& vfBest, CAmount& nBest, int iterations = 1000) { std::vector<char> vfIncluded; @@ -199,8 +199,6 @@ static void ApproximateBestSubset(const std::vector<OutputGroup>& groups, const vfBest.assign(groups.size(), true); nBest = nTotalLower; - FastRandomContext insecure_rand; - for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++) { vfIncluded.assign(groups.size(), false); @@ -237,7 +235,7 @@ static void ApproximateBestSubset(const std::vector<OutputGroup>& groups, const } } -std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue) +std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue, FastRandomContext& rng) { SelectionResult result(nTargetValue); @@ -246,7 +244,7 @@ std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, std::vector<OutputGroup> applicable_groups; CAmount nTotalLower = 0; - Shuffle(groups.begin(), groups.end(), FastRandomContext()); + Shuffle(groups.begin(), groups.end(), rng); for (const OutputGroup& group : groups) { if (group.GetSelectionAmount() == nTargetValue) { @@ -278,9 +276,9 @@ std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, std::vector<char> vfBest; CAmount nBest; - ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue, vfBest, nBest); + ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue, vfBest, nBest); if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE) { - ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest); + ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest); } // If we have a bigger coin and (either the stochastic approximation didn't find a good solution, diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index 496a026999..a0941d32df 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -73,8 +73,9 @@ public: }; /** Parameters for one iteration of Coin Selection. */ -struct CoinSelectionParams -{ +struct CoinSelectionParams { + /** Randomness to use in the context of coin selection. */ + FastRandomContext& rng_fast; /** Size of a change output in bytes, determined by the output type. */ size_t change_output_size = 0; /** Size of the input to spend a change output in virtual bytes. */ @@ -100,17 +101,20 @@ struct CoinSelectionParams * reuse. Dust outputs are not eligible to be added to output groups and thus not considered. */ bool m_avoid_partial_spends = false; - CoinSelectionParams(size_t change_output_size, size_t change_spend_size, CFeeRate effective_feerate, - CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial) : - change_output_size(change_output_size), - change_spend_size(change_spend_size), - m_effective_feerate(effective_feerate), - m_long_term_feerate(long_term_feerate), - m_discard_feerate(discard_feerate), - tx_noinputs_size(tx_noinputs_size), - m_avoid_partial_spends(avoid_partial) - {} - CoinSelectionParams() {} + CoinSelectionParams(FastRandomContext& rng_fast, size_t change_output_size, size_t change_spend_size, CFeeRate effective_feerate, + CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial) + : rng_fast{rng_fast}, + change_output_size(change_output_size), + change_spend_size(change_spend_size), + m_effective_feerate(effective_feerate), + m_long_term_feerate(long_term_feerate), + m_discard_feerate(discard_feerate), + tx_noinputs_size(tx_noinputs_size), + m_avoid_partial_spends(avoid_partial) + { + } + CoinSelectionParams(FastRandomContext& rng_fast) + : rng_fast{rng_fast} {} }; /** Parameters for filtering which OutputGroups we may use in coin selection. @@ -246,10 +250,10 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo * @param[in] target_value The target value to select for * @returns If successful, a SelectionResult, otherwise, std::nullopt */ -std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value); +std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng); // Original coin selection algorithm as a fallback -std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue); +std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue, FastRandomContext& rng); } // namespace wallet #endif // BITCOIN_WALLET_COINSELECTION_H diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp index 9b1e7c0d22..931baeac90 100644 --- a/src/wallet/spend.cpp +++ b/src/wallet/spend.cpp @@ -386,7 +386,7 @@ std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAm 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. - if (auto knapsack_result{KnapsackSolver(all_groups, nTargetValue + coin_selection_params.m_change_fee)}) { + if (auto knapsack_result{KnapsackSolver(all_groups, nTargetValue + coin_selection_params.m_change_fee, coin_selection_params.rng_fast)}) { knapsack_result->ComputeAndSetWaste(coin_selection_params.m_cost_of_change); results.push_back(*knapsack_result); } @@ -394,7 +394,7 @@ std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAm // 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; - if (auto srd_result{SelectCoinsSRD(positive_groups, srd_target)}) { + if (auto srd_result{SelectCoinsSRD(positive_groups, srd_target, coin_selection_params.rng_fast)}) { srd_result->ComputeAndSetWaste(coin_selection_params.m_cost_of_change); results.push_back(*srd_result); } @@ -501,7 +501,7 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, const std::vec // Cases where we have 101+ outputs all pointing to the same destination may result in // privacy leaks as they will potentially be deterministically sorted. We solve that by // explicitly shuffling the outputs before processing - Shuffle(vCoins.begin(), vCoins.end(), FastRandomContext()); + Shuffle(vCoins.begin(), vCoins.end(), coin_selection_params.rng_fast); } // Coin Selection attempts to select inputs from a pool of eligible UTXOs to fund the @@ -657,7 +657,7 @@ static bool CreateTransactionInternal( FastRandomContext rng_fast; CMutableTransaction txNew; // The resulting transaction that we make - CoinSelectionParams coin_selection_params; // Parameters for coin selection, init with dummy + CoinSelectionParams coin_selection_params{rng_fast}; // Parameters for coin selection, init with dummy coin_selection_params.m_avoid_partial_spends = coin_control.m_avoid_partial_spends; // Set the long term feerate estimate to the wallet's consolidate feerate diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp index b9f12158ca..f0c799b43e 100644 --- a/src/wallet/test/coinselector_tests.cpp +++ b/src/wallet/test/coinselector_tests.cpp @@ -164,10 +164,17 @@ inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& coins) inline std::vector<OutputGroup>& KnapsackGroupOutputs(const std::vector<COutput>& coins, CWallet& wallet, const CoinEligibilityFilter& filter) { - CoinSelectionParams coin_selection_params(/* change_output_size= */ 0, - /* change_spend_size= */ 0, /* effective_feerate= */ CFeeRate(0), - /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0), - /* tx_noinputs_size= */ 0, /* avoid_partial= */ false); + FastRandomContext rand{}; + CoinSelectionParams coin_selection_params{ + rand, + /* change_output_size= */ 0, + /* change_spend_size= */ 0, + /* effective_feerate= */ CFeeRate(0), + /* long_term_feerate= */ CFeeRate(0), + /* discard_feerate= */ CFeeRate(0), + /* tx_noinputs_size= */ 0, + /* avoid_partial= */ false, + }; static std::vector<OutputGroup> static_groups; static_groups = GroupOutputs(wallet, coins, coin_selection_params, filter, /*positive_only=*/false); return static_groups; @@ -176,6 +183,7 @@ inline std::vector<OutputGroup>& KnapsackGroupOutputs(const std::vector<COutput> // Branch and bound coin selection tests BOOST_AUTO_TEST_CASE(bnb_search_test) { + FastRandomContext rand{}; // Setup std::vector<CInputCoin> utxo_pool; SelectionResult expected_result(CAmount(0)); @@ -301,10 +309,16 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) } // Make sure that effective value is working in AttemptSelection when BnB is used - CoinSelectionParams coin_selection_params_bnb(/* change_output_size= */ 0, - /* change_spend_size= */ 0, /* effective_feerate= */ CFeeRate(3000), - /* long_term_feerate= */ CFeeRate(1000), /* discard_feerate= */ CFeeRate(1000), - /* tx_noinputs_size= */ 0, /* avoid_partial= */ false); + CoinSelectionParams coin_selection_params_bnb{ + rand, + /* change_output_size= */ 0, + /* change_spend_size= */ 0, + /* effective_feerate= */ CFeeRate(3000), + /* long_term_feerate= */ CFeeRate(1000), + /* discard_feerate= */ CFeeRate(1000), + /* tx_noinputs_size= */ 0, + /* avoid_partial= */ false, + }; { std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), "", m_args, CreateMockWalletDatabase()); wallet->LoadWallet(); @@ -351,6 +365,9 @@ BOOST_AUTO_TEST_CASE(bnb_search_test) BOOST_AUTO_TEST_CASE(knapsack_solver_test) { + FastRandomContext rand{}; + const auto temp1{[&rand](std::vector<OutputGroup>& g, const CAmount& v) { return KnapsackSolver(g, v, rand); }}; + const auto KnapsackSolver{temp1}; std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), "", m_args, CreateMockWalletDatabase()); wallet->LoadWallet(); LOCK(wallet->cs_wallet); @@ -660,6 +677,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test) BOOST_AUTO_TEST_CASE(ApproximateBestSubset) { + FastRandomContext rand{}; std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), "", m_args, CreateMockWalletDatabase()); wallet->LoadWallet(); LOCK(wallet->cs_wallet); @@ -673,7 +691,7 @@ BOOST_AUTO_TEST_CASE(ApproximateBestSubset) add_coin(coins, *wallet, 1000 * COIN); add_coin(coins, *wallet, 3 * COIN); - const auto result = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1003 * COIN); + const auto result = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1003 * COIN, rand); BOOST_CHECK(result); BOOST_CHECK_EQUAL(result->GetSelectedValue(), 1003 * COIN); BOOST_CHECK_EQUAL(result->GetInputSet().size(), 2U); @@ -714,10 +732,16 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test) CAmount target = rand.randrange(balance - 1000) + 1000; // Perform selection - CoinSelectionParams cs_params(/* change_output_size= */ 34, - /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0), - /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0), - /* tx_noinputs_size= */ 0, /* avoid_partial= */ false); + CoinSelectionParams cs_params{ + rand, + /* change_output_size= */ 34, + /* change_spend_size= */ 148, + /* effective_feerate= */ CFeeRate(0), + /* long_term_feerate= */ CFeeRate(0), + /* discard_feerate= */ CFeeRate(0), + /* tx_noinputs_size= */ 0, + /* avoid_partial= */ false, + }; CCoinControl cc; const auto result = SelectCoins(*wallet, coins, target, cc, cs_params); BOOST_CHECK(result); |