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

furszy · 2022-12-18T14:02:43Z

Coming from the following comment #25729 (comment).

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 · 2022-12-18T14:02:45Z

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.

murchandamus

Concept ACK

src/wallet/spend.cpp

src/wallet/test/coinselector_tests.cpp

src/wallet/coinselection.cpp

furszy · 2023-01-20T01:58:06Z

Updated with two points:

Added coverage for bnb max weight exceeded 41fb2c4.
Cleaned further the coin selection test f0add1d (noticed by @aureleoules inside #25806)

murchandamus

crACK w/ nits f0add1d0a7507e5601d7da54f62fe9ab272b3281

src/wallet/coinselection.h

src/wallet/test/coinselector_tests.cpp

src/wallet/coinselection.cpp

furszy · 2023-02-11T13:10:30Z

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

murchandamus

reACK 7d5a02ecb2af934ea0fa76c9013b2a2fc968b726

furszy · 2023-03-07T12:51:18Z

rebased, conflicts solved.

aureleoules

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

Sidenote, It seems this chunk of code is unused.

Unused code

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

aureleoules · 2023-04-03T20:38:26Z

src/wallet/spend.cpp

    if (auto bnb_result{SelectCoinsBnB(groups.positive_group, nTargetValue, coin_selection_params.m_cost_of_change)}) {
        results.push_back(*bnb_result);
-    }
+    } else append_error(bnb_result);


1284223 (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

Suggested change

} else append_error(bnb_result);

} else {

append_error(bnb_result);

}

Hmm, what about something like this furszy@0ddd8f4

src/wallet/spend.cpp

src/wallet/coinselection.cpp

furszy · 2023-04-03T22:14:54Z

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.

aureleoules · 2023-04-03T23:47:15Z

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

Concept ACK

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

src/wallet/coinselection.h

src/wallet/coinselection.cpp

furszy · 2023-04-04T18:26:15Z

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.

S3RK

Almost Code Review ACK 2a475c4
modulo one comment

src/wallet/spend.cpp

…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.

…x 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 <[email protected]>

… weight

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

Basic positive and negative scenarios

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

S3RK · 2023-04-06T16:23:24Z

ACK 25ab147

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

murchandamus

reACK 25ab147

theStack

Code-review ACK 25ab147

achow101 · 2023-04-20T20:25:29Z

ACK 25ab147

…t excee…

DrahtBot added the Wallet label Dec 18, 2022

furszy force-pushed the 2022_coin_selection_weight branch 3 times, most recently from 7663cbd to b4510ce Compare December 19, 2022 00:11

DrahtBot added the Needs rebase label Jan 4, 2023

furszy force-pushed the 2022_coin_selection_weight branch 5 times, most recently from 9392eaa to 4c249f8 Compare January 4, 2023 14:51

DrahtBot removed the Needs rebase label Jan 4, 2023

DrahtBot mentioned this pull request Jan 11, 2023

refactor: Split util/system into exception, shell, and fs-specific files #25152

Closed

murchandamus reviewed Jan 11, 2023

View reviewed changes

src/wallet/spend.cpp Show resolved Hide resolved

src/wallet/test/coinselector_tests.cpp Outdated Show resolved Hide resolved

src/wallet/coinselection.cpp Outdated Show resolved Hide resolved

src/wallet/coinselection.cpp Outdated Show resolved Hide resolved

furszy force-pushed the 2022_coin_selection_weight branch from 4c249f8 to 962b7d8 Compare January 13, 2023 16:47

murchandamus reviewed Jan 13, 2023

View reviewed changes

src/wallet/coinselection.cpp Outdated Show resolved Hide resolved

furszy force-pushed the 2022_coin_selection_weight branch 2 times, most recently from 10c5df8 to f0add1d Compare January 20, 2023 01:53

This was referenced Jan 20, 2023

refactor: wallet, remove global 'ArgsManager' dependency #26889

Merged

Introduce MockableDatabase for wallet unit tests #26715

Merged

murchandamus approved these changes Feb 10, 2023

View reviewed changes

furszy force-pushed the 2022_coin_selection_weight branch from f0add1d to 7d5a02e Compare February 11, 2023 13:07

murchandamus reviewed Feb 13, 2023

View reviewed changes

DrahtBot added the Needs rebase label Feb 17, 2023

DrahtBot removed the Needs rebase label Mar 7, 2023

furszy mentioned this pull request Mar 8, 2023

Option to ignore small inputs when internal wallet is building TXes? #20870

Open

aureleoules approved these changes Apr 3, 2023

View reviewed changes

theStack reviewed Apr 4, 2023

View reviewed changes

src/wallet/coinselection.h Outdated Show resolved Hide resolved

S3RK reviewed Apr 4, 2023

View reviewed changes

src/wallet/coinselection.cpp Show resolved Hide resolved

furszy force-pushed the 2022_coin_selection_weight branch from ba7970c to 488dbea Compare April 4, 2023 18:21

furszy force-pushed the 2022_coin_selection_weight branch from 488dbea to 2a475c4 Compare April 5, 2023 00:40

S3RK reviewed Apr 5, 2023

View reviewed changes

src/wallet/spend.cpp Outdated Show resolved Hide resolved

DrahtBot requested review from aureleoules and murchandamus April 5, 2023 07:01

furszy and others added 7 commits April 5, 2023 09:32

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

9d9689e

…x 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 <[email protected]>

test: coin selection, add coverage for SRD

d3a1c09

coin selection: BnB, don't return selection if exceeds max allowed tx…

2d11258

… weight

wallet: clean post coin selection max weight filter

5a2bc45

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

test: coverage for bnb max weight

ba9431c

Basic positive and negative scenarios

refactor: coinselector_tests, unify wallet creation code

25ab147

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

furszy force-pushed the 2022_coin_selection_weight branch from 2a475c4 to 25ab147 Compare April 5, 2023 12:33

murchandamus reviewed Apr 6, 2023

View reviewed changes

theStack approved these changes Apr 6, 2023

View reviewed changes

achow101 merged commit 395b932 into bitcoin:master Apr 20, 2023

sidhujag pushed a commit to syscoin/syscoin that referenced this pull request Apr 21, 2023

Merge bitcoin#26720: wallet: coin selection, don't return results tha…

6768102

…t excee…

furszy deleted the 2022_coin_selection_weight branch May 27, 2023 01:46

bitcoin locked and limited conversation to collaborators May 26, 2024

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

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

Uh oh!

Conversation

furszy commented Dec 18, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Dec 18, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Reviews

Conflicts

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

furszy commented Jan 20, 2023

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

furszy commented Feb 11, 2023

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

furszy commented Mar 7, 2023

Uh oh!

aureleoules left a comment

Choose a reason for hiding this comment

Uh oh!

aureleoules Apr 3, 2023

Choose a reason for hiding this comment

Uh oh!

furszy Apr 3, 2023

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

furszy commented Apr 3, 2023

Uh oh!

aureleoules commented Apr 3, 2023

Uh oh!

theStack left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

furszy commented Apr 4, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

S3RK left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

S3RK commented Apr 6, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

theStack left a comment

Choose a reason for hiding this comment

Uh oh!

achow101 commented Apr 20, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

furszy commented Dec 18, 2022 •

edited

Loading

DrahtBot commented Dec 18, 2022 •

edited

Loading

furszy commented Apr 4, 2023 •

edited

Loading

S3RK left a comment •

edited

Loading

S3RK commented Apr 6, 2023 •

edited

Loading