diff options
author | Andrew Chow <achow101-github@achow101.com> | 2022-03-23 13:41:16 -0400 |
---|---|---|
committer | Andrew Chow <achow101-github@achow101.com> | 2022-03-23 13:50:57 -0400 |
commit | 3ab96f2945cccea7278df10dba4e18fa0aca7780 (patch) | |
tree | b6d1eeb27db8cdc4dfd70b5b105d506db525056d /src/wallet | |
parent | f9ed0aec1bd49f2d01e15519788497723c1a4eaa (diff) | |
parent | fa7deaa0464576a229b5a6ab13ad033c16d0dada (diff) | |
download | bitcoin-3ab96f2945cccea7278df10dba4e18fa0aca7780.tar.xz |
Merge bitcoin/bitcoin#24560: wallet: Use single FastRandomContext when creating a wallet tx
fa7deaa0464576a229b5a6ab13ad033c16d0dada wallet: Pass FastRandomContext& to coin selection (MarcoFalke)
77773b061cb13229a8afb46f6f3ab89fc70eabe3 wallet: Pass FastRandomContext& to DiscourageFeeSniping (MarcoFalke)
Pull request description:
Passing around a single randomness context shouldn't come with any downsides, but documents better where randomness is used and allows the unit test to be deterministic, if they wish to be so.
ACKs for top commit:
achow101:
ACK fa7deaa0464576a229b5a6ab13ad033c16d0dada
promag:
Code review ACK fa7deaa0464576a229b5a6ab13ad033c16d0dada.
glozow:
light code review ACK fa7deaa0464576a229b5a6ab13ad033c16d0dada
Tree-SHA512: c16287708cc82ce58311710595d0127af42fb156c93fbcaa5bde634ce323d325f4d8c99a74af24423ab22b5ad58163dd771e8b1a0e7d6bff39c9fb2a1cb21bc7
Diffstat (limited to 'src/wallet')
-rw-r--r-- | src/wallet/coinselection.cpp | 16 | ||||
-rw-r--r-- | src/wallet/coinselection.h | 34 | ||||
-rw-r--r-- | src/wallet/spend.cpp | 23 | ||||
-rw-r--r-- | src/wallet/test/coinselector_tests.cpp | 50 |
4 files changed, 75 insertions, 48 deletions
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp index 20891a3e28..2df66ac15b 100644 --- a/src/wallet/coinselection.cpp +++ b/src/wallet/coinselection.cpp @@ -165,14 +165,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) { @@ -187,7 +187,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; @@ -195,8 +195,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); @@ -233,7 +231,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); @@ -242,7 +240,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) { @@ -274,9 +272,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 a707ef89d2..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 @@ -585,7 +585,8 @@ static bool IsCurrentForAntiFeeSniping(interfaces::Chain& chain, const uint256& * Set a height-based locktime for new transactions (uses the height of the * current chain tip unless we are not synced with the current chain */ -static void DiscourageFeeSniping(CMutableTransaction& tx, interfaces::Chain& chain, const uint256& block_hash, int block_height) +static void DiscourageFeeSniping(CMutableTransaction& tx, FastRandomContext& rng_fast, + interfaces::Chain& chain, const uint256& block_hash, int block_height) { // All inputs must be added by now assert(!tx.vin.empty()); @@ -616,8 +617,8 @@ static void DiscourageFeeSniping(CMutableTransaction& tx, interfaces::Chain& cha // that transactions that are delayed after signing for whatever reason, // e.g. high-latency mix networks and some CoinJoin implementations, have // better privacy. - if (GetRandInt(10) == 0) { - tx.nLockTime = std::max(0, int(tx.nLockTime) - GetRandInt(100)); + if (rng_fast.randrange(10) == 0) { + tx.nLockTime = std::max(0, int(tx.nLockTime) - int(rng_fast.randrange(100))); } } else { // If our chain is lagging behind, we can't discourage fee sniping nor help @@ -653,9 +654,10 @@ static bool CreateTransactionInternal( { AssertLockHeld(wallet.cs_wallet); + 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 @@ -782,10 +784,9 @@ static bool CreateTransactionInternal( assert(change_and_fee >= 0); CTxOut newTxOut(change_and_fee, scriptChange); - if (nChangePosInOut == -1) - { + if (nChangePosInOut == -1) { // Insert change txn at random position: - nChangePosInOut = GetRandInt(txNew.vout.size()+1); + nChangePosInOut = rng_fast.randrange(txNew.vout.size() + 1); } else if ((unsigned int)nChangePosInOut > txNew.vout.size()) { @@ -811,7 +812,7 @@ static bool CreateTransactionInternal( for (const auto& coin : selected_coins) { txNew.vin.push_back(CTxIn(coin.outpoint, CScript(), nSequence)); } - DiscourageFeeSniping(txNew, wallet.chain(), wallet.GetLastBlockHash(), wallet.GetLastBlockHeight()); + DiscourageFeeSniping(txNew, rng_fast, wallet.chain(), wallet.GetLastBlockHash(), wallet.GetLastBlockHeight()); // Calculate the transaction fee TxSize tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), &wallet, &coin_control); 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); |