Restrict the maximum memory pool size to avoid potential DoS issues.
The mechanism is simply to recursively remove the transactions which have the lowest priority until the memory pool is below the maximum size.
compiles and passes tests, but has not been extensively tested
this is intended to replace #3753
Iterating though the entire mempool whenever the limit size is exceeded seems inefficient, especially with larger mempools. I would either keep an index ordered by priority/whatever, or use random deletes instead.
Also, needs a hook for the wallet to mark its own transactions as “precious”, or the conflict detection mechanism will break.
You should not remove any transactions that have dependencies before first removing their dependent transactions.
Also how about preserving nBlockPrioritySize worth of the highest priority transactions, and then pruning the rest based on fees.
I was playing with recursively splitting utxos recently, and managed to fill my two testnet nodes mempools to 300mb (>110k tx’s) over half an hour. One node was used for broadcasting, the other for informational purposes. Both gave similar results throughout, so I suspect many nodes accumulated the same. https://www.blocktrail.com/tBTC/address/mvoh3Jwirz6YLdSdpp1558uHWdJ9Qpijjg
Since all of these transactions were dependent on a single UTXO, perhaps nodes could limit the number of dependant transactions in the memory pool. As @ashleyholman noted, tracking hierarchy is probably a good idea, since after pruning an unconfirmed transaction with 100k unconfirmed child transactions, further spammy spends would no longer be added to the mempool as the inputs would be missing.
I’m less clear on how this would affect the relay policy however - not relaying child-of-pruned transactions means the spammer (or legitimate user) would need to find other peers.
EDIT: Also, if the presence of a transaction in the mempool is a requirement to relay other, dependent unconfirmed transactions, you could exhaust the networks mempool as a whole by giving it a fixed size.
I managed to produce 1/4 of your proposed limit in an hour or two. I had a 4000 tBTC output to play with, which should have given me millions of transactions, but I cut it off. I can probably determine the minimum sized output needed to produce your limit.. will try this now.
@pstratem I just had some further thoughts about this.. hope you don’t mind my 2c
In general I think it would make sense to align the policy of choosing transactions to pack into a block (in CreateNewBlock) and the policy for mempool retention. The only difference would be nBlockMaxSize vs nMaxMempoolSize.
So how about splitting out the transaction selection code from CreateNewBlock into a policy class, and then re-using this for mempool pruning? It would be like constructing an nMaxMempoolSize block, and throwing out any transactions that weren’t included.
@ashleyholman I’m going to take a look at the various places that policy is applied and figure out how to work from there.
So far I see
Transaction select for CreateNewblock Relay policy
Am I missing anything?
Sounds good! Let me know if you want any assistance with writing code or testing, because I’m quite interested in this patch so am happy to get involved :)
If you’re implementing this as a full sweep of the mempool (like the CreateNewBlock code does), maybe it should run less often than every time a tx comes in. You could have two limits, 1 for the threshold (size at which to trigger the cleanup) and another for the size to prune down to.
@pstratem Thanks for getting started on this. I’d been putting off working on it because it wasn’t clear to me that there was agreement on how to boot things from the mempool. In my mind though, you would keep all the transactions in a sorted list (or up to 3 lists, one by priority, one by fee, one for wallet transactions) and that same sorting would be used in 3 places. For booting things at the end to limit mempool size, for creating new blocks, and for improvements to fee estimation. The sorted list is a requirement to really improve the fee estimation over where it is now with just some historical analysis.
As for the priority calculation code, it does appear in a couple of places, but I fixed the one instance where it was calculating it differently. They all result in the same calculation now.
CTxMemPool::addUnchecked() but only if a certain amount of time has passed (24h by default).
Will focus now on a hierarchical check for wtx (don’t remove wtx dependent tx).
@morcos Unfortunately that was the same conclusion that I came to.
If I can get everybody to agree on some algorithm for calculating a single priority number which takes into account dPriority, nFee, and IsMine/IsFromMe then the code here (and potentially in CreateNewBlock) becomes much simpler.
actually it’s probably a lot easier to keep dPriority in its own queue, because that queue is a pain to maintain as all the transactions in it are updating their priority every block.
also having CPFP implemented will make this work a lot better if we can make it efficient
When I’ve contemplated updating this code in the past I’ve thought that storing mempool entries using a Boost multi-index container (with indexes on fee-per-kb, priority, and time inserted) would be the right thing to do. See http://www.boost.org/doc/libs/1_58_0/libs/multi_index/doc/index.html
The goal would be to do all the sorting as transactions enter the mempool, so CreateNewBlock doesn’t have to do any sorting and is very fast. As morcos says, though, handling priority is tricky because priority changes over time, although I bet some clever thinking could come up with a way to represent priorities that takes advantage of the fact that priorities only get better over time, they never get worse.
On further consideration… protecting wallet transactions from eviction is an information leak.
GetPriority in txmempool.cpp is wrong after all.
@pstratem: I’m not sure if adding whitelist flag to CTxMemPoolEntry is the right way. How would you then protect a 0-conf input (which has low priority for some reasons and therefore is marked for removal) used within a just created wtx (not part of the assumed pool sweep)? Or also the other way (wtx outpoint used in tx input and marked for deletion during poolsweep).
But the potential privacy leak is indeed a problem. And thanks for bringing this up.
What if we just make sure the wallet can handle mempool removals of any type (no protection of wtx at all)?
Worst case to handle is probably a chain (or just “flat” and multiple) of low fee self-transaction used as 0conf-inputs for a outgoing standard wtx.
Suddenly remove of a incoming 0conf wtx should be tolerated and is already possible in other wallets.
If someone spends a 0conf he takes the risk of producing a invalid wtx.
The problem is that the wallet uses the mempool as a means for estimating whether an unconfirmed transaction is expected to be confirmed.
With the memory-size-limited mempool, it pretty much loses that functionality, because when you set your limit lower than most mempools in the network, or even lower than just a few miners, that does not decrease your confirmation chances; only your ability to estimate them.
I think the better solution is to stop depending on the mempool for this, and do conflict tracking inside the wallet. Not sure I want to touch that code, though…
Does this open a new DoS vulnerability?
If you can fill transactions to the max mempool size of some peers, you can replace any dropped transaction with little additional fee. This set of transactions would propagate through any peers that have a mempool limit smaller than the set of transactions.
Perhaps an index of outputs that have been redeemed by transactions dropped from the mempool needs to exist to prevent this?
@pstratem And if a transaction is dropped from the mempool, an attacker can replace that transaction and have that replacement transaction propagate among all peers that have also dropped the transaction.
The resources used to broadcast X bytes of data to the set of nodes that the data can propagate to is the cost of uploading X bytes to my peer(s) that will propagate it.
@pstratem Yes, I considered the fact that you must have a higher fee in my first comment “you can replace any dropped transaction with little additional fee.”
If you order by fees it is very cheap to outbid your own transactions and drop them.
Update:
It’s the same issue that the replace by fee patch has around enforcing a minimum delta in fees for replacement, is that right?
Yes, however replace-by-fee has the advantage of having the transaction available, hence the suggestion of a mempool already-redeemed-output index. @sipa That prevents this attack and is much less complex than building a new index.
However, what happens when I have a 100KB transaction with lowish fees that someone wants to evict? Can no one broadcast a 500 byte transaction to that peer without paying a 100KB fee first?
I think the logic should be to pay the fee for your transaction plus the fee per kb of tx you replaced. The 100KB transaction would be dropped and the next 100KB worth of transactions added to the mempool would need account for that 100KB transactions fee.
Transactions that are old are now removed first.
The memory pool is then trimmed on a strict feerate basis.