Date: Mon, 10 Jun 2019 16:34:33 +0000
To: "David A. Harding" <dave@dtrt.org>,
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: rhavar@protonmail.com
Reply-To: rhavar@protonmail.com
Message-ID: <Vc5Hs-nKxWVZNRQlA2vc0KTKPN29OtbkcyGmwQzRFk1oc5WME_j0cdFYHAGcU2p2Y9ozTNnXwYhjBS4UyULZkb6UKAxPgeDm8ld3BpJ_VDs=@protonmail.com>
In-Reply-To: <20190609140334.upcqalp24zrecwye@ganymede>
References: <871s0c1tvg.fsf@rustcorp.com.au>
	<F252D824-5BE6-4B03-B59D-D40EAFBAEE84@mattcorallo.com>
	<871s07nvi1.fsf@rustcorp.com.au>
	<20190609140334.upcqalp24zrecwye@ganymede>
Feedback-ID: RdfuD--Ffc-FNb_4UIG1XA3s5stj1f6Yt84KENdha_3WoiW3STYpu7X5uGR72LvTfQZpxEhSRHGSlNfV5XM5RA==:Ext:ProtonMail
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] [PROPOSAL] Emergency RBF (BIP 125)
Precedence: list

What about this? We store a RBU ("relay bandwidth used") with each transact=
ion in the mempool. Where RBU is defined as the size of the transaction + R=
BU of all transactions it has evicted.

For a replacement to be valid: The feerate must be higher than what it's ev=
icting, and the fee must be greater than minRelayFee*RBU.


-Ryan

=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90 Original Me=
ssage =E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90=E2=80=90
On Sunday, June 9, 2019 7:07 AM, David A. Harding via bitcoin-dev <bitcoin-=
dev@lists.linuxfoundation.org> wrote:

> On Thu, Jun 06, 2019 at 02:46:54PM +0930, Rusty Russell via bitcoin-dev w=
rote:
>
> > 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 =3D 24 GB across all nodes, no=
t
> 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 w=
orse
> > > >     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 poli=
cy
> > > > 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=3D<n>
>
>        Do not accept transactions if number of in-mempool ancestors is <n=
> or
>
>        more (default: 25)
>
>
> -limitdescendantcount=3D<n>
>
>        Do not accept transactions if any ancestor would have <n> or more
>
>        in-mempool descendants (default: 25)
>
>
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev