WIP: Update mempool performance

[dmalkr]

Preliminary questions

• [ ] Does almost all nodes must have current transaction set for work, or just majority of nodes (2/3+)?
• [ ] Which is most probably count of nodes in system? 10, 100, 1000, 1000000?
• [ ] Does we need transaction exchange for PoS, PoW or for both?

Network improvement

Definition. Let's map all transactions to small bitmap using some hash function (or even last TXID bits). We below call such bitmap as "mempool bitmap", or just "bitmap".

• [ ] Pull-based quering about transactions. One node can generate random bitmaps (which in OR-sum form bitmap all filled with "1") and dispatch connected nodes. Other nodes send only matched transactions. This method can be used to initialize mempool when new node starts (or when node was offline a long period of time).
• [ ] Bitmap size. Average mempool size in BitCoin according to https://jochen-hoenicke.de/queue/#0,1y is 10000 transactions. We can use this value to estimate our future size. So 2^15 - 2^16 bits (32768-65536 bits) length is enough for the bitmap (which represents mempool) to be sparse. And also it is relatively small: 4-8Kb.
• [ ] Push based spead of a single transaction. When transaction appear, it can be broadcasted across the network by push. What to do with duplication of this transaction on some nodes? Is it important?
  • [ ] Or node can collect transactions a short period of time, and other nodes can query it periodically (using pull-based & bitmap-based method).

Filtering

• [ ] It is need to benchmark first and select suitable data structure...

---

See also: #430, #58

[Shimuuar]

In my understanding any blockchain where anyone could submit transaction will need some variant of mempool to keep and propagate transactions which are not included in the blocks. Naturally mempool cannot provide any guarantee and transactions are disseminated on best effort basis. Only protection against censorship is number of nodes and routes and network and that most nodes have no interest in censorship. More specifically:

Does almost all nodes must have current transaction set for work, or just majority of nodes (2/3+)?

I think in mempool there's almost no MUSTs in RFC meaning. Miners/validators can continue to work regardless of mempool content. They still want to include as many TXs as possible for economic reasons.

Figures of merit for mempool are a) how long it takes for TX to propagate to 95% (or some other value) of nodes in the network. b) how quickly node that just joined network could sync mempool

Which is most probably count of nodes in system? 10, 100, 1000, 1000000?

Nobody knows. Hopefully a lot bitcoin has about 10^4-10^5 full nodes. Estimates are wildly different. If system is adopted we should have at least thousands of nodes.

Does we need transaction exchange for PoS, PoW or for both?

For all of them

[dmalkr]

So there are following tasks:

• benchmarks:
  • [ ] local benchmarks (improve Jupyter notebook for estimate mempool stats)
  • [ ] network benchmarks (for that 4-nodes "real Moscow network cluster")
  • so we will know current mempool speed and current mempool issues; and also can compare improvements
• [ ] find suitable data structure for 1) fast removing, 2) sorting (or fast extraction) by transaction fee
• [ ] implement transaction download via pull queries
• [ ] (re)implement sole transaction query via push queries
• [ ] maybe implement fast two-stage mempool clearing (see discussion with Alexey 17.02.2020)