polycratia

Make a coin selection impossible to construct wrong

· 10 min read

The wallet bugs that lose fees do not live in the selection strategy. They live in the seam between that strategy and the transaction builder. You get a selection that overpays by a few thousand base units. You get a change output that one side counted and the other did not, and a fee that is whatever happened to be left after the subtraction. All of it is arithmetic that was correct when it was computed and stopped being correct one step later, and none of it raises anything.

That seam forgives less than most money bugs do. A payment service can reconcile a mismatch the next morning and move the money back. A transaction that overpaid its fee is settled by the time anyone notices: the miner keeps the difference, and there is nobody to invoice. So the only useful place to catch the mistake is before the result object exists. That is the design I settled on in utxo-select, and the rest of this post is the reasoning.

The shape of the bug#

Almost every coin selection I have read returns something like this, mine included at some point:

python
# the shape I keep finding - not the shape I ship
def select(utxos, target, fee_rate):
    chosen, total = [], 0
    for utxo in sorted(utxos, key=lambda u: -u.value):
        chosen.append(utxo)
        total += utxo.value
        if total >= target:
            break
    fee = estimate_fee(vsize_of(chosen), fee_rate)
    change = total - target - fee
    return chosen, change, fee

Three return values, each of them true at the moment it was computed. Any later edit to chosen leaves change and fee describing a transaction that is not the one being built any more: you drop an output that turned out to be too shallow, you de-duplicate an outpoint that appeared twice, you decide not to create the change output after all. The function cannot object, because what it returned was numbers and not a statement about a set.

A sharper problem hides in the last line, and it comes down to the direction of the subtraction. Here change is the remainder, so an error in the size estimate lands in change, where it is at least visible as money that came back smaller than you expected. Flip the two (define fee as whatever is left after the target and the change) and the equation holds by construction no matter what. The error does not turn into a mismatch. It turns into a bigger fee, which looks exactly like a fee. Whichever field you compute by subtraction is the field that quietly absorbs every mistake upstream of it, and when that field is the fee, the mistake leaves the building.

Put the equation in the constructor#

So the result type does not get to be a tuple. In utxo-select a Selection carries the parts (the inputs it spends, the change, the fee, the virtual size) and checks its own arithmetic in __post_init__. It refuses empty inputs, a negative change or fee, and any set of parts where total_input differs from total_output plus the fee. Here is the load-bearing line, with the messages abridged:

python
@property
def total_input(self) -> int:
    return sum(utxo.value for utxo in self.inputs)

def __post_init__(self) -> None:
    if not self.inputs:
        raise ValueError("a selection must spend at least one input")
    if self.total_input != self.total_output + self.fee:
        raise ValueError("inputs must equal outputs plus fee")

An underpaying or overpaying selection cannot be constructed at all. That is what I was after: not a strategy that computes carefully, but a strategy that computed carelessly and then has nowhere to put the result. The type is not there to calculate. It is there to refuse.

It also settles where the arithmetic lives. I have built custodial wallet services for BTC and ETH, and fee arithmetic is exactly the kind of logic that drifts across a strategy, a builder and a broadcaster until no single function owns it, and then the only thing that would notice a mistake is reconciliation after the fact. One type that will not exist unless the ring closes costs you less than three careful functions.

Derive the totals, never store them#

total_input, total_output and has_change are derived from the parts instead of stored next to them. Two copies of a number drift. One copy cannot. The same discipline sits at the other boundary, in models.py, where the request's total is a property and every amount goes through one validator:

python
def _check_int(value: object, name: str, *, minimum: int) -> None:
    if isinstance(value, bool) or not isinstance(value, int):
        raise TypeError(
            f"{name} must be an int of base units, got {type(value).__name__}"
        )
    if value < minimum:
        raise ValueError(f"{name} must be >= {minimum}, got {value}")


@property
def total_target_value(self) -> int:
    return sum(target.value for target in self.targets)

Rejecting bool is not pedantry. True is an int in Python and sums perfectly happily, so a flag that reaches an amount field adds one base unit and no exception. Floats go out for the same reason: every amount and size in the library is an integer of base units, which leaves rounding error no way in. estimate_fee keeps that property by rounding up and taking the rate per 1000 virtual bytes, so a rate finer than one unit per vbyte is still an integer rather than a float waiting to lose a cent.

The parts have to be real before the equation means anything#

An equation over a bag of inputs is only as good as the bag. A duplicated outpoint satisfies total_input == total_output + fee beautifully and produces a transaction no node will relay, because the sum is a truthful statement about a list that was never a set. So duplicates die upstream, in _checked_candidates, which raises on a repeated outpoint instead of quietly collapsing it.

The other upstream filter is economic. An output that costs at least as much to spend as it holds moves a selection away from covering its targets and never toward it:

python
def _effective_value(utxo: Utxo, fee_rate: int) -> int:
    """What an output is worth once the fee for spending it is taken off."""
    return utxo.value - estimate_fee(_input_vsize(utxo), fee_rate)


eligible = [
    utxo
    for utxo in candidates
    if policy.accepts(utxo) and _effective_value(utxo, request.fee_rate) > 0
]
if policy.consolidates_at(request.fee_rate):
    return tuple(sorted(eligible, key=lambda u: (u.value, u.outpoint)))
return tuple(sorted(eligible, key=lambda u: (-u.value, u.outpoint)))

Ties break by outpoint in both directions, so two equal-valued outputs do not make the answer depend on the order the candidates arrived in. That matters less for correctness than for being able to reproduce a selection from a bug report, which in practice is the same thing.

The equation catches lost money, not wasted money#

Here is the honest limit of all this. total_input == total_output + fee is exact, and exactness is not frugality. Drop the change output and the remainder legally becomes fee: the equation still closes, and the wallet has quietly tipped the miner. Sometimes that is the right trade. On the README's example wallet, branch-and-bound finds a single candidate that covers a bill of 100_000, overshoots by 96, hands those 96 to the fee and creates no change output at all. It pays 2_400 where largest-first pays 2_712 and leaves behind a change output that will cost another 1_776 to spend. At fee_rate=12_000 a change output costs 408 to create and 1_776 to spend later, 2_184 together, and overshooting by less than that is cheaper than returning it politely.

So the bound on waste cannot be an invariant. It is a property test, with the tolerance written down and named:

python
def wasted_fee_bound(result, request):
    return (
        max(request.dust_threshold, 1)
        + estimate_fee(
            OUTPUT_OVERHEAD_VSIZE + request.change_script_size, request.fee_rate
        )
        + estimate_fee(
            INPUT_OVERHEAD_VSIZE + DEFAULT_INPUT_SCRIPT_SIZE, request.fee_rate
        )
        + len(result.inputs)
    )


@seeds
@strategies
def test_the_fee_never_overpays_beyond_the_cost_of_change(seed, strategy):
    case = scenario(seed)
    result = run(strategy, case)
    if not isinstance(result, Selection):
        return
    if case.request.change_policy is ChangePolicy.FORBID_CHANGE:
        return

    required = estimate_fee(result.vsize, case.request.fee_rate)
    if result.has_change:
        assert result.fee == required
    else:
        assert result.fee - required <= wasted_fee_bound(result, case.request)

Two mechanisms, two homes. The type enforces what has to be true every time, so it can raise. The test enforces what should usually be true, and it states precisely how much slack it tolerates, including the per-input rounding term that both strategies incur while they are still pricing inputs one at a time. An invariant with exceptions is not an invariant. A bound with a name is a bound you can argue about in a code review. The same test suite asserts the ring directly too, which is how I know the constructor is not the only thing holding it:

python
total_input = sum(utxo.value for utxo in result.inputs)
target_value = case.request.total_target_value
assert result.change >= 0
assert result.fee >= 0
assert total_input >= target_value + result.fee
assert total_input == target_value + result.change + result.fee

Failure is a value, not an absence#

If the result type is the only place arithmetic gets settled, then "no result" has to be a thing of its own, or your callers improvise. Returning None invites a caller to carry on with a zero change and a zero fee. A SelectionFailure carries why instead: how much was available against how much was required, how many candidates there were against how many the policy left eligible, how many were spendable at this rate at all, and how much value is waiting on confirmations. The messages separate the cases a caller would otherwise conflate:

python
f"{self.reason.value}: {self.available} available from "
f"{self.eligible_count} of {self.candidate_count} candidates, "
f"short by {self.shortfall}; {self.withheld_value} waits on "
f"confirmations"

A wallet that cannot pay because the fee rate has made its small outputs unspendable is in a different situation from one that is merely waiting for a confirmation, and the second will fix itself. The all-dust case is reported first precisely because there it is the rate and not the balance that is wrong, and that output becomes ordinary money again in a cheaper block.

What I would do differently#

I wrote the property tests before I tightened the constructor, so the equation lived in the tests for a while. That order was backwards, I think. A test tells you the strategy was wrong after you ran it. A constructor tells the strategy it is wrong at the line that got it wrong, and it tells every future strategy too: the branch-and-bound path inherited the check for free instead of needing its own audit.

The other thing I would do earlier is ban tuples from the strategy boundary outright. Every intermediate that returns (inputs, change, fee) is an invitation to edit one of the three, and the honest version of that signature is a type that will not let you.

Pick the direction of your subtractions deliberately, derive every total from the parts, and let the result type refuse to exist unless the ring closes. What you have left is a selection that may be unwise, but cannot be wrong.

react

$ new-project --brief

or email hey@polycratia.com