]> git.bitcoin.ninja Git - rust-lightning/blob - lightning/src/events/bump_transaction.rs
Merge pull request #2439 from tnull/2023-05-fix-0conf-sigs-racing-confirms
[rust-lightning] / lightning / src / events / bump_transaction.rs
1 // This file is Copyright its original authors, visible in version control
2 // history.
3 //
4 // This file is licensed under the Apache License, Version 2.0 <LICENSE-APACHE
5 // or http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
6 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your option.
7 // You may not use this file except in accordance with one or both of these
8 // licenses.
9
10 //! Utilities for bumping transactions originating from [`Event`]s.
11 //!
12 //! [`Event`]: crate::events::Event
13
14 use alloc::collections::BTreeMap;
15 use core::ops::Deref;
16
17 use crate::chain::chaininterface::{BroadcasterInterface, compute_feerate_sat_per_1000_weight, fee_for_weight, FEERATE_FLOOR_SATS_PER_KW};
18 use crate::chain::ClaimId;
19 use crate::io_extras::sink;
20 use crate::ln::channel::ANCHOR_OUTPUT_VALUE_SATOSHI;
21 use crate::ln::chan_utils;
22 use crate::ln::chan_utils::{
23         ANCHOR_INPUT_WITNESS_WEIGHT, HTLC_SUCCESS_INPUT_ANCHOR_WITNESS_WEIGHT,
24         HTLC_TIMEOUT_INPUT_ANCHOR_WITNESS_WEIGHT, ChannelTransactionParameters, HTLCOutputInCommitment
25 };
26 use crate::ln::features::ChannelTypeFeatures;
27 use crate::ln::PaymentPreimage;
28 use crate::prelude::*;
29 use crate::sign::{ChannelSigner, EcdsaChannelSigner, SignerProvider, WriteableEcdsaChannelSigner};
30 use crate::sync::Mutex;
31 use crate::util::logger::Logger;
32
33 use bitcoin::{OutPoint, PackedLockTime, PubkeyHash, Sequence, Script, Transaction, Txid, TxIn, TxOut, Witness, WPubkeyHash};
34 use bitcoin::blockdata::constants::WITNESS_SCALE_FACTOR;
35 use bitcoin::consensus::Encodable;
36 use bitcoin::secp256k1;
37 use bitcoin::secp256k1::{PublicKey, Secp256k1};
38 use bitcoin::secp256k1::ecdsa::Signature;
39
40 const EMPTY_SCRIPT_SIG_WEIGHT: u64 = 1 /* empty script_sig */ * WITNESS_SCALE_FACTOR as u64;
41
42 const BASE_INPUT_SIZE: u64 = 32 /* txid */ + 4 /* vout */ + 4 /* sequence */;
43
44 const BASE_INPUT_WEIGHT: u64 = BASE_INPUT_SIZE * WITNESS_SCALE_FACTOR as u64;
45
46 /// The parameters required to derive a channel signer via [`SignerProvider`].
47 #[derive(Clone, Debug, PartialEq, Eq)]
48 pub struct ChannelDerivationParameters {
49         /// The value in satoshis of the channel we're attempting to spend the anchor output of.
50         pub value_satoshis: u64,
51         /// The unique identifier to re-derive the signer for the associated channel.
52         pub keys_id: [u8; 32],
53         /// The necessary channel parameters that need to be provided to the re-derived signer through
54         /// [`ChannelSigner::provide_channel_parameters`].
55         ///
56         /// [`ChannelSigner::provide_channel_parameters`]: crate::sign::ChannelSigner::provide_channel_parameters
57         pub transaction_parameters: ChannelTransactionParameters,
58 }
59
60 /// A descriptor used to sign for a commitment transaction's anchor output.
61 #[derive(Clone, Debug, PartialEq, Eq)]
62 pub struct AnchorDescriptor {
63         /// The parameters required to derive the signer for the anchor input.
64         pub channel_derivation_parameters: ChannelDerivationParameters,
65         /// The transaction input's outpoint corresponding to the commitment transaction's anchor
66         /// output.
67         pub outpoint: OutPoint,
68 }
69
70 impl AnchorDescriptor {
71         /// Returns the UTXO to be spent by the anchor input, which can be obtained via
72         /// [`Self::unsigned_tx_input`].
73         pub fn previous_utxo(&self) -> TxOut {
74                 TxOut {
75                         script_pubkey: self.witness_script().to_v0_p2wsh(),
76                         value: ANCHOR_OUTPUT_VALUE_SATOSHI,
77                 }
78         }
79
80         /// Returns the unsigned transaction input spending the anchor output in the commitment
81         /// transaction.
82         pub fn unsigned_tx_input(&self) -> TxIn {
83                 TxIn {
84                         previous_output: self.outpoint.clone(),
85                         script_sig: Script::new(),
86                         sequence: Sequence::ENABLE_RBF_NO_LOCKTIME,
87                         witness: Witness::new(),
88                 }
89         }
90
91         /// Returns the witness script of the anchor output in the commitment transaction.
92         pub fn witness_script(&self) -> Script {
93                 let channel_params = self.channel_derivation_parameters.transaction_parameters.as_holder_broadcastable();
94                 chan_utils::get_anchor_redeemscript(&channel_params.broadcaster_pubkeys().funding_pubkey)
95         }
96
97         /// Returns the fully signed witness required to spend the anchor output in the commitment
98         /// transaction.
99         pub fn tx_input_witness(&self, signature: &Signature) -> Witness {
100                 let channel_params = self.channel_derivation_parameters.transaction_parameters.as_holder_broadcastable();
101                 chan_utils::build_anchor_input_witness(&channel_params.broadcaster_pubkeys().funding_pubkey, signature)
102         }
103
104         /// Derives the channel signer required to sign the anchor input.
105         pub fn derive_channel_signer<S: WriteableEcdsaChannelSigner, SP: Deref>(&self, signer_provider: &SP) -> S
106         where
107                 SP::Target: SignerProvider<Signer = S>
108         {
109                 let mut signer = signer_provider.derive_channel_signer(
110                         self.channel_derivation_parameters.value_satoshis,
111                         self.channel_derivation_parameters.keys_id,
112                 );
113                 signer.provide_channel_parameters(&self.channel_derivation_parameters.transaction_parameters);
114                 signer
115         }
116 }
117
118 /// A descriptor used to sign for a commitment transaction's HTLC output.
119 #[derive(Clone, Debug, PartialEq, Eq)]
120 pub struct HTLCDescriptor {
121         /// The parameters required to derive the signer for the HTLC input.
122         pub channel_derivation_parameters: ChannelDerivationParameters,
123         /// The txid of the commitment transaction in which the HTLC output lives.
124         pub commitment_txid: Txid,
125         /// The number of the commitment transaction in which the HTLC output lives.
126         pub per_commitment_number: u64,
127         /// The key tweak corresponding to the number of the commitment transaction in which the HTLC
128         /// output lives. This tweak is applied to all the basepoints for both parties in the channel to
129         /// arrive at unique keys per commitment.
130         ///
131         /// See <https://github.com/lightning/bolts/blob/master/03-transactions.md#keys> for more info.
132         pub per_commitment_point: PublicKey,
133         /// The details of the HTLC as it appears in the commitment transaction.
134         pub htlc: HTLCOutputInCommitment,
135         /// The preimage, if `Some`, to claim the HTLC output with. If `None`, the timeout path must be
136         /// taken.
137         pub preimage: Option<PaymentPreimage>,
138         /// The counterparty's signature required to spend the HTLC output.
139         pub counterparty_sig: Signature
140 }
141
142 impl HTLCDescriptor {
143         /// Returns the outpoint of the HTLC output in the commitment transaction. This is the outpoint
144         /// being spent by the HTLC input in the HTLC transaction.
145         pub fn outpoint(&self) -> OutPoint {
146                 OutPoint {
147                         txid: self.commitment_txid,
148                         vout: self.htlc.transaction_output_index.unwrap(),
149                 }
150         }
151
152         /// Returns the UTXO to be spent by the HTLC input, which can be obtained via
153         /// [`Self::unsigned_tx_input`].
154         pub fn previous_utxo<C: secp256k1::Signing + secp256k1::Verification>(&self, secp: &Secp256k1<C>) -> TxOut {
155                 TxOut {
156                         script_pubkey: self.witness_script(secp).to_v0_p2wsh(),
157                         value: self.htlc.amount_msat / 1000,
158                 }
159         }
160
161         /// Returns the unsigned transaction input spending the HTLC output in the commitment
162         /// transaction.
163         pub fn unsigned_tx_input(&self) -> TxIn {
164                 chan_utils::build_htlc_input(&self.commitment_txid, &self.htlc, &ChannelTypeFeatures::anchors_zero_htlc_fee_and_dependencies())
165         }
166
167         /// Returns the delayed output created as a result of spending the HTLC output in the commitment
168         /// transaction.
169         pub fn tx_output<C: secp256k1::Signing + secp256k1::Verification>(&self, secp: &Secp256k1<C>) -> TxOut {
170                 let channel_params = self.channel_derivation_parameters.transaction_parameters.as_holder_broadcastable();
171                 let broadcaster_keys = channel_params.broadcaster_pubkeys();
172                 let counterparty_keys = channel_params.countersignatory_pubkeys();
173                 let broadcaster_delayed_key = chan_utils::derive_public_key(
174                         secp, &self.per_commitment_point, &broadcaster_keys.delayed_payment_basepoint
175                 );
176                 let counterparty_revocation_key = chan_utils::derive_public_revocation_key(
177                         secp, &self.per_commitment_point, &counterparty_keys.revocation_basepoint
178                 );
179                 chan_utils::build_htlc_output(
180                         0 /* feerate_per_kw */, channel_params.contest_delay(), &self.htlc,
181                         &ChannelTypeFeatures::anchors_zero_htlc_fee_and_dependencies(), &broadcaster_delayed_key, &counterparty_revocation_key
182                 )
183         }
184
185         /// Returns the witness script of the HTLC output in the commitment transaction.
186         pub fn witness_script<C: secp256k1::Signing + secp256k1::Verification>(&self, secp: &Secp256k1<C>) -> Script {
187                 let channel_params = self.channel_derivation_parameters.transaction_parameters.as_holder_broadcastable();
188                 let broadcaster_keys = channel_params.broadcaster_pubkeys();
189                 let counterparty_keys = channel_params.countersignatory_pubkeys();
190                 let broadcaster_htlc_key = chan_utils::derive_public_key(
191                         secp, &self.per_commitment_point, &broadcaster_keys.htlc_basepoint
192                 );
193                 let counterparty_htlc_key = chan_utils::derive_public_key(
194                         secp, &self.per_commitment_point, &counterparty_keys.htlc_basepoint
195                 );
196                 let counterparty_revocation_key = chan_utils::derive_public_revocation_key(
197                         secp, &self.per_commitment_point, &counterparty_keys.revocation_basepoint
198                 );
199                 chan_utils::get_htlc_redeemscript_with_explicit_keys(
200                         &self.htlc, &ChannelTypeFeatures::anchors_zero_htlc_fee_and_dependencies(), &broadcaster_htlc_key, &counterparty_htlc_key,
201                         &counterparty_revocation_key,
202                 )
203         }
204
205         /// Returns the fully signed witness required to spend the HTLC output in the commitment
206         /// transaction.
207         pub fn tx_input_witness(&self, signature: &Signature, witness_script: &Script) -> Witness {
208                 chan_utils::build_htlc_input_witness(
209                         signature, &self.counterparty_sig, &self.preimage, witness_script, &ChannelTypeFeatures::anchors_zero_htlc_fee_and_dependencies() /* opt_anchors */
210                 )
211         }
212
213         /// Derives the channel signer required to sign the HTLC input.
214         pub fn derive_channel_signer<S: WriteableEcdsaChannelSigner, SP: Deref>(&self, signer_provider: &SP) -> S
215         where
216                 SP::Target: SignerProvider<Signer = S>
217         {
218                 let mut signer = signer_provider.derive_channel_signer(
219                         self.channel_derivation_parameters.value_satoshis,
220                         self.channel_derivation_parameters.keys_id,
221                 );
222                 signer.provide_channel_parameters(&self.channel_derivation_parameters.transaction_parameters);
223                 signer
224         }
225 }
226
227 /// Represents the different types of transactions, originating from LDK, to be bumped.
228 #[derive(Clone, Debug, PartialEq, Eq)]
229 pub enum BumpTransactionEvent {
230         /// Indicates that a channel featuring anchor outputs is to be closed by broadcasting the local
231         /// commitment transaction. Since commitment transactions have a static feerate pre-agreed upon,
232         /// they may need additional fees to be attached through a child transaction using the popular
233         /// [Child-Pays-For-Parent](https://bitcoinops.org/en/topics/cpfp) fee bumping technique. This
234         /// child transaction must include the anchor input described within `anchor_descriptor` along
235         /// with additional inputs to meet the target feerate. Failure to meet the target feerate
236         /// decreases the confirmation odds of the transaction package (which includes the commitment
237         /// and child anchor transactions), possibly resulting in a loss of funds. Once the transaction
238         /// is constructed, it must be fully signed for and broadcast by the consumer of the event
239         /// along with the `commitment_tx` enclosed. Note that the `commitment_tx` must always be
240         /// broadcast first, as the child anchor transaction depends on it.
241         ///
242         /// The consumer should be able to sign for any of the additional inputs included within the
243         /// child anchor transaction. To sign its anchor input, an [`EcdsaChannelSigner`] should be
244         /// re-derived through [`AnchorDescriptor::derive_channel_signer`]. The anchor input signature
245         /// can be computed with [`EcdsaChannelSigner::sign_holder_anchor_input`], which can then be
246         /// provided to [`build_anchor_input_witness`] along with the `funding_pubkey` to obtain the
247         /// full witness required to spend.
248         ///
249         /// It is possible to receive more than one instance of this event if a valid child anchor
250         /// transaction is never broadcast or is but not with a sufficient fee to be mined. Care should
251         /// be taken by the consumer of the event to ensure any future iterations of the child anchor
252         /// transaction adhere to the [Replace-By-Fee
253         /// rules](https://github.com/bitcoin/bitcoin/blob/master/doc/policy/mempool-replacements.md)
254         /// for fee bumps to be accepted into the mempool, and eventually the chain. As the frequency of
255         /// these events is not user-controlled, users may ignore/drop the event if they are no longer
256         /// able to commit external confirmed funds to the child anchor transaction.
257         ///
258         /// The set of `pending_htlcs` on the commitment transaction to be broadcast can be inspected to
259         /// determine whether a significant portion of the channel's funds are allocated to HTLCs,
260         /// enabling users to make their own decisions regarding the importance of the commitment
261         /// transaction's confirmation. Note that this is not required, but simply exists as an option
262         /// for users to override LDK's behavior. On commitments with no HTLCs (indicated by those with
263         /// an empty `pending_htlcs`), confirmation of the commitment transaction can be considered to
264         /// be not urgent.
265         ///
266         /// [`EcdsaChannelSigner`]: crate::sign::EcdsaChannelSigner
267         /// [`EcdsaChannelSigner::sign_holder_anchor_input`]: crate::sign::EcdsaChannelSigner::sign_holder_anchor_input
268         /// [`build_anchor_input_witness`]: crate::ln::chan_utils::build_anchor_input_witness
269         ChannelClose {
270                 /// The unique identifier for the claim of the anchor output in the commitment transaction.
271                 ///
272                 /// The identifier must map to the set of external UTXOs assigned to the claim, such that
273                 /// they can be reused when a new claim with the same identifier needs to be made, resulting
274                 /// in a fee-bumping attempt.
275                 claim_id: ClaimId,
276                 /// The target feerate that the transaction package, which consists of the commitment
277                 /// transaction and the to-be-crafted child anchor transaction, must meet.
278                 package_target_feerate_sat_per_1000_weight: u32,
279                 /// The channel's commitment transaction to bump the fee of. This transaction should be
280                 /// broadcast along with the anchor transaction constructed as a result of consuming this
281                 /// event.
282                 commitment_tx: Transaction,
283                 /// The absolute fee in satoshis of the commitment transaction. This can be used along the
284                 /// with weight of the commitment transaction to determine its feerate.
285                 commitment_tx_fee_satoshis: u64,
286                 /// The descriptor to sign the anchor input of the anchor transaction constructed as a
287                 /// result of consuming this event.
288                 anchor_descriptor: AnchorDescriptor,
289                 /// The set of pending HTLCs on the commitment transaction that need to be resolved once the
290                 /// commitment transaction confirms.
291                 pending_htlcs: Vec<HTLCOutputInCommitment>,
292         },
293         /// Indicates that a channel featuring anchor outputs has unilaterally closed on-chain by a
294         /// holder commitment transaction and its HTLC(s) need to be resolved on-chain. With the
295         /// zero-HTLC-transaction-fee variant of anchor outputs, the pre-signed HTLC
296         /// transactions have a zero fee, thus requiring additional inputs and/or outputs to be attached
297         /// for a timely confirmation within the chain. These additional inputs and/or outputs must be
298         /// appended to the resulting HTLC transaction to meet the target feerate. Failure to meet the
299         /// target feerate decreases the confirmation odds of the transaction, possibly resulting in a
300         /// loss of funds. Once the transaction meets the target feerate, it must be signed for and
301         /// broadcast by the consumer of the event.
302         ///
303         /// The consumer should be able to sign for any of the non-HTLC inputs added to the resulting
304         /// HTLC transaction. To sign HTLC inputs, an [`EcdsaChannelSigner`] should be re-derived
305         /// through [`HTLCDescriptor::derive_channel_signer`]. Each HTLC input's signature can be
306         /// computed with [`EcdsaChannelSigner::sign_holder_htlc_transaction`], which can then be
307         /// provided to [`HTLCDescriptor::tx_input_witness`] to obtain the fully signed witness required
308         /// to spend.
309         ///
310         /// It is possible to receive more than one instance of this event if a valid HTLC transaction
311         /// is never broadcast or is but not with a sufficient fee to be mined. Care should be taken by
312         /// the consumer of the event to ensure any future iterations of the HTLC transaction adhere to
313         /// the [Replace-By-Fee
314         /// rules](https://github.com/bitcoin/bitcoin/blob/master/doc/policy/mempool-replacements.md)
315         /// for fee bumps to be accepted into the mempool, and eventually the chain. As the frequency of
316         /// these events is not user-controlled, users may ignore/drop the event if either they are no
317         /// longer able to commit external confirmed funds to the HTLC transaction or the fee committed
318         /// to the HTLC transaction is greater in value than the HTLCs being claimed.
319         ///
320         /// [`EcdsaChannelSigner`]: crate::sign::EcdsaChannelSigner
321         /// [`EcdsaChannelSigner::sign_holder_htlc_transaction`]: crate::sign::EcdsaChannelSigner::sign_holder_htlc_transaction
322         /// [`HTLCDescriptor::tx_input_witness`]: HTLCDescriptor::tx_input_witness
323         HTLCResolution {
324                 /// The unique identifier for the claim of the HTLCs in the confirmed commitment
325                 /// transaction.
326                 ///
327                 /// The identifier must map to the set of external UTXOs assigned to the claim, such that
328                 /// they can be reused when a new claim with the same identifier needs to be made, resulting
329                 /// in a fee-bumping attempt.
330                 claim_id: ClaimId,
331                 /// The target feerate that the resulting HTLC transaction must meet.
332                 target_feerate_sat_per_1000_weight: u32,
333                 /// The set of pending HTLCs on the confirmed commitment that need to be claimed, preferably
334                 /// by the same transaction.
335                 htlc_descriptors: Vec<HTLCDescriptor>,
336                 /// The locktime required for the resulting HTLC transaction.
337                 tx_lock_time: PackedLockTime,
338         },
339 }
340
341 /// An input that must be included in a transaction when performing coin selection through
342 /// [`CoinSelectionSource::select_confirmed_utxos`]. It is guaranteed to be a SegWit input, so it
343 /// must have an empty [`TxIn::script_sig`] when spent.
344 #[derive(Clone, Debug, Hash, PartialOrd, Ord, PartialEq, Eq)]
345 pub struct Input {
346         /// The unique identifier of the input.
347         pub outpoint: OutPoint,
348         /// The UTXO being spent by the input.
349         pub previous_utxo: TxOut,
350         /// The upper-bound weight consumed by the input's full [`TxIn::script_sig`] and
351         /// [`TxIn::witness`], each with their lengths included, required to satisfy the output's
352         /// script.
353         pub satisfaction_weight: u64,
354 }
355
356 /// An unspent transaction output that is available to spend resulting from a successful
357 /// [`CoinSelection`] attempt.
358 #[derive(Clone, Debug, Hash, PartialOrd, Ord, PartialEq, Eq)]
359 pub struct Utxo {
360         /// The unique identifier of the output.
361         pub outpoint: OutPoint,
362         /// The output to spend.
363         pub output: TxOut,
364         /// The upper-bound weight consumed by the input's full [`TxIn::script_sig`] and [`TxIn::witness`], each
365         /// with their lengths included, required to satisfy the output's script. The weight consumed by
366         /// the input's `script_sig` must account for [`WITNESS_SCALE_FACTOR`].
367         pub satisfaction_weight: u64,
368 }
369
370 impl Utxo {
371         const P2WPKH_WITNESS_WEIGHT: u64 = 1 /* num stack items */ +
372                 1 /* sig length */ +
373                 73 /* sig including sighash flag */ +
374                 1 /* pubkey length */ +
375                 33 /* pubkey */;
376
377         /// Returns a `Utxo` with the `satisfaction_weight` estimate for a legacy P2PKH output.
378         pub fn new_p2pkh(outpoint: OutPoint, value: u64, pubkey_hash: &PubkeyHash) -> Self {
379                 let script_sig_size = 1 /* script_sig length */ +
380                         1 /* OP_PUSH73 */ +
381                         73 /* sig including sighash flag */ +
382                         1 /* OP_PUSH33 */ +
383                         33 /* pubkey */;
384                 Self {
385                         outpoint,
386                         output: TxOut {
387                                 value,
388                                 script_pubkey: Script::new_p2pkh(pubkey_hash),
389                         },
390                         satisfaction_weight: script_sig_size * WITNESS_SCALE_FACTOR as u64 + 1 /* empty witness */,
391                 }
392         }
393
394         /// Returns a `Utxo` with the `satisfaction_weight` estimate for a P2WPKH nested in P2SH output.
395         pub fn new_nested_p2wpkh(outpoint: OutPoint, value: u64, pubkey_hash: &WPubkeyHash) -> Self {
396                 let script_sig_size = 1 /* script_sig length */ +
397                         1 /* OP_0 */ +
398                         1 /* OP_PUSH20 */ +
399                         20 /* pubkey_hash */;
400                 Self {
401                         outpoint,
402                         output: TxOut {
403                                 value,
404                                 script_pubkey: Script::new_p2sh(&Script::new_v0_p2wpkh(pubkey_hash).script_hash()),
405                         },
406                         satisfaction_weight: script_sig_size * WITNESS_SCALE_FACTOR as u64 + Self::P2WPKH_WITNESS_WEIGHT,
407                 }
408         }
409
410         /// Returns a `Utxo` with the `satisfaction_weight` estimate for a SegWit v0 P2WPKH output.
411         pub fn new_v0_p2wpkh(outpoint: OutPoint, value: u64, pubkey_hash: &WPubkeyHash) -> Self {
412                 Self {
413                         outpoint,
414                         output: TxOut {
415                                 value,
416                                 script_pubkey: Script::new_v0_p2wpkh(pubkey_hash),
417                         },
418                         satisfaction_weight: EMPTY_SCRIPT_SIG_WEIGHT + Self::P2WPKH_WITNESS_WEIGHT,
419                 }
420         }
421 }
422
423 /// The result of a successful coin selection attempt for a transaction requiring additional UTXOs
424 /// to cover its fees.
425 #[derive(Clone, Debug)]
426 pub struct CoinSelection {
427         /// The set of UTXOs (with at least 1 confirmation) to spend and use within a transaction
428         /// requiring additional fees.
429         pub confirmed_utxos: Vec<Utxo>,
430         /// An additional output tracking whether any change remained after coin selection. This output
431         /// should always have a value above dust for its given `script_pubkey`. It should not be
432         /// spent until the transaction it belongs to confirms to ensure mempool descendant limits are
433         /// not met. This implies no other party should be able to spend it except us.
434         pub change_output: Option<TxOut>,
435 }
436
437 /// An abstraction over a bitcoin wallet that can perform coin selection over a set of UTXOs and can
438 /// sign for them. The coin selection method aims to mimic Bitcoin Core's `fundrawtransaction` RPC,
439 /// which most wallets should be able to satisfy. Otherwise, consider implementing [`WalletSource`],
440 /// which can provide a default implementation of this trait when used with [`Wallet`].
441 pub trait CoinSelectionSource {
442         /// Performs coin selection of a set of UTXOs, with at least 1 confirmation each, that are
443         /// available to spend. Implementations are free to pick their coin selection algorithm of
444         /// choice, as long as the following requirements are met:
445         ///
446         /// 1. `must_spend` contains a set of [`Input`]s that must be included in the transaction
447         ///    throughout coin selection, but must not be returned as part of the result.
448         /// 2. `must_pay_to` contains a set of [`TxOut`]s that must be included in the transaction
449         ///    throughout coin selection. In some cases, like when funding an anchor transaction, this
450         ///    set is empty. Implementations should ensure they handle this correctly on their end,
451         ///    e.g., Bitcoin Core's `fundrawtransaction` RPC requires at least one output to be
452         ///    provided, in which case a zero-value empty OP_RETURN output can be used instead.
453         /// 3. Enough inputs must be selected/contributed for the resulting transaction (including the
454         ///    inputs and outputs noted above) to meet `target_feerate_sat_per_1000_weight`.
455         ///
456         /// Implementations must take note that [`Input::satisfaction_weight`] only tracks the weight of
457         /// the input's `script_sig` and `witness`. Some wallets, like Bitcoin Core's, may require
458         /// providing the full input weight. Failing to do so may lead to underestimating fee bumps and
459         /// delaying block inclusion.
460         ///
461         /// The `claim_id` must map to the set of external UTXOs assigned to the claim, such that they
462         /// can be re-used within new fee-bumped iterations of the original claiming transaction,
463         /// ensuring that claims don't double spend each other. If a specific `claim_id` has never had a
464         /// transaction associated with it, and all of the available UTXOs have already been assigned to
465         /// other claims, implementations must be willing to double spend their UTXOs. The choice of
466         /// which UTXOs to double spend is left to the implementation, but it must strive to keep the
467         /// set of other claims being double spent to a minimum.
468         fn select_confirmed_utxos(
469                 &self, claim_id: ClaimId, must_spend: Vec<Input>, must_pay_to: &[TxOut],
470                 target_feerate_sat_per_1000_weight: u32,
471         ) -> Result<CoinSelection, ()>;
472         /// Signs and provides the full witness for all inputs within the transaction known to the
473         /// trait (i.e., any provided via [`CoinSelectionSource::select_confirmed_utxos`]).
474         fn sign_tx(&self, tx: Transaction) -> Result<Transaction, ()>;
475 }
476
477 /// An alternative to [`CoinSelectionSource`] that can be implemented and used along [`Wallet`] to
478 /// provide a default implementation to [`CoinSelectionSource`].
479 pub trait WalletSource {
480         /// Returns all UTXOs, with at least 1 confirmation each, that are available to spend.
481         fn list_confirmed_utxos(&self) -> Result<Vec<Utxo>, ()>;
482         /// Returns a script to use for change above dust resulting from a successful coin selection
483         /// attempt.
484         fn get_change_script(&self) -> Result<Script, ()>;
485         /// Signs and provides the full [`TxIn::script_sig`] and [`TxIn::witness`] for all inputs within
486         /// the transaction known to the wallet (i.e., any provided via
487         /// [`WalletSource::list_confirmed_utxos`]).
488         fn sign_tx(&self, tx: Transaction) -> Result<Transaction, ()>;
489 }
490
491 /// A wrapper over [`WalletSource`] that implements [`CoinSelection`] by preferring UTXOs that would
492 /// avoid conflicting double spends. If not enough UTXOs are available to do so, conflicting double
493 /// spends may happen.
494 pub struct Wallet<W: Deref, L: Deref>
495 where
496         W::Target: WalletSource,
497         L::Target: Logger
498 {
499         source: W,
500         logger: L,
501         // TODO: Do we care about cleaning this up once the UTXOs have a confirmed spend? We can do so
502         // by checking whether any UTXOs that exist in the map are no longer returned in
503         // `list_confirmed_utxos`.
504         locked_utxos: Mutex<HashMap<OutPoint, ClaimId>>,
505 }
506
507 impl<W: Deref, L: Deref> Wallet<W, L>
508 where
509         W::Target: WalletSource,
510         L::Target: Logger
511 {
512         /// Returns a new instance backed by the given [`WalletSource`] that serves as an implementation
513         /// of [`CoinSelectionSource`].
514         pub fn new(source: W, logger: L) -> Self {
515                 Self { source, logger, locked_utxos: Mutex::new(HashMap::new()) }
516         }
517
518         /// Performs coin selection on the set of UTXOs obtained from
519         /// [`WalletSource::list_confirmed_utxos`]. Its algorithm can be described as "smallest
520         /// above-dust-after-spend first", with a slight twist: we may skip UTXOs that are above dust at
521         /// the target feerate after having spent them in a separate claim transaction if
522         /// `force_conflicting_utxo_spend` is unset to avoid producing conflicting transactions. If
523         /// `tolerate_high_network_feerates` is set, we'll attempt to spend UTXOs that contribute at
524         /// least 1 satoshi at the current feerate, otherwise, we'll only attempt to spend those which
525         /// contribute at least twice their fee.
526         fn select_confirmed_utxos_internal(
527                 &self, utxos: &[Utxo], claim_id: ClaimId, force_conflicting_utxo_spend: bool,
528                 tolerate_high_network_feerates: bool, target_feerate_sat_per_1000_weight: u32,
529                 preexisting_tx_weight: u64, target_amount_sat: u64,
530         ) -> Result<CoinSelection, ()> {
531                 let mut locked_utxos = self.locked_utxos.lock().unwrap();
532                 let mut eligible_utxos = utxos.iter().filter_map(|utxo| {
533                         if let Some(utxo_claim_id) = locked_utxos.get(&utxo.outpoint) {
534                                 if *utxo_claim_id != claim_id && !force_conflicting_utxo_spend {
535                                         log_trace!(self.logger, "Skipping UTXO {} to prevent conflicting spend", utxo.outpoint);
536                                         return None;
537                                 }
538                         }
539                         let fee_to_spend_utxo = fee_for_weight(
540                                 target_feerate_sat_per_1000_weight, BASE_INPUT_WEIGHT as u64 + utxo.satisfaction_weight,
541                         );
542                         let should_spend = if tolerate_high_network_feerates {
543                                 utxo.output.value > fee_to_spend_utxo
544                         } else {
545                                 utxo.output.value >= fee_to_spend_utxo * 2
546                         };
547                         if should_spend {
548                                 Some((utxo, fee_to_spend_utxo))
549                         } else {
550                                 log_trace!(self.logger, "Skipping UTXO {} due to dust proximity after spend", utxo.outpoint);
551                                 None
552                         }
553                 }).collect::<Vec<_>>();
554                 eligible_utxos.sort_unstable_by_key(|(utxo, _)| utxo.output.value);
555
556                 let mut selected_amount = 0;
557                 let mut total_fees = fee_for_weight(target_feerate_sat_per_1000_weight, preexisting_tx_weight);
558                 let mut selected_utxos = Vec::new();
559                 for (utxo, fee_to_spend_utxo) in eligible_utxos {
560                         if selected_amount >= target_amount_sat + total_fees {
561                                 break;
562                         }
563                         selected_amount += utxo.output.value;
564                         total_fees += fee_to_spend_utxo;
565                         selected_utxos.push(utxo.clone());
566                 }
567                 if selected_amount < target_amount_sat + total_fees {
568                         log_debug!(self.logger, "Insufficient funds to meet target feerate {} sat/kW",
569                                 target_feerate_sat_per_1000_weight);
570                         return Err(());
571                 }
572                 for utxo in &selected_utxos {
573                         locked_utxos.insert(utxo.outpoint, claim_id);
574                 }
575                 core::mem::drop(locked_utxos);
576
577                 let remaining_amount = selected_amount - target_amount_sat - total_fees;
578                 let change_script = self.source.get_change_script()?;
579                 let change_output_fee = fee_for_weight(
580                         target_feerate_sat_per_1000_weight,
581                         (8 /* value */ + change_script.consensus_encode(&mut sink()).unwrap() as u64) *
582                                 WITNESS_SCALE_FACTOR as u64,
583                 );
584                 let change_output_amount = remaining_amount.saturating_sub(change_output_fee);
585                 let change_output = if change_output_amount < change_script.dust_value().to_sat() {
586                         log_debug!(self.logger, "Coin selection attempt did not yield change output");
587                         None
588                 } else {
589                         Some(TxOut { script_pubkey: change_script, value: change_output_amount })
590                 };
591
592                 Ok(CoinSelection {
593                         confirmed_utxos: selected_utxos,
594                         change_output,
595                 })
596         }
597 }
598
599 impl<W: Deref, L: Deref> CoinSelectionSource for Wallet<W, L>
600 where
601         W::Target: WalletSource,
602         L::Target: Logger
603 {
604         fn select_confirmed_utxos(
605                 &self, claim_id: ClaimId, must_spend: Vec<Input>, must_pay_to: &[TxOut],
606                 target_feerate_sat_per_1000_weight: u32,
607         ) -> Result<CoinSelection, ()> {
608                 let utxos = self.source.list_confirmed_utxos()?;
609                 // TODO: Use fee estimation utils when we upgrade to bitcoin v0.30.0.
610                 const BASE_TX_SIZE: u64 = 4 /* version */ + 1 /* input count */ + 1 /* output count */ + 4 /* locktime */;
611                 let total_output_size: u64 = must_pay_to.iter().map(|output|
612                         8 /* value */ + 1 /* script len */ + output.script_pubkey.len() as u64
613                 ).sum();
614                 let total_satisfaction_weight: u64 = must_spend.iter().map(|input| input.satisfaction_weight).sum();
615                 let total_input_weight = (BASE_INPUT_WEIGHT * must_spend.len() as u64) + total_satisfaction_weight;
616
617                 let preexisting_tx_weight = 2 /* segwit marker & flag */ + total_input_weight +
618                         ((BASE_TX_SIZE + total_output_size) * WITNESS_SCALE_FACTOR as u64);
619                 let target_amount_sat = must_pay_to.iter().map(|output| output.value).sum();
620                 let do_coin_selection = |force_conflicting_utxo_spend: bool, tolerate_high_network_feerates: bool| {
621                         log_debug!(self.logger, "Attempting coin selection targeting {} sat/kW (force_conflicting_utxo_spend = {}, tolerate_high_network_feerates = {})",
622                                 target_feerate_sat_per_1000_weight, force_conflicting_utxo_spend, tolerate_high_network_feerates);
623                         self.select_confirmed_utxos_internal(
624                                 &utxos, claim_id, force_conflicting_utxo_spend, tolerate_high_network_feerates,
625                                 target_feerate_sat_per_1000_weight, preexisting_tx_weight, target_amount_sat,
626                         )
627                 };
628                 do_coin_selection(false, false)
629                         .or_else(|_| do_coin_selection(false, true))
630                         .or_else(|_| do_coin_selection(true, false))
631                         .or_else(|_| do_coin_selection(true, true))
632         }
633
634         fn sign_tx(&self, tx: Transaction) -> Result<Transaction, ()> {
635                 self.source.sign_tx(tx)
636         }
637 }
638
639 /// A handler for [`Event::BumpTransaction`] events that sources confirmed UTXOs from a
640 /// [`CoinSelectionSource`] to fee bump transactions via Child-Pays-For-Parent (CPFP) or
641 /// Replace-By-Fee (RBF).
642 ///
643 /// [`Event::BumpTransaction`]: crate::events::Event::BumpTransaction
644 pub struct BumpTransactionEventHandler<B: Deref, C: Deref, SP: Deref, L: Deref>
645 where
646         B::Target: BroadcasterInterface,
647         C::Target: CoinSelectionSource,
648         SP::Target: SignerProvider,
649         L::Target: Logger,
650 {
651         broadcaster: B,
652         utxo_source: C,
653         signer_provider: SP,
654         logger: L,
655         secp: Secp256k1<secp256k1::All>,
656 }
657
658 impl<B: Deref, C: Deref, SP: Deref, L: Deref> BumpTransactionEventHandler<B, C, SP, L>
659 where
660         B::Target: BroadcasterInterface,
661         C::Target: CoinSelectionSource,
662         SP::Target: SignerProvider,
663         L::Target: Logger,
664 {
665         /// Returns a new instance capable of handling [`Event::BumpTransaction`] events.
666         ///
667         /// [`Event::BumpTransaction`]: crate::events::Event::BumpTransaction
668         pub fn new(broadcaster: B, utxo_source: C, signer_provider: SP, logger: L) -> Self {
669                 Self {
670                         broadcaster,
671                         utxo_source,
672                         signer_provider,
673                         logger,
674                         secp: Secp256k1::new(),
675                 }
676         }
677
678         /// Updates a transaction with the result of a successful coin selection attempt.
679         fn process_coin_selection(&self, tx: &mut Transaction, mut coin_selection: CoinSelection) {
680                 for utxo in coin_selection.confirmed_utxos.drain(..) {
681                         tx.input.push(TxIn {
682                                 previous_output: utxo.outpoint,
683                                 script_sig: Script::new(),
684                                 sequence: Sequence::ZERO,
685                                 witness: Witness::new(),
686                         });
687                 }
688                 if let Some(change_output) = coin_selection.change_output.take() {
689                         tx.output.push(change_output);
690                 } else if tx.output.is_empty() {
691                         // We weren't provided a change output, likely because the input set was a perfect
692                         // match, but we still need to have at least one output in the transaction for it to be
693                         // considered standard. We choose to go with an empty OP_RETURN as it is the cheapest
694                         // way to include a dummy output.
695                         log_debug!(self.logger, "Including dummy OP_RETURN output since an output is needed and a change output was not provided");
696                         tx.output.push(TxOut {
697                                 value: 0,
698                                 script_pubkey: Script::new_op_return(&[]),
699                         });
700                 }
701         }
702
703         /// Handles a [`BumpTransactionEvent::ChannelClose`] event variant by producing a fully-signed
704         /// transaction spending an anchor output of the commitment transaction to bump its fee and
705         /// broadcasts them to the network as a package.
706         fn handle_channel_close(
707                 &self, claim_id: ClaimId, package_target_feerate_sat_per_1000_weight: u32,
708                 commitment_tx: &Transaction, commitment_tx_fee_sat: u64, anchor_descriptor: &AnchorDescriptor,
709         ) -> Result<(), ()> {
710                 // Our commitment transaction already has fees allocated to it, so we should take them into
711                 // account. We compute its feerate and subtract it from the package target, using the result
712                 // as the target feerate for our anchor transaction. Unfortunately, this results in users
713                 // overpaying by a small margin since we don't yet know the anchor transaction size, and
714                 // avoiding the small overpayment only makes our API even more complex.
715                 let commitment_tx_sat_per_1000_weight: u32 = compute_feerate_sat_per_1000_weight(
716                         commitment_tx_fee_sat, commitment_tx.weight() as u64,
717                 );
718                 let anchor_target_feerate_sat_per_1000_weight = core::cmp::max(
719                         package_target_feerate_sat_per_1000_weight - commitment_tx_sat_per_1000_weight,
720                         FEERATE_FLOOR_SATS_PER_KW,
721                 );
722
723                 log_debug!(self.logger, "Peforming coin selection for anchor transaction targeting {} sat/kW",
724                         anchor_target_feerate_sat_per_1000_weight);
725                 let must_spend = vec![Input {
726                         outpoint: anchor_descriptor.outpoint,
727                         previous_utxo: anchor_descriptor.previous_utxo(),
728                         satisfaction_weight: commitment_tx.weight() as u64 + ANCHOR_INPUT_WITNESS_WEIGHT + EMPTY_SCRIPT_SIG_WEIGHT,
729                 }];
730                 let coin_selection = self.utxo_source.select_confirmed_utxos(
731                         claim_id, must_spend, &[], anchor_target_feerate_sat_per_1000_weight,
732                 )?;
733
734                 let mut anchor_tx = Transaction {
735                         version: 2,
736                         lock_time: PackedLockTime::ZERO, // TODO: Use next best height.
737                         input: vec![anchor_descriptor.unsigned_tx_input()],
738                         output: vec![],
739                 };
740                 #[cfg(debug_assertions)]
741                 let total_satisfaction_weight =
742                         coin_selection.confirmed_utxos.iter().map(|utxo| utxo.satisfaction_weight).sum::<u64>() +
743                                 ANCHOR_INPUT_WITNESS_WEIGHT + EMPTY_SCRIPT_SIG_WEIGHT;
744
745                 self.process_coin_selection(&mut anchor_tx, coin_selection);
746                 let anchor_txid = anchor_tx.txid();
747
748                 debug_assert_eq!(anchor_tx.output.len(), 1);
749                 #[cfg(debug_assertions)]
750                 let unsigned_tx_weight = anchor_tx.weight() as u64 - (anchor_tx.input.len() as u64 * EMPTY_SCRIPT_SIG_WEIGHT);
751
752                 log_debug!(self.logger, "Signing anchor transaction {}", anchor_txid);
753                 anchor_tx = self.utxo_source.sign_tx(anchor_tx)?;
754
755                 let signer = anchor_descriptor.derive_channel_signer(&self.signer_provider);
756                 let anchor_sig = signer.sign_holder_anchor_input(&anchor_tx, 0, &self.secp)?;
757                 anchor_tx.input[0].witness = anchor_descriptor.tx_input_witness(&anchor_sig);
758
759                 #[cfg(debug_assertions)] {
760                         let signed_tx_weight = anchor_tx.weight() as u64;
761                         let expected_signed_tx_weight = unsigned_tx_weight + total_satisfaction_weight;
762                         // Our estimate should be within a 1% error margin of the actual weight and we should
763                         // never underestimate.
764                         assert!(expected_signed_tx_weight >= signed_tx_weight &&
765                                 expected_signed_tx_weight - (expected_signed_tx_weight / 100) <= signed_tx_weight);
766                 }
767
768                 log_info!(self.logger, "Broadcasting anchor transaction {} to bump channel close with txid {}",
769                         anchor_txid, commitment_tx.txid());
770                 self.broadcaster.broadcast_transactions(&[&commitment_tx, &anchor_tx]);
771                 Ok(())
772         }
773
774         /// Handles a [`BumpTransactionEvent::HTLCResolution`] event variant by producing a
775         /// fully-signed, fee-bumped HTLC transaction that is broadcast to the network.
776         fn handle_htlc_resolution(
777                 &self, claim_id: ClaimId, target_feerate_sat_per_1000_weight: u32,
778                 htlc_descriptors: &[HTLCDescriptor], tx_lock_time: PackedLockTime,
779         ) -> Result<(), ()> {
780                 let mut htlc_tx = Transaction {
781                         version: 2,
782                         lock_time: tx_lock_time,
783                         input: vec![],
784                         output: vec![],
785                 };
786                 let mut must_spend = Vec::with_capacity(htlc_descriptors.len());
787                 for htlc_descriptor in htlc_descriptors {
788                         let htlc_input = htlc_descriptor.unsigned_tx_input();
789                         must_spend.push(Input {
790                                 outpoint: htlc_input.previous_output.clone(),
791                                 previous_utxo: htlc_descriptor.previous_utxo(&self.secp),
792                                 satisfaction_weight: EMPTY_SCRIPT_SIG_WEIGHT + if htlc_descriptor.preimage.is_some() {
793                                         HTLC_SUCCESS_INPUT_ANCHOR_WITNESS_WEIGHT
794                                 } else {
795                                         HTLC_TIMEOUT_INPUT_ANCHOR_WITNESS_WEIGHT
796                                 },
797                         });
798                         htlc_tx.input.push(htlc_input);
799                         let htlc_output = htlc_descriptor.tx_output(&self.secp);
800                         htlc_tx.output.push(htlc_output);
801                 }
802
803                 log_debug!(self.logger, "Peforming coin selection for HTLC transaction targeting {} sat/kW",
804                         target_feerate_sat_per_1000_weight);
805                 #[cfg(debug_assertions)]
806                 let must_spend_satisfaction_weight =
807                         must_spend.iter().map(|input| input.satisfaction_weight).sum::<u64>();
808                 let coin_selection = self.utxo_source.select_confirmed_utxos(
809                         claim_id, must_spend, &htlc_tx.output, target_feerate_sat_per_1000_weight,
810                 )?;
811                 #[cfg(debug_assertions)]
812                 let total_satisfaction_weight =
813                         coin_selection.confirmed_utxos.iter().map(|utxo| utxo.satisfaction_weight).sum::<u64>() +
814                                 must_spend_satisfaction_weight;
815                 self.process_coin_selection(&mut htlc_tx, coin_selection);
816
817                 #[cfg(debug_assertions)]
818                 let unsigned_tx_weight = htlc_tx.weight() as u64 - (htlc_tx.input.len() as u64 * EMPTY_SCRIPT_SIG_WEIGHT);
819
820                 log_debug!(self.logger, "Signing HTLC transaction {}", htlc_tx.txid());
821                 htlc_tx = self.utxo_source.sign_tx(htlc_tx)?;
822
823                 let mut signers = BTreeMap::new();
824                 for (idx, htlc_descriptor) in htlc_descriptors.iter().enumerate() {
825                         let signer = signers.entry(htlc_descriptor.channel_derivation_parameters.keys_id)
826                                 .or_insert_with(|| htlc_descriptor.derive_channel_signer(&self.signer_provider));
827                         let htlc_sig = signer.sign_holder_htlc_transaction(&htlc_tx, idx, htlc_descriptor, &self.secp)?;
828                         let witness_script = htlc_descriptor.witness_script(&self.secp);
829                         htlc_tx.input[idx].witness = htlc_descriptor.tx_input_witness(&htlc_sig, &witness_script);
830                 }
831
832                 #[cfg(debug_assertions)] {
833                         let signed_tx_weight = htlc_tx.weight() as u64;
834                         let expected_signed_tx_weight = unsigned_tx_weight + total_satisfaction_weight;
835                         // Our estimate should be within a 1% error margin of the actual weight and we should
836                         // never underestimate.
837                         assert!(expected_signed_tx_weight >= signed_tx_weight &&
838                                 expected_signed_tx_weight - (expected_signed_tx_weight / 100) <= signed_tx_weight);
839                 }
840
841                 log_info!(self.logger, "Broadcasting {}", log_tx!(htlc_tx));
842                 self.broadcaster.broadcast_transactions(&[&htlc_tx]);
843                 Ok(())
844         }
845
846         /// Handles all variants of [`BumpTransactionEvent`].
847         pub fn handle_event(&self, event: &BumpTransactionEvent) {
848                 match event {
849                         BumpTransactionEvent::ChannelClose {
850                                 claim_id, package_target_feerate_sat_per_1000_weight, commitment_tx,
851                                 commitment_tx_fee_satoshis, anchor_descriptor, ..
852                         } => {
853                                 log_info!(self.logger, "Handling channel close bump (claim_id = {}, commitment_txid = {})",
854                                         log_bytes!(claim_id.0), commitment_tx.txid());
855                                 if let Err(_) = self.handle_channel_close(
856                                         *claim_id, *package_target_feerate_sat_per_1000_weight, commitment_tx,
857                                         *commitment_tx_fee_satoshis, anchor_descriptor,
858                                 ) {
859                                         log_error!(self.logger, "Failed bumping commitment transaction fee for {}",
860                                                 commitment_tx.txid());
861                                 }
862                         }
863                         BumpTransactionEvent::HTLCResolution {
864                                 claim_id, target_feerate_sat_per_1000_weight, htlc_descriptors, tx_lock_time,
865                         } => {
866                                 log_info!(self.logger, "Handling HTLC bump (claim_id = {}, htlcs_to_claim = {})",
867                                         log_bytes!(claim_id.0), log_iter!(htlc_descriptors.iter().map(|d| d.outpoint())));
868                                 if let Err(_) = self.handle_htlc_resolution(
869                                         *claim_id, *target_feerate_sat_per_1000_weight, htlc_descriptors, *tx_lock_time,
870                                 ) {
871                                         log_error!(self.logger, "Failed bumping HTLC transaction fee for commitment {}",
872                                                 htlc_descriptors[0].commitment_txid);
873                                 }
874                         }
875                 }
876         }
877 }