bitcoindevkit / bitcoindevkit/coin-select

LowestFee::bound's resize lower bound is inadmissible: greedy prefix's segwit corrections inflate ideal_fee

Open
#56 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
18
Forks
14
PR merge metrics
No merged PRs in 30d

Description

## Summary

`LowestFee::bound`'s "resize trick" lower bound is inadmissible: the crossing point and `scale` are computed from the greedy prefix's **actual** fee and weight, which include `input_weight()`'s non-additive corrections (+2 wu witness header once the tx is segwit, +1 wu per legacy input in a segwit tx, input-count varint growth). A target-meeting descendant that avoids the prefix's segwit corrections pays less fee than the returned `ideal_fee`, so `bound()` can exceed a real descendant's `score()`. Per the `BnbMetric::bound` contract this silently prunes the branch containing the true lowest-fee selection, and BnB returns a suboptimal (higher-fee) coin selection.

Verified on current master (cd8cec4) with a deterministic 136-sat violation (repro below).

## Mechanism

`bound()` (target not yet met) walks the `value_pwu`-sorted unselected list until `is_funded`, deselects the crossing input, and computes `scale` from `rate_excess_wu` of the prefix — quantities that embed the prefix's corrected weight. With a segwit candidate at the head of the ordering:

- the prefix carries +2 (witness header) and +1 per legacy input of correction weight;
- an all-legacy descendant avoids those corrections, so it can meet the target with a real fee a few sats **below** `ideal_fee`.

The same correction-blindness affects the walk in two more spots (found while reviewing bitcoindevkit/coin-select#47, which hit the analogous bug in its new metric):

1. the `max_weight` fractional prune compares the *prefix's corrected* weight against the cap, so it can return `None` (prune) although a correction-avoiding descendant fits under the cap;
2. the `select_iter().find(is_funded)? -> None` prune assumes prefix-funded-ness is exhaustive, but a subset that *excludes* a positive-ev candidate whose marginal corrections outweigh its ev can be funded while no prefix is.

## Reproduction (against master)

```rust
use bdk_coin_select::metrics::LowestFee;
use bdk_coin_select::{
BnbMetric, Candidate, CoinSelector, Drain, DrainWeights, FeeRate, Target, TargetFee,
TargetOutputs,
};

#[test]
fn lowest_fee_bound_beaten_by_correction_avoiding_descendant() {
// feerate 100 sat/vb (25 spwu).
let rate = FeeRate::from_sat_per_vb(100.0);
let candidates = vec![
// SW: same raw weight as L1/L2 but 10 sats more -> best value_pwu, so the greedy
// prefix takes it first and carries +2 (header) +1 (L1's witness-length byte) wu of
// corrections that the all-legacy descendant {L1, L2} avoids.
Candidate { value: 20_010, weight: 400, input_count: 1, is_segwit: true },
Candidate { value: 20_000, weight: 400, input_count: 1, is_segwit: false },
Candidate { value: 20_000, weight: 400, input_count: 1, is_segwit: false },
];
let mut cs = CoinSelector::new(&candidates);
cs.sort_candidates_by_descending_value_pwu();

// D = {L1, L2}.
let mut d = cs.clone();
for (idx, c) in cs.candidates().collect::>() {
if !c.is_segwit {
d.select(idx);
}
}

let mut t = Target {
fee: TargetFee { rate, absolute: 0, replace: None },
outputs: TargetOutputs { value_sum: 0, weight_sum: 100, n_outputs: 1 },
max_weight: None,
};
// Pad so W_D % 4 == 0: fee(W_D) has no vbyte rounding and the prefix's +3 wu of
// corrections cross a vbyte boundary (the walk cannot stop at {SW, L1}).
let w_d = d.weight(t.outputs, DrainWeights::NONE);
t.outputs.weight_sum += (4 - (w_d % 4)) % 4;
// T such that D overshoots by exactly 2 sats.
let fee_d = rate.implied_fee(d.weight(t.outputs, DrainWeights::NONE));
t.outputs.value_sum = 40_000 - fee_d - 2;

let mut metric = LowestFee {
long_term_feerate: FeeRate::from_sat_per_vb(1.0),
dust_relay_feerate: FeeRate::from_sat_per_vb(1.0),
drain_weights: DrainWeights { output_weight: 100, spend_weight: 600, n_outputs: 1 },
};

let score = metric.score(&d, t).expect("D is funded and scoreable");
let bound = metric.bound(&cs, t).expect("root bound exists");
assert!(bound <= score, "INADMISSIBLE: bound {:?} > score {:?}", bound, score);
}
```

Output on cd8cec4:

```
excess(D)=2 score(D)=Ordf32(23502.0) bound(root)=Ordf32(23638.0)
INADMISSIBLE: bound Ordf32(23638.0) > score Ordf32(23502.0)
```

The walk selects `SW`, cannot stop at `{SW, L1}` (the +3 wu of corrections push it across a vbyte boundary), crosses at `L2`, and returns `ideal_fee` based on the corrected prefix — 136 sats above what `{L1, L2}` actually pays.

## Suggested fix

bitcoindevkit/coin-select#47 hit the same defect in its `ChangelessWaste` metric and fixed it by replacing the resize walk with a fractional knapsack computed **entirely in raw-weight-linear arithmetic**: any target-met descendant `D ⊇ cs` satisfies `Σ ev_lin(D∖cs) >= gap` with `ev_lin = value - raw_weight * spwu` and `gap = target.value + W(cs)*spwu - selected_value(cs)` (the true fee only rounds *up* from the linear fee, and `cs`'s corrections are common to every descendant while corrections only grow). The greedy order is unchanged (`ev_lin/raw = value_pwu - spwu` is monotone in `value_pwu`), and the resulting quantity cannot be undercut by correction avoidance. The same treatment works in fee space: `ideal_fee_lin = gap`-covering value sum instead of the prefix-derived `scale * value`. That PR's discussion/commits (`resize_bound` caveat note, `ChangelessWaste::bound` derivation) have the details.

Found during a review of bitcoindevkit/coin-select#47.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start at LowestFee::bound and compare its resize walk with the ChangelessWaste::bound derivation discussed in coin-select#47. Run the provided lowest_fee_bound_beaten_by_correction_avoiding_descendant reproduction first, then verify the fee and max_weight pruning paths using raw-weight-linear arithmetic. Done means bound remains admissible for correction-avoiding descendants and the regression passes.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
blockchain
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
55/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.