Merge bitcoin/bitcoin#25647: wallet: return change from SelectionResult

4fef5344288e454460b80db0316294e1ec1ad8ad wallet: use GetChange() when computing waste (S3RK)
87e0ef903133492e76b7c7556209554d4a0c3d66 wallet: use GetChange() in tx building (S3RK)
15e97a6886902ebb378829993a972dc52558aa92 wallet: add SelectionResult::GetChange (S3RK)
72cad28da05cfce9e4950f2dc5a709da41d251f4 wallet: calculate and store min_viable_change (S3RK)
e3210a722542a9cb5f7e4be72470dbe488c281fd wallet: account for preselected inputs in target (S3RK)
f8e796348b644c011ad9a8312356d4426c16cc4b wallet: add SelectionResult::Merge (S3RK)
06f558e4e2164d1916f258c731efe4586728a23b wallet: accurate SelectionResult::m_target (S3RK)
c8cf08ea743e430c2bf3fe46439594257b0937e5 wallet: ensure m_min_change_target always covers change fee (S3RK)

Pull request description:

  Benefits:
  1. more accurate waste calculation for knapsack. Waste calculation is now consistent with tx building code. Before we always assumed change for knapsack even when the solution is changeless4.
  2. simpler tx building code. Only create change output when it's needed
  3. makes it easier to correctly account for fees for CPFP inputs (should be done in a follow up)

  In the first three commits we fix the code to accurately track selection target in `SelectionResult::m_target`
  Then we introduce new variable `min_change` that represents the minimum viable change amount
  Then we introduce `SelectionResult::GetChange()` which incapsulates dropping change for fee logic and uses correct values of `SelectionResult::m_target`
  Then we use `SelectionResult::GetChange()` in both tx building and waste calculation code

  This PR is a refactoring and shouldn't change the behaviour.
  There is only one known small change (arguably a bug fix). Before we dropped change output if it's smaller than `cost_of_change` after paying change fees. This is incorrect as `cost_of_change` already includes `change_fee`.

ACKs for top commit:
  achow101:
    ACK 4fef5344288e454460b80db0316294e1ec1ad8ad
  Xekyo:
    crACK 4fef5344288e454460b80db0316294e1ec1ad8ad
  furszy:
    Code review ACK 4fef5344
  w0xlt:
    ACK https://github.com/bitcoin/bitcoin/pull/25647/commits/4fef5344288e454460b80db0316294e1ec1ad8ad

Tree-SHA512: 31a7455d4129bc39a444da0f16ad478d690d4d9627b2b8fdb5605facc6488171926bf02f5d7d9a545b2b59efafcf5bb3d404005e4da15c7b44b3f7d441afb941

2 files changed, 14 insertions, 7 deletions

diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index 4dfdc87a38..30a7fb9eb6 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -248,9 +248,9 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
 
     // Iteration exhaustion test
     CAmount target = make_hard_case(17, utxo_pool);
-    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), target, 0)); // Should exhaust
+    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), target, 1)); // Should exhaust
     target = make_hard_case(14, utxo_pool);
-    const auto result7 = SelectCoinsBnB(GroupCoins(utxo_pool), target, 0); // Should not exhaust
+    const auto result7 = SelectCoinsBnB(GroupCoins(utxo_pool), target, 1); // Should not exhaust
     BOOST_CHECK(result7);
 
     // Test same value early bailout optimization
@@ -289,8 +289,8 @@ 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{
         rand,
-        /*change_output_size=*/ 0,
-        /*change_spend_size=*/ 0,
+        /*change_output_size=*/ 31,
+        /*change_spend_size=*/ 68,
         /*min_change_target=*/ 0,
         /*effective_feerate=*/ CFeeRate(3000),
         /*long_term_feerate=*/ CFeeRate(1000),
@@ -298,6 +298,9 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
         /*tx_noinputs_size=*/ 0,
         /*avoid_partial=*/ false,
     };
+    coin_selection_params_bnb.m_change_fee = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_output_size);
+    coin_selection_params_bnb.m_cost_of_change = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_spend_size) + coin_selection_params_bnb.m_change_fee;
+    coin_selection_params_bnb.min_viable_change = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_spend_size);
     {
         std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), "", m_args, CreateMockWalletDatabase());
         wallet->LoadWallet();
@@ -777,6 +780,8 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test)
             /*tx_noinputs_size=*/ 0,
             /*avoid_partial=*/ false,
         };
+        cs_params.m_cost_of_change = 1;
+        cs_params.min_viable_change = 1;
         CCoinControl cc;
         const auto result = SelectCoins(*wallet, available_coins, target, cc, cs_params);
         BOOST_CHECK(result);
diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp
index 3465f2f331..90a328179e 100644
--- a/src/wallet/test/fuzz/coinselection.cpp
+++ b/src/wallet/test/fuzz/coinselection.cpp
@@ -58,6 +58,8 @@ FUZZ_TARGET(coinselection)
     coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
     coin_params.m_long_term_feerate = long_term_fee_rate;
     coin_params.m_effective_feerate = effective_fee_rate;
+    coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
+    coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
 
     // Create some coins
     CAmount total_balance{0};
@@ -83,11 +85,11 @@ FUZZ_TARGET(coinselection)
     const auto result_bnb = SelectCoinsBnB(group_pos, target, cost_of_change);
 
     auto result_srd = SelectCoinsSRD(group_pos, target, fast_random_context);
-    if (result_srd) result_srd->ComputeAndSetWaste(cost_of_change);
+    if (result_srd) result_srd->ComputeAndSetWaste(cost_of_change, cost_of_change, 0);
 
-    CAmount change_target{GenerateChangeTarget(target, fast_random_context)};
+    CAmount change_target{GenerateChangeTarget(target, coin_params.m_change_fee, fast_random_context)};
     auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context);
-    if (result_knapsack) result_knapsack->ComputeAndSetWaste(cost_of_change);
+    if (result_knapsack) result_knapsack->ComputeAndSetWaste(cost_of_change, cost_of_change, 0);
 
     // If the total balance is sufficient for the target and we are not using
     // effective values, Knapsack should always find a solution.