Investigate how to optimize transaction propagation

[lasarojc]

This tasks tracks efforts in investigating how to optimize the propagation of transactions, namely the mempool protocol.

The goal is to investigate the literature on the topic and existing solutions adopted by other blockchain products in order to identify alternative propagation approaches that may be applied to CometBFT. Even if an approach cannot be directly applied to CometBFT, it may have aspects that might be considered on future designs of the mempool.

Original issue: tendermint/tendermint#9925

Literature

Transaction propagation can be translated into gossiping pieces of information in an unknown, unstructured, and partially connected network. Some fundamental and general references for gossip to start the investigation:

• Epidemic algorithms for replicated database maintenance (1987)
• Bimodal Multicast (1999)
• Gossip (book chapter, 2011)

In addition, we should survey literature on gossip and anti-entropy protocols, with an emphasis on BFT solutions.

Other protocols

This is a (not comprehensive and under construction) list of existing solutions for transaction propagation:

• Celestia
  • Content Addressable Transaction Pool
  • This topic was already discussed, but we need to document the outputs
• Narwhal mempool:
  • https://github.com/MystenLabs/narwhal
  • https://decentralizedthoughts.github.io/2022-06-28-DAG-meets-BFT/
  • https://www.youtube.com/watch?v=K5ph4-7vvHk
• Solana:
  • gulf-stream
• CodedHotstuff
• Anoma/Thyphon:
  • https://arxiv.org/abs/2306.16153

Definition of Done

• We have identified alternatives for transaction propagating that may be applied to CometBFT.
• We have an initial comparison of pros and cons of each alternative we have identified and investigated.

[lasarojc]

It makes sense to talk only about mempool here, but I believe the result of this step will actually provide some guidance on consensus as well. You may want o capture this as an added bonus for this issue.

[cason]

It makes sense to talk only about consensus here, but I believe the resoult of this step will actually provide some guidance on consensus as well. You may want o capture this as an added bonus for this issue.

Do you mean mempool?

[lasarojc]

Some extra references

• https://arxiv.org/pdf/2101.00378.pdf
• https://bitcoincore.org/en/2016/06/07/compact-blocks-faq/
• https://www.youtube.com/watch?v=z7rC95kCGJ0
• Coded Hotstuff: https://dspace.mit.edu/bitstream/handle/1721.1/147694/3548606.3563494.pdf?sequence=1&isAllowed=y

[matthewdowney]

Suggesting Aeron's UDP multicast approach to improving message passing perf without compromising too much on reliability as one more resource related to the bimodal multicast literature.

In tradfi it's used in a different context (Raft consensus) but certain design elements might translate.