create_tx returns wrong fee in TransactionDetails

[icota]

Code:

    #[test]
    fn test_create_psbt() {
        let wallet =
            Wallet::new("wpkh([96f9192b/84h/0h/0h]tpubDCxzhZZE31g2EqSv1UajMAw5Hd62htydz9r2XBkrccHgBh8uw3n62zr6Zjmj64tfTk8Tjxo6VctjUMAh5DXWTErfQPC6RmQhTdtNnXuTXTQ/0/*)",
                        Some("wpkh([96f9192b/84h/0h/0h]tpubDCxzhZZE31g2EqSv1UajMAw5Hd62htydz9r2XBkrccHgBh8uw3n62zr6Zjmj64tfTk8Tjxo6VctjUMAh5DXWTErfQPC6RmQhTdtNnXuTXTQ/1/*)"),
                        Network::Testnet,
                        MemoryDatabase::new()).unwrap();

        let client = get_electrum_client(-1, "ssl://electrum.blockstream.info:60002").unwrap();
        let blockchain = ElectrumBlockchain::from(client);
        wallet.sync(&blockchain, SyncOptions { progress: None }).unwrap();

        let send_to = Address::from_str("tb1ql7w62elx9ucw4pj5lgw4l028hmuw80sndtntxt").unwrap();

        let mut builder = wallet.build_tx();
        builder
            .add_recipient(send_to.script_pubkey(), 8630)
            .enable_rbf()
            .fee_rate(FeeRate::from_sat_per_vb(2.01));

        let (psbt, details) = builder.finish().unwrap();

        let encoded = base64::encode(&serialize(&psbt));

        println!("{:#?}", details);
        println!("Serialised PSBT: {}", encoded);
    }

Output:

TransactionDetails {
    transaction: None,
    txid: 5b26b2f1d02a3e4071b59eafb9f850be7d0473932c89fab1eb87431786e97454,
    received: 0,
    sent: 8859,
    fee: Some(
        286,
    ),
    confirmation_time: None,
}

Serialised PSBT: cHNidP8BAFIBAAAAAdOTVyY/5hjDQYUKam9+g6bkbxJ4PwvD3f1Saf/KEDVgAQAAAAD9////AbYhAAAAAAAAFgAU/52lZ+YvMOqGVPodX71HvvjjvhPM3CIAAAEA3gIAAAAAAQGf1tOQsvoLPsvez3A80v2JnOBScd2/7kkBqLrQhQUZgQEAAAAA/f///wLoAwAAAAAAABYAFMdzEdB6CzwaFgVhItyENxRYlPAXmyIAAAAAAAAWABTnWaUiYJz7lGIpOKDhy2pDK8WddgJHMEQCIGT75qgVcsjPfDInYlkLAnO+0AhSHdIel7O9wnpndNtFAiAJBZpGgEymbymAkWdTPw/KiR0bz40NOSmyqZtnE09tqgEhAnqMGbHDlAgnb9QreIPgd3/Ysnc7p/NdaFLQrMWiLrUX2WciAAEBH5siAAAAAAAAFgAU51mlImCc+5RiKTig4ctqQyvFnXYiBgMGUe86OhUasoZU7VPVXj8wODEei5kKSGWu/tUHEW1m9hiW+RkrVAAAgAAAAIAAAACAAQAAAAUAAAAAAA==

At first glance 8630 + 286 = 8916 is greater than both TransactionDetails sent value and the balance of UTXOs of the provided tpub which at this time is 8859 sats.

Back of envelope calculations say fee for this tx should be 229 sats. Parsing the above PSBT with Core's decodepsbt confirms it:

                ]
            }
        ],
        "outputs": [
            {}
        ],
        "fee": 0.00000229
    }
]

Build environment

BDK tag/commit: a328607
OS+version: Ubuntu 22.04
Rust/Cargo version: 1.54.0
Rust/Cargo target: x86_64

[danielabrozzoni]

Thanks for opening the issue! You're right, there's definitely something weird going on, I'm looking into it.

Out of curiosity: can you actually finalize the psbt? (Using the private descriptors instead of the public ones).
If so, what's the feerate of the finalized tx?

I wonder if the problem is that the specified fee_rate is too high and we don't correctly handle this case

[evanlinjin]

I just wanted to point out that the example code is written as a test and...

/// Default coin selection algorithm used by [`TxBuilder`](super::tx_builder::TxBuilder) if not
/// overridden
#[cfg(not(test))]
pub type DefaultCoinSelectionAlgorithm = BranchAndBoundCoinSelection;
#[cfg(test)]
pub type DefaultCoinSelectionAlgorithm = LargestFirstCoinSelection; // make the tests more predictable

Just in case the bug is algorithm-specific.

[icota]

Thanks for looking into this!

@danielabrozzoni I can finalize the above PSBT without issue.

@evanlinjin my colleague @BitcoinQnA noticed this in "production" so it's probably reproducible with both of the above algorithms.

[danielabrozzoni]

The good news is that @csralvall's #630 fixed the problem (and we didn't even notice in code review 😁). #666 will add a test to make sure we don't introduce those bugs anymore, and me and @afilini are discussing how to better test the fee calculation and the coin selection (spoiler: fuzzing 🌸)

Just for the sake of completeness, the original issue was that we would calculate drain_val using saturating_sub:

bdk/src/wallet/mod.rs

Line 819 in 3644a45

let drain_val = (coin_selection.selected_amount() - outgoing).saturating_sub(fee_amount);

Which means that if coin_selection.selected_amount() - outgoing - fee_amount was supposed to be <0, using saturating_sub it would result in 0.

Which is fine... unless you suppose the value of drain_val is precise, and you add it back to the fees when no drain output is created:

bdk/src/wallet/mod.rs

Lines 841 to 843 in 3644a45

	if drain_val.is_dust(&drain_output.script_pubkey) {
	fee_amount += drain_val;
	} else {

Which is exactly what was happening here: drain_val was 0, but coin_selection.selected_amount() - outgoing - fee_amount was -57, which meant that we added 0 instead of -57 to the fee_amount, and it would result in 286 instead of 229.