From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 85148C002B for ; 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 ; 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 ; 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 ; Thu, 2 Feb 2023 08:40:15 +0000 (UTC) Received: by mail-ed1-x532.google.com with SMTP id u21so1219840edv.3 for ; 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 (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 To: bitcoin-dev@lists.linuxfoundation.org Message-ID: In-Reply-To: References: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
=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.<= br />
=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&=23160;mevwatch.info&=23160;(ethereum), and we had =46IBRE (I th= ink 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://blog.bitmex.com/txwithhold-smart-contracts/)
2. Temporary Censorship Attacks in the Presence of Rational Miners (h= ttps://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--