Re: [bitcoin-dev] One-Shot Replace-By-Fee-Rate
On Sun, Jan 28, 2024 at 12:27:06PM -0500, Murch via bitcoin-dev wrote: > I agree in the detail, but not about the big picture. You are right that > it’s a problem that `tx_LM` and `tx_HS` spend the same input and therefore > are direct conflicts. > > Luckily, it is unnecessary for my scenario that `tx_LM` and `tx_HS` > conflict. The scenario only requires that `tx_LM` conflicts with `tx_LL` and > `tx_RBFr`. `tx_HS` is supposed to get dropped indirectly per the conflict > with `tx_LL`. > > It seems to me that my example attack should work when a third confirmed > input `c3` is introduced as follows: > `tx_LM` spends `c3` instead of `c2`, and `tx_RBFr` spends both `c2` and > `c3`, which allows the following four conflicts: > > - `tx_HS` and `tx_RBFr` conflict on spending `c2` > - `tx_HS` and `tx_LS` conflict on spending `tx_LL:0` > - `tx_LL` and `tx_LM` conflict on spending `c1` > - `tx_LM` and `tx_RBFr` conflict on spending `c3` > > `tx_RBFr` would end up slightly bigger and therefore have a bigger fee, but > otherwise the number should work out fine as they are. > I have not verified this yet (thanks for sharing your code), but I might be > able to take another look in the coming week if you haven’t by then. > > It seems to me that my main point stands, though: the proposed RBFr rules > would enable infinite replacement cycles in combination with the existing > RBF rules. Yes, *that* version of the attack does work, and I was able to succesfully create a modified version of the previous script that demonstrates it on a regtest node. The attack is still exploiting a failure of our current RBF rules: the replacement of tx_RBFr with tx_HS represents a fee-rate/mining score decrease that replaces a more profitable transaction, tx_RBFR, with an much less profitable transaction, ts_HS. Notably, I belive that sdaufter's "Enforce incentive compatibility" pull-req(1) would reject it, though I haven't actually tested that. To fix this issue I've added a commit(2) to the libre-relay-v26.0 branch that rejects replacements that spend unconfirmed inputs if the replacement is conflicting with multiple transactions at once. Let's look at why this change fixes the issue, making cycles impossible. Bitcoin Core already uses the term "mining score" to try to measure the profitability of a transaction. We'll define a similar measure, fee-rate-depth, a tuple consisting of the raw fee-rate of a transaction and the depth of the transaction, in terms of the maximum depth of unconfirmed parents that must be mined for the transaction to be mined. The fee-rate-depth is improved if the fee-rate is increased and/or the depth is decreased. For example suppose we have the following unconfirmed transaction graph: t1 <- t2 <- t3 The depth of t1 is 0, as it only spends confirmed inputs. The depth of t2 is 1, as it spends a 0-depth transaction, and the depth of t3 is 2, as it spends a 1-depth transaction. Suppose we have a new transaction, t2b, that conflicts with t2, and with fee-rates t2 < t2b < t3. Assuming that the total fee paid by t2b is high enough, an RBF replacement is allowed: t1 <- t2b While t3 paid a higher fee-rate than t2b, the fee-rate-depth has still improved, because the depth of t2b is less than the depth of t3. With this new change, is the fee-rate-depth always improved? Yes. Rule #6/PaysMoreThanConflicts ensures that the fee-rate of direct conflicts is always improved by the replacement. With *indirect* conflicts, while the fee-rate may or may not be improved, the *depth* is improved, because we are replacing a deeper transaction with a shallower transaction. Secondly, for direct replacements the modified HasNoNewUnconfirmed function ensures that the depth of fee-rate-depth is never made worse by prohibiting the replacement of shallower transactions with deeper transactions. This is impossible because with the new rule, if a transaction has any unconfirme dinputs at all - a non-zero depth - only a single transaction is allowed to be replaced at a time. Thus at worse the depth will remain constant, while rule #6 will ensure that the fee-rate is improved. Obviously, we could probably improve on this further with more nuanced rules. But the HasNoNewUnconfirmed fix is simple to implement, and in practice shouldn't affect very many use-cases. Pretty much all replacements of transactions spending unconfirmed outputs is for CPFP, and I'm not actually aware of any wallets that try to batch CPFP transactions together. There probably are some. But it's certainly not common. That's sufficient for the purposes of Libre Relay, whose replace-by-fee-rate implementation is intended as a prototype to validate the idea. 1) https://github.com/bitcoin/bitcoin/pull/26451 2) https://github.com/petertodd/bitcoin/commit/fec7965277c2287d3eaba59fdc5b75729bd4838a -- https://petertodd.org 'peter'[:-1]@petertodd.org signature.asc Description: PGP signature ___
Re: [bitcoin-dev] One-Shot Replace-By-Fee-Rate
Hi Peter, Thanks you for investigate my concern and replicate the scenario I drafted. On 27.01.24 02:19, Peter Todd wrote: I actually tried this attack out, and it fails at step #4 due to the Rule #6, PaysMoreThanConflicts, check. While on stacker.news you stated that: tx_HS has 5000 vB and pays 21 s/vB, but since it spends an output from a low-feerate parent, it’s mining score is only 1.95 s/vB. and You RBF tx_LL and tx_HS with tx_LM that has 100,000 vB and pays 3.05 s/vB (fee: 305,000 s) by spending the outputs C1 and C2. This is permitted, since only tx_LL is a direct conflict, so the feerate of tx_HS does not have to be beat directly. tx_HS _is_ considered to be a direct conflict, and its raw fee-rate _does_ have to be beat directly. While ts_HS does spend an unconfirmed output, it appears that the fee-rate PaysMoreThanConflicts uses to calculate if ts_HS can be beaten is ts_HS's raw fee-rate. So looks like your understanding was incorrect on these two points. I agree in the detail, but not about the big picture. You are right that it’s a problem that `tx_LM` and `tx_HS` spend the same input and therefore are direct conflicts. Luckily, it is unnecessary for my scenario that `tx_LM` and `tx_HS` conflict. The scenario only requires that `tx_LM` conflicts with `tx_LL` and `tx_RBFr`. `tx_HS` is supposed to get dropped indirectly per the conflict with `tx_LL`. It seems to me that my example attack should work when a third confirmed input `c3` is introduced as follows: `tx_LM` spends `c3` instead of `c2`, and `tx_RBFr` spends both `c2` and `c3`, which allows the following four conflicts: - `tx_HS` and `tx_RBFr` conflict on spending `c2` - `tx_HS` and `tx_LS` conflict on spending `tx_LL:0` - `tx_LL` and `tx_LM` conflict on spending `c1` - `tx_LM` and `tx_RBFr` conflict on spending `c3` `tx_RBFr` would end up slightly bigger and therefore have a bigger fee, but otherwise the number should work out fine as they are. I have not verified this yet (thanks for sharing your code), but I might be able to take another look in the coming week if you haven’t by then. It seems to me that my main point stands, though: the proposed RBFr rules would enable infinite replacement cycles in combination with the existing RBF rules. Murch ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] One-Shot Replace-By-Fee-Rate
On Mon, Jan 22, 2024 at 01:12:45PM -0500, Murch via bitcoin-dev wrote:
> Hi Peter,
>
> On 1/18/24 13:23, Peter Todd via bitcoin-dev wrote:
> > Reposting this blog post here for discussion:
> >
> > https://petertodd.org/2024/one-shot-replace-by-fee-rate
>
> I saw your proposal mentioned on Stacker News and read it with interest. In
> response, I described a replacement cycle that can be used to broadcast the
> same five transactions repeatedly:
>
> https://stacker.news/items/393182
>
> The gist is that by using two confirmed inputs and five transactions, you
> can use RBFr to reduce the absolute fee while raising the feerate to top
> block levels, then immediately use the current RBF rules to introduce a
> high-feerate transaction that beats the RBFr transaction but is hampered by
> a low-feerate parent and not attractive for mining, then use RBF to replace
> its low-feerate parent, then use the RBFr transaction again to reduce the
> absolute feerate. Due to the asymmetric replacements, the same transactions
> can replace each other in that order in every cycle. Please refer to the
> linked write-up for details, I’ve included weights, fees, and a transaction
> graph to make my example comprehensible.
>
> Among those five transactions, the only transaction attractive for block
> inclusion would be the small RBFr transaction with a
> bottom-of-the-next-block feerate. Today, if it were mined it would amount to
> fees of around 4000 sats every few blocks to make the entire network relay
> transactions of more than 205,000 vB every few seconds. Given that my
> example is minimal, it should be possible to further increase bandwidth
> cost.
>
> Assuming that I did not make a mistake, i.e. all the replacements are viable
> and my scenario is compatible with your proposal, the described One-Shot
> Replace-By-Fee-Rate proposal would not be safe for deployment on the
> network.
I actually tried this attack out, and it fails at step #4 due to the Rule #6,
PaysMoreThanConflicts, check.
While on stacker.news you stated that:
tx_HS has 5000 vB and pays 21 s/vB, but since it spends an output from a
low-feerate parent, it’s mining score is only 1.95 s/vB.
and
You RBF tx_LL and tx_HS with tx_LM that has 100,000 vB and pays 3.05 s/vB
(fee:
305,000 s) by spending the outputs C1 and C2. This is permitted, since only
tx_LL is a direct conflict, so the feerate of tx_HS does not have to be beat
directly.
tx_HS _is_ considered to be a direct conflict, and its raw fee-rate _does_ have
to be beat directly. While ts_HS does spend an unconfirmed output, it appears
that the fee-rate PaysMoreThanConflicts uses to calculate if ts_HS can be
beaten is ts_HS's raw fee-rate. So looks like your understanding was incorrect
on these two points.
FYI here is the actual test script I used to test this attack. You can run it
using Bitcoin v26.0 with the -acceptnonstdtxn -mempoolfullrbf=1 command line
arguments, with python-bitcoinlib v0.12.2 installed.
#!/usr/bin/env python3
import bitcoin
bitcoin.SelectParams('regtest')
import bitcoin.rpc
import sys
from bitcoin.core import *
from bitcoin.core.script import *
from bitcoin.wallet import *
proxy = bitcoin.rpc.Proxy()
my_addr = proxy.getnewaddress().to_scriptPubKey()
coins = proxy.listunspent(1)
print(coins[0:2])
txo1 = coins[0]['outpoint']
txo1_amount = coins[0]['amount']
txo2 = coins[1]['outpoint']
txo2_amount = coins[1]['amount']
print(txo1)
print(txo2)
for i in range(0, 1):
# Step 2
tx_ll = CTransaction(
[CTxIn(txo1)],
[CTxOut(txo1_amount - 10, my_addr),
CTxOut(0, CScript([OP_RETURN, b'x' * 9]))])
r = proxy.signrawtransactionwithwallet(tx_ll)
assert(r['complete'])
tx_ll_signed = r['tx']
print('tx_ll = %s' % b2lx(proxy.sendrawtransaction(tx_ll_signed)))
tx_ls = CTransaction(
[CTxIn(COutPoint(tx_ll.GetTxid(), 0))],
[CTxOut(txo1_amount - 10 - 300, my_addr)])
r = proxy.signrawtransactionwithwallet(tx_ls)
assert(r['complete'])
tx_ls_signed = r['tx']
print('tx_ls = %s' % b2lx(proxy.sendrawtransaction(tx_ls_signed)))
# Step 3
tx_hs = CTransaction(
[CTxIn(COutPoint(tx_ll.GetTxid(), 0)),
CTxIn(txo2)],
[CTxOut((txo1_amount - 10) + txo2_amount - 4000, my_addr)])
r = proxy.signrawtransactionwithwallet(tx_hs)
assert(r['complete'])
tx_hs_signed = r['tx']
print('tx_hs = %s ' % b2lx(proxy.sendrawtransaction(tx_hs_signed)))
# Step 4
tx_lm = CTransaction(
[CTxIn(txo1),
CTxIn(txo2)],
[CTxOut(txo1_amount + txo2_amount - 30, my_addr),
CTxOut(0, CScript([OP_RETURN, b'x' * 9]))])
r = proxy.signrawtransactionwithwallet(tx_lm)
assert(r['complete'])
tx_lm_signed = r['tx']
print('tx_lm = %s' % b2lx(proxy.sendrawtransaction(tx_lm_signed)))
signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
Re: [bitcoin-dev] One-Shot Replace-By-Fee-Rate
Hi Peter, On 1/22/24 17:52, Peter Todd wrote: An even simpler fix would be to just require that all unconfirmed inputs in a replacement come from the *same* replaced transaction. That would make certain rare, but economically viable, replacements infeasible. But it would definitely fix the issue. The replacements spend at most a single unconfirmed input in my infinite relay cycle example. Murch ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] One-Shot Replace-By-Fee-Rate
On Mon, Jan 22, 2024 at 10:52:01PM +, Peter Todd via bitcoin-dev wrote: > An even simpler fix would be to just require that all unconfirmed inputs in a > replacement come from the *same* replaced transaction. That would make certain > rare, but economically viable, replacements infeasible. But it would > definitely > fix the issue. FYI I've implemented this fix, and pure replace-by-fee-rate with a minimum 2x fee-rate increate, in my Libre Relay fork: https://github.com/petertodd/bitcoin/tree/libre-relay-v26.0 Similar to my full-RBF peering fork, it uses a new service bit to ensure it's peering with other Libre Relay nodes to make transaction propagation actually works. I wouldn't call this a "public" release at this point. But people are welcome to review the code and try it out. I have a few mainnet and testnet nodes running it right now. I'm *very* interested if anyone else can find any further exploits in the pure replace-by-fee-rate code. I'm also interested to see if anyone bothers to spend the money to do the well-known, and expensive, replace-by-fee-rate DoS attacks. The fun thing about this release, is Libre Relay also removes the restrictions on OP_Return, which I'm sure will make some people quite angry... So maybe that'll give someone an incentive to attack it. :D I'm already sufficiently well connected to get oversized OP_Return's mined. So if you want to do that too, running a Libre Relay node will work. -- https://petertodd.org 'peter'[:-1]@petertodd.org signature.asc Description: PGP signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] One-Shot Replace-By-Fee-Rate
On Mon, Jan 22, 2024 at 01:12:45PM -0500, Murch via bitcoin-dev wrote: > Hi Peter, > > On 1/18/24 13:23, Peter Todd via bitcoin-dev wrote: > > Reposting this blog post here for discussion: > > > > https://petertodd.org/2024/one-shot-replace-by-fee-rate > > I saw your proposal mentioned on Stacker News and read it with interest. In > response, I described a replacement cycle that can be used to broadcast the > same five transactions repeatedly: > > https://stacker.news/items/393182 So if this does in fact work - I haven't actually tested it - the root problem here is not replace-by-fee-rate, but rather our current replace-by-fee rules: in step 7 you've clearly replaced a more desirable, high fee-rate, transaction that will be mined soon with a low fee-rate transaction that will not be. That's obviously not incentive compatible for miners, for the same reason that replace-by-fee-rate generally is incentive compatible. I had incorrectly thought we had gotten rid of those cases... But looks like the definition of BIP-125 Rule #2, "The replacement transaction may only include an unconfirmed input if that input was included in one of the original transactions.", is not sufficient because you can combine unconfirmed inputs from two different replaced transactions, making a resulting transaction that is less valuable to miners than one of the replaced transactions. IIUC Suhas has a draft fix here that would solve this issue: https://github.com/bitcoin/bitcoin/pull/26451 An even simpler fix would be to just require that all unconfirmed inputs in a replacement come from the *same* replaced transaction. That would make certain rare, but economically viable, replacements infeasible. But it would definitely fix the issue. > The gist is that by using two confirmed inputs and five transactions, you > can use RBFr to reduce the absolute fee while raising the feerate to top > block levels, then immediately use the current RBF rules to introduce a > high-feerate transaction that beats the RBFr transaction but is hampered by > a low-feerate parent and not attractive for mining, then use RBF to replace > its low-feerate parent, then use the RBFr transaction again to reduce the > absolute feerate. Due to the asymmetric replacements, the same transactions > can replace each other in that order in every cycle. Please refer to the > linked write-up for details, I’ve included weights, fees, and a transaction > graph to make my example comprehensible. BTW do you mind if I reproduce those graphics, with credit, to explain the issue? I have a few places where I could make use of it, eg the replace-by-fee-rate post itself. -- https://petertodd.org 'peter'[:-1]@petertodd.org signature.asc Description: PGP signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] One-Shot Replace-By-Fee-Rate
Hi Peter, On 1/18/24 13:23, Peter Todd via bitcoin-dev wrote: > Reposting this blog post here for discussion: > > https://petertodd.org/2024/one-shot-replace-by-fee-rate I saw your proposal mentioned on Stacker News and read it with interest. In response, I described a replacement cycle that can be used to broadcast the same five transactions repeatedly: https://stacker.news/items/393182 The gist is that by using two confirmed inputs and five transactions, you can use RBFr to reduce the absolute fee while raising the feerate to top block levels, then immediately use the current RBF rules to introduce a high-feerate transaction that beats the RBFr transaction but is hampered by a low-feerate parent and not attractive for mining, then use RBF to replace its low-feerate parent, then use the RBFr transaction again to reduce the absolute feerate. Due to the asymmetric replacements, the same transactions can replace each other in that order in every cycle. Please refer to the linked write-up for details, I’ve included weights, fees, and a transaction graph to make my example comprehensible. Among those five transactions, the only transaction attractive for block inclusion would be the small RBFr transaction with a bottom-of-the-next-block feerate. Today, if it were mined it would amount to fees of around 4000 sats every few blocks to make the entire network relay transactions of more than 205,000 vB every few seconds. Given that my example is minimal, it should be possible to further increase bandwidth cost. Assuming that I did not make a mistake, i.e. all the replacements are viable and my scenario is compatible with your proposal, the described One-Shot Replace-By-Fee-Rate proposal would not be safe for deployment on the network. Best, Murch ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
[bitcoin-dev] One-Shot Replace-By-Fee-Rate
Reposting this blog post here for discussion:
https://petertodd.org/2024/one-shot-replace-by-fee-rate
---
layout: post
title: "One-Shot Replace-by-Fee-Rate"
date: 2024-01-18
tags:
- bitcoin
- rbf
- pinning
---
Currently Bitcoin Core implements a Replace-by-Fee (RBF) policy, where
transactions are not replaced unless the new transaction pays at least a higher
total fee than the replaced transaction, regardless of fee-rate.
When RBF was first implemented over 8 years ago this was a reasonable,
conservative, default. However, since then we've found that strictly requiring
a higher absolute fee creates the potential for [transaction
pinning](https://bitcoinops.org/en/topics/transaction-pinning/) attacks in
contracting protocols such as Lightning; replacing transactions based on
*fee-rate* would make it possible[^bip125-rule-5-pinning] to eliminate these
attacks by eliminating BIP-125 Rule #3 pinning.
[^bip125-rule-5-pinning]: The other notable pinning attack against RBF is to
cause BIP-125 Rule #5 to be exceeded. But that is easily solved by just
rejecting transactions that would make transactions already in the mempool to
be irreplaceable.
Here we will propose an incentive compatible solution, One-Shot
Replace-By-Fee-Rate, that mitigates prior concerns over replace-by-fee-rate
policies by allowing the replacement to only happen when it would immediately
bring a transaction close enough to the top of the mempool to be mined in the
next block or so. Finally, we will show that both one-shot and pure
replace-by-fee-rate policies sufficiently resist bandwidth exhaustion attacks
to be implementable.
*Thanks goes to [Fulgur Ventures](https://fulgur.ventures/) for sponsoring this
research. They had no editorial control over the contents of this post and did
not review it prior to publication.*
# Contents
{:.no_toc}
0. TOC
{:toc}
## Background
### The Expected Return of an Unconfirmed Transaction
Suppose there exists a transaction that pays a fee of $$F$$ at a fee-rate $$r$$.
What is the expected return $$E$$ of that transaction to miners as a whole? If
the transaction pays a fee-rate high enough to definitely get mined in the next
block, the answer seems obvious: $$E = F$$. The transaction will be mined, and
miners as a whole will earn the entire $$F$$ fee.
But what if that transaction pays a lower fee-rate? For example, as I write
this, [mempool.space](https://mempool.space) reports that their mempool
contains $$535\mathrm{MvB}$$ of transactions, enough that a typical Bitcoin
Core node with its typical $$300\mathrm{MB}$$ mempool size limit would reject
transactions paying less than $$22.9\frac{\mathrm{sat}}{\mathrm{vB}}$$.
If a transaction has a fee-rate of $$23\frac{\mathrm{sat}}{\mathrm{vB}}$$, just
barely enough to get into a default mempool, what is that transaction worth to
miners? How do we even answer this question?
Intuitively it seems obvious that the low fee-rate transaction should be worth
less than the high fee-rate transaction, because
the low fee-rate transaction probably won't be mined for days, or even weeks,
if ever.
Certainly, in a shorter time frame, a transaction at the bottom of the mempool
does not directly represent income to the miner.
We can think about this a bit more rigorously by observing that because block
finding is a Poisson Process, **even if** we ignore the supply of new
transactions, the probability that a transaction $$n$$ blocks deep is mined in
a time interval $$t$$ is the probability that $$N \ge n$$ blocks are found in
the time interval $$t$$. That probability rapidly diminishes as $$n$$
increases, because it's less and less likely for so many blocks to be found in
a short period of time.
### Unconfirmed Transactions are Honest Signals
Do low fee-rate transactions have a value? Yes!
Assuming your node is well connected, unconfirmed transactions in your mempool
are *honest signals*: because unconfirmed transactions *could* be mined,
they're clear evidence that if you wish your transaction to be mined sooner, you
need to offer an even higher fee-rate. There's a constant supply of people with
high time preference who want their transactions mined in a short period of
time. So low fee-rate transactions indirectly increase the revenue of miners in
the short term, because they force higher time preference transactors to outbid
them.
Note how I said a higher fee-rate, not fee: because it maximizes revenue to mine
transactions in fee-rate order, fee-rate is what matters in terms of priority.
### Expected Return vs Fee-Rate
Suppose we now have *two* different conflicting transactions, $$a$$ and $$b$$.
Suppose that the total size of $$a$$ is $$10\mathrm{vB}$$, and pays
$$23\frac{\mathrm{sat}}{\mathrm{vB}}$$, for a total fee of
$$230\mathrm{sat}$$. Meanwhile $$b$$ has a size of just $$150\mathrm{vB}$$,
and pays $$15000\frac{\mathrm{sat}}{\mathrm{vB}}$$, for a total fee of
$$225\mathrm{sat}$$.
It seems intuitive that transaction $$b$$ is the
