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
- At high feerates, using unnecessary inputs can significantly increase the fees
- Users are upset when fees are relatively large compared to the amount sent
- Minimizing the input set is an NP-hard problem
- Always minimizing the weight of the input set can lead to fragmentation of the wallet’s UTXO pool
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 c of 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 exceeds c + 3 output 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.
