Let TxBuilder avoid previously used UTXOs (UTXO locking)

[tnull]

Describe the enhancement
When sequentially creating multiple transactions, TxBuilder might currently reuse the same UTXOs, potentially exposing us to double-spend ourselves if we want to bring all of these generated transactions on-chain. It would be nice if the TxBuilder could track the used UTXOs internally, and allow to auto-unlock them after a set amount of time.

Use case
This is important for sequentially opening multiple Lightning channels, e.g., in LDK Node.

[notmandatory]

We had some offline discussions about how to approach this issue, recapping here:

Step 1: create example of how to do it outside of bdk such as by manually keeping a set of used but not broadcast utxos, and then feeding that set to the TxBuilder to exclude the UTXOs when creating new transactions.

Step 2: based on experience with 1, create API changes for the Wallet (or TxBuilder?) that will make it possible to automatically manage the set of used but not broadcast UTXOs.

[LLFourn]

I think we want to support this in bdk_chain and bdk::Wallet explicitly. See cancel_tx in v1.0.0-alpha.0 PR:

bdk/src/wallet/mod.rs

Line 1385 in 7e8f849

pub fn cancel_tx(&mut self, tx: &Transaction) {

The idea is when a tx is cancelled in the future we can mark those utxos as no longer used and return them to the "utxo" pool.

See also the necessary feature in bdk_chain: LLFourn/bdk_core_staging#186

There are other cases where you want to reserve utxos that will have to be done via a different method (manual marking) which we can also provide.

[evanlinjin]

Currently, the proposed solution to this is (for BDK 1.0):

KeychainTracker should have mark_spent and unmark_spent that work in a similar way to mark_used and unmark_used in KeychainTxOutIndex. The reason we want this is to be able to "reserve" utxos so other threads cannot use them when we've decide to construct a transaction using them.

However, as we are replacing the KeychainTracker with IndexedTxGraph (as specified in #895), these methods should be added to IndexedTxGraph.

[LLFourn]

It's a little bit harder to say that IndexedTxGraph should have this method. Perhaps this should just exist in bdk::Wallet for now by storing a HashSet so you can reserve things.

[notmandatory]

See #913

[ValuedMammal]

Proposal for UTXO locking feature

approach: to be implemented in the wallet module

1. Add a coins map to the Wallet structure where the key is an OutPoint and the value is an optional expiration Height of the temporary freeze. This type can be extended in the future to include more complete information about a LocalOutput, or a general coin profile, etc.

pub struct Wallet {
    // map of outpoint to expiration height
    utxo_locks: HashMap<OutPoint, Option<Height>>,
    ...
}

2. Add methods on Wallet to load/reload coins and to lock a UTXO

/// Populates the the coins map. By default all utxos are unlocked.
pub fn reload_coins(&mut self) {
    // for utxo in self.unspent()
        // self.utxo_locks.insert(outpoint, None)
}

/// Locks the UTXO at `outpoint` for `n` number of blocks.
pub fn lock_utxo(&mut self, outpoint: OutPoint, n: blocks) { ... }

3. Filter locked UTXOs during get_available_utxos. The function should check if each UTXO is locked given the last known chain tip when getting the available coins for coin selection. A lock will automatically expire after syncing the wallet and advancing the local chain past the expiration height.

fn get_available_utxos(&self) -> Vec<(LocalOutput, Weight)> {
    self.list_unspent()
        .filter(|utxo| !self.is_utxo_locked(utxo.outpoint, self.latest_checkpoint().height()))
        .map(|utxo| { ... } )
        .collect()
}

[storopoli]

pub struct Wallet {
    // map of outpoint to expiration height
    utxo_locks: HashMap<OutPoint, Option<Height>>,
    ...
}

This should be a BTreeMap since we will generally be searching through it. It has $O( \log(n))$ complexity for the worst case scenario since it keeps the keys sorted.
Whereas HashMap needs to sort the keys first in any search, hence complexity $O(n \log (n))$

[notmandatory]

since this is a new feature and shouldn't break existing API I'm assigning it to the 1.1 milestone.

[tnull]

/// Populates the the coins map. By default all utxos are unlocked.

I want to note that it might be preferable to have the locking status persisted across restarts. Otherwise the user will need to keep track of the locked outpoints on top of Wallet once again. IMO, BDK should handle all of this and do the right thing (tm). I wonder if we'd also ever need an API method to explictly unlock a UTXO?

[notmandatory]

If the API in #1669 is acceptable then I think we should add this functionality at the Wallet layer and plumb it through to the chain layer only if/when needed.