Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Utxo filtering done twice (presumed redundantly) while creating transaction #1794

Open
nymius opened this issue Jan 9, 2025 · 2 comments · May be fixed by #1798
Open

Utxo filtering done twice (presumed redundantly) while creating transaction #1794

nymius opened this issue Jan 9, 2025 · 2 comments · May be fixed by #1798

Comments

@nymius
Copy link
Contributor

nymius commented Jan 9, 2025

Description

Wallet::create_tx is removing duplicated utxos twice.
Wallet::preselect_utxos is used in Wallet::create_tx to get the required and optional utxos. Notice that Wallet::preselect_utxos already filters required utxos from the list of optional ones. However, a second filtering is performed anyways with coin_selection::filter_duplicates a few lines later in the same Wallet::create_tx. I think one of the two is redundant.

I created a test to assert what I'm referring here. It changes some parts of the API visibility to allow the isolation of the referred function calls.

diff --git a/crates/wallet/src/wallet/coin_selection.rs b/crates/wallet/src/wallet/coin_selection.rs
index 4429fae7..bbad2d84 100644
--- a/crates/wallet/src/wallet/coin_selection.rs
+++ b/crates/wallet/src/wallet/coin_selection.rs
@@ -723,7 +723,7 @@ fn calculate_cs_result(
 /// Remove duplicate UTXOs.
 ///
 /// If a UTXO appears in both `required` and `optional`, the appearance in `required` is kept.
-pub(crate) fn filter_duplicates<I>(required: I, optional: I) -> (I, I)
+pub fn filter_duplicates<I>(required: I, optional: I) -> (I, I)
 where
     I: IntoIterator<Item = WeightedUtxo> + FromIterator<WeightedUtxo>,
 {
diff --git a/crates/wallet/src/wallet/mod.rs b/crates/wallet/src/wallet/mod.rs
index 2e068a95..fea34bd8 100644
--- a/crates/wallet/src/wallet/mod.rs
+++ b/crates/wallet/src/wallet/mod.rs
@@ -1989,7 +1989,7 @@ impl Wallet {
 
     /// Given the options returns the list of utxos that must be used to form the
     /// transaction and any further that may be used if needed.
-    fn preselect_utxos(
+    pub fn preselect_utxos(
         &self,
         params: &TxParams,
         current_height: Option<u32>,
diff --git a/crates/wallet/src/wallet/tx_builder.rs b/crates/wallet/src/wallet/tx_builder.rs
index 868d51df..aeb76d3b 100644
--- a/crates/wallet/src/wallet/tx_builder.rs
+++ b/crates/wallet/src/wallet/tx_builder.rs
@@ -111,21 +111,21 @@ use crate::{KeychainKind, LocalOutput, Utxo, WeightedUtxo};
 #[derive(Debug)]
 pub struct TxBuilder<'a, Cs> {
     pub(crate) wallet: &'a mut Wallet,
-    pub(crate) params: TxParams,
+    pub params: TxParams,
     pub(crate) coin_selection: Cs,
 }
 
 /// The parameters for transaction creation sans coin selection algorithm.
 //TODO: TxParams should eventually be exposed publicly.
 #[derive(Default, Debug, Clone)]
-pub(crate) struct TxParams {
+pub struct TxParams {
     pub(crate) recipients: Vec<(ScriptBuf, Amount)>,
     pub(crate) drain_wallet: bool,
     pub(crate) drain_to: Option<ScriptBuf>,
     pub(crate) fee_policy: Option<FeePolicy>,
     pub(crate) internal_policy_path: Option<BTreeMap<String, Vec<usize>>>,
     pub(crate) external_policy_path: Option<BTreeMap<String, Vec<usize>>>,
-    pub(crate) utxos: Vec<WeightedUtxo>,
+    pub utxos: Vec<WeightedUtxo>,
     pub(crate) unspendable: HashSet<OutPoint>,
     pub(crate) manually_selected_only: bool,
     pub(crate) sighash: Option<psbt::PsbtSighashType>,
diff --git a/crates/wallet/tests/wallet.rs b/crates/wallet/tests/wallet.rs
index dcc8030b..b26c711a 100644
--- a/crates/wallet/tests/wallet.rs
+++ b/crates/wallet/tests/wallet.rs
@@ -819,6 +819,44 @@ fn test_create_tx_drain_wallet_and_drain_to_and_with_recipient() {
     );
 }
 
+#[test]
+fn filter_candidate_utxos_twice() {
+    use bdk_wallet::TxParams;
+    use bdk_wallet::{Utxo, WeightedUtxo};
+    let (wallet, _) = get_funded_wallet_wpkh();
+
+    let ((required_v1, optional_v1), last_utxo) = {
+        let utxos: Vec<_> = wallet.list_unspent().map(|u| u.outpoint).collect();
+        let mut params = TxParams::default();
+        let last_utxo = wallet.get_utxo(*utxos.last().unwrap()).unwrap();
+        let descriptor = wallet.public_descriptor(last_utxo.keychain);
+        let satisfaction_weight = descriptor.max_weight_to_satisfy().unwrap();
+        params.utxos.push(WeightedUtxo {
+            satisfaction_weight,
+            utxo: Utxo::Local(last_utxo.clone()),
+        });
+        (wallet.preselect_utxos(&params, None), last_utxo)
+    };
+
+    let ((required_v3, optional_v3), optional_v2) = {
+        use bdk_wallet::coin_selection;
+
+        let descriptor = wallet.public_descriptor(last_utxo.keychain);
+        let satisfaction_weight = descriptor.max_weight_to_satisfy().unwrap();
+        let mut optional_v2 = optional_v1.clone();
+        optional_v2.push(WeightedUtxo {
+            satisfaction_weight,
+            utxo: Utxo::Local(last_utxo),
+        });
+        (coin_selection::filter_duplicates(required_v1.clone(), optional_v2.clone()), optional_v2)
+    };
+
+    assert_eq!(required_v1, required_v3);
+    assert!(optional_v1 != optional_v2);
+    assert_eq!(optional_v1, optional_v3);
+}
+
+
 #[test]
 fn test_create_tx_drain_to_and_utxos() {
     let (mut wallet, _) = get_funded_wallet_wpkh();

Probably the only case where the second coin_selection::filter_duplicate is triggered is when drain_wallet is true. I think this can be refactored to avoid the burden for all the other cases.

@nymius
Copy link
Contributor Author

nymius commented Jan 13, 2025

There is a test for coin_selection::filter_duplicates which expresses the different duplicate cases clearly:

  1. no duplication
  2. duplication in the required utxos only
  3. duplication in the optional utxos only
  4. duplication across the required and optional utxos.

Case 1 is out of concern.
Case 2 is covered by the source of required_utxos, list_unspent which roots back the provided UTxOs to a HashMap which should avoid any duplication by definition.
Case 4 is the one I'm claiming is already covered by Wallet::preselect_utxos.
Case 3 is the only one I found should be useful in Wallet::create_tx after UTxO preselection, as optional UTxOs are stored in a Vec and no checks are performed about the duplicity of their members.

@ValuedMammal
Copy link
Contributor

I agree it would be ideal to not have to use filter_duplicates and instead ensure that the wallet doesn't produce duplicate candidates. Apparently it's possible to call add_utxo multiple times with the same outpoint and I think that could be easily fixed. We also need to check that no foreign utxos are duplicated in either the required or optionals.

@nymius nymius linked a pull request Jan 13, 2025 that will close this issue
6 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Status: Todo
Development

Successfully merging a pull request may close this issue.

3 participants