wallet: Introduce SelectionResult for encapsulating a coin selection solution #22019

achow101 · 2021-05-21T23:09:24Z

Instead of returning a set of selected coins and their total value as separate items, encapsulate both of these, and other variables, into a new SelectionResult struct. This allows us to have all of the things relevant to a coin selection solution be in a single object. SelectionResult enables us to implement the waste calculation in a cleaner way.

All of the coin selection functions (SelectCoinsBnB, KnapsackSolver, AttemptSelection, and SelectCoins) are changed to use a SelectionResult as the output parameter.

Based on #22009

DrahtBot · 2021-05-22T03:49:39Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#23534 (wallet: Allow negtive effective value inputs when subtracting fee from outputs by achow101)
#23497 (Add src/node/ and src/wallet/ code to node:: and wallet:: namespaces by ryanofsky)
#23475 (wallet: add config to prioritize a solution that doesn't create change in coin selection by brunoerg)
#23367 (Optimize coin selection by dropping BnB upper limit by S3RK)
#23202 (wallet: allow psbtbumpfee to work with txs with external inputs by achow101)
#23201 (wallet: Allow users to specify input weights when funding a transaction by achow101)
#13226 (Optimize SelectCoinsBnB by tracking the selection by index rather than by position by Empact)

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.

glozow

Concept ACK

murchandamus

Light review, concept ACK

murchandamus · 2021-09-03T20:22:38Z

src/wallet/test/coinselector_tests.cpp

@@ -178,15 +197,15 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
    // Select 1 Cent
    add_coin(1 * CENT, 1, actual_selection);
    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret));
-    BOOST_CHECK(equal_sets(selection, actual_selection));
+    BOOST_CHECK(equivalent_sets(selection, actual_selection));


Commit 80402a1: This may be more a comment on the commit message, but shouldn't the result of BnB be deterministic? Are the OutputGroups unsorted, or how is this happening?

I don't remember the specifics, but I think it had to with different txids being in utxo_pool and actual_selection

src/wallet/coinselection.h

src/wallet/test/coinselector_tests.cpp

src/wallet/spend.cpp

src/wallet/coinselection.cpp

src/wallet/test/coinselector_tests.cpp

src/wallet/coinselection.cpp

src/wallet/spend.h

laanwj · 2021-12-02T15:16:15Z

Code review ACK e142d9a
Seems pretty close to merge, found some last minute nits (sorry).

glozow

utACK e142d9a, a few suggestions/questions

src/wallet/coinselection.cpp

src/wallet/test/coinselector_tests.cpp

src/wallet/spend.cpp

src/wallet/coinselection.cpp

Introduces a SelectionResult struct which contains the set of selected inputs and the total transaction fee for the transaction. This will be used by the various SelectCoins* functions. Additionally helpers are provided to compute the total input value and result comparisons.

Replace the CoinSet actual_selection with a SelectionResult expected_result. We don't use the SelectionResult functions yet, but will soon. -BEGIN VERIFY SCRIPT- sed -i 's/CoinSet actual_selection/SelectionResult expected_result(CAmount(0))/' src/wallet/test/coinselector_tests.cpp sed -i 's/actual_selection/expected_result.m_selected_inputs/' src/wallet/test/coinselector_tests.cpp sed -i 's/expected_result.m_selected_inputs.clear/expected_result.Clear/' src/wallet/test/coinselector_tests.cpp -END VERIFY SCRIPT-

Removes coins_out and value_ret has SelectCoinsBnB return a std::optional<SelectionResult>

Returns a std::optional<SelectionResult> from KnapsackSolver instead of using out parameters for the inputs set and selected value.

Changes SelectCoinsSRD to return a SelectionResult.

In SelectCoins, for our preset inputs, we combine all of the preset inputs into a single OutputGroup. This allows us to combine the preset inputs with additional selection algo results.

Replace setCoinsRet and nValueRet with a SelectionResult in AttemptSelection

Replace setCoinsRet and nValueRet with SelectionResult

laanwj · 2021-12-09T16:20:34Z

Code review ACK 05300c1

glozow

reACK 05300c1. Thanks for taking suggestions!

glozow · 2021-12-09T16:30:43Z

src/wallet/spend.cpp

-    const auto& best_result = std::min_element(results.begin(), results.end(), [](const auto& a, const auto& b) {
-        return std::get<0>(a) < std::get<0>(b) || (std::get<0>(a) == std::get<0>(b) && std::get<1>(a).size() > std::get<1>(b).size());
-    });
-    setCoinsRet = std::get<1>(*best_result);
-    nValueRet = std::get<2>(*best_result);
-    return true;
+    auto& best_result = *std::min_element(results.begin(), results.end());


maflcko

left some q

maflcko · 2021-12-09T17:07:11Z

src/wallet/coinselection.cpp

+
+CAmount SelectionResult::GetWaste() const
+{
+    Assume(m_waste != std::nullopt);


This will need to be Assert, otherwise you might run into UB, no?

maflcko · 2021-12-09T17:07:40Z

src/wallet/coinselection.cpp

+    Assume(m_waste != std::nullopt);
+    Assume(other.m_waste != std::nullopt);
+    // As this operator is only used in std::min_element, we want the result that has more inputs when waste are equal.
+    return *m_waste < *other.m_waste || (*m_waste == *other.m_waste && m_selected_inputs.size() > other.m_selected_inputs.size());


…capsulating a coin selection solution b09b4f2 Use SelectionResult in SelectCoins (Andrew Chow) ee30ea0 Use SelectionResult in AttemptSelection (Andrew Chow) ffacd8b Use SelectionResult for waste calculation (Andrew Chow) 4e02a76 Make an OutputGroup for preset inputs (Andrew Chow) c63ef3d Return SelectionResult from SelectCoinsSRD (Andrew Chow) ac4f10a Return SelectionResult from KnapsackSolver (Andrew Chow) 361c7c2 Return SelectionResult from SelectCoinsBnB (Andrew Chow) d099e74 Make member variables of SelectionResult private (Andrew Chow) af51708 scripted-diff: Use SelectionResult in coin selector tests (Andrew Chow) c6aca86 Introduce SelectionResult struct (Andrew Chow) 3f4a86b Fix bnb_search_test to use set equivalence for (Andrew Chow) Pull request description: Instead of returning a set of selected coins and their total value as separate items, encapsulate both of these, and other variables, into a new `SelectionResult` struct. This allows us to have all of the things relevant to a coin selection solution be in a single object. `SelectionResult` enables us to implement the waste calculation in a cleaner way. All of the coin selection functions (`SelectCoinsBnB`, `KnapsackSolver`, `AttemptSelection`, and `SelectCoins`) are changed to use a `SelectionResult` as the output parameter. Based on #22009 ACKs for top commit: laanwj: Code review ACK b09b4f2 Tree-SHA512: e4dbb4d78a6cda9c237d230b19e7265591efac5a101a64e6970f0654e2c4f93d13bb5d07b98e8c7b8d37321753dbfc94c28c3a7810cb1c59b5bc29b08a8493ef

DrahtBot added the Wallet label May 21, 2021

achow101 force-pushed the selectionresult branch from ada015b to ca52211 Compare May 25, 2021 15:51

achow101 force-pushed the selectionresult branch from ca52211 to c5eaaa7 Compare June 1, 2021 19:35

achow101 force-pushed the selectionresult branch from c5eaaa7 to 5b89c40 Compare June 2, 2021 22:47

This was referenced Jun 5, 2021

wallet test: Add test for subtract fee from recipient behavior #22155

Merged

Optimize SelectCoinsBnB by tracking the selection by index rather than by position #13226

Merged

achow101 force-pushed the selectionresult branch from 5b89c40 to e598278 Compare June 9, 2021 17:22

achow101 force-pushed the selectionresult branch from e598278 to 812b972 Compare July 3, 2021 01:29

glozow reviewed Aug 24, 2021

View reviewed changes

achow101 force-pushed the selectionresult branch 2 times, most recently from 4681b17 to 0d8fe54 Compare September 1, 2021 21:19

achow101 marked this pull request as ready for review September 1, 2021 21:20

DrahtBot added the Needs rebase label Sep 3, 2021

achow101 force-pushed the selectionresult branch from 0d8fe54 to 2df49b3 Compare September 3, 2021 21:25

murchandamus reviewed Sep 3, 2021

View reviewed changes

DrahtBot removed the Needs rebase label Sep 3, 2021

achow101 force-pushed the selectionresult branch from 2df49b3 to a066567 Compare September 4, 2021 00:34

DrahtBot mentioned this pull request Sep 7, 2021

Enable clang-tidy bugprone-argument-comment and fix violations #22903

Merged

This was referenced Nov 18, 2021

wallet: Allow negative effective value inputs when subtracting fee from outputs #23534

Closed

scripted-diff: Use clang-tidy syntax for C++ named arguments #23545

Closed

laanwj reviewed Nov 23, 2021

View reviewed changes

src/wallet/coinselection.cpp Show resolved Hide resolved

laanwj reviewed Nov 23, 2021

View reviewed changes

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

laanwj reviewed Nov 23, 2021

View reviewed changes

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

laanwj reviewed Nov 23, 2021

View reviewed changes

src/wallet/coinselection.cpp Show resolved Hide resolved

achow101 force-pushed the selectionresult branch 4 times, most recently from dd05b60 to e142d9a Compare November 23, 2021 23:26

laanwj reviewed Dec 2, 2021

View reviewed changes

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

glozow reviewed Dec 2, 2021

View reviewed changes

achow101 added 10 commits December 5, 2021 13:39

Make member variables of SelectionResult private

a339add

Return SelectionResult from SelectCoinsBnB

60d2ca7

Removes coins_out and value_ret has SelectCoinsBnB return a std::optional<SelectionResult>

Return SelectionResult from KnapsackSolver

0ef6184

Returns a std::optional<SelectionResult> from KnapsackSolver instead of using out parameters for the inputs set and selected value.

Return SelectionResult from SelectCoinsSRD

51a9c00

Changes SelectCoinsSRD to return a SelectionResult.

Make an OutputGroup for preset inputs

e8f7ae5

In SelectCoins, for our preset inputs, we combine all of the preset inputs into a single OutputGroup. This allows us to combine the preset inputs with additional selection algo results.

Use SelectionResult for waste calculation

bb50850

Use SelectionResult in AttemptSelection

9d9b101

Replace setCoinsRet and nValueRet with a SelectionResult in AttemptSelection

Use SelectionResult in SelectCoins

05300c1

Replace setCoinsRet and nValueRet with SelectionResult

achow101 force-pushed the selectionresult branch from e142d9a to 05300c1 Compare December 5, 2021 18:49

laanwj merged commit c840ab0 into bitcoin:master Dec 9, 2021

glozow reviewed Dec 9, 2021

View reviewed changes

maflcko reviewed Dec 9, 2021

View reviewed changes

bitcoin locked and limited conversation to collaborators Dec 13, 2022

wallet: Introduce SelectionResult for encapsulating a coin selection solution #22019

wallet: Introduce SelectionResult for encapsulating a coin selection solution #22019

Uh oh!

Conversation

achow101 commented May 21, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented May 22, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

glozow left a comment

Choose a reason for hiding this comment

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

murchandamus Sep 3, 2021

Choose a reason for hiding this comment

Uh oh!

achow101 Sep 3, 2021

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

laanwj commented Dec 2, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

glozow left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

laanwj commented Dec 9, 2021

Uh oh!

glozow left a comment

Choose a reason for hiding this comment

Uh oh!

glozow Dec 9, 2021

Choose a reason for hiding this comment

Uh oh!

maflcko left a comment

Choose a reason for hiding this comment

Uh oh!

maflcko Dec 9, 2021

Choose a reason for hiding this comment

Uh oh!

maflcko Dec 13, 2021

Choose a reason for hiding this comment

Uh oh!

maflcko Dec 9, 2021

Choose a reason for hiding this comment

Uh oh!

Uh oh!

achow101 commented May 21, 2021 •

edited

Loading

DrahtBot commented May 22, 2021 •

edited

Loading

laanwj commented Dec 2, 2021 •

edited

Loading