While further research is certainly a good idea, I push back pretty hard on this example!
You have already violated a major assumption here, by accepting a non-standard-size transaction. Yet we’ve already hand-waved over the bin-packing problem, accepting that it can be suboptimal in theory while Good Enough in practice. If this is untrue, we have other problems.
Simplicity and predictability itself is a virtue, as long as the result is congruent in practice: miners will almost certainly agree with this, as we’ve seen them lose real rewards by trying to be tricky with block construction in the past! (I posit, far more than more optimal packing strategies will gain them in their lives).
I think if we were to analyze the difference in practice we will end up so far below the engineering salary required to implement and vet the more complex scheme
Yes, the stratum2-gives-100% case was exactly why I suggested leaving this door firmly closed, and only considering the immediate next block in bitcoin. If some other implementation wants to implement a more complex system, they can do the work, and we can assess the damage at that time.
@rustyrussell
Sorry for the transaction size typo; I corrected my earlier post and added a footnote mentioning the error. With that correction made, do you still find the example objectionable?
My RBF policy suggestion is that we should allow a replacement transaction to evict some set of conflicts if:
the feerate diagram of the resulting mempool is strictly better, and
the total fees in the mempool go up by at least the min relay fee times the size of the new transaction
I’ll call this the “Feerate Diagram Policy”.
I think you’ve suggested an alternate RBF policy that would allow a replacement transaction to evict some set of conflicts if:
the new transactions would all appear in the next block, and
none of the conflicting transactions would have appeared in the next block
Is there any entry in this table that you’d disagree with?
The Next Block Policy seems to land in a region that we should avoid, namely of failing to guarantee incentive compatibility while also opening up the network to DoS (the example I gave in the OP shows a DoS vector that is possible when total fees are allowed to drop, which is relevant here).
My immediate proposal – part of the cluster mempool design – is that we switch our RBF acceptance rules to follow the Feerate Diagram Policy I described above (the rationale for which is laid out in the OP). This by itself doesn’t “solve” the pinning issues that occur when low-feerate children are attached to transactions, but for all the reasons I’ve laid out we don’t currently have even an incentive compatibility framework that allows us to know under what circumstances allowing total fees to drop might be okay, let alone a DoS-resistant mechanism for doing so.
Instead, I think relay rules like the v3 relay policy (V3 transaction policy for anti-pinning) are our best bet to mitigate pinning vectors for the foreseeable future.
And in the long-run, maybe someone can come up with an anti-DoS design that works better on an open network than what we’ve come up with so far, and if that is coupled with a better understanding of what is incentive compatible, then maybe there will be room for alternate pinning solutions…? (I don’t think anyone should count on this being invented anytime soon!)
I don’t know if the Next Block Policy proposal would also layer on the Feerate Diagram Policy when considering replacements that wouldn’t touch the top block; if so then the answer here should be “maybe”. But if the Next Block Policy always rejected replacements that would be further down in the mempool because the new transaction is not in the top block, then I’d argue that it would definitely miss replacements that are incentive compatible, and hence the entry should be “Yes”. ↩︎
Sorry, I should have filtered that myself! All good, thanks!
I’m still kind of nerd crushing on the clarity of your post, TBH. It’s really nice!
FDP “probably rejects some incentive compatible” is trivially Yes, I think? In a flat mempool a miner should accept a 64 byte tx which pays a greater feerate than a larger tx it replaces. It’s not immediately clear to how we would quantify it, but I suspect that the total fee rule makes FDP less incentive compatible in realistic scenarios than NBP.
Secondly, DoS resistance is not a binary. I’m not sure we’d be happy with the traffic increase if every tx RBF-stomped its way through the mempool in currently-allowed minimal increments? (To be fair, I haven’t calculated this in detail!). On the other hand, if we allowed a possible violation of the “must pay your way” rule which was difficult to execute in practice (such as filling the second block and hoping it doesn’t get mined before you replace it with the first block) we might be able to convince ourselves it’s not too bad statistically. Especially since we can adjust this, somewhat, by using greater hysteresis (e.g. you get an exception if you’re going from > 2 blocks in to < 0.5 block in the mempool, etc).
My main issue with this table, though, is the missing column is the one I care about! That’s the adversarial case.
And while v3 is a useful hack for CPFP, we don’t want CPFP as fees rise: we want inline fees and we want to stack multiple txs as much as possible to share the fee in/out (presumably using future covenant tech), but this means v3 doesn’t help us
Yes, I was initially assuming a carveout for the sharpest case where we currently clash with miner incentives, which is things going in the top block (also enables clients to have a Grug-like RBF model of “not in block yet, Grug pay more!” which suits my abilities). I think this would also apply to FDP, which has the same issue.
But I think to evaluate it we need to know:
how much of a DoS we are opening,
how incentive compatible it really is (given an non-infinite discount on future blocks, sigh), and
how much does it really help against the adversarial case.
(1) and (3) seem to require some mempool model and maybe a propagation model and a major thesis or three…
Actually, thinking about this overnight, I realized the DoS caused by carving out the “total fees” rule for block 1 entry is less than the one we already have.
You can already play the “free relay” game at the bottom of the mempool. In this case, there are three outcomes:
Fees go up, you get evicted, you win a Free Relay.
Fees go don’t go up, you don’t get to play this round.
Fees go down for long enough, your tx gets mined, you lose.
The same game played on the 1-block boundary (with the Next Block Carvout) is worse:
Fees go up, you get evicted, you win.
Fees don’t go up, you get mined, you lose.
In addition, this game is more expensive than the tail-of-mempool game.
Unfortunately, you can play both games, so strictly speaking it does make the DoS opportunity greater. But it’s a fairly strong argument that this does not make it significantly worse, either.
This is a fair way out of my expertise, though: have I missed anything?
Without derailing this excellent conversation happening too much, V3 in its current form I’d argue is useful for a number of the fee tropes, just not for single tx exogenous fees specifically, which of course is a bit of a shame, but it’s not just for CPFP!
I might be reading this game wrong, but if it’s evicted, we attempt to make subsequent txs “pay for it” by increasing minfee by incremental rate. So it’s limited in scope and by time(similar to how we allow free relay for transactions that sat in mempool for 2 weeks and time out). Strictly weaker than harvesting the fees directly of course.
I’m going with “Probably” rather than “Yes” exactly because we haven’t yet done the work to quantify or characterize the circumstances under which such a replacement would be incentive compatible. My guess is that in a situation like what you’re describing, the reason our intuition is that the replacement should be taken is because maybe we’re assuming there’s some infinite demand for blockspace at whatever the feerate is you’re talking about, and so miners are literally giving up nothing to accept a higher feerate (but smaller fee) transaction.
However, I don’t presently have a precise argument about what is needed to justify this conclusion, and I don’t think anyone else does either – so until someone carefully writes up the assumptions under which this behavior is incentive compatible, I’ll assume there’s some chance our intuition may yet be wrong. In particular, as I mentioned in the OP, in a world where there is just one miner/mining pool on the network (like @ajtowns described, in a stratumv2 world where everyone expects to gets their hashrate-proportion of all tx fees), it seems reasonable that the natural RBF policy is one that requires total fees to always increase, so there’s some reason to think that the incentives and game theory are more complex than we’re accounting for?
Yes you’re absolutely right that this isn’t a binary thing – what I had in my head when I typed the “Is DoS resistant?” phrase is a much narrower statement about free relay, which I think I could better phrase as: “Does the minimum relay feerate bound the ratio between (fees-in-mempool + fees-mined-in-blocks) and vbytes-relayed-on-the-network?”
With that narrower statement, I think my table would hold. That raises the question about whether this bound on costs to relay bytes is a useful characterization of relay policies. I think it is, because (a) it makes it very easy to calculate the costs for generating a given amount of traffic, and (b) it makes it so that all usages of tx relay bandwidth are treated equally.
Can you elaborate on what you mean by this? My guess would be that you are referring to RBF pinning, and maybe you mean: how can a 3rd party increase the costs of me replacing a transaction I created, in such a way that it does not increase the likelihood of the transaction getting confirmed that is somehow commensurate with the adversary’s costs?
Defining what a pin really is seems somewhat difficult to me (curious if anyone has a precise definition we can use?), at least in part because if we are just looking at RBF policies like the Feerate Diagram Policy I have proposed here, there is always some fee you can put on a replacement transaction to get it into the mempool. So it’s just a question of whether, in a given situation, you think that is a “fair” number. But defining fairness here is pretty hard, and I think it exactly comes back to incentive compatibility questions for miners… To see why, consider that we might need to answer this same question in a different context:
Imagine that Alice creates a transaction (tx A) that pays Bob, and she’s thinking about relaying a double-spend (tx A’) to send the funds back to herself. Under what circumstances should the network accept A’ as a replacement for A? In particular, if Bob has issued his own transaction B that spends A, under what circumstances should the network prefer the tx package A+B rather than A’?
This CPFP vs. RBF choice is fundamental to the question of what our RBF policies should be. It’s unfair to Bob (and to miners!) if Alice can replace tx A at such a cheap price that miners would have been better off with the A+B package, and similarly it seems unfair to Alice (and to miners!) if the costs of her replacing A+B are far beyond what the incentive compatible amount would be for miners to take tx A’ instead.
I think, today, we don’t really have a good framework to answer this question. If someone thinks they have assumptions under which we can do better in particular examples, then that would be a great place for us to start working from, and we can decide whether the assumptions are reasonable and what use cases would open up as a result.
I’m surprised by this take on v3: if you think CPFP is bad, then when designing your own protocol you could disallow it, simply by not having any immediately spendable outputs? Or, for general transaction spends that are not tied to any particular protocol/where you can’t control how the outputs might be spent, we could propose other ideas, such as allowing users to opt-in to a policy where children are either not allowed at all[1], or are allowed only under very limited circumstances.
So the way I’d look at v3 is exactly from the opposite perspective: we all agree that unconfirmed transaction chains are generally bad, and v3 gives us a way (for the first time) to actually limit them, and thereby make RBF more useful.
One thought experiment that I think is helpful: suppose in Bitcoin’s history, relay of transactions with unconfirmed parents was non-standard by default. Under what circumstances would we have relaxed that policy to allow for unconfirmed transaction chains? My guess is that we would only have permitted it for cases that make sense and meet particular use cases, like a single CPFP transaction bumping a single parent (much like v3!), which is easy for users to understand and for mining code to optimize for.
However, since we started with allowing arbitrary topologies and chains of transactions, we are left going in the other direction, of finding ways to cut back on what topologies are permitted instead. Our mempool issues would be far, far simpler in a world where clusters were limited to size 1!
You’re right that mempool eviction can give rise to free relay, but at any given moment, the number of additional bytes that have been relayed beyond what should have been allowed due to the minimum relay feerate is bounded at most by 101kvb, the maximum size of a descendant package. This is because (as Greg also pointed out above) the mempool minimum fee rises to ensure that new transactions being relayed will pay sufficient fee so that the last eviction is paid for before the next one takes place.
However, with the Next Block Policy, you can play the free relay game over and over again. Exactly how much depends on the distribution of fees in the mempool. I’ll try to redo the calculation I wrote about above in the specific context of a Next Block Policy RBF rule.
For concreteness: let’s say we’re allowing any transaction into the mempool as long as it would go into the next block, and as long as any conflicts are not already in the 1st or 2nd block which would be mined (so this captures one of your suggestions above of requiring some gap in the mempool order between what is accepted and what would be evicted).
What should we assume the distribution of feerates in the mempool is? I just grabbed this screen shot from mempool.space to see what the feerate ranges are for the past few and next few blocks:
I haven’t checked if this data is correct, but it looks like the feerate to get into the next block may not be that much higher than for blocks 3, 4, 5, etc. So for the sake of argument, let’s assume a hypothetical where a feerate of 20s/vbyte puts you out of the top 2 blocks, and a feerate of 40s/vbyte or higher would put you in the next block, and we’ll see what an attacker could do:
Let’s say an attacker filled up the mempool from blocks 3 and higher with transactions at 20 sats/vbyte. I think with my default mempool settings, due to various overhead my node has roughly 80 blocks worth of transactions in it right now (with a basically full mempool), so let’s say the attacker relays 78MvB of transaction data in 780 transactions of size 100kvb[2] to accomplish this.
According to this transaction size calculator, an attacker can then relay about 45k vbytes of transaction data (using p2tr) that conflict with one input of each of these 780 transactions. Under our assumption, this transaction would evict all 780 transactions as long as the feerate on this new transaction is 40 sats/vbyte, or about 1.8Msats in total[3].
Total vbytes relayed: about 78.5MvB.
Total fees collected: 1.8M sats.
This is far below what the minimum relay feerate would imply miners should collect in order for this much data to be relayed. Or, another way to look at it is that the attacker was able to drain all but the top 2 blocks in the mempool for just 1.8M sats spent, in the process removing 78MvB * 20 sats/vbyte = 15.6 BTC from the mempool. (Please correct me if I made any numerical errors here.)
Moreover, the attacker could then repeat this attack, over and over again, tying up CPU and relay bandwidth of 78 blocks worth of data, for just 1.8M sats in cost each time (about 900USD at today’s prices?). Also note that in the process, the attacker has likely driven up the cost to enter the mempool up to 20 sats/vbyte by filling it up in the first place, but without an actual corresponding increase of fees collected by the miners.
We could discuss whether this is an attack anyone would have an economic incentive to perform (perhaps one miner attacking another, by draining their mempool?), but regardless I would maintain that this is not something that we should permit to happen, for both anti-DoS and incentive compatibility reasons.
This was actually something that was brought up a long time ago on the bitcoin-dev mailing list; see for instance [bitcoin-dev] BIP proposal: No chaining off replaceable transactions. The main issue with that particular proposal was that it would have applied to all opt-in-rbf transactions and prevented the ability to CPFP. However, we could imagine a few variations: (a) the v3 proposal itself, which allows a single small child; (b) only allowing a child if the resulting parent+child package would be included in the next block, but otherwise disallowing children; (c) some variant of v3 where the child transaction size is limited even further, say to 200 vbytes, so that CPFP is still permitted but the number of extra bytes that a replacement might have to pay for is as small as reasonably possible. See also Greg’s writeup, V3 and some possible futures, which covers some more general ideas that may be possible in a post-cluster-mempool world. ↩︎
My guess is that it would take on the order of several minutes to get these transactions to relay across the network using Bitcoin Core, but I haven’t modeled it carefully. I believe we currently relay transactions at 7 tx/second to inbound peers and about 17.5 tx/second to outbound peers. Not sure what the network’s overall bandwidth looks like for this much data though. ↩︎
If you object to the number of transactions being evicted at once, since BIP 125 caps the number of conflicts from a single replacement at 100, then just imagine the attacker does this in 8 transactions that are all approximately 1/8th the size – I don’t think a conflict limit has a meaningful effect on these numbers. ↩︎
is accepted into the mempool at a low feerate (so will not be mined in the near future)
conflicts with a high feerate tx, V, but is not RBF-replacable by V
the fee cost to fix this is excessive, whether by:
bringing P’s feerate up to a level where it will be mined soon (by CPFP or out of band accelerator payments to miners); or
bumping V’s fee such that it becomes a valid RBF-replacement; or
constructing an alternative tx U that has a high feerate and does RBF-replace P
“Excessive” is always a judgement call. I think if you retain the requirement that total fees always increase, then the only way to prevent fees becoming excessive is to require that the total size of txs evicted by replacing P with U is at most only a small multiple of the size of V. That multiple then tells you exactly how much U needs to overpay compared to V, so ideally you choose it based on your own definition of “excessive”.
An alternative highly speculative design, that would at minimum require magic new opcodes and might not be possible at all in bitcoin’s model, would be to allow deconstructing the pinning transaction: that is, if you start off with P spending inputs C, I_1, .., I_n and creating outputs X, P_O versus the simpler tx that spends C, V_I and creates outputs X, V_O, you could imagine constructing a new tx U that spends C, V_I and creates outputs X, V_O, M, and another transaction W that spends M, I_1, .., I_n to create the single output P_O, reusing the same signatures for I_1, .., I_n from P. That way miners aren’t losing any total fees, pinning is easily worked around as long as you observe the pin, and everyone’s happy.
However specifying a constraint for spending C such that all the sibling inputs have signatures that allow C to be replaced by M (but not some other output with the same scriptPubKey and value) and only commit to the output P_O is probably quite tricky, if it’s even possible at all.
Some pictures. The transaction we’d like, with small size, modest fee, high feerate:
flowchart LR
Contract ---> V ---> Results
VI ---> V ---> VO
The pinning transaction, with large size, possible high fee, but low/modest feerate:
flowchart LR
Contract ---> P ---> Results
P1 ---> P ---> PO
P2 ---> P
Pn ---> P
The magic solution; U has small size, modest fee, high feerate, and gets the contract results, while any additional fees from P are still available by mining M, even if its feerate is low/modest.
flowchart LR
Contract ---> U ---> Results
VI ---> U ---> VO
U ---> M
P1 ---> M<---> PO
P2 ---> M
Pn ---> M
If you’re dropped from the mempool, it’s like you never existed. There’s no “minimum increase” other than what gets you in the (now more expensive) mempool?
(Edit: Apparently this is wrong, because minfee increases? For how long does that happen?)
There’s a halflife of 12 hours specified, which decreases to 6 hours if the mempool is less than half full, or 3 hours if the mempool is less than a quarter full; provided there’s been a block since the last time the minfee was bumped due to tx eviction, the minfee will decay towards 0 at that rate. So at 20sat/vb, when the minfee is raised by 1sat/vb it’ll take ~53min to decay back; at 50sat/vb, about 21 minutes; at 100sat/vb about 10 minutes; at 5sat/vb about 4 hours.
Predicting fees is Too Hard, and over-paying increasingly Too Expensive. So you really need to BYO fees at spend time (rather than construction/signature exchange time), and if you can do that you can ride out fee spikes without needing to renegotiate with the other party, too, making your protocol more robust.
With current tech, we can only do this for SIGHASH-SINGLE/ANYONE_CAN_PAY (limiting your protocol to single in and out, which doesn’t usually work for multi-party stuff), OR using CPFP which requires one output which is spendable immediately.
i.e. CPFP is the only game in town today. v3 helps here today!
But I think the end game of Bitcoin is high fees (which will justify a great deal of engineering and effort to mitigate), and introspection which allows us more room to optimize. The medium case is bringing your own fee input/output at spend time, but really optimal is paying someone (over lightning or anything but onchain Bitcoin) to gather multiple unrelated txs together from everyone, with one fee input and output covering the entire thing.
Perhaps we would end up using introspection to limit the tx size anyway, so we just need the no-unconfirmed-children rule. Or perhaps the diminishing returns from bundling mean the tx size doesn’t have to be very large.
Now I write this out, I think I understand @instagibbs point about the generality of the v3 proposal, which would still serve here?
(End of a long day here, I will digest the rest of your post before the weekend, I hope!)
Thanks, indeed, this makes the “free relay at bottom of the mempool” game less easy to play, depending on how fast that decays. From AJ’s answer, I’d guesstimate 10-100 blocks might be typical, but it’s not a far cry from 2 weeks…
(Please correct me if I made any numerical errors here.)
Even if you did, the order of magnitude is correct.
this is not something that we should permit to happen, for both anti-DoS and incentive compatibility reasons.
I agree with anti-DoS, but it’s not even clear that it’s not incentive compatible. If you expect other miners to do the replacement, it depends on your discount rate. Which is annoyingly circular reasoning, but I think we can do better.
Let’s assume v3 rules, so children need not apply. All the pre-signed transactions I know of can trivially enforce this condition, so it seems fair, and cuts the problem down a fair way.
What does it fundamentally cost to drop a random transaction from the mempool? If we assume the Mempool Is Always Full, then it seems reasonable that it will be eventually replaced by a transaction at feerate minfee - epsilon. And if we assume a tx of < 101k, and some continuous looking feerate distribution around and below the bottom of the mempool, I’m happy to ignore epsilon.
In this model, a miner would consider an RBF tx fundamentally incentive compatible be comparing the total fees above the minfee rate. To give some numbers:
My node’s mempool is oversized, but a quick grep/cut/awk hack gives me the threshold for block 78 as 7.7432 sat/vb (and block 1 as 14.0673 sat/vb). Under this model, a 100k tx paying 774,320 sats is worth epsilon (~0), so a miner would want to accept a replacement 1k tx paying any higher feerate, say 7744 sats.
Now, does this actually help our pinning attack? Not as much as the previous proposal, at least on these numbers. Halfway up the mempool (block 39) is 12.0378 sat/vb (higher in the mempool means it’s more likely to get mined and just fail, so this is a reasonable worst-case sketch). Mallory puts a 100k tx there, be paying 1,203,780 sats, thus a fee-above-minimum of 429,460 sats. Alice’s 1k tx would have to beat that fee-above-minimum, so 437 sat/vb feerate (it could otherwise get in the top block for 14 sat/vb, so this does feel like extortion).
But I think it does imply that there’s a significant conflict between miner incentives and the current RBF DoS rules (under which Alice’s 1k tx would have to pay a feerate of 1204 sats/vb).
While I think that Suhas’s example above is somewhat similar, I recently elaborated an example how introducing a replace-by-feerate scheme in addition to our current RBF rules would cause new substantial DOS vectors. While my example is based on a concrete proposal, I believe that it illustrates a general issue afflicting all schemes that do away with the absolute fee increase in replacements: mempool - What is the problem with the recent "One-Shot Replace-by-Fee-Rate" Proposal? - Bitcoin Stack Exchange
My example entails a negligible cost to the attacker while permitting continuous resubmission of essentially the same transaction cycle. The collection of transaction has a substantially larger total weight than the data that is ever up for inclusion in the blocks and hence severely underpays for relay to the detriment of the entire network’s bandwith-usage. I hope studying my write-up would help substantiate why transaction replacements must increase the total fees in the mempool.
I think this technical definition is overspecialized (or perhaps implied by the question?).
The problem is: you want to spend some shared input in a timely manner, and are prepared to pay competitive rates to do so vs other transactions. Another transaction is preventing this. You don’t really care why, or which tx gets mined, but you have some deadline.
I think we’ve demonstrated that there are cases where the miners are incentivized to fix this, and cases they are not. In the latter case, there’s a Schelling point where, even if it’s not directly incentive compatible for a miner to replace, it becomes so if the other miners do. Such a Schelling point might come into existence if (1) miners agree it’s generally better for the network, (2) the gains of not doing so are minor anyway, and (3) it’s the default.
We still have to deal with the DoS problem, but perhaps that’s as simple as “if a tx has been in the mempool for over 12 blocks and you’re offered feerate to get the replacement into the top of mempool, and they’ve both v3, allow RBF ignoring the total fee rule”.
This was the link I was looking for earlier, thanks!!
We need to consider three things here:
Bandwidth consumption
Higher layer protocol efficacy
Miner incentives
I think we’ve demonstrated a conflict between them (i.e. we need to compromise, and we implicitly are already).
I don’t think your example works for lightning today, where the first transaction is of fixed size, so games can only be played with the children, and v3 restricts those.
But it does effect a general stackable-txs case, which is where we’re headed eventually, so must be considered. Sigh, ok
The real problem in your example seems to be step 7: by RBF not considering the package feerate, but a single tx feerate, it discards an imminent tx! This is not incentive compatible if you assume any reasonable discount rate for future blocks?
The stackable case is interesting in that an attacker can easily coordinate with itself to pin 100 channels, but collective action to outbid it might be prohibitive in terms of interactivity. So even if a miner “knows” it would pairwise not take the pin-evicting txs, it might err on the side of taking it anyways, excluding DoS concerns.
My ideal is if we had some future discounting, and we applied it to diagram checks, we could make all diagrams comparable during these checks. With that in hand, incentives and DoS checks would be two completely separate concerns. From there we can think about alternative anti-DoS measures with a bit more clarity.
