Faster and better mempool

[Shimuuar]

Filtering and creation of new block

Performance here is more critical for PoW since miner wants to create new candidate block as soon as he receives new block. Time spent for creation of candidate block is time lost for mining. Below I make assumption that conflicting transaction are relatively rare.

1. Remove all transactions from new block using their hashes. We probably already computed hashes of all transaction during block verification.
2. Split transaction validation in two parts: a) context free that doesn't depend on blockchain state and b) contextual validation that depends on state. Only do former once.
3. Non-miners/proposers should filter mempool asynchronously.
4. There's interesting interplay between block creation and removing invalid transactions. When we select transactions for block we have to validate them in context of all previous transactions. This validation could be reused for discarding now invalid transactions. Things become a bit more complicated in case of conflicting TXs. For example if we have two transactions: A & B which try to spend same output. Both could reside in mempool. If we already included A then B will be marked as invalid. It's however will be valid as long as A is not committed to the blockchain. I'm not sure how much it's of a problem

Transaction selection

We also want to be able to sort transaction by their fee/size ratio (or whatever is figure of merit for the miners). Right now they're stored in simple FIFO order. We may need to keep FIFO for transaction gossip purposes.

Gossip

Current transaction gossip is grossly inefficient. Node just send every transaction is has to every node. Following strategy should be more efficient:

1. Once node gets new transaction it broadcasts tx to all peers. This should make transaction propagation faster.
2. transaction already in mempool are transmitted only on request. When node starts andits mempool is empty it sends request for tx to its peers. Request should include list of tx/bloom filter for hashes of tx it has already.

[thesz]

May I suggest a "partial parsing" approach?

First, I am thinking about possibly massively parallel monoidal parsing ([1] and [2] and [3]). Or, if you prefer, a parallel scan.

We sort transactions by their profitability first and perform beam search (basically, a breadth-first search with constrained front size). This can allow us to address several edge cases: we choose between conflicting transactions based on their profitability and we can also handle inclusion of less profitable transactions that allow for more profitable transactions to be included.

The validation part can also be handled partially: for each transaction we can add requirement that effects on the left provide necessary conditions; we also provide effects of transaction; when combining two transactions (or lists of transactions) we Logically AND required conditions that are not canceled and Logically OR conditions that are produced.

Essentially, it is application of associative operation in monoidal parsing or parallel prefix sums. Logical ANDs and ORs above can be implemented as merge operations, for most of the time.

And, as a side note, we can also select transactions that most probably will not be selected in a block or two. That would allow to spend more time selecting these and spare us from checking state more often when new block is received.