bitcoindevkit / bitcoindevkit/bdk_wallet

Coin selection fallback selects UTXOs with negative effective value

Open
#553 0 comments 0 reactions 0 assignees View on GitHub
bug discussion
Dominant language
Rust
Stars
59
Forks
105
Avg merge
10d 9h
Merged PRs (30d)
1

Description

**Describe the bug**

`BranchAndBoundCoinSelection::coin_select` filters optional UTXOs to positive effective value before running BnB (`src/wallet/coin_selection.rs`, `optional_ogs` with `.filter(|u| u.effective_value.is_positive())`). When BnB does not find a changeless solution (the common case), it falls back to `self.fallback_algorithm.coin_select(required_utxos, optional_utxos, ...)` with the **original, unfiltered** `optional_utxos`. `select_sorted_utxos`, used by `SingleRandomDraw`, `LargestFirst` and `OldestFirst`, has no effective-value check, so UTXOs whose value is below their own spend cost at the requested fee rate get selected.

Each such input reduces the change by (spend cost − value). Because adding one raises the fee target faster than the accumulated value, the loop may also run out of UTXOs and return `InsufficientFunds` even though a valid selection exists.

This is likely acceptable or intended in some setups (dust consolidation, or users are expected to mark dust unspendable), so this issue is mainly to gather feedback on whether the fallback should apply the same filter as BnB.

This issue was found by AI.

**To Reproduce**

```rust
// wallet funded with one 50_000 sat UTXO (test_utils), plus 8 x 300 sat outputs
let (mut wallet, _) = get_funded_wallet_wpkh();
for _ in 0..8 {
receive_output_in_latest_block(&mut wallet, Amount::from_sat(300));
}
let addr = wallet.next_unused_address(KeychainKind::External);
let mut builder = wallet.build_tx();
builder
.add_recipient(addr.script_pubkey(), Amount::from_sat(30_000))
.fee_rate(FeeRate::from_sat_per_vb_unchecked(50));
let res = builder.finish();
```

Over 50 runs on master (`6fc68462`): 25 failed with `InsufficientFunds { needed: 62_675 sat, available: 52_400 sat }`; of the 25 successful builds, 21 included dust inputs and paid 10,425–20,625 sat in fees versus 7,025 sat for the single-input solution.

**Expected behavior**

Coin selection should not fail, or pay noticeably more, when a straightforward selection from positive-effective-value UTXOs exists. How the fallback treats negative-effective-value UTXOs is up to the maintainers.

**Build environment**
- BDK tag/commit: `6fc68462` (master)

**Which backend(s) are relevant (if any)?**
- [x] None / not backend-related (e.g. `bdk_chain`, `bdk_core`)

**Is this blocking production use?**
- [x] No

Contributor guide

Open the contributing guide

Research direction

Start in src/wallet/coin_selection.rs at BranchAndBoundCoinSelection::coin_select, optional_utxos, and the fallback call. Reproduce the provided wallet scenario at a 50 sat/vB fee rate, then inspect select_sorted_utxos and the fallback algorithms. Done means the fallback behavior for negative-effective-value UTXOs is decided and the reported unnecessary failures or excess fees are covered by a regression test.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
blockchain
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
65/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.