Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id BC964C000B for ; Mon, 14 Jun 2021 16:47:13 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 99AC483A41 for ; Mon, 14 Jun 2021 16:47:13 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.098 X-Spam-Level: X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: smtp1.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id mh33IrgA7Giv for ; Mon, 14 Jun 2021 16:47:11 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-wr1-x433.google.com (mail-wr1-x433.google.com [IPv6:2a00:1450:4864:20::433]) by smtp1.osuosl.org (Postfix) with ESMTPS id E12E383437 for ; Mon, 14 Jun 2021 16:47:10 +0000 (UTC) Received: by mail-wr1-x433.google.com with SMTP id a20so15303867wrc.0 for ; Mon, 14 Jun 2021 09:47:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=ly0t5Dya589sUUVPjjzOqqC/LRRxB2lqppgsRT4C21w=; b=i8l9hiTVwh6ywNIBA7ZHAEgDD3iQQ+H1lQUZzNYwJ8tqr2OdghJ1uOYZk/cui9mzcG 1jW9LETLGXG8uo2DaQO0seY4p3W8MrvZmK3Arh8FlhMnK1rW/O1kVMzaZ87027fyl+tG tyJzLLzkm/csLCtYjsrSGQts5ovELUE3w9m4R8udCWAECKyBZmZ5uIcVMkYNWnz1W0PW Vkl2NOoI7QdSPFD/RCvd0SohBOa3Wmu4pGkay5RrGaKbn2tCLIzyGcnaJvW/4AwAtcRk gD7bHF/3TCzXBB3SW4LPTDnI5NoPVBvXTlQFdqLM7QHnb7uP7eRJO/jHn0pgdI9l7p/V +Mgw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=ly0t5Dya589sUUVPjjzOqqC/LRRxB2lqppgsRT4C21w=; b=KqNy64omQ3RQj9txdlnB2KPpoZ/gBGlBEp5pXcZ8Hgk1tWUGuK8YqFuXObveHhiLng CN4I5ppdR1qfuaVtDNOguw4p4H1F9nQcno1WAb/TX1oAFv92I2VmcB7moV+KoHzE5Cv+ nt+lVQ/3Cw3tY0iOP+kbpNrula91DX9Jx4jKHu1lkfhHPzr1TFBbPCdRYujGJtKuy3/b CkDn6KgpqXF7qoeGL2rO6SM7xQkMu5eP81KY+QSBqCSbDuUXcyJY0UzoEihiZ+1A7EeQ I3zAkKhycvoL9JN+6zRxYbz6mIGjByTA/xDUOWUDJmY0fdM1CconbzEE9sP8EkWnEhpx uuVQ== X-Gm-Message-State: AOAM531qGJjudBHAGRJq62YCiVTZzpAKTIf0XKViVzzzt5idrcZawC2P 4YwJs8x/VZX9wXb9WKsLBdUF2zAlHayUxhDpubo= X-Google-Smtp-Source: ABdhPJw1dpW1Z9wA86z/9RELmBY4vCtI18NoZiWXPw/nKY/mE/rTt+SmwjCPkTiLhW2w0Rjd37Bm+kwsufNd+zX+tqQ= X-Received: by 2002:a5d:64e4:: with SMTP id g4mr20068489wri.290.1623689229100; Mon, 14 Jun 2021 09:47:09 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Antoine Riard Date: Mon, 14 Jun 2021 12:46:56 -0400 Message-ID: To: Lloyd Fournier Content-Type: multipart/alternative; boundary="000000000000b9eb5005c4bc9b81" X-Mailman-Approved-At: Mon, 14 Jun 2021 17:04:35 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 14 Jun 2021 16:47:14 -0000 --000000000000b9eb5005c4bc9b81 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable > 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 =C3=A0 01:57, Lloyd Fournier a =C3=A9crit : > On Fri, 11 Jun 2021 at 07:45, Antoine Riard > wrote: > >> Hi Lloyd, >> >> Thanks for this tx mutation proposal extending the scope of fee-bumping >> techniques. IIUC, the 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 fee= s ? >> > > 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 followin= g : >> >> >> >> Where 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 > . > > >> 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 lur= e 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 fo= r > 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 > but this means we can't compress 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. Thu= s > we need something like OP_PUSH_TAPROOT_OUTPUT_KEY 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 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 origin= al > idea. > > This works for lightning commit tx and for the case of a PTLC contract. I= t > 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 =C3=A0 22:28, Lloyd Fournier = a >> =C3=A9crit : >> >>> 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 nee= d to >>> bump the fee of a transaction you must necessarily have funds in an out= put >>> 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 presi= gned >>> transactions will have to use ANYPREVOUT as in your proposal. The advan= tage >>> is that it does not require keeping extra inputs around to bump the fee= . >>> >>> So imagine a new opcode OP_CHECKSIG_MUTATED >>> . >>> This would check that is valid against if the >>> current transaction had the output at reduced by = . To >>> make this more efficient, if the public key is one byte: 0x02 it refere= nces >>> the taproot *external key* (similar to how ANYPREVOUT uses 0x01 to refe= r 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. Bu= t 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 fundi= ng >>> output: >>> >>> 1. OP_CHECKSIG_MUTATED(0, 0x02, , ) >>> OP_CHECKSIGADD(p1-fee-bump-key, ) OP_2 >>> OP_NUMEQUALVERIFY >>> 2. OP_CHECKSIG_MUTATED(1, 0x02, , ) >>> OP_CHECKSIGADD(p2-fee-bump-key, ) 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 and adds a signature under their >>> fee-bump-key for the new tx and reveals their fee bump leaf. >>> is checked against the old transaction while the f= ee >>> 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 betwe= en >>>> input-based and CPFP fee-bumping techniques, and their apparent trade-= offs >>>> in terms of onchain footprint, tx-relay bandwidth rebroadcast, batchin= g >>>> 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 c= hain >>>> of unconfirmed transactions are limited in size, if any output is spen= dable >>>> by any contract participant, it can be leveraged as a pinning vector t= o >>>> 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 participa= nt, >>>> even if ultimately only one of them serves as an anchor to attach a CP= FP. >>>> >>>> ## 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 t= oday >>>> is the leverage of the SIGHASH_ANYONECANPAY/SIGHASH_SINGLE malleabilit= y >>>> flags. If the transaction is the latest stage of the contract, a bumpi= ng >>>> 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 w= ould >>>> be the deployment of the SIGHASH_ANYPREVOUT softfork proposal. This ne= w >>>> 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-bumpi= ng >>>> input value might be wasted. This edge can be smoothed by broadcasting= a >>>> preliminary fan-out transaction with a set of outputs providing a rang= e 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 t= o 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 transa= ction >>>> 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 adjus= t >>>> feerate point must be broadcasted first, 1 input and 2 outputs more mu= st 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 conges= tion, >>>> 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 bounde= d >>>> rationality of the participants w.r.t to an unconfirmed spend of the >>>> contract utxo across network mempools. Under this assumption, the bump= ed >>>> transaction might have been replaced by a concurrent state. To guarant= ee >>>> efficiency of the CPFP the whole chain of transactions should be >>>> rebroadcast, perhaps wasting bandwidth consumption for a still-identic= al >>>> 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 t= he >>>> chain validity in itself. Beyond the rebroadcast of the updated root u= nder >>>> 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 b= ut it >>>> doesn't break the chain validity in itself. Assuming a future mempool >>>> acceptance logic to authorize in-place substitution, the rest of the c= hain >>>> 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 t= he >>>> same time and would like to combine their fee-bumping. With CPFP, one >>>> anchor output and one bumping input must be consumed per aggregated ch= ain, >>>> 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, multipl= e >>>> chains of transactions cannot be aggregated. One bumping input must be >>>> attached per chain, though if a preliminary fan-out transaction is rel= ied >>>> 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 bum= ping >>>> input and outgoing output can be attached to the aggregated root. Batc= hing >>>> 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 ro= ot >>>> outputs thus saturating the in-mempool package limits. To avoid these >>>> shenanigans, LN channels are relying on the carve-out mechanism. Thoug= h, >>>> 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 i= t >>>> 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 rebroadca= st >>>> 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=3D252960.0 >>>> [3] In theory, an already-relayed transaction shouldn't pass Core's >>>> `filterInventoryKnown`. In practice, if the transaction is announced a= s >>>> part of a package_id, the child might have changed, not the parent, le= ading >>>> to a redundant relay of the latter. >>>> _______________________________________________ >>>> bitcoin-dev mailing list >>>> bitcoin-dev@lists.linuxfoundation.org >>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >>>> >>> --000000000000b9eb5005c4bc9b81 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
> 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 high= er fee.

Note, I think you're still struggling with some trust is= sue that anchor upgrade is at least eliminating for LN, namely the pre-agre= ement among a group of signers about the effective feerate to use at some u= nknown time point in the future. If you authorize your counterparty for a b= roadcast 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 f= ee-bumping output reserve proportional to what has been contributed as a fu= nding collateral. Thus disincentivizing misuse of the common fee-bumping re= serve in a game-theoretical way. But if you take the example of a LN channe= l, you're now running into another issue. Off-chain balances might fluc= tuate 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 en= during some significant timevalue bleeding on your fee-bumping reserve.
=
Single-party managed fee-bumping reserve doesn't seem to suffer fro= m this drawback ?

Otherwise, I think your new construction OP_PUSH_T= APROOT_OUTPUT_KEY is correct and solves the O(log(n)) tapleaves issue.
<= /div>
L= e=C2=A0dim. 13 juin 2021 =C3=A0=C2=A001:57, Lloyd Fournier <lloyd.fourn@gmail.com> a =C3=A9crit=C2= =A0:
On Fri, 11 Jun= 2021 at 07:45, Antoine Riard <antoine.riard@gmail.com> wrote:
<= div class=3D"gmail_quote">
Hi Lloyd,

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

Right.


Let's do a qui= ck analysis of this scheme.
* onchain footprint : one tapleaf per contra= ct participant, with O(log n) increase of witness size, also one output per= contract participant
=C2=A0
Yes but w= e can fix this (see below).

* tx-relay bandwidth rebroadcast : assuming afo= rementioned in-place mempool substitution policy, the mutated transaction <= br>
* batching : fee-bumping value is extract from contract transaction itsel= f, so O(n) per contract
* mempool flexibility : the mutated transaction<= br>* watchtower key management : to enable outsourcing, the mutating key mu= st be shared, in theory enabling contract value siphoning to miner fees ?
=C2=A0
Yes. You could use OP_LESSTHAN to ma= ke sure the value being deducted by the watchtower is not above a threshold= .


Further, I think tx mutation scheme can be achieved in an= other 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-valu= e distribution can be unilaterally finalized at a later time through the fi= nalizing key [0].
=C2=A0
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 co= uld just exchange two signatures instead. One optimistic one on the externa= l key and one pessimistic SIGHASH_ANYAMOUNT one on the <contract_key>= .


Note, I think that the tx mutation proposal relies on int= eractivity in the worst-case scenario where a counterparty wants to increas= e 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-bum= ping 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 on= e party.
Let's take a better exampl= e: A PTLC output with both timeout and success pre-signed transactions spen= ding from it. We must only let the person offering the PTLC reduce the outp= ut of the timeout tx and the converse for the success tx.
Note very= carefully that if we naively apply OP_CHECKSIG_MUTATED or SIGHASH_ANYAMOUN= T with one tapleaf for each party then we risk one party being able to lowe= r the other party's output by doing a switcharoo on the tapleaf after t= hey see the signature for their counterparty's tx in the mempool. In yo= ur example you could fix it by having a different <contract_key> but = this means we can't compress <contract_key> by just using the tap= root internal/external key.

What about this: I= nstead of party specific "finalizing_alice_key" or p1-fee-bump-ke= y as I denoted it, we just use the key of the output whose value we are red= ucing. This also solves the O(log(n)) tapleaves for OP_CHECKSIG_MUTATED app= roach as well -- just have one tapleaf for fee bumping but authorize it und= er the key of the output we are reducing. Thus we need something like OP_PU= SH_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 b= e 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_OUTPU= T_KEY.
This makes a lot of sense as it matches the semantics of w= hat we are trying to achieve: allow the owner of an output (whether an indi= vidual or group) to reduce that output's value to pay a higher fee.
Furthermore this removes all keys from the tapleaf since they are al= l 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 whe= re this would be inconvenient or impossible to use as the main pre-signed t= x fee bumping system.

Cheers,
<= br>
LL

Le=C2=A0dim. 6 juin 2021 =C3=A0=C2=A022:28, Lloyd Fournier <lloyd.fourn@gmail.com<= /a>> a =C3=A9crit=C2=A0:






Cheers,

LL


On Fri, 2= 8 May 2021 at 07:13, Antoine Riard via bitcoin-dev <bitcoin-dev@lists.li= nuxfoundation.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 techniq= ues, 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 f= or a while in the Bitcoin ecosystem. However, its usage in contract protoco= ls with distrusting counterparties raised some security issues. As mempool&= #39;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 ultimate= ly only one of them serves as an anchor to attach a CPFP.

## Input-B= ased

I think input-based fee-bumping has been less studied as fee-bu= mping primitive for L2s [1]. One variant of input-based fee-bumping usable = today is the leverage of the SIGHASH_ANYONECANPAY/SIGHASH_SINGLE malleabili= ty 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 who= le package.

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

Even assuming SIGHASH_ANYPREVOUT, if the first stage contract tra= nsaction includes multiple outputs (e.g the LN's commitment tx has mult= iple HTLC outputs), SIGHASH_SINGLE can't be used and the fee-bumping in= put value might be wasted. This edge can be smoothed by broadcasting a prel= iminary fan-out transaction with a set of outputs providing a range of feer= ate points for the bumped transaction.

This overhead could be smooth= ed even further in the future with more advanced sighash malleability flags= like SIGHASH_IOMAP, allowing transaction signers to commit to a map of inp= uts/outputs [2]. In the context of input-based, the overflowed fee value co= uld 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 in= puts (one for the commitment, one for the bumping utxo) and 1 output. Oncha= in footprint: 2 inputs + 3 outputs.

Input-based (today): If the bump= ing utxo is offering an adequate feerate point in function of network mempo= ols 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 outp= uts.

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. O= nchain footprint: 1 input + 1 output.

## Tx-Relay Bandwidth Rebroadc= ast

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

In= put-based (today): In case of rebroadcast, the fee-bumping input is attache= d to the root of the chain of transactions and as such breaks the chain val= idity in itself. Beyond the rebroadcast of the updated root under replaceme= nt policy, the remaining transactions must be updated and rebroadcast. Rebr= oadcast footprint: the whole chain of transactions.

Input-based(SIGH= ASH_ANYPREVOUT+SIGHASH_IOMAP): In case of rebroadcast, the fee-bumping is a= ttached to the root of the chain of transactions but it doesn't break t= he 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 trans= actions. For e.g, a LN operator is desirous to non-cooperatively close mult= iple 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 ag= gregated chain, even if the child transaction fields can be shared. Batchin= g perf: 1 input/1 output per aggregated chain.

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

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

## Fee-B= umping Mempool Flexibility

CPFP: In the context of multi-party proto= cols, one of your counterparties might build a branch of transactions from = one of the root outputs thus saturating the in-mempool package limits. To a= void 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 limi= ts don't restrain its acceptance and it works whatever the number of co= ntract participants.

To conclude, this post scores 2 fee-bumping pri= mitives for multi-party protocols on a range of factors. It hopes to unrave= l the ground for a real feerate performance framework of second-layers prot= ocols .

Beyond that, few points can be highlighted a) future soft fo= rks allow significant onchain footprint savings, especially in case of batc= hing, b) future package relay bandwidth efficiency should account for rebro= adcast frequency of CPFPing multi-party protocols. On this latter point one= follow-up might be to evaluate differing package relay *announcement* sche= mes in function of odds of non-cooperative protocol broadcast/odds of concu= rrent broadcast/rebroadcast frequencies.

Thoughts ?

Cheers,Antoine

[0] https://lists.lin= uxfoundation.org/pipermail/bitcoin-dev/2018-November/016518.html
[1]= Beyond the revault architecture : https://github.c= om/revault/practical-revault/blob/master/revault.pdf
[2] Already pro= posed a while back : https://bitcointalk.org/index.php?topic=3D252960= .0
[3] In theory, an already-relayed transaction shouldn't pass = Core's `filterInventoryKnown`. In practice, if the transaction is annou= nced 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/mail= man/listinfo/bitcoin-dev
--000000000000b9eb5005c4bc9b81--