Date: Sun, 9 Jun 2019 10:07:36 -0400
From: "David A. Harding" <dave@dtrt.org>
To: Rusty Russell <rusty@rustcorp.com.au>,
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20190609140334.upcqalp24zrecwye@ganymede>
References: <871s0c1tvg.fsf@rustcorp.com.au>
	<F252D824-5BE6-4B03-B59D-D40EAFBAEE84@mattcorallo.com>
	<871s07nvi1.fsf@rustcorp.com.au>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <871s07nvi1.fsf@rustcorp.com.au>
User-Agent: NeoMutt/20170113 (1.7.2)
Subject: Re: [bitcoin-dev] [PROPOSAL] Emergency RBF (BIP 125)
Precedence: list

On Thu, Jun 06, 2019 at 02:46:54PM +0930, Rusty Russell via bitcoin-dev wrote:
> Matt Corallo <lf-lists@mattcorallo.com> writes:
> > 2) wrt rule 4, I'd like to see a calculation of worst-case free
> > relay. I think we're already not in a great place, but maybe it's
> > worth it or maybe there is some other way to reduce this cost
> > (intuitively it looks like this proposal could make things very,
> > very, very bad).
> 
> I *think* you can currently create a tx at 1 sat/byte, have it
> propagate, then RBF it to 2 sat/byte, 3... and do that a few thousand
> times before your transaction gets mined.

Yes, the current incremental relay fee in Bitcoin Core is 0.00001000
BTC/KvB.

> If that's true, I don't think this proposal makes it worse.

Here's a scenario that I think shows it being at least 20x worse.

Let's imagine that you create two transactions:

  tx0: A very small transaction (~100 vbytes) that's just 1-in, 1-out.
       At the minimum relay fee, this costs 0.00000100 BTC

  tx1: A child of that transaction that's very large (~100,000 vbytes,
       or almost 400,000 bytes using special scripts that allow witness
       stuffing).  At the minimum relay fee, this costs 0.00100000 BTC

Under the current rules, if an attacker wants to fee-bump tx0 by the
minimum incremental fee (a trivial amount, ~0.00000100 BTC), the
attacker's replacement also needs to pay for the eviction of the huge
child tx1 by that same incremental fee (~0.00100000).

Thus the replacement would cost the attacker a minimum of about
0.00100100 (~1 mBTC) for the original transactions and 0.00100100 for
the replacement (about 2 mBTC total).

The attacker could then spend another 1 mBTC re-attaching the child and
yet another 1 mBTC bumping again, incuring about a 2 mBTC cost per
replacement round.  At writing, 2 mBTC is about $14.00 USD---an amount
that's probably enough to deter most attacks at scale.

* * *

Under the new proposed rule 6, Mallory's replacement cost would be the
amount to get the small tx0 to near the top of the mempool (say
0.00100000 BTC/KvB, so 0.00010000 BTC total).  Because this would evict
the expensive child, it would actually reduce the original amount paid
by the attacker by 90% compared to the previous section's example where
using RBF increased the original costs by 100%.

The 0.1 mBTC cost of this attack is about $0.70 USD today for the
roughly the same data relay use as one round of the currently possible
attack.  In short, if I haven't misplaced a decimal point or made some
other mistake, I think the proposed rule 6 would result in approximately
a 95% reduction in the cost paid by an attacker for wasting 400,000
bytes of bandwidth per node (x60,000 nodes = 24 GB across all nodes, not
counting INV overhead).

Although the attacker might only get one replacement per block per
transaction pair out of this version of the attack, they could execute
the attack many times in parallel using different tranaction pairs.  If
this is combined with the treadmill leapfrogging Russell O'Connor
described elsewhere in this thread, the attack could possibly be
repeated multiple times per block per transaction pair at only slightly
increased cost (to pay the increasing next-block transaction fees).

> >> 3) wrt rule 5, I'd like to see benchmarks, it's probably a pretty
> >> nasty DoS attack, but it may also be the case that is (a) not worse
> >> than other fundamental issues or (b) sufficiently expensive.
> 
> I thought we still meet rule 5 in practice since bitcoind will never
> even accept a tree of unconfirmed txs which is > 100 txs?  That would
> still stand, it's just that we'd still consider a replacement.

Although the BIP125 limit is 100, Bitcoin Core's current default is 25.[1]
(When RBF was implemented in Bitcoin Core, transaction ancestry was only
tracked for purposes of ensuring valid transaction ordering within
blocks; later when CPFP was implemented, ancestry was additionally used
to calculate each transaction's package fee---the value of it and all
its unconfirmed ancestors.  This requires more computation to update
the mempool metadata when the ancestry graph changes.)

Again, I'd be thinking here of something similar to O'Connor's
treadmilling attack where replacements can push each other out of the
top mempool and so create enough churn for a CPU exhaustion attack.

> >>  Obviously there is also a ton more client-side knowledge required
> >>  and complexity to RBF decisions here than other previous, more
> >>  narrowly-targeted proposals.
> I'd say from the lightning side it's as simple as a normal RBF policy
> until you get within a few blocks of a deadline, then you increase the
> fees until it's well within reach of the next block.

It's already hard for wallet software to determine whether or not its
transactions have successfully been relayed.  This proposal requires LN
wallets not only be able to guess where the next-block feerate boundary
is in other nodes' individual mempools (now and in the future for the
time it takes the transaction to propagate to ~100% of miners), but it
possibly requires that under the condition that the LN wallet can't
guess too low because it might not get another chance for relay in the
limited time available before contract expiration.

On top of that, there's O'Connor's suggestion to increase treadmilling
costs by only allowing bumps if they're in the top-half of the
next-block mempool.

Considered that way, I worry that these constraints produce a recipe for
paying extremely high feerates.  If that's an actual risk, is that
actually significantly better than dealing with the existing transaction
pinning issue where one needs to pay a high total fee in order to evict
a bunch of junk descendents?  Paying lots of fees may not be the optimal
solution to the problem of having to pay lots of fees.  :-)

-Dave

[1] Excerpt from bitcoind -help-debug :

  -limitancestorcount=<n>
       Do not accept transactions if number of in-mempool ancestors is <n> or
       more (default: 25)

  -limitdescendantcount=<n>
       Do not accept transactions if any ancestor would have <n> or more
       in-mempool descendants (default: 25)