LowestFee::bound panics on assert!(ideal_fee >= 0.0) due to f32 rounding

[evanlinjin]

Summary

LowestFee::bound can panic via assert!(ideal_fee >= 0.0) on valid inputs, reachable through the public run_bnb/bnb_solutions API.

https://github.com/bitcoindevkit/coin-select/blob/cd8cec4/src/metrics/lowest_fee.rs#L276

Cause

In the not-yet-funded arm of bound(), the "perfect resized input" relaxation computes:

let ideal_fee = scale.0 * to_resize.value as f32 + cs.selected_value() as f32
    - target.value() as f32;
assert!(ideal_fee >= 0.0);

With sat values in the millions (well within f32's 24-bit integer mantissa limit of ~16.7M, but large enough that intermediate rounding bites), scale = remaining / value rounds such that scale * value + selected - target lands a tiny amount below zero. At target.fee.rate == 0 this is easiest to hit, since scale is derived purely from the value gap.

Reproduction

Found by differential fuzzing (10/1500 random scenarios with realistic UTXO sizes). One concrete panic case:

• 15 candidates with values up to ~1.5M sats, e.g. {4167(w360), 13447(w7597), 1480489(w2663), 17281(w368), 26718(w755), 237889(w4570), 273139(w997), 145266(w2124), ...}
• Target { fee: { rate: 0.0 spwu, absolute: 0, replace: None }, outputs: { value_sum: 52692, weight_sum: 208, n_outputs: 1 } }
• LowestFee { long_term_feerate: 0.59 spwu, dust_relay_feerate: 1.4 spwu, drain_weights: { output_weight: 342, spend_weight: 815, n_outputs: 2 } }
• cs.run_bnb(target, metric, 100_000) → panicked at 'assertion failed: ideal_fee >= 0.0'

Suggested fix

0 is always an admissible lower bound for a fee, so clamping preserves correctness:

let ideal_fee = (scale.0 * to_resize.value as f32 + cs.selected_value() as f32
    - target.value() as f32)
    .max(0.0);

(Alternatively compute the relaxation in f64 and keep a debug_assert! with an epsilon.)

Found while stress-testing #53; the bug predates that PR and reproduces on current master (cd8cec4).

🤖 Generated with Claude Code