coin selection: knapsack, select closest UTXO above target if result exceeds max tx size

The simplest scenario where this is useful is on the 'check_max_weight' unit test
already:

We create 1515 UTXOs with 0.033 BTC each, and 1 UTXO with 50 BTC. Then perform
Coin Selection.

As the selection of the 1515 small UTXOs exceeds the max allowed tx size, the
expectation here is to receive a selection result that only contain the big
UTXO (which is not happening for the reasons stated below).

As knapsack returns a result that exceeds the max allowed transaction size, we
fallback to SRD, which selects coins randomly up until the target is met. So
we end up with a selection result with lot more coins than what is needed.

1 files changed, 18 insertions, 1 deletions

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 5ea9b7fad3..75027520dd 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -15,6 +15,13 @@
 #include <optional>
 
 namespace wallet {
+// Common selection error across the algorithms
+static util::Result<SelectionResult> ErrorMaxWeightExceeded()
+{
+    return util::Error{_("The inputs size exceeds the maximum weight. "
+                         "Please try sending a smaller amount or manually consolidating your wallet's UTXOs")};
+}
+
 // Descending order comparator
 struct {
     bool operator()(const OutputGroup& a, const OutputGroup& b) const
@@ -253,7 +260,7 @@ static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::v
 }
 
 util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
-                                              CAmount change_target, FastRandomContext& rng)
+                                             CAmount change_target, FastRandomContext& rng, int max_weight)
 {
     SelectionResult result(nTargetValue, SelectionAlgorithm::KNAPSACK);
 
@@ -313,6 +320,16 @@ util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, c
             }
         }
 
+        // If the result exceeds the maximum allowed size, return closest UTXO above the target
+        if (result.GetWeight() > max_weight) {
+            // No coin above target, nothing to do.
+            if (!lowest_larger) return ErrorMaxWeightExceeded();
+
+            // Return closest UTXO above target
+            result.Clear();
+            result.AddInput(*lowest_larger);
+        }
+
         if (LogAcceptCategory(BCLog::SELECTCOINS, BCLog::Level::Debug)) {
             std::string log_message{"Coin selection best subset: "};
             for (unsigned int i = 0; i < applicable_groups.size(); i++) {