Overview
Coin selection is the process by which a Bitcoin wallet automatically chooses which UTXOs (unspent transaction outputs) to use as inputs when building a transaction. This decision has significant implications for transaction fees, privacy, and the long-term health of the wallet's UTXO pool. A good coin selection algorithm minimizes fees, avoids unnecessary change outputs, and resists creating dust or linking unrelated addresses.
When a user wants to send 0.05 BTC but holds their balance across dozens of UTXOs of varying sizes, the wallet must decide which combination of UTXOs to spend. This is a variant of the subset sum problem — an NP-hard computational problem — which means wallets rely on heuristics rather than computing the mathematically optimal solution for every transaction.
Common Algorithms
Example: Sending 0.03 BTC from a wallet with these UTXOs:
A: 0.01 BTC B: 0.02 BTC C: 0.05 BTC
D: 0.005 BTC E: 0.03 BTC F: 0.10 BTC
Algorithm Selected Change Notes
────────────────────────────────────────────────────────────
Largest First F (0.10) ~0.07 BTC Large change output
Smallest First D+A+B (0.035) ~0.005 BTC Consolidates small UTXOs
Branch & Bound E (0.03) 0 (exact!) No change output needed
Knapsack A+B (0.03) ~0 BTC Random walk approximation
Bitcoin Core's Approach
Bitcoin Core has evolved its coin selection strategy over the years. The current approach uses a multi-strategy pipeline:
- Branch and Bound (BnB): First attempts to find an exact match — a set of UTXOs whose total value equals the payment amount plus fees, producing no change output. This is the ideal outcome.
- Knapsack solver: If no exact match exists, falls back to a randomized approximation that tries to minimize the change output.
- Single Random Draw (SRD): Randomly selects UTXOs until the target is met, providing a baseline solution.
The wallet then compares the solutions from each strategy and selects the one with the lowest "waste metric" — a score that accounts for current fees, future fees to spend the change, and the cost of creating excess inputs.
Privacy Implications
Coin selection has direct privacy consequences that most users are unaware of:
- Input merging: Using multiple UTXOs in one transaction tells an observer they belong to the same entity (the common input ownership heuristic used in chain analysis)
- Change output creation: Change outputs are linked to the sender, and analysts use various heuristics to identify which output is the payment and which is change
- UTXO consolidation timing: Merging small UTXOs during low-fee periods is cost-effective but reveals address linkage
Privacy-focused wallets may use different coin selection strategies, such as selecting a single UTXO that covers the payment (avoiding input merging) or preferring UTXOs from CoinJoin rounds.
Fee Optimization
The choice of inputs directly affects the transaction's fee because each input adds to the transaction's size (and therefore its fee rate cost):
Input sizes by type:
┌─────────────────────┬──────────────┐
│ Input Type │ Size (vBytes)│
├─────────────────────┼──────────────┤
│ P2PKH (Legacy) │ 148 │
│ P2SH-P2WPKH (Nested)│ 91 │
│ P2WPKH (SegWit) │ 68 │
│ P2TR (Taproot) │ 57.5 │
└─────────────────────┴──────────────┘
Using fewer, larger UTXOs = fewer inputs = lower fee
Using many small UTXOs = more inputs = higher fee
A well-designed coin selection algorithm balances immediate fee costs against the future cost of spending change outputs, recognizing that today's change output is tomorrow's input.
Coin Selection vs. Coin Control
Coin selection is the automatic process; coin control is the manual override. When a user exercises coin control, they bypass the wallet's algorithm and explicitly choose which UTXOs to spend. Privacy-conscious users often prefer coin control, especially when managing UTXOs from different contexts (e.g., KYC exchanges versus peer-to-peer transactions).
Related Concepts
- UTXO — the inputs that coin selection algorithms choose from
- Fee — the cost that coin selection directly influences
- Change Address — the output created when selected inputs exceed the payment amount
- Coin Control — the manual alternative to automatic coin selection
- Dust — uneconomical UTXOs that coin selection must handle carefully