wallet: Decide which coin selection solution to use based on waste metric #22009
Conversation
|
Note that there will be a followup PR to this which introduces a struct that encapsulates the selection. This struct will also do the waste calculation which will remove the ugly tuples stuff that is currently done to allow for the waste calculation. |
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. ConflictsReviewers, this pull request conflicts with the following ones:
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. |
|
With #17331 now merged, this is ready for review. |
sipa
left a comment
sipa
left a comment
There was a problem hiding this comment.
Does this introduce any behavior changes besides the long-term feerate change?
I would think not, as the BNB search always has waste 0, so if it works, it will still always be chosen?
There is a behavior change as BnB can non-zero waste. Part of the waste is the excess thrown away to fees. Because BnB uses a matching window, it is possible for it to have an excess which is included as part of the waste calculation. Additionally, the difference between the fee and the long term fee is usually non-zero, so the waste is also usually non-zero. The main result of this behavior change is that when target feerate is less than the long term feerate, we will choose the result that consolidates more. This is because the difference between the fee and the long term fee will be negative which generally makes the waste negative. When you have more inputs, the waste will be more negative, and so the most negative solution is used. When the target feerate is greater than the long term feerate, then we will choose the result that pays the least fees. This is because the difference between the fee and the long term fee is positive, so the waste is generally positive. With less inputs, both the waste and fees will be lower, so we end up choosing the solution with lower fees. This strategy does not necessarily mean that one algorithm will tend to be chosen over another, but rather as a standard way to measure how "good" they are. |
|
@achow101 Oh, of course. Thanks for reminding me on the point of the waste metric. |
jarolrod
left a comment
jarolrod
left a comment
There was a problem hiding this comment.
Concept ACK
This is interesting. This allows us to decide which algorithm to use by examining, what can be considered, the opportunity cost of each coin selection algorithm.
The long term feerate is really the highest feerate that the user is comfortable with making consolidatory transactions. This is should thus be something that can be configured by the user via a new startup option -consolidatefeerate. The default value is 10 sat/vbyte, chosen arbitrarily (it seems like a reasonable number).
Instead of calling AttemptSelection with the hopes/instruction that it uses BnB, call SelectCoinsBnB directly to test it.
In order to change the KnapsackSolver tests to call KnapsackSolver, we need KnapsackGroupOutputs to create the OutputGroups filtered with the filter criteria.
When doing the coin selector tests for KnapsackSolver, call it directly instead of using AttemptSelection and hoping/instructing it uses KnapsackSolver. -BEGIN VERIFY SCRIPT- sed -i 's/testWallet\.AttemptSelection( /KnapsackSolver(/g' src/wallet/test/coinselector_tests.cpp sed -i 's/testWallet\.AttemptSelection(/KnapsackSolver(/g' src/wallet/test/coinselector_tests.cpp sed -i 's/, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params)/, KnapsackGroupOutputs(filter_standard), setCoinsRet, nValueRet)/g' src/wallet/test/coinselector_tests.cpp sed -i 's/, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)/, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet)/g' src/wallet/test/coinselector_tests.cpp sed -i 's/, filter_standard_extra, vCoins, setCoinsRet, nValueRet, coin_selection_params)/, KnapsackGroupOutputs(filter_standard_extra), setCoinsRet, nValueRet)/g' src/wallet/test/coinselector_tests.cpp sed -i 's/BOOST_CHECK( /BOOST_CHECK(/g' src/wallet/test/coinselector_tests.cpp -END VERIFY SCRIPT-
Tests for some waste calculation scenarios add_coin is modified to allow fee and long term fee to be set for an added CInputCoin.
Instead of always choosing BnB if it finds a solution, always do both BnB and KnapsackSolver and choose the one which has the least waste.
|
reACK 86beee0 via git range-diff fe47558...86beee0 |
|
re-utACK 86beee0 |
glozow
left a comment
glozow
left a comment
There was a problem hiding this comment.
post merge ACK 86beee0 via git range-diff fe47558...86beee0
changes were addressing #22009 (comment), #22009 (comment), #22009 (comment)
| // 0 Waste only when fee == long term fee, no change, and no excess | ||
| add_coin(1 * COIN, 1, selection, fee, fee); | ||
| add_coin(2 * COIN, 2, selection, fee, fee); | ||
| const CAmount exact_target = in_amt - 2 * fee; | ||
| BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, 0, exact_target)); |
There was a problem hiding this comment.
As it was discussed in the review club, there are more scenarios when the waste can be zero. Thus the "only" doesn't seem appropriate here.
I went ahead and opened another PR fixing this with addition of those extra cases. #22938.
…algorithm 3633b66 Use SelectCoinsSRD if it has less waste (Andrew Chow) 8bf789b Add SelectCoinsSRD function (Andrew Chow) 2ad3b5d tests: wallet_basic lock needed unspents (Andrew Chow) b77885f tests: wallet_txn explicilty specify inputs (Andrew Chow) 59ba7d2 tests: rpc_fundrawtx better test for UTXO inclusion with include_unsafe (Andrew Chow) a165bfb tests: rpc_fundrawtx use specific inputs for unavailable change test (Andrew Chow) df765a4 tests: rpc_fundrawtx lock to UTXO types (Andrew Chow) Pull request description: To ease in the use of SRD as our fallback mechanism, this PR adds it as a secondary fallback algorithm in addition to the knapsack solver. Since #22009, the solution with the least waste will be chosen. This pattern is continued with SRD simply being another solution whose waste is compared. ACKs for top commit: glozow: reACK 3633b66 via `git range-diff 981b9d1...3633b66`, thanks for taking the suggestions laanwj: Concept and code review ACK 3633b66 Tree-SHA512: 895659f553fea2230990136565bdf18b1328de8b0ce47f06b64bb4d69301f6dd68cb38debe5c24fb6de1317b735fc020a987c541f00bbea65229de47e53adf92
…te_test efcaefc test: Add remaining scenarios of 0 waste (rajarshimaitra) Pull request description: As per the [review club](https://bitcoincore.reviews/22009) discussion on #22009 , it was observed that there were other two fee scenarios in which selection waste could be zero. These are: - (LTF - Fee) == Change Cost - (LTF - Fee) == Excess Even though these are obvious by the definition of waste metric, adding tests for them can be helpful in explaining its behavior to new readers of the code base, along with pinning the behavior for future. This PR adds those two cases to waste calculation unit test. Also let me know if I am missing more scenarios. ACKs for top commit: jonatack: Tested re-ACK efcaefc achow101: ACK efcaefc meshcollider: ACK efcaefc Tree-SHA512: 13fe3e2c0ea7bb58d34e16c32908b84705130dec16382ff941e5e60ca5b379f9c5811b33f36c4c72d7a98cfbb6af2f196d0a69e96989afa4b9e49893eaadd7cb
…oin selection solution 05300c1 Use SelectionResult in SelectCoins (Andrew Chow) 9d9b101 Use SelectionResult in AttemptSelection (Andrew Chow) bb50850 Use SelectionResult for waste calculation (Andrew Chow) e8f7ae5 Make an OutputGroup for preset inputs (Andrew Chow) 51a9c00 Return SelectionResult from SelectCoinsSRD (Andrew Chow) 0ef6184 Return SelectionResult from KnapsackSolver (Andrew Chow) 60d2ca7 Return SelectionResult from SelectCoinsBnB (Andrew Chow) a339add Make member variables of SelectionResult private (Andrew Chow) cbf0b9f scripted-diff: Use SelectionResult in coin selector tests (Andrew Chow) 9d1d86d Introduce SelectionResult struct (Andrew Chow) 94d851d 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 05300c1 Tree-SHA512: e4dbb4d78a6cda9c237d230b19e7265591efac5a101a64e6970f0654e2c4f93d13bb5d07b98e8c7b8d37321753dbfc94c28c3a7810cb1c59b5bc29b08a8493ef
ghost
mentioned this pull request
… same as GetSelectionWaste ec7d736 [wallet] assert BnB internally calculated waste is the same as GetSelectionWaste() (glozow) Pull request description: #22009 introduced a `GetSelectionWaste()` function to determine how much "waste" a coin selection solution has, and is a mirror of the waste calculated inside of `SelectCoinsBnB()`. It would be bad for these two waste metrics to deviate, since it could negatively affect how often we select the BnB solution. Add an assertion to help tests catch a potential accidental change. ACKs for top commit: achow101: ACK ec7d736 Xekyo: ACK ec7d736 Tree-SHA512: 3ab7ad45ae92e7ce3f21824fb975105b6be8382edf47c252df5d13d973a3abdcb675132d223b42fcbb669cca879672c904b8a58d0676e12bf381a9219f4db37c
16 participants
Branch and Bound introduced a metric that we call waste. This metric is used as part of bounding the search tree, but it can be generalized to all coin selection solutions, including those with change. As such, this PR introduces the waste metric at a higher level so that we can run both of our coin selection algorithms (BnB and KnapsackSolver) and choose the one which has the least waste. In the event that both find a solution with the same change, we choose the one that spends more inputs.
Also this PR sets the long term feerate to 10 sat/vb rather than using the 1008 block estimate. This allows the long term feerate to be the feerate that we switch between consolidating and optimizing for fees. This also removes a bug where the long term feerate would incorrectly be set to the fallback fee. While this doesn't matter prior to this PR, it does have an effect following this. The long term feerate can be configured by the user through a new
-consolidatefeerateoption.