The cost of change is the tolerance a changeless search needs

2026-10-30 · 10 min read

A coin selection that makes no change output will often pay the miner more than its size implies, and that overpayment is usually the right outcome rather than a bug. A change output gets billed twice (once as an output in this transaction, once as an input in some later one), so the amount a changeless spend may overshoot its target by is not a tuning knob. It is a price, and it comes out of the same fee model that prices everything else in the transaction.

I have been building custodial wallet and on-chain payment systems since 2018, and for years I treated the tolerance inside a branch-and-bound coin selector as a policy decision: a dust-ish number somebody picked once, tunable per wallet. It is not a policy decision. It is computable, it is the only value that makes the search correct rather than merely lucky, and deriving it from the fee model instead of from configuration removes a whole category of argument. The code here is from utxo-select (https://github.com/polycratia/utxo-select), a coin selection library I am writing in Python. It is pre-alpha; the changeless search is the part of it I find most instructive.

Change is paid for twice#

A transaction is billed for its size, not its value. Paying a thousand base units and paying a billion cost you the same if the transaction has the same shape.

Size arrives in fixed pieces: about 10 virtual bytes of transaction overhead, then 41 vbytes plus the signature script for every input, then 9 vbytes plus the locking script for every output. With the legacy defaults the models carry (107 for the signature data, 25 for the locking script) an input is 148 vbytes and an output is 34. At 12 base units per vbyte, which is fee_rate=12_000 quoted per 1000 vbytes so that rates finer than one unit per vbyte stay expressible in integer arithmetic, that is 1_776 for each input and 408 for each output, whatever they hold.

Two things follow, and most of the library sits downstream of them.

An output is worth less than it says. Moving an output that holds 45_000 costs 1_776, so it brings 43_224 to the table. That is its effective value, and an output holding less than the fee to spend it brings nothing at all at that rate.

A change output costs 408 to create now and 1_776 to spend later, 2_184 together. A selection that overshoots its target by less than 2_184 and hands the remainder to the fee has therefore spent less than one that returns the remainder politely. The receipt looks worse and the wallet is better off.

That is the whole thesis. Everything below is the work of putting that arithmetic somewhere you can check it, instead of leaving it as folklore inside a constant.

The tolerance is computed, not configured#

select_branch_and_bound builds the figure before it searches:

if request.change_script_type is not None:
    change_spend_vsize = _weight_to_vsize(
        request.change_script_type.input_weight
    )
else:
    change_spend_vsize = _weight_to_vsize(
        _hint_input_weight(change_spend_script_size)
    )
cost_of_change = estimate_fee(
    _output_vsize(request.change_script_type, request.change_script_size),
    request.fee_rate,
) + estimate_fee(change_spend_vsize, request.fee_rate)

Two terms, two tenses. The first prices the change output as it will appear in the transaction being built. The second prices the input that will one day spend it.

That second term needs to know a script kind, and the right one is the change output's own: whatever shape you hand your change back to yourself in is the shape you will later have to spend from. So when the request names a change_script_type, that type prices the future input. When it does not, the caller's change_spend_script_size hint does, defaulting to DEFAULT_INPUT_SCRIPT_SIZE, 107, the signature data of a legacy P2PKH input.

This is not pedantry. The witness discount is big enough to move the answer: the one-input, one-target, one-change spend in the README is 141 vbytes and 1_692 in fees in P2WPKH shapes, against 226 vbytes and 2_712 for the same selection in legacy shapes. A tolerance hardcoded around legacy inputs is roughly wrong in a segwit wallet, and wrong in the dangerous direction: it accepts overshoots that are not in fact cheaper than returning change.

What the search is bounded by#

The target the search aims at is not the invoice. It is the invoice plus the fee for a transaction that carries the targets, no change output and, for now, no inputs:

base_vsize = _tx_vsize((), request, with_change=False)
target_value = request.total_target_value
selection_target = target_value + estimate_fee(base_vsize, request.fee_rate)

Candidates are whatever the policy accepts and whose _effective_value is positive; an output that costs more to move than it holds never gets considered. The pool is sorted by effective value, descending, with the outpoint breaking ties so the answer does not depend on dictionary order. Ascending instead when the policy consolidates at this fee rate, so a match is looked for among the small outputs first.

Take the five-output wallet from the README at fee_rate=12_000, paying a single target of 100_000:

The base transaction is 10 vbytes of overhead plus one 34-vbyte output, so 44 vbytes and 528 in fees. selection_target is 100_528. The tolerance, from the section above, is 2_184.

Now the search itself:

def _search_changeless(
    pool: Sequence[tuple[int, Utxo]],
    selection_target: int,
    cost_of_change: int,
    max_tries: int,
) -> tuple[Utxo, ...] | None:
    values = [effective for effective, _ in pool]
    available = sum(values)
    if available < selection_target:
        return None

    selected: list[bool] = []
    current = 0
    best: list[bool] | None = None
    best_excess = cost_of_change + 1

The loop is bounded in a few directions, and one of those bounds is the thesis.

Below. If current plus everything still available cannot reach selection_target, the branch is dead and the loop backtracks. Running that same test once at the top is why an underfunded wallet returns None immediately instead of exploring a tree that cannot hold an answer.

Above. If current exceeds selection_target by more than cost_of_change, the branch is dead too, not because it fails to pay, but because paying that way costs more than returning the difference as change. This is the only bound that encodes a judgement, and the judgement is the one from the fee model: 2_184. The 200_000 output alone covers the bill with an excess of 97_696, so it gets pruned on sight.

By budget. At most max_tries nodes get visited, 100_000 by default. A wallet with many similar outputs has a combinatorially large subset space, and a coin selector sits on the path of a user pressing send.

In between, every total at or above the target whose excess beats the best so far is recorded, and the loop keeps going: only an exact match ends it early. So what you get is the smallest overshoot the search saw inside its budget, not the first acceptable one. There is also a prune that matters more than it looks: a candidate equal in effective value to one just skipped is skipped too. Two outputs of the same value produce subsets that differ only in which of them is included, and exploring both halves of that is pure waste.

For this wallet the 102_400 output lands at 100_624 against a target of 100_528: an excess of 96, comfortably inside 2_184, so it is kept.

A refinement, not a replacement#

Exact matches are rare. A wallet's outputs do not generally happen to add up to a stranger's invoice plus a fee, and a selector that failed whenever they did not would be useless. So the changeless search does not own the outcome.

It declines the question outright when the request demands change: ChangePolicy.REQUIRE_CHANGE goes straight to select_largest_first untouched, because a policy that insists on a change output has nothing to gain from a search for not having one. And when the search comes back empty, the baseline answers under the same policy:

chosen = _search_changeless(
    pool, selection_target, cost_of_change, max_tries
)
if chosen is None:
    return select_largest_first(candidates, request, policy=policy)

total_input = sum(utxo.value for utxo in chosen)
vsize = _tx_vsize(chosen, request, with_change=False)
fee = total_input - target_value
# The search prices each input on its own, which can miss the marker and
# flag of the transaction they end up in; a subset that no longer pays for
# the size it would occupy is not a solution after all.
if fee < estimate_fee(vsize, request.fee_rate):
    return select_largest_first(candidates, request, policy=policy)

return Selection(
    inputs=chosen,
    targets=request.targets,
    change=0,
    fee=fee,
    vsize=vsize,
)

The detail I would point a reviewer at is that the fallback carries the baseline's failure, not its own. If the wallet cannot pay at all, the caller gets the SelectionFailure and FailureReason that select_largest_first would have produced (insufficient funds, or nothing eligible under the policy) rather than a less useful report that no changeless subset was found. The caller asked for a payment. "My search found nothing" answers a question nobody posed.

For the example wallet the selection that comes out is one input of 102_400, 192 vbytes, and a fee of 102_400 - 100_000, so 2_400 against the 2_304 that 192 vbytes actually cost. Ninety-six base units go to the miner and no change output exists. Largest-first on the same request spends the 200_000 output: 226 vbytes, 2_712 in fees, 97_288 handed back as change, and that change will itself cost 1_776 to move, so the real price is 4_488, and the wallet still holds every small output it held before.

What I would change#

Price the subset, not the inputs. Effective value rounds each input's virtual size up on its own, which is a safe way to compare candidates and an unsafe way to total them: the input_vsize docstring says as much. That approximation is what the fee < estimate_fee(vsize, ...) guard exists to catch, and I would rather not make the pricing error than undo it after the fact. Carrying weight units through the search and dividing by four once at the end, the way estimate_vsize already does for whole transactions, would make the guard unnecessary instead of load-bearing.

Make the result say who produced it. A silent fallback to the baseline is right for the caller and wrong for whoever is reading logs six months later, wondering why fees look different on Tuesdays. A Selection that records which strategy answered costs one field and saves an afternoon.

Treat max_tries as a budget with observable exhaustion. Hitting the node limit and quietly producing the baseline's answer is indistinguishable, from outside, from a wallet that simply had no exact match. Those are different facts about a wallet, and probably only one of them is worth acting on.

The thing I would not change is where the tolerance comes from. Once the number is computed from the fee model rather than configured, the question "may this spend overpay the miner?" stops being a matter of taste and becomes arithmetic that either balances or does not.