A Free-Relay Attack Exploiting Min-Relay-Fee Differences

It's common for some nodes, especially miners, to have larger than default mempools, leading to lower-than-normal minrelayfees. This can be exploited for free-relay attacks as follows:

1. Publish tx A, with an unusually low fee-rate, below typical
   min-relay-fees, but with a sufficient size to have a reasonably large absolute
   fee. In my experience it is not difficult to get very low fee rate
   transactions mined if they're broadcast by well-connected nodes. Specific
   connections to miners is not required.

2. Publish B, double-spending A, with a fee-rate high enough to be accepted by
   most mempools. But with a total fee less than A.

3. Publish C, spending B, with a low fee rate and large size. Nodes with A will
   not accept C, as it spends a txout that they're not aware of.

4. To recover funds, double-spend A with A', with a sufficiently high fee-rate
   to get mined.

Since package replacement has not been implemented, the combination of C and B will not replace A, and the total cost of the attack will be limited to the cost of spending A.

As usual, C can in turn be double-spent at higher and higher fee-rates. C could also be double-spent across multiple different nodes with different, almost identical, variants of C.

# Mitigation

Package replacement. Though it is still economically irrational for miners to "mitigate" this attack: they earn more money by simply mining the high fee-rate A', with replace-by-fee-rate.

# Responsible Disclosure

You're reading it. Since this type of attack is public, other variants of attacks along these lines should just be openly discussed. Better to have plenty of people who understand the issue so there's lots of eyes on potential fixes.