Selections from select_utxos_with_algorithm are rejected by send_to_address (BranchAndBound always fails)

[jvsena42]

Summary

OnchainPayment::select_utxos_with_algorithm and Wallet::build_transaction_psbt disagree about what a valid UTXO selection is. The result: a selection produced by select_utxos_with_algorithm is rejected by send_to_address with Error::InsufficientFunds, even though the wallet holds far more than the send amount.

This is deterministic for CoinSelectionAlgorithm::BranchAndBound at ordinary fee rates, because BnB is designed to return changeless selections and build_transaction_psbt demands an excess that a changeless selection can never have.

Reproduced on v0.7.0-rc.62; both code paths are unchanged on main.

Downstream: synonymdev/bitkit-android#843, synonymdev/bitkit-ios#489.

Reproduction

Wallet: 18 P2WPKH UTXOs — 2000 3500 4200 5000 6100 7800 2500 3000 8900 4500 2100 5500 3200 6700 9100 4800 2700 7300 (88,900 sat total).

select_utxos_with_algorithm(target_amount_sats = 35_000,
                            fee_rate = 1 sat/vB,
                            algorithm = BranchAndBound)
  -> 10 UTXOs, 35,700 sat

send_to_address(addr, ExactRetainingReserve { amount_sats: 35_000 }, 1 sat/vB, utxos_to_spend = <above>)
  -> Err(InsufficientFunds)

Log:

DEBUG [ldk_node::wallet:1444] Found 18 spendable UTXOs out of 18 total UTXOs
ERROR [ldk_node::wallet:1550] Selected UTXOs have insufficient value. Have: 35700sats, Need at least: 36000sats

Switching the algorithm to LargestFirst or OldestFirst makes the identical send succeed, because those always leave a large change output.

Defect 1 — select_utxos_with_algorithm under-selects by the base-tx fee

src/payment/onchain.rs:372 passes the bare target_amount_sats through to crates/bdk-wallet-aggregate/src/utxo.rs:198:

let target = Amount::from_sat(target_amount);
...
BranchAndBoundCoinSelection::<SingleRandomDraw>::default().coin_select(
    vec![], weighted_utxos, fee_rate, target, drain_script, &mut rng,
)

BDK's coin_select contract is that target_amount already includes the fee for the base transaction — nVersion, nLockTime, the in/out counts, the segwit marker, and the recipient output(s). TxBuilder computes that before calling in; here nothing does. The selection therefore only ever covers amount + input fees, and is short by fee_rate × (tx overhead + recipient output vbytes).

In the repro: BnB covered 35,000 + 10 × 68 vB = 35,680 and returned 35,700. The real 10-in/1-out transaction is 722 vB, so 35,722 was required — 22 sat short. At higher fee rates the shortfall scales linearly.

Defect 2 — build_transaction_psbt's fee buffer is unrelated to the transaction

src/wallet/mod.rs:1539-1557:

// Assume a typical tx with 1 input and 2 outputs (~200 vbytes)
let typical_tx_weight = Weight::from_vb(200).expect("Valid weight");
let fee_buffer = fee_rate.fee_wu(typical_tx_weight).expect("Valid fee calculation").to_sat();
// Use at least 1000 sats as minimum buffer
let min_fee_buffer = fee_buffer.max(1000);
let min_required = amount_sats.saturating_add(min_fee_buffer);
if selected_value < min_required {
    return Err(Error::InsufficientFunds);
}

The buffer ignores the actual selected inputs, so it is wrong in both directions:

• Too strict. A changeless BnB solution has selected_value − amount_sats ≈ fee, and BnB only accepts solutions within cost_of_change of the target. At any fee rate at or below 5 sat/vB the .max(1000) floor exceeds that excess, so every successful BnB selection is rejected. This is why the bug reproduces 100% of the time rather than intermittently.
• Too lenient. A 10-input transaction at 5 sat/vB really costs ~3,765 sat, but only 1,000 is demanded — so a genuinely insufficient selection passes this check and fails later inside the PSBT builder.

Failure condition, in general: selected_total − amount_sats < max(200 × fee_rate, 1000).

Defect 3 (contributing) — the failure is invisible until broadcast time

OnchainPayment::calculate_total_fee (src/payment/onchain.rs:458) catches its own InsufficientFunds and silently retries as AllRetainingReserve, which does not run the guard:

if matches!(result, Err(Error::InsufficientFunds)) && amount_sats <= spendable_balance {
    let all_retaining = OnchainSendAmount::AllRetainingReserve { cur_anchor_reserve_sats };
    if let Ok(fee) = self.wallet.calculate_transaction_fee(address, all_retaining, ...) {
        return Ok(fee);
    }
}

So a caller estimating the fee for a selection that send_to_address will reject gets back a plausible drain fee (722 sat in the repro) with no error and no log at the caller's level. Wallets show the user a valid-looking confirmation screen, and the send only fails once they commit. Whatever the fix for defects 1 and 2, this fallback should at minimum be distinguishable by the caller.

Suggested fixes

1. select_utxos_with_algorithm should add the base-tx fee (overhead + recipient outputs at fee_rate) to the target before calling BDK's coin_select, matching the contract TxBuilder honours.
2. Replace the max(200 vB × fee_rate, 1000) heuristic with a fee derived from the actual selected input weights and the intended output set — or drop the pre-check entirely and let the PSBT builder report the real shortfall, which it already computes correctly.
3. Make calculate_total_fee's drain fallback observable to callers rather than silently substituting a different transaction's fee.

A regression test asserting that every CoinSelectionAlgorithm's output is accepted by send_to_address for the same target and fee rate would have caught this — the current coverage only asserts selected_total >= target, which is exactly the assertion that is too weak here.