From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 2BA9AC0001 for ; Thu, 27 May 2021 20:14:30 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 1A69460C31 for ; Thu, 27 May 2021 20:14:30 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: 0.602 X-Spam-Level: X-Spam-Status: No, score=0.602 tagged_above=-999 required=5 tests=[BAYES_50=0.8, 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: smtp3.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5Ios1Y26zRgD for ; Thu, 27 May 2021 20:14:28 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-wr1-x42c.google.com (mail-wr1-x42c.google.com [IPv6:2a00:1450:4864:20::42c]) by smtp3.osuosl.org (Postfix) with ESMTPS id 3BAF960C23 for ; Thu, 27 May 2021 20:14:28 +0000 (UTC) Received: by mail-wr1-x42c.google.com with SMTP id m18so1105879wrv.2 for ; Thu, 27 May 2021 13:14:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=VKJ01t308pj2cyAOnL61Y/AnoGplrX1Mqrmcag8mgL0=; b=WHucsR5VsVBf9dry1U4WW6KhtTOm+4/3jbVMleS0v9IXTVTbJmhQQs7K+7aFFg+Ppm k6xasliVqHZREXHGRCCpW8YSKEEnL13MBKbiPygGyOtUAu5A0wiiTqfCeuP1wrP6roiw Hm3ysSTQujOC0HrfmmX93VpxOvqQGpAUsW5ugpcWkxliYR7DND5MS5qLXZ2yVV21puph e0gLGplMQJfIhUuaTM9E2Rg8Gd8nYErOKjzs80z0+g68xdea03VuYT9AmILVwZFka7MV eYgFYCt9SsW+MB3i/P2GMmxeBCoH8R9sL4vyYySKZKF1/yoK0/Zm64o6wGjVLdeE5Z8q JBWg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=VKJ01t308pj2cyAOnL61Y/AnoGplrX1Mqrmcag8mgL0=; b=gGsvxbLtnDA2xGxZhosniftHK5B5qQWWs7jZAcCMRE2Glr4uYK5TBP71+MGX8VnP8U NumDctVHgR1QP0Ge+KXPapbepjMXKbjcXi7+topE14voFlzlk6Qa8potWjMsu+jRjVyh vn4tg0VRUJwjw4WhGmAZVW2cnlmELObiV9JE22F/Ii6hLls4FHbmP0Ho5iugwWh+aUiM rDLW1d3b5s70Xivs2O9oq4omNit9Xeh4GReDqVByIGY2Ei0F6h3+OT59h+Bk/wculCkG zFC8MDy1QmoeKqiyDiVpiooRYmlaD//skYYYzaSoeYQmfNUJ5u6MG3syy2IShQyAdN9n xRZQ== X-Gm-Message-State: AOAM533F8fo4j85rn+ooox8N/bfVJfRqbMeLIfcGJrrXC+5omZ4Dg7Ze ekHWap4yB0ygGBFBmzmcAcdzmSIPubHVno8U9FmBfJYVyJslFQ== X-Google-Smtp-Source: ABdhPJwujRXRkZ+QZJwXgxtc7a59NJSto7z2jgh6AuC5a3SEyCgGGK3jOMYsF1cUtxl/D9s4VRgIejU1DxxhlCUGS+U= X-Received: by 2002:adf:f54b:: with SMTP id j11mr4910015wrp.376.1622146466005; Thu, 27 May 2021 13:14:26 -0700 (PDT) MIME-Version: 1.0 From: Antoine Riard Date: Thu, 27 May 2021 16:14:13 -0400 Message-ID: To: Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000e1475105c355673a" X-Mailman-Approved-At: Thu, 27 May 2021 21:10:33 +0000 Subject: [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: Thu, 27 May 2021 20:14:30 -0000 --000000000000e1475105c355673a Content-Type: text/plain; charset="UTF-8" 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. --000000000000e1475105c355673a Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi,

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

Thanks to Darosi= or 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 distrusti= ng counterparties raised some security issues. As mempool's chain of un= confirmed transactions are limited in size, if any output is spendable by a= ny contract participant, it can be leveraged as a pinning vector to downgra= de odds of transaction confirmation [0].

That said, contract transac= tions 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 th= em serves as an anchor to attach a CPFP.

## Input-Based

I thi= nk input-based fee-bumping has been less studied as fee-bumping primitive f= or L2s [1]. One variant of input-based fee-bumping usable today is the leve= rage of the SIGHASH_ANYONECANPAY/SIGHASH_SINGLE malleability flags. If the = transaction is the latest stage of the contract, a bumping input can be att= ached just-in-time, thus increasing the feerate of the whole package.
However, as of today, input-based fee-bumping doesn't work to bump fi= rst stages of contract transactions as it's destructive of the txid, an= d as such breaks chain of pre-signed transactions. A first improvement woul= d be the deployment of the SIGHASH_ANYPREVOUT softfork proposal. This new m= alleability flag allows a transaction to be signed without reference to any= specific previous output. That way,=C2=A0 spent transactions can be fee-bu= mped without altering validity of the chain of transactions.

Even as= suming 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 b= e wasted. This edge can be smoothed by broadcasting a preliminary fan-out t= ransaction with a set of outputs providing a range of feerate points for th= e bumped transaction.

This overhead could be smoothed even further i= n the future with more advanced sighash malleability flags like SIGHASH_IOM= AP, 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 i= nputs + 3 outputs.

Input-based (today): If the bumping utxo is offer= ing an adequate feerate point in function of network mempools congestion at= time of broadcast, only 1 input. If a preliminary fan-out transaction to a= djust feerate point must be broadcasted first, 1 input and 2 outputs more m= ust 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 rationali= ty of the participants w.r.t to an unconfirmed spend of the contract utxo a= cross network mempools. Under this assumption, the bumped transaction might= have been replaced by a concurrent state. To guarantee efficiency of the C= PFP the whole chain of transactions should be rebroadcast, perhaps wasting = bandwidth consumption for a still-identical bumped transaction [3]. Rebroad= cast 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 re= maining transactions must be updated and rebroadcast. Rebroadcast footprint= : the whole chain of transactions.

Input-based(SIGHASH_ANYPREVOUT+SI= GHASH_IOMAP): In case of rebroadcast, the fee-bumping is attached to the ro= ot of the chain of transactions but it doesn't break the chain validity= in itself. Assuming a future mempool acceptance logic to authorize in-plac= e substitution, the rest of the chain could be preserved. Rebroadcast footp= rint: the root of the chain of transactions.

## Fee-Bumping Batching=

CPFP: In the context of multi-party protocols, in optimistic scenar= ios, 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 a= nchor output and one bumping input must be consumed per aggregated chain, e= ven if the child transaction fields can be shared. Batching perf: 1 input/1= output per aggregated chain.

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

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

## Fee-Bumping Mempool Fl= exibility

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

Input-based: The root of the chain of transac= tion is the package's oldest ancestor, so package limits don't rest= rain its acceptance and it works whatever the number of contract participan= ts.

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 .

Be= yond that, few points can be highlighted a) future soft forks allow signifi= cant onchain footprint savings, especially in case of batching, b) future p= ackage 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 o= f odds of non-cooperative protocol broadcast/odds of concurrent broadcast/r= ebroadcast 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<= /a>
[2] Already proposed a while back : https://bitcointalk.org/index.php?topic=3D25= 2960.0
[3] In theory, an already-relayed transaction shouldn't p= ass Core's `filterInventoryKnown`. In practice, if the transaction is a= nnounced as part of a package_id, the child might have changed, not the par= ent, leading to a redundant relay of the latter.
--000000000000e1475105c355673a--