bitcoindevkit / bitcoindevkit/coin-select

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

Open Beginner friendly
#58 1 comment 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.