Replacing the Transaction Builder

# Replacing the Transaction Builder ## Motivation **Problem**:  1. The PSBT building functionality in `bdk_wallet` currently relies on the code in `descriptor/policy.rs`. The `policy` module is both unfinished and unmaintained. The updated implementation of this work now lives in `miniscript` library under the new `plan` module.  2. Similar to 1, transaction building now relies on `coin_selection.rs` which is also planned to be deprecated. The `bdk_coin_select` crate was recently rolled out to the BDK org but so far has seen little adoption. It offers updated coin selection logic, enhanced functionality, and greatly improved test coverage. BDK Wallet is poised to be a major user of this library which will in turn drive future developments in the space of coin selection. To take full advantage of the new functionality and pave the way for future success, we need to update the dependencies and rework the internals to provide a new transaction building interface. Failure to complete one or both of these steps can lead to worse outcomes for development and a degradation of user experience. The remainder of this document is dedicated to outlining the overarching design goals and the specific details that users and developers should know. Please note this is a living document and changes should be expected. ## Background and Previous Work - [`bdk_tx`](https://github.com/bitcoindevkit/bdk-tx) A modular transaction building library - [Miniscript `plan` API suggestions](https://hackmd.io/@valuedmammal/B1lxzomj0) (hackmd) - [Planning ahead](https://github.com/ValuedMammal/planning-ahead) (talk) ## Design and Implementation ### struct - `PsbtParams` - `ReplaceParams` ### enum - `SelectionStrategy` ### method - `Wallet::create_psbt` and no-std counterpart - `Wallet::replace_by_fee` and no-std counterpart. - Both of the above require `std` feature, as they depend on the system RNG. The no-std counterparts take an additional `rng: &mut impl RngCore` as parameter. - `Wallet::replace_by_fee_and_recipients` is a standalone function that is designed to take in the minimum information necessary to create a replacement (**1 or more txids to replace, a feerate, and a recipients vector**) - Various helpers which remain private and contain logic that is common to both `create_psbt` and `replace_by_fee` - `assets` - `parse_params` - `filter_spendable` - `target_outputs` - `create_psbt_from_selection` - `plan_input` - `try_plan` ### Other key changes - No more `policy_path` API. Specifying the spending path is now done via the `Assets` API through the use of `PsbtParams::add_assets`. The wallet will create a `Plan` for each eligible UTXO by combining the utxo-specific assets with the assets provided by the user. If the spending path is unambiguous or implied by virtue of the descriptor, then this feature is optional and no additional assets are needed. - `UtxoFilter` enables specifying a user-defined function which takes a `&FullTxOut` and decides whether it should be retained for the purpose of coin selection. `UtxoFilter` is versatile enough that it can be used to implement an "unspendable" list, or define a confirmation policy, etc. - `TxOrdering` is made generic, by exposing the generic type from `TxSort<T>`, so that it can apply a sorting function to two distinct slices `&mut [In]`, `&mut [Out]`. This was done in order to sort the items of the `Selection` before calling `Selection::create_psbt`. - The `CoinSelectionAlgorithm` trait is no longer used, and is instead replaced by a new `SelectionStrategy` enum. The library is responsible for implementing different coin selection strategies. We currently offer `SingleRandomDraw`, which selects coins at random, and `LowestFee`, which is based on a branch-and-bound algorithm. ## Rationale **Why `PsbtParams` instead of `TxBuilder`?** The current `TxBuilder` suffers from a large amount of technical debt as a result of the feature bloat that has occurred over time. This makes adding new features to `TxBuilder` increasingly difficult, especially considering that some of the original functionality is either obsolete or less generally useful. `TxBuilder` is primarily used by `Wallet::create_tx` which is a highly used code path that users depend on. We don't want to risk shipping new or immature features that could lead to subtle or surprising behavior changes. Instead we'll continue to support `TxBuilder` in the short term as far as bug fixes, and start encouraging users to try out the new APIs with plans to eventually deprecate `TxBuilder`. **What is the relationship between `PsbtParams` and `ReplaceParams`?** `ReplaceParams` is a simple wrapper around `PsbtParams`. It holds the params internally, along with its own separate data field(s), and exposes a separate interface. This was done to provide greater separation of concerns between normal PSBT building and creating replacements, while benefiting from much of the shared logic. For instance it would be a user error to add utxos to spend that are outputs of txs which are bound for replacement. `ReplaceParams` exists to make these kinds of invalid states impossible. An alternative could be to have some sort of `PsbtState` enum with different internal states that exposes a single interface and manages state transitions, e.g. from `PsbtState::Psbt` to `PsbtState::Replace`. The intuition is that once you are committed to doing an RBF, we shouldn't allow you to go back and meddle with the params (that might otherwise only apply to the PSBT state). ## Issues There's a known issue in BDK in which we fail to account for the fee and weight of unconfirmed ancestors when creating txs. This means that the feerate specified for the child tx may undershoot the package feerate calculated by the miner.