Proposer often gossips the first block parts to all peers

[evan-forbes]

Currently when the proposer creates a block, it will send each block part over the internal message queue. This can actually take a some time. The gossip routine doesn't account for that and will start gossiping immediately, which results in sending the same block parts to all peers instead of sending them randomly.

This is why when we trace the block parts, we often see them downloaded in order. This also defeats the purpose of using block parts entirely, as we end up gossiping the entire block to all peers.

below we can see a diagram that illustrates block propagation for a given height that shows this occuring. on the y axis we have block part indexes, and on the x axis

If we simply wait for the block to go over the internal message queue before gossiping, it fixes the issue and we gossip all of the block parts randomly!

There's still quite a bit of room to optimize which parts we send to each peer. One simple non-breaking change would be to not gossip block parts entirely randomly. Instead, we should keep track of which parts have been sent to any peer, and prefer to send a part to a peer if it has been sent to fewer peers.

While I'm convinced that this was one of the bottlenecks, it certainly isn't the only one since this change still doesn't increase throughput on its own. ATM, I think there's quite a lot of backup occurring, because we frequently end up receiving block parts super late.

[ebuchman]

Nice find! There's some old related issues, see HasPropoposalBlockPart (tendermint/tendermint#627) and the idea of gossiping block parts rarest first (tendermint/spec#309). But seems this specific problem had been missed!

HasProposalBlockPart (along with some strategic sleeps) was actually implemented last year (see cometbft/cometbft#904) and should have pretty significant bandwidth improvements for large blocks and large networks. I wonder if it would address a lot of what you're seeing here. Though probably there will still be inefficiency from sending everyone the first part first so I think waiting for the full proposal to be sent over the queue also makes a lot of sense.