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

[Antoine Riard <antoine.riard@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 13331 bytes --]

Hi Lloyd,

Thanks for this tx mutation proposal extending the scope of fee-bumping
techniques. IIUC, the <output_index> serves as a pointer to increase the
output amount by value to recover the recompute the transaction hash
against which the original signature is valid ?

Let's do a quick analysis of this scheme.
* onchain footprint : one tapleaf per contract participant, with O(log n)
increase of witness size, also one output per contract participant
* tx-relay bandwidth rebroadcast : assuming aforementioned in-place mempool
substitution policy, the mutated transaction
* batching : fee-bumping value is extract from contract transaction itself,
so O(n) per contract
* mempool flexibility : the mutated transaction
* watchtower key management : to enable outsourcing, the mutating key must
be shared, in theory enabling contract value siphoning to miner fees ?

Further, I think tx mutation scheme can be achieved in another way, with
SIGHASH_ANYAMOUNT. A contract participant tapscript will be the following :

<contract_key> <finalizing_alice_key>

Where <contract_signature> is committed with SIGHASH_ANYAMOUNT, blanking
nValue of one or more outputs. That way, the fee-to-contract-value
distribution can be unilaterally finalized at a later time through the
finalizing key [0].

Note, I think that the tx mutation proposal relies on interactivity in the
worst-case scenario where a counterparty wants to increase its fee-bumping
output from the contract balance. This interactivity may lure a
counterparty to alway lock the worst-case fee-bumping reserve in the
output. I believe anchor output enables more "real-time" fee-bumping
reserve adjustment ?

Cheers,
Antoine

[0] Incautious sighash alleability is unsafe. Be careful, otherwise kitties
will perish by the thousands :
https://github.com/revault/practical-revault/pull/83

Le dim. 6 juin 2021 à 22:28, Lloyd Fournier <lloyd.fourn@gmail.com> a
écrit :

> Hi Antione,
>
> Thanks for bringing up this important topic. I think there might be
> another class of solutions over input based, CPFP and sponsorship. I'll
> call them tx mutation schemes. The idea is that you can set a key that can
> increase the fee by lowering a particular output after the tx is signed
> without invalidating the signature. The premise is that anytime you need to
> bump the fee of a transaction you must necessarily have funds in an output
> that are going to you and therefore you can sacrifice some of them to
> increase the fee. This is obviously destructive to txids so child presigned
> transactions will have to use ANYPREVOUT as in your proposal. The advantage
> is that it does not require keeping extra inputs around to bump the fee.
>
> So imagine a new opcode OP_CHECKSIG_MUTATED <output index> <publickey>
> <value> <signature>.
> This would check that <signature> is valid against <publickey> if the
> current transaction had the output at <output index> reduced by <value>. To
> make this more efficient, if the public key is one byte: 0x02 it references
> the taproot *external key* (similar to how ANYPREVOUT uses 0x01 to refer to
> internal key[1]).
> Now for our protocol we want both parties (p1 and p2) to be able to fee
> bump a commitment transaction. They use MuSig to sign the commitment tx
> under the external key with a decent fee for the current conditions. But in
> case it proves insufficient they have added the following two leaves to
> their key in the funding output as a backup so that p1 and p2 can
> unilaterally bump the fee of anything they sign spending from the funding
> output:
>
> 1. OP_CHECKSIG_MUTATED(0, 0x02, <fee-bump-value>, <original-signature>)
> OP_CHECKSIGADD(p1-fee-bump-key, <p1-fee-bump-signature>)  OP_2
> OP_NUMEQUALVERIFY
> 2. OP_CHECKSIG_MUTATED(1, 0x02, <fee-bump-value>, <original-signature>)
> OP_CHECKSIGADD(p2-fee-bump-key, <p2-fee-bump-signature>) OP_2
> OP_NUMEQUALVERIFY
>
> where <...> indicates the thing comes from the witness stack.
> So to bump the fee of the commit tx after it has been signed either party
> takes the <original-signature> and adds a signature under their
> fee-bump-key for the new tx and reveals their fee bump leaf.
> <original-signature> is checked against the old transaction while the fee
> bumped transaction is checked against the fee bump key.
>
> I know I have left out how to change mempool eviction rules to accommodate
> this kind of fee bumping without DoS or pinning attacks but hopefully I
> have demonstrated that this class of solutions also exists.
>
> [1] https://github.com/ajtowns/bips/blob/bip-anyprevout/bip-0118.mediawiki
>
> Cheers,
>
> LL
>
>
>
> On Fri, 28 May 2021 at 07:13, Antoine Riard via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> 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.
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>

[-- Attachment #2: Type: text/html, Size: 14572 bytes --]