rhavar at protonmail.com [ARCHIVE] on Nostr: 📅 Original date posted:2019-06-10 📝 Original message:What about this? We store ...
📅 Original date posted:2019-06-10
📝 Original message:What about this? We store a RBU ("relay bandwidth used") with each transaction in the mempool. Where RBU is defined as the size of the transaction + RBU of all transactions it has evicted.
For a replacement to be valid: The feerate must be higher than what it's evicting, and the fee must be greater than minRelayFee*RBU.
-Ryan
‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Sunday, June 9, 2019 7:07 AM, David A. Harding via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
> On Thu, Jun 06, 2019 at 02:46:54PM +0930, Rusty Russell via bitcoin-dev wrote:
>
> > Matt Corallo lf-lists at 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)
>
>
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
📝 Original message:What about this? We store a RBU ("relay bandwidth used") with each transaction in the mempool. Where RBU is defined as the size of the transaction + RBU of all transactions it has evicted.
For a replacement to be valid: The feerate must be higher than what it's evicting, and the fee must be greater than minRelayFee*RBU.
-Ryan
‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Sunday, June 9, 2019 7:07 AM, David A. Harding via bitcoin-dev <bitcoin-dev at lists.linuxfoundation.org> wrote:
> On Thu, Jun 06, 2019 at 02:46:54PM +0930, Rusty Russell via bitcoin-dev wrote:
>
> > Matt Corallo lf-lists at 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)
>
>
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev