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.

Sign up for GitHub

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

Jump to bottom

Refactor/use iterators to preselect utxos #1798

Open
wants to merge 5 commits into
base: master
Choose a base branch
from
Open

Refactor/use iterators to preselect utxos #1798

wants to merge 5 commits into from

Conversation

nymius
Copy link
Contributor

@nymius nymius commented Jan 13, 2025

Description

There were multiple calls for de-duplication of selected UTxOs in Wallet::create_tx: (1) and (2).

As the test test_filter_duplicates shows, there are four possible cases for duplication of UTxOs while feeding the coin selection algorithms.

  1. no duplication: out of concern
  2. duplication in the required utxos only: covered by the source of required_utxos, Wallet::list_unspent, which roots back the provided UTxOs to a HashMap which should avoid any duplication by definition
  3. duplication in the optional utxos only: is the only one possible as optional UTxOs are stored in a Vec and no checks are performed about the duplicity of their members.
  4. duplication across the required and optional utxos: is already covered by Wallet::preselect_utxos, which avoid the processing of required UTxOs while listing the unspent available UTxOs in the wallet.

This refactor does the following:

  • Refactors TxParams::utxos type to be HashSet<LocalOutput> avoiding the duplication case 3
  • Keeps avoiding case 4 without overhead and allowing a query closer to O(1) on avg. to cover duplication case 4 (before was O(n) where n is the size of required utxos) thanks to the above change.
  • Still covers case 2 because the source of required_utxos, Wallet::list_unspent comes from a HashMap which should avoid duplication by definition.
  • Moves the computation of the WeightedUtxos to the last part of UTxO filtering, allowing the unification of the computation for local outputs.
  • Removes some extra allocations done for helpers structures or intermediate results while filtering UTxOs.
  • Allows for future integration of UTxO filtering methods for other utilities, e.g.: filter locked utxos 
    .filter(|utxo| !self.is_utxo_locked(utxo.outpoint, self.latest_checkpoint().height()))
  • Adds more comments for each filtering step.
  • Differentiates foreign_utxos, which should include a provided satisfation weight to use them effectively, and utxos, manually selected UTxOs for which the wallet can compute their satisfaction weight without external resources.

With these changes all four cases would be covered, and coin_selection::filter_duplicates is no longer needed.

Fixes #1794.

Notes to the reviewers

I haven't added test because the refactor doesn't include new features and the duplication improvements are based on the nature of structs that avoid duplication per se (HashMap, HashSet).

Changelog notice

No changes to public APIs.

Checklists

  • I've signed all my commits
  • I followed the contribution guidelines
  • I ran cargo fmt and cargo clippy before committing
  • This pull request breaks the existing API No
  • I've added tests to reproduce the issue which are now passing I haven't added any new tests
  • I'm linking the issue being fixed by this PR

@nymius
refactor(wallet): use iterators and adaptors in preselect_utxos
389de5d 
There were multiple calls for de-duplication of selected UTxOs.

As the test `test_filter_duplicates` shows, there are four possible
cases for duplication of UTxOs while feeding the coin selection
algorithms.

1. no duplication: out of concern
2. duplication in the required utxos only: covered by the source of
   `required_utxos`, `Wallet::list_unspent`, which roots back the
   provided `UTxOs` to a `HashMap` which should avoid any duplication by
   definition
3. duplication in the optional utxos only: is the only one possible as
   optional `UTxOs` are stored in a `Vec` and no checks are performed
   about the duplicity of their members.
4. duplication across the required and optional utxos: is already
   covered by `Wallet::preselect_utxos`, which avoid the processing of
   required UTxOs while listing the unspent available UTxOs in the
   wallet.

This refactor changes:
- `TxParams::utxos` type to be `HashSet<LocalOutput>` avoiding the
  duplication case 3, and allowing a query closer to O(1) on avg. to
  cover duplication case 4 (before was O(n) where n is the size of
  required utxos).
- Moves the computation of the `WeightedUtxos` to the last part of UTxO
  filtering, allowing the unification of the computation for local
  outputs.
- Removes some extra allocations done for helpers structures or
  intermediate results while filtering UTxOs.
- Allows for future integration of UTxO filtering methods for other
  utilities.
- Adds more comments for each filtering step.

With these changes all four cases would be covered, and
`coin_selection::filter_duplicates` would be no longer needed.
@evanlinjin
Copy link
Member

Hey @nymius, does this actually fix something or is this purely a refactor?

Note that we want to redo the tx building / creating logic to use bdk_coin_select and miniscript planning module so I think it's good policy to only do changes that are fixes or implement features that users are requesting.

evanlinjin
evanlinjin reviewed Jan 14, 2025
View reviewed changes
crates/wallet/src/wallet/mod.rs
Comment on lines +1984 to +2021
// only process optional UTxOs if manually_selected_only is false
.take_while(|_| !params.manually_selected_only)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think you are trying to be too fancy here. It'll be easier to read if we use an if statement and have may_spend as a separate variable.

let may_spend = if params.manually_selected_only {
    // This will be empty
} else {
    self.list_unspent()
    // etc...
};

@nymius
Copy link
Contributor Author

nymius commented Jan 14, 2025 •
edited
Loading

Hey @nymius, does this actually fix something or is this purely a refactor?

Hi @evanlinjin. Yes, maybe I went to far with the changes, still, it fixes the duplicate issue I open in #1794 by using a HashSet to handle manually selected UTxOs.

Then, about the refactor:

The research of the code push me to isolate the pre selection steps as items on a checklist and that's why It ended up as a refactor.

My idea is to further isolate each filter in their own iterator adaptor (a separated function for each one) that consumes impl Iterator<Item = LocalOutputs> and returns the same type, to later also allow the introduction of custom filters in TxParams which I think can be helpful to implement checks on the ability to spend a Taproot output, for example, in Silent Payments.

The heavy use of iterators came for trying to avoid the allocation of helpers, like satisfies_confirmed.

I envisioned something like this:

let optional_utxos = self
    .list_unspent()
    .check_are_not_already_manually_selected()
    .check_are_not_unspendable()
    .check_confirmed_only_if_RBF()
    .check_is_local_utxo()
    .check_is_mature_if_coinbase();
// then
let (required, optional) = optional_utxos.chain(required_utxos.iter().clone())
    .get_weighted_utxos()
    .chain(foreign_utxos.iter().clone())
    .apply_custom_validation_for_all_tx_inputs()
    .split_utxos_in_required_and_optional()

Discussing this today with @ValuedMammal, I decided to do the following changes:

  1. Just return optional utxos as they are the only needed values.
  2. Move the calculus of WeightedUtxos to another method. Placed inside create_tx for now
  3. Rename preselect_utxos to filter_utxos to correct the semantics the above point will change.
  4. Implement unit test for the feature to make the PR sound.
  5. Make current_height parameter not optional.

If we don't agree on the above, I propose the following alternatives:

  • keep points 1 and 2 above.
  • keep the old filtering implementation in place.
  • keep the changes to the build_fee_bump (new foreign_utxos field in TxParams).
  • drop all the other changes.

@nymius nymius force-pushed the refactor/use-iterators-to-preselect-utxos branch from 05ac09c to e42b5aa Compare January 15, 2025 21:30
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@evanlinjin evanlinjin evanlinjin left review comments

At least 1 approving review is required to merge this pull request.

Assignees

@nymius nymius

Labels
module-wallet
Projects
BDK
Status: In Progress
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

Utxo filtering done twice (presumed redundantly) while creating transaction
3 participants
@nymius @evanlinjin @notmandatory