Refactor spend conflict checks in the mempool storage to increase performance

[jvff]

Motivation

ZIP-401 prevents memory DoS by setting a maximum mempool size. This mempool size is much larger than Zebra's current mempool size.

PR #2765 implemented a simple algorithm to check if a transaction has spend conflicts with another transaction already in the mempool.

That algorithm works well for a mempool with few transactions. But as the size of the mempool increases, performance will be impacted. The algorithm is O(n*m), where n is the number of spent UTXOs and revealed nullifiers in the transaction and m is the number of spent UTXOs and revealed nullifiers in all transactions already in the mempool.

So as part of implementing ZIP-401, we need to make the spend conflict checks more efficient. Otherwise, we replace a memory DoS with a CPU DoS.

Specifications

Adoption of this proposal would increase robustness of Zcash nodes against denial-of-service attack, in particular attacks that attempt to exhaust node memory.

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

The default value of 80000000 for mempooltxcostlimit represents no more than 40 blocks’ worth of transactions in the worst case, which is the default expiration height after the Blossom network upgrade.

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

Designs

The original idea was to to cache the spent UTXOs and revealed nullifiers from all transactions in
the mempool using HashSets. This would mean that the conflict check would only be O(n), but it adds complexity to the code to add a transaction to the mempool and to remove a transaction from the mempool, because the caches must be updated.

If this idea is implemented, the has_spend_conflicts method could be updated to something like:

fn has_spend_conflicts<'slf, 'tx, Extractor, Outputs, Output>(
    &'slf self,
    tx: &'tx UnminedTx,
    extractor: Extractor,
    existing_outputs: &'slf HashSet<Output>,
) -> bool
where
    'slf: 'tx,
    Extractor: Fn(&'tx Transaction) -> Outputs,
    Outputs: IntoIterator<Item = Output>,
    Output: Eq + Hash + 'tx,
{
    let new_outputs = extractor(&tx.transaction).into_iter();

    new_outputs.any(|output| existing_outputs.contains(output))
}

[teor2345]

If we need to look up the conflicting transaction, we might want a HashMap<Output, transaction::Hash>.

But I don't know if we'll need to do that - I guess we'll find out!

[teor2345]

We moved the eviction tickets to the next sprint, so I'm going to move this one too.

[mpguerra]

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

[mpguerra]

This definitely seems optional, so I'm going to un-schedule it for now, it will still be tracked in the mempool epic for when we think the mempool will be large enough that this is necessary