MIME-Version: 1.0
References: <CALZpt+FvLb=N5Qygs+dPmh1o9QCwXj8RoznF5n47opOq7CG_0g@mail.gmail.com>
In-Reply-To: <CALZpt+FvLb=N5Qygs+dPmh1o9QCwXj8RoznF5n47opOq7CG_0g@mail.gmail.com>
From: Lloyd Fournier <lloyd.fourn@gmail.com>
Date: Mon, 7 Jun 2021 12:27:36 +1000
Message-ID: <CAH5Bsr2gmqqS1LWuT679vzOEywo=gCdNdOX-Jb9aFFb=EPZcHg@mail.gmail.com>
To: Antoine Riard <antoine.riard@gmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000006b0ee605c423caee"
Subject: Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques :
 Input-Based vs Child-Pay-For-Parent
Precedence: list

--0000000000006b0ee605c423caee
Content-Type: text/plain; charset="UTF-8"

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
>

--0000000000006b0ee605c423caee
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>Hi Antione,</div><div><br></div><div>Thanks for bring=
ing up this important topic. I think there might be another class of soluti=
ons over input based, CPFP and sponsorship. I&#39;ll call them tx mutation =
schemes. The idea is that you can set a key that can increase the fee by lo=
wering a particular output after the tx is signed without invalidating the =
signature.=20
 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 therefor=
e you can sacrifice some of them to increase the fee. This is obviously des=
tructive to txids so child presigned transactions will have to use ANYPREVO=
UT as in your proposal. The advantage is that it does not require keeping e=
xtra inputs around to bump the fee.<br></div><div><br></div><div>So imagine=
 a new opcode OP_CHECKSIG_MUTATED &lt;output index&gt;=20
&lt;publickey&gt; &lt;value&gt;  &lt;signature&gt;.</div><div>This would ch=
eck that &lt;signature&gt; is valid against &lt;publickey&gt; if the curren=
t transaction had the output at &lt;output index&gt; reduced by &lt;value&g=
t;. To make this more efficient, if the public key is one byte: 0x02 it ref=
erences the taproot *external key* (similar to how ANYPREVOUT uses 0x01 to =
refer to internal key[1]).<br></div><div>Now for our protocol we want both =
parties (p1 and p2) to be able to fee bump a commitment transaction. They u=
se 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 a=
dded the following two leaves to their key in the funding output as a backu=
p so that p1 and p2 can unilaterally bump the fee of anything they sign spe=
nding from the funding output:<br></div><div><br></div><div>1. OP_CHECKSIG_=
MUTATED(0, 0x02, &lt;fee-bump-value&gt;,=20

&lt;original-signature&gt;) OP_CHECKSIGADD(p1-fee-bump-key, &lt;p1-fee-bump=
-signature&gt;)=C2=A0
OP_2 OP_NUMEQUALVERIFY

</div><div>2.=20
OP_CHECKSIG_MUTATED(1, 0x02, &lt;fee-bump-value&gt;,=20

&lt;original-signature&gt;) OP_CHECKSIGADD(p2-fee-bump-key, &lt;p2-fee-bump=
-signature&gt;) OP_2 OP_NUMEQUALVERIFY</div><div><br></div><div>where &lt;.=
..&gt; indicates the thing comes from the witness stack.</div><div>So to bu=
mp the fee of the commit tx after it has been signed either party takes the=
 &lt;original-signature&gt; and adds a signature under their fee-bump-key f=
or the new tx and reveals their fee bump leaf. &lt;original-signature&gt; i=
s checked against the old transaction while the fee bumped transaction is c=
hecked against the fee bump key.<br></div><div><br></div><div>
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 hav=
e demonstrated that this class of solutions also exists.<br></div><div><br>=
</div><div>[1] <a href=3D"https://github.com/ajtowns/bips/blob/bip-anyprevo=
ut/bip-0118.mediawiki" target=3D"_blank">https://github.com/ajtowns/bips/bl=
ob/bip-anyprevout/bip-0118.mediawiki</a></div><div><br></div><div>Cheers,</=
div><div><br></div><div>LL<br></div><div><br></div><div><br></div></div><br=
><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Fri, 2=
8 May 2021 at 07:13, Antoine Riard via bitcoin-dev &lt;<a href=3D"mailto:bi=
tcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@lists.li=
nuxfoundation.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote"=
 style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);p=
adding-left:1ex"><div dir=3D"ltr">Hi,<br><br>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.<br><br=
>Thanks to Darosior for reviews, ideas and discussions.<br><br>## Child-Pay=
-For-Parent<br><br>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].<br><br>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.<br><br>## Input-B=
ased<br><br>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.<br><br>However, as of today, input-based fee-bumping doesn&#39;=
t work to bump first stages of contract transactions as it&#39;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.<br><br>Even assuming SIGHASH_ANYPREVOUT, if the first stage contract tra=
nsaction includes multiple outputs (e.g the LN&#39;s commitment tx has mult=
iple HTLC outputs), SIGHASH_SINGLE can&#39;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.<br><br>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.<br><br>## Onchain Footprint<br><br=
>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.<br><br>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.<br><br>Input-based (SIGHASH_ANYPREVOUT+SIGHASH_IOMAP): As long as the =
bumping utxo&#39;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.<br><br>## Tx-Relay Bandwidth Rebroadc=
ast<br><br>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.<br><br>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.<br><br>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&#39;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.<br><br>## Fee=
-Bumping Batching<br><br>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.<br><br>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.<br><br>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.<br><br>## Fee-B=
umping Mempool Flexibility<br><br>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&#39;=
t scale beyond 2 contract participants.<br><br>Input-based: The root of the=
 chain of transaction is the package&#39;s oldest ancestor, so package limi=
ts don&#39;t restrain its acceptance and it works whatever the number of co=
ntract participants.<br><br>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 .<br><br>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.<br><br>Thoughts ?<br><br>Cheers,<b=
r>Antoine<br><br>[0] <a href=3D"https://lists.linuxfoundation.org/pipermail=
/bitcoin-dev/2018-November/016518.html" target=3D"_blank">https://lists.lin=
uxfoundation.org/pipermail/bitcoin-dev/2018-November/016518.html</a><br>[1]=
 Beyond the revault architecture : <a href=3D"https://github.com/revault/pr=
actical-revault/blob/master/revault.pdf" target=3D"_blank">https://github.c=
om/revault/practical-revault/blob/master/revault.pdf</a><br>[2] Already pro=
posed a while back : <a href=3D"https://bitcointalk.org/index.php?topic=3D2=
52960.0" target=3D"_blank">https://bitcointalk.org/index.php?topic=3D252960=
.0</a><br>[3] In theory, an already-relayed transaction shouldn&#39;t pass =
Core&#39;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.<br></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--0000000000006b0ee605c423caee--