path: root/8a/57ad513e34c8f4be81d0b4108e6107b12d5da9

Return-Path: <johanth@gmail.com>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 53080C0032
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 26 Oct 2023 16:52:18 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp1.osuosl.org (Postfix) with ESMTP id 2E8C683EFC
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 26 Oct 2023 16:52:18 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 2E8C683EFC
Authentication-Results: smtp1.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20230601 header.b=POb2cbg7
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -0.2
X-Spam-Level: 
X-Spam-Status: No, score=-0.2 tagged_above=-999 required=5
 tests=[BAYES_20=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001]
 autolearn=ham autolearn_force=no
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 oLA7XwC-49xC
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 26 Oct 2023 16:52:16 +0000 (UTC)
Received: from mail-oi1-x235.google.com (mail-oi1-x235.google.com
 [IPv6:2607:f8b0:4864:20::235])
 by smtp1.osuosl.org (Postfix) with ESMTPS id B762083F01
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 26 Oct 2023 16:52:16 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org B762083F01
Received: by mail-oi1-x235.google.com with SMTP id
 5614622812f47-3b512dd7d5bso709809b6e.1
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 26 Oct 2023 09:52:16 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=gmail.com; s=20230601; t=1698339135; x=1698943935;
 darn=lists.linuxfoundation.org; 
 h=content-transfer-encoding:to:subject:message-id:date:from
 :mime-version:from:to:cc:subject:date:message-id:reply-to;
 bh=ooKEZhFsSF5PoSb049v6RnIS4wtRDRdXlV/yqv/Okoc=;
 b=POb2cbg7rVaLiZt87kipR4IBQSQudz/1gbsAdx5ar6zICbyZDPYgyjoKGto+dyxT2M
 mAcaMXdlcsujF130D3iVVtDT1Juqd9mNpNM1AiWERdL6HsXhW+e0xDSdNxGZJ6YnvBG4
 nAq+6vedvXvYpltuICnsYRj2PEg51/cA4ZFBtu68e0pdMvtWBHLFjMMPeuDvRvPW04Z2
 mxHSTngnNZktQjdCip1zFIQbQ11XoGR6QjaZyUjhW/Eq47873l7dWduSFGKfqEWiFdMW
 PT5ROjQNyZ1EBzk11K/AYzs83vh+uSNe02acauBRLzmEMTXiOMH5bOoCpCGdkq4Blcan
 o2og==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20230601; t=1698339135; x=1698943935;
 h=content-transfer-encoding:to:subject:message-id:date:from
 :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id
 :reply-to;
 bh=ooKEZhFsSF5PoSb049v6RnIS4wtRDRdXlV/yqv/Okoc=;
 b=Bu6F/WAHeHSF0jYB78ozR2z+whdbLefMTCUK9twYoNSssrOdMq2iDjd8Gjv+fzIuTS
 ulObcyaJCPtCIyBEkeBiv7zhO76r34FQiewzU3ERciAlU5/bKbWQrYFNGzDIMj1YiNav
 4vGAoNcvFNX/0UCXD2pB1RJYJJJ30DRmwfT/SwAyMhi+MEnDCN2bbee05HsLoD4WTbda
 pt8VNIiRgLjIrGpTCZCaFcZm9qNU3c1EfzoYFdBGVPH2aV9llJUKys9XmiGacyCbA+vs
 82y7O1fxtHiASUo2RRoZfcNJ9sRDnM73rVC3K1BiT3blDh3IjCHstuwTZBiFfHHo8g5d
 YWqw==
X-Gm-Message-State: AOJu0YzCZzOujm5rB6VEt3MZB8eWl7gG5cLVdkGaFHlRZPK5Wb2Srm9h
 yw+6Sx98+bnjZWBLYkzNwR/Y7nx10Msd68AKcNCuz4ZpqRECEVHC
X-Google-Smtp-Source: AGHT+IE1owKntHLnnZpqNUFG25dt0ASLynvQ7cCbE0TSFsIfz0MLg4hW3dUf+k37WvSkCmynqeyDg2c6HyPpV5bK480=
X-Received: by 2002:a05:6808:208d:b0:3b2:dd49:4e9d with SMTP id
 s13-20020a056808208d00b003b2dd494e9dmr24543009oiw.6.1698339135250; Thu, 26
 Oct 2023 09:52:15 -0700 (PDT)
MIME-Version: 1.0
From: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= <johanth@gmail.com>
Date: Thu, 26 Oct 2023 12:52:03 -0400
Message-ID: <CAD3i26Dux33wF=Ki0ouChseW7dehRuz+QC54bmsm7xzm2YACQQ@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Mailman-Approved-At: Thu, 26 Oct 2023 19:27:57 +0000
Subject: [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: Thu, 26 Oct 2023 16:52:19 -0000

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 g=
et
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 shou=
ld
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 capacity mu=
st 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 g=
et
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 escape 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 many 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 that pay=
s
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-=
attack
[2] https://github.com/lightning/bolts/issues/845
[3] https://github.com/lightning/bolts/blob/aad959a297ff66946effb165518143b=
e15777dd6/02-peer-protocol.md#rationale-7
[4] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-November/0=
21182.html
[5] https://github.com/halseth/tapsim/blob/b07f29804cf32dce0168ab5bb40558cb=
b18f2e76/examples/matt/claimpool/script.txt
[6] https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-October/=
003257.html
[7] https://github.com/lightning/bolts/issues/845#issuecomment-937736734
[8] https://github.com/lightning/bolts/blob/8a64c6a1cef979b3f0cecb00ba7a48c=
2d28b3588/03-transactions.md?plain=3D1#L333
[9] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-May/020450=
.html