On the Robustness of Gossip Protocols in Modern Blockchains
Study finds common blockchain gossip settings may fail to deliver quorum messages under realistic adversaries.
The paper analyzes gossip used by large validator committees in Ethereum, Polkadot, Bitcoin, and Solana against realistic network adversaries. Analytically and empirically, commonly chosen random-graph parameters do not guarantee that enough honest nodes receive consensus messages to form a quorum. Solana's dynamic trees are efficient but fragile, Polkadot's grid is robust at high bandwidth cost, and Ethereum GossipSub is efficient and resilient yet parameter-sensitive. Erdős-Rényi graphs offer a strong tradeoff when average fanout exceeds 15 for networks up to 5000 nodes.
- Typical random-graph settings may not deliver quorum messages to enough honest nodes.
- Solana trees are bandwidth-efficient but fragile under adaptive attacks.
- Polkadot's grid is robust but bandwidth-heavy; GossipSub is sensitive to parameters.
- ER graphs work well when average fanout exceeds 15 for up to 5000 nodes.
Full article194 words · extracted from arxiv.org · click to collapse
Modern platforms such as Ethereum and Polkadot nowadays execute Byzantine fault-tolerant consensus protocols over large validator committees, often comprising hundreds of nodes. At this scale, complete graph topologies for connecting nodes are impractical, leading systems to adopt various gossip mechanisms, often in an ad hoc manner. In this paper, we study the robustness of widely deployed gossip protocols used in committee-based blockchains against realistic network adversaries. We show, both analytically and through extensive empirical measurements, that the graph parameters commonly chosen to instantiate random graphs are insufficient to guarantee that enough honest nodes receive consensus messages for quorum formation in existing protocols. Motivated by this finding, we empirically assess the robustness of Bitcoin's Erdős-Rényi (ER) graphs, Polkadot's grid topology, Ethereum's GossipSub, and Solana's chunk- and tree-based disseminations. Our results reveal surprising tradeoffs: Solana's dynamic trees are bandwidth-efficient in benign settings but fragile under adaptive attacks; Polkadot's grid achieves strong robustness at the cost of high bandwidth overhead; GossipSub is both bandwidth-efficient and resilient to adaptive adversaries, yet highly sensitive to parameter choices; and ER graphs provide a strong robustness-efficiency tradeoff, e.g., when the (average) fanout degree exceeds 15 for networks up to 5000 nodes.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2610.21526