Bitcoin Coin Selection Algorithms: Branch-and-Bound, SRD, and Knapsack Compared

Every Bitcoin transaction begins with a decision most users never see: which UTXOs should the wallet select as inputs? Given a target payment amount, a wallet must choose from its pool of unspent outputs to construct a transaction that covers the payment, the network fee, and ideally nothing more. This is the coin selection problem, and the algorithm a wallet uses has direct consequences for fees, privacy, and long-term UTXO set health.

Bitcoin Core has iterated on coin selection for over a decade, evolving from a single heuristic to a multi-algorithm framework that runs four strategies in parallel and picks the best result. This article compares each algorithm: Knapsack, Branch-and-Bound, Single Random Draw, and the newest addition, CoinGrinder. We will examine how each one works, when each excels, and what tradeoffs they impose.

Why Coin Selection Matters

Bitcoin does not have accounts with balances. Instead, each wallet holds a collection of discrete UTXOs, each representing an output from a prior transaction that has not yet been spent. When you want to send 0.05 BTC, your wallet cannot simply debit a balance. It must select one or more of these UTXOs as transaction inputs, construct outputs for the recipient and (usually) for change, and pay a fee proportional to the transaction weight.

A naive approach (just pick the biggest UTXO) creates problems over time. It fragments the wallet into many small dust-sized change outputs, wastes fees by including more bytes than necessary, and links addresses together in ways that chain analysis firms exploit. Good coin selection balances three competing objectives:

• Minimize current transaction fees (fewer or smaller inputs reduce weight)
• Minimize future costs (avoid creating uneconomical change outputs)
• Preserve privacy (reduce the information leaked through input selection patterns)

The Effective Value Model

Before comparing algorithms, it helps to understand the concept of effective value, which underpins modern coin selection in Bitcoin Core. Each UTXO has a face value (the amount of bitcoin it holds) and a cost to spend (determined by its input weight multiplied by the current feerate). The effective value is the difference:

effectiveValue = utxo.value - feePerByte × inputWeight

A UTXO with a face value of 1,000 sats and a spending cost of 1,200 sats at the current feerate has a negative effective value. Including it in a transaction would cost more than it contributes. Bitcoin Core filters out such UTXOs before coin selection begins, preventing algorithms from selecting inputs that are uneconomical to spend.

Effective values shift with feerates: A UTXO that is economical to spend at 5 sat/vB may become uneconomical at 50 sat/vB. This means your spendable balance can appear to shrink during fee spikes, even though the UTXOs still exist on chain.

Knapsack: The Original Heuristic

The Knapsack solver was Bitcoin Core's primary coin selection algorithm from its earliest versions through version 0.16. At its core, it treats coin selection as a variant of the Subset Sum problem (which is NP-complete) and uses stochastic approximation to find a workable solution.

How Knapsack works

The algorithm runs 1,000 iterations of a randomized selection process. In each iteration, it sorts all eligible UTXOs by value (largest first), then walks through the list with a 50% random inclusion probability for each UTXO. If the running total reaches the target, the algorithm records the selection. After all iterations, the selection with the smallest overshoot wins.

Two special cases short-circuit the process: if any single UTXO exactly matches the target, it is returned immediately. If the smallest UTXO larger than the target produces less waste than the best combination found, that single UTXO is preferred.

Knapsack limitations

The randomized nature of Knapsack creates several problems. Running the same wallet with the same UTXO set can produce different transaction inputs on different runs, making behavior unpredictable and harder to test. The algorithm frequently overshoots the target by significant amounts, creating unnecessary change outputs that add weight to the current transaction and create future spending costs. The 1,000 iterations also make it computationally heavier than the alternatives.

Branch-and-Bound: Exact Match Seeking

Branch-and-Bound (BnB) was introduced in Bitcoin Core 0.17.0 via PR #10637, implementing an algorithm designed by Mark "Murch" Erhardt in his 2016 Master's thesis at the Karlsruhe Institute of Technology. Andrew Chow (achow101) authored the implementation, which was merged on March 14, 2018.

The key insight behind BnB is that the most fee-efficient transaction is one with no change output at all. If a wallet can find a combination of UTXOs whose total effective value exactly matches the payment amount plus fees, the transaction avoids the approximately 34 vB cost of a change output and eliminates the future cost of spending that change.

How Branch-and-Bound works

BnB constructs a binary decision tree where each level represents a UTXO, and the two branches represent including or excluding that UTXO. The algorithm uses depth-first search, always exploring the inclusion branch first. It backtracks when any of these conditions are met:

• The current selection exceeds the target range
• The waste of the current selection exceeds the best known solution
• The remaining UTXOs cannot bring the total up to the target

A hard iteration limit of 100,000 prevents the search from running indefinitely on large UTXO sets. When BnB finds a valid solution (inputs match the target within a small tolerance), no change output is needed. The small overshoot, if any, is donated to the miner as additional fee.

Determinism matters: Unlike Knapsack, BnB is fully deterministic. Given the same UTXO set, target, and feerate, it will always produce the same result. This makes wallet behavior predictable and significantly easier to test and debug.

When Branch-and-Bound fails

BnB only succeeds when the UTXO set contains a combination that closely matches the target. With small UTXO pools or unusual target amounts, no exact match may exist within the 100,000 iteration budget. In practice, BnB finds solutions roughly 20-30% of the time depending on the wallet's UTXO composition. When it fails, Bitcoin Core falls back to other algorithms. BnB is also disabled when the "subtract fee from outputs" option is used.

Single Random Draw: Simplicity as a Feature

Single Random Draw (SRD) was added to Bitcoin Core via PR #17526, authored by Andrew Chow and merged in September 2021. It shipped in Bitcoin Core 23.0 and is remarkably concise: roughly 20 lines of code.

How SRD works

The algorithm randomly shuffles the pool of eligible UTXOs, then picks them one by one until the accumulated total is sufficient to cover the payment amount plus fees (including the cost of a change output). Whatever surplus remains becomes the change output.

That is it. No iterations, no backtracking, no optimization. SRD always produces a change output, and it makes no attempt to minimize fees directly. Its value comes from the randomness itself: by selecting unpredictably, SRD sometimes stumbles into solutions that outperform the more structured algorithms according to the waste metric.

Why randomness helps

Simulations run during the PR review showed that adding SRD to the algorithm pool reduced overall fees by approximately 6% and produced 4.4% fewer change outputs compared to using only BnB and Knapsack. SRD acts as a hedge against the structured algorithms hitting their worst cases. In the multi-algorithm comparison framework, SRD is selected roughly one-third of the time.

CoinGrinder: Optimized for High Fees

CoinGrinder is the newest coin selection algorithm in Bitcoin Core, introduced via PR #27877 by Mark Erhardt (murchandamus). It was merged on February 9, 2024 and shipped in Bitcoin Core 27.0 (released April 17, 2024).

How CoinGrinder works

CoinGrinder uses a deterministic search strategy similar to BnB, exploring the powerset of the UTXO pool, but with a different objective. Instead of seeking an exact match to avoid change, CoinGrinder seeks the input set with the minimum total weight. It always creates a change output, but it minimizes the number and size of inputs to reduce the fee paid at the current (high) feerate.

The algorithm is bounded by iteration limits to prevent excessive computation, and it uses pruning heuristics to skip branches that cannot improve on the current best solution.

Activation condition

CoinGrinder only runs when the effective feerate exceeds three times the long-term feerate estimate. With Bitcoin Core's default long-term feerate of 10 sat/vB, this means CoinGrinder activates at roughly 30+ sat/vB. This threshold exists for a reason: always minimizing the input count would fragment the wallet's UTXO pool into many small outputs over time. As Erhardt noted in the PR discussion: "minimizing the input set for all transactions tends to grind a wallet's UTXO pool to dust."

CoinGrinder simulation results

Simulations published on Delving Bitcoin showed that CoinGrinder reduced total fees by approximately 9.5% in sustained high-feerate scenarios. However, the final UTXO count was higher than the baseline (188 vs. 116 in one simulation), confirming the fragmentation tradeoff that justifies the activation threshold.

Algorithm Comparison

Each algorithm occupies a distinct niche within the coin selection framework. The following table summarizes their key properties:

The Waste Metric: Picking the Winner

Since Bitcoin Core 22.0, the wallet does not simply use one algorithm. It runs all eligible algorithms, collects their results, and selects the one with the lowest waste score. The waste metric was introduced via PR #22009 by Andrew Chow and serves as a unified cost function that accounts for both current and future spending costs.

Waste metric formula

The waste score has two components. The first captures the cost of change or excess:

• With a change output: the fee to create the change output now, plus the estimated fee to spend it later (using the long-term feerate)
• Without change (BnB solution): the small excess donated to the miner

The second component captures input timing cost:

inputCost = Σ(inputWeight × (effectiveFeerate - longTermFeerate))

When the current feerate is higher than the long-term estimate, each input adds positive waste (you are overpaying relative to average). When the current feerate is lower, each input adds negative waste, creating a bias toward spending more inputs. This is the mechanism that drives UTXO consolidation during low-fee periods.

Consolidation incentives

The waste metric's design encodes a deliberate strategy: spend more inputs when fees are cheap (consolidate the UTXO pool), spend fewer inputs when fees are expensive (preserve the pool). The long-term feerate defaults to 10 sat/vB in Bitcoin Core, configurable via the -consolidatefeerate option. When ties occur in the waste comparison, Bitcoin Core prefers the solution that spends more inputs, further encouraging consolidation.

Coin Selection and Privacy

Every multi-input transaction provides data for the common-input-ownership heuristic: the assumption that all inputs to a transaction belong to the same entity. This heuristic is widely used by chain analysis firms and is correct in the vast majority of cases (the notable exception being CoinJoin transactions).

How each algorithm affects privacy

The privacy impact differs across algorithms and fee environments:

• BnB produces the best privacy outcome when it succeeds: a changeless transaction reveals no change address and uses the fewest inputs necessary
• CoinGrinder minimizes inputs at high feerates, reducing the number of addresses linked together per transaction
• Knapsack and SRD often select more inputs than strictly necessary, linking more addresses
• Consolidation during low-fee periods (encouraged by the waste metric) deliberately links many UTXOs, trading privacy for future fee savings

Output type grouping

Bitcoin Core also implements a privacy enhancement that runs coin selection per output type before mixing types. The wallet first attempts to construct the transaction using only UTXOs of a single address type (for example, all bech32 P2WPKH outputs). Mixing address types in a single transaction reveals that the wallet holds multiple output types, which narrows the anonymity set. Only if no single-type solution exists does the wallet fall back to mixing output types.

Privacy is a spectrum: No coin selection algorithm alone provides strong privacy. Techniques like PayJoin and CoinJoin actively break the common-input heuristic, while coin control lets users manually select which UTXOs to spend. Algorithmic coin selection provides baseline privacy hygiene, not comprehensive protection.

Impact on UTXO Set Health

Over time, coin selection shapes the composition of a wallet's UTXO pool. An algorithm that consistently creates small change outputs will fragment the pool into many dust-like UTXOs that become expensive or impossible to spend during fee spikes. An algorithm that aggressively consolidates will link addresses and reduce the number of available UTXOs for future transactions.

The interplay between these effects is why Bitcoin Core runs all algorithms and compares results. No single strategy is optimal across all fee environments and wallet states. For deeper strategies on managing UTXOs over time, see our guide on Bitcoin UTXO management strategies.

The Current Bitcoin Core Pipeline

As of Bitcoin Core 27.0 and later (the pipeline remains the same through v29.0), coin selection operates as a multi-stage process:

1. Filter UTXOs by eligibility (confirmation status, effective value, output type)
2. Attempt coin selection per output type individually (for privacy)
3. Run all eligible algorithms: BnB, Knapsack, SRD, and CoinGrinder (if feerate exceeds 3x the long-term estimate)
4. Compare all valid results using the waste metric
5. Select the result with the lowest waste score (ties favor more inputs)
6. If no single-type result exists, fall back to mixed output types and repeat

This framework is extensible. Future algorithms can be added by implementing the selection logic and feeding results into the waste metric comparison. The design separates the question of "how to search" from "how to evaluate," allowing each algorithm to focus on its strength.

Coin Selection Beyond Bitcoin Core

Not all wallets use Bitcoin Core's algorithms. Many wallet implementations, particularly mobile wallets, use simpler strategies due to resource constraints or different design priorities.

Common alternative approaches

• Largest-first: always pick the biggest UTXOs. Simple but creates many small change outputs
• Smallest-first: spend dust UTXOs when possible. Cleans the pool but uses many inputs, increasing fees
• FIFO (oldest first): spend the oldest UTXOs first. Reduces the risk of address reuse detection but has no fee optimization
• Manual coin control: the user selects inputs directly. Maximum control and privacy but requires expertise

The Bitcoin Dev Kit (BDK) and LDK both implement BnB-based coin selection for applications building on top of the Bitcoin protocol. BDK's implementation closely mirrors Bitcoin Core's approach with BnB as the primary algorithm and a random fallback.

Algorithm Selection Flowchart

The following pseudocode describes Bitcoin Core's current coin selection decision process:

function ChooseSelectionResult(utxos, target, feerate):
    results = []

    // Always try BnB (unless subtract-fee-from-outputs)
    bnb = BranchAndBound(utxos, target)
    if bnb.success:
        results.push(bnb)

    // Always try Knapsack
    knapsack = KnapsackSolver(utxos, target)
    if knapsack.success:
        results.push(knapsack)

    // CoinGrinder only at high feerates
    if feerate > 3 * longTermFeerate:
        grinder = CoinGrinder(utxos, target)
        if grinder.success:
            results.push(grinder)

    // Always try SRD
    srd = SingleRandomDraw(utxos, target)
    if srd.success:
        results.push(srd)

    // Pick the result with lowest waste
    return min(results, by: wasteMetric)

Real-World Implications for Fee Budgets

The practical impact of coin selection depends heavily on feerate conditions and wallet state. Consider a wallet with 50 UTXOs ranging from 0.001 BTC to 0.5 BTC, trying to send 0.1 BTC:

• At 3 sat/vB: BnB might find a changeless solution, saving the 34 vB change output cost. If not, the waste metric favors solutions that consolidate additional small UTXOs since fees are cheap
• At 30 sat/vB: CoinGrinder activates and competes for selection. If a single 0.1+ BTC UTXO exists, CoinGrinder likely wins by using it alone with minimal input weight
• At 100+ sat/vB: CoinGrinder strongly dominates. Each extra input costs roughly 6,800 sats (68 vB × 100 sat/vB for a P2WPKH input), so minimizing input count becomes critical

For wallets that handle high transaction volume, the cumulative effect of good coin selection is significant. The combination of BnB's changeless transactions and the waste metric's consolidation incentives can reduce total fees by 10-20% over time compared to naive strategies. See our analysis of Bitcoin fee market dynamics for more context on feerate fluctuations.

How Spark Sidesteps the Problem

Spark's statechain-based architecture operates fundamentally differently from the UTXO model. Transfers on Spark do not construct Bitcoin transactions: they reassign ownership of existing outputs through cryptographic key rotation. There is no input selection, no change output, and no per-transfer fee calculation based on transaction weight.

However, understanding coin selection remains relevant for Spark users. Depositing Bitcoin into Spark requires an on-chain transaction, and withdrawing (unilateral exit) does as well. The quality of coin selection used for these on-chain operations directly affects the cost of entering and leaving the Spark layer. Wallets built on the Spark SDK should implement strong coin selection for these on-chain touchpoints while leveraging Spark's feeless transfers for everything between deposit and withdrawal.

For users who want to avoid on-chain UTXO management entirely, Spark-powered wallets like General Bread abstract away the complexity of coin selection, fee estimation, and UTXO management behind a simple send-and-receive interface.

Key Takeaways

Bitcoin coin selection has matured from a single randomized heuristic to a sophisticated multi-algorithm framework. Each algorithm addresses a specific failure mode of the others:

• BnB eliminates change outputs when possible, saving both current and future fees
• Knapsack provides a reliable fallback that always finds a solution
• SRD hedges against structured algorithms hitting their worst cases
• CoinGrinder minimizes fees during high-feerate periods by reducing input count
• The waste metric ties them together with a unified cost function that adapts to fee conditions

For developers building Bitcoin wallets or applications, implementing at minimum BnB with a random fallback (as BDK does) provides the bulk of the fee savings. For those building on Layer 2 protocols like Spark, good coin selection at the on-chain boundary points remains important even when the majority of transactions bypass the UTXO model entirely.

This article is for educational purposes only. It does not constitute financial or investment advice. Bitcoin and Layer 2 protocols involve technical and financial risk. Always do your own research and understand the tradeoffs before using any protocol.