[Bug]: Branch and Bound coin selection fails on fragmented wallet

[piotr-iohk]

What happened?

Sending 35,000 sat from a wallet with 18 small UTXOs (2,000–9,100 sat each, ~88,900 sat total) fails with "Coin selection failed" when using the default Branch and Bound algorithm.

Switching coin selection to Largest First or First-In-First-Out allows the same send to succeed.

Expected behavior

Branch and Bound should successfully select UTXOs and build a valid transaction when the total wallet balance is well above the send amount (88,900 sat available, sending 35,000 sat).

Steps to Reproduce

1. Generate a fragmented wallet using seedkit:

   cd bitkit-e2e-tests/tools/seedkit && go build -o seedkit .
   ./seedkit run fragmented

   This creates 18 UTXOs ranging from 2,000 to 9,100 sat across 18 addresses.
2. Restore the generated mnemonic in Bitkit iOS.
3. Wait for sync to complete (18 UTXOs, ~88,900 sat total).
4. Go to Settings > Coin Selection > verify Autopilot with Branch and Bound is selected (default).
5. Attempt to send 35,000 sat to any address.
6. Observe: "Send Error - Coin selection failed".
7. Go to Settings > Coin Selection > switch to Largest First or First-In-First-Out.
8. Retry the same send.
9. Observe: transaction succeeds.

Logs / Screenshots / Recordings

bitkit_logs_2026-03-12_14-42-13.zip

Screen.Recording.2026-03-12.at.16.11.01.mov

Bitkit Version

2.0.4

Device / OS

iOS Simulator

Reproducibility

Always

Additional context

• Android counterpart: [Bug]: Branch and Bound coin selection fails on fragmented wallet bitkit-android#843
• Wallet was restored from backup (seedkit-generated mnemonic on regtest).
• On-chain only, no Lightning channels.
• The issue is in the BDK/LDK-Node coin selection layer. Branch and Bound likely fails to find an exact-match solution among many small inputs and doesn't fall back to combining them.
• Same issue reproduced on Android: [Bug]: Branch and Bound coin selection fails on fragmented wallet bitkit-android#843
• The fragmented wallet scenario (18 UTXOs, 2k-9.1k sat) is realistic for users who receive many small payments (e.g., merchants, tipping).
• Related user report: a user reported coin selection failure in Slack on Mar 11 (screenshots of "Send Error - Coin selection failed" on iOS with Autopilot/Branch and Bound).