Limit the size and age of the ZIP-401 rejected transaction ID list

[mpguerra]

Motivation

ZIP-401 limits the number of transactions in the rejected list, and the age of the entries in that list.

This Ticket Depends On

RecentlyEvicted:

• Randomly evict mempool transactions based on their eviction weights #2780
  • Add the serialized transaction size to UnminedTx #2778
  • Return the transaction fee in the mempool response #2779
    • Look up the UTXOs in the transaction verifier, then pass them to verify_transparent_inputs_and_outputs #2440

Specification

The checked items are covered by other tickets.

EvictTransaction MUST do the following:

• Select a random transaction to evict, with probability in direct proportion to eviction weight.
• Add the txid and the current time to RecentlyEvicted,
  • dropping the oldest entry in RecentlyEvicted if necessary to keep it to at most eviction_memory_entries entries.
• Remove [the randomly selected transaction] from the mempool.

• Nodes SHOULD remove transactions from RecentlyEvicted that were evicted more than mempoolevictionmemoryminutes minutes ago. This MAY be done periodically, and/or just before RecentlyEvicted is accessed when receiving a transaction.

https://zips.z.cash/zip-0401#specification

Design

The ZIP-401 reject list must be implemented as a new list in MempoolStorage. This avoids bugs that confuse different rejection rules.

Since this time is only used by the local node, it should be monotonic (strictly increasing):
https://docs.rs/tokio/1.11.0/tokio/time/struct.Instant.html

If we use an IndexMap<transaction::Hash, Instant>, we can efficiently evict transaction IDs by using IndexMap::pop, until we reach a transaction that's below the eviction limit:
https://docs.rs/indexmap/1.7.0/indexmap/map/struct.IndexMap.html#order

[mpguerra]

Are we already doing this? It was in the list of mempool tasks but did not have an issue number assigned

[upbqdn]

This is part of #2744:

Rejected set is recommended capped at 40K, we should check if everything we currently put in the rejected set maps to what ZIP-401 considers part of that 40K.

[teor2345]

This is part of #2744:

Rejected set is recommended capped at 40K, we should check if everything we currently put in the rejected set maps to what ZIP-401 considers part of that 40K.

#2744 is a very large ticket, so I'm splitting it up into sub-tickets.

[teor2345]

Hey team! Please add your planning poker estimate with ZenHub @conradoplg @dconnolly @jvff @oxarbitrage @upbqdn

[conradoplg]

If we use an IndexMap<transaction::Hash, Instant>, we can efficiently evict transaction IDs by using IndexMap::pop, until we reach a transaction that's below the eviction limit: https://docs.rs/indexmap/1.7.0/indexmap/map/struct.IndexMap.html#order

I think that doesn't work because pop removes the last inserted item (newest) and we need to remove starting from the first (oldest). We can remove the first item with shift_remove but it's O(n).

I've searched a bit and couldn't find any library that would solve that, so I think the solution is to have another list (VecDeque) with (Hash, Instant) tuples. What do you think @teor2345 ?

[teor2345]

If we use an IndexMap<transaction::Hash, Instant>, we can efficiently evict transaction IDs by using IndexMap::pop, until we reach a transaction that's below the eviction limit: https://docs.rs/indexmap/1.7.0/indexmap/map/struct.IndexMap.html#order

I think that doesn't work because pop removes the last inserted item (newest) and we need to remove starting from the first (oldest). We can remove the first item with shift_remove but it's O(n).

I've searched a bit and couldn't find any library that would solve that, so I think the solution is to have another list (VecDeque) with (Hash, Instant) tuples. What do you think @teor2345 ?

Yeah, I think you're right.

Here's one way we could implement this

• ordered_entries: VecDeque<(transaction::Hash, Instant)> - reject list entries in insertion order, allows duplicate Hashes
• unique_entries: HashMap<transaction::Hash, Instant> - unique reject list entries and their most recent insertion times

Here's how we could implement the operations:

Add or update the age of an entry - O(1):
- push onto the back of ordered_entries
- insert or replace in unique_entries

Remove the oldest entries when they have expired - O(expired):

• search from the front of ordered_entries for the first time that hasn't expired
• drain the expired entries from ordered_entries
  • also remove the ID from unique_entries if the times are equal

Remove the oldest entry when the list is too long - O(1):

• remove the excess entry from the front of ordered_entries
• remove the ID from unique_entries if the times are equal