bitcoindevkit / bitcoindevkit/coin-select
Changeless<LowestFee> prunes away changeless solutions that max_weight forces
- Dominant language
- Rust
- Stars
- 18
- Forks
- 14
- PR merge metrics
- No merged PRs in 30d
Description
## What `Changeless` is meant to do
`Changeless` finds the best selection that has **no change output**. It asks the inner metric (usually `LowestFee`) whether a selection would have change; if it would, that selection doesn't count.
To avoid searching pointlessly it has a shortcut, `change_unavoidable`: *if every selection reachable from here would have change, skip this whole branch.* It decides that by building the reachable selection with the **smallest excess** — add every remaining coin with negative effective value, since those shrink the excess. If even that one still has change, prune.
## The bug
There is a second route to being changeless that the shortcut does not know about.
`LowestFee` refuses to add change when the change output would push the transaction over `Target::max_weight`. So a selection can be changeless **purely because change would not fit**. The shortcut only reasons about excess, so it prunes branches containing exactly those solutions.
Net effect: BnB reports *no solution* while a perfectly good changeless solution exists.
## Verified reproduction (master, `abfb0ed`)
Three candidates, `max_weight = 710`, 1 sat/vb, target value 10 000, `DrainWeights::TR_KEYSPEND`:
```rust
let candidates = vec![
Candidate { value: 121_861, weight: 200, input_count: 1, is_segwit: true },
Candidate { value: 1_000, weight: 500, input_count: 1, is_segwit: true },
Candidate { value: 193_757, weight: 368, input_count: 1, is_segwit: true },
];
let target = Target {
fee: TargetFee { rate: FeeRate::from_sat_per_vb(1.0), absolute: 0, replace: None },
outputs: TargetOutputs { value_sum: 10_000, weight_sum: 100, n_outputs: 1 },
max_weight: Some(710),
};
let metric = || Changeless(LowestFee {
long_term_feerate: FeeRate::from_sat_per_vb(1.0),
dust_relay_feerate: FeeRate::from_sat_per_vb(1.0),
drain_weights: DrainWeights::TR_KEYSPEND,
});
let mut a = CoinSelector::new(&candidates);
let expected = common::exhaustive_search(&mut a, target, &mut metric());
let mut b = CoinSelector::new(&candidates);
let found = common::bnb_search(&mut b, target, metric(), usize::MAX);
assert_eq!(expected.map(|(s, _)| s), found.ok().map(|(s, _)| s));
```
```
solution=[0✔, 2✔, 1☐], score=305618 <- brute force
exhaustive = Some(Ordf32(305618.0))
bnb = Err(RoundLimit { max_rounds: 18446744073709551615, rounds: 2 })
```
`rounds: 2` matters: the queue **emptied**, so this is a prune, not a round limit. Unlimited-rounds BnB should be an exact detector here.
## Mechanism
| selection | weight, no change | weight, with change | change? | `Changeless` score |
| --- | --- | --- | --- | --- |
| `{0}` | 342 | 514 (fits) | yes, 111 732 | rejected — has change |
| `{0,2}` | 710 (exactly the cap) | 882 (**over** cap) | no | **305 618** |
At node `{0}`, `LowestFee` wants change, so `change_unavoidable` looks for a reachable selection with less excess. The only remaining coin (candidate 1) has *positive* effective value (+875), so nothing is added; the "least excess" selection is `{0}` itself, which still has change → **prune**. But `{0,2}` sits under `{0}`, and it is changeless because its change would weigh 882 > 710.
## Fix options — input wanted
1. **Make the shortcut cap-aware.** Don't prune when a reachable selection could exceed the cap *with* change weights. Cheap conservative test: if selecting everything still fits under cap-with-change, prune as today; otherwise don't. Keeps the prune wherever it is valid.
2. **Drop the shortcut whenever `target.max_weight.is_some()`.** Simplest and correct; loses pruning on every capped problem.
3. **Have the inner metric say *why* it refused change** (not worthwhile / dust / too heavy) so the wrapper can reason instead of guessing. More invasive, but removes the guesswork for good — and any future reason for refusing change won't silently reintroduce this.
My read: (1) is the best cost/benefit, (3) is the honest fix. Which do you prefer?
## Notes
- Unrelated to unconfirmed ancestors — reproduces on plain master, and predates #64.
- Distinct from #17 (`Changeless` usefulness when combined), though both are about this wrapper.
- In #64 the new `Changeless` proptest forces `max_weight: None` with a comment pointing here, so this stays visible rather than hidden.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start with Changeless::change_unavoidable and inspect how it evaluates LowestFee when Target::max_weight is set. Reproduce the three-candidate case, comparing common::exhaustive_search with common::bnb_search. Done means BnB finds the changeless selection instead of pruning it, with the relevant regression coverage added; the issue leaves the preferred fix to be decided.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- backend
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100