Subject: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

From: Antoine Riard <[email-masked]>
Date: Thu, 27 May 2021 16:14:13 -0400

Hi,

This post is pursuing a wider discussion around better fee-bumping
strategies for second-layer protocols. It draws out a comparison between
input-based and CPFP fee-bumping techniques, and their apparent trade-offs
in terms of onchain footprint, tx-relay bandwidth rebroadcast, batching
opportunity and mempool flexibility.

Thanks to Darosior for reviews, ideas and discussions.

## Child-Pay-For-Parent

CPFP is a mature fee-bumping technique, known and used for a while in the
Bitcoin ecosystem. However, its usage in contract protocols with
distrusting counterparties raised some security issues. As mempool's chain
of unconfirmed transactions are limited in size, if any output is spendable
by any contract participant, it can be leveraged as a pinning vector to
downgrade odds of transaction confirmation [0].

That said, contract transactions interested to be protected under the
carve-out logic require to add a new output for any contract participant,
even if ultimately only one of them serves as an anchor to attach a CPFP.

## Input-Based

I think input-based fee-bumping has been less studied as fee-bumping
primitive for L2s [1]. One variant of input-based fee-bumping usable today
is the leverage of the SIGHASH_ANYONECANPAY/SIGHASH_SINGLE malleability
flags. If the transaction is the latest stage of the contract, a bumping
input can be attached just-in-time, thus increasing the feerate of the
whole package.

However, as of today, input-based fee-bumping doesn't work to bump first
stages of contract transactions as it's destructive of the txid, and as
such breaks chain of pre-signed transactions. A first improvement would be
the deployment of the SIGHASH_ANYPREVOUT softfork proposal. This new
malleability flag allows a transaction to be signed without reference to
any specific previous output. That way,  spent transactions can be
fee-bumped without altering validity of the chain of transactions.

Even assuming SIGHASH_ANYPREVOUT, if the first stage contract transaction
includes multiple outputs (e.g the LN's commitment tx has multiple HTLC
outputs), SIGHASH_SINGLE can't be used and the fee-bumping input value
might be wasted. This edge can be smoothed by broadcasting a preliminary
fan-out transaction with a set of outputs providing a range of feerate
points for the bumped transaction.

This overhead could be smoothed even further in the future with more
advanced sighash malleability flags like SIGHASH_IOMAP, allowing
transaction signers to commit to a map of inputs/outputs [2]. In the
context of input-based, the overflowed fee value could be redirected to an
outgoing output.

## Onchain Footprint

CPFP: One anchor output per participant must be included in the commitment
transaction. To this anchor must be attached a child transaction with 2
inputs (one for the commitment, one for the bumping utxo) and 1 output.
Onchain footprint: 2 inputs + 3 outputs.

Input-based (today): If the bumping utxo is offering an adequate feerate
point in function of network mempools congestion at time of broadcast, only
1 input. If a preliminary fan-out transaction to adjust feerate point must
be broadcasted first, 1 input and 2 outputs more must be accounted for.
Onchain footprint: 2 inputs + 3 outputs.

Input-based (SIGHASH_ANYPREVOUT+SIGHASH_IOMAP): As long as the bumping
utxo's value is wide enough to cover the worst-case of mempools congestion,
the bumped transaction can be attached 1 input and 1 output. Onchain
footprint: 1 input + 1 output.

## Tx-Relay Bandwidth Rebroadcast

CPFP: In the context of multi-party protocols, we should assume bounded
rationality of the participants w.r.t to an unconfirmed spend of the
contract utxo across network mempools. Under this assumption, the bumped
transaction might have been replaced by a concurrent state. To guarantee
efficiency of the CPFP the whole chain of transactions should be
rebroadcast, perhaps wasting bandwidth consumption for a still-identical
bumped transaction [3]. Rebroadcast footprint: the whole chain of
transactions.

Input-based (today): In case of rebroadcast, the fee-bumping input is
attached to the root of the chain of transactions and as such breaks the
chain validity in itself. Beyond the rebroadcast of the updated root under
replacement policy, the remaining transactions must be updated and
rebroadcast. Rebroadcast footprint: the whole chain of transactions.

Input-based(SIGHASH_ANYPREVOUT+SIGHASH_IOMAP): In case of rebroadcast, the
fee-bumping is attached to the root of the chain of transactions but it
doesn't break the chain validity in itself. Assuming a future mempool
acceptance logic to authorize in-place substitution, the rest of the chain
could be preserved. Rebroadcast footprint: the root of the chain of
transactions.

## Fee-Bumping Batching

CPFP: In the context of multi-party protocols, in optimistic scenarios, we
can assume aggregation of multiple chains of transactions. For e.g, a LN
operator is desirous to non-cooperatively close multiple channels at the
same time and would like to combine their fee-bumping. With CPFP, one
anchor output and one bumping input must be consumed per aggregated chain,
even if the child transaction fields can be shared. Batching perf: 1
input/1 output per aggregated chain.

Input-based (today): Unless the contract allows interactivity, multiple
chains of transactions cannot be aggregated. One bumping input must be
attached per chain, though if a preliminary fan-out transaction is relied
on to offer multiple feerate points, transaction fields can be shared.
Batching perf: 1 input/1 output per aggregated chain.

Input-based (SIGHASH_ANYPREVOUT+SIGHASH_IOMAP): Multiple chains of
transactions might be aggregated together *non-interactively*. One bumping
input and outgoing output can be attached to the aggregated root. Batching
perf: 1 input/1 output per aggregation.

## Fee-Bumping Mempool Flexibility

CPFP: In the context of multi-party protocols, one of your counterparties
might build a branch of transactions from one of the root outputs thus
saturating the in-mempool package limits. To avoid these shenanigans, LN
channels are relying on the carve-out mechanism. Though, the carve-out
mechanism includes its own limitation and doesn't scale beyond 2 contract
participants.

Input-based: The root of the chain of transaction is the package's oldest
ancestor, so package limits don't restrain its acceptance and it works
whatever the number of contract participants.

To conclude, this post scores 2 fee-bumping primitives for multi-party
protocols on a range of factors. It hopes to unravel the ground for a real
feerate performance framework of second-layers protocols .

Beyond that, few points can be highlighted a) future soft forks allow
significant onchain footprint savings, especially in case of batching, b)
future package relay bandwidth efficiency should account for rebroadcast
frequency of CPFPing multi-party protocols. On this latter point one
follow-up might be to evaluate differing package relay *announcement*
schemes in function of odds of non-cooperative protocol broadcast/odds of
concurrent broadcast/rebroadcast frequencies.

Thoughts ?

Cheers,
Antoine

[0]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-November/016518.html
[1] Beyond the revault architecture :
https://github.com/revault/practical-revault/blob/master/revault.pdf
[2] Already proposed a while back :
https://bitcointalk.org/index.php?topic=252960.0
[3] In theory, an already-relayed transaction shouldn't pass Core's
`filterInventoryKnown`. In practice, if the transaction is announced as
part of a package_id, the child might have changed, not the parent, leading
to a redundant relay of the latter.