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

From: Antoine Riard <antoine.riard@gmail•com>
To: Lloyd Fournier <lloyd.fourn@gmail•com>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
Date: Mon, 14 Jun 2021 12:46:56 -0400	[thread overview]
Message-ID: <CALZpt+E09jViG0owWpSWBoG5rjk_=HdMgQisp_1DsBEKBq-D2w@mail.gmail.com> (raw)
In-Reply-To: <CAH5Bsr0V6r3+GsDg=CbDshj=QnpAr+saXftG_pazkWvL=m-W3g@mail.gmail.com>

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

> This makes a lot of sense as it matches the semantics of what we are
trying
to achieve: allow the owner of an output (whether an individual or group)
to reduce that output's value to pay a higher fee.

Note, I think you're still struggling with some trust issue that anchor
upgrade is at least eliminating for LN, namely the pre-agreement among a
group of signers about the effective feerate to use at some unknown time
point in the future. If you authorize your counterparty for a broadcast at
feerate X, how do you prevent a broadcast at feerate Y, where Y is far
under X, thus maliciously burning a lot of your fee-bumping reserve ?

Of course, one mitigation is to make a contribution to a common fee-bumping
output reserve proportional to what has been contributed as a funding
collateral. Thus disincentivizing misuse of the common fee-bumping reserve
in a game-theoretical way. But if you take the example of a LN channel,
you're now running into another issue. Off-chain balances might fluctuate
in a way that most of the time, your fee-bumping reserve contribution is
out-of-proportion with your balance amounts to protect ? And as such
enduring some significant timevalue bleeding on your fee-bumping reserve.

Single-party managed fee-bumping reserve doesn't seem to suffer from this
drawback ?

Otherwise, I think your new construction OP_PUSH_TAPROOT_OUTPUT_KEY is
correct and solves the O(log(n)) tapleaves issue.

Le dim. 13 juin 2021 à 01:57, Lloyd Fournier <lloyd.fourn@gmail•com> a
écrit :

> On Fri, 11 Jun 2021 at 07:45, Antoine Riard <antoine.riard@gmail•com>
> wrote:
>
>> 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 ?
>>
>
> Right.
>
>
>> 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
>>
>
> Yes but we can fix this (see below).
>
> * 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 ?
>>
>
> Yes. You could use OP_LESSTHAN to make sure the value being deducted by
> the watchtower is not above a threshold.
>
>
>> 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].
>>
>
> Yes, that's also a way to do it. I was trying to preserve the original
> external key signature in my attempt but this is probably not necessary. L2
> protocols could just exchange two signatures instead. One optimistic one on
> the external key and one pessimistic SIGHASH_ANYAMOUNT one on the
> <contract_key>.
>
>
>> 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 ?
>>
>
> Hmmm well I was hoping that you wouldn't need interaction ever. I can see
> that my commitment TX example was too contrived because it has balance
> outputs that go exclusively to one party.
> Let's take a better example: A PTLC output with both timeout and success
> pre-signed transactions spending from it. We must only let the person
> offering the PTLC reduce the output of the timeout tx and the converse for
> the success tx.
> Note very carefully that if we naively apply OP_CHECKSIG_MUTATED or
> SIGHASH_ANYAMOUNT with one tapleaf for each party then we risk one party
> being able to lower the other party's output by doing a switcharoo on the
> tapleaf after they see the signature for their counterparty's tx in the
> mempool. In your example you could fix it by having a different
> <contract_key> but this means we can't compress <contract_key> by just
> using the taproot internal/external key.
>
> What about this: Instead of party specific "finalizing_alice_key" or
> p1-fee-bump-key as I denoted it, we just use the key of the output whose
> value we are reducing. This also solves the O(log(n)) tapleaves for
> OP_CHECKSIG_MUTATED approach as well -- just have one tapleaf for fee
> bumping but authorize it under the key of the output we are reducing. Thus
> we need something like OP_PUSH_TAPROOT_OUTPUT_KEY <output index> which
> takes the taproot external key at that output (fail if not taproot) and
> puts it on the stack. So to be clear you have the <output index> on the
> witness stack rather than having it fixed in a particular tapleaf (as per
> my original post) and then use OP_DUP to pass it to both
> OP_CHECKSIG_MUTATED and OP_PUSH_TAPROOT_OUTPUT_KEY.
> This makes a lot of sense as it matches the semantics of what we are
> trying to achieve: allow the owner of an output (whether an individual or
> group) to reduce that output's value to pay a higher fee.
> Furthermore this removes all keys from the tapleaf since they are all
> aliased to either the input we are spending or one of the output keys of
> the tx we are spending to. This is quite a big improvement over my original
> idea.
>
> This works for lightning commit tx and for the case of a PTLC contract. It
> also seems to work for the DLC funding output. I'd be interested to know if
> anyone can think of a protocol where this would be inconvenient or
> impossible to use as the main pre-signed tx fee bumping system.
>
> Cheers,
>
> LL
>
> 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: 20757 bytes --]