[Bug]: Branch and Bound coin selection fails on fragmented wallet #843
Description
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
- Generate a fragmented wallet using seedkit:
This creates 18 UTXOs ranging from 2,000 to 9,100 sat across 18 addresses.
cd bitkit-e2e-tests/tools/seedkit && go build -o seedkit . ./seedkit run fragmented
- Restore the generated mnemonic in Bitkit Android.
- Wait for sync to complete (18 UTXOs, ~88,900 sat total).
- Go to Settings > Coin Selection > verify Autopilot with Branch and Bound is selected (default).
- Attempt to send 35,000 sat to any address.
- Observe: "Send Error - Coin selection failed".
- Go to Settings > Coin Selection > switch to Largest First or First-In-First-Out.
- Retry the same send.
- Observe: transaction succeeds.
Logs / Screenshots / Recordings
Screen.Recording.2026-03-12.at.16.03.29.mov
Bitkit Version
2.1.0
Device / OS
Android Emulator, Android 13 (API 33)
Reproducibility
Always
Additional context
- iOS counterpart: [Bug]: Branch and Bound coin selection fails on fragmented wallet bitkit-ios#489
- 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, not Bitkit's UI. 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 iOS (will file separately).
- The fragmented wallet scenario (18 UTXOs, 2k-9.1k sat) is realistic for users who receive many small payments (e.g., merchants, tipping).