path: root/43/8bc1ce2893655f75b2c6032597129554a8b579

Return-Path: <antoine.riard@gmail.com>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138])
 by lists.linuxfoundation.org (Postfix) with ESMTP id BC964C000B
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 14 Jun 2021 16:47:10 +0000 (UTC)
Received: by mail-wr1-x433.google.com with SMTP id a20so15303867wrc.0
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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: <CALZpt+FvLb=N5Qygs+dPmh1o9QCwXj8RoznF5n47opOq7CG_0g@mail.gmail.com>
 <CAH5Bsr2gmqqS1LWuT679vzOEywo=gCdNdOX-Jb9aFFb=EPZcHg@mail.gmail.com>
 <CALZpt+Hj-KdiuQueAhkeTwzJvu5Wo9zdBQ39aZGrSmjJvgbkDQ@mail.gmail.com>
 <CAH5Bsr0V6r3+GsDg=CbDshj=QnpAr+saXftG_pazkWvL=m-W3g@mail.gmail.com>
In-Reply-To: <CAH5Bsr0V6r3+GsDg=CbDshj=QnpAr+saXftG_pazkWvL=m-W3g@mail.gmail.com>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Mon, 14 Jun 2021 12:46:56 -0400
Message-ID: <CALZpt+E09jViG0owWpSWBoG5rjk_=HdMgQisp_1DsBEKBq-D2w@mail.gmail.com>
To: Lloyd Fournier <lloyd.fourn@gmail.com>
Content-Type: multipart/alternative; boundary="000000000000b9eb5005c4bc9b81"
X-Mailman-Approved-At: Mon, 14 Jun 2021 17:04:35 +0000
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
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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 <lloyd.fourn@gmail.com> a
=C3=A9crit :

> 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 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 :
>>
>> <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 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
> <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. Thu=
s
> 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 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 <lloyd.fourn@gmail.com> =
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 <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 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, <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 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

<div dir=3D"ltr">&gt; This makes a lot of sense as it matches the semantics=
 of what we are trying<br>to achieve: allow the owner of an output (whether=
 an individual or group)<br>to reduce that output&#39;s value to pay a high=
er fee.<br><br>Note, I think you&#39;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=
 ?<br><br>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&#39;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.<br>=
<br>Single-party managed fee-bumping reserve doesn&#39;t seem to suffer fro=
m this drawback ?<br><br>Otherwise, I think your new construction OP_PUSH_T=
APROOT_OUTPUT_KEY is correct and solves the O(log(n)) tapleaves issue.<br><=
/div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">L=
e=C2=A0dim. 13 juin 2021 =C3=A0=C2=A001:57, Lloyd Fournier &lt;<a href=3D"m=
ailto:lloyd.fourn@gmail.com">lloyd.fourn@gmail.com</a>&gt; a =C3=A9crit=C2=
=A0:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px=
 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D=
"ltr"><div dir=3D"ltr"><div dir=3D"ltr" class=3D"gmail_attr">On Fri, 11 Jun=
 2021 at 07:45, Antoine Riard &lt;<a href=3D"mailto:antoine.riard@gmail.com=
" target=3D"_blank">antoine.riard@gmail.com</a>&gt; wrote:<br></div></div><=
div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin=
:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"=
><div dir=3D"ltr">Hi Lloyd,<br><br>Thanks for this tx mutation proposal ext=
ending the scope of fee-bumping techniques. IIUC, the &lt;output_index&gt; =
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=
 ?<br></div></blockquote><div><br></div><div>Right.</div><div> <br></div><b=
lockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-le=
ft:1px solid rgb(204,204,204);padding-left:1ex"><div><br>Let&#39;s do a qui=
ck analysis of this scheme.<br>* onchain footprint : one tapleaf per contra=
ct participant, with O(log n) increase of witness size, also one output per=
 contract participant<br></div></blockquote><div>=C2=A0</div><div>Yes but w=
e can fix this (see below).</div><div><br></div><blockquote class=3D"gmail_=
quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,=
204);padding-left:1ex"><div>* tx-relay bandwidth rebroadcast : assuming afo=
rementioned in-place mempool substitution policy, the mutated transaction <=
br></div></blockquote><blockquote class=3D"gmail_quote" style=3D"margin:0px=
 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><di=
v>* batching : fee-bumping value is extract from contract transaction itsel=
f, so O(n) per contract<br>* 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 ?</=
div></blockquote><div>=C2=A0</div><div>Yes. You could use OP_LESSTHAN to ma=
ke sure the value being deducted by the watchtower is not above a threshold=
.</div><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px=
 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><di=
v dir=3D"ltr"><br>Further, I think tx mutation scheme can be achieved in an=
other way, with SIGHASH_ANYAMOUNT. A contract participant tapscript will be=
 the following :<br><br>&lt;contract_key&gt; &lt;finalizing_alice_key&gt;<b=
r><br>Where &lt;contract_signature&gt; 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].<br></div></blockquote><div>=C2=A0</div><div>Yes, that&#39=
;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 &lt;contract_key&gt;=
.</div><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px=
 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><di=
v dir=3D"ltr"><br>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 &quot;real-time&quot; fee-bum=
ping reserve adjustment ?<br></div></blockquote></div><div class=3D"gmail_q=
uote"><br></div><div class=3D"gmail_quote">Hmmm well I was hoping that you =
wouldn&#39;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.<br></div><div class=3D"gmail_quote">Let&#39;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.<br><div>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&#39;s output by doing a switcharoo on the tapleaf after t=
hey see the signature for their counterparty&#39;s tx in the mempool. In yo=
ur example you could fix it by having a different &lt;contract_key&gt; but =
this means we can&#39;t compress &lt;contract_key&gt; by just using the tap=
root internal/external key.<br></div><div><br></div><div>What about this: I=
nstead of party specific &quot;finalizing_alice_key&quot; 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 &lt;output index&gt; 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 &lt;output index&gt; 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.</div><div>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&#39;s value to pay a higher fee.</di=
v><div>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.<br></div><div><br></div><div>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&#39;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.<br></div><div><br></div><div>Cheers, <br></div><div><=
br></div><div>LL<br></div><div><br></div><blockquote class=3D"gmail_quote" =
style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);pa=
dding-left:1ex"><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_=
attr">Le=C2=A0dim. 6 juin 2021 =C3=A0=C2=A022:28, Lloyd Fournier &lt;<a hre=
f=3D"mailto:lloyd.fourn@gmail.com" target=3D"_blank">lloyd.fourn@gmail.com<=
/a>&gt; a =C3=A9crit=C2=A0:<br></div><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);paddin=
g-left:1ex"><div dir=3D"ltr"><div>Hi Antione,</div><div><br></div><div>Than=
ks for bringing up this important topic. I think there might be another cla=
ss of solutions 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 t=
he fee by lowering a particular output after the tx is signed without inval=
idating 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>
</blockquote></div>
</blockquote></div></div>
</blockquote></div>

--000000000000b9eb5005c4bc9b81--