EPIC: Pull based block prop and catchup

[evan-forbes]

The Celestia protocol will likely separate block propagation into two phases. "Preparation", for distributing data before the block is created, and "recovery" for distributing data after the block has been created. In order to utilize the data distributed before the block is created, the recovery phase must also be pull based. Therefore, the constraints for recovery are:

• 100% of the Block data MUST be delivered to >2/3 of the voting power before the ProposalTimeout is reached
• MUST use pull based gossip

context around the why and when of recovery

In order to take advantage of data gossiped during preparation, the recovery mechanism must also be pull based. This includes distributing the block directly after 2/3s have voted for the block (catchup), as those are essentially the same problem, and cannot be separated without losing a lot of efficiency. The existing mechanism is push based, which makes it incompatible with compact blocks.

Previous prototypes of compact blocks used the mempool. The problem with only using the mempool for block prop is that it is 1) still relied on a push based catchup mechanism 2) limited in the number of mechanisms that can be used to speed up block prop. This includes streaming chunks of the block, using distribution techniques for sets of haves and wants similar to vacuum, or adding erasure encoding.

The existing push based approach currently utilizes streaming and is limited to roughly 5MB/s consensus throughput for a realistic network. We must match this performance before shipping compact blocks, as this is required to handle scenarios where the demand far exceeds capacity.

Therefore, instead of leaping straight to a version of compact blocks that only uses the mempool, it makes sense to build a highly optimized pull based block prop / catchup that competes with the existing mech. Then we can add compact blocks, and later preparation

• Specify PBBT and Compact Blocks #1565
• ADR: PBBT #1598
• Add essentials for block prop reactor
• Add PBBT Messages and ValidateBasic methods
• Add customizable amounts of parity data to the part set