Add Gutter Guard Selector #28977
Add Gutter Guard Selector #28977
Conversation
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. Code CoverageFor detailed information about the code coverage, see the test coverage report. ReviewsSee the guideline for information on the review process.
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update. 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. |
884bfb2 to
d0f8d9e
Compare
d0f8d9e to
1e19f92
Compare
Does a random selection limited to three more output groups than largest-first selection would select to fund the transaction. If the limit is exceeded during selection, the output group with the lowest effective value is discarded.
1e19f92 to
4a94fc8
Compare
|
tested ACK 4a94fc8 I read through the conversation, understood the problem and use case for this solution, compiled from source, wrote tests similar to those included |
|
Is there a benefit to using SRD here over something oldest first? We are already doing SRD so it might be better to use a different underlying strategy. Having a selection based on oldest first would also be useful for consuming negative EV UTXOs at very low feerates, e.g. less than 3 s/vb. It also seems like having the limit be inversely scaled by feerate would be better than the fixed limit. That way, as the feerates increase, we get less consolidatory instead of current behavior where it switches at a particular threshold. |
|
Yeah, oldest first might be better for soaking up tiny UTXOs at low feerates that have been piling up during bouts of high feerates. @achow101: What do you think about one of the two like the following progression
† allow negative effective value inputs Additionally the unneeded UTXOs should be bounded dependent on the count of the wallet UTXO pool such as the minimum of this progress and e.g. 10% of the wallet’s UTXO count. I guess I’ll have to simulate this. |
|
🐙 This pull request conflicts with the target branch and needs rebase. |
|
Closing as this is going to be superseded by Sand Compactor |
Please refer to the topic on Delving Bitcoin discussing Gutter Guard/Coingrinder simulation results.
Gutter Guard Selector bounds the worst case on coin selection outcomes by ensuring that there is at least one candidate input set that exceeds the minimal necessary input count by at most three.
Does a random selection limited to three more output groups than largest-first selection would select to fund the transaction. If the limit is exceeded during selection, the output group with the lowest effective value is discarded.
Motivations
Approach
Bitcoin Core uses multiple coin selection algorithms to generate candidate input sets. It then picks the least wasteful input set per the weight metric, but none of the deployed algorithms explicitly look for low-weight input sets. Gutter Guard Selector determines a likely minimum count
cof output groups that are necessary to fund the transaction via largest-first selection. It then randomly selects output groups into a lowest-effective-value heap. If the heap exceedsc + 3output groups, the output group with the lowest-effective value is discarded. It then checks whether the selection can fund the transaction. This approach will always succeed given the effective value available exceeds the selection target.Trade-offs
Largest-first selection (LF) (and to a lesser degree an approach that minimizes the weight of an input set) might grind a wallet’s UTXO pool to dust if overused. Incoming payments grow the wallet’s UTXO pool, while transactions with a single input and a change output result in the same UTXO count as before. LF will additionally decrease range of amounts in the wallet by reducing the amount of the supreme element.
Branch and Bound looks for a changeless input set. If there are multiple solutions, it prefers the one with the lowest waste, but there might not be a solution, or even the least wasteful one could be composed of many inputs. Knapsack minimizes the distance between target amount and selected amount which is independent from the input set’s weight. Single Random Draw just does a single random drawing from the UTXO pool—if there are a ton of UTXOs in the wallet, this will likely result in a large input set. While we pick the least wasteful among the presented input set candidates, there is no guarantee that any of the three deployed algorithms will produce a thrifty input set.
In contrast, Gutter Guard Selector is expected to reduce the UTXO pool of a fragmented wallet by at least three UTXOs. When many UTXOs exist that are larger than the target, a solution with fewer inputs and less weight may be found. When transactions with low feerates are being built, the waste metric prefers heavier input sets which may be proposed by other coin selection algorithms anyway. At high feerates, Gutter Guard Selector ensures that there is an input set candidate that isn’t absurdly wasteful and therefore delimits the worst case.