BnB exclusion dedup keys on (value, weight) only, merging candidates with different is_segwit/input_count

[evanlinjin]

Summary

BnB's exclusion-branch deduplication treats candidates as interchangeable when they share (value, weight) — but candidates that differ in is_segwit or input_count contribute different amounts to input_weight() (via the segwit marker/flag + per-input witness-length adjustment, and the input-count varint). Banning the whole "equivalence" run can therefore ban a strictly cheaper candidate along with a costlier lookalike, and BnB returns a slightly suboptimal result while reporting it as the optimum.

https://github.com/bitcoindevkit/coin-select/blob/cd8cec4/src/bnb.rs#L146-L148

let to_ban = (next.value, next.weight);
for (next_index, next) in cs.unselected() {
    if (next.value, next.weight) != to_ban {
        break;
    }
    ...
}

Impact

Found by differential fuzzing against a brute-force exhaustive-search oracle: 20/1500 random scenarios (mixed segwit/non-segwit pools) produced a run_bnb LowestFee score above the true optimum, with deltas of 5–36 sats (e.g. bnb score 3758 vs optimum 3752). Also reproduced under Changeless. Any pool containing two candidates with equal (value, weight) but different is_segwit or input_count is susceptible.

Not a soundness panic — the returned selection is valid, just not the optimum the API promises.

Suggested fix

Include the weight-relevant fields in the equivalence key:

let to_ban = (next.value, next.weight, next.is_segwit, next.input_count);

Two candidates are only interchangeable for the search when all fields affecting input_weight() match. This keeps the dedup optimization for true duplicates (the common case for same-script-type UTXOs) while never merging distinct cost profiles.

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

🤖 Generated with Claude Code