Choosing UTXOs Like a Knapsack Packer
Every time a Bitcoin wallet builds a transaction, it faces a decision that looks deceptively simple: which unspent outputs (UTXOs) should it spend to cover the payment? In practice this is a genuine combinatorial optimization problem — a close cousin of the classic knapsack problem — with two competing objectives pulling in different directions: minimize the transaction fee (fewer, larger inputs are cheaper) and maximize privacy (avoid leaving an obviously-linkable change output, and avoid revealing too much about your total holdings).
In this article we formalize UTXO selection as a constrained optimization problem, implement the same core algorithm real wallets use — Branch and Bound (BnB) — compare it against two baseline strategies, and visualize the fee/privacy landscape across a range of payment sizes and network fee rates.
Why This Is a Knapsack Problem
Given a wallet holding UTXOs $u_1, u_2, \dots, u_n$ (in satoshis) and a target payment $T$, we want to choose a subset $S \subseteq {1,\dots,n}$, represented by binary decision variables $x_i \in {0,1}$, such that:
$$
\sum_{i=1}^{n} x_i , u_i \geq T + F(S)
$$
where $F(S)$ is the fee required to spend that particular set of inputs. This is a variable-capacity knapsack: unlike the textbook 0/1 knapsack, the “capacity” itself ($T + F(S)$) depends on how many items you pack, because every additional input adds bytes — and therefore fee — to the transaction.
The transaction size in virtual bytes is modeled as:
$$
V(n_{in}, n_{out}) = \beta + n_{in}\cdot v_{in} + n_{out}\cdot v_{out}
$$
where $\beta$ is the fixed overhead (version, locktime, segwit marker), $v_{in}$ is the size of a single P2WPKH input (approximately 68 vB), and $v_{out}$ is the size of a single P2WPKH output (approximately 31 vB). The fee is then:
$$
F(n_{in}, n_{out}) = \tau \cdot V(n_{in}, n_{out})
$$
with $\tau$ the fee rate in sat/vB.
Reframing With Effective Value
The trick that makes this tractable is the notion of effective value — the amount an input is actually worth once you subtract the cost of spending it:
$$
e_i = u_i - \tau \cdot v_{in}
$$
Any UTXO with $e_i \leq 0$ is uneconomical to spend at the current fee rate (dust) and should be excluded outright. Using effective values, we fold the per-input fee cost directly into the “size” of each knapsack item, and define an adjusted target that accounts for the base overhead and a single payment output:
$$
T’ = T + \tau(\beta + v_{out})
$$
The goal becomes: find $S$ minimizing the waste
$$
w(S) = \sum_{i \in S} e_i - T’, \qquad \text{subject to } \sum_{i \in S} e_i \geq T’
$$
If we can land exactly in the window $[T’, T’ + C_{change}]$, where
$$
C_{change} = \tau(v_{in} + v_{out})
$$
is the cost of adding a change output, we avoid creating change entirely — the small excess is simply absorbed into the miner fee. No change output means no change address, which is one of the biggest wins for privacy: it removes the “change output heuristic” that chain analysts use to link addresses back to the same wallet.
The Branch and Bound Algorithm
Exhaustively checking all $2^n$ subsets is fine for small wallets but doesn’t scale. Branch and Bound explores the same search tree but prunes aggressively:
- Lower-bound pruning: if the current partial sum plus the sum of all remaining candidates still can’t reach $T’$, abandon the branch.
- Upper-bound pruning: if the current partial sum already exceeds $T’ + C_{change}$, abandon the branch (since effective values are positive, it only gets worse).
- Candidates are sorted by effective value descending, so promising large inputs are tried first and the tree collapses quickly.
This is the same idea used by Bitcoin Core’s actual coin selection engine.
Baseline Strategies for Comparison
- Greedy Largest-First: repeatedly add the biggest remaining UTXO until the target is covered. Fast, deterministic, but tends to always produce change and reveals your largest holdings.
- Single Random Draw (SRD): shuffle the UTXO set and accumulate in random order, repeated over many trials, keeping the best result. This is what wallets fall back on when BnB can’t find an exact match, and it has the nice property of not correlating input selection with UTXO size (a privacy plus).
A Concrete Example
We’ll use a wallet holding 15 UTXOs ranging from 2,100 to 120,000 sats, a payment target of 150,000 sats, and a fee rate of 15 sat/vB. The script below runs all three strategies, reports the fee, leftover change, and a heuristic privacy score, then produces three visualizations: the UTXO set itself, a head-to-head comparison of the strategies, and a 3D surface showing how selection cost scales with both payment size and fee rate.
Full Python Implementation
1 | import numpy as np |
Target payment: 150,000 sats | Fee rate: 15.0 sat/vB [Branch & Bound] inputs used : 7 fee : 7800 sats change : 0 sats waste (fee+chg): 7800 sats privacy score : 82.5 / 100 [Greedy Largest-First] inputs used : 2 fee : 3128 sats change : 65872 sats waste (fee+chg): 69000 sats privacy score : 54.6 / 100 [Single Random Draw] inputs used : 3 fee : 4000 sats change : 0 sats waste (fee+chg): 4000 sats privacy score : 92.5 / 100
Code Walkthrough
Cost model functions — fee_no_change, cost_of_change, and build_result centralize every fee/change calculation so all three strategies are scored with exactly the same accounting rules. build_result first checks whether the leftover amount after paying a single-output fee fits within cost_of_change; if so, the excess is simply absorbed into the fee (no change output, best for privacy). Otherwise a second output is added and the true change amount is computed with the correct two-output fee.
branch_and_bound is the core solver. It first strips out any UTXO whose effective value would be negative (dust at the current fee rate), sorts the rest by effective value descending, and precomputes suffix sums so it can instantly tell, at any point in the search, whether the remaining candidates could possibly reach the target. The recursive dfs function tries including and excluding each candidate in turn; the two pruning checks (current_sum > target_adj + c_change and current_sum + suffix_sum[i] < target_adj) keep the search space tiny in practice even though the worst case is exponential.
greedy_largest_first and single_random_draw are simpler accumulation strategies used purely as a baseline. SRD repeats the random accumulation 300 times and keeps whichever trial produced the least waste — this mirrors how real wallets use randomness to avoid a predictable, fingerprintable selection pattern.
privacy_score is a deliberately simple heuristic, not a rigorous metric: it rewards avoiding a change output, and penalizes both large change amounts (a stronger signal to chain analysts) and using many inputs (which reveals more of your holdings at once).
The grid search in Visualization 3 re-runs Branch and Bound (falling back to greedy) at 196 combinations of target amount and fee rate. Because each run only searches a 15-item tree, the whole grid completes in well under a second — this is the same reason real wallets can afford to run BnB on every transaction they build.
Interpreting the 3D Fee Landscape
The resulting surface should show waste rising in two directions: moving along the fee-rate axis makes every input more expensive to include, so the algorithm either needs fewer, larger inputs (harder to hit exactly) or absorbs more into the fee; moving along the target-amount axis simply requires summing more value, increasing the chance of overshoot. The interesting region to look at is where the surface dips toward the axis — those are the (target, fee rate) combinations where an exact, change-free match exists in this particular UTXO set, which is exactly the situation Branch and Bound is designed to find.
Privacy Considerations Recap
Fee minimization and privacy maximization aren’t always aligned. A single large UTXO minimizes fees (one input, tiny transaction) but reveals a big chunk of your balance in one output. Combining many small UTXOs can look more “organic” and avoid revealing a single large holding, but costs more in fees and links more addresses together in one transaction. Avoiding a change output is close to a free lunch for privacy — it removes the single most exploited heuristic in blockchain analysis — which is precisely why Branch and Bound searches for an exact match before falling back to any change-producing strategy.
Conclusion
UTXO selection is a small but genuinely NP-hard combinatorial problem hiding inside every Bitcoin transaction. Branch and Bound turns it into a fast, practical search by reframing the knapsack in terms of effective value and pruning aggressively, and it’s a good illustration of how a well-chosen problem transformation can make an exponential search tree collapse to something that runs in milliseconds on real wallet-sized inputs.