path: root/6a/e1fff3664e2bf59f1f69d31a040dfbd20ce5f3

Return-Path: <naumenko.gs@gmail.com>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 85148C002B
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  2 Feb 2023 08:40:18 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp1.osuosl.org (Postfix) with ESMTP id 5F3158188D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  2 Feb 2023 08:40:18 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 5F3158188D
Authentication-Results: smtp1.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20210112 header.b=NQoYGjkg
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 smtp1.osuosl.org ([127.0.0.1])
 by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id aQUlsWBqQUwb
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  2 Feb 2023 08:40:16 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org CAAC981336
Received: from mail-ed1-x532.google.com (mail-ed1-x532.google.com
 [IPv6:2a00:1450:4864:20::532])
 by smtp1.osuosl.org (Postfix) with ESMTPS id CAAC981336
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  2 Feb 2023 08:40:15 +0000 (UTC)
Received: by mail-ed1-x532.google.com with SMTP id u21so1219840edv.3
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 02 Feb 2023 00:40:15 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
 h=mime-version:subject:references:in-reply-to:message-id:to:from:date
 :from:to:cc:subject:date:message-id:reply-to;
 bh=lt5fE5Vr/Y8uWejLT5d+W0I17pUZgC8++ArdgHiZyxw=;
 b=NQoYGjkgkRWIaXihRtjSWcneN/dUJvQhD+3NcHhar7CTDPg0XENPfjWcZ4YyNNxzMf
 YavtNg8zMAVYoSqtrqYWMoVIPvSTGi50EBeYPIENA5MdNq3EJExyavKcMgwAxKyDOZWz
 KZBf/qNfgarZHyEvYcdStGkM5bkw/j63x8Ve6VRGssU5sPyzr7Bp1+Lb655acuU6bC+f
 fbjQP3JAOvR5v01iHx4lClSk/zuUI4AqFKU3ZQg1X1V0lUFFaIqiniX8FtWEN6nNFFeS
 xmKkexcOYDcovfMbicPvsclUyPYwiX3ZMv3Z5wKX9l5k1x3dvthXYVSMoVa9lqDSy7Yt
 dLZg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=mime-version:subject:references:in-reply-to:message-id:to:from:date
 :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to;
 bh=lt5fE5Vr/Y8uWejLT5d+W0I17pUZgC8++ArdgHiZyxw=;
 b=RMXx1knzvbwrUEkzJpl5s5SGvNVIM7Z842AFzld9zq6tjCzJvAFuQn3aw5Ov4ZuHB9
 u/oZihgDwDR/7fm/FSuRqeT01Zm/JLraE+1MimZryiPw8M8TyqvxBcd2jIiOcwJdoYhS
 jscuwDKzwWOdiLwHpe492XA1O2J5AvB/TT3PlQE2JM2F2o0G1K47m0ZWEDqPI7hLZn+w
 WekQQlkaIu87UF1DnOF9QQrPqc42dGP73kvhyGpA23PfAQIub405ZXdVYZM2hLaClyzk
 atfB3/ZSSupdhPG3s4SURe8O2yK3ht8mC9YY051D50Oslg7RCogwMO5pE1VJbHFoX3aF
 PUjg==
X-Gm-Message-State: AO0yUKU4QSylM6boTfxEzNeCJMEmd5uXuZfzbHsg0TbqTiyZZy6vrnx6
 J8R9DDVjPyhIfmIvROcYVClwIhxkhnCfMw==
X-Google-Smtp-Source: AK7set8ZrmQpjjyF2kBd2TXJkDkbXEhr6fYn74M4iFXf8+wMZI5t6kysTatT7lB9mVW0WzbxeSFFxQ==
X-Received: by 2002:aa7:c403:0:b0:46c:8544:42be with SMTP id
 j3-20020aa7c403000000b0046c854442bemr4935946edq.5.1675327213650; 
 Thu, 02 Feb 2023 00:40:13 -0800 (PST)
Received: from [10.118.166.124] ([193.32.249.173])
 by smtp.gmail.com with ESMTPSA id
 v22-20020a056402175600b004a2067d6ba4sm9457428edx.52.2023.02.02.00.40.12
 for <bitcoin-dev@lists.linuxfoundation.org>
 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128);
 Thu, 02 Feb 2023 00:40:13 -0800 (PST)
Date: Thu, 2 Feb 2023 10:40:04 +0200
From: Gleb Naumenko <naumenko.gs@gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <f594c2f8-d712-48e4-a010-778dd4d0cadb@Spark>
In-Reply-To: <a0898fd1-88db-41b0-97b3-a1c7a1640b39@Spark>
References: <a0898fd1-88db-41b0-97b3-a1c7a1640b39@Spark>
X-Readdle-Message-ID: f594c2f8-d712-48e4-a010-778dd4d0cadb@Spark
MIME-Version: 1.0
Content-Type: multipart/alternative; boundary="63db76eb_75a2a8d4_5b0"
X-Mailman-Approved-At: Thu, 02 Feb 2023 09:11:50 +0000
Subject: [bitcoin-dev] Costless bribes against time-sensitive protocols
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, 02 Feb 2023 08:40:18 -0000

--63db76eb_75a2a8d4_5b0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

=23=23 Intro

Most of it feels like implicit knowledge, but I couldn't find anything wr=
itten so here it is. The ideas towards anchor outputs and the conclusions=
 probably have some new perspectives.

This post is about the game-theoretic security of time-sensitive protocol=
s if miners are open to censorship for a reward. To become practical, the=
 following has to happen.

1) a substantial hashrate has to be willing to participate in this behavi=
our, according to the known formula from the Whitepaper. The more blocks =
it takes to attack (defined by a particular protocol configuration and co=
uld be tuned), the exponentially higher % hashrate is required.

2) a communication layer is required to send bribes to these miners. This=
 could be a private transaction relay network, or a mempool allowing stil=
l-time-locked transactions. It could be even an announcement board (e.g.,=
 submitting raw txs under a Twitter hashtag and inviting miners to monito=
r it).

3) a bribe transaction construction (will be explained later).

In this post, I talk about the case when:
1. a significant hashrate (e.g., 95%+) is open to take these bribes;
2. but miners don't trust each other;
3. and there is no reorgs.

Assumption =5C*(2) is more nuanced. What I mean here is roughly =22miner =
X would rather take an immediate gain than commit to a lenghty scenario w=
here many miners coordinate to take reward on behalf of each other and th=
en distribute it accordingly to the hashrate=22. The game theory of this =
assumption should be better defined in the future.

We will see, how widely known tweaks lift the bar for (2) and (3) and how=
 this could be further improved.

*A special case of this scenario is miners withholding Alice's transactio=
n to force her to bump fees, even if Bob hasn't submitted a bribe. Here I=
 assume miners won't do it unless there is an external incentive (Bob's b=
ribe), although this issue is also interesting.*

=23=23 Simple opcode-based construction

The simplest time-sensitive two-party contract is PowSwap (a bet on the f=
uture block issuance rate), a single on-chain UTXO with the following spe=
nding conditions:
- Alice=E2=80=99s key can spend if height=3DH is reached;
- Bob=E2=80=99s key can spend if Time=3DT is reached.

Say H is approaching quickly, and T is far behind. Bob now uses a private=
 mining relay to submit his non-mineable transaction paying e.g. half of =
the UTXO value towards fees.

Alice has two problems: 1) she can=E2=80=99t figure out why her transacti=
on isn=E2=80=99t mined and how much fee to overpay; 2) the attack is free=
 for Bob (he has nothing to lose), while Alice loses everything up to the=
 full UTXO value.

=23=23 Simple nLockTime-based construction

If parties use pre-signed transactions with nLockTime (instead of the opc=
odes), Bob=E2=80=99s fee can be pre-signed to a rather low value, so that=
 Alice can reasonably overbid it without much loss (she probably doesn't =
even need to take any action).

Bob can, however, bump the fee by creating a CP=46P transaction with supe=
r-high fee. All it requires now is submitting twice as much data to the p=
rivate mining relay (and burning slightly more in fees).

=23=23 nLockTime-based construction with OP=5FCSV output

If Bob=E2=80=99s output can=E2=80=99t be spent right away, but is forced =
to be deterred to even one block in the future, it makes taking this brib=
e not rational: a censoring miner can=E2=80=99t be sure about the deferre=
d reward (remember, miners don't trust each other). At the same time, min=
ing the honest transaction and taking its fee is always available earlier=
.

Smart contracts could possibly make it rational for miners (see =5B1=5D),=
 e.g. by allowing Bob to allocate the bribe based on the historic hashrat=
e distribution linked to coinbase pubkeys.

At the same time, this approach makes dynamic fee management impossible.

=23=23 Anchor outputs

Anchor outputs allow bringing external capital for fee management while l=
ocking internal capital. Bob can use this capital for a bribe. If the att=
ack fails, Bob's external capital remains safe, so this is not so bad for=
 Bob.

The attack can be more costly if this external capital was claimable:
- by Alice: e.g., Alice can steal a (covenanted) anchor output if it's re=
vealed before Bob's nLockTime makes it mineable (requires her to monitor =
the private relay);
- or by miners, e.g. if Alice forces Bob, at contract setup, to use a rev=
erse time-lock (the anchor can be stolen by miner if seen before time=3DT=
); or if mining Alice's honest transaction also allows miners to take Bob=
's fee output (e.g., Alice's honest transaction *could* act as a parent/p=
reimage, conditionally, although this may require reverse time-locking Al=
ice to protect Bob...)

*Ephemeral anchors doesn=E2=80=99t do much w.r.t. our trade-off, as it is=
 a mempool-oriented thing.*

=23=23 Lightning

Lightning is different from the described protocol in two things:
1) It relies on intermediate transactions (e.g., Commitment in Poon-Dryja=
);
2) Usually both parties have some balance in the channel.

I believe that (1) doesn=E2=80=99t change the situation much, it just mak=
es it more nuanced.
(2) is irrelevant because an attacker can just spend the entire channel b=
efore the attack.
Thus, most of these concerns apply to lightning equally.

=23=23 Related work

The LN paper briefly mentioned this problem, although it was claimed impr=
actical due to a high degree of required collusion. We already see privat=
e mining relay in=C2=A0mevwatch.info=C2=A0(ethereum), and we had =46IBRE =
(I think it was neutral).

=5B2=5D discussed constructions and economics for bribing miners. =5B1=5D=
 suggests more practical considerations for achieving this. Both don=E2=80=
=99t focus on the risks of particular time-sensitive protocol constructio=
ns.

=5B3=5D highlighted a similar protocol risk, but the proposed solution se=
ems to work only if an attacker has funds to lose locked in the contract =
(e.g., collateral, lightning balance, powswap payout).

=23=23 Conclusions

To increase the attack bar w.r.t the configuration described in the intro=
, we should either:
- stick to the *nLockTime-based construction with OP=5FCSV output*, forge=
t about dynamic fee management, and hope that bribe allocation smart cont=
racts doesn't work out;
- use anchor outputs (or another external fee scheme), but enforce a way =
to steal/burn the external fee if it's an attack;
- design new fee/channel constructions.

These ideas may also be helpful for alternative payment channels designs =
as well (v3+ephemeral anchors, SIGHASH=5FGROUP, etc.), or in the future t=
o protect against more powerful covenants allowing stronger bribes (see =5B=
1=5D).

Thanks to Antoine Riard and Greg Sanders for initial discussion.

-------------------------

=23=23 References

1. TxWithhold Smart Contracts by Gleb Naumenko =7C BitMEX Blog (https://b=
log.bitmex.com/txwithhold-smart-contracts/)
2. Temporary Censorship Attacks in the Presence of Rational Miners (https=
://eprint.iacr.org/2019/748.pdf)
3. MAD-HTLC: Because HTLC is Crazy-Cheap to Attack (https://arxiv.org/pdf=
/2006.12031.pdf)

--63db76eb_75a2a8d4_5b0
Content-Type: text/html; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

<html xmlns=3D=22http://www.w3.org/1999/xhtml=22>
<head>
<title></title>
</head>
<body>
<div name=3D=22messageBodySection=22>
<div dir=3D=22auto=22>=23=23 Intro<br />
<br />
Most of it feels like implicit knowledge, but I couldn't find anything wr=
itten so here it is. The ideas towards anchor outputs and the conclusions=
 probably have some new perspectives.<br />
<br />
This post is about the game-theoretic security of time-sensitive protocol=
s if miners are open to censorship for a reward. To become practical, the=
 following has to happen.<br />
<br />
1) a substantial hashrate has to be willing to participate in this behavi=
our, according to the known formula from the Whitepaper. The more blocks =
it takes to attack (defined by a particular protocol configuration and co=
uld be tuned), the exponentially higher % hashrate is required.<br />
<br />
2) a communication layer is required to send bribes to these miners. This=
 could be a private transaction relay network, or a mempool allowing stil=
l-time-locked transactions. It could be even an announcement board (e.g.,=
 submitting raw txs under a Twitter hashtag and inviting miners to monito=
r it).<br />
<br />
3) a bribe transaction construction (will be explained later).<br />
<br />
In this post, I talk about the case when:<br />
1. a significant hashrate (e.g., 95%+) is open to take these bribes;<br /=
>
2. but miners don't trust each other;<br />
3. and there is no reorgs.<br />
<br />
Assumption =5C*(2) is more nuanced. What I mean here is roughly =22miner =
X would rather take an immediate gain than commit to a lenghty scenario w=
here many miners coordinate to take reward on behalf of each other and th=
en distribute it accordingly to the hashrate=22. The game theory of this =
assumption should be better defined in the future.<br />
<br />
We will see, how widely known tweaks lift the bar for (2) and (3) and how=
 this could be further improved.<br />
<br />
*A special case of this scenario is miners withholding Alice's transactio=
n to force her to bump fees, even if Bob hasn't submitted a bribe. Here I=
 assume miners won't do it unless there is an external incentive (Bob's b=
ribe), although this issue is also interesting.*<br />
<br />
=23=23 Simple opcode-based construction<br />
<br />
The simplest time-sensitive two-party contract is PowSwap (a bet on the f=
uture block issuance rate), a single on-chain UTXO with the following spe=
nding conditions:<br />
- Alice=E2=80=99s key can spend if height=3DH is reached;<br />
- Bob=E2=80=99s key can spend if Time=3DT is reached.<br />
<br />
Say H is approaching quickly, and T is far behind. Bob now uses a private=
 mining relay to submit his non-mineable transaction paying e.g. half of =
the UTXO value towards fees.<br />
<br />
Alice has two problems: 1) she can=E2=80=99t figure out why her transacti=
on isn=E2=80=99t mined and how much fee to overpay; 2) the attack is free=
 for Bob (he has nothing to lose), while Alice loses everything up to the=
 full UTXO value.<br />
<br />
=23=23 Simple nLockTime-based construction<br />
<br />
If parties use pre-signed transactions with nLockTime (instead of the opc=
odes), Bob=E2=80=99s fee can be pre-signed to a rather low value, so that=
 Alice can reasonably overbid it without much loss (she probably doesn't =
even need to take any action).<br />
<br />
Bob can, however, bump the fee by creating a CP=46P transaction with supe=
r-high fee. All it requires now is submitting twice as much data to the p=
rivate mining relay (and burning slightly more in fees).<br />
<br />
=23=23 nLockTime-based construction with OP=5FCSV output<br />
<br />
If Bob=E2=80=99s output can=E2=80=99t be spent right away, but is forced =
to be deterred to even one block in the future, it makes taking this brib=
e not rational: a censoring miner can=E2=80=99t be sure about the deferre=
d reward (remember, miners don't trust each other). At the same time, min=
ing the honest transaction and taking its fee is always available earlier=
.<br />
<br />
Smart contracts could possibly make it rational for miners (see =5B1=5D),=
 e.g. by allowing Bob to allocate the bribe based on the historic hashrat=
e distribution linked to coinbase pubkeys.<br />
<br />
At the same time, this approach makes dynamic fee management impossible.<=
br />
<br />
=23=23 Anchor outputs<br />
<br />
Anchor outputs allow bringing external capital for fee management while l=
ocking internal capital. Bob can use this capital for a bribe. If the att=
ack fails, Bob's external capital remains safe, so this is not so bad for=
 Bob.<br />
<br />
The attack can be more costly if this external capital was claimable:<br =
/>
- by Alice: e.g., Alice can steal a (covenanted) anchor output if it's re=
vealed before Bob's nLockTime makes it mineable (requires her to monitor =
the private relay);<br />
- or by miners, e.g. if Alice forces Bob, at contract setup, to use a rev=
erse time-lock (the anchor can be stolen by miner if seen before time=3DT=
); or if mining Alice's honest transaction also allows miners to take Bob=
's fee output (e.g., Alice's honest transaction *could* act as a parent/p=
reimage, conditionally, although this may require reverse time-locking Al=
ice to protect Bob...)<br />
<br />
*Ephemeral anchors doesn=E2=80=99t do much w.r.t. our trade-off, as it is=
 a mempool-oriented thing.*<br />
<br />
=23=23 Lightning<br />
<br />
Lightning is different from the described protocol in two things:<br />
1) It relies on intermediate transactions (e.g., Commitment in Poon-Dryja=
);<br />
2) Usually both parties have some balance in the channel.<br />
<br />
I believe that (1) doesn=E2=80=99t change the situation much, it just mak=
es it more nuanced.<br />
(2) is irrelevant because an attacker can just spend the entire channel b=
efore the attack.<br />
Thus, most of these concerns apply to lightning equally.<br />
<br />
=23=23 Related work<br />
<br />
The LN paper briefly mentioned this problem, although it was claimed impr=
actical due to a high degree of required collusion. We already see privat=
e mining relay in&=23160;<a href=3D=22http://mevwatch.info=22 target=3D=22=
=5Fblank=22>mevwatch.info</a>&=23160;(ethereum), and we had =46IBRE (I th=
ink it was neutral).<br />
<br />
=5B2=5D discussed constructions and economics for bribing miners. =5B1=5D=
 suggests more practical considerations for achieving this. Both don=E2=80=
=99t focus on the risks of particular time-sensitive protocol constructio=
ns.<br />
<br />
=5B3=5D highlighted a similar protocol risk, but the proposed solution se=
ems to work only if an attacker has funds to lose locked in the contract =
(e.g., collateral, lightning balance, powswap payout).<br />
<br />
=23=23 Conclusions<br />
<br />
To increase the attack bar w.r.t the configuration described in the intro=
, we should either:<br />
- stick to the *nLockTime-based construction with OP=5FCSV output*, forge=
t about dynamic fee management, and hope that bribe allocation smart cont=
racts doesn't work out;<br />
- use anchor outputs (or another external fee scheme), but enforce a way =
to steal/burn the external fee if it's an attack;<br />
- design new fee/channel constructions.<br />
<br />
These ideas may also be helpful for alternative payment channels designs =
as well (v3+ephemeral anchors, SIGHASH=5FGROUP, etc.), or in the future t=
o protect against more powerful covenants allowing stronger bribes (see =5B=
1=5D).<br />
<br />
Thanks to Antoine Riard and Greg Sanders for initial discussion.<br />
<br />
-------------------------<br />
<br />
=23=23 References<br />
<br />
1. TxWithhold Smart Contracts by Gleb Naumenko =7C BitMEX Blog (<a href=3D=
=22https://blog.bitmex.com/txwithhold-smart-contracts/=22 target=3D=22=5F=
blank=22>https://blog.bitmex.com/txwithhold-smart-contracts/</a>)<br />
2. Temporary Censorship Attacks in the Presence of Rational Miners (<a hr=
ef=3D=22https://eprint.iacr.org/2019/748.pdf=22 target=3D=22=5Fblank=22>h=
ttps://eprint.iacr.org/2019/748.pdf</a>)<br />
3. MAD-HTLC: Because HTLC is Crazy-Cheap to Attack (<a href=3D=22https://=
arxiv.org/pdf/2006.12031.pdf=22 target=3D=22=5Fblank=22>https://arxiv.org=
/pdf/2006.12031.pdf</a>)</div>
</div>
</body>
</html>

--63db76eb_75a2a8d4_5b0--