Consider gossiping small blocks to improve block propagation time

[sandreim]

After a new block is produced and imported nodes announce it to the peers they are connected to by sending a BlockAnnounce message. Peers can then request the block by sending a BlockRequest message and receive back a BlockResponse containing the block data.

This approach saves bandwidth by allowing peers to request only blocks they have not seen yet, avoiding downloading it multiple times. However, there is a cost: the block propagation time increases. If for example the latency between two peers is 200ms, it takes at least 600ms for the block to propagate from one peer to another.

We should consider improving the block propagation time of the RC by introducing a gossip protocol for small blocks. This makes the validator node views synchronise faster. Parachain consensus gossip between any two nodes only works if they have a common view, so views getting in sync faster ensure faster candidate backing and approval checking which further drives smoother block times and faster finality.

For example, on the Polkadot RC, most of the blocks are around 75KB, which might make it feasible to just gossip them. Large blocks, such ones containing parachain code upgades, would still work as they do now, but that is < 1% of blocks, allowing us to be much faster 99% of the time.

For parachains this is also beneficial, especially when collators are in different geographic regions and when fast blocks are used (500ms). This would increase the chances that next authors get the block fast enough and decrease the chances of building a fork.

At first we shoild do some research and project how the bandwidth utilisation increases vs the latency benefits given the current number of expected peer connections. I'd suggest a max block size that can be gossiped to be128KB which should be good for RC, given the usage now and future usage. However, if core usage ramps up significantly we can look at increasing the threshold, but at same time block size should go down after AHM.

[sandreim]

CC @paritytech/sdk-node

[bkchr]

We first need to propagate before import, which will bring down gossip time drastically.

After we have direct propagation before import it would make sense to not send all the transactions and instead just their hash. Assuming that you have the transaction already in your local pool, you don't need to receive them a second time. If you don't have them, you could fetch them.

Your optimization kind of optimizes for empty blocks. Not sure this is the right target to optimize for. So, not sure we need this.

[sandreim]

We first need to propagate before import, which will bring down gossip time drastically.

I agree, but if we also implement what I'm saying here it will stack making it even better.

After we have direct propagation before import it would make sense to not send all the transactions and instead just their hash. Assuming that you have the transaction already in your local pool, you don't need to receive them a second time. If you don't have them, you could fetch them.

Fetching them is still subject to latency so that would increase the block execution time, making import slower. But hard to tell how often this happens in practice.

For RC we won't be able to do this and there should not be transactions on RC after AHM.

Your optimization kind of optimizes for empty blocks. Not sure this is the right target to optimize for. So, not sure we need this.

I am thinking it holds most value for RC. Some simple estimations show that BackedCandidate would take ~659 bytes, assuming no messages are being sent via HRMP/UMP. That means 132kb if all 200 cores are backing a candidate. While I'd love to have this problem, is not realistic. I'd say that 50% is something more realistic and you end up with around 66kb of bytes in backed candidates.

Messaging in the future should be happening off-chain and only posting a few hashes on-chain, so I'd still think we'd fit in 256kb worse case scenario long term. If that is a workable number in terms of bandwidth, it would still be a good idea to implement this after we do #65

[burdges]

We should consider improving the block propagation time of the RC by introducing a gossip protocol for small blocks. This makes the validator node views synchronise faster.

This is fine, provided one pays close attention to bandwidth, etc. Academic CS would claim this is a true gossip protocol and more secure than what we do now, but academic CS maybe full of shit here. ;)

At a higher level..

@AlistairStewart and I have discussed faster gossip schemes a fair bit, especially recently, both for parachains and the relay chain. And Alistair has been breaking Aptos and Sui's liveness. And Alistair recently gave a research team talk on the various hot fast concensus protocol.

As a loose rule, these faster gossip schemes have often used erasure coding so they obtain guarantees resembling the supposed gossip guarantees but faster.

PC: At the parachain level, we anyways need existing RC avaliability scheme, so when PC liveness fails we fallback quickly to collators reconstructing from all validators, ala polkadot-fellows/RFCs#154 or maybe systematic validators first if fast enough. We then have considerable flexibility undernear the umbrella of this RC availability fallback.

As a memepool-free example, we have each collator i make micro-basti-ish blocks b_{s,i} from the tx it recieved, and send b_{s,i} to every collator, so then the assigned block producer j creates the real block b_s for their slot s by selecting some compatible subset of the b_{s,i}. In this, each collator sees each micro-basti-ish block b_{s,i} twice, once from i and once from j. We could optimise this future in several ways, or provide weak assurances using rateless codes, but imho all that complexity sounds unecessary. Instead, if k has a slot much later than j then maybe k could delay checking b_{s,i} and instead check only b_s from j.

RC: Alistair convinced me we should update polkadot-fellows/RFCs#144 to do a two step concensus, but exactly if/how we'd do availability remains unclear so far. It's tempting to make core 0 always be the RC block itself, but this requires 2+ round of availability bitfield votes.