An overview of the cluster mempool proposal

sdaftuar · January 12, 2024, 3:04pm

@harding Thanks for giving this a thorough read!

Great question, as this is something that I have discussed at length with others.

I take the view that the feerate diagram should represent the amount of fees that a miner would receive by mining a given number of vbytes from the mempool, and if the mempool runs out of vbytes when you’re trying to look up the corresponding total fees for that size, then the natural thing to do is to assume you have 0-fee paying transactions that take up the additional space.

So in your example, I would pad the diagram for NEW to be of the same size as OLD, and the amount of fees in NEW’s diagram at 123,456 vbytes would be the same as the amount of fees in NEW’s diagram at 78,901 vbytes. And so if NEW is greater than OLD at 78,901 vbytes, but less than old at 123,456 vbytes, I would say that the two mempools are incomparable, and not accept a transaction that would move us from one of those states to the other.

Another point of view one could have is that there’s some “tail feerate”, possibly greater than 0, at which there is essentially an infinite supply of transactions that could be included by miners in blocks. If this is your view, then you could imagine picking some tail feerate value (presumably, this is a value that has an upper bound given by the lowest chunk feerate in the mempool), and then extrapolating the feerate diagram of NEW at that feerate so that it has the same size as OLD, and then doing a comparison on the resulting diagrams which will then be the same size.

However, if you take this view that the tail feerate is greater than 0, then this should also change the way you view a NEW mempool that has more vbytes than the OLD mempool, such that you ought to extrapolate the feerate diagram of OLD in that situation so that you are imputing more fees in the OLD mempool than are actually there. This in turn would then prevent some replacements that would be successful if we used a tail feerate of 0 instead, and frankly it seems surprising to me that we’d assume the existence of fees that a miner running our software can’t actually realize.

So my overall view is that a tail feerate of 0 is the most justifiable idea right now. Moreover, even if we had an interpretation of mempool incentive compatibility that permitted some non-zero tail feerate, we’d still be limited by the anti-DoS rule that requires total fees to go up (to prevent free relay), making the point moot – so for now at least, I think this is more of a theoretical issue than a practical one.

I could imagine in the future that research could be done regarding incentive-compatibility to take into account the idea that feerates near the top of the mempool are more significant for miners than feerates near the bottom of the mempool, and therefore an optimal diagram comparison would apply some kind of discounting to things at the bottom versus things at the top. And should someone develop a robust model for how to do this, I think we could update our software in the future to implement a different test.

I don’t have a proof, but my intuition is that there is no solution here.

The problem is that literally any non-child transaction in the mempool today might be a candidate for having a child that satisfies the criteria of the carveout rule. For the sake of my illustrative capabilities, assume that we’d like to enforce a cluster size limit of 10, and we had a mempool cluster that looked like this:

graph TD;
    P1-->C1
    P2-->C2
    P2-->C1
    P3-->C3;
    P3-->C2;
    P4-->C3;
    P4-->C4;
    P5-->C4;
    P5-->C5;

This cluster is full, but any any one of those transactions P1, P2, …, P5 might have another spendable output allowing creation of children that would match the requirements of the current carveout rule (which just checks that the incoming transaction have exactly 1 ancestor and be below some size limit). So to implement carveout in its current form, we’d have to be either willing to (a) evict an existing transaction from this cluster to make room, or (b) allow all 5 new transactions to be added, blowing through our cluster size limit of 10 and creating a cluster of size 15.

Neither of these options is good. For (a), there are two issues with evicting an existing transaction. The first is that any of the in-mempool parent transactions might be a shared transaction in some multiparty contracting protocol, and the other participant might be relying on their spend of their output to be the one that gets the parent confirmed. Now, we could mitigate that by trying to use our RBF rules to find another transaction in the cluster to evict, to make room for the new transaction; but this is problematic for two reasons. One is that you could easily be pinned by transactions that are larger but pay a lower feerate, and be forced into a choice of supporting carveout at the expense of opening up free relay attacks; the other is that this introduces a great deal of complexity into our validation code if we have to find a transaction to evict, given that there may be many choices for which one to evict, creating a lot of processing overhead to determine which is the most incentive compatible outcome (and I imagine there could easily be incomparable options to sort amongst).

For (b), my philosophy on this work is that we should strive for cluster size limits that we are allowed to meet and never exceed – for instance, if we thought that it was safe to have clusters with 100 transactions, maybe you could design a policy regime where the default limit is much lower (say 50), and then we permit carveout exceptions and try to reason that this could never take us above 100. I think this would be bad design, though, as it means that we’re significantly restricting the permitted cluster size for the vast majority of network users in order to try to reason about what I view as a very edge case situation. My engineering opinion is also that this is just bad software design, of having a limit in mind that you can’t actually enforce without some analysis of emergent properties at a higher layer.

Anyway, it’s possible that I’m wrong about there being no simple workarounds here, so if you have other ideas of things to consider please suggest away…

However it strikes me that there’s a more obvious solution available to us: if we have an idea for what topology the carveout rule is intended to match, then we should instead just offer a policy regime that allows transactions to opt into that topology, and then we can enforce cluster size limits as we’d like to. The v3 transaction proposal is designed with this in mind, so if it proves to be workable for the use cases that currently rely on carveout, I think this would be vastly superior.

instagibbs · January 12, 2024, 3:21pm

Yes, it’s completely natural to apply some sort of future discounting, as something far away from “top blocks” are likely to:

be trimmed
be RBF’d
timeout

so reflecting that uncertainty directly is something someone can explore further. I did some initial number analysis to see if it could help anti-pin(it can’t )

A minor note, but this also necessarily opens up to “mempoolfullrbf” style RBFs, good or bad.

One idea I’d had, which Suhas has essentially responded to above, is that we could:

receive new chunk somehow that exceeds cluster limits
allow temporary exceeding of limits
re-linearize cluster with exceeded limits
“chop off” the excess at the end

As Suhas notes, this can get pretty weird with pinning/anti-DoS. I don’t think it’s a dead-end, but more of a whiteboarding project at this point.

harding · January 12, 2024, 6:04pm

The idea described below in this post doesn’t work. I tried to find a way to make carveout compatible with cluster mempool and failed. Normally I wouldn’t advertise my failures, but I think it could be useful to future discussions to show several people tried working this problem and couldn’t find a solution.

Your description and diagram match how carveout works (AIUI) but I think it’s worth noting that LN anchor channels only have exactly 2 outputs that can be spent in the same block as the parent transaction (see BOLT3). This is necessary to prevent a malicious counterparty who controls >1 output from using the carveout themselves and preventing its use by the honest counterparty, so I think we can safely assume that any other thoughtful users of carveouts are doing something similar. An implication of this is that your diagram’s P2 to P5 could not have a carveout attached because both immediately-spendable outputs have already been spent.

I think we can reformulate carveout’s rules as used by LN:

A carveout is 1,000 vbytes or less
A carveout has exactly one unconfirmed ancestor (it’s parent)
A carveout’s parent has no unconfirmed ancestors
A carveout is either the first or second spent output of a transaction that has fewer than three of its outputs spent so far

Checking whether a newly received transaction obeys rule #1 is obviously easy. Checking that it obeys rule #2 is also easy because we have to look up each of a transaction’s inputs anyway. When we find the carveout’s exactly one unconfirmed ancestor, we can check that it obeys rule #3 using the same mechanism (no special traits or caching required). Now to check rule #4 we need only determine how many spends of the parent transaction’s outputs are currently in the mempool; if it’s currently 0 or 1, and all the previous rules were satisfied, we tag this transaction as a carveout and allow it to exceed the cluster size limit.

Using free CPU cycles, we can periodically check every transaction tagged as a carveout to see if its parent now has three or more spends, in which case we can clear the carveout flag.

When writing the above, I thought my proposed scheme meant a cluster could never have more than two carveouts. However, here’s a case where there can be many more:

graph TD;
  P1 --> CO1;
  P2 --> CO2;
  P3 --> CO3;
  P1 & P2 & P3 --> C1[Regular child];

instagibbs · January 12, 2024, 6:21pm

doesn’t actually matter for the example, but I believe it’s 10kvB

sdaftuar · January 12, 2024, 7:27pm

Just thought it is worth noting here that in trying to think about what the LN carveout rule should match for, rules 2, 3 and 4 are all about the transaction graph topology – and yet currently, the LN anchors have no enforced topology restrictions (beyond their construction of having 2 spendable outputs – but those outputs can be spent arbitrarily). If we had a way to enforce that spends of an anchor output were not permitted to have additional children or pull in additional parents, then this problem again becomes easy – which is exactly what v3 contemplates.

sdaftuar · February 2, 2024, 2:30pm

I was wondering if a form of sibling eviction might work as a topological (if not economic) substitute for the carveout rule going away. That is, is there a sibling eviction policy that we could adopt which would give current users of the CPFP carveout rule an economic way to get a transaction into the mempool when the cluster it would be joining is full? If so, then this might be an alternative we could consider to the suggestion of using v3 policy rules as a carveout replacement.

Specifically, I was wondering if we could implement the following sibling eviction policy, as part of the cluster mempool approach:

If a new transaction is rejected from the mempool due to a cluster size limit, and it has a single unconfirmed parent, and that parent has exactly 1 other unconfirmed child, then consider that child as a candidate for eviction in order to accept the new transaction. Specifically, we’d use our RBF rules (feerate diagram check) to determine if the mempool + new transaction - replacement candidate is strictly better than the existing mempool, and process the replacement if so.

I should point out immediately that with no other constraints on the sibling described in that rule, that RBF pinning with a high fee transaction would be possible. Still, I wondered if having some way to evict a transaction to make room for another might still be valuable, in a general setting, as that gives users more options than rules which have no economic mechanism to bypass.

However, I don’t think we can easily achieve this behavior while maintaining an additional intuitive property:

Any transactions we evict under this policy should not succeed in re-entering the mempool if immediately resubmitted.

The proposed rule fails this test. Consider this picture:

    flowchart 
         A --> B
         A-.-> C
         B--> D
        E["E: some tx connected to a big cluster"] --> B

Imagine tx C arrives, and we consider eviction of tx B to make room for it. Even if “accept tx C and evict tx B (along with B’s descendants)” is a valid replacement under the feerate diagram check, it’s possible that immediately re-accepting tx B would be successful, because without tx D it might be under the cluster size limits.

To resolve this, we could (say) require for our rule that tx B only be evaluated for eviction if it has no unconfirmed children. However, then we immediately lose the benefits for something like this as a carveout alternative, because it’s trivially pinnable by a counterparty where if the other sibling has multiple children, no sibling eviction would be considered.

Alternatively, we could find some child transaction to consider evicting; however if there is more than one candidate, then we might be in a difficult situation of trying to pick which one to evaluate, and there’s no obvious way to make that choice.

By contrast, the v3 rules resolve this problem, by requiring that v3 children have no children of their own.

(Just sharing this in the spirit of @harding’s comment about the potential value in looking at failed ideas!)

instagibbs · February 2, 2024, 2:41pm

Can you motivate this as a principled objection? Mempool quality increases, just not in the most optimal way possible. The alternative is to not improve the mempool at all?

Again, if our constraint is “we can only pick the optimal evictions”, sure this is intractable, but I am not convinced of that. For now I’d rather focus on the premise of the objection on the simple non-v3 case.

Also while we’re here, the other strategy previously discussed to allow cluster limits to be breached, temporarily and in some limited size/count way, linearize, then “prune” until you get back to cluster limits. Accept/reject said linearization based on normal diagram checks. I know you’ve already dismissed this, but good to have alternatives all in one place.

With other objections you’ve had aside, I think this strategy is more limited because you may not be able to practically make the sibling eviction candidates small.

sdaftuar · February 2, 2024, 2:51pm

Hmm, I’m not sure that I can – it just seems like this is a messy behavior, and so I think we’re missing something in the design if we can’t come up with a cleaner way of achieving the goal. It’s wasteful to have to rebroadcast/revalidate transactions that never should have been evicted in the first place.

Also I suppose there are other solutions we could consider; one is that we somehow require a peer sending us this transaction to do the work of calculating which transaction we should evict to make room for a new transaction, which we then just verify will satisfy our requirements? Seems like that could be a “clean” approach from an engineering aesthetics point of view, though it begs the question of how that determination might be made by a wallet in the first place.

Edit: Maybe the broader observation is, if this narrow idea for sibling eviction is still this messy, and it has obvious pinning vectors anyway due to how RBF works, and it only applies in a very limited topology to begin with, is it worth adding the complexity to the implementation?

instagibbs · February 2, 2024, 3:02pm

Doesn’t work when the peer cannot “see” the other transactions. You can’t really give hints that will work consistently.

I don’t buy that premise though either, I was deferring for sake of argument.

It would certainly have to be well motivated. In a future package relay world there’s a few, less so in the near future where 1p1c makes most sense.

edit: last thoughts for now

something I had thought of and forgot later, but sibling eviction is less important in a “top block” world
We could decide that later, with “top block”-like solutions that allow relaxed topologies, sibling eviction could be an add-on measure where we do something simple to avoid DoS but perhaps not remove all pins

ajtowns · February 3, 2024, 11:29am

I’m not sure I see this as bad? The mempool would be going from:

[E] [A] (separate clusters)
[E, B] [A]
[E, B, D] [A]
[E, A, C]
[E, A, C, B]

Those are all fairly different states, and each one is strictly improving the feerate diagram. That seems like a good thing!

The only drawback I can see is that “B” would be potentially be being relayed and validated twice (which is wasteful, and you might be able to convert that into a DoS attack of some sort if you can cheaply construct lots of C’s and D’s?).

If there was some reasonable way of jumping directly from “[EBD] [A]” to “[EACB]” without the intervening step where B is evicted from the mempool, that would seem perfect. If we already have a linearisation of the stuff we’re evicting (ie “[…BD]”) could we just try adding those txs back in in order immediately?

instagibbs · February 5, 2024, 3:08pm

As a post-processing kind of step, the replacing chunk would have had to pay total/incremental for evicting the things being re-added, so this seems relatively conservative.

Even better is if we could cheaply compute a small subset of items(ordered by increasing CFR?) that we could remove to make the new chunk fit. This would allow the evict-er to pay less in fees, but also might stray into computationally dubious territory.

instagibbs · February 8, 2024, 2:14pm

Something like this might be general enough to be useful(Uncle eviction?):

If proposed chunk is too large for cluster by (remaining_size, remaining_count):

add all existing chunks to minheap by CFR
While heap not empty, pop chunk: For each transaction in chunk(in reverse topo order):
if in proposed chunks’ ancestor set: skip
else mark for eviction and reduce remaining_size by tx size and remaining_count by 1 If remaining_size <= 0 and remaining_count <= 0: break
If anything was marked for eviction: Do diagram check (don’t check remaining_*, maybe we split clusters accidentally?)

You could also restrict the space of transactions to evict to something more “local” like the descendants of the proposed chunk’s ancestors’(not including the ancestor set itself). This should allow eviction in every case still if the new chunk’s fees are high enough, while acting a bit more “locally”.

These should allow improvements to the mempool with O(nlogn) processing, and no resubmission of transactions? Doesn’t solve incremental relay pins of course.

sdaftuar · February 8, 2024, 2:48pm

Nothing strikes me as particularly problematic with the algorithm you describe – I think there are a bunch of bounded search algorithms we could consider which look for a subset that is strictly better than what we started with – but I think if we accept that (a) we don’t currently have a framework for deciding what an optimal subset of transactions from a too-big-cluster is, and (b) that therefore any approach that tries to find something better than what we have is going to be guesswork for now, then I think it would make sense to motivate the logic with a use case that would need it.

I’d hope that with more research, at some point in the future we are able to come up with a rigorous notion of what an optimal subset of transactions from a too-big-cluster is, and at that point it would be a shame if we were held up in deploying it due to reliance that has developed on existing behavior. (Of course, if there are use cases that would concretely benefit today from our guesswork solutions, then that would be a reason in favor of trying something like this.)

EDIT: regarding this:

You could have a resubmission of transactions that works, if I understand the algorithm right. Consider this picture:

    flowchart
         A["A: 10kvb, 1 sat/vb"] --> B:["B: 90 kvb, 50 sat/vb"]
         A-->C:["C: 1kvb, 5 sat/vb"]
         A-.->D:["D: 5kvb, 1M sat/vb"]

So A, B, C are in the mempool and D arrives. ABC is at the cluster size limit, and the cluster should chunk as [AB, C]. Running your algorithm, we mark C for eviction, and then mark B for eviction – at which point we’ve freed enough space. We compare [AD] to [AB, C] and assuming I made D’s feerate high enough, it gets in. But now there is room for C to be re-added as well.

instagibbs · February 8, 2024, 3:23pm

You’re of course right, since we’re not optimally pruning these effects can still happen. So you might want to have the evicting party pay for it, but then let it back in via re-submission. Or just be more optimal.

Shower-thought level quality aside, the goal is to give wallets, who maybe don’t even see the cluster limit being hit, a way to improve the mempool and get their transactions confirmed. If we find an even better way later, we should take it.

A couple use-cases for motivation in the future, all relying on cluster sizes of above 2:

0-conf funding transactions in LN. Funding transaction may have descendants added on, so the anchor spend(or slightly larger replacement) is unable to enter the cluster.
Ark/Timeout trees. You may want log(n) nodes in the tree published with a single anchor at the end of the chain, but once enough branches are put into the mempool, you’re unable to make attempts at inclusion.

Adding anchors at each step “fixes” these, but significant marginal bytes to protect against scenarios no one has seen in the wild is a hard sell.

hebasto · February 18, 2024, 3:28pm

Do I understand correctly that the cluster size limit might affect the experience of the CoinJoin transaction participants? Considering a transaction with no ancestors, which has the number of outputs that exceeds the cluster size limit, only first max_cluster_size - 1 participants will be able to spend their outputs, no?

sdaftuar · February 18, 2024, 3:40pm

Just to be clear, only the first max_cluster_size - 1 participants will be able to spend their outputs in separate transactions before the parent transaction is confirmed, but yes that is correct.

Note that today, the descendant count limit (25 transactions by default) already imposes a restriction on unconfirmed spends of outputs from a single transaction. While we haven’t finalized a proposed cluster size limit yet, my hope is that we’ll be able to support a number that is bigger than 25 (in my draft PR, this number is set to 100 for now).

hebasto · February 21, 2024, 12:31pm

Without knowing a mempool ordering, is it possible for a wallet to construct an RBF transaction candidate that will be guaranteed to be accepted?

if not,

What kind of a mempool ordering data would be sufficient for a wallet to achieve such a goal?

sdaftuar · February 21, 2024, 1:59pm

I think the short answer is “no” – philosophically at least, what I’m proposing is that our RBF rules become even more of a black box than they are today.

When we first implemented RBF in Bitcoin Core (back in 2015), I had suggested that we write up our replacement rules in a BIP (BIP 125) so that wallets would be able to know what the rules are and be able to comply with them. However, because those rules depend on the feerates and total fees of all conflicting transactions (including descendants of direct conflicts), wallets already need access to a full node’s mempool in order to know how to replace a given transaction.

Because of this existing complexity, my understanding is that most (all?) wallets today, in practice, just try to keep bumping the fee on a transaction until it is accepted by a full node’s mempool (if access to one is available) or until it confirms. I’d be curious to know if there are wallets in use that attempt to calculate the BIP 125 requirements for themselves though, and if so, how they achieve it.

Let’s say we’re constructing a new transaction T, which would directly conflict with some existing transactions {E_1, ..., E_N}. Then in theory, in order to calculate exactly whether T would be a successful replacement, we’d need to know:

the existing orderings of the clusters that each E_i is currently in.
the orderings of the clusters that would be affected by adding T and removing each E_i from the mempool
the total fees of T, and the total fees of the transactions being removed from the mempool.

In practice, though, the rules line up largely with what I think users expect. You can take a look at my draft PR (https://github.com/bitcoin/bitcoin/pull/28676) and look at the changes that needed to be made to the functional tests – basically no substantive changes were made to the tests in feature_rbf.py. So I think that is indicative that the rules aren’t really changing in ways that are unexpected for real-world use cases.

hebasto · February 22, 2024, 10:04am

The amount of work required to reject an RBF replacement might be substantial. Does this create a new potential attack vector?

sdaftuar · February 22, 2024, 10:31am

Yes, I agree that we need to be mindful of the validation costs of RBF and impose RBF limits to prevent those costs from being too high.

There are two differences between validation of RBF transactions and non-RBF transactions:

RBF transactions require re-clustering and relinearizing all the clusters which have seen evictions. (Re-clustering is an O(n) operation in the number of transactions, and roughly speaking we can bound re-linearization cost to O(n^2) in the number of transactions in a single cluster.)
Doing a feerate diagram comparison of the old vs the new clusters. This is linear in the number of chunks of the two diagrams (which is bounded by the number of transactions in the clusters that the diagrams come from).

Today’s RBF rules (BIP 125) impose a limit on the number of total transactions that would be evicted by a single replacement at 100. For cluster mempool, if we limited the number of direct conflicts a single transaction could have at 100, and if clusters end up being limited to at most 100 transactions, then this might be good enough – effectively bounding the number of extra linearizations at 100 and the size of a feerate diagram comparison to 10,000 entries. But we’ll get a better sense of this as we do more benchmarking – if this is too many, we could do some kind of more precise calculation of how many clusters are being relinearized and how many entries the feerate diagram has, and bound things based on the exact numbers we care about limiting so that validating a single transaction is not too expensive.