Bitcoin Coin Selection

Coin Selection

Coin selection chooses which subset of available UTXOs to spend for a target amount + fee. Trade-offs: fee minimization, privacy, change-output dust avoidance, UTXO-set hygiene.

Inputs to the algorithm

• Target amount (T).
• Fee rate (r sat/vB).
• Available UTXOs { (value_i, vsize_when_spent_i) }.
• Per-output-type vsize constants (P2WPKH ~ 68 vB to spend, P2TR ~ 57 vB).
• Min change amount (dust threshold + small overhead).

Algorithm 1: Branch and Bound (BnB)

Bitcoin Core's primary algorithm (Murch 2017).

Goal: find a subset that sums exactly to T + fee + change_buffer, avoiding change output entirely.

branch_and_bound(utxos, target):
  utxos.sort_by(value, descending)
  best = None
  recurse(included=[], remaining=utxos, sum=0):
    if sum > target + threshold: return  # exceed
    if abs(sum - target) <= waste_metric:
      best = included; return
    if remaining empty: return
    # branch: include / exclude next utxo
    recurse(included + [head], tail, sum + head.value)
    recurse(included, tail, sum)

Backtracking with pruning. If BnB finds an exact-match solution (within rounding), no change output needed → saves the cost of a change output (~31 vB for P2WPKH change).

If BnB fails (no exact match), wallet falls back to knapsack or SRD.

Algorithm 2: Knapsack

Heuristic: iterate UTXOs, include each if it fits, else continue. Simple but may select more inputs than necessary. Pre-Murch default.

Algorithm 3: Single Random Draw (SRD)

Randomly draw UTXOs until sum ≥ target + fee. Privacy-friendly: no heuristic-readable patterns from chain analysis.

srd(utxos, target):
  shuffle(utxos)
  selected = []; sum = 0
  for u in utxos:
    selected.push(u); sum += u.value
    if sum >= target + fee_for_count(len(selected)): break
  return selected

Waste metric (Murch)

Defines "best" selection as one that minimizes:

waste = excess + change_cost + (input_count - 1) * fee_per_input

• excess = sum(selected) - target - change.
• change_cost = vsize of change output × fee rate (cost of the change output) + future cost to spend that change later.

Wallets use this to compare candidate solutions.

Change avoidance

If sum(selected) is within ~$change_threshold$ of target (typically ~1000 sats above), spend everything as fee instead of creating dusty change. Algorithmic threshold = change_cost.

UTXO consolidation

When fee rates are low, batch many UTXOs into one output. Saves future tx fees but reveals on-chain history correlation.

• Privacy cost: consolidates the chain-analysis cluster into one identifiable cluster.
• Mitigation: use CoinJoin before consolidation, or consolidate within a single account that's already correlated.

Privacy-aware selection

Heuristics chain analysts use:

• Common Input Ownership Heuristic — multiple inputs in one tx likely owned by same entity. Mitigation: include only one UTXO per tx when feasible.
• Round-amount payment heuristic — round payment outputs are likely the recipient. Mitigation: avoid round amounts.
• Same-script-type clustering — tx with all P2WPKH inputs from one wallet style. Mitigation: vary script types across wallets.

Privacy-focused wallets (Wasabi, Sparrow with PayJoin) use SRD to avoid heuristic-friendly patterns.

Implementations

Common bugs

• Selecting the largest UTXO regardless of need → big change output, high fees.
• Not accounting for fee rate when computing the target → underpaid fee → tx stuck.
• Treating dust outputs (< 546 sats P2PKH, < 294 sats P2WPKH) as spendable in the future → unspendable, just dead weight.
• Forgetting that change output adds vbytes (~31 P2WPKH change ≈ 124 WU).

See also

• fee-estimation/SKILL.md
• rbf-cpfp/SKILL.md
• ../privacy/coinjoin/SKILL.md