Repository: bitcoin/bitcoin (language: cpp)

Issue:
Coin selection, CreateTransaction, MAX_STANDARD_TX_SIZE
While regtesting with [bitcoin-spock](https://github.com/msgilligan/bitcoin-spock) I noticed at some point the transaction creation via `sendtoaddress -> CreateTransaction()` fails, because the created transaction is larger than `MAX_STANDARD_TX_SIZE`.

During the process a lot of raw transactions are created, which have smallish outputs and when then using `sendtoaddress`, it appears to attempt to create a transaction that spends too many of those dust-ish outputs.

The transaction to create does not have many outputs, but it looks like it's caused by the coin selection, which selects too many inputs. Testing was done with a 0.9 branch, but on the first glimpse I believe this issue is as well be present in 0.10. If this is a known issue, and if there is already a guard against this behavior, I'd be happy about a hint.

Sorry in advance, I do not have a test script to reproduce this issue in an isolated manner. A potential fix would probably require to adjust the coin selection, so that it selects a combination of coins, which, in addition to the size of the rest of the transaction, is still smaller than the limit.



Discussion / hints:
There have been some modifications to coin selection algorithm, maybe they improve things, see e.g. #4906

Thanks for the link! Unfortunally it doesn't seem to be related, but this issue is certainly something that probably won't appear outside of a testing environment. I created a test for it nevertheless:

https://github.com/dexX7/bitcoin/blob/qa-coin-selection-limit/qa/rpc-tests/coinselection_size_limit.py

The problem is that the coin selection doesn't relate to the transaction size at all. I came up with three scenarios, all failing at the moment:

Scenario 1:
- The actor starts with 1x 50.0 BTC and 1000x 0.05 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

Scenario 2:
- The actor starts with 500x 0.1 BTC and 1000x 0.05 BTC (100.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

Scenario 3 (available as RPC test):
- The actor starts with 1x 50.0 BTC, 500x 0.1 BTC and 1000x 0.05 BTC (150.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

For each scenario at least one solution exists, where a combination of coins results in a transaction that has a size of less than `MAX_STANDARD_TX_SIZE`.

Is this a duplicate of  #1643?
@MarcoFalke: looks like both issues tackle coin selection, while @dooglus' is about minimizing fees, mine is about making sure the transaction creation doesn't fail to begin with. Though optimizing fees also results in small transactions.

What's on top: there isn't a check during coin selection, whether the transaction is still within MAX_STANDARD_TX_SIZE.
From a quick glance, it looks to me that we still not check for the maximum weight during coin selection. So, while the much lighter modern input types make it even less likely that the max weight would be hit and at high feerates we deliberately aim for a small input weight, I don't think that we currently explicitly prevent that outcome during coin selection when it's in the consolidatory feerate range.

It would probably be a good first issue to check whether a selection result will be smaller than the maximum weight and to discard a selection result if not. Hopefully the other selection result candidates or a later back-off iteration would find a solution that fits then, but a slightly more involved task could be to add logic that guides coin selection to avoid exceeding the maximum weight if possible.

Fix patch:
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index b889d31928d64..ba1d60fe44c0f 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -5,6 +5,7 @@
 #include <wallet/coinselection.h>
 
 #include <consensus/amount.h>
+#include <consensus/consensus.h>
 #include <policy/feerate.h>
 #include <util/check.h>
 #include <util/system.h>
@@ -354,6 +355,10 @@ void OutputGroup::Insert(const COutput& output, size_t ancestors, size_t descend
     // descendants is the count as seen from the top ancestor, not the descendants as seen from the
     // coin itself; thus, this value is counted as the max, not the sum
     m_descendants = std::max(m_descendants, descendants);
+
+    if (output.input_bytes > 0) {
+        m_weight += output.input_bytes * WITNESS_SCALE_FACTOR;
+    }
 }
 
 bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const
@@ -436,18 +441,25 @@ void SelectionResult::Clear()
 {
     m_selected_inputs.clear();
     m_waste.reset();
+    m_weight = 0;
 }
 
 void SelectionResult::AddInput(const OutputGroup& group)
 {
     util::insert(m_selected_inputs, group.m_outputs);
     m_use_effective = !group.m_subtract_fee_outputs;
+
+    m_weight += group.m_weight;
 }
 
 void SelectionResult::AddInputs(const std::set<COutput>& inputs, bool subtract_fee_outputs)
 {
     util::insert(m_selected_inputs, inputs);
     m_use_effective = !subtract_fee_outputs;
+
+    m_weight += std::accumulate(inputs.cbegin(), inputs.cend(), 0, [](int sum, const auto& coin) {
+        return sum + std::max(coin.input_bytes, 0) * WITNESS_SCALE_FACTOR;
+    });
 }
 
 void SelectionResult::Merge(const SelectionResult& other)
@@ -462,6 +474,8 @@ void SelectionResult::Merge(const SelectionResult& other)
     }
     util::insert(m_selected_inputs, other.m_selected_inputs);
     assert(m_selected_inputs.size() == expected_count);
+
+    m_weight += other.m_weight;
 }
 
 const std::set<COutput>& SelectionResult::GetInputSet() const
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index 2ab4061a9b194..ecfc5bfd6b214 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -6,6 +6,7 @@
 #define BITCOIN_WALLET_COINSELECTION_H
 
 #include <consensus/amount.h>
+#include <consensus/consensus.h>
 #include <policy/feerate.h>
 #include <primitives/transaction.h>
 #include <random.h>
@@ -223,6 +224,8 @@ struct OutputGroup
     /** Indicate that we are subtracting the fee from outputs.
      * When true, the value that is used for coin selection is the UTXO's real value rather than effective value */
     bool m_subtract_fee_outputs{false};
+    /** Total weight of the UTXOs in this group. */
+    int m_weight{0};
 
     OutputGroup() {}
     OutputGroup(const CoinSelectionParams& params) :
@@ -295,6 +298,8 @@ struct SelectionResult
     bool m_use_effective{false};
     /** The computed waste */
     std::optional<CAmount> m_waste;
+    /** Total weight of the selected inputs */
+    int m_weight{0};
 
 public:
     explicit SelectionResult(const CAmount target, SelectionAlgorithm algo)
@@ -353,6 +358,8 @@ struct SelectionResult
     CAmount GetTarget() const { return m_target; }
 
     SelectionAlgorithm GetAlgo() const { return m_algo; }
+
+    int GetWeight() const { return m_weight; }
 };
 
 std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change);
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index 52d10b74b538b..1724b11268e21 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -2,9 +2,11 @@
 // Distributed under the MIT software license, see the accompanying
 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
+#include <algorithm>
 #include <consensus/amount.h>
 #include <consensus/validation.h>
 #include <interfaces/chain.h>
+#include <numeric>
 #include <policy/policy.h>
 #include <script/signingprovider.h>
 #include <util/check.h>
@@ -555,14 +557,24 @@ std::optional<SelectionResult> ChooseSelectionResult(const CWallet& wallet, cons
         results.push_back(*srd_result);
     }
 
-    if (results.size() == 0) {
+    if (results.empty()) {
         // No solution found
         return std::nullopt;
     }
 
+    std::vector<SelectionResult> eligible_results;
+    std::copy_if(results.begin(), results.end(), std::back_inserter(eligible_results), [coin_selection_params](const SelectionResult& result) {
+        const auto initWeight{coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR};
+        return initWeight + result.GetWeight() <= static_cast<int>(MAX_STANDARD_TX_WEIGHT);
+    });
+
+    if (eligible_results.empty()) {
+        return std::nullopt;
+    }
+
     // Choose the result with the least waste
     // If the waste is the same, choose the one which spends more inputs.
-    auto& best_result = *std::min_element(results.begin(), results.end());
+    auto& best_result = *std::min_element(eligible_results.begin(), eligible_results.end());
     return best_result;
 }
 
@@ -867,19 +879,16 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
     const auto change_spend_fee = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size);
     coin_selection_params.min_viable_change = std::max(change_spend_fee + 1, dust);
 
+    // Static vsize overhead + outputs vsize. 4 nVersion, 4 nLocktime, 1 input count, 1 witness overhead (dummy, flag, stack size)
+    coin_selection_params.tx_noinputs_size = 10 + GetSizeOfCompactSize(vecSend.size()); // bytes for output count
+
     // vouts to the payees
-    if (!coin_selection_params.m_subtract_fee_outputs) {
-        coin_selection_params.tx_noinputs_size = 10; // Static vsize overhead + outputs vsize. 4 nVersion, 4 nLocktime, 1 input count, 1 witness overhead (dummy, flag, stack size)
-        coin_selection_params.tx_noinputs_size += GetSizeOfCompactSize(vecSend.size()); // bytes for output count
-    }
     for (const auto& recipient : vecSend)
     {
         CTxOut txout(recipient.nAmount, recipient.scriptPubKey);
 
         // Include the fee cost for outputs.
-        if (!coin_selection_params.m_subtract_fee_outputs) {
-            coin_selection_params.tx_noinputs_size += ::GetSerializeSize(txout, PROTOCOL_VERSION);
-        }
+        coin_selection_params.tx_noinputs_size += ::GetSerializeSize(txout, PROTOCOL_VERSION);
 
         if (IsDust(txout, wallet.chain().relayDustFee())) {
             return util::Error{_("Transaction amount too small")};
@@ -888,7 +897,7 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
     }
 
     // Include the fees for things that aren't inputs, excluding the change output
-    const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);
+    const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.m_subtract_fee_outputs ? 0 : coin_selection_params.tx_noinputs_size);
     CAmount selection_target = recipients_sum + not_input_fees;
 
     // Fetch manually selected coins


Test patch:
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index c764264cd7a03..ce875d5442962 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.
diff --git a/test/functional/rpc_fundrawtransaction.py b/test/functional/rpc_fundrawtransaction.py
index 6874154f35f04..bf218bfee9f1d 100755
--- a/test/functional/rpc_fundrawtransaction.py
+++ b/test/functional/rpc_fundrawtransaction.py
@@ -987,7 +987,7 @@ def test_transaction_too_large(self):
             outputs[recipient.getnewaddress()] = 0.1
         wallet.sendmany("", outputs)
         self.generate(self.nodes[0], 10)
-        assert_raises_rpc_error(-4, "Transaction too large", recipient.fundrawtransaction, rawtx)
+        assert_raises_rpc_error(-4, "Insufficient funds", recipient.fundrawtransaction, rawtx)
         self.nodes[0].unloadwallet("large")
 
     def test_external_inputs(self):