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>
MIME-Version: 1.0
Content-Type: multipart/alternative; boundary="63db76eb_75a2a8d4_5b0"
Subject: [bitcoin-dev] Costless bribes against time-sensitive protocols
Precedence: list

--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--