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

[evanlinjin]

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 #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)

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::<Vec<_>>() {
        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

#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 #47.