Goals of Coin Selection
The challenge for picking a Coin Selection algorithm is that there are multiple goals to optimize for:
Privacy
A wallet's default behavior should be reasonable conducive to the users' financial privacy. The Coin Selection should reveal as little as possible about the wallet contents. Wallets should avoid linking too many addresses, not reveal excessive funds when unnecessary, minimize discernible patterns and fingerprints, but also maintain sufficient UTXOs to spread the balance out. Wallets should never reuse addresses.
Transaction Fee
The Coin Selection must aim to curtail the transaction fee for current transactions, but also minimize the total transaction fees in the long term. Since every UTXO must be spent eventually, it may be sometimes opportune to spend more UTXOs at a low feerate now, than at a high feerate later.
UTXO pool shaping
Dust should always be avoided, but generally small UTXOs will have a large relative cost at elevated feerates, so we should aim to avoid creating tiny change outputs. As a rule of thumb, wallets should not create UTXOs that cost a significant chunk of their value at moderate feerates. Aim for change to be at least 20–50k sats (less for smaller, more for larger input scripts).
Curtail UTXO set size
All UTXOs have to be stored on every full node, and all UTXOs have to be spent eventually. A wallet should keep sufficient UTXOs to maintain financial privacy, but as few as possible to minimize future blockchain data, fees, and the on-going storage cost on every full node.
Unfortunately, some of these goals are antagonal, and therefore every solution must find an appropriate balance for its priorities.
Common algorithms
Let's go over some of the most common algorithms for coin selection, as well as their advantages and disadvantages. We'll look at:
- Oldest first (FIFO)
- Newest first (LIFO)
- Smallest first
- Largest first
- Random
- Knapsack (used by Bitcoin Core)
- Branch and Bound (used by Bitcoin Core)
- Multi-algorithm (used by Bitcoin Core)
Oldest first (FIFO)
Pick UTXOs in order of descending confirmation count.
Good
- Will consolidate small UTXOs eventually as they come up
- Input sets are representative of your UTXO pool's composition, neither particularly small or large
- Will transition wallet's UTXO pool to the new output format when a new output type is adopted for receiving
- Will spend UTXOs from same period of time together which may reduce mixing of fingerprints due to different software versions
Bad
- Gives a date for the oldest UTXO in the wallet, which e.g. reveals how long a user at least has been using this wallet
- The values and confirmation count spacing of UTXOs may be used to estimate total wallet balance
- The timestamp ranges on different transactions may form a serial pattern allowing to associate different transactions of the same wallet and to disambiguate it from other wallets using the same software (since time stamp ranges should never overlap except in last or first confirmation height)
- Might be used to infer information about a wallet by watching when a known output is spent
- Will not minimize the transaction fee
Newest first (LIFO)
Pick UTXOs with lowest confirmation count first.
Good
- Most UTXOs have a small transaction graph, which may be beneficial for privacy
- Spent UTXOs are closest in acquisition value to value at spending time resulting in smallest effective gain/loss
Bad
- Hardly any consolidation at all if wallet's funds are increasing over time
- Grinds latest UTXO down, until a newer is received or it is used up. May result in the wallet's UTXO pool having lots of small UTXOs.
- Will combine the extensive transaction graphs of multiple youngest UTXOs when a larger amount is sent
- Will link up all your recent activity by always reusing the newest change output
- Will not minimize transaction fee
Smallest first
Pick UTXOs in order of ascending value.
Good
- Consolidates small UTXOs ASAP, curbing the wallet's UTXO pool and minimizing future spending cost
Bad
- Reveals lower bound for current UTXO values in wallet
- Maximizes input sets which increases transaction fees for current transaction
- Tends to overconsolidate the UXTO pool, reducing financial privacy
- Links lots of addresses
- Decreases value range of wallet's UTXO pool
Largest first
Pick UTXOs in order of descending value.
Good
- Minimal transaction fees for current transaction
- Links few addresses
- Likely to create sizeable change outputs
Bad
- Reveals upper bound for UTXO value in wallet
- May reveal that wallet holds vastly more funds than necessary to make the current payment
- Links consecutive transactions while change output is still the largest UTXO
- Defers consolidation of small UTXOs, maximizing future cost
- Bloats wallet's UTXO pool (and the global UTXO set) as single recipient spends are usually ±0 on UTXO pool count (minus one input, plus one change output), but incoming transactions increase the UTXO pool
Random
Draft UTXOs with equal chance randomly from all available.
Good
- Selected UTXOs have no consistent fingerprints like age or value
- Input sets are probabilistically representative of wallet's UTXO pool composition, becoming more consolidatory when more small UTXOs are present
- Easy to implement
- Random change output amounts increase value diversity
Bad
- Does not minimize fees
- May exhibit some fingerprints randomly such as revealing much greater funds in the wallet than necessary for payment
Knapsack (used by Bitcoin Core)
This algorithm (which incidentally does not solve a Knapsack problem) approaches Coin Selection by sorting all UTXOs by value and running 1000 iterations of selections randomly picking UTXOs with a 50% chance from largest to smallest. Whenever it overshoots the target, it deselects the last included UTXO and continues with smaller UTXOs. The algorithm is described exhaustively in in What is the coin selection algorithm?.
Good
- Produces small UTXO pool
- Pseudorandom selection of UTXOs reveals little information about the wallet
Bad
- Aggressively consolidates tiny UTXOs including uneconomical outputs
- Always aims for 10 mBTC change outputs (fingerprint and unnecessarily large)
- With a lot of small UTXOs in your wallet, likely to cause big transaction fees
- Unnecessarily expensive computation
Branch and Bound (used by Bitcoin Core since v0.17)
Deterministically search the UTXO pool's combination space for the least wasteful change-avoidant input set. Since there not always is a changeless input set, Bitcoin Core falls back to using the above described "Knapsack" approach in that case.
Good
- Creates no change output which reduces current fees, future fees, cuts transaction graph for wallet, and has consolidatory effect on wallet's UTXO pool
- Uses minimal input set among viable candidates reducing address linkage and fees
- Selected UTXOs have no consistent fingerprints like age or value
- Uses more inputs at lower feerates and fewer inputs at higher feerates due to waste metric
- Prefers spending less blockspace efficient output types at lower feerates and more efficient output types at higher feerates due to waste metric
Bad
- Does not always produce a solution
- Sender cannot CPFP since there is no change output
- More complicated to implement and expensive to compute
Multi-algorithm (to be used by Bitcoin Core v23+)
The next release after Bitcoin Core 22.0 will run Knapsack, Single Random Draw, and Branch and Bound coin selection in parallel and then choose among the three resulting input set candidates the one that scores best according to the waste heuristic, which was previously already used to pick the best Branch and Bound solution.
Good
- Spends more inputs at low feerates, fewer at high feerates reducing total fees
- Consolidates small inputs when economically sensible
- Since input sets are sourced from multiple approaches, patterns are more difficult to identify
- Often avoids change, improving privacy, fees and reducing linkage
Bad
- Complicated to implement and test
- Computationally intensive to compute
- Still uses a fairly high minimum change of 10 mBTC (when change is produced)
Update in Nov 2021:
- Remove ambiguous use of term "dust"
- Complete rewrite to update to my current understanding
- Add Random Selection, Branch and Bound, and Bitcoin Core's multi-algorithm approach
Update in 2021:
- Removed a few allusions to Coin Age Priority as transaction selection policy in block building which was removed in Bitcoin Core 0.12.0 in 2016.
- Removed erroneous claim that spending multiple inputs from the same address is cheaper
Note that Bitcoin Core used the Knapsack solver as its only algorithm until 2017, but since then has added an improved algorithm proposed by the author of this answer.
Update in 2014:
I have been looking into coming up with a better Coin Selection Algorithm, but haven't found one yet that significantly improves on the Core Client Selection Algorithm.
Here are some ideas to improve it:
- When a UTXO is randomly selected, add all other UTXOs associated with the same address as well: less linking of transactions improves privacy, potentially consolidates UTXOs into fewer.
- Instead of selecting the smallest change, one could aim to create a change of the same size as the spending target. Assuming that people mostly send useful amounts, this would create new UTXOs of useful value instead of the smallest possible changes as it currently does. It also makes it harder to guess what was the change and what was the payment.
- Select UTXO set to minimize transaction fee, instead of minimizing change output.
