Coin selection should return a reason, not None

2026-08-31 · 9 min read

A withdrawal fails at three in the morning and the log line says the coin selector returned None. That one value covers at least four different situations: two of them are answered by funding the hot wallet, two by changing the request, and nothing in the log says which one you are looking at. The information existed inside the function for a few microseconds and was discarded at the return statement.

I have shipped custodial BTC and ETH wallets and on-chain payment flows since 2018, and this is the failure mode I keep meeting. Coin selection gets written as a predicate — it either produced inputs or it did not — and then the whole operational cost of that decision lands on whoever is awake. They reconstruct the reason by hand from a balance snapshot and a fee chart. That reconstruction is the library's job.

This is the thing I wanted to get right in utxo-select, a small coin selection library I maintain. It is pre-alpha: the models, size estimation, largest-first and branch-and-bound are in place, and the remaining strategies are not. But the failure type was designed before either strategy was, and that ordering turned out to matter more than the strategies did.

Four answers hiding behind one None#

A selection can fail in ways that a caller would answer differently:

The last one only fails a selection under REQUIRE_CHANGE. Under the default policy a remainder too small to be worth its own output is given to the fee instead, which is the right default and a surprising one the first time you see the fee come out larger than you asked for.

The distinction that earns its keep operationally is the first two. insufficient_funds means no fee rate on earth makes this transaction; the wallet is simply too small for what was asked. insufficient_after_fees means the wallet covers the payment and loses to the fee, so waiting for a quieter mempool or picking fewer, larger inputs can still close the gap. Those are different pages in a runbook, and a boolean cannot tell them apart.

Because the outcome is a returned value rather than an exception, the caller narrows it with isinstance and the type checker keeps the branches honest:

from utxo_select import FailureReason, Selection, SelectionFailure
from utxo_select import select_largest_first


def explain(result: Selection | SelectionFailure) -> str:
    if isinstance(result, Selection):
        return (
            f"ok: {len(result.inputs)} inputs, fee {result.fee}, "
            f"change {result.change}, vsize {result.vsize}"
        )
    if result.reason is FailureReason.INSUFFICIENT_FUNDS:
        return f"underfunded before any fee, short by {result.shortfall}"
    if result.reason is FailureReason.INSUFFICIENT_AFTER_FEES:
        return (
            f"a lower fee rate closes a gap of {result.shortfall}; "
            f"spending everything would owe {result.fee}"
        )
    if result.reason is FailureReason.DUST_ONLY:
        return f"all {result.candidate_count} candidates are dust at this rate"
    return f"can pay, but change would not clear dust; needs {result.shortfall}"


print(explain(select_largest_first(utxos, request)))

That function is the entire on-call improvement. It is also the thing you cannot write against a selector that returns None.

The fee is inside the loop, not after it#

Here is why two of those reasons are even distinguishable, and why they are hard.

The naive shape of coin selection is: sum the candidates, compare against the targets plus the fee, take inputs until the comparison passes. That shape does not work, because the fee is not a constant you can compute up front. A transaction costs a fixed overhead, plus 41 virtual bytes and an unlocking script for every input, plus 9 virtual bytes and a locking script for every output. Every input you add to cover the fee makes the fee larger. Sometimes it makes it larger than the input was worth.

So the required amount is a function of the answer you are still computing. Selection and fee estimation are one loop:

from utxo_select import ScriptType, estimate_fee, estimate_vsize

fee_rate = 12_000  # per 1000 virtual bytes

vsize = estimate_vsize(
    inputs=[ScriptType.P2WPKH, ScriptType.P2WPKH],
    outputs=[ScriptType.P2TR, ScriptType.P2WPKH],
)
print(vsize, estimate_fee(vsize, fee_rate=fee_rate))

# What one more input actually costs you at this rate:
print(estimate_fee(ScriptType.P2WPKH.input_vsize, fee_rate=fee_rate))
print(estimate_fee(ScriptType.P2PKH.input_vsize, fee_rate=fee_rate))

That marginal number is the whole story. An output is worth its value minus the fee of spending it — its effective value — and an output whose effective value is negative should never be picked up, no matter how short the selection is. That is what dust_only names: a wallet with a visible balance that cannot pay anything at all at the current rate, because every coin in it is underwater against its own input cost. Users report this as "my balance is wrong". It is not wrong. It is unspendable, which is a different bug report entirely, and the selector is the only component that knows.

Estimates are upper bounds and both the virtual size and the fee round up. Underpaying is what leaves a transaction stuck in the mempool, and a transaction stuck in the mempool at three in the morning is strictly worse than a selection that refused with a reason.

A failure that carries its own arithmetic#

A reason code alone still makes the operator go and look things up. The numbers behind the verdict should travel with it: what the candidates hold (available) against what they would have needed (required), the shortfall between them, the fee a transaction spending every candidate would owe, the target_value that was asked for, and how many candidates were worth spending at all.

result = select_largest_first(utxos, request)

if isinstance(result, SelectionFailure):
    print(result.available, result.required, result.shortfall)
    print(result.spendable_count, "of", result.candidate_count, "spendable")
    print(result.dust_count, "dust at this rate")
    print("gap not caused by the fee rate:", result.required - result.fee)

That last line is the one I reach for most. required - fee is the part of the gap the fee rate is not responsible for, which immediately tells you whether waiting for the mempool to calm down is a strategy or a waste of an hour. dust_count tells you whether the wallet needs a consolidation transaction rather than a top-up. None of these are new computations — the selector did all of them on its way to failing. It just has to not throw them away.

Why a failure is a value and a success is checked#

Two choices hold this together.

First, failure is a returned value, not an exception. Not being able to pay is an ordinary outcome of asking a wallet to pay, not an exceptional one, and modelling it as a value forces every caller to look at it. An exception gets swallowed by a broad except three frames up and turns back into None with extra steps.

Second, success is verified before it can exist. A Selection checks its own identity in __post_init__ — inputs equal targets plus change plus fee — and refuses to be constructed otherwise:

if self.total_input != self.total_output + self.fee:
    raise ValueError(
        f"selection does not balance: {self.total_input} in, "
        f"{self.total_output} out, {self.fee} fee"
    )

This is the same discipline as a double-entry ledger, and it is there for the same reason: the expensive failures are not the loud ones. An underpaying selection is a transaction that looks fine, broadcasts fine, and sits unconfirmed. Making that state unconstructible is worth more than any amount of downstream validation.

The pairing also lets a strategy degrade honestly. Branch-and-bound searches for a subset that pays the targets and the fee exactly, so the transaction carries no change output at all — which saves the change output's fee now and the fee of spending it later. Exact matches are the exception, not the rule. When the search budget runs out (100000 nodes by default, tunable via max_tries), the largest-first result is returned instead. The caller gets the best available answer rather than a failure, and it never has to guess which strategy produced it, because a Selection reports its own fee, change and has_change.

What I would do differently#

I would write the failure type before the first strategy, not after — and this time I did, which is the only reason branch-and-bound needed no new reasons when it landed. The four outcomes are properties of the problem, not of the algorithm. Every strategy fails for the same four causes; if adding a strategy adds a reason, the reason vocabulary was wrong.

The thing I underestimated is how much of the failure payload is inference rather than measurement. available and candidate_count are facts. required is a claim that depends on which script types you assumed and how you rounded, and spendable_count depends on the fee rate at the moment you asked. Those numbers are only true for one request. I would put more of that context into the failure itself rather than letting a log line imply it was universal.

A coin selector is not a predicate over a wallet. It is an oracle about a wallet at a fee rate, and the answer "no" is the least interesting thing it knows.