Merge bitcoin/bitcoin#25729: wallet: Check max transaction weight in CoinSelection

c7c7ee9d0b2d7b303b9300f941e37e09e7d8d8b6 test: Check max transaction weight in CoinSelection (Aurèle Oulès)
6b563cae92957dc30dc35103a7c321fdb0115ef3 wallet: Check max tx weight in coin selector (Aurèle Oulès)

Pull request description:

  This PR is an attempt to fix #5782.

  I have added 4 test scenarios, 3 of them provided here https://github.com/bitcoin/bitcoin/issues/5782#issuecomment-73819058 (slightly modified to use a segwit wallet).

  Here are my benchmarks :
  ## PR
  |               ns/op |                op/s |    err% |          ins/op |          cyc/op |    IPC |         bra/op |   miss% |     total | benchmark
  |--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
  |        1,466,341.00 |              681.97 |    0.6% |   11,176,762.00 |    3,358,752.00 |  3.328 |   1,897,839.00 |    0.3% |      0.02 | `CoinSelection`

  ## Master

  |               ns/op |                op/s |    err% |          ins/op |          cyc/op |    IPC |         bra/op |   miss% |     total | benchmark
  |--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
  |        1,526,029.00 |              655.30 |    0.5% |   11,142,188.00 |    3,499,200.00 |  3.184 |   1,994,156.00 |    0.2% |      0.02 | `CoinSelection`

ACKs for top commit:
  achow101:
    reACK c7c7ee9d0b2d7b303b9300f941e37e09e7d8d8b6
  w0xlt:
    ACK https://github.com/bitcoin/bitcoin/pull/25729/commits/c7c7ee9d0b2d7b303b9300f941e37e09e7d8d8b6
  furszy:
    diff ACK c7c7ee9d

Tree-SHA512: ef0b28576ff845174651ba494aa9adee234c96e6f886d0e032eceb7050296e45b099dda0039d1dfb9944469f067627b2101f3ff855c70353cf39d1fc7ee81828

1 files changed, 119 insertions, 0 deletions

diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index c764264cd7..ce875d5442 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -4,6 +4,7 @@
 
 #include <consensus/amount.h>
 #include <node/context.h>
+#include <policy/policy.h>
 #include <primitives/transaction.h>
 #include <random.h>
 #include <test/util/setup_common.h>
@@ -930,6 +931,124 @@ BOOST_AUTO_TEST_CASE(effective_value_test)
     BOOST_CHECK_EQUAL(output5.GetEffectiveValue(), nValue); // The effective value should be equal to the absolute value if input_bytes is -1
 }
 
+static std::optional<SelectionResult> select_coins(const CAmount& target, const CoinSelectionParams& cs_params, const CCoinControl& cc, std::function<CoinsResult(CWallet&)> coin_setup, interfaces::Chain* chain, const ArgsManager& args)
+{
+    std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(chain, "", args, CreateMockWalletDatabase());
+    wallet->LoadWallet();
+    LOCK(wallet->cs_wallet);
+    wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
+    wallet->SetupDescriptorScriptPubKeyMans();
+
+    auto available_coins = coin_setup(*wallet);
+
+    const auto result = SelectCoins(*wallet, available_coins, /*pre_set_inputs=*/ {}, target, cc, cs_params);
+    if (result) {
+        const auto signedTxSize = 10 + 34 + 68 * result->GetInputSet().size(); // static header size + output size + inputs size (P2WPKH)
+        BOOST_CHECK_LE(signedTxSize * WITNESS_SCALE_FACTOR, MAX_STANDARD_TX_WEIGHT);
+
+        BOOST_CHECK_GE(result->GetSelectedValue(), target);
+    }
+    return result;
+}
+
+static bool has_coin(const CoinSet& set, CAmount amount)
+{
+    return std::any_of(set.begin(), set.end(), [&](const auto& coin) { return coin.GetEffectiveValue() == amount; });
+}
+
+BOOST_AUTO_TEST_CASE(check_max_weight)
+{
+    const CAmount target = 49.5L * COIN;
+    CCoinControl cc;
+
+    FastRandomContext rand;
+    CoinSelectionParams cs_params{
+        rand,
+        /*change_output_size=*/34,
+        /*change_spend_size=*/68,
+        /*min_change_target=*/CENT,
+        /*effective_feerate=*/CFeeRate(0),
+        /*long_term_feerate=*/CFeeRate(0),
+        /*discard_feerate=*/CFeeRate(0),
+        /*tx_noinputs_size=*/10 + 34, // static header size + output size
+        /*avoid_partial=*/false,
+    };
+
+    auto chain{m_node.chain.get()};
+
+    {
+        // Scenario 1:
+        // The actor starts with 1x 50.0 BTC and 1515x 0.033 BTC (~100.0 BTC total) unspent outputs
+        // Then tries to spend 49.5 BTC
+        // The 50.0 BTC output should be selected, because the transaction would otherwise be too large
+
+        // Perform selection
+
+        const auto result = select_coins(
+            target, cs_params, cc, [&](CWallet& wallet) {
+                CoinsResult available_coins;
+                for (int j = 0; j < 1515; ++j) {
+                    add_coin(available_coins, wallet, CAmount(0.033 * COIN), CFeeRate(0), 144, false, 0, true);
+                }
+
+                add_coin(available_coins, wallet, CAmount(50 * COIN), CFeeRate(0), 144, false, 0, true);
+                return available_coins;
+            },
+            chain, m_args);
+
+        BOOST_CHECK(result);
+        BOOST_CHECK(has_coin(result->GetInputSet(), CAmount(50 * COIN)));
+    }
+
+    {
+        // Scenario 2:
+
+        // The actor starts with 400x 0.0625 BTC and 2000x 0.025 BTC (75.0 BTC total) unspent outputs
+        // Then tries to spend 49.5 BTC
+        // A combination of coins should be selected, such that the created transaction is not too large
+
+        // Perform selection
+        const auto result = select_coins(
+            target, cs_params, cc, [&](CWallet& wallet) {
+                CoinsResult available_coins;
+                for (int j = 0; j < 400; ++j) {
+                    add_coin(available_coins, wallet, CAmount(0.0625 * COIN), CFeeRate(0), 144, false, 0, true);
+                }
+                for (int j = 0; j < 2000; ++j) {
+                    add_coin(available_coins, wallet, CAmount(0.025 * COIN), CFeeRate(0), 144, false, 0, true);
+                }
+                return available_coins;
+            },
+            chain, m_args);
+
+        BOOST_CHECK(has_coin(result->GetInputSet(), CAmount(0.0625 * COIN)));
+        BOOST_CHECK(has_coin(result->GetInputSet(), CAmount(0.025 * COIN)));
+    }
+
+    {
+        // Scenario 3:
+
+        // The actor starts with 1515x 0.033 BTC (49.995 BTC total) unspent outputs
+        // No results should be returned, because the transaction would be too large
+
+        // Perform selection
+        const auto result = select_coins(
+            target, cs_params, cc, [&](CWallet& wallet) {
+                CoinsResult available_coins;
+                for (int j = 0; j < 1515; ++j) {
+                    add_coin(available_coins, wallet, CAmount(0.033 * COIN), CFeeRate(0), 144, false, 0, true);
+                }
+                return available_coins;
+            },
+            chain, m_args);
+
+        // No results
+        // 1515 inputs * 68 bytes = 103,020 bytes
+        // 103,020 bytes * 4 = 412,080 weight, which is above the MAX_STANDARD_TX_WEIGHT of 400,000
+        BOOST_CHECK(!result);
+    }
+}
+
 BOOST_AUTO_TEST_CASE(SelectCoins_effective_value_test)
 {
     // Test that the effective value is used to check whether preset inputs provide sufficient funds when subtract_fee_outputs is not used.