Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

limit the mempool size #2344

Open
daira opened this issue May 4, 2017 · 7 comments

Comments

@daira
Copy link
Contributor

commented May 4, 2017

Review upstream patches relating to mempool size limitation, and decide on a policy and associated config options. Generally we like random-drop policies (because they are less gameable by an attacker), but there may be variations such as weighted random-drop that may be useful to consider. Upstream tends to favour fee-based policies, but privacy and affordability considerations may discourage us from taking that route for Zcash.

@zookozcash

This comment has been minimized.

Copy link

commented May 5, 2017

Red flag: Nathan mistakenly thought that the Incident Response team had required this ticket to be prioritised for 1.0.9. In fact the opposite was true, the Incident Response team (me as Executive Coordinator) had decided that we would take steps to fix the problem in the short term explicitly under the assumption that this would not imply that this ticket would be prioritised for 1.0.9.

@daira

This comment has been minimized.

Copy link
Contributor Author

commented May 5, 2017

I believe this (and #2343) is necessary to address serious denial of service vulnerabilities, and the longer we leave it out, the longer Zcash will be subject to those vulnerabilities. Whether it goes into 1.0.9 depends on the release manager's assessment of whether it's ready (currently, we don't have a patch, so it will probably have to be 1.0.10).

@daira daira added this to the 1.0.10 milestone May 5, 2017

@nathan-at-least

This comment has been minimized.

Copy link
Contributor

commented May 10, 2017

Design Caution: Zooko and I like 'random eviction' style policies for two reasons: one is that they are conceptually simple (and therefore, hopefully the code is simple), and two is that they should avoid 'wrost-case' attacks. The latter would be where a more sophisticated solution could be gamed, but a random process will always make some progress regardless of gamed input.

However, I believe a random eviction of mempool contents without other changes could, without care, lead to a bandwidth cascade that looks something like this:

  • node A mempool is too large, it evicts tx1.
  • node B mempool is too large, it evicts tx2.
  • node A and B discover the other has a transaction they don't currently have, so they send tx1 and tx2 via p2p protocol.
  • the process repeats.

If all nodes on the network are in this state, it's easy to see how without the addition of any new transactions, there will be nonterminating bandwidth use.

It's easy to avoid this in a fairly simple manner:

  • if the mempool is larger than K size, eject transactions.
  • if the mempool is larget than L size, where L < K with some sufficient buffer, do not request new transactions when you learn about them.

Another note: random ejection isn't as simple as we'd like, because we must eject any dependents.

A further note: miners may want a different policy that's more sophisticated to maximize profit. My position is that our Zcash dev team should prioritize safety and stability, and if miners want to maximize their fee profit by making a different trade-off, they should develop and maintain their own policy. (This note is true of any design decision, whether or not we use random eviction.)

@nathan-at-least

This comment has been minimized.

Copy link
Contributor

commented Jun 19, 2017

Given the complications with 'random eviction' above, I now favor a simpler policy and implementation: if adding a given transaction would require storing more than MEMPOOL_SIZE_LIMIT bytes, then do not add that new transaction.

This means old transactions are favored over new ones, and if there is a backlog, new submissions will tend to be dropped. This could be problematic if old transactions are somehow 'stuck' and could never be mined. If we implement transaction local wall-clock expiry, that is an orthogonal feature that would address 'stuck' transactions.

Finally, this policy does not maximize fees. I strongly prefer simpler policies and implementations, over complex but more competitive ones. Miners who have an interest in being competitive could develop their own logic. In fact, if we tried to make something more sophisticated, successful miners will probably still develop their own custom logic. Instead, we want to make the 'reference implementation' simpler and safer.

@nathan-at-least

This comment has been minimized.

Copy link
Contributor

commented Jun 19, 2017

Hm, if there are stuck transactions and some pathological or malicious case, it may be necessary for node operators to drop all txns from their mempool, or drop specific transactions. Do we have that either feature yet?

@str4d str4d modified the milestones: 1.0.11 Release, 1.0.10 Release Jun 21, 2017

@daira daira removed this from the 1.0.11 Release milestone Jul 3, 2017

@daira daira added this to 1.0.14: Upstream Improvements in Release planning Nov 11, 2017

@str4d str4d added this to the 1.0.14 milestone Nov 28, 2017

@str4d str4d removed this from the 1.0.14 milestone Dec 21, 2017

@str4d str4d added this to the 1.0.15 milestone Jan 2, 2018

@str4d str4d moved this from 1.0.15: Upstream Improvements to 1.1.0: Upstream Improvements in Release planning Jan 25, 2018

@str4d str4d modified the milestones: 1.0.15, 1.1.0 Jan 26, 2018

@str4d str4d moved this from 1.1.0: Upstream Improvements to 2.0.0: Upstream Improvements in Release planning Mar 30, 2018

@str4d str4d modified the milestones: v1.1.0, v2.0.0 Mar 30, 2018

@daira daira added the bug label Jun 14, 2018

@str4d str4d removed this from the v1.1.2 milestone Jul 2, 2018

@SergioDemianLerner

This comment has been minimized.

Copy link
Contributor

commented Oct 1, 2018

Related to the supposed drawback of random eviction of mempool: The tx-cycle will not happen in practice because nodes will not re-advertise a transaction without motive. They only advertise a tx when the tx is received and is not in the mempool (with some additional restrictions).
So in the sequence:

  1. node A mempool is too large, it evicts tx1.
  2. node B mempool is too large, it evicts tx2.
  3. node A and B discover the other has a transaction they don't currently have, so they send tx1 and tx2 via p2p protocol.

The last step never happens because the protocol doesn't execute steps to "discover" a transaction they don't have, unless it's advertised.

Note that if there is a continuous stream of new transactions and the mempool is full, random eviction favors newer transactions simply because older transactions have higher probability of having been removed. If there are very few new transactions and mempool is not full, then transaction expiry would come into play.

@mms710 mms710 added this to Needs Prioritization in Arborist Team Jan 3, 2019

@daira

This comment has been minimized.

Copy link
Contributor Author

commented Apr 26, 2019

We can't rely on transaction expiry to clear the mempool of transactions that are part of a DoS, because expiry is opt-in. Random drop is the best policy.

@mms710 mms710 moved this from Needs Prioritization to Protocol Backlog in Arborist Team May 1, 2019

@mms710 mms710 moved this from Protocol Backlog to Arborist Product Priorities in Arborist Team May 1, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.