aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/wallet/coinselection.cpp10
-rw-r--r--src/wallet/coinselection.h36
-rw-r--r--src/wallet/test/coinselector_tests.cpp213
3 files changed, 143 insertions, 116 deletions
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index d6b9b68e1f..63a5866a8e 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -449,15 +449,15 @@ void OutputGroupTypeMap::Push(const OutputGroup& group, OutputType type, bool in
}
}
-CAmount GetSelectionWaste(const std::set<std::shared_ptr<COutput>>& inputs, CAmount change_cost, CAmount target, bool use_effective_value)
+CAmount SelectionResult::GetSelectionWaste(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());
+ assert(!m_selected_inputs.empty());
// Always consider the cost of spending an input now vs in the future.
CAmount waste = 0;
CAmount selected_effective_value = 0;
- for (const auto& coin_ptr : inputs) {
+ for (const auto& coin_ptr : m_selected_inputs) {
const COutput& coin = *coin_ptr;
waste += coin.GetFee() - coin.long_term_fee;
selected_effective_value += use_effective_value ? coin.GetEffectiveValue() : coin.txout.nValue;
@@ -493,9 +493,9 @@ void SelectionResult::ComputeAndSetWaste(const CAmount min_viable_change, const
const CAmount change = GetChange(min_viable_change, change_fee);
if (change > 0) {
- m_waste = GetSelectionWaste(m_selected_inputs, change_cost, m_target, m_use_effective);
+ m_waste = GetSelectionWaste(change_cost, m_target, m_use_effective);
} else {
- m_waste = GetSelectionWaste(m_selected_inputs, 0, m_target, m_use_effective);
+ m_waste = GetSelectionWaste(0, m_target, m_use_effective);
}
}
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index afd868fc89..fd75ad67a0 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -275,26 +275,6 @@ struct OutputGroupTypeMap
typedef std::map<CoinEligibilityFilter, OutputGroupTypeMap> FilteredOutputGroups;
-/** Compute the waste for this result given the cost of change
- * and the opportunity cost of spending these inputs now vs in the future.
- * If change exists, waste = change_cost + inputs * (effective_feerate - long_term_feerate)
- * If no change, waste = excess + inputs * (effective_feerate - long_term_feerate)
- * where excess = selected_effective_value - target
- * change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size
- *
- * Note this function is separate from SelectionResult for the tests.
- *
- * @param[in] inputs The selected inputs
- * @param[in] change_cost The cost of creating change and spending it in the future.
- * Only used if there is change, in which case it must be positive.
- * Must be 0 if there is no change.
- * @param[in] target The amount targeted by the coin selection algorithm.
- * @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<std::shared_ptr<COutput>>& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true);
-
-
/** Choose 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.
* Change target covers at least change fees and adds a random value on top of it.
@@ -348,6 +328,22 @@ private:
}
}
+ /** Compute the waste for this result given the cost of change
+ * and the opportunity cost of spending these inputs now vs in the future.
+ * If change exists, waste = change_cost + inputs * (effective_feerate - long_term_feerate)
+ * If no change, waste = excess + inputs * (effective_feerate - long_term_feerate)
+ * where excess = selected_effective_value - target
+ * change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size
+ *
+ * @param[in] change_cost The cost of creating change and spending it in the future.
+ * Only used if there is change, in which case it must be positive.
+ * Must be 0 if there is no change.
+ * @param[in] target The amount targeted by the coin selection algorithm.
+ * @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(CAmount change_cost, CAmount target, bool use_effective_value = true);
+
public:
explicit SelectionResult(const CAmount target, SelectionAlgorithm algo)
: m_target(target), m_algo(algo) {}
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index c8283f453a..3964e9adde 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -58,15 +58,17 @@ static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result)
result.AddInput(group);
}
-static void add_coin(const CAmount& nValue, int nInput, CoinSet& set, CAmount fee = 0, CAmount long_term_fee = 0)
+static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result, CAmount fee, CAmount long_term_fee)
{
CMutableTransaction tx;
tx.vout.resize(nInput + 1);
tx.vout[nInput].nValue = nValue;
tx.nLockTime = nextLockTime++; // so all transactions get different hashes
- COutput coin(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ 148, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, fee);
- coin.long_term_fee = long_term_fee;
- set.insert(std::make_shared<COutput>(coin));
+ std::shared_ptr<COutput> coin = std::make_shared<COutput>(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ 148, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, fee);
+ OutputGroup group;
+ group.Insert(coin, /*ancestors=*/ 0, /*descendants=*/ 0);
+ coin->long_term_fee = long_term_fee; // group.Insert() will modify long_term_fee, so we need to set it afterwards
+ result.AddInput(group);
}
static void add_coin(CoinsResult& available_coins, CWallet& wallet, const CAmount& nValue, CFeeRate feerate = CFeeRate(0), int nAge = 6*24, bool fIsFromMe = false, int nInput =0, bool spendable = false, int custom_size = 0)
@@ -827,7 +829,6 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test)
BOOST_AUTO_TEST_CASE(waste_test)
{
- CoinSet selection;
const CAmount fee{100};
const CAmount change_cost{125};
const CAmount fee_diff{40};
@@ -835,92 +836,122 @@ BOOST_AUTO_TEST_CASE(waste_test)
const CAmount target{2 * COIN};
const CAmount excess{in_amt - fee * 2 - target};
- // Waste with change is the change cost and difference between fee and long term fee
- add_coin(1 * COIN, 1, selection, fee, fee - fee_diff);
- add_coin(2 * COIN, 2, selection, fee, fee - fee_diff);
- const CAmount waste1 = GetSelectionWaste(selection, change_cost, target);
- BOOST_CHECK_EQUAL(fee_diff * 2 + change_cost, waste1);
- selection.clear();
-
- // Waste without change is the excess and difference between fee and long term fee
- add_coin(1 * COIN, 1, selection, fee, fee - fee_diff);
- add_coin(2 * COIN, 2, selection, fee, fee - fee_diff);
- const CAmount waste_nochange1 = GetSelectionWaste(selection, 0, target);
- BOOST_CHECK_EQUAL(fee_diff * 2 + excess, waste_nochange1);
- selection.clear();
-
- // Waste with change and fee == long term fee is just cost of change
- add_coin(1 * COIN, 1, selection, fee, fee);
- add_coin(2 * COIN, 2, selection, fee, fee);
- BOOST_CHECK_EQUAL(change_cost, GetSelectionWaste(selection, change_cost, target));
- selection.clear();
-
- // Waste without change and fee == long term fee is just the excess
- add_coin(1 * COIN, 1, selection, fee, fee);
- add_coin(2 * COIN, 2, selection, fee, fee);
- BOOST_CHECK_EQUAL(excess, GetSelectionWaste(selection, 0, target));
- selection.clear();
-
- // Waste will be greater when fee is greater, but long term fee is the same
- add_coin(1 * COIN, 1, selection, fee * 2, fee - fee_diff);
- add_coin(2 * COIN, 2, selection, fee * 2, fee - fee_diff);
- const CAmount waste2 = GetSelectionWaste(selection, change_cost, target);
- BOOST_CHECK_GT(waste2, waste1);
- selection.clear();
-
- // Waste with change is the change cost and difference between fee and long term fee
- // With long term fee greater than fee, waste should be less than when long term fee is less than fee
- add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
- add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
- const CAmount waste3 = GetSelectionWaste(selection, change_cost, target);
- BOOST_CHECK_EQUAL(fee_diff * -2 + change_cost, waste3);
- BOOST_CHECK_LT(waste3, waste1);
- selection.clear();
-
- // Waste without change is the excess and difference between fee and long term fee
- // With long term fee greater than fee, waste should be less than when long term fee is less than fee
- add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
- add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
- const CAmount waste_nochange2 = GetSelectionWaste(selection, 0, target);
- BOOST_CHECK_EQUAL(fee_diff * -2 + excess, waste_nochange2);
- BOOST_CHECK_LT(waste_nochange2, waste_nochange1);
- selection.clear();
-
- // No Waste when fee == long_term_fee, no change, and no excess
- add_coin(1 * COIN, 1, selection, fee, fee);
- add_coin(2 * COIN, 2, selection, fee, fee);
- const CAmount exact_target{in_amt - fee * 2};
- BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, /*change_cost=*/0, exact_target));
- selection.clear();
-
- // No Waste when (fee - long_term_fee) == (-cost_of_change), and no excess
- const CAmount new_change_cost{fee_diff * 2};
- add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
- add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
- BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, new_change_cost, target));
- selection.clear();
-
- // No Waste when (fee - long_term_fee) == (-excess), no change cost
- const CAmount new_target{in_amt - fee * 2 - fee_diff * 2};
- add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
- add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
- BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, /*change_cost=*/ 0, new_target));
- selection.clear();
-
- // Negative waste when the long term fee is greater than the current fee and the selected value == target
- const CAmount exact_target1{3 * COIN - 2 * fee};
- const CAmount target_waste1{-2 * fee_diff}; // = (2 * fee) - (2 * (fee + fee_diff))
- add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
- add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
- BOOST_CHECK_EQUAL(target_waste1, GetSelectionWaste(selection, /*change_cost=*/ 0, exact_target1));
- selection.clear();
-
- // Negative waste when the long term fee is greater than the current fee and change_cost < - (inputs * (fee - long_term_fee))
- const CAmount large_fee_diff{90};
- const CAmount target_waste2{-2 * large_fee_diff + change_cost}; // = (2 * fee) - (2 * (fee + large_fee_diff)) + change_cost
- add_coin(1 * COIN, 1, selection, fee, fee + large_fee_diff);
- add_coin(2 * COIN, 2, selection, fee, fee + large_fee_diff);
- BOOST_CHECK_EQUAL(target_waste2, GetSelectionWaste(selection, change_cost, target));
+ // The following tests that the waste is calculated correctly in various scenarios.
+ // ComputeAndSetWaste will first determine the size of the change output. We don't really
+ // care about the change and just want to use the variant that always includes the change_cost,
+ // so min_viable_change and change_fee are set to 0 to ensure that.
+ {
+ // Waste with change is the change cost and difference between fee and long term fee
+ SelectionResult selection1{target, SelectionAlgorithm::MANUAL};
+ add_coin(1 * COIN, 1, selection1, fee, fee - fee_diff);
+ add_coin(2 * COIN, 2, selection1, fee, fee - fee_diff);
+ selection1.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0);
+ BOOST_CHECK_EQUAL(fee_diff * 2 + change_cost, selection1.GetWaste());
+
+ // Waste will be greater when fee is greater, but long term fee is the same
+ SelectionResult selection2{target, SelectionAlgorithm::MANUAL};
+ add_coin(1 * COIN, 1, selection2, fee * 2, fee - fee_diff);
+ add_coin(2 * COIN, 2, selection2, fee * 2, fee - fee_diff);
+ selection2.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0);
+ BOOST_CHECK_GT(selection2.GetWaste(), selection1.GetWaste());
+
+ // Waste with change is the change cost and difference between fee and long term fee
+ // With long term fee greater than fee, waste should be less than when long term fee is less than fee
+ SelectionResult selection3{target, SelectionAlgorithm::MANUAL};
+ add_coin(1 * COIN, 1, selection3, fee, fee + fee_diff);
+ add_coin(2 * COIN, 2, selection3, fee, fee + fee_diff);
+ selection3.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0);
+ BOOST_CHECK_EQUAL(fee_diff * -2 + change_cost, selection3.GetWaste());
+ BOOST_CHECK_LT(selection3.GetWaste(), selection1.GetWaste());
+ }
+
+ {
+ // Waste without change is the excess and difference between fee and long term fee
+ SelectionResult selection_nochange1{target, SelectionAlgorithm::MANUAL};
+ add_coin(1 * COIN, 1, selection_nochange1, fee, fee - fee_diff);
+ add_coin(2 * COIN, 2, selection_nochange1, fee, fee - fee_diff);
+ selection_nochange1.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0);
+ BOOST_CHECK_EQUAL(fee_diff * 2 + excess, selection_nochange1.GetWaste());
+
+ // Waste without change is the excess and difference between fee and long term fee
+ // With long term fee greater than fee, waste should be less than when long term fee is less than fee
+ SelectionResult selection_nochange2{target, SelectionAlgorithm::MANUAL};
+ add_coin(1 * COIN, 1, selection_nochange2, fee, fee + fee_diff);
+ add_coin(2 * COIN, 2, selection_nochange2, fee, fee + fee_diff);
+ selection_nochange2.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0);
+ BOOST_CHECK_EQUAL(fee_diff * -2 + excess, selection_nochange2.GetWaste());
+ BOOST_CHECK_LT(selection_nochange2.GetWaste(), selection_nochange1.GetWaste());
+ }
+
+ {
+ // Waste with change and fee == long term fee is just cost of change
+ SelectionResult selection{target, SelectionAlgorithm::MANUAL};
+ add_coin(1 * COIN, 1, selection, fee, fee);
+ add_coin(2 * COIN, 2, selection, fee, fee);
+ selection.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0);
+ BOOST_CHECK_EQUAL(change_cost, selection.GetWaste());
+ }
+
+ {
+ // Waste without change and fee == long term fee is just the excess
+ SelectionResult selection{target, SelectionAlgorithm::MANUAL};
+ add_coin(1 * COIN, 1, selection, fee, fee);
+ add_coin(2 * COIN, 2, selection, fee, fee);
+ selection.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0);
+ BOOST_CHECK_EQUAL(excess, selection.GetWaste());
+ }
+
+ {
+ // No Waste when fee == long_term_fee, no change, and no excess
+ const CAmount exact_target{in_amt - fee * 2};
+ SelectionResult selection{exact_target, SelectionAlgorithm::MANUAL};
+ add_coin(1 * COIN, 1, selection, fee, fee);
+ add_coin(2 * COIN, 2, selection, fee, fee);
+ selection.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0);
+ BOOST_CHECK_EQUAL(0, selection.GetWaste());
+ }
+
+ {
+ // No Waste when (fee - long_term_fee) == (-cost_of_change), and no excess
+ SelectionResult selection{target, SelectionAlgorithm::MANUAL};
+ const CAmount new_change_cost{fee_diff * 2};
+ add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
+ add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
+ selection.ComputeAndSetWaste(/*min_viable_change=*/0, new_change_cost, /*change_fee=*/0);
+ BOOST_CHECK_EQUAL(0, selection.GetWaste());
+ }
+
+ {
+ // No Waste when (fee - long_term_fee) == (-excess), no change cost
+ const CAmount new_target{in_amt - fee * 2 - fee_diff * 2};
+ SelectionResult selection{new_target, SelectionAlgorithm::MANUAL};
+ add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
+ add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
+ selection.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0);
+ BOOST_CHECK_EQUAL(0, selection.GetWaste());
+ }
+
+ {
+ // Negative waste when the long term fee is greater than the current fee and the selected value == target
+ const CAmount exact_target{3 * COIN - 2 * fee};
+ SelectionResult selection{exact_target, SelectionAlgorithm::MANUAL};
+ const CAmount target_waste1{-2 * fee_diff}; // = (2 * fee) - (2 * (fee + fee_diff))
+ add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
+ add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
+ selection.ComputeAndSetWaste(/*min_viable_change=*/0, /*change_cost=*/0, /*change_fee=*/0);
+ BOOST_CHECK_EQUAL(target_waste1, selection.GetWaste());
+ }
+
+ {
+ // Negative waste when the long term fee is greater than the current fee and change_cost < - (inputs * (fee - long_term_fee))
+ SelectionResult selection{target, SelectionAlgorithm::MANUAL};
+ const CAmount large_fee_diff{90};
+ const CAmount target_waste2{-2 * large_fee_diff + change_cost}; // = (2 * fee) - (2 * (fee + large_fee_diff)) + change_cost
+ add_coin(1 * COIN, 1, selection, fee, fee + large_fee_diff);
+ add_coin(2 * COIN, 2, selection, fee, fee + large_fee_diff);
+ selection.ComputeAndSetWaste(/*min_viable_change=*/0, change_cost, /*change_fee=*/0);
+ BOOST_CHECK_EQUAL(target_waste2, selection.GetWaste());
+ }
}
BOOST_AUTO_TEST_CASE(effective_value_test)
generated by cgit v1.2.3 (git 2.26.2) at 2024-07-16 21:20:06 +0000