PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Robustness of Gossip Protocols in Modern Blockchains

Wenting Li, Jannik Albrecht, Frederik Armknecht, Ghassan Karame

arXiv:2610.21526v1cs.CR

TL;DR

Large validator committees cannot practically use complete graphs, so blockchains rely on gossip protocols whose robustness must be assessed alongside consensus quorum needs. The paper analyzes and measures deployed protocols under realistic network adversaries. Its results show that robustness and bandwidth vary substantially by protocol and parameter choice, with sufficiently high-degree random graphs providing a practical tradeoff.

  • Problem

    The paper examines how gossip protocols in large blockchain committees withstand realistic network adversaries while delivering enough messages for BFT quorum formation.

    Source: §1 · p. 1

  • Method

    The authors combine an analytical and empirical framework for random graphs with SimBlock measurements of deployed gossip protocols under targeted and mobile adversaries.

    Source: §1 · p. 2

  • Results

    Random graphs with degree d ≥15 offer strong robustness with efficiency, while Polkadot’s grid is robust but costly, Solana’s trees are fragile under attack, and GossipSub is parameter-sensitive.

    Source: §1 · p. 2, §7 · p. 15

  • Takeaways & Limitations

    Random graphs with sufficient degree emerge as a practical choice for decentralized deployments, while the studied protocols can fall short of classical BFT robustness requirements.

    Source: §7 · p. 15

    The evaluation uses SimBlock rather than live networks because live message control and controlled variation of network size and churn are infeasible.

    Source: §4.1 · p. 6

Abstract

from arXiv · show

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\H{o}s-R\'enyi (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.

1. Introduction

Large validator committees make complete communication graphs impractical, yet gossip topology can determine whether enough honest nodes receive messages for BFT quorum formation. The paper evaluates deployed gossip protocols against realistic adversaries and finds substantial robustness–bandwidth tradeoffs.

1. Introduction

  • A network partition can undermine the bounded message-delivery assumptions used in blockchain security analyses and potentially cause major forks.Source: §1 · p. 1
  • Large validator committees make complete graphs impractical, prompting platforms such as Ethereum and Polkadot to use more efficient dissemination protocols.Ethereum uses GossipSub, while Polkadot uses a grid-like protocol with a maximum two-hop distance between nodes.Source: §1 · p. 1
  • The paper asks which parameters make gossip robust against realistic adaptive adversaries and how deployed protocols compare in robustness and performance.Source: §1 · p. 2
  • The authors study robustness and efficiency after peer discovery has completed and the overlay topology has formed, using targeted attacks and mobile adversaries.They analyze random graphs analytically and empirically, then assess Polkadot, Ethereum, and Solana protocols using SimBlock measurements of delay and coverage.Source: §1 · p. 2
  • Solana’s chunk-based dissemination and dynamic trees achieve coverage comparable to other protocols with the lowest bandwidth overhead in benign settings, but fail to guarantee quorum coverage under adaptive attacks.Source: §1 · p. 2
  • Polkadot’s grid maintains high robustness against mobile adversaries, but its bandwidth overhead exceeds Solana’s by more than 20×.Source: §1 · p. 2
  • GossipSub offers moderate-to-high coverage under mobile adversaries and low bandwidth use, but misestimated message rates or latency can disconnect honest peers and rapidly degrade robustness.Its efficiency partly comes from excluding poorly performing peers from dissemination paths.Source: §1 · p. 2
  • Random graphs with fanout ≥15 offer a favorable robustness–bandwidth tradeoff for networks up to 5,000 nodes, while fanout 8 is insufficient against mobile or adaptive attacks.The authors report that sufficiently high-degree random graphs can in some cases exceed the provisions of more sophisticated protocols.Source: §1 · p. 2

2. System & Network Model

The model represents communication networks as potentially changing graphs and gossip dissemination as changes in node information states. It evaluates dissemination by the fraction of benign nodes informed over time.

2. System & Network Model

  • The extended graph model represents churn through changing topologies and dissemination through node states, supporting both protocol evaluation and attack analysis.Source: §2 · p. 2

2.1. Communication Networks

  • An Erdős–Rényi network has n nodes, with each possible edge included independently with probability p and average degree d = p · (n − 1).The model also represents churn as the fraction of nodes that may leave and rejoin, with online and offline durations drawn from a specified distribution.Source: §2.1 · p. 3

2.2. Gossip Protocol

  • Gossip begins with an origin informed and other nodes unaware; in later epochs, nodes update their states from received messages and send messages to peers according to their state.A run completes when no node’s state changes, and succeeds when all benign nodes are informed.Source: §2.2 · p. 3
  • Quality(t) measures the fraction of benign nodes informed at time t, capturing dissemination effectiveness over time.Source: §2.2 · p. 3

3. Security Model & Analysis

The analysis models realistic adversaries and evaluates gossip security through coverage and delay, then shows how node corruption can isolate honest nodes and prevent BFT quorum formation in Erdős–Rényi graphs.

3.1. Attacker Model

  • The attacker may control a bounded fraction β of nodes, act as a mobile adversary, and exploit topology knowledge; the analysis evaluates the overlay after peer discovery.The model also includes crashes and churn, and considers eclipsing and passive non-responsive behavior.Source: §3.1 · pp. 3–4

3.2. Robustness

  • Robustness is evaluated through expected coverage, the maximum fraction of benign nodes eventually informed, and delay, the time to reach that coverage.Reduced coverage can leave nodes uninformed and break consensus; increased delay can also undermine security.Source: §3.2 · p. 4

3.3. Analysis: Random Graphs with BFT

  • Corrupting less than 1/3·(1−1/n) of nodes can suffice to prevent quorum formation under the peer-corruption strategy.The analysis considers additional honest nodes isolated by having all their peers corrupted; increasing degree reduces this isolation risk.Source: §3.3 · p. 5
  • At n = 500, ER graphs with average degree d ≥12 are highly resilient, while at d = 6 and β = 0.3 coverage falls to 62.8%, preventing quorum formation.Greedy centrality-based attacks also reduce coverage below random corruption; betweenness performs slightly worse than degree or closeness centrality.Source: Figure 2 · p. 5, §3.3 · p. 6

4. Robustness Evaluation

This section evaluates message coverage, delay, and quorum robustness across random graphs, Polkadot’s grid, Ethereum’s GossipSub, and Solana’s dynamic trees under adversarial and real-world conditions, including churn.

4.1. Methodology & Setup

  • The evaluation uses a calibrated, validated SimBlock simulator because live-network tests cannot control messages, network size, or churn for comprehensive delay and robustness measurements.Extensions are checked against analytical bounds and live-network message-arrival latency distributions; the simulator abstracts away mining and generates messages at fixed intervals from randomly selected honest nodes.Source: §4.1 · p. 6
  • Experiments vary network size from 50 to 5,000 nodes, churn from 5% to 50%, and corruption bound β from 0.1 to below 0.5, with static and adaptive adversaries.The simulator uses empirically calibrated locations, latencies, and bandwidths; at 50% churn and β = 0.2, about 66.8% of nodes remain benign and online, sufficient for a classical BFT quorum.Source: §4.1 · p. 7

4.2. Robustness of Random Graphs

  • For n = 1,000 and d = 8, ER coverage falls from 68.15% at β = 0.3 to 65.51% at β = 0.32, below the BFT quorum threshold, and to 35.61% at β = 0.5.Degree- and betweenness-based attacks most strongly degrade coverage and delay; at β = 0.33, degree-based corruption increases delay from 1.49 s to 3.12 s and reduces coverage to 64.17%.Source: Figure 6 · p. 9, §4.2 · p. 9
  • In ER graphs, adaptive attacks with δcor = 10 ms suppress propagation, while coverage can approach 92% at β = 0.3 and δcor = 100 ms; 50% churn alone reduces coverage to about 85%.At β = 0.2 and 40% churn, coverage falls to about 65%; in dynamic settings, average degree has little effect.Source: §4.2 · pp. 9–10
  • For n = 5,000 and β = 0.5, increasing ER degree from 8 to 20 raises coverage from 36.04% to 49.98% and lowers delay from 6.27 s to 4.8 s.The results indicate that d ≈ 15 captures much of the robustness benefit; additional edges yield little further improvement.Source: §4.2 · p. 9, Figure 7 · p. 10

4.3. Robustness of Grid Topologies (Polkadot)

  • Polkadot’s grid maintains coverage at 1 − β in static networks, but under high churn it cannot guarantee required coverage against strong adversaries with β ∈ [0.25, 0.33].Its high connectivity supports resilience, but also increases message duplication and bandwidth overhead; at n = 500, delay rises from about 1.55 s without attacks to 2.28 s at β = 0.33, contradicting a two-hop bound for full dissemination.Source: §4.3 · p. 10

4.4. Robustness of GossipSub

  • At 0.01 msg/sec, GossipSub coverage drops to nearly 10% for n ≤ 200 even with β = 0, as peer scoring penalizes honest nodes; varying Dlazy does not change the findings.The evaluation also tests 80 KB messages at rates of 0.01, 1, and 10 messages per second over 10,000 seconds.Source: Figure 9 · p. 11, §4.4 · p. 11
  • GossipSub’s lazy pull preserves coverage under churn better than a random graph, but coverage falls below quorum at churn ≥20% versus ≥5% for the random graph.Lazy pull periodically advertises recent message metadata to Dlazy = 12 random peers; its churn coverage is comparable to a grid without excessive message overhead.Source: §4.4 · p. 11
  • GossipSub selective dropping can push coverage below quorum: at ξ = 0.5, networks of n = 100 and n = 200 reach only 66% and 65%, respectively.Other evaluated drop rates have little coverage impact, while dropping every message triggers detection and pruning; low message rates can also cause honest peers to be pruned and connections exhausted.Source: §4.4 · p. 11

4.5. Robustness of Dynamic Trees (Solana)

  • Under Solana’s real-world stake distribution, random corruption follows the equal-stake trend, whereas stake-weighted corruption prevents dissemination entirely.Equal stake is favorable to dissemination because it removes the adversary’s ability to exploit stake concentration when choosing nodes to corrupt.Source: §4.5 · p. 12
  • Solana’s dissemination delay is about 0.3 s at β = 0.1, and at β = 0.2 with 80% coverage, d = 200 takes 0.75 s in a 5,000-node network.When coverage degrades under stronger adversaries, latency becomes highly variable; the quality curve has flat periods while chunks propagate before enough arrive to reconstruct the message.Source: §4.5 · p. 12
  • For Solana, 30% churn pushes coverage below the BFT threshold when β ≥0.2, consistent with insecurity once corruption exceeds 0.2.Offline nodes affect coverage like corrupted nodes.Source: §4.5 · p. 12
  • For Solana, at β = 0.3 coverage collapses as tree height grows: d = 50 becomes insufficient for n ≥200, while d = 200 reaches ≈36% at n ≥5,000.At β ≤0.2, coverage remains healthy through n = 5,000 for d = 50; the height-related drops align with h = ⌈log_d(n)⌉.Source: §4.5 · pp. 12–13, Figure 11 · p. 13

5. Interpretation of Findings

The findings show that robustness, bandwidth use, and coverage depend strongly on topology and operating conditions. No evaluated protocol dominates across these dimensions, though sufficiently connected ER graphs offer a strong balance.

5.1. RQ1: When are Gossip Protocols Insecure?

  • For networks up to 5,000 nodes, ER coverage gains saturate at approximately d ≥15; further degree adds bandwidth overhead, while churn reduces coverage.Coverage is largely independent of network size, whereas delay grows with network size.Source: §5.1 · p. 13
  • Grid topologies keep coverage above the required bounds in all considered configurations, making them suitable when node bandwidth is not limiting.Source: §5.1 · p. 13
  • GossipSub can have insufficient coverage at low transaction rates even without adversaries, and selective dropping can push coverage below quorum while leaving adversary scores largely unaffected.Its scoring depends on message-rate and latency assumptions, making parameter tuning important.Source: §5.1 · p. 13
  • At β = 0.33, dynamic-tree coverage falls from 67% at n = 200 to at most 15% at n = 5,000; churn also weakens all four protocols, often below consensus coverage needs.For about 1,000 Solana nodes, the passage estimates only about 30% can reconstruct messages when one third crash.Source: §5.1 · p. 13

5.2. RQ2: How Do Gossip Protocols Compare?

  • ER graphs with d ≥15, grids, high-rate GossipSub with d = 8, and fully connected Solana networks achieve the best coverage in their stated settings.Dynamic trees are least reliable as network size grows or node degree falls; under churn, grids exceed ER coverage by about 1% at β = 0.1, c = 0.05, and up to 4.1% at β = 0.3, c = 0.5.Source: §5.2 · p. 13
  • Without adaptive attack, dynamic trees transfer about 142 MB, GossipSub 337 MB, ER graphs 685 MB, and grids about 2.97 GB to gossip an 80 KB message in a 1,000-node network.At one Polkadot block every 6 seconds, the grid volume amounts to 41.75 GB per node per day.Source: §5.2 · p. 14, Table 2 · p. 14
  • At β = 0.33 with corrupted nodes not relaying, transmitted volume is 226 MB for GossipSub, 515 MB for ER graphs, and 2.3 GB for grids; dynamic trees are omitted for insufficient coverage.The relative volumes are 67%, 75%, and 77% of benign volume, respectively.Source: §5.2 · p. 14, Table 2 · p. 14
  • Sufficiently connected ER graphs (d ≥15) offer a practical balance of robustness and performance without the added complexity of other protocols.The analysis concludes that none of the studied protocols achieves a markedly better robustness-performance-bandwidth tradeoff than ER graphs.Source: §5.2 · p. 14

6. Related Work

Prior work addresses gossip efficiency, robustness, and network-layer attacks through distinct approaches. The paper positions its contribution as measuring adaptive topology attacks and comparing effective coverage across multiple protocols.

6. Related Work

  • Efficiency work reduces bandwidth or latency through compact blocks, set reconciliation, or routing optimizations –.Source: §6 · p. 14
  • The paper extends GossipSub scoring analysis by measuring effective coverage alongside three other gossip protocols for direct security comparison.Source: §6 · p. 14
  • Earlier rumor-spreading analyses largely abstract away Byzantine behavior and adversarial membership manipulation,, while later approaches address Byzantine faults or static random edge corruption,.Source: §6 · p. 14
  • Network-layer studies examine eclipse and routing attacks,, –, whereas this paper targets adaptive exploitation of topology without discovery vulnerabilities or extra compromised routing resources.Source: §6 · p. 14

7. Conclusion

The conclusion reports a gap between consensus delivery assumptions and the guarantees gossip protocols provide under realistic network adversaries. Across the evaluated protocols, sufficiently high-degree random graphs emerge as a practical robustness-performance tradeoff.

7. Conclusion

  • Measurements reveal a gap between classical BFT guarantees and the guarantees existing gossip protocols provide against realistic network adversaries.Source: §7 · p. 15
  • Polkadot's grid is most robust under adaptive attacks but has very high bandwidth cost, while random graphs achieve similar robustness at d ≥15.Source: §7 · p. 15
  • Bitcoin's degree-8 random graph and Solana's dynamic trees prove unreliable under attack, while GossipSub's variable performance is highly sensitive to parameter tuning.Source: §7 · p. 15
  • Simulator code and experiment data are available for reproducibility at.Source: §7 · p. 15

Appendix A. Centrality Metrics

The appendix introduces four centrality measures used in the analysis: degree, eigenvector, betweenness, and closeness centrality.

Appendix A. Centrality Metrics

  • Degree centrality measures a node's one-hop connectivity as its degree normalized by the maximum possible degree, n−1.Source: Appendix A · p. 16
  • Eigenvector centrality accounts for a node's links and its neighbors' centrality, using the corresponding entry of the adjacency matrix's principal eigenvector.Source: Appendix A · p. 16
  • Betweenness centrality measures how often a node acts as a bridge on shortest paths between other nodes.Source: Appendix A · p. 16
  • Closeness centrality reflects a node's proximity to the rest of the network using shortest-path distances.Source: Appendix A · p. 16

Appendix B. Simulator Validation

The simulator is checked against observed message-arrival distributions from four blockchain networks, with close distribution matches reported for each. Solana’s validation accounts for its continuous, multi-shred block dissemination.

Appendix B. Simulator Validation

  • The validation compares simulated message-arrival-time CDFs and PDFs with measurements from unmodified validator nodes or public network telemetry.The authors state that direct live-network evaluation was infeasible, so they checked whether the simulator reproduces benign network behavior.Source: Appendix B · p. 16
  • Pearson correlations between simulated and observed latency distributions were 0.93 for Bitcoin, 0.99 for Polkadot, 0.95 for Ethereum, and 0.94 for Solana.Figure 12 presents CDFs and PDFs for observed and simulated propagation latencies.Source: Appendix B · pp. 17–18, Figure 12 · p. 17
  • Polkadot telemetry was self-selected and over-represented European infrastructure, so the simulated comparison used 600 predominantly European validators and 80 KB messages.Reports with zero propagation time or delays exceeding 6 seconds were excluded.Source: Appendix B · p. 17
  • Solana validation derives slot-level latency from 100 KB messages emitted every 50 ms across a 700-node network, shifting per-message distributions by offsets from 0 to 200 ms.The measured metric is the time between a node receiving the first and last shred in a slot.Source: Appendix B · p. 18

Appendix C. Peer Scoring in GossipSub

GossipSub scores mesh peers using weighted indicators that are capped or decay over time. Negative-scoring peers are pruned, and the retained scoring incentives favor long mesh tenure and prompt message delivery.

Appendix C. Peer Scoring in GossipSub

  • GossipSub’s peer score is a weighted sum of indicators, with indicators capped or decayed at intervals and rounded to zero below a threshold.The evaluation assumes a single topic and omits invalid-message and application-specific indicators because it does not simulate invalid messages.Source: Appendix C · p. 18
  • P3a penalizes peers whose message deliveries fall below a threshold during a short delivery window, which the paper says prevents replay-based attacks.The count includes messages, including duplicates, delivered within DeliveryWin3 after ActivationWin3.Source: Appendix C · p. 18
  • P3b records failed lazy-pull deliveries and carries forward when a peer is pruned, while negative-scoring peers are removed from the mesh.Pruning resets P1 and P2; P3b is retained and incremented by any active P3a penalty.Source: Appendix C · p. 18

Appendix D. Additional Plots

The appendix adds plots and a table covering adversarial effects on ER graphs, quorum formation under churn, Solana coverage, Polkadot node additions, and GossipSub lazy-pull settings. The supplied captions identify the comparisons but do not report their outcomes.

Appendix D. Additional Plots

  • The ER-graph plots examine how adversary budget β, degree d, and corruption delays affect coverage and delay.The corruption-delay plot specifies d = 8.Source: Figure 13 · p. 18, Figure 14 · p. 18, Figure 15 · p. 18
  • The additional topology plots cover Solana coverage under real-world stake distribution and the impact of adding randomly selected nodes in Polkadot..Source: Figure 17 · p. 19, Figure 16
  • The appendix also plots the impact of the number of lazy-pull nodes in GossipSub and tabulates churn’s impact on BFT and NS quorum formation.The table distinguishes outcomes for both quorum types, NS only, or neither.Source: Figure 18 · p. 19, Table 4 · p. 19

Appendix E. Ethics Considerations

The ethics discussion confines experiments to controlled simulations and publicly available validation data, and notes that some findings rely on partial topology knowledge. The included meta-review summary describes comparisons across four gossip designs and adversarial strategies.

Appendix E. Ethics Considerations

  • Experiments were conducted only in controlled simulations, without interfering with live Solana or GossipSub nodes; simulator validation used public trackers and telemetry.The paper also reports disclosing findings to Solana and GossipSub developers.Source: Appendix E · p. 19
  • Some results depend on partial topology knowledge, and Ethereum’s live mainnet topology is not publicly disclosed; the paper presents a Testnet topology reconstructed by prior work.The authors say they rely on established prior methods rather than introducing new topology-extraction techniques, citing ethical considerations.Source: Appendix E · p. 19

Appendix F. Meta-Review

  • The program committee prepared the meta-review as part of the 2027 IEEE Symposium on Security and Privacy review process..Source: Appendix F · p. 19

F.1. Summary

  • The meta-review summary describes simulations comparing Bitcoin’s ER graph, Polkadot’s grid, GossipSub, and Solana’s dynamic trees using message coverage, delay, and adversarial models.The adversaries include random corruption and selective corruption under differing levels of observability.Source: §F.1 · p. 19

F.2. Scientific Contributions

The paper studies an often-overlooked blockchain issue across widely used gossip protocols and presents a simulation framework for examining efficiency and robustness trade-offs under adversarial models.

F.2. Scientific Contributions

  • The authors present a simulation framework for studying gossip efficiency and robustness under different adversarial models.The in-depth experimental study examines trade-offs between these properties.Source: §F.3 · p. 19
  • The cross-layer study connects network behavior with consensus across gossip protocols used in important blockchain systems.The passage describes the issue as relevant to many real-world systems.Source: §F.3 · p. 19, §F.2 · p. 19

F.3. Reasons for Acceptance

  • The work is presented as a valuable step forward in an established field and as a tool for future science.These are the two reasons for acceptance named in the passage.Source: §F.3 · p. 19, §F.2 · p. 19
Loading 2610.21526v1…