On the Robustness of Gossip Protocols in Modern Blockchains

The gist: The study investigates how graph parameters commonly chosen for gossip protocols in committee-based blockchains are insufficient to guarantee enough honest nodes receive consensus messages for quorum formation against realistic adaptive adversaries.

Motivation and Problem

Modern platforms execute Byzantine fault-tolerant consensus protocols over large validator committees, often comprising hundreds of nodes, which makes complete graph topologies impractical At this scale, complete graph topologies for connecting nodes are impractical, leading systems to adopt various gossip mechanisms The interplay between the network layer and the consensus layer has been largely overlooked, with most existing designs treating these two components almost in isolation This separation appears to be an artifact of the field’s development The analysis aims to answer the following research questions: RQ1: Under which parameters and settings are gossip protocols robust against realistic adaptive adversaries? RQ2: How do various gossip protocols compare with respect to their robustness and performance?

Adversarial Model and Robustness Metrics

The framework incorporates a practical threat model with targeted attacks and mobile adversaries, which can release corrupted nodes and corrupt others as the network evolves Adversarial Actions include bounding the fraction of corrupted nodes by parameter β ∈ [0, 1] The model accounts for node corruption through the method Corrupt(N∗) which results in all nodes in Ncor t:= Nt ∩ N ∗ being corrupted and placed under the attackers control Adversarial Knowledge includes full knowledge of the graph, minimum knowledge, and partial knowledge, with the analysis targeting the robustness of the gossip layer itself Robustness is evaluated using two security-critical metrics: Coverage (omega = maxt≥tstart[Quality(t)] denotes the highest possible fraction of benign nodes that eventually will be informed) and Delay (∆ = min[δ ≥ 0Quality(tstart + δ) = omega] is the minimum time it takes until the maximum coverage is achieved)

Analysis of Random Graphs

The analysis shows that the default parameters used in currently deployed random graph topologies (such as Bitcoin’s fanout degree of 8, or the de facto standard fanout degree of ln (n) in random graphs of size n [13]) are ill-suited for composition with classical Byzint Fault Tolerance (BFT) protocols For example, corrupting nodes c and d suffices to reduce the largest connected component of honest nodes to at most two nodes, which is too limited to reach the minimum quorum size of 1/3(n − 1) = 5 required for classical BFT consensus A straightforward strategy consists of randomly corrupting ncor nodes, with the additional effect that coverage can reach up to Ω ≥ 1 − β against an adaptive adversary that can reassign its corrupted nodes during propagation Greedy strategies, such as peer-corruption-strategy, show that β > d3d + 1·(1 − 1/n) is a sufficient criterion to prevent quorum formation in classical BFT protocols

Comparison of Gossip Protocols

The results reveal surprising tradeoffs: Solanas dynamic trees are bandwidth-efficient in benign settings but fragile under adaptive attacks, while Polkadots 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 ER graphs provide a strong robustness efficiency tradeoff, e.g., when the (average) fanout degree exceeds 15 for networks up to 5000 nodes In contrast, Solanas dynamic trees with chunk-based dissemination cannot guarantee sufficient coverage for any network size or fanout satisfying n > d when β = 0.33

Conclusion and Practical Choices

The best coverage is achieved by ER graphs with a sufficiently large node degree (d ≥ 15), by grid topologies across most settings, by GossipSub with a targeted node degree of d = 8 when message rate λ is high, and in Solana for fully connected networks Overall, despite their simplicity, random graphs with a sufficient degree emerge as a practical choice for decentralized deployments, offering a strong balance between robustness and performance while remaining simple to analyze and implement The authors conclude that none of the modern gossip protocols we study achieves a markedly better tradeoff between robustness, performance, and bandwidth than a simple Erdos–Rényi (ER) random graph, a structure whose properties are well understood

How it works

The model extends existing graph models along two dimensions: it incorporates dynamic topologies that account for churn and introduces node states to represent information dissemination The extended graph model not only forms the basis for the evaluation in Section 4 but also allows for characterizing new attacks that yield the bounds in Section 3.3

System and Network Model

A communication network is modeled as an undirected graph G = (N, E), where nodes N represent the members of the network, and the edges E ⊆ N × N their communication links Permissionless blockchain networks are commonly modeled by Erdos–Réyni graphs G(n, p) Churn is captured via the churn rate c, which represents the fraction of nodes that may leave and rejoin the network

Gossip Protocol Modeling

Each node is modeled as being stateful, where State(N, t) ∈ S is the state of node N at point in time t At subsequent epochs t > tstart, the node first updates its state based on messages received in the previous epoch and then sends messages to its peers depending on its state The gossip protocol is successful if, upon completion, all benign nodes are informed that is Ntend,sfinal = Ntend

Robustness Evaluation

The empirical measurements use SimBlock [10], [16], an event-based blockchain network simulator implemented in Java The simulator takes as input the network topology that emerges once peer discovery completes and evaluates its resilience to attack We vary the network size from 50 to 5,000 nodes and mark a fraction of nodes as churn nodes c ∈ [5%, 50%] that periodically join and leave

Topologies Evaluated

We consider undirected network graphs G = (N, E) and evaluate three topology classes as follows: Random Graphs (unstructured topology), Grid Matrix (fully structured topology), and Dynamic Trees (semi-structured topology)

Empirical Results Summary

Coverage is always at the respective bound (1 − β) for static networks, indicating that the remaining honest nodes stay connected despite corruption The delay increases with the adversarial bound β, as corrupted nodes effectively remove edges and lengthen paths However, at high churn rates, it fails to guarantee the required coverage against strong adversaries (β ∈ [0.25, 0.33]) The grid topology’s high connectivity provides strong resilience against adversarial behavior GossipSub exhibits insufficient coverage at low transaction rates, and its peerscoring mechanism implicitly assumes more than one transaction per second The dynamic trees with double recovery chunks cannot guarantee sufficient coverage for any network size or fanout satisfying n > d when β = 0.

1. Bold Header: Improved Consensus Resilience via Degree Thresholds

The system can maintain quorum formation against adaptive attacks when employing Erdos–Rényi graphs with a sufficiently high fanout degree, specifically exceeding 15 for networks up to 5000 nodes. This allows the AI system to achieve robustness even under mobile adversaries.

2. Bold Header: Optimized Network Topology Selection

The AI can dynamically select network topologies based on required robustness trade-offs; for instance, choosing a grid topology ensures strong robustness at the cost of high bandwidth overhead, while random graphs require a degree d ≥ 15 for comparable performance to grids in certain settings.

3. Bold Header: Adaptive Gossip Protocol Tuning

The system can dynamically tune GossipSub parameters, specifically careful parameter tuning, to maintain resilience against adaptive adversaries by adjusting the score refresh interval and penalty weight when message rates or network latency are misestimated.

4. Bold Header: Robust Message Dissemination for Low-Rate Systems

For AI systems operating at low transaction rates, the protocol can be configured with GossipSub to ensure coverage matches that of grids and random graphs with only about half the node degree, leveraging its peer scoring mechanism to preferentially disconnect underperforming peers.

5. Bold Header: Dynamic Tree Protocol Reliability Assessment

The system can predict failure points in Solana’s dynamic trees, as the paper shows that for a corruption bound of β = 0.33, coverage degrades sharply, from 67% at n = 200 to at most 15% at n = 5,000, indicating where the protocol is insufficient to form a quorum.