Multi descriptor: Decouple transaction building logic by evanlinjin · Pull Request #647 · bitcoindevkit/bdk

evanlinjin · 2022-06-30T16:29:08Z

Description

The end goal of this PR is to have the ability to a single wallet with multiple descriptors.

Notes to the reviewers

In the Discord channel @ #multi-descriptor-wallets, @afilini suggested a roadmap:

I think a reasonable roadmap would be:

pr to add "database factories" or something similar

pr to add "multi-wallet" support (collection of the current Wallet struct). The subwallets will only use the "external" keychain, and at the multi-wallet level you can define what to use as internal/external

pr to remove the two keychains from the wallet struct, deal with renaming and deprecating stuff (users should switch from Wallet to MultiWallet with two subwallets etc)

The "database factories" structure is already implemented in a separate PR: #654 (And can be used later).

This PR mainly addresses the initial portion of step 2.

My Approach

The most difficult aspect of adding multi-descriptor capability is in the transaction creation. Everything else from retrieving address, UTXOs, signing, transactions, balances and syncing are trivial tasks. Hence, my approach is to first decouple the transaction building logic from Wallet so that it can be reused for multi-descriptor (or even for users of BDK that don't want a wallet). In that being said, I have kept what @afilini said in mind (paraphrasing)...

Avoid resulting in a huge pr that breaks everything.
... I'm sure it's gonna take a while to get pr 2 to work well and it's probably better if we avoid replacing the current Wallet with it immediately.

Therefore, I have ensured the following things for my approach:

Instead of moving logic out of Wallet, I have turned various member functions into static functions (renamed to start with _). The original functions will call these static functions. This way, we do not change the "external interface" of Wallet and more-or-less keep these bits and pieces in the same place (so hopefully git will not complain so much when we merge).
I have introduced a new trait SpendableCollection to replace the functionality of Wallet/Database within TxBuilder. To keep Wallet working with the new modified TxBuilder, a struct SpendablesFromDb is formed which implements SpendableCollection, and wraps Database (and some fields of Wallet).

Noteworthy changes

Not in any particular order...

Introduction of the SpendableCollection trait (and SpendableCollectionInner which defines it's "explicitly required" methods). These traits represent a collection of owned and spendable UTXO's, Descriptors and their associated transactions. Note that it's members SpendableCollectionInner::get_{external|internal}_descriptors returns Vecs (so we can support multiple descriptor implementations in the very near future).
The CoinSelectionAlgorithm trait's type constraint has been moved to it's function definition (the constrained type was only used as input anyway) - I hope this change is okay?

Instead of referencing descriptors by KeychainKind, I have changed to use the ExtendedDescriptor directly (again, for muti-descriptors in the future). This change has some small caveats...

bdk/src/wallet/spendable_collection.rs

Lines 73 to 101 in 574dcc4

    
               /// Obtains unspent UTXOs with satisfaction weights. 
        
               /// This was called get_available_utxos in [`Wallet`]. 
        
               /// 
        
               /// TODO @evanlinjin: 
        
               ///     With the old implementation, we can call `get_descriptor_from_keychain` to obtain the 
        
               ///     parent descriptor without relying on a "cache" of relationships between `ScriptPubKey`s 
        
               ///     and "paths". 
        
               ///     However, we cannot continue to use this approach since we need to generalize everything 
        
               ///     to support multiple descriptors. 
        
               ///     A possible solution would be to replace usage of [`KeychainKind`] with 
        
               ///     `(KeychainKind, u32)`, so descriptors are referenced with an additional index. 
        
               /// 
        
               ///     For now, we need to ensure the aforementioned relationship is sufficiently cached to 
        
               ///     avoid "missing" available UTXOs. 
        
               fn get_weighted_unspent_utxos(&self) -> Result<Vec<(LocalUtxo, usize)>, Error> { 
        
                   let out = self 
        
                       .get_unspent_utxos()? 
        
                       .iter() 
        
                       .filter_map(|utxo| { 
        
                           let (parent_desc, _) = self 
        
                               .get_path_of_script_pubkey(&utxo.txout.script_pubkey) 
        
                               // @evanlinjin: Will return here with `None` if not sufficiently cached. 
        
                               .unwrap()?; 
        
                           let weight = parent_desc.max_satisfaction_weight().unwrap(); 
        
                           Some((utxo.clone(), weight)) 
        
                       }) 
        
                       .collect::<Vec<_>>(); 
        
                   Ok(out) 
        
               }

bdk/src/wallet/mod.rs

Lines 5279 to 5283 in 574dcc4

    
           // @evanlinjin: If you are wondering why this line is added, see comments in 
        
           // [`SpendableCollection::get_weighted_unspent_utxos`]. 
        
           wallet 
        
               .cache_addresses(KeychainKind::External, 0, 5) 
        
               .unwrap();

TxBuilder, other than needing the BatchDatabase constraint with SpendableCollection, uses static members from Wallet (as mentioned above). Hence, we needed to add another phantom constraint imposed by the constraints of those Wallet methods (this can be removed once we ACTUALLY move stuff out of Wallet).
TODO @evanlinjin: I have probably forgotten to mention something here... I will keep this space updated.

Tests

It seems that I have not broken the functionality of Wallet and all the non-doc tests continue to pass.

Next steps

Once @afilini and everyone else is happy with my approach thus far, I will create a multi-descriptor implementation of SpendableCollection and do tests to see if multi-descriptor transaction creation works as expected.

Since CoinSelectionAlgorithm now takes a SpendableCollection as an input (instead of a BatchDatabase, I need to ensure that SpendableCollection is satisfactory for all coin selection algorithms.

I also still need to decouple Fee-bumping logic.

Checklists

All Submissions:

I've signed all my commits
I followed the contribution guidelines
I ran cargo fmt and cargo clippy before committing

New Features:

I've added tests for the new feature
I've added docs for the new feature
I've updated CHANGELOG.md

Bugfixes:

This pull request breaks the existing API
I've added tests to reproduce the issue which are now passing
I'm linking the issue being fixed by this PR

Store policy paths in a map with ExtendedDescriptor as key. This way we can re-use the TxParams struct in multi-descriptor/multi-wallet contexts.

Use `ExtendedDescriptor` instead of `Keychain`

This is a WIP. Explanation for my approach (will be / is) provided in the PR's description box.

* Added `MultiTracker::latest_blockheight` method. * Update documentation to reflect changes.

afilini

I still feel like I'm trying to wrap my head around this, but conceptually I think it makes sense and I really like how this allows us to slowly move away from Wallet by making it "backward compatible" with MultiTracker.

afilini · 2022-07-14T13:55:03Z

src/wallet/tx_builder.rs

-    pub(crate) internal_policy_path: Option<BTreeMap<String, Vec<usize>>>,
-    pub(crate) external_policy_path: Option<BTreeMap<String, Vec<usize>>>,
+    pub(crate) descriptor_policy_paths:
+        BTreeMap<&'a ExtendedDescriptor, BTreeMap<String, Vec<usize>>>,


Maybe we can avoid the lifetime by using something else as a key? like the descriptor's checksum?

I will change to use checksum once #671 is approved and merged :)

src/wallet/multi_tracker.rs

afilini · 2022-07-14T14:14:50Z

src/wallet/multi_tracker.rs

+    /// * Confirmed height.
+    /// * Descriptor + Child index.
+    /// * Satisfaction weight of scriptPubKey (weight of corresponding scriptSig/witness data).
+    fn iter_unspent(&self) -> Result<Box<dyn Iterator<Item = (LocalUtxo, usize)> + '_>, Error>;


We actually have a WeightedUtxo struct that is basically a utxo + the weight, maybe that's more convenient here

However, WeightedUtxo can be of a foreign Utxo so it is not as "direct" as using an union here (since this method is about iterating unspent, and owned UTXOs). Should I keep it as is?

afilini · 2022-07-14T14:16:25Z

src/wallet/multi_tracker.rs

+
+        let secp = SecpCtx::new();
+
+        for index in 0..2100_u32 {


Wait, that's a lot! Deriving all the descriptors up to index 2100 may take a very long time. Do you think it makes sense to add an extra argument for a "max index"? Most of the time I guess the caller would only need to derive up to 100/200

This is the default implementation of the method and I intended it just to be there for convenience. But you are right, so I've changed it to check for 200 iterations, and added a comment saying that this method should be overloaded. Would that be enough? It seems inelegant to add another input imo.

src/wallet/multi_tracker.rs

afilini · 2022-07-15T07:59:13Z

src/wallet/multi_tracker.rs

+        // TODO: Add as struct field
+        let desc_map = self
+            .iter_descriptors()?
+            .map(|desc| (desc.descriptor.to_string(), desc))


I think here again you can just use the checksum which is shorter

Will wait on #671 :)

afilini · 2022-07-15T08:11:47Z

src/wallet/multi_tracker.rs

+
+/// Implements [`MultiTracker`] with one external descriptor and an optional internal descriptor.
+// #[derive(Clone)]
+pub struct LegacyTracker<'a, D> {


Is there a specific reason why you chose to not let this struct own the descriptors and the database and instead use references?

Is it to make this easier to clone for example? I see that in the TxBuilder you have to clone this, in that case it makes sense, but then the question is: why can't you store a reference in the TxBuilder like we used to do before with the Wallet?

@afilini It is just to avoid copying data in memory. The assumption is that one would only use LegacyTracker with the existence of Wallet (which is a good assumption imo). Since, the whole point of LegacyTracker is to get Wallet to "implement" MultiTracker, since transaction-building and signing logic is to be wrapped around MultiTracker. Right now this tx logic uses static functions of Wallet (which is confusing), but will avoid annoying git as much as possible. Those static functions, responsible for tx logic, should eventually be moved out of Wallet when the time is right.

src/wallet/coin_selection.rs

afilini · 2022-07-15T08:20:49Z

src/wallet/coin_selection.rs

 ///
 /// For an example see [this module](crate::wallet::coin_selection)'s documentation.
-pub trait CoinSelectionAlgorithm<D: Database>: std::fmt::Debug {
+pub trait CoinSelectionAlgorithm: std::fmt::Debug {


I'm trying to figure out how these changes affect my original idea for the coin selection: the reason why the D generic was defined here was that we wanted to offer a way to use custom databases in a custom coin selection without being restricted on the API in any way.

For example, let's say I have my custom database that exposes some kind of metric that I'd like to use for the coin selection, then I can implement CoinSelectionAlgorithm<MyCustomDb> and this would make the cs get a &MyCustomDb (not a generic &dyn Database), which would allow me to use any custom API I have.

It's not the end of the world to lose this ability because again it was something that probably nobody used, but I think it was kind of cool and I'm wondering if we can somehow preserve this even with the MultiTracker.

But since CoinSelectionAlgorithm is a trait, we can have a struct implement CoinSelectionAlgorithm (with special databases and parameters as fields) so we can still do those custom algorithms without the need for the generic type. Let me know if I've missed something though

src/wallet/coin_selection.rs

… comments

It should return `Ok(None)` when tx is not found, but return `Err` when `OutPoint.vout` is invalid.

@afilini

6db5b4a Introduce `get_checksum_bytes` method and improvements (志宇) Pull request description: ### Description `get_checksum_bytes()` returns a descriptor checksum as `[u8; 8]` instead of `String`, potentially improving performance and memory usage. In addition to this, since descriptors only use characters that fit within a UTF-8 8-bit code unit ([US-ASCII](https://www.charset.org/charsets/us-ascii)), there is no need to use the `char` type (which is 4 bytes). This can also potentially bring in some performance and memory-usage benefits. ### Notes to the reviewers This is useful because we will be using descriptor checksums for indexing operations in the near future (multi-descriptor wallets #486 ). Refer to comments by @afilini : * #647 (comment) * #647 (comment) * #654 (comment) ### Checklists #### All Submissions: * [x] I've signed all my commits * [x] I followed the [contribution guidelines](https://github.com/bitcoindevkit/bdk/blob/master/CONTRIBUTING.md) * [x] I ran `cargo fmt` and `cargo clippy` before committing #### New Features: * [x] I've added tests for the new feature * [x] I've added docs for the new feature * [x] I've updated `CHANGELOG.md` ACKs for top commit: afilini: ACK 6db5b4a Tree-SHA512: 1cecc3a1514a3ec3ac0a50775f6b3c4dd9785e3606390ceba57cc6248b8ff19c4023add0643c48dd9d84984341c506c036c4880fca4a4358ce1b54ccb4c56687

2c02a44 Test: No address reuse for single descriptor (志宇) Pull request description: ### Description Just a simple new test. This test is to ensure there are no regressions when we later change internal logic of `Wallet`. A single descriptor wallet should always get a new address with `AddressIndex::New` even if we alternate grabbing internal/external keychains. I thought of adding this during work on #647 ### Checklists #### All Submissions: * [x] I've signed all my commits * [x] I followed the [contribution guidelines](https://github.com/bitcoindevkit/bdk/blob/master/CONTRIBUTING.md) * [x] I ran `cargo fmt` and `cargo clippy` before committing ACKs for top commit: danielabrozzoni: tACK 2c02a44 rajarshimaitra: tACK 2c02a44 Tree-SHA512: d065ae0979dc3ef7c26d6dfc19c88498e4bf17cc908e4f5677dcbf62ee59162e666cb00eb87b96d4c2557310960e3677eec7b6d907a5a4860cb7d2d74dba07b0

evanlinjin · 2023-01-13T10:09:27Z

This work will be replaced with BDK Core/Chain.

evanlinjin mentioned this pull request Jun 30, 2022

BDK Descriptor Improvements: Add multi descriptor capability in wallet bitcoindevkit/bdk_wallet#188

Open

evanlinjin force-pushed the tx-params-for-multi-descriptors branch 3 times, most recently from 5a0e85a to 14d2e99 Compare June 30, 2022 17:27

evanlinjin changed the title ~~Change TxParams for multi-descriptor capability~~ Add Multi-descriptor capability. Jul 1, 2022

evanlinjin changed the title ~~Add Multi-descriptor capability.~~ Add multi-descriptor capability Jul 1, 2022

notmandatory assigned evanlinjin Jul 4, 2022

notmandatory added the new feature New feature or request label Jul 4, 2022

evanlinjin force-pushed the tx-params-for-multi-descriptors branch from c27a900 to 5e3afe5 Compare July 5, 2022 17:07

evanlinjin changed the title ~~Add multi-descriptor capability~~ Multi descriptor: Root PR Jul 5, 2022

evanlinjin force-pushed the tx-params-for-multi-descriptors branch 2 times, most recently from ac2f4ed to 574dcc4 Compare July 9, 2022 05:23

evanlinjin changed the title ~~Multi descriptor: Root PR~~ Multi descriptor: decouple transaction building logic. Jul 9, 2022

evanlinjin changed the title ~~Multi descriptor: decouple transaction building logic.~~ Multi descriptor: Decouple transaction building logic Jul 9, 2022

evanlinjin mentioned this pull request Jul 9, 2022

Test: No address reuse for single descriptor #661

Merged

3 tasks

evanlinjin force-pushed the tx-params-for-multi-descriptors branch 11 times, most recently from 617c2b2 to 5aaf2bf Compare July 14, 2022 10:08

evanlinjin added 4 commits July 14, 2022 19:01

Change TxParams for multi-descriptor context

bc7994b

Store policy paths in a map with ExtendedDescriptor as key. This way we can re-use the TxParams struct in multi-descriptor/multi-wallet contexts.

Modify Error::SpendingPolicyRequired

ea622b4

Use `ExtendedDescriptor` instead of `Keychain`

.gitignore for vscode

82f3b95

WIP: Decouple TxBuilder from Wallet.

9df2586

This is a WIP. Explanation for my approach (will be / is) provided in the PR's description box.

evanlinjin added 4 commits July 14, 2022 19:03

WIP: Decoupled signing logic

7215623

WIP: Added TxBuilder::finish_and_sign

f1d2b9e

WIP: Decouple fee-bump logic

66931d2

WIP: Change SpendableCollection to use boxed Iterators

aac576d

evanlinjin force-pushed the tx-params-for-multi-descriptors branch 2 times, most recently from 4c6bf84 to ae9a331 Compare July 14, 2022 11:22

WIP: Rename SpendableCollection to MultiTracker and tweaks.

e3ca1ce

* Added `MultiTracker::latest_blockheight` method. * Update documentation to reflect changes.

evanlinjin force-pushed the tx-params-for-multi-descriptors branch from ae9a331 to e3ca1ce Compare July 14, 2022 12:19

WIP: Introduce LocalOutputItem

128eeb0

afilini reviewed Jul 15, 2022

View reviewed changes

evanlinjin mentioned this pull request Jul 16, 2022

Introduce get_checksum_bytes method and improvements #671

Merged

6 tasks

notmandatory mentioned this pull request Jul 16, 2022

W29 BDK Library Team Call bitcoindevkit/.github#14

Closed

22 tasks

evanlinjin added 6 commits July 17, 2022 08:00

WIP: Add header comments for multi_tracker.rs

930f3f1

WIP: Reduce iterations for MultiTracker:get_path_of_script_pubkey and…

ff7a93c

… comments

WIP: Fix MultiTracker::get_output logic

7649de6

It should return `Ok(None)` when tx is not found, but return `Err` when `OutPoint.vout` is invalid.

WIP: Fix MultiTracker::new_auto_address logic

400dbd1

WIP: Fix documentation in coin_selection.rs

2a302d2

WIP: Provide error message for coin_selection::test::tx

7432b07

DanGould mentioned this pull request Jul 30, 2022

BIP78: Allow mixed inputs and clarify a few things bitcoin/bips#1244

Closed

evanlinjin closed this Jan 13, 2023

	/// Obtains unspent UTXOs with satisfaction weights.
	/// This was called get_available_utxos in [`Wallet`].
	///
	/// TODO @evanlinjin:
	/// With the old implementation, we can call `get_descriptor_from_keychain` to obtain the
	/// parent descriptor without relying on a "cache" of relationships between `ScriptPubKey`s
	/// and "paths".
	/// However, we cannot continue to use this approach since we need to generalize everything
	/// to support multiple descriptors.
	/// A possible solution would be to replace usage of [`KeychainKind`] with
	/// `(KeychainKind, u32)`, so descriptors are referenced with an additional index.
	///
	/// For now, we need to ensure the aforementioned relationship is sufficiently cached to
	/// avoid "missing" available UTXOs.
	fn get_weighted_unspent_utxos(&self) -> Result<Vec<(LocalUtxo, usize)>, Error> {
	let out = self
	.get_unspent_utxos()?
	.iter()
	.filter_map(\|utxo\| {
	let (parent_desc, _) = self
	.get_path_of_script_pubkey(&utxo.txout.script_pubkey)
	// @evanlinjin: Will return here with `None` if not sufficiently cached.
	.unwrap()?;
	let weight = parent_desc.max_satisfaction_weight().unwrap();
	Some((utxo.clone(), weight))
	})
	.collect::<Vec<_>>();
	Ok(out)
	}

	// @evanlinjin: If you are wondering why this line is added, see comments in
	// [`SpendableCollection::get_weighted_unspent_utxos`].
	wallet
	.cache_addresses(KeychainKind::External, 0, 5)
	.unwrap();

Conversation

evanlinjin commented Jun 30, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Description

Notes to the reviewers

My Approach

Noteworthy changes

Tests

Next steps

Checklists

All Submissions:

New Features:

Bugfixes:

Uh oh!

afilini left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

evanlinjin commented Jan 13, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

evanlinjin commented Jun 30, 2022 •

edited

Loading