Randomly evict mempool transactions based on their eviction weights

[teor2345]

Motivation

ZIP-401 specifies weighted random mempool transaction evictions:
https://zips.z.cash/zip-0401#specification

This Ticket Depends On

match by txid not wtxid:

• Match rejected transactions correctly by TXID or WTXID #2819

serialized transaction size in bytes:

• Add the serialized transaction size to UnminedTx #2778

transaction fee:

• 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

Consensus Rules

The mempool of a node holds a set of transactions.
Each transaction has a cost, which is an integer defined as:
max(serialized transaction size in bytes, 4000)

Each transaction also has an eviction weight, which is cost + low_fee_penalty,
where low_fee_penalty is 16000 if the transaction pays a fee less than the conventional fee, otherwise 0. The conventional fee is currently defined as 1000 zatoshis.

Each node also MUST hold a FIFO queue RecentlyEvicted of pairs (txid, time), where the time indicates when the transaction with the given txid was evicted. The txid (rather than the wtxid ...) is used even for version 5 transactions after activation of NU5.

On receiving a transaction:

• If it is in RecentlyEvicted, the transaction MUST be dropped.
• Calculate its cost. If the total cost of transactions in the mempool including this one would exceed mempooltxcostlimit, then the node MUST repeatedly call EvictTransaction (with the new transaction included as a candidate to evict) until the total cost does not exceed mempooltxcostlimit.

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 ...
• Remove [the randomly selected transaction] from the mempool.

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

Design

rand::distributions::weighted::WeightedIndex is a weighted random implementation from a very popular crate.

It supports any collection type with continuous integer indexes. (Like Vec or VecDeque.)

[teor2345]

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

[teor2345]

This ticket's dependencies conflict with the NU5 block validation code freeze, so it needs to be done after NU5 testnet activation in sprint 19.

[teor2345]

Partly unblocked by just using zero fees until #2779 gets merged.