Coin Selection Algorithm

What Is a Coin Selection Algorithm?

A coin selection algorithm is the process a Bitcoin wallet uses to decide which unspent transaction outputs to consume when building a new transaction. Because Bitcoin tracks balances as discrete coins (UTXOs) rather than a single account balance, every spend requires the wallet to assemble a set of inputs whose combined value covers the payment amount plus fees.

The choice of which coins to spend has cascading effects. Selecting too many inputs inflates the transaction weight and increases fees. Selecting too few may require a change output, which adds cost now and creates a small UTXO that costs fees to spend later. Combining coins from different sources links them on-chain via the common-input-ownership heuristic, degrading privacy. A good coin selection algorithm navigates all of these trade-offs automatically.

Mathematically, coin selection is a variant of the subset sum problem, which is NP-hard. Wallets therefore rely on heuristic algorithms that find good (but not always optimal) solutions within practical time limits.

How It Works

When a wallet constructs a transaction, it follows a general sequence: enumerate eligible UTXOs, run one or more selection algorithms, compare results using a scoring function, and build the transaction with the winning input set. Bitcoin Core (as of v27.0+) runs four algorithms and selects the result with the lowest waste score.

Branch and Bound (BnB)

Introduced in Bitcoin Core v0.17.0 (October 2018) via PR #10637, Branch and Bound searches for an exact-match input set that eliminates the change output entirely. The algorithm is based on Mark Erhardt's (Murch's) master's thesis at the Karlsruhe Institute of Technology.

BnB constructs a binary decision tree where each level represents including or excluding a specific UTXO. It sorts UTXOs by effective value (face value minus the fee cost to spend that input) in descending order, then performs a depth-first search. Branches are pruned when the running total exceeds the target range or when the remaining UTXOs cannot reach it. The algorithm explores up to 100,000 combinations before falling back to other methods.

The "target range" includes a tolerance window: if the total inputs exceed the payment plus fees by less than the cost of creating and later spending a change output, BnB accepts the slight overpayment as preferable to generating change. This makes changeless transactions more common.

Knapsack Solver

The Knapsack solver is Bitcoin Core's legacy algorithm, present since the earliest versions. It uses stochastic approximation: over 1,000 randomized iterations, it includes each UTXO with a 50% probability on a first pass, then fills the gap with remaining UTXOs on a second pass. The iteration that produces the smallest excess over the target wins.

Knapsack almost always produces a change output, but its randomization provides a privacy benefit: the same wallet builds different input sets for similar transactions, making fingerprinting harder.

CoinGrinder

Added in Bitcoin Core v27.0 (April 2024) via PR #27877, CoinGrinder searches for the input set with the minimum transaction weight. It only activates at elevated feerates (by default, when the current feerate is at least three times the long-term consolidation feerate, typically 30+ sat/vB). At high fees, minimizing input count directly saves money. At normal fees, this strategy would grind the UTXO pool into increasingly small fragments over time, which is why it remains dormant during low-fee periods.

Single Random Draw (SRD)

Shipped in Bitcoin Core v23.0, Single Random Draw randomly shuffles all eligible UTXOs and greedily adds them until the target amount is reached. Despite its simplicity, simulations showed SRD was selected as the winner roughly one-third of the time, outperforming the Knapsack solver in many scenarios.

The Waste Metric

After all algorithms produce candidates, Bitcoin Core scores each result using the waste metric (introduced in PR #22009). The formula:

waste = timing_cost + change_cost + excess_amount

timing_cost  = input_weight × (current_feerate − long_term_feerate)
change_cost  = fee_to_create_change + fee_to_spend_change_later
excess_amount = overpayment when no change output is created

The timing cost penalizes spending many inputs when fees are high (positive value) and rewards consolidation when fees are low (negative value). The long-term feerate defaults to 10 sat/vB and is configurable via the -consolidatefeerate setting. When waste scores are tied, Bitcoin Core prefers the result that spends more inputs, consolidating the UTXO set opportunistically.

Other Common Algorithms

Wallet implementations beyond Bitcoin Core use a variety of simpler strategies:

For a deeper look at how input selection affects on-chain costs, see the research article on Bitcoin fee market dynamics.

Privacy Implications

Coin selection is one of the most significant factors in Bitcoin on-chain privacy. When a transaction has multiple inputs, chain analysis firms assume all inputs belong to the same entity: the common-input-ownership heuristic. This assumption is the foundation of nearly all blockchain surveillance.

Combining a UTXO received from a KYC exchange with a UTXO from a non-KYC source permanently links those coins on-chain. Consistent selection patterns (always largest-first, for example) can also fingerprint a wallet implementation, revealing which software created the transaction.

Users who need fine-grained control over which UTXOs are spent together can use coin control: a manual override that lets the user hand-pick inputs instead of relying on automatic selection. Privacy-enhancing techniques like CoinJoin and PayJoin further break the common-input heuristic by mixing inputs from multiple participants in a single transaction.

For a comprehensive overview of on-chain privacy techniques, see the Bitcoin privacy landscape research article.

Use Cases

Fee Optimization

Each input adds weight to a transaction: roughly 68 vBytes for native SegWit inputs and up to 148 vBytes for legacy inputs. At a feerate of 50 sat/vB, each additional SegWit input costs approximately 3,400 sats. A smart coin selection algorithm minimizes the number of inputs (and avoids unnecessary change outputs) to keep fees low, especially during high-fee periods driven by mempool congestion.

UTXO Set Management

Over time, wallets accumulate many small UTXOs from incoming payments. Without deliberate management, these fragments become uneconomical to spend when fees rise. A well-designed coin selection algorithm performs opportunistic UTXO consolidation: when fees are low, it prefers to include more inputs than strictly necessary, merging small UTXOs into a single larger change output. The waste metric drives this behavior automatically by making extra inputs "free" or even beneficial below the long-term feerate.

Merchant and Exchange Wallets

High-volume wallets process hundreds or thousands of withdrawals per day. Coin selection becomes critical at this scale: poor selection can cost thousands of dollars in excess fees daily. Many exchanges use custom algorithms tuned for batched transactions, where a single transaction pays multiple recipients, changing the optimization calculus significantly.

Risks and Considerations

Dust Accumulation

Naive algorithms like largest-first progressively fragment the wallet into smaller UTXOs. Once a UTXO's value drops below the cost to spend it (a condition sometimes exploited in dust attacks), it becomes stranded. The Bitcoin network enforces a dust limit of 546 satoshis for legacy outputs and 294 satoshis for SegWit outputs, below which transactions are rejected by default relay policy. In practice, UTXOs under roughly 10,000 sats may be uneconomical to spend during fee spikes.

Privacy Degradation

Automatic coin selection can unknowingly combine UTXOs from different privacy contexts. A wallet that mixes exchange-sourced coins with privately received coins creates a permanent, public link between those sources. Users who value privacy should review their coin control settings and consider labeling UTXOs by source.

Computational Cost

Wallets with very large UTXO pools (thousands of coins) can experience noticeable delays during coin selection. Bitcoin Core caps its Branch and Bound and CoinGrinder searches at 100,000 combinations to keep selection time reasonable, but the Knapsack solver's 1,000 iterations still add latency in extreme cases.

How Spark Eliminates the Problem

The coin selection problem is inherent to the UTXO model: every on-chain spend requires choosing inputs, paying per-input fees, and managing change. Layer 2 protocols like Spark remove this overhead entirely.

On Spark, transfers happen off-chain through key rotation rather than on-chain transactions. There are no inputs to select, no change outputs to create, and no per-byte fees to optimize. A user who received a thousand small payments has the same transfer cost as one who received a single large deposit. For a detailed comparison, see the research article on the UTXO model vs. account model.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.