Fee estimation belongs inside the coin selection loop

2026-09-03 · 9 min read

Coin selection on a UTXO chain is usually written as two steps: pick inputs until they cover the amount, then compute the fee and adjust. That order cannot be made to work. The fee is a function of the transaction's virtual size, the size is a function of which inputs you chose, and how many inputs you need is a function of the fee. It is a circular dependency, and the only honest way to resolve it is to estimate the fee inside the selection loop rather than after it.

I have been building custodial wallets and on-chain payment systems since 2018, and this is the bug I have watched people rediscover most often. It never looks like a bug at first. It looks like a transaction that sits in the mempool longer than it should, or a wallet that reports a spendable balance it cannot actually spend, or a change output worth less than it costs to spend later. All three have the same root: the fee was computed against a transaction that was already decided.

I keep the reference implementation of the argument in the open at github.com/polycratia/utxo-select — a small Python library that does coin selection, change computation, size estimation and failure reporting as one thing rather than four.

The circle#

Spell the dependency out and it stops being abstract.

A transaction's weight is fixed overhead plus a per-input cost plus a per-output cost, and virtual size is that weight divided by four, rounded up. The per-input cost depends on the script type of the output being spent: a legacy P2PKH input is 148 vbytes, a P2WPKH input is 68, a Taproot key-path input is 58. So each candidate you add pushes the size up by a different amount depending on what kind of output it is, and pushes the required total up by that amount multiplied by the fee rate.

from utxo_select import ScriptType, estimate_fee, estimate_vsize

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

print(vsize, estimate_fee(vsize, fee_rate=12_000))
print(ScriptType.P2PKH.input_vsize)  # marginal cost of one more legacy input

Fee rates here are quoted per 1000 virtual bytes and everything is an integer of base units, because satoshi arithmetic that touches a float is a bug waiting for a rounding boundary. 12_000 is twelve satoshi per vbyte.

Now run the naive algorithm. You need 100,000. You take inputs by descending value until you have 100,000. Then you compute the fee — say it comes to 1,800 — and discover you are short. So you add another input. That input is worth 45,000, which covers the shortfall easily, but it also added 68 vbytes to the transaction, which added another 816 to the fee. This time you are still fine. Next time, with a smaller candidate, you will not be.

Why the second pass does not save you#

The fix people reach for is a second pass: cover the amount, compute the fee, add inputs until the fee is covered too. This terminates on well-funded wallets and quietly diverges on the wallets where it matters.

The reason is that an input is not free money. Spending an output of value v at fee rate r costs estimate_fee(script.input_vsize, r), and what the input is actually worth to this transaction is the difference. That difference is the effective value, and it can be zero or negative. An output holding 500 satoshi, spent as P2WPKH at twelve satoshi per vbyte, costs 816 to spend. Adding it to close a shortfall makes the shortfall larger.

def effective_value(utxo, script_type, fee_rate):
    return utxo.value - estimate_fee(script_type.input_vsize, fee_rate)

That is one line, and it is the line that turns "add inputs until it fits" from a heuristic into an algorithm. Candidates with a non-positive effective value are not candidates; a wallet made entirely of them cannot fund anything at any amount, which is a distinct failure from being merely underfunded, and the library reports it as dust_only.

One caveat on input_vsize that took me an embarrassingly long time to internalize: rounding each input's weight to vbytes independently overstates the total, because the rounding happens once per input instead of once per transaction. It is a safe number to compare two candidates with — it is an upper bound, and upper bounds are what you want when the failure mode is underpaying — but it is not a term to sum into a total. The total goes through estimate_vsize over the actual input and output lists.

So the loop looks like this. Nothing exotic, just the fee re-derived on every iteration against the transaction as it currently stands:

from utxo_select import ScriptType, estimate_fee, estimate_vsize

def cover(candidates, target, fee_rate,
          spend=ScriptType.P2WPKH,
          outputs=(ScriptType.P2TR, ScriptType.P2WPKH)):
    chosen, total = [], 0
    for utxo in sorted(candidates, key=lambda u: u.value, reverse=True):
        chosen.append(utxo)
        total += utxo.value
        vsize = estimate_vsize([spend] * len(chosen), list(outputs))
        required = target + estimate_fee(vsize, fee_rate)
        if total >= required:
            return chosen, required, total - required
    return None, None, None

The important line is required, recomputed after every append. There is no point in the function where the amount to beat is a constant.

The change output is a term in the size, not a leftover#

The second place the circularity bites is change, and it bites harder because the coupling runs the other way. Change is not what is left over after the fee. Change is an output, an output has a size, and that size is in the fee you just computed.

A P2WPKH change output is 31 vbytes, which at twelve satoshi per vbyte costs 372 to create. So the moment the remainder drops below the dust threshold — 546 in the usual configuration — you face a decision the naive pipeline has no place to express: you cannot create the output, and you cannot silently drop it either, because dropping it shrinks the transaction, lowers the fee, and increases the remainder you were about to discard.

The honest resolutions are a small, closed set, which is why change policy is an input to selection rather than a post-processing step:

from utxo_select import ChangePolicy, SelectionRequest, Target, Utxo

request = SelectionRequest(
    targets=(Target(value=100_000),),
    fee_rate=12_000,
    dust_threshold=546,
    change_policy=ChangePolicy.ALLOW_CHANGE,
)

ALLOW_CHANGE gives a remainder too small to be worth an output to the fee instead — you overpay slightly, but nothing unspendable is created. REQUIRE_CHANGE keeps adding inputs until the change clears dust, which is what you want when the change address is doing accounting work downstream. FORBID_CHANGE never creates one at all. What you must not do is create a 400-satoshi output and call the selection successful. That output costs 816 to spend. You have not given the user change; you have given them a liability and charged them a fee for it.

Changeless spends make the coupling explicit#

Branch-and-bound is the strategy where the whole argument becomes visible, because it optimizes for the change output not existing. It searches for a subset of candidates that pays the targets and the fee exactly, with no remainder worth returning.

from utxo_select import Selection, select_branch_and_bound

result = select_branch_and_bound(utxos, request)

if isinstance(result, Selection) and not result.has_change:
    print("changeless", result.fee, result.vsize)

"Exactly" needs a tolerance, and the tolerance is derived, not tuned. Dropping the change output saves its fee now — 372 — and saves the fee of spending that output later — 816. So a subset that overshoots the target by less than roughly 1,188 at this rate is still an improvement over the alternative, and can be accepted as a solution. That bound is not a magic constant. It is two fee estimates, both of which require knowing the script types involved, which means the search cannot be separated from size estimation any more than the greedy loop could.

Exact matches are rare in real wallets, so the search runs against a budget — 100,000 nodes by default, tunable — and falls back to the largest-first result when it runs out. A selector that returned a failure there would be lying: an answer existed, it just was not the elegant one.

One more consequence worth stating plainly. Because the fee lives inside the loop, the selector can tell you why it failed in terms a human can act on. "The candidates do not hold the target amount" and "they hold the target amount but not the fee on top of it" are different sentences, and only the second one is fixed by waiting for a cheaper fee rate. A selector that added the fee afterwards cannot distinguish them, because at the moment it gave up it did not know what the fee was going to be.

What I would do differently#

The first version I ever wrote returned a boolean and mutated a transaction builder in place. Both were mistakes. Returning a value that is either a balanced selection — inputs equal targets plus change plus fee, checked — or a structured failure carrying available, required and shortfall removed an entire category of bug, because there is no longer a state where the caller holds a half-built transaction and a False.

The other thing I would fix earlier: round up, everywhere, without apology. Virtual size rounds up. The fee rounds up. Signatures are counted at their maximum encoded length rather than their typical one. Paying one base unit more than necessary costs nothing anybody will ever measure. Paying one less drops you below the rate a fee estimator quoted, and a transaction that misses its band by a single satoshi is stuck just as thoroughly as one that missed by a thousand.

Coin selection reads like a knapsack problem, and it is tempting to treat the fee as a constraint you apply to the solution. It is not a constraint on the solution. It is a function of the solution. Write the loop that way and the awkward cases — dust, changeless spends, wallets that are technically funded and practically not — stop being special cases and start being outcomes the same arithmetic produces on its own.