path: root/8b/9ea14f9acd54c10ce800ca3637281d2129d514

Return-Path: <antoine.riard@gmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 2102AC0037;
 Sun, 17 Dec 2023 22:56:55 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id DA97F40873;
 Sun, 17 Dec 2023 22:56:54 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org DA97F40873
Authentication-Results: smtp4.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20230601 header.b=CWI2Ydbh
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
Received: from smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id b7UNRohwaIpk; Sun, 17 Dec 2023 22:56:51 +0000 (UTC)
Received: from mail-io1-xd2b.google.com (mail-io1-xd2b.google.com
 [IPv6:2607:f8b0:4864:20::d2b])
 by smtp4.osuosl.org (Postfix) with ESMTPS id E306840862;
 Sun, 17 Dec 2023 22:56:50 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org E306840862
Received: by mail-io1-xd2b.google.com with SMTP id
 ca18e2360f4ac-7b783ee6d73so119069439f.2; 
 Sun, 17 Dec 2023 14:56:50 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=gmail.com; s=20230601; t=1702853810; x=1703458610;
 darn=lists.linuxfoundation.org; 
 h=cc:to:subject:message-id:date:from:in-reply-to:references
 :mime-version:from:to:cc:subject:date:message-id:reply-to;
 bh=X+RGaoxFOvJyqEmeVr7Yr5iC6CDRhNzsGPs7UxcXfLU=;
 b=CWI2YdbhiGp1GrGH10KF15wL3Ew0Yai6MNt4e+p/m014reLfqqUU4zz7awRkolNDSQ
 uMONedUwJb0zBYGwoGhU14TLnO6ADpxFmkDUQZTrIYE1VeUwxnK77QCYDNp5O1m9J5ws
 ekYhyrfzLStgsVTlwEpRNZFvI1cIFEnwqAQCWx0xY0aBB6ND2yDm6YRP7K9KDav6xwwn
 BNG75AhYzMckdGz04kz++274xn/fWFDjoVhU22+7txs7z2LdW+Ld70huKvjD9+2RxEir
 rV+pAXmAEBH1351FUXhB9oUKbeb4DuSXMfrXQ4TTZgmfs7Vic028wF+hxSC5+dSKtmPq
 //uQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20230601; t=1702853810; x=1703458610;
 h=cc:to:subject:message-id:date:from:in-reply-to:references
 :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id
 :reply-to;
 bh=X+RGaoxFOvJyqEmeVr7Yr5iC6CDRhNzsGPs7UxcXfLU=;
 b=If/+qk8bhWVbV4HemaTfgf36PkTGKj4xfR9jq/XmTVrcL5rCxUl0JfVVnQumNNeuoE
 z7eT4z3ZNyWttVXDLn/ZEa9d/YpbpGLiGn3uyI0Lt+Jv2/NCPQ5Ij4KOEF36z/lUkwc2
 MKLJDk/78Y4GeSvrRlLZ9T4Ec7x5Kl+m08XhddQ5myrjcm20d+LT3P1Ri+Hv4+31xzkX
 ooyZFEbc+p1opOn/G2D9oG9lECrlpqK9KSr11xzmZrpWcfRqoI1WWyzp3hu0eD20kWQ8
 TSY8BGCWRXkL/ijMGp20UvuIrg9WUOheTkRUVj1TJbsieHPfHkY1D53DECze9aQBw7Yy
 PaqA==
X-Gm-Message-State: AOJu0YzTHg8IHAzT+LnPWR+gP3qCagef78LltIfnRZZiOYlkE3Fd7qD1
 FOufkVi3UznoEI69By/YqToFqc7VNYSvMdRIC38=
X-Google-Smtp-Source: AGHT+IHZArY4lO+po2tld0x3EFy3hEnqvKxhBDWP377gEO/Z7hOsdUQglHy1XbzqM8qBXaT5enNoyovGX17mH9Ixouo=
X-Received: by 2002:a05:6602:2d95:b0:7a6:7bbe:5aa0 with SMTP id
 k21-20020a0566022d9500b007a67bbe5aa0mr17912788iow.0.1702853809617; Sun, 17
 Dec 2023 14:56:49 -0800 (PST)
MIME-Version: 1.0
References: <CAD3i26Dux33wF=Ki0ouChseW7dehRuz+QC54bmsm7xzm2YACQQ@mail.gmail.com>
 <CALZpt+GqOeZvkw738GBF0_G4B5fm6noieiddG2QzrbHOG=wTxA@mail.gmail.com>
 <CAD3i26B0UAdAbPdNazrQ0RwtorhMM6NnXHkUXqDd3-+mBDLJEA@mail.gmail.com>
In-Reply-To: <CAD3i26B0UAdAbPdNazrQ0RwtorhMM6NnXHkUXqDd3-+mBDLJEA@mail.gmail.com>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Sun, 17 Dec 2023 22:56:38 +0000
Message-ID: <CALZpt+HDEWQfy-MMUUCjAmR4uqqyyfyEut94wdNs1GjRrmYgxg@mail.gmail.com>
To: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= <johanth@gmail.com>
Content-Type: multipart/alternative; boundary="0000000000006d3f3b060cbc8c92"
X-Mailman-Approved-At: Mon, 18 Dec 2023 00:35:49 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
 "lightning-dev\\\\@lists.linuxfoundation.org"
 <lightning-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] HTLC output aggregation as a mitigation for tx
 recycling, jamming, and on-chain efficiency (covenants)
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: Sun, 17 Dec 2023 22:56:55 -0000

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

Hi Johan,

> Is this a concern though, if we assume there's no revoked state that
> can be broadcast (Eltoo)? Could you share an example of how this would
> be played out by an attacker?

Sure, let's assume no revoked state can be broadcast (Eltoo).

My understanding of the new covenant mechanism is the aggregation or
collapsing of all HTLC outputs in one or at least 2 outputs (offered /
received).
Any spend of an aggregated HTLC "payout" should satisfy the script
locking condition by presenting a preimage and a signature.
An offerd aggregated HTLC output might collapse a M number of HTLC
"payout", where M is still limited by the max standard transaction
relay, among other things.

The offered-to counterparty can claim any subset N of the aggregation
M by presenting the list of signatures and preimages (How they're
feeded to the spent script is a covenant implementation detail).
However, there is no guarantee that the offered-to counterparty reveal
"all" the preimages she is awarded off. Non-spent HTLC outputs are
clawback to a remainder subset of M, M'.

I think this partial reveal of HTLC payout preimages still opens the
door to replacement cycling attacks.

Let's say you have 5 offered HTLC "payouts" between Alice and Bob
aggregated in a single output, 4 of value 0.1 BTC and 1 of value 1
BTC. All expire at timelock T.
At T, Alice broadcasts an aggregated HTLC-timeout spend for the 5 HTLC
with 0.0.1 BTC on-chain fee.

Bob can craft a HTLC-preimage spend of the single offered output
spending one of 0.1 BTC HTLC payout (and revealing its preimage) while
burning all the value as fee. This replaces out Alice's honest
HTLC-timeout out of network mempools, are they're concurrent spend.
Bob can repeat this trick as long as there is HTLC "payout" remaining
in the offered set, until he's being able to do a HTLC off-chain
double-spend of the 1 BTC HTLC "payout".

This stealing gain of the 1 BTC HTLC "payout" covers what has been
burned as miners fees to replace cycle out Alice's sequence of honest
HTLC-timeout.

And it should be noted that Bob might benefit from network mempools
congestion delaying the confirmation of his malicious low-value
high-fee HTLC-preimage transactions.

> I'm not sure what you mean here, could you elaborate?

See https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-December/0=
22191.html
and my answer there.
I think "self-sustained" fees is one only part of the solution, the
other part being the sliding delay of the HTLC timelock based on block
feerate.
Otherwise, a replacement cycling attacker can always benefit from
network mempools congestion spontaneously pushing out a malicious
cycling transaction out of block templates.

> That sounds possible, but how would you deal with the exponential
> blowup in the number of combinations?

In a taproot-world, "swallow the bullet" in terms of witness size
growth in case of non-cooperative closure.
I think this is where introducing an accumulator at the Script level
to efficiently test partial set membership would make sense.
Note, exponential blowup is an issue for mass non-coordinated
withdrawals of a payment pool too.

Best,
Antoine


Le lun. 11 d=C3=A9c. 2023 =C3=A0 09:17, Johan Tor=C3=A5s Halseth <johanth@g=
mail.com> a
=C3=A9crit :

> Hi, Antoine.
>
> > The attack works on legacy channels if the holder (or local) commitment
> transaction confirms first, the second-stage HTLC claim transaction is
> fully malleable by the counterparty.
>
> Yes, correct. Thanks for pointing that out!
>
> > I think one of the weaknesses of this approach is the level of
> malleability still left to the counterparty, where one might burn in mine=
rs
> fees all the HTLC accumulated value promised to the counterparty, and for
> which the preimages have been revealed off-chain.
>
> Is this a concern though, if we assume there's no revoked state that
> can be broadcast (Eltoo)? Could you share an example of how this would
> be played out by an attacker?
>
> > I wonder if a more safe approach, eliminating a lot of competing
> interests style of mempool games, wouldn't be to segregate HTLC claims in
> two separate outputs, with full replication of the HTLC lockscripts in bo=
th
> outputs, and let a covenant accepts or rejects aggregated claims with
> satisfying witness and chain state condition for time lock.
>
> I'm not sure what you mean here, could you elaborate?
>
> > I wonder if in a PTLC world, you can generate an aggregate curve point
> for all the sub combinations of scalar plausible. Unrevealed curve points
> in a taproot branch are cheap. It might claim an offered HTLC near-consta=
nt
> size too.
>
> That sounds possible, but how would you deal with the exponential
> blowup in the number of combinations?
>
> Cheers,
> Johan
>
>
> On Tue, Nov 21, 2023 at 3:39=E2=80=AFAM Antoine Riard <antoine.riard@gmai=
l.com>
> wrote:
> >
> > Hi Johan,
> >
> > Few comments.
> >
> > ## Transaction recycling
> > The transaction recycling attack is made possible by the change made
> > to HTLC second level transactions for the anchor channel type[8];
> > making it possible to add fees to the transaction by adding inputs
> > without violating the signature. For the legacy channel type this
> > attack was not possible, as all fees were taken from the HTLC outputs
> > themselves, and had to be agreed upon by channel counterparties during
> > signing (of course this has its own problems, which is why we wanted
> > to change it).
> >
> > The attack works on legacy channels if the holder (or local) commitment
> transaction confirms first, the second-stage HTLC claim transaction is
> fully malleable by the counterparty.
> >
> > See
> https://github.com/lightning/bolts/blob/master/03-transactions.md#offered=
-htlc-outputs
> (only remote_htlcpubkey required)
> >
> > Note a replacement cycling attack works in a future package-relay world
> too.
> >
> > See test:
> https://github.com/ariard/bitcoin/commit/19d61fa8cf22a5050b51c4005603f43d=
72f1efcf
> >
> > > The idea of HTLC output aggregation is to collapse all HTLC outputs o=
n
> > > the commitment to a single one. This has many benefits (that I=E2=80=
=99ll get
> > > to), one of them being the possibility to let the spender claim the
> > > portion of the output that they=E2=80=99re right to, deciding how muc=
h should
> > > go to fees. Note that this requires a covenant to be possible.
> >
> > Another advantage of HTLC output aggregation is the reduction of
> fee-bumping reserves requirements on channel counterparties, as
> second-stage HTLC transactions have common fields (nVersion, nLocktime,
> ...) *could* be shared.
> >
> > > ## A single HTLC output
> > > Today, every forwarded HTLC results in an output that needs to be
> > > manifested on the commitment transaction in order to claw back money
> > > in case of an uncooperative channel counterparty. This puts a limit o=
n
> > > the number of active HTLCs (in order for the commitment transaction t=
o
> > > not become too large) which makes it possible to jam the channel with
> > > small amounts of capital [1]. It also turns out that having this limi=
t
> > > be large makes it expensive and complicated to sweep the outputs
> > > efficiently [2].
> >
> > > Instead of having new HTLC outputs manifest for each active
> > > forwarding, with covenants on the base layer one could create a singl=
e
> > > aggregated output on the commitment. The output amount being the sum
> > > of the active HTLCs (offered and received), alternatively one output
> > > for received and one for offered. When spending this output, you woul=
d
> > > only be entitled to the fraction of the amount corresponding to the
> > > HTLCs you know the preimage for (received), or that has timed out
> > > (offered).
> >
> > > ## Impacts to transaction recycling
> > > Depending on the capabilities of the covenant available (e.g.
> > > restricting the number of inputs to the transaction) the transaction
> > > spending the aggregated HTLC output can be made self sustained: the
> > > spender will be able to claim what is theirs (preimage or timeout) an=
d
> > > send it to whatever output they want, or to fees. The remainder will
> > > go back into a covenant restricted output with the leftover HTLCs.
> > > Note that this most likely requires Eltoo in order to not enable fee
> > > siphoning[7].
> >
> > I think one of the weaknesses of this approach is the level of
> malleability still left to the counterparty, where one might burn in mine=
rs
> fees all the HTLC accumulated value promised to the counterparty, and for
> which the preimages have been revealed off-chain.
> >
> > I wonder if a more safe approach, eliminating a lot of competing
> interests style of mempool games, wouldn't be to segregate HTLC claims in
> two separate outputs, with full replication of the HTLC lockscripts in bo=
th
> outputs, and let a covenant accepts or rejects aggregated claims with
> satisfying witness and chain state condition for time lock.
> >
> > > ## Impacts to slot jamming
> > > With the aggregated output being a reality, it changes the nature of
> > > =E2=80=9Cslot jamming=E2=80=9D [1] significantly. While channel capac=
ity must still be
> > > reserved for in-flight HTLCs, one no longer needs to allocate a
> > > commitment output for each up to some hardcoded limit.
> >
> > > In today=E2=80=99s protocol this limit is 483, and I believe most
> > > implementations default to an even lower limit. This leads to channel
> > > jamming being quite inexpensive, as one can quickly fill a channel
> > > with small HTLCs, without needing a significant amount of capital to
> > > do so.
> >
> > > The origins of the 483 slot limits is the worst case commitment size
> > > before getting into unstandard territory [3]. With an aggregated
> > > output this would no longer be the case, as adding HTLCs would no
> > > longer affect commitment size. Instead, the full on-chain footprint o=
f
> > > an HTLC would be deferred until claim time.
> >
> > > Does this mean one could lift, or even remove the limit for number of
> > > active HTLCs? Unfortunately, the obvious approach doesn=E2=80=99t see=
m to get
> > > rid of the problem entirely, but mitigates it quite a bit.
> >
> > Yes, protocol limit of 483 is a long-term limit on the payment
> throughput of the LN, though as an upper bound we have the dust limits an=
d
> mempool fluctuations rendering irrelevant the claim of such aggregated du=
st
> outputs. Aggregated claims might give a more dynamic margin of what is a
> tangible and trust-minimized HTLC payment.
> >
> > > ### Slot jamming attack scenario
> > > Consider the scenario where an attacker sends a large number of
> > > non-dust* HTLCs across a channel, and the channel parties enforce no
> > > limit on the number of active HTLCs.
> >
> > > The number of payments would not affect the size of the commitment
> > > transaction at all, only the size of the witness that must be
> > > presented when claiming or timing out the HTLCs. This means that ther=
e
> > > is still a point at which chain fees get high enough for the HTLC to
> > > be uneconomical to claim. This is no different than in today=E2=80=99=
s spec,
> > > and such HTLCs will just be stranded on-chain until chain fees
> > > decrease, at which point there is a race between the success and
> > > timeout spends.
> >
> > > There seems to be no way around this; if you want to claim an HTLC
> > > on-chain, you need to put the preimage on-chain. And when the HTLC
> > > first reaches you, you have no way of predicting the future chain fee=
.
> > > With a large number of uneconomical HTLCs in play, the total BTC
> > > exposure could still be very large, so you might want to limit this
> > > somewhat.
> >
> > > * Note that as long as the sum of HTLCs exceeds the dust limit, one
> > > could manifest the output on the transaction.
> >
> > Unless we introduce sliding windows during which the claim periods of a=
n
> HTLC can be claimed and freeze accordingly the HTLC-timeout path.
> >
> > See: https://fc22.ifca.ai/preproceedings/119.pdf
> >
> > Bad news: you will need off-chain consensus on the feerate threshold at
> which the sliding windows kick-out among all the routing nodes
> participating in the HTLC payment path.
> >
> > > ## The good news
> > > With an aggregated HTLC output, the number of HTLCs would no longer
> > > impact the commitment transaction size while the channel is open and
> > > operational.
> >
> > > The marginal cost of claiming an HTLC with a preimage on-chain would
> > > be much lower; no new inputs or outputs, only a linear increase in th=
e
> > > witness size. With a covenant primitive available, the extra footprin=
t
> > > of the timeout and success transactions would no longer exist.
> >
> > > Claiming timed out HTLCs could still be made close to constant size
> > > (no preimage to present), so no additional on-chain cost with more
> > > HTLCs.
> >
> > I wonder if in a PTLC world, you can generate an aggregate curve point
> for all the sub combinations of scalar plausible. Unrevealed curve points
> in a taproot branch are cheap. It might claim an offered HTLC near-consta=
nt
> size too.
> >
> > > ## The bad news
> > > The most obvious problem is that we would need a new covenant
> > > primitive on L1 (see below). However, I think it could be beneficial
> > > to start exploring these ideas now in order to guide the L1 effort
> > > towards something we could utilize to its fullest on L2.
> >
> > > As mentioned, even with a functioning covenant, we don=E2=80=99t esca=
pe the
> > > fact that a preimage needs to go on-chain, pricing out HTLCs at
> > > certain fee rates. This is analogous to the dust exposure problem
> > > discussed in [6], and makes some sort of limit still required.
> >
> > Ideally such covenant mechanisms would generalize to the withdrawal
> phase of payment pools, where dozens or hundreds of participants wish to
> confirm their non-competing withdrawal transactions concurrently. While
> unlocking preimage or scalar can be aggregated in a single witness, there
> will still be a need to verify that each withdrawal output associated wit=
h
> an unlocking secret is present in the transaction.
> >
> > Maybe few other L2s are answering this N-inputs-to-M-outputs pattern
> with advanced locking scripts conditions to satisfy.
> >
> > > ### Open question
> > > With PTLCs, could one create a compact proof showing that you know th=
e
> > > preimage for m-of-n of the satoshis in the output? (some sort of
> > > threshold signature).
> >
> > > If we could do this we would be able to remove the slot jamming issue
> > > entirely; any number of active PTLCs would not change the on-chain
> > > cost of claiming them.
> >
> > See comments above, I think there is a plausible scheme here you just
> generate all the point combinations possible, and only reveal the one you
> need at broadcast.
> >
> > > ## Covenant primitives
> > > A recursive covenant is needed to achieve this. Something like OP_CTV
> > > and OP_APO seems insufficient, since the number of ways the set of
> > > HTLCs could be claimed would cause combinatorial blowup in the number
> > > of possible spending transactions.
> >
> > > Personally, I=E2=80=99ve found the simple yet powerful properties of
> > > OP_CHECKCONTRACTVERIFY [4] together with OP_CAT and amount inspection
> > > particularly interesting for the use case, but I=E2=80=99m certain ma=
ny of the
> > > other proposals could achieve the same thing. More direct inspection
> > > like you get from a proposal like OP_TX[9] would also most likely hav=
e
> > > the building blocks needed.
> >
> > As pointed out during the CTV drama and payment pool public discussion
> years ago, what would be very useful to tie-break among all covenant
> constructions would be an efficiency simulation framework. Even if the sa=
me
> semantic can be achieved independently by multiple covenants, they
> certainly do not have the same performance trade-offs (e.g average and
> worst-case witness size).
> >
> > I don't think the blind approach of activating many complex covenants a=
t
> the same time is conservative enough in Bitcoin, where one might design
> "malicious" L2 contracts, of which the game-theory is not fully understoo=
d.
> >
> > See e.g https://blog.bitmex.com/txwithhold-smart-contracts/
> >
> > > ### Proof-of-concept
> > > I=E2=80=99ve implemented a rough demo** of spending an HTLC output th=
at pays
> > > to a script with OP_CHECKCONTRACTVERIFY to achieve this [5]. The idea
> > > is to commit to all active HTLCs in a merkle tree, and have the
> > > spender provide merkle proofs for the HTLCs to claim, claiming the su=
m
> > > into a new output. The remainder goes back into a new output with the
> > > claimed HTLCs removed from the merkle tree.
> >
> > > An interesting trick one can do when creating the merkle tree, is
> > > sorting the HTLCs by expiry. This means that one in the timeout case
> > > claim a subtree of HTLCs using a single merkle proof (and RBF this
> > > batched timeout claim as more and more HTLCs expire) reducing the
> > > timeout case to constant size witness (or rather logarithmic in the
> > > total number of HTLCs).
> >
> > > **Consider it an experiment, as it is missing a lot before it could b=
e
> > > usable in any real commitment setting.
> >
> > I think this is an interesting question if more advanced cryptosystems
> based on assumptions other than the DL problem could constitute a factor =
of
> scalability of LN payment throughput by orders of magnitude, by decouplin=
g
> number of off-chain payments from the growth of the on-chain witness size
> need to claim them, without lowering in security as with trimmed HTLC due
> to dust limits.
> >
> > Best,
> > Antoine
> >
> > Le jeu. 26 oct. 2023 =C3=A0 20:28, Johan Tor=C3=A5s Halseth via bitcoin=
-dev <
> bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit :
> >>
> >> Hi all,
> >>
> >> After the transaction recycling has spurred some discussion the last
> >> week or so, I figured it could be worth sharing some research I=E2=80=
=99ve
> >> done into HTLC output aggregation, as it could be relevant for how to
> >> avoid this problem in a future channel type.
> >>
> >> TLDR; With the right covenant we can create HTLC outputs that are much
> >> more chain efficient, not prone to tx recycling and harder to jam.
> >>
> >> ## Transaction recycling
> >> The transaction recycling attack is made possible by the change made
> >> to HTLC second level transactions for the anchor channel type[8];
> >> making it possible to add fees to the transaction by adding inputs
> >> without violating the signature. For the legacy channel type this
> >> attack was not possible, as all fees were taken from the HTLC outputs
> >> themselves, and had to be agreed upon by channel counterparties during
> >> signing (of course this has its own problems, which is why we wanted
> >> to change it).
> >>
> >> The idea of HTLC output aggregation is to collapse all HTLC outputs on
> >> the commitment to a single one. This has many benefits (that I=E2=80=
=99ll get
> >> to), one of them being the possibility to let the spender claim the
> >> portion of the output that they=E2=80=99re right to, deciding how much=
 should
> >> go to fees. Note that this requires a covenant to be possible.
> >>
> >> ## A single HTLC output
> >> Today, every forwarded HTLC results in an output that needs to be
> >> manifested on the commitment transaction in order to claw back money
> >> in case of an uncooperative channel counterparty. This puts a limit on
> >> the number of active HTLCs (in order for the commitment transaction to
> >> not become too large) which makes it possible to jam the channel with
> >> small amounts of capital [1]. It also turns out that having this limit
> >> be large makes it expensive and complicated to sweep the outputs
> >> efficiently [2].
> >>
> >> Instead of having new HTLC outputs manifest for each active
> >> forwarding, with covenants on the base layer one could create a single
> >> aggregated output on the commitment. The output amount being the sum
> >> of the active HTLCs (offered and received), alternatively one output
> >> for received and one for offered. When spending this output, you would
> >> only be entitled to the fraction of the amount corresponding to the
> >> HTLCs you know the preimage for (received), or that has timed out
> >> (offered).
> >>
> >> ## Impacts to transaction recycling
> >> Depending on the capabilities of the covenant available (e.g.
> >> restricting the number of inputs to the transaction) the transaction
> >> spending the aggregated HTLC output can be made self sustained: the
> >> spender will be able to claim what is theirs (preimage or timeout) and
> >> send it to whatever output they want, or to fees. The remainder will
> >> go back into a covenant restricted output with the leftover HTLCs.
> >> Note that this most likely requires Eltoo in order to not enable fee
> >> siphoning[7].
> >>
> >> ## Impacts to slot jamming
> >> With the aggregated output being a reality, it changes the nature of
> >> =E2=80=9Cslot jamming=E2=80=9D [1] significantly. While channel capaci=
ty must still be
> >> reserved for in-flight HTLCs, one no longer needs to allocate a
> >> commitment output for each up to some hardcoded limit.
> >>
> >> In today=E2=80=99s protocol this limit is 483, and I believe most
> >> implementations default to an even lower limit. This leads to channel
> >> jamming being quite inexpensive, as one can quickly fill a channel
> >> with small HTLCs, without needing a significant amount of capital to
> >> do so.
> >>
> >> The origins of the 483 slot limits is the worst case commitment size
> >> before getting into unstandard territory [3]. With an aggregated
> >> output this would no longer be the case, as adding HTLCs would no
> >> longer affect commitment size. Instead, the full on-chain footprint of
> >> an HTLC would be deferred until claim time.
> >>
> >> Does this mean one could lift, or even remove the limit for number of
> >> active HTLCs? Unfortunately, the obvious approach doesn=E2=80=99t seem=
 to get
> >> rid of the problem entirely, but mitigates it quite a bit.
> >>
> >> ### Slot jamming attack scenario
> >> Consider the scenario where an attacker sends a large number of
> >> non-dust* HTLCs across a channel, and the channel parties enforce no
> >> limit on the number of active HTLCs.
> >>
> >> The number of payments would not affect the size of the commitment
> >> transaction at all, only the size of the witness that must be
> >> presented when claiming or timing out the HTLCs. This means that there
> >> is still a point at which chain fees get high enough for the HTLC to
> >> be uneconomical to claim. This is no different than in today=E2=80=99s=
 spec,
> >> and such HTLCs will just be stranded on-chain until chain fees
> >> decrease, at which point there is a race between the success and
> >> timeout spends.
> >>
> >> There seems to be no way around this; if you want to claim an HTLC
> >> on-chain, you need to put the preimage on-chain. And when the HTLC
> >> first reaches you, you have no way of predicting the future chain fee.
> >> With a large number of uneconomical HTLCs in play, the total BTC
> >> exposure could still be very large, so you might want to limit this
> >> somewhat.
> >>
> >> * Note that as long as the sum of HTLCs exceeds the dust limit, one
> >> could manifest the output on the transaction.
> >>
> >> ## The good news
> >> With an aggregated HTLC output, the number of HTLCs would no longer
> >> impact the commitment transaction size while the channel is open and
> >> operational.
> >>
> >> The marginal cost of claiming an HTLC with a preimage on-chain would
> >> be much lower; no new inputs or outputs, only a linear increase in the
> >> witness size. With a covenant primitive available, the extra footprint
> >> of the timeout and success transactions would no longer exist.
> >>
> >> Claiming timed out HTLCs could still be made close to constant size
> >> (no preimage to present), so no additional on-chain cost with more
> >> HTLCs.
> >>
> >> ## The bad news
> >> The most obvious problem is that we would need a new covenant
> >> primitive on L1 (see below). However, I think it could be beneficial
> >> to start exploring these ideas now in order to guide the L1 effort
> >> towards something we could utilize to its fullest on L2.
> >>
> >> As mentioned, even with a functioning covenant, we don=E2=80=99t escap=
e the
> >> fact that a preimage needs to go on-chain, pricing out HTLCs at
> >> certain fee rates. This is analogous to the dust exposure problem
> >> discussed in [6], and makes some sort of limit still required.
> >>
> >> ### Open question
> >> With PTLCs, could one create a compact proof showing that you know the
> >> preimage for m-of-n of the satoshis in the output? (some sort of
> >> threshold signature).
> >>
> >> If we could do this we would be able to remove the slot jamming issue
> >> entirely; any number of active PTLCs would not change the on-chain
> >> cost of claiming them.
> >>
> >> ## Covenant primitives
> >> A recursive covenant is needed to achieve this. Something like OP_CTV
> >> and OP_APO seems insufficient, since the number of ways the set of
> >> HTLCs could be claimed would cause combinatorial blowup in the number
> >> of possible spending transactions.
> >>
> >> Personally, I=E2=80=99ve found the simple yet powerful properties of
> >> OP_CHECKCONTRACTVERIFY [4] together with OP_CAT and amount inspection
> >> particularly interesting for the use case, but I=E2=80=99m certain man=
y of the
> >> other proposals could achieve the same thing. More direct inspection
> >> like you get from a proposal like OP_TX[9] would also most likely have
> >> the building blocks needed.
> >>
> >> ### Proof-of-concept
> >> I=E2=80=99ve implemented a rough demo** of spending an HTLC output tha=
t pays
> >> to a script with OP_CHECKCONTRACTVERIFY to achieve this [5]. The idea
> >> is to commit to all active HTLCs in a merkle tree, and have the
> >> spender provide merkle proofs for the HTLCs to claim, claiming the sum
> >> into a new output. The remainder goes back into a new output with the
> >> claimed HTLCs removed from the merkle tree.
> >>
> >> An interesting trick one can do when creating the merkle tree, is
> >> sorting the HTLCs by expiry. This means that one in the timeout case
> >> claim a subtree of HTLCs using a single merkle proof (and RBF this
> >> batched timeout claim as more and more HTLCs expire) reducing the
> >> timeout case to constant size witness (or rather logarithmic in the
> >> total number of HTLCs).
> >>
> >> **Consider it an experiment, as it is missing a lot before it could be
> >> usable in any real commitment setting.
> >>
> >>
> >> [1]
> https://bitcoinops.org/en/topics/channel-jamming-attacks/#htlc-jamming-at=
tack
> >> [2] https://github.com/lightning/bolts/issues/845
> >> [3]
> https://github.com/lightning/bolts/blob/aad959a297ff66946effb165518143be1=
5777dd6/02-peer-protocol.md#rationale-7
> >> [4]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-November/021=
182.html
> >> [5]
> https://github.com/halseth/tapsim/blob/b07f29804cf32dce0168ab5bb40558cbb1=
8f2e76/examples/matt/claimpool/script.txt
> >> [6]
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-October/00=
3257.html
> >> [7]
> https://github.com/lightning/bolts/issues/845#issuecomment-937736734
> >> [8]
> https://github.com/lightning/bolts/blob/8a64c6a1cef979b3f0cecb00ba7a48c2d=
28b3588/03-transactions.md?plain=3D1#L333
> >> [9]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-May/020450.h=
tml
> >> _______________________________________________
> >> bitcoin-dev mailing list
> >> bitcoin-dev@lists.linuxfoundation.org
> >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr"><pre style=3D"color:rgb(0,0,0);white-space:pre-wrap"><font=
 face=3D"arial, sans-serif">Hi Johan,

&gt; Is this a concern though, if we assume there&#39;s no revoked state th=
at
&gt; can be broadcast (Eltoo)? Could you share an example of how this would
&gt; be played out by an attacker?

Sure, let&#39;s assume no revoked state can be broadcast (Eltoo).

My understanding of the new covenant mechanism is the aggregation or collap=
sing of all HTLC outputs in one or at least 2 outputs (offered / received).
Any spend of an aggregated HTLC &quot;payout&quot; should satisfy the scrip=
t locking condition by presenting a preimage and a signature.
An offerd aggregated HTLC output might collapse a M number of HTLC &quot;pa=
yout&quot;, where M is still limited by the max standard transaction relay,=
 among other things.

The offered-to counterparty can claim any subset N of the aggregation M by =
presenting the list of signatures and preimages (How they&#39;re feeded to =
the spent script is a covenant implementation detail). However, there is no=
 guarantee that the offered-to counterparty reveal &quot;all&quot; the prei=
mages she is awarded off. Non-spent HTLC outputs are clawback to a remainde=
r subset of M, M&#39;.

I think this partial reveal of HTLC payout preimages still opens the door t=
o replacement cycling attacks.

Let&#39;s say you have 5 offered HTLC &quot;payouts&quot; between Alice and=
 Bob aggregated in a single output, 4 of value 0.1 BTC and 1 of value 1 BTC=
. All expire at timelock T.
At T, Alice broadcasts an aggregated HTLC-timeout spend for the 5 HTLC with=
 0.0.1 BTC on-chain fee.

Bob can craft a HTLC-preimage spend of the single offered output spending o=
ne of 0.1 BTC HTLC payout (and revealing its preimage) while burning all th=
e value as fee. This replaces out Alice&#39;s honest HTLC-timeout out of ne=
twork mempools, are they&#39;re concurrent spend.=C2=A0</font><span style=
=3D"font-family:arial,sans-serif">Bob can repeat this trick as long as ther=
e is HTLC &quot;payout&quot; remaining in the offered set, until </span>he&=
#39;s being able<span style=3D"font-family:arial,sans-serif"> to do a HTLC =
off-chain double-spend of the 1 BTC HTLC &quot;payout&quot;.</span></pre><p=
re style=3D"color:rgb(0,0,0);white-space:pre-wrap"><font face=3D"arial, san=
s-serif">This stealing gain of the 1 BTC HTLC &quot;payout&quot; covers wha=
t has been burned as miners fees to replace cycle out Alice&#39;s sequence =
of honest HTLC-timeout.</font></pre><pre style=3D"color:rgb(0,0,0);white-sp=
ace:pre-wrap"><font face=3D"arial, sans-serif">And it should be noted that =
Bob might benefit from network mempools congestion delaying the confirmatio=
n of his malicious low-value high-fee HTLC-preimage transactions.

&gt; I&#39;m not sure what you mean here, could you elaborate?

See <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023=
-December/022191.html">https://lists.linuxfoundation.org/pipermail/bitcoin-=
dev/2023-December/022191.html</a> and my answer there.
I think &quot;self-sustained&quot; fees is one only part of the solution, t=
he other part being the sliding delay of the HTLC timelock based on block f=
eerate.
Otherwise, a replacement cycling attacker can always benefit from network m=
empools congestion spontaneously pushing out a malicious cycling transactio=
n out of block templates.

&gt; That sounds possible, but how would you deal with the exponential
&gt; blowup in the number of combinations?

In a taproot-world, &quot;swallow the bullet&quot; in terms of witness size=
 growth in case of non-cooperative closure.
I think this is where introducing an accumulator at the Script level to eff=
iciently test partial set membership would make sense.
Note, exponential blowup is an issue for mass non-coordinated withdrawals o=
f a payment pool too.

Best,
Antoine</font></pre></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" c=
lass=3D"gmail_attr">Le=C2=A0lun. 11 d=C3=A9c. 2023 =C3=A0=C2=A009:17, Johan=
 Tor=C3=A5s Halseth &lt;<a href=3D"mailto:johanth@gmail.com">johanth@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-width:1px;border-left-style:s=
olid;border-left-color:rgb(204,204,204);padding-left:1ex">Hi, Antoine.<br>
<br>
&gt; The attack works on legacy channels if the holder (or local) commitmen=
t transaction confirms first, the second-stage HTLC claim transaction is fu=
lly malleable by the counterparty.<br>
<br>
Yes, correct. Thanks for pointing that out!<br>
<br>
&gt; I think one of the weaknesses of this approach is the level of malleab=
ility still left to the counterparty, where one might burn in miners fees a=
ll the HTLC accumulated value promised to the counterparty, and for which t=
he preimages have been revealed off-chain.<br>
<br>
Is this a concern though, if we assume there&#39;s no revoked state that<br=
>
can be broadcast (Eltoo)? Could you share an example of how this would<br>
be played out by an attacker?<br>
<br>
&gt; I wonder if a more safe approach, eliminating a lot of competing inter=
ests style of mempool games, wouldn&#39;t be to segregate HTLC claims in tw=
o separate outputs, with full replication of the HTLC lockscripts in both o=
utputs, and let a covenant accepts or rejects aggregated claims with satisf=
ying witness and chain state condition for time lock.<br>
<br>
I&#39;m not sure what you mean here, could you elaborate?<br>
<br>
&gt; I wonder if in a PTLC world, you can generate an aggregate curve point=
 for all the sub combinations of scalar plausible. Unrevealed curve points =
in a taproot branch are cheap. It might claim an offered HTLC near-constant=
 size too.<br>
<br>
That sounds possible, but how would you deal with the exponential<br>
blowup in the number of combinations?<br>
<br>
Cheers,<br>
Johan<br>
<br>
<br>
On Tue, Nov 21, 2023 at 3:39=E2=80=AFAM Antoine Riard &lt;<a href=3D"mailto=
:antoine.riard@gmail.com" target=3D"_blank">antoine.riard@gmail.com</a>&gt;=
 wrote:<br>
&gt;<br>
&gt; Hi Johan,<br>
&gt;<br>
&gt; Few comments.<br>
&gt;<br>
&gt; ## Transaction recycling<br>
&gt; The transaction recycling attack is made possible by the change made<b=
r>
&gt; to HTLC second level transactions for the anchor channel type[8];<br>
&gt; making it possible to add fees to the transaction by adding inputs<br>
&gt; without violating the signature. For the legacy channel type this<br>
&gt; attack was not possible, as all fees were taken from the HTLC outputs<=
br>
&gt; themselves, and had to be agreed upon by channel counterparties during=
<br>
&gt; signing (of course this has its own problems, which is why we wanted<b=
r>
&gt; to change it).<br>
&gt;<br>
&gt; The attack works on legacy channels if the holder (or local) commitmen=
t transaction confirms first, the second-stage HTLC claim transaction is fu=
lly malleable by the counterparty.<br>
&gt;<br>
&gt; See <a href=3D"https://github.com/lightning/bolts/blob/master/03-trans=
actions.md#offered-htlc-outputs" rel=3D"noreferrer" target=3D"_blank">https=
://github.com/lightning/bolts/blob/master/03-transactions.md#offered-htlc-o=
utputs</a> (only remote_htlcpubkey required)<br>
&gt;<br>
&gt; Note a replacement cycling attack works in a future package-relay worl=
d too.<br>
&gt;<br>
&gt; See test: <a href=3D"https://github.com/ariard/bitcoin/commit/19d61fa8=
cf22a5050b51c4005603f43d72f1efcf" rel=3D"noreferrer" target=3D"_blank">http=
s://github.com/ariard/bitcoin/commit/19d61fa8cf22a5050b51c4005603f43d72f1ef=
cf</a><br>
&gt;<br>
&gt; &gt; The idea of HTLC output aggregation is to collapse all HTLC outpu=
ts on<br>
&gt; &gt; the commitment to a single one. This has many benefits (that I=E2=
=80=99ll get<br>
&gt; &gt; to), one of them being the possibility to let the spender claim t=
he<br>
&gt; &gt; portion of the output that they=E2=80=99re right to, deciding how=
 much should<br>
&gt; &gt; go to fees. Note that this requires a covenant to be possible.<br=
>
&gt;<br>
&gt; Another advantage of HTLC output aggregation is the reduction of fee-b=
umping reserves requirements on channel counterparties, as second-stage HTL=
C transactions have common fields (nVersion, nLocktime, ...) *could* be sha=
red.<br>
&gt;<br>
&gt; &gt; ## A single HTLC output<br>
&gt; &gt; Today, every forwarded HTLC results in an output that needs to be=
<br>
&gt; &gt; manifested on the commitment transaction in order to claw back mo=
ney<br>
&gt; &gt; in case of an uncooperative channel counterparty. This puts a lim=
it on<br>
&gt; &gt; the number of active HTLCs (in order for the commitment transacti=
on to<br>
&gt; &gt; not become too large) which makes it possible to jam the channel =
with<br>
&gt; &gt; small amounts of capital [1]. It also turns out that having this =
limit<br>
&gt; &gt; be large makes it expensive and complicated to sweep the outputs<=
br>
&gt; &gt; efficiently [2].<br>
&gt;<br>
&gt; &gt; Instead of having new HTLC outputs manifest for each active<br>
&gt; &gt; forwarding, with covenants on the base layer one could create a s=
ingle<br>
&gt; &gt; aggregated output on the commitment. The output amount being the =
sum<br>
&gt; &gt; of the active HTLCs (offered and received), alternatively one out=
put<br>
&gt; &gt; for received and one for offered. When spending this output, you =
would<br>
&gt; &gt; only be entitled to the fraction of the amount corresponding to t=
he<br>
&gt; &gt; HTLCs you know the preimage for (received), or that has timed out=
<br>
&gt; &gt; (offered).<br>
&gt;<br>
&gt; &gt; ## Impacts to transaction recycling<br>
&gt; &gt; Depending on the capabilities of the covenant available (e.g.<br>
&gt; &gt; restricting the number of inputs to the transaction) the transact=
ion<br>
&gt; &gt; spending the aggregated HTLC output can be made self sustained: t=
he<br>
&gt; &gt; spender will be able to claim what is theirs (preimage or timeout=
) and<br>
&gt; &gt; send it to whatever output they want, or to fees. The remainder w=
ill<br>
&gt; &gt; go back into a covenant restricted output with the leftover HTLCs=
.<br>
&gt; &gt; Note that this most likely requires Eltoo in order to not enable =
fee<br>
&gt; &gt; siphoning[7].<br>
&gt;<br>
&gt; I think one of the weaknesses of this approach is the level of malleab=
ility still left to the counterparty, where one might burn in miners fees a=
ll the HTLC accumulated value promised to the counterparty, and for which t=
he preimages have been revealed off-chain.<br>
&gt;<br>
&gt; I wonder if a more safe approach, eliminating a lot of competing inter=
ests style of mempool games, wouldn&#39;t be to segregate HTLC claims in tw=
o separate outputs, with full replication of the HTLC lockscripts in both o=
utputs, and let a covenant accepts or rejects aggregated claims with satisf=
ying witness and chain state condition for time lock.<br>
&gt;<br>
&gt; &gt; ## Impacts to slot jamming<br>
&gt; &gt; With the aggregated output being a reality, it changes the nature=
 of<br>
&gt; &gt; =E2=80=9Cslot jamming=E2=80=9D [1] significantly. While channel c=
apacity must still be<br>
&gt; &gt; reserved for in-flight HTLCs, one no longer needs to allocate a<b=
r>
&gt; &gt; commitment output for each up to some hardcoded limit.<br>
&gt;<br>
&gt; &gt; In today=E2=80=99s protocol this limit is 483, and I believe most=
<br>
&gt; &gt; implementations default to an even lower limit. This leads to cha=
nnel<br>
&gt; &gt; jamming being quite inexpensive, as one can quickly fill a channe=
l<br>
&gt; &gt; with small HTLCs, without needing a significant amount of capital=
 to<br>
&gt; &gt; do so.<br>
&gt;<br>
&gt; &gt; The origins of the 483 slot limits is the worst case commitment s=
ize<br>
&gt; &gt; before getting into unstandard territory [3]. With an aggregated<=
br>
&gt; &gt; output this would no longer be the case, as adding HTLCs would no=
<br>
&gt; &gt; longer affect commitment size. Instead, the full on-chain footpri=
nt of<br>
&gt; &gt; an HTLC would be deferred until claim time.<br>
&gt;<br>
&gt; &gt; Does this mean one could lift, or even remove the limit for numbe=
r of<br>
&gt; &gt; active HTLCs? Unfortunately, the obvious approach doesn=E2=80=99t=
 seem to get<br>
&gt; &gt; rid of the problem entirely, but mitigates it quite a bit.<br>
&gt;<br>
&gt; Yes, protocol limit of 483 is a long-term limit on the payment through=
put of the LN, though as an upper bound we have the dust limits and mempool=
 fluctuations rendering irrelevant the claim of such aggregated dust output=
s. Aggregated claims might give a more dynamic margin of what is a tangible=
 and trust-minimized HTLC payment.<br>
&gt;<br>
&gt; &gt; ### Slot jamming attack scenario<br>
&gt; &gt; Consider the scenario where an attacker sends a large number of<b=
r>
&gt; &gt; non-dust* HTLCs across a channel, and the channel parties enforce=
 no<br>
&gt; &gt; limit on the number of active HTLCs.<br>
&gt;<br>
&gt; &gt; The number of payments would not affect the size of the commitmen=
t<br>
&gt; &gt; transaction at all, only the size of the witness that must be<br>
&gt; &gt; presented when claiming or timing out the HTLCs. This means that =
there<br>
&gt; &gt; is still a point at which chain fees get high enough for the HTLC=
 to<br>
&gt; &gt; be uneconomical to claim. This is no different than in today=E2=
=80=99s spec,<br>
&gt; &gt; and such HTLCs will just be stranded on-chain until chain fees<br=
>
&gt; &gt; decrease, at which point there is a race between the success and<=
br>
&gt; &gt; timeout spends.<br>
&gt;<br>
&gt; &gt; There seems to be no way around this; if you want to claim an HTL=
C<br>
&gt; &gt; on-chain, you need to put the preimage on-chain. And when the HTL=
C<br>
&gt; &gt; first reaches you, you have no way of predicting the future chain=
 fee.<br>
&gt; &gt; With a large number of uneconomical HTLCs in play, the total BTC<=
br>
&gt; &gt; exposure could still be very large, so you might want to limit th=
is<br>
&gt; &gt; somewhat.<br>
&gt;<br>
&gt; &gt; * Note that as long as the sum of HTLCs exceeds the dust limit, o=
ne<br>
&gt; &gt; could manifest the output on the transaction.<br>
&gt;<br>
&gt; Unless we introduce sliding windows during which the claim periods of =
an HTLC can be claimed and freeze accordingly the HTLC-timeout path.<br>
&gt;<br>
&gt; See: <a href=3D"https://fc22.ifca.ai/preproceedings/119.pdf" rel=3D"no=
referrer" target=3D"_blank">https://fc22.ifca.ai/preproceedings/119.pdf</a>=
<br>
&gt;<br>
&gt; Bad news: you will need off-chain consensus on the feerate threshold a=
t which the sliding windows kick-out among all the routing nodes participat=
ing in the HTLC payment path.<br>
&gt;<br>
&gt; &gt; ## The good news<br>
&gt; &gt; With an aggregated HTLC output, the number of HTLCs would no long=
er<br>
&gt; &gt; impact the commitment transaction size while the channel is open =
and<br>
&gt; &gt; operational.<br>
&gt;<br>
&gt; &gt; The marginal cost of claiming an HTLC with a preimage on-chain wo=
uld<br>
&gt; &gt; be much lower; no new inputs or outputs, only a linear increase i=
n the<br>
&gt; &gt; witness size. With a covenant primitive available, the extra foot=
print<br>
&gt; &gt; of the timeout and success transactions would no longer exist.<br=
>
&gt;<br>
&gt; &gt; Claiming timed out HTLCs could still be made close to constant si=
ze<br>
&gt; &gt; (no preimage to present), so no additional on-chain cost with mor=
e<br>
&gt; &gt; HTLCs.<br>
&gt;<br>
&gt; I wonder if in a PTLC world, you can generate an aggregate curve point=
 for all the sub combinations of scalar plausible. Unrevealed curve points =
in a taproot branch are cheap. It might claim an offered HTLC near-constant=
 size too.<br>
&gt;<br>
&gt; &gt; ## The bad news<br>
&gt; &gt; The most obvious problem is that we would need a new covenant<br>
&gt; &gt; primitive on L1 (see below). However, I think it could be benefic=
ial<br>
&gt; &gt; to start exploring these ideas now in order to guide the L1 effor=
t<br>
&gt; &gt; towards something we could utilize to its fullest on L2.<br>
&gt;<br>
&gt; &gt; As mentioned, even with a functioning covenant, we don=E2=80=99t =
escape the<br>
&gt; &gt; fact that a preimage needs to go on-chain, pricing out HTLCs at<b=
r>
&gt; &gt; certain fee rates. This is analogous to the dust exposure problem=
<br>
&gt; &gt; discussed in [6], and makes some sort of limit still required.<br=
>
&gt;<br>
&gt; Ideally such covenant mechanisms would generalize to the withdrawal ph=
ase of payment pools, where dozens or hundreds of participants wish to conf=
irm their non-competing withdrawal transactions concurrently. While unlocki=
ng preimage or scalar can be aggregated in a single witness, there will sti=
ll be a need to verify that each withdrawal output associated with an unloc=
king secret is present in the transaction.<br>
&gt;<br>
&gt; Maybe few other L2s are answering this N-inputs-to-M-outputs pattern w=
ith advanced locking scripts conditions to satisfy.<br>
&gt;<br>
&gt; &gt; ### Open question<br>
&gt; &gt; With PTLCs, could one create a compact proof showing that you kno=
w the<br>
&gt; &gt; preimage for m-of-n of the satoshis in the output? (some sort of<=
br>
&gt; &gt; threshold signature).<br>
&gt;<br>
&gt; &gt; If we could do this we would be able to remove the slot jamming i=
ssue<br>
&gt; &gt; entirely; any number of active PTLCs would not change the on-chai=
n<br>
&gt; &gt; cost of claiming them.<br>
&gt;<br>
&gt; See comments above, I think there is a plausible scheme here you just =
generate all the point combinations possible, and only reveal the one you n=
eed at broadcast.<br>
&gt;<br>
&gt; &gt; ## Covenant primitives<br>
&gt; &gt; A recursive covenant is needed to achieve this. Something like OP=
_CTV<br>
&gt; &gt; and OP_APO seems insufficient, since the number of ways the set o=
f<br>
&gt; &gt; HTLCs could be claimed would cause combinatorial blowup in the nu=
mber<br>
&gt; &gt; of possible spending transactions.<br>
&gt;<br>
&gt; &gt; Personally, I=E2=80=99ve found the simple yet powerful properties=
 of<br>
&gt; &gt; OP_CHECKCONTRACTVERIFY [4] together with OP_CAT and amount inspec=
tion<br>
&gt; &gt; particularly interesting for the use case, but I=E2=80=99m certai=
n many of the<br>
&gt; &gt; other proposals could achieve the same thing. More direct inspect=
ion<br>
&gt; &gt; like you get from a proposal like OP_TX[9] would also most likely=
 have<br>
&gt; &gt; the building blocks needed.<br>
&gt;<br>
&gt; As pointed out during the CTV drama and payment pool public discussion=
 years ago, what would be very useful to tie-break among all covenant const=
ructions would be an efficiency simulation framework. Even if the same sema=
ntic can be achieved independently by multiple covenants, they certainly do=
 not have the same performance trade-offs (e.g average and worst-case witne=
ss size).<br>
&gt;<br>
&gt; I don&#39;t think the blind approach of activating many complex covena=
nts at the same time is conservative enough in Bitcoin, where one might des=
ign &quot;malicious&quot; L2 contracts, of which the game-theory is not ful=
ly understood.<br>
&gt;<br>
&gt; See e.g <a href=3D"https://blog.bitmex.com/txwithhold-smart-contracts/=
" rel=3D"noreferrer" target=3D"_blank">https://blog.bitmex.com/txwithhold-s=
mart-contracts/</a><br>
&gt;<br>
&gt; &gt; ### Proof-of-concept<br>
&gt; &gt; I=E2=80=99ve implemented a rough demo** of spending an HTLC outpu=
t that pays<br>
&gt; &gt; to a script with OP_CHECKCONTRACTVERIFY to achieve this [5]. The =
idea<br>
&gt; &gt; is to commit to all active HTLCs in a merkle tree, and have the<b=
r>
&gt; &gt; spender provide merkle proofs for the HTLCs to claim, claiming th=
e sum<br>
&gt; &gt; into a new output. The remainder goes back into a new output with=
 the<br>
&gt; &gt; claimed HTLCs removed from the merkle tree.<br>
&gt;<br>
&gt; &gt; An interesting trick one can do when creating the merkle tree, is=
<br>
&gt; &gt; sorting the HTLCs by expiry. This means that one in the timeout c=
ase<br>
&gt; &gt; claim a subtree of HTLCs using a single merkle proof (and RBF thi=
s<br>
&gt; &gt; batched timeout claim as more and more HTLCs expire) reducing the=
<br>
&gt; &gt; timeout case to constant size witness (or rather logarithmic in t=
he<br>
&gt; &gt; total number of HTLCs).<br>
&gt;<br>
&gt; &gt; **Consider it an experiment, as it is missing a lot before it cou=
ld be<br>
&gt; &gt; usable in any real commitment setting.<br>
&gt;<br>
&gt; I think this is an interesting question if more advanced cryptosystems=
 based on assumptions other than the DL problem could constitute a factor o=
f scalability of LN payment throughput by orders of magnitude, by decouplin=
g number of off-chain payments from the growth of the on-chain witness size=
 need to claim them, without lowering in security as with trimmed HTLC due =
to dust limits.<br>
&gt;<br>
&gt; Best,<br>
&gt; Antoine<br>
&gt;<br>
&gt; Le jeu. 26 oct. 2023 =C3=A0 20:28, Johan Tor=C3=A5s Halseth via bitcoi=
n-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=
=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt; a =C3=A9crit :<br=
>
&gt;&gt;<br>
&gt;&gt; Hi all,<br>
&gt;&gt;<br>
&gt;&gt; After the transaction recycling has spurred some discussion the la=
st<br>
&gt;&gt; week or so, I figured it could be worth sharing some research I=E2=
=80=99ve<br>
&gt;&gt; done into HTLC output aggregation, as it could be relevant for how=
 to<br>
&gt;&gt; avoid this problem in a future channel type.<br>
&gt;&gt;<br>
&gt;&gt; TLDR; With the right covenant we can create HTLC outputs that are =
much<br>
&gt;&gt; more chain efficient, not prone to tx recycling and harder to jam.=
<br>
&gt;&gt;<br>
&gt;&gt; ## Transaction recycling<br>
&gt;&gt; The transaction recycling attack is made possible by the change ma=
de<br>
&gt;&gt; to HTLC second level transactions for the anchor channel type[8];<=
br>
&gt;&gt; making it possible to add fees to the transaction by adding inputs=
<br>
&gt;&gt; without violating the signature. For the legacy channel type this<=
br>
&gt;&gt; attack was not possible, as all fees were taken from the HTLC outp=
uts<br>
&gt;&gt; themselves, and had to be agreed upon by channel counterparties du=
ring<br>
&gt;&gt; signing (of course this has its own problems, which is why we want=
ed<br>
&gt;&gt; to change it).<br>
&gt;&gt;<br>
&gt;&gt; The idea of HTLC output aggregation is to collapse all HTLC output=
s on<br>
&gt;&gt; the commitment to a single one. This has many benefits (that I=E2=
=80=99ll get<br>
&gt;&gt; to), one of them being the possibility to let the spender claim th=
e<br>
&gt;&gt; portion of the output that they=E2=80=99re right to, deciding how =
much should<br>
&gt;&gt; go to fees. Note that this requires a covenant to be possible.<br>
&gt;&gt;<br>
&gt;&gt; ## A single HTLC output<br>
&gt;&gt; Today, every forwarded HTLC results in an output that needs to be<=
br>
&gt;&gt; manifested on the commitment transaction in order to claw back mon=
ey<br>
&gt;&gt; in case of an uncooperative channel counterparty. This puts a limi=
t on<br>
&gt;&gt; the number of active HTLCs (in order for the commitment transactio=
n to<br>
&gt;&gt; not become too large) which makes it possible to jam the channel w=
ith<br>
&gt;&gt; small amounts of capital [1]. It also turns out that having this l=
imit<br>
&gt;&gt; be large makes it expensive and complicated to sweep the outputs<b=
r>
&gt;&gt; efficiently [2].<br>
&gt;&gt;<br>
&gt;&gt; Instead of having new HTLC outputs manifest for each active<br>
&gt;&gt; forwarding, with covenants on the base layer one could create a si=
ngle<br>
&gt;&gt; aggregated output on the commitment. The output amount being the s=
um<br>
&gt;&gt; of the active HTLCs (offered and received), alternatively one outp=
ut<br>
&gt;&gt; for received and one for offered. When spending this output, you w=
ould<br>
&gt;&gt; only be entitled to the fraction of the amount corresponding to th=
e<br>
&gt;&gt; HTLCs you know the preimage for (received), or that has timed out<=
br>
&gt;&gt; (offered).<br>
&gt;&gt;<br>
&gt;&gt; ## Impacts to transaction recycling<br>
&gt;&gt; Depending on the capabilities of the covenant available (e.g.<br>
&gt;&gt; restricting the number of inputs to the transaction) the transacti=
on<br>
&gt;&gt; spending the aggregated HTLC output can be made self sustained: th=
e<br>
&gt;&gt; spender will be able to claim what is theirs (preimage or timeout)=
 and<br>
&gt;&gt; send it to whatever output they want, or to fees. The remainder wi=
ll<br>
&gt;&gt; go back into a covenant restricted output with the leftover HTLCs.=
<br>
&gt;&gt; Note that this most likely requires Eltoo in order to not enable f=
ee<br>
&gt;&gt; siphoning[7].<br>
&gt;&gt;<br>
&gt;&gt; ## Impacts to slot jamming<br>
&gt;&gt; With the aggregated output being a reality, it changes the nature =
of<br>
&gt;&gt; =E2=80=9Cslot jamming=E2=80=9D [1] significantly. While channel ca=
pacity must still be<br>
&gt;&gt; reserved for in-flight HTLCs, one no longer needs to allocate a<br=
>
&gt;&gt; commitment output for each up to some hardcoded limit.<br>
&gt;&gt;<br>
&gt;&gt; In today=E2=80=99s protocol this limit is 483, and I believe most<=
br>
&gt;&gt; implementations default to an even lower limit. This leads to chan=
nel<br>
&gt;&gt; jamming being quite inexpensive, as one can quickly fill a channel=
<br>
&gt;&gt; with small HTLCs, without needing a significant amount of capital =
to<br>
&gt;&gt; do so.<br>
&gt;&gt;<br>
&gt;&gt; The origins of the 483 slot limits is the worst case commitment si=
ze<br>
&gt;&gt; before getting into unstandard territory [3]. With an aggregated<b=
r>
&gt;&gt; output this would no longer be the case, as adding HTLCs would no<=
br>
&gt;&gt; longer affect commitment size. Instead, the full on-chain footprin=
t of<br>
&gt;&gt; an HTLC would be deferred until claim time.<br>
&gt;&gt;<br>
&gt;&gt; Does this mean one could lift, or even remove the limit for number=
 of<br>
&gt;&gt; active HTLCs? Unfortunately, the obvious approach doesn=E2=80=99t =
seem to get<br>
&gt;&gt; rid of the problem entirely, but mitigates it quite a bit.<br>
&gt;&gt;<br>
&gt;&gt; ### Slot jamming attack scenario<br>
&gt;&gt; Consider the scenario where an attacker sends a large number of<br=
>
&gt;&gt; non-dust* HTLCs across a channel, and the channel parties enforce =
no<br>
&gt;&gt; limit on the number of active HTLCs.<br>
&gt;&gt;<br>
&gt;&gt; The number of payments would not affect the size of the commitment=
<br>
&gt;&gt; transaction at all, only the size of the witness that must be<br>
&gt;&gt; presented when claiming or timing out the HTLCs. This means that t=
here<br>
&gt;&gt; is still a point at which chain fees get high enough for the HTLC =
to<br>
&gt;&gt; be uneconomical to claim. This is no different than in today=E2=80=
=99s spec,<br>
&gt;&gt; and such HTLCs will just be stranded on-chain until chain fees<br>
&gt;&gt; decrease, at which point there is a race between the success and<b=
r>
&gt;&gt; timeout spends.<br>
&gt;&gt;<br>
&gt;&gt; There seems to be no way around this; if you want to claim an HTLC=
<br>
&gt;&gt; on-chain, you need to put the preimage on-chain. And when the HTLC=
<br>
&gt;&gt; first reaches you, you have no way of predicting the future chain =
fee.<br>
&gt;&gt; With a large number of uneconomical HTLCs in play, the total BTC<b=
r>
&gt;&gt; exposure could still be very large, so you might want to limit thi=
s<br>
&gt;&gt; somewhat.<br>
&gt;&gt;<br>
&gt;&gt; * Note that as long as the sum of HTLCs exceeds the dust limit, on=
e<br>
&gt;&gt; could manifest the output on the transaction.<br>
&gt;&gt;<br>
&gt;&gt; ## The good news<br>
&gt;&gt; With an aggregated HTLC output, the number of HTLCs would no longe=
r<br>
&gt;&gt; impact the commitment transaction size while the channel is open a=
nd<br>
&gt;&gt; operational.<br>
&gt;&gt;<br>
&gt;&gt; The marginal cost of claiming an HTLC with a preimage on-chain wou=
ld<br>
&gt;&gt; be much lower; no new inputs or outputs, only a linear increase in=
 the<br>
&gt;&gt; witness size. With a covenant primitive available, the extra footp=
rint<br>
&gt;&gt; of the timeout and success transactions would no longer exist.<br>
&gt;&gt;<br>
&gt;&gt; Claiming timed out HTLCs could still be made close to constant siz=
e<br>
&gt;&gt; (no preimage to present), so no additional on-chain cost with more=
<br>
&gt;&gt; HTLCs.<br>
&gt;&gt;<br>
&gt;&gt; ## The bad news<br>
&gt;&gt; The most obvious problem is that we would need a new covenant<br>
&gt;&gt; primitive on L1 (see below). However, I think it could be benefici=
al<br>
&gt;&gt; to start exploring these ideas now in order to guide the L1 effort=
<br>
&gt;&gt; towards something we could utilize to its fullest on L2.<br>
&gt;&gt;<br>
&gt;&gt; As mentioned, even with a functioning covenant, we don=E2=80=99t e=
scape the<br>
&gt;&gt; fact that a preimage needs to go on-chain, pricing out HTLCs at<br=
>
&gt;&gt; certain fee rates. This is analogous to the dust exposure problem<=
br>
&gt;&gt; discussed in [6], and makes some sort of limit still required.<br>
&gt;&gt;<br>
&gt;&gt; ### Open question<br>
&gt;&gt; With PTLCs, could one create a compact proof showing that you know=
 the<br>
&gt;&gt; preimage for m-of-n of the satoshis in the output? (some sort of<b=
r>
&gt;&gt; threshold signature).<br>
&gt;&gt;<br>
&gt;&gt; If we could do this we would be able to remove the slot jamming is=
sue<br>
&gt;&gt; entirely; any number of active PTLCs would not change the on-chain=
<br>
&gt;&gt; cost of claiming them.<br>
&gt;&gt;<br>
&gt;&gt; ## Covenant primitives<br>
&gt;&gt; A recursive covenant is needed to achieve this. Something like OP_=
CTV<br>
&gt;&gt; and OP_APO seems insufficient, since the number of ways the set of=
<br>
&gt;&gt; HTLCs could be claimed would cause combinatorial blowup in the num=
ber<br>
&gt;&gt; of possible spending transactions.<br>
&gt;&gt;<br>
&gt;&gt; Personally, I=E2=80=99ve found the simple yet powerful properties =
of<br>
&gt;&gt; OP_CHECKCONTRACTVERIFY [4] together with OP_CAT and amount inspect=
ion<br>
&gt;&gt; particularly interesting for the use case, but I=E2=80=99m certain=
 many of the<br>
&gt;&gt; other proposals could achieve the same thing. More direct inspecti=
on<br>
&gt;&gt; like you get from a proposal like OP_TX[9] would also most likely =
have<br>
&gt;&gt; the building blocks needed.<br>
&gt;&gt;<br>
&gt;&gt; ### Proof-of-concept<br>
&gt;&gt; I=E2=80=99ve implemented a rough demo** of spending an HTLC output=
 that pays<br>
&gt;&gt; to a script with OP_CHECKCONTRACTVERIFY to achieve this [5]. The i=
dea<br>
&gt;&gt; is to commit to all active HTLCs in a merkle tree, and have the<br=
>
&gt;&gt; spender provide merkle proofs for the HTLCs to claim, claiming the=
 sum<br>
&gt;&gt; into a new output. The remainder goes back into a new output with =
the<br>
&gt;&gt; claimed HTLCs removed from the merkle tree.<br>
&gt;&gt;<br>
&gt;&gt; An interesting trick one can do when creating the merkle tree, is<=
br>
&gt;&gt; sorting the HTLCs by expiry. This means that one in the timeout ca=
se<br>
&gt;&gt; claim a subtree of HTLCs using a single merkle proof (and RBF this=
<br>
&gt;&gt; batched timeout claim as more and more HTLCs expire) reducing the<=
br>
&gt;&gt; timeout case to constant size witness (or rather logarithmic in th=
e<br>
&gt;&gt; total number of HTLCs).<br>
&gt;&gt;<br>
&gt;&gt; **Consider it an experiment, as it is missing a lot before it coul=
d be<br>
&gt;&gt; usable in any real commitment setting.<br>
&gt;&gt;<br>
&gt;&gt;<br>
&gt;&gt; [1] <a href=3D"https://bitcoinops.org/en/topics/channel-jamming-at=
tacks/#htlc-jamming-attack" rel=3D"noreferrer" target=3D"_blank">https://bi=
tcoinops.org/en/topics/channel-jamming-attacks/#htlc-jamming-attack</a><br>
&gt;&gt; [2] <a href=3D"https://github.com/lightning/bolts/issues/845" rel=
=3D"noreferrer" target=3D"_blank">https://github.com/lightning/bolts/issues=
/845</a><br>
&gt;&gt; [3] <a href=3D"https://github.com/lightning/bolts/blob/aad959a297f=
f66946effb165518143be15777dd6/02-peer-protocol.md#rationale-7" rel=3D"noref=
errer" target=3D"_blank">https://github.com/lightning/bolts/blob/aad959a297=
ff66946effb165518143be15777dd6/02-peer-protocol.md#rationale-7</a><br>
&gt;&gt; [4] <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin=
-dev/2022-November/021182.html" rel=3D"noreferrer" target=3D"_blank">https:=
//lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-November/021182.html=
</a><br>
&gt;&gt; [5] <a href=3D"https://github.com/halseth/tapsim/blob/b07f29804cf3=
2dce0168ab5bb40558cbb18f2e76/examples/matt/claimpool/script.txt" rel=3D"nor=
eferrer" target=3D"_blank">https://github.com/halseth/tapsim/blob/b07f29804=
cf32dce0168ab5bb40558cbb18f2e76/examples/matt/claimpool/script.txt</a><br>
&gt;&gt; [6] <a href=3D"https://lists.linuxfoundation.org/pipermail/lightni=
ng-dev/2021-October/003257.html" rel=3D"noreferrer" target=3D"_blank">https=
://lists.linuxfoundation.org/pipermail/lightning-dev/2021-October/003257.ht=
ml</a><br>
&gt;&gt; [7] <a href=3D"https://github.com/lightning/bolts/issues/845#issue=
comment-937736734" rel=3D"noreferrer" target=3D"_blank">https://github.com/=
lightning/bolts/issues/845#issuecomment-937736734</a><br>
&gt;&gt; [8] <a href=3D"https://github.com/lightning/bolts/blob/8a64c6a1cef=
979b3f0cecb00ba7a48c2d28b3588/03-transactions.md?plain=3D1#L333" rel=3D"nor=
eferrer" target=3D"_blank">https://github.com/lightning/bolts/blob/8a64c6a1=
cef979b3f0cecb00ba7a48c2d28b3588/03-transactions.md?plain=3D1#L333</a><br>
&gt;&gt; [9] <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin=
-dev/2022-May/020450.html" rel=3D"noreferrer" target=3D"_blank">https://lis=
ts.linuxfoundation.org/pipermail/bitcoin-dev/2022-May/020450.html</a><br>
&gt;&gt; _______________________________________________<br>
&gt;&gt; bitcoin-dev mailing list<br>
&gt;&gt; <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D=
"_blank">bitcoin-dev@lists.linuxfoundation.org</a><br>
&gt;&gt; <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitc=
oin-dev" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation=
.org/mailman/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--0000000000006d3f3b060cbc8c92--