bitcoindevkit / bitcoindevkit/coin-select
BnB exclusion dedup keys on (value, weight) only, merging candidates with different is_segwit/input_count
- Dominant language
- Rust
- Stars
- 18
- Forks
- 14
- PR merge metrics
- No merged PRs in 30d
Description
## 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
```rust
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:
```rust
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](https://claude.com/claude-code)
Contributor guide
No contributing guide indexed for this repository
Research direction
Start in src/bnb.rs around lines 146-148 and trace how run_bnb performs exclusion-branch deduplication and calculates input_weight(). Use the differential fuzzing scenarios or exhaustive-search oracle described in the issue to check candidates with matching value and weight but different is_segwit or input_count. Done means distinct cost profiles are no longer merged and BnB does not return a score above the true optimum.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- blockchain
- Issue type
- Bug
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 78/100