From 1e52e6bd0a8888efb4ed247d74ec7ca9dfc2e002 Mon Sep 17 00:00:00 2001 From: glozow Date: Mon, 7 Mar 2022 13:45:06 +0000 Subject: refactor coin selection for parameterizable change target no behavior changes, since the target is always MIN_CHANGE --- src/wallet/coinselection.h | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) (limited to 'src/wallet/coinselection.h') diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index 504d57aa78..480c9664ca 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -94,6 +94,9 @@ struct CoinSelectionParams { size_t change_output_size = 0; /** Size of the input to spend a change output in virtual bytes. */ size_t change_spend_size = 0; + /** Mininmum change to target in Knapsack solver: select coins to cover the payment and + * at least this value of change. */ + CAmount m_min_change_target{MIN_CHANGE}; /** Cost of creating the change output. */ CAmount m_change_fee{0}; /** Cost of creating the change output + cost of spending the change output in the future. */ @@ -115,11 +118,13 @@ 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(FastRandomContext& rng_fast, size_t change_output_size, size_t change_spend_size, CFeeRate effective_feerate, + CoinSelectionParams(FastRandomContext& rng_fast, size_t change_output_size, size_t change_spend_size, + CAmount min_change_target, 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_min_change_target(min_change_target), m_effective_feerate(effective_feerate), m_long_term_feerate(long_term_feerate), m_discard_feerate(discard_feerate), @@ -267,7 +272,8 @@ std::optional SelectCoinsBnB(std::vector& utxo_poo std::optional SelectCoinsSRD(const std::vector& utxo_pool, CAmount target_value, FastRandomContext& rng); // Original coin selection algorithm as a fallback -std::optional KnapsackSolver(std::vector& groups, const CAmount& nTargetValue, FastRandomContext& rng); +std::optional KnapsackSolver(std::vector& groups, const CAmount& nTargetValue, + CAmount change_target, FastRandomContext& rng); } // namespace wallet #endif // BITCOIN_WALLET_COINSELECTION_H -- cgit v1.2.3 From a44236addd01cff4e4d751e0f379d399fbfc8eae Mon Sep 17 00:00:00 2001 From: glozow Date: Mon, 7 Mar 2022 13:46:49 +0000 Subject: [wallet] randomly generate change targets If the wallet always chooses 1 million sats as its change target, it is easier to fingerprint transactions created by the Core wallet. --- src/wallet/coinselection.h | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) (limited to 'src/wallet/coinselection.h') diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index 480c9664ca..1da9f86cb5 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -17,6 +17,14 @@ namespace wallet { static constexpr CAmount MIN_CHANGE{COIN / 100}; //! final minimum change amount after paying for fees static const CAmount MIN_FINAL_CHANGE = MIN_CHANGE/2; +//! lower bound for randomly-chosen target change amount +static constexpr CAmount CHANGE_LOWER{50000}; +//! upper bound for randomly-chosen target change amount +static constexpr CAmount CHANGE_UPPER{1000000}; +// Ensure that any randomly generated change targets are less than or equal to before. +// Otherwise, tests may fail if funds are not enough to cover change. +static_assert(CHANGE_UPPER <= MIN_CHANGE); +static_assert(CHANGE_LOWER <= MIN_FINAL_CHANGE); /** A UTXO under consideration for use in funding a new transaction. */ class COutput @@ -99,6 +107,8 @@ struct CoinSelectionParams { CAmount m_min_change_target{MIN_CHANGE}; /** Cost of creating the change output. */ CAmount m_change_fee{0}; + /** The pre-determined minimum value to target when funding a change output. */ + CAmount m_change_target{0}; /** Cost of creating the change output + cost of spending the change output in the future. */ CAmount m_cost_of_change{0}; /** The targeted feerate of the transaction being built. */ @@ -223,6 +233,21 @@ struct OutputGroup */ [[nodiscard]] CAmount GetSelectionWaste(const std::set& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true); + +/** Chooose a random change target for each transaction to make it harder to fingerprint the Core + * wallet based on the change output values of transactions it creates. + * The random value is between 50ksat and min(2 * payment_value, 1milsat) + * When payment_value <= 25ksat, the value is just 50ksat. + * + * Making change amounts similar to the payment value may help disguise which output(s) are payments + * are which ones are change. Using double the payment value may increase the number of inputs + * needed (and thus be more expensive in fees), but breaks analysis techniques which assume the + * coins selected are just sufficient to cover the payment amount ("unnecessary input" heuristic). + * + * @param[in] payment_value Average payment value of the transaction output(s). + */ +[[nodiscard]] CAmount GenerateChangeTarget(CAmount payment_value, FastRandomContext& rng); + struct SelectionResult { private: -- cgit v1.2.3 From 46f2fed6c5e0fa623bfeabf61ba4811d5cf8f47c Mon Sep 17 00:00:00 2001 From: glozow Date: Thu, 10 Mar 2022 10:38:31 +0000 Subject: [wallet] remove MIN_CHANGE --- src/wallet/coinselection.h | 10 +--------- 1 file changed, 1 insertion(+), 9 deletions(-) (limited to 'src/wallet/coinselection.h') diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h index 1da9f86cb5..2e20efa8c1 100644 --- a/src/wallet/coinselection.h +++ b/src/wallet/coinselection.h @@ -13,18 +13,10 @@ #include namespace wallet { -//! target minimum change amount -static constexpr CAmount MIN_CHANGE{COIN / 100}; -//! final minimum change amount after paying for fees -static const CAmount MIN_FINAL_CHANGE = MIN_CHANGE/2; //! lower bound for randomly-chosen target change amount static constexpr CAmount CHANGE_LOWER{50000}; //! upper bound for randomly-chosen target change amount static constexpr CAmount CHANGE_UPPER{1000000}; -// Ensure that any randomly generated change targets are less than or equal to before. -// Otherwise, tests may fail if funds are not enough to cover change. -static_assert(CHANGE_UPPER <= MIN_CHANGE); -static_assert(CHANGE_LOWER <= MIN_FINAL_CHANGE); /** A UTXO under consideration for use in funding a new transaction. */ class COutput @@ -104,7 +96,7 @@ struct CoinSelectionParams { size_t change_spend_size = 0; /** Mininmum change to target in Knapsack solver: select coins to cover the payment and * at least this value of change. */ - CAmount m_min_change_target{MIN_CHANGE}; + CAmount m_min_change_target{0}; /** Cost of creating the change output. */ CAmount m_change_fee{0}; /** The pre-determined minimum value to target when funding a change output. */ -- cgit v1.2.3