wallet: coin selection, don't return results that exceed the max allowed weight

furszy commented at 2:02 pm on December 18, 2022: member

Coming from the following comment #25729 (review).

The reason why we are adding hundreds of UTXO from different sources when the target amount is covered only by one of them is because only SRD returns a usable result.

Context: In the test, we create 1515 UTXOs with 0.033 BTC each, and 1 UTXO with 50 BTC. Then perform Coin Selection to fund 49.5 BTC.

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 following reason:

Knapsack returns a result that exceeds the max allowed transaction size, when it should return the closest utxo above the target, so we fallback to SRD who 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.

DrahtBot commented at 2:02 pm on December 18, 2022: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	S3RK, Xekyo, theStack, achow101
Stale ACK	aureleoules

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#26715 (Introduce MockableDatabase for wallet unit tests by achow101)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

DrahtBot added the label Wallet on Dec 18, 2022

furszy force-pushed on Dec 18, 2022

furszy force-pushed on Dec 19, 2022

DrahtBot added the label Needs rebase on Jan 4, 2023

furszy force-pushed on Jan 4, 2023

DrahtBot removed the label Needs rebase on Jan 4, 2023

in src/wallet/spend.cpp:571 in 56f0c212d2 outdated

555 
556     std::vector<OutputGroup> positive_groups = GroupOutputs(wallet, available_coins, coin_selection_params, eligibility_filter, /*positive_only=*/true);
557     if (auto bnb_result{SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change)}) {
558         results.push_back(*bnb_result);
559-    }
560+    } else append_error(bnb_result);

murchandamus commented at 9:34 pm on January 11, 2023:

I’m not sure I get how that else branch is reached. Is util::Error() falsy?

furszy commented at 11:22 pm on January 11, 2023:

yeah. Internally the result class contains a variant and the bool operator returns true/false depending on what the variant is holding.

small extra note: this will look much better after #25806.

murchandamus commented at 2:09 am on January 12, 2023:

Ah cool, thanks for explaining

in src/wallet/test/coinselector_tests.cpp:1112 in 595cbc02f4 outdated

1004@@ -997,7 +1005,10 @@ BOOST_AUTO_TEST_CASE(check_max_weight)
1005             chain, m_args);
1006 
1007         BOOST_CHECK(result);
1008-        BOOST_CHECK(has_coin(result->GetInputSet(), CAmount(50 * COIN)));
1009+        // Verify that only the 50 BTC UTXO was selected
1010+        const auto& selection_res = result->GetInputSet();
1011+        BOOST_CHECK(selection_res.size() == 1);
1012+        BOOST_CHECK(selection_res.begin()->GetEffectiveValue() == 50 * COIN);

murchandamus commented at 9:45 pm on January 11, 2023:

I think this introduces a low chance failure of the test. The feerate is 0 which means that input sets with multiple inputs have a better waste score than one with only one input. It seems to me that all coin selection algorithms are being run, so if SRD finds a solution with 675 or fewer inputs, it should get preferred. While I agree that SRD should be improved in that we should curb excessive input sets like this, I think the test was correct previously and is incorrect now.

furszy commented at 1:47 pm on January 12, 2023:

hmm that doesn’t sound right.

As we set all feerates to 0, the change cost will be 0. So the waste calculation is simply a waste = inputs total amount - target. So we actually will never select the SRD result, because SRD is forced to select the 50 btc UTXO to succeed (otherwise it surpasses the max allowed weight).

In other words, Knapsacks result always return a waste of 0.5 btc, while SRD will return a waste of 0.5 btc + every extra added input that appears on the shuffled vector prior reaching the 50 btc UTXO. So, knapsacks_waste <= srd_waste.

murchandamus commented at 2:10 pm on January 12, 2023:

No, the waste is calculated via waste = weight_of_inputs × (feerate - long_term_feerate_estimate) where the LTFRE is 10 ṩ/vB. This means that at a feerate of 0 ṩ/vB, an input set with greater weight results in a lower (“more negative”) waste. I.e. if the SRD solution happens to roll an input set with 500 small inputs plus the 50 ₿ input it would fit in the standard transaction weight and have a better score than the input set with only the 50 ₿ input.

furszy commented at 2:47 pm on January 12, 2023:

the waste is calculated via waste = weight_of_inputs × (feerate - long_term_feerate_estimate) where the LTFRE is 10 ṩ/vB.

Where is the LTFRE set to 10ṩ/vB?

I’m seeing that it’s set to 0: https://github.com/bitcoin/bitcoin/blob/edc3d1b296e34838d649dc21b8483a52e214932a/src/wallet/test/coinselector_tests.cpp#L971-L972

So inside GetSelectionWaste the loop over all the inputs should be returning waste = 0 (waste = weight_of_inputs × (feerate - long_term_feerate_estimate) –> waste =  weight_of_inputs * 0).

Then below, as change_cost is 0 too, we get into: https://github.com/bitcoin/bitcoin/blob/edc3d1b296e34838d649dc21b8483a52e214932a/src/wallet/coinselection.cpp#L396-L400

murchandamus commented at 4:48 pm on January 12, 2023:

Ah, my bad. I did not expect anyone to change LTFRE in tests. :face_with_spiral_eyes: In that case, the weight of the inputs is irrelevant for the waste score (because weight × (0 - 0) = 0), and it will prefer an input set with change over one without change (unless excess is also 0). So very likely, the outcome of this test depends on either SRD being unsuccessful and/or that the order in which results are evaluated in ChooseSelectionResult(…) prefers the Knapsack result. I don’t think that’s is a good idea.

Since we are explicitly testing the behavior of Knapsack, this should be a test that just runs Knapsack and checks that the Knapsack behavior is expected.

Also pondering whether it’s necessary that the LTFRE setting is amended for this test—I totally did not expect that, and it may also change the expected outcome of other tests. Thanks for pointing that out.

murchandamus commented at 6:14 pm on January 12, 2023:

Having thought some more about this, setting LTFRE and cost_of_change to 0 basically turns off BnB. It will then only generate solutions that match the target to the satoshi. Definitely feels off that behavior of coin selection algorithms is so fundamentally changed in coinselector_tests.cpp. :thinking:

furszy commented at 7:40 pm on January 12, 2023:

In that case, the weight of the inputs is irrelevant for the waste score (because weight × (0 - 0) = 0), and it will prefer an input set with change over one without change (unless excess is also 0). So very likely, the outcome of this test depends on either SRD being unsuccessful and/or that the order in which results are evaluated in ChooseSelectionResult(…) prefers the Knapsack result.

Actually, the result does not depend on the order in which the algorithms are executed. SRD always success and has a higher waste than snapsack (only could fail if after shuffling the vector, the big UTXO is located at last, so fail is due an exceeded max weight):

The feerates are 0, same as the change cost, so the waste calculation is just a simple:

0waste = selected_effective_value - target;

So, Snapsack result only contains the 50 BTC UTXO (waste = 0,5 btc). And, SRD result has the 50 BTC UTXO + all the other small UTXOs that appear in the shuffled vector prior to the big UTXO (waste = 0,5 btc + all smaller UTXOs).

Essentially, the best selection that SRD could make is when the big UTXO appears first after shuffling the coins vector, which is equal to the only solution that snapsack returns. All the other solutions that SRD could return have a higher waste than snapsack.

Since we are explicitly testing the behavior of Knapsack, this should be a test that just runs Knapsack and checks that the Knapsack behavior is expected.

Make a specific test for this sounds good too. But I still think that would be nice to make tests that use the entire coin selection process and check that the expected result is returned (not only checking that any valid result is retrieved): check the inputs size, the value of them, the algorithm used etc.

Having thought some more about this, setting LTFRE and cost_of_change to 0 basically turns off BnB. It will then only generate solutions that match the target to the satoshi. Definitely feels off that behavior of coin selection algorithms is so fundamentally changed in coinselector_tests.cpp. 🤔

So we have a new working path hehe (probably more suited for a follow-up PR): validate BnB further by reviewing all the test running the entire coin selection process with the feerates and change_cost in 0. Plus, would be nice to code new tests running coin selection and expecting the best result to be retrieved by BnB.

murchandamus commented at 8:54 pm on January 12, 2023:

I think you may be referring to the description before BnB, which only describes the case for changeless input sets.

If you check GetSelectionWaste(…), you’ll see that the formula is waste = input_weight × (feerate - LTFRE) + excess + cost_of_change. excess is the amount of sats dropped to the fees because we overshot the selection target but do not have enough for a change output. It can only be non-zero in changeless solutions. cost_of_change is set to zero in changeless solutions, since we do not create change. So, the score will only ever include a non-zero value for one of excess or cost_of_change. Since both SRD and Knapsack create change, both add cost_of_change which is zero here. Since LTFRE == feerate, the input weight also gets multiplied with 0. So any input set for both these algorithms will always have a waste score of 0.

Which is to say, if either of these coin selection results under the above circumstances reports a waste score that is non-zero, I would suspect you have found a bug.

in src/wallet/coinselection.cpp:199 in d1f67afc60 outdated

194         const OutputGroup& group = utxo_pool.at(i);
195         Assume(group.GetSelectionAmount() > 0);
196+
197+        // If the selection weight exceeds the maximum allowed size, the random selection failed.
198+        weight += group.m_weight;
199+        if (weight > max_weight) return ErrorMaxWeightExceeded();

murchandamus commented at 9:51 pm on January 11, 2023:

A better way to improve SRD would perhaps be to keep all the selected inputs in a min-effective-value heap, and to kick out the least valuable inputs while the selected weight exceeds max_weight during selection.

furszy commented at 3:32 pm on January 12, 2023:

loved it, awesome idea :D

in src/wallet/coinselection.cpp:125 in 4c249f83f4 outdated

122+                    max_tx_size_exceeded = true; // at least one result exceeds the max weight
123+                } else {
124+                    // Set best selection
125+                    best_selection = curr_selection;
126+                    best_waste = curr_waste;
127+                }

murchandamus commented at 10:05 pm on January 11, 2023:

We should not continue searching a subtree when the selection already exceeds the max_weight. Instead of only checking it when we have selected sufficient funds, I would add curr_selection_weight > max_weight as a backtrack reason before else if (curr_value >= selection_target):

    if (curr_value + curr_available_value < selection_target || // Cannot possibly reach target with the amount remaining in the curr_available_value.
        curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch
        (curr_waste > best_waste && is_feerate_high)) { // Don't select things which we know will be more wasteful if the waste is increasing
        backtrack = true;
    } else if (curr_selection_weight > max_weight) { // Exceeding weight for standard tx, cannot find more solutions by adding more inputs
        max_tx_size_exceeded = true; // at least one selection attempt exceeded the max weight
        backtrack = true;
    } else if (curr_value >= selection_target) {       // Selected value is within range

furszy commented at 1:55 pm on January 12, 2023:

yeah better 👌🏼 , thanks

murchandamus commented at 10:10 pm on January 11, 2023: contributor

Concept ACK

furszy force-pushed on Jan 13, 2023

in src/wallet/coinselection.cpp:237 in 42afb84687 outdated

233+        }
234+
235+        // Add group to selection
236         selected_eff_value += group.GetSelectionAmount();
237-        result.AddInput(group);
238+        heap.push(group);

murchandamus commented at 6:25 pm on January 13, 2023:

Cool, thanks for putting the heap in already. I think it’ll be simpler if you first add the new group to the heap and then use the heap to decide whether the new or old group should be popped to get below weight:

 0          
 1        // Add group to selection
 2        heap.push(group);
 3        selected_eff_value += group.GetSelectionAmount();
 4        weight += group.m_weight;
 5        
 6        // If the selection weight exceeds the maximum allowed size, remove the least valuable inputs until we
 7        // are below max weight.
 8        if (weight > max_weight) { 
 9            max_tx_size_exceeded = true; // mark it in case we don't find any useful result.
10
11            do {
12                const OutputGroup& to_remove_group = heap.top();
13                selected_eff_value -= to_remove_group.GetSelectionAmount();
14                weight -= to_remove_group.m_weight;
15                heap.pop();
16            } while (!heap.empty() && weight > max_weight);
17        }

furszy commented at 9:38 pm on January 13, 2023:

Nice 👌🏼, applied changes and added your co-authorship. Thanks :).

furszy force-pushed on Jan 13, 2023

furszy force-pushed on Jan 20, 2023

furszy commented at 1:58 am on January 20, 2023: member

Updated with two points:

Added coverage for bnb max weight exceeded https://github.com/bitcoin/bitcoin/pull/26720/commits/41fb2c4dd8a15dc0c59ca4d5d0befab707ca8954.
Cleaned further the coin selection test f0add1d (noticed by @aureleoules inside #25806)

in src/wallet/coinselection.h:388 in c723827ac2 outdated

383@@ -384,9 +384,12 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
384  *
385  * @param[in]  utxo_pool    The positive effective value OutputGroups eligible for selection
386  * @param[in]  target_value The target value to select for
387+ * @param[in]  rng The randomness source to shuffle coins
388+ * @param[in] max_weight The maximum allowed weight for a selection result to be valid

murchandamus commented at 9:31 pm on February 10, 2023:

Nit: whitespace

furszy commented at 1:07 pm on February 11, 2023:

done

in src/wallet/test/coinselector_tests.cpp:1042 in bcb6f22130 outdated

1025+            for (int j = 0; j < 60; ++j) { // 60 UTXO --> 19,8 BTC total --> weight 272 * 60 = 16320 kvb
1026+                add_coin(available_coins, wallet, CAmount(0.33 * COIN), CFeeRate(0), 144, false, 0, true);
1027+            }
1028+            for (int i = 0; i < 10; i++) { // 10 UTXO --> 20 BTC total --> weight 272 * 10 = 2720 kvb
1029+                add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(0), 144, false, 0, true);
1030+            }

murchandamus commented at 9:50 pm on February 10, 2023:

0        CAmount target = 25.33L * COIN;
1        int max_weight = 10000; // WU
2        const auto& res = SelectCoinsSRD(target, cs_params, m_node.chain.get(), m_args, max_weight, [&](CWallet& wallet) {
3            CoinsResult available_coins;
4            for (int j = 0; j < 60; ++j) { // 60 UTXO --> 19,8 BTC total --> 60 × 272 WU = 16320 WU
5                add_coin(available_coins, wallet, CAmount(0.33 * COIN), CFeeRate(0), 144, false, 0, true);
6            }
7            for (int i = 0; i < 10; i++) { // 10 UTXO --> 20 BTC total --> 10 × 272 WU = 2720 WU
8                add_coin(available_coins, wallet, CAmount(2 * COIN), CFeeRate(0), 144, false, 0, true);
9            }

I was reconstructing what sort of input set this test will find. From what I gather, we can have up to 36 inputs, and we’ll need 9 of the 2 ₿ UTXOs to hit the target amount. However, I was confused that the limit is 10'000 and labeled “weight”, while the inputs are appraised at “272 kvb”. It would work out, though if the max_weight were interpreted as 10'000 WU, and the inputs are 272 WU each (i.e. 68 vB). Are we looking at P2WPKH inputs here?

furszy commented at 12:52 pm on February 11, 2023:

ah yeah, good catch. All the numbers are expressed in weight units. And yes, inputs are all P2WPKH (all of them in every coinselector_tests.cpp test case).

in src/wallet/coinselection.cpp:102 in 2c9b9507c9 outdated

 98@@ -97,6 +99,7 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
 99     CAmount best_waste = MAX_MONEY;
100 
101     bool is_feerate_high = utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee;
102+    bool max_tx_size_exceeded = false;

murchandamus commented at 9:52 pm on February 10, 2023:

Nit: weight != size

0    bool max_tx_weight_exceeded = false;

furszy commented at 1:07 pm on February 11, 2023:

fixed

in src/wallet/coinselection.cpp:113 in 2c9b9507c9 outdated

108@@ -106,6 +109,9 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
109             curr_value > selection_target + cost_of_change || // Selected value is out of range, go back and try other branch
110             (curr_waste > best_waste && is_feerate_high)) { // Don't select things which we know will be more wasteful if the waste is increasing
111             backtrack = true;
112+        } else if (curr_selection_weight > max_weight) { // Exceeding weight for standard tx, cannot find more solutions by adding more inputs
113+            max_tx_size_exceeded = true; // at least one selection attempt exceeded the max weight

murchandamus commented at 9:53 pm on February 10, 2023:

0            max_tx_weight_exceeded = true; // at least one selection attempt exceeded the max weight

furszy commented at 1:07 pm on February 11, 2023:

done

in src/wallet/coinselection.cpp:171 in 2c9b9507c9 outdated

167     }
168 
169     // Check for solution
170     if (best_selection.empty()) {
171-        return util::Error();
172+        return max_tx_size_exceeded ? ErrorMaxWeightExceeded() : util::Error();

murchandamus commented at 9:54 pm on February 10, 2023:

0        return max_tx_weight_exceeded ? ErrorMaxWeightExceeded() : util::Error();

furszy commented at 1:07 pm on February 11, 2023:

done

murchandamus approved

murchandamus commented at 10:15 pm on February 10, 2023: contributor

crACK w/ nits f0add1d0a7507e5601d7da54f62fe9ab272b3281

furszy force-pushed on Feb 11, 2023

furszy commented at 1:10 pm on February 11, 2023: member

Feedback tackled, thanks for the review Xekyo! Pushed diff.

murchandamus commented at 7:03 pm on February 13, 2023: contributor

reACK 7d5a02ecb2af934ea0fa76c9013b2a2fc968b726

DrahtBot added the label Needs rebase on Feb 17, 2023

furszy force-pushed on Feb 20, 2023

DrahtBot removed the label Needs rebase on Feb 20, 2023

DrahtBot added the label Needs rebase on Mar 7, 2023

wallet: refactor coin selection algos to return util::Result

so the selection processes can retrieve different errors and not
uninformative std::nullopt

1284223691

furszy force-pushed on Mar 7, 2023

furszy commented at 12:51 pm on March 7, 2023: member

rebased, conflicts solved.

DrahtBot removed the label Needs rebase on Mar 7, 2023

in src/wallet/spend.cpp:568 in 1284223691 outdated

564+    };
565 
566     if (auto bnb_result{SelectCoinsBnB(groups.positive_group, nTargetValue, coin_selection_params.m_cost_of_change)}) {
567         results.push_back(*bnb_result);
568-    }
569+    } else append_error(bnb_result);

aureleoules commented at 8:38 pm on April 3, 2023:

1284223691127e76135a46d251c52416104f0ff1 (same below)

If an if only has a single-statement then-clause, it can appear on the same line as the if, without braces. In every other case, braces are required, and the then and else clauses must appear correctly indented on a new line. https://github.com/bitcoin/bitcoin/blob/master/doc/developer-notes.md#coding-style-c

0    } else {
1		append_error(bnb_result);
2	}

furszy commented at 10:10 pm on April 3, 2023:

Hmm, what about something like this https://github.com/furszy/bitcoin-core/commit/0ddd8f4e2672f4826b87b1cfda617a3c15caabea

in src/wallet/spend.cpp:567 in 187ce369ff outdated

562@@ -563,12 +563,15 @@ util::Result<SelectionResult> ChooseSelectionResult(const CAmount& nTargetValue,
563         }
564     };
565 
566+    // Maximum allowed transaction weight
567+    int max_weight = MAX_STANDARD_TX_WEIGHT - (coin_selection_params.tx_noinputs_size * WITNESS_SCALE_FACTOR);

aureleoules commented at 8:57 pm on April 3, 2023:

nit: Maybe rename the variable to max_inputs_weight to make it clearer?

furszy commented at 10:12 pm on April 3, 2023:

it’s the maximum allowed transaction weight, not only for the inputs.

theStack commented at 0:09 am on April 4, 2023:

it’s the maximum allowed transaction weight, not only for the inputs.

I don’t think so? The coin selection algos don’t have any knowledge about the additional data of the to-be-created tx (static header size + outputs), so they can only work with a weight limit on the inputs.

murchandamus commented at 3:38 pm on April 4, 2023:

I’m confused, @aureleoules’s suggestion makes sense to me. If it’s the maximum allowed transaction weight, why is it reduced by the tx_noinputs_size? If it’s supposed to be the allowance for inputs, it might additionally need to be reduced by an allowance for the change output?

furszy commented at 4:19 pm on April 4, 2023:

it’s the maximum allowed transaction weight, not only for the inputs. I don’t think so? The coin selection algos don’t have any knowledge about the additional data of the to-be-created tx (static header size + outputs), so they can only work with a weight limit on the inputs.

oops, I shouldn’t answer comments at night. My bad. Un-resolving this. it’s ok to say that is the max inputs weight. Will rename the variable in the next push.

If it’s supposed to be the allowance for inputs, it might additionally need to be reduced by an allowance for the change output?

Good point. Need to also deduce the change_spend_size for knapsack and SRD.

furszy commented at 6:21 pm on April 4, 2023:

pushed

in src/wallet/coinselection.cpp:187 in fd8cf58d73 outdated

172@@ -172,9 +173,20 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
173     return result;
174 }
175 
176-util::Result<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng)
177+class MinOutputGroupComparator
178+{
179+public:
180+    int operator() (const OutputGroup& group1, const OutputGroup& group2)

aureleoules commented at 9:00 pm on April 3, 2023:

fd8cf58d736ed9614f46b4f5b3c92f71ff9c46d4 nit

0    const int operator() (const OutputGroup& group1, const OutputGroup& group2)

furszy commented at 6:18 pm on April 4, 2023:

hmm why? warning: 'const' type qualifier on return type has no effect

aureleoules commented at 11:32 pm on April 4, 2023:

Whoops I meant int operator() (const OutputGroup& group1, const OutputGroup& group2) const

furszy commented at 0:40 am on April 5, 2023:

sure, pushed

aureleoules approved

aureleoules commented at 9:32 pm on April 3, 2023: member

ACK 1284223691127e76135a46d251c52416104f0ff1 - I verified the tests are correct and the code looks good to me.

Sidenote, It seems this chunk of code is unused.

 0diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
 1index 92d33bd38..26405d63a 100644
 2--- a/src/wallet/coinselection.cpp
 3+++ b/src/wallet/coinselection.cpp
 4@@ -448,13 +448,6 @@ void OutputGroupTypeMap::Push(const OutputGroup& group, OutputType type, bool in
 5     }
 6 }
 7 
 8-std::optional<Groups> OutputGroupTypeMap::Find(OutputType type)
 9-{
10-    auto it_by_type = groups_by_type.find(type);
11-    if (it_by_type == groups_by_type.end()) return std::nullopt;
12-    return it_by_type->second;
13-}
14-
15 CAmount GetSelectionWaste(const std::set<std::shared_ptr<COutput>>& inputs, CAmount change_cost, CAmount target, bool use_effective_value)
16 {
17     // This function should not be called with empty inputs as that would mean the selection failed

furszy commented at 10:14 pm on April 3, 2023: member

Thanks aureleoules for the feedback.

Sidenote, It seems this chunk of code is unused.

That chunk of code is not in master, #27227 already cleaned it.

in src/wallet/coinselection.h:419 in 1284223691 outdated

417@@ -417,10 +418,10 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
418  * @param[in]  target_value The target value to select for
419  * @returns If successful, a SelectionResult, otherwise, std::nullopt

theStack commented at 11:24 pm on April 3, 2023:

in commit 1284223691127e76135a46d251c52416104f0ff1: this doxygen comment about the return-value has to be adapted w.r.t. std::nullopt

furszy commented at 6:21 pm on April 4, 2023:

pushed

aureleoules commented at 11:47 pm on April 3, 2023: member

That chunk of code is not in master, #27227 already cleaned it.

Ah great, I’m not up-to-date with all the recently merged PRs, it’s been a while since I reviewed any!

theStack commented at 0:04 am on April 4, 2023: contributor

Concept ACK

Changes look good at a first glance :ok_hand:, will do a second round tomorrow.

in src/wallet/coinselection.cpp:22 in ba7970c793 outdated

17 
18 namespace wallet {
19+// Common selection error across the algorithms
20+static util::Result<SelectionResult> ErrorMaxWeightExceeded()
21+{
22+    return util::Error{_("The inputs size exceeds the maximum weight. "

S3RK commented at 7:31 am on April 4, 2023:

I haven’t written a test for this, so all the following is not verified and just my guess based on the code understanding.

This is not a regression in this particular PR, but this could lead to misleading errors in a situation when a proper solution exists, but our coin selection failed to find it and only found solution that exceeded weight. Let’s imagine following scenario:

UTXO pool: two big coins 50BTC, a ton of 0.001BTC.
Target amount: 90BTC
Proper solution: just take two big coins and create a change output.

I think none of the coin selection algorithms will be able to reliably find the proper solution.

BnB won’t be able to find it, because proper solution includes change.
Knapsack again optimises for the match, therefore it discards the proper solution in favour of a closer match that exceeds the weight limit.
SRD misses proper solution with 75% chance, because it checks each coin exactly once. If it skipped at least one of two big coins it will never find the proper solution.

I think we should a) make the message more explicit about the fact that solution might exist, but we just failed to find one b) propose users to select coins manually as another remedy c) better document the shortcomings of our coin selection.

S3RK commented at 7:38 am on April 4, 2023:

I wrote #24580 at some point to capture known to me inefficiencies of current coin selection. The scenario I described above is very close to case no.3 in test_one_big_and_many_small_coins

furszy commented at 1:56 pm on April 4, 2023:

I haven’t written a test for this, so all the following is not verified and just my guess based on the code understanding.

This is not a regression in this particular PR, but this could lead to misleading errors in a situation when a proper solution exists, but our coin selection failed to find it and only found solution that exceeded weight. Let’s imagine following scenario:

UTXO pool: two big coins 50BTC, a ton of 0.001BTC.

Target amount: 90BTC

Proper solution: just take two big coins and create a change output.

I think none of the coin selection algorithms will be able to reliably find the proper solution.

BnB won’t be able to find it, because proper solution includes change.

Knapsack again optimises for the match, therefore it discards the proper solution in favour of a closer match that exceeds the weight limit.

SRD misses proper solution with 75% chance, because it checks each coin exactly once. If it skipped at least one of two big coins it will never find the proper solution.

No wait, have you checked the introduced SRD changes? https://github.com/bitcoin/bitcoin/pull/26720/commits/fd8cf58d736ed9614f46b4f5b3c92f71ff9c46d4.

The algorithm now uses a min-effective-value heap; it discards the least valuable input/s while the selected weight exceeds the maximum allowed weight.

So in your scenario, SRD will always find a solution.

Basically, it adds coins to a heap while the target is not met. So, if the max weight is exceeded, it pops the least valuable coin and adds the new one. Then keeps walking-through the coins vector until (1) target is covered, or (2) fail due an insufficient funds or (3) fail due having enough funds but the max allowed weight was exceeded.

I think we should a) make the message more explicit about the fact that solution might exist, but we just failed to find one b) propose users to select coins manually as another remedy c) better document the shortcomings of our coin selection.

I think that you are only having in mind part of the process and maybe not contemplating the expanded coin eligibility process. If no solution was found in the first selection attempt round, we are running the selection algorithms multiple times. Not only once.

An edge case would be that the coins that are needed to create a valid selection are in the last coin eligibility filter, but even in that situation, SRD will find a solution.

Still, let’s say that also SRD doesn’t return a result for some reason. And we don’t find a solution even when the user has enough funds. The solution shouldn’t be placed here. It can be placed at the end of AutomaticCoinSelection, because there we know the total available balance (and also the discarded coins, which since acf0119d24c9f8fae825093249a46cd38e4a3a91 we are also contemplating) so we can easily return a “you have enough funds but the wallet coin selection process failed, please select coins manually” instead of the general “Insufficient Funds”.

Side note: As this PR isn’t conflicting with master, I haven’t rebase it. So, there are improvements like the discarded coins early return (due the coin eligibility filtering process) that are not here.

S3RK commented at 6:38 am on April 5, 2023:

ah, yes. You’re right, now I see why SRD will always find a solution if it exists. LGTM

furszy force-pushed on Apr 4, 2023

furszy commented at 6:26 pm on April 4, 2023: member

Thanks all for the feedback :). Update Diff:

Renamed max_weight to max_inputs_weight.
Deduced change output weight from the max allowed weight for Knapsack and SRD (not from BnB as it’s specialized to not create change).
Adapted doxygen comment to current sources.

furszy force-pushed on Apr 5, 2023

in src/wallet/spend.cpp:574 in e7b4680f1c outdated

569     if (auto bnb_result{SelectCoinsBnB(groups.positive_group, nTargetValue, coin_selection_params.m_cost_of_change)}) {
570         results.push_back(*bnb_result);
571     } else append_error(bnb_result);
572 
573+    // As Knapsack and SRD can create change, also deduce change weight.
574+    max_inputs_weight -= (coin_selection_params.change_spend_size * WITNESS_SCALE_FACTOR);

S3RK commented at 6:42 am on April 5, 2023:

I think this should be change_output_size not change_spend_size

furszy commented at 12:33 pm on April 5, 2023:

yep thanks, fixed

S3RK commented at 7:01 am on April 5, 2023: contributor

Almost Code Review ACK 2a475c4 modulo one comment

DrahtBot requested review from aureleoules on Apr 5, 2023

DrahtBot requested review from murchandamus on Apr 5, 2023

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.

6107ec2229

coin selection: heap-ify SRD, don't return selection if exceeds max tx weight

Uses a min-effective-value heap, so we can remove the least valuable input/s
while the selected weight exceeds the maximum allowed weight.

Co-authored-by: Murch <murch@murch.one>

9d9689e5a6

test: coin selection, add coverage for SRD d3a1c098e4

coin selection: BnB, don't return selection if exceeds max allowed tx weight 2d112584e3

wallet: clean post coin selection max weight filter

Now the coin selection algorithms contemplate the
maximum allowed weight internally and return
std::nullopt if their result exceeds it.

5a2bc45ee0

test: coverage for bnb max weight

Basic positive and negative scenarios

ba9431c505

refactor: coinselector_tests, unify wallet creation code

same lines of code repeated across the entire file over and over.

25ab14712b

furszy force-pushed on Apr 5, 2023

S3RK commented at 4:23 pm on April 6, 2023: contributor

ACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635

The only change is my previous comment addressed about using correct variable to determine change output size.

murchandamus commented at 6:05 pm on April 6, 2023: contributor

reACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635

theStack approved

theStack commented at 11:36 pm on April 6, 2023: contributor

Code-review ACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635

achow101 commented at 8:25 pm on April 20, 2023: member

ACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635

achow101 merged this on Apr 20, 2023

achow101 closed this on Apr 20, 2023

sidhujag referenced this in commit 67681025fc on Apr 21, 2023

furszy deleted the branch on May 27, 2023

bitcoin locked this on May 26, 2024

wallet: coin selection, don’t return results that exceed the max allowed weight #26720

Reviews

Conflicts