On the Robustness of Gossip Protocols in Modern Blockchains

On the Robustness of Gossip Protocols in Modern Blockchains

arXiv:2610.21526v1 [cs.CR] 15 Oct 2026

Wenting Li∗ , Jannik Albrecht∗ , Frederik Armknecht‡ , and Ghassan Karame∗

∗ Ruhr University Bochum, Germany

‡ University of Mannheim, Germany

first.last@ruhr-uni-bochum.de

armknecht@uni-mannheim.de

Abstract—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, Polkadots grid topology, Ethereums GossipSub, and Solanas chunk- and tree-based disseminations. Our results reveal surprising tradeoffs: Solanas dynamic trees are bandwidth-efficient in benign settings but fragile under adaptive attacks; 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; and ER graphs provide a strong robustnessefficiency tradeoff, e.g., when the (average) fanout degree exceeds 15 for networks up to 5000 nodes.

1. Introduction Decentralized platforms are rapidly gaining ground as a key technology in blockchain deployments, machine learning (e.g., federated and decentralized learning [1]–[3]), social networks (e.g., federated social networks such as Mastodon [4], [5]), file storage (e.g., IFPS [6]), and content and music distribution (e.g., Odysee [7] and Audius [8]). At the core of almost all decentralized deployments lies a peerto-peer (P2P) network that is responsible for reliably propagating critical information and metadata to all nodes. For instance, the security analysis of blockchain protocols often assumes a synchronous model where messages arrive at all nodes within a bounded delay window [9]. Any partition in the P2P network, however, can break these guarantees [10], potentially causing major forks [11]. The interplay between the network layer and the consensus layer has been largely overlooked, with most ex-

isting designs treating these two components almost in isolation. This separation appears to be an artifact of the field’s development. Historically, BFT protocols were deployed on only a small number of nodes. With such a limited scale, a complete graph was the natural choice: every node could communicate directly with every other, keeping overhead tolerable. Today, however, platforms such as Ethereum, Polkadot, and Cosmos run BFT-style consensus across large validator committees. For the first time in decades, BFT protocols operate at scale, involving hundreds or even thousands of participantsfor example, Ethereum and Polkadot maintain validator committees of roughly 9,000 and 600 nodes, respectively. This substantial increase in committee size renders the reliance on complete graphs impractical. Consequently, modern decentralized platforms have replaced them with more sophisticated dissemination protocols, adapted from the P2P networking literature, to enable validators to exchange information efficiently and reach consensus at scale. Ethereum, for example, uses GossipSub [12] to organize nodes into a mesh network in which full messages are pushed across peers, complemented by metadata-only links that periodically advertise information about recently seen messages. Polkadot, in contrast, uses a grid-like dissemination protocol that guarantees a maximum two-hop distance between any two nodes, ensuring rapid and efficient information propagation. This disconnect (i.e., designing network protocols and consensus protocols in isolation) is not only inefficient but also affects safety and liveness. For example, consider the graphs in Figure 1, each consisting of n = 7 nodes, where nodes run a classical BFT-style consensus algorithm (similar to that used in Ethereum) to agree on the next block. Here, an adversary may corrupt up to two nodes, which falls well within the BFT compromise threshold of ≤ 13 (n − 1). In Figure 1a, corrupting nodes c and d suffices to reduce the largest connected component of honest nodes to at most two nodes. Since coverage (i.e., the maximum number of honest nodes that receive a gossip) is then too limited to reach the minimum quorum size of 13 (2n + 1) = 5 required for classical BFT consensus, the protocol is likely to fail in making progress. The graph in Figure 1b, by contrast, tolerates the corruption of any two nodes without the coverage dropping below 5. In other words, the graph in Figure 1b is clearly more robust than that of Figure 1a. In this paper, we address the fundamental problem of

network simulator SimBlock [16] to measure delay (the maximum time for a gossip to spread) and coverage (maximum number of nodes that receive the gossip) of the gossip mechanisms employed by Polkadot, Ethereum, and Solana with respect to various parameters, such as the network size, the fanout degree, the churn rate, and various adversarial strategies (Section 4). Our analysis in Section 5 reveals the following surprising results: In the absence of attacks, Solanas gossip protocol (i.e., dynamic trees combined with chunk-based dissemination) achieves coverage comparable to that of other gossip protocols while incurring the lowest bandwidth overhead. However, under realistic adaptive attacks, Solana exhibits the lowest robustness and fails to guarantee the minimum coverage required to form a quorum. • Polkadots grid topology, in contrast, maintains consistently high robustness even in the presence of mobile adversaries, but this robustness comes at the cost of substantial bandwidth overhead, exceeding that of Solana by more than a factor of 20. • GossipSub achieves moderate to high coverage under mobile adversaries and is the most bandwidth-efficient protocol in this setting, as it actively excludes poorly performing peers from dissemination paths. This efficiency, however, depends critically on careful parameter tuning: if the expected message rate or network latency is misestimated, GossipSub may disconnect not only corrupted peers but also honest ones, leading to a rapid degradation in robustness. • Random graphs fail to provide sufficient robustness against mobile/adaptive attacks when configured with a fanout of 8, as in Bitcoin.1 However, with an appropriately chosen fanout degree (≥ 15 ≫ ln (5,000) for up to n = 5,000 nodes), they strike a favorable trade-off between robustness and bandwidth efficiency, in some cases exceeding the provisions of more sophisticated protocols. • Last but not least, network churn significantly further degrades the robustness of existing gossip protocols, preventing quorum formation across most studied protocols. •

(a) Example 1

(b) Example 2

Figure 1: Two examples with different graph topologies. A compromise of two nodes in Figure 1a reduces the coverage to 2 and hence prevents the formation of a quorum, whereas a compromise of any two nodes in the more robust graph in Figure 1b does not affect gossip reception by the remaining honest nodes. Dashed lines highlight connected components. evaluating the robustness of gossip protocols under realistic adversarial strategies. While the examples in Figure 1 are relatively straightforward, the challenge is that consensus security is well established in theoretical models, whereas gossip effectiveness is typically measured through empirical metrics such as coverage and delay. Bridging the two requires a unifying model that captures the security-relevant dynamics of churn and message dissemination, together with metrics that translate gossip behavior into security properties under a realistic adversary. Our 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? We address these questions as follows. First, we introduce a novel framework that captures both the robustness and the efficiency of existing gossip protocols once peer discovery has completed and the overlay topology has formed (Section 2). 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. Such adversaries adapt their choice of corrupted nodes based on readily available information about node placement within the network. Leveraging our framework, we analyze the robustness of random graph topologies and show, both analytically and empirically, 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 Byzantine Fault Tolerance (BFT) protocols (Section 3). We then use this observation as a guiding example and extend our analysis to modern gossip protocols deployed in real-world committee-based blockchains, including Polkadots grid-based gossip [14], Ethereums GossipSub [12], and Solanas chunk- and tree-based protocols [15]. More specifically, we considerably extend the popular blockchain

2. System & Network Model In this section, we introduce our model for capturing the process of data dissemination in (potentially dynamic) communication networks. Our 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. 1 Coincidentally, with an estimated network size of n = 5, 000 in Bitcoin, this closely matches the Erdős-Rényi threshold [13], where connectivity is almost guaranteed if the average degree is ≈ ln (n).

2.1. Communication Networks We model a communication network 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 Erdős–Rényi graphs G(n, p). These are randomly connected graphs with n nodes, where each edge between any two nodes exists independently with probability p, resulting in an average node degree of d = p · (n − 1). The peers Peers(N ) of a node N are all neighboring nodes, i.e., nodes directly connected to N by an edge. To evaluate a gossip protocol, it is important to check if a gossip spawned at some node N eventually reaches another node N ′ . A pair of two distinct nodes (N, N ′ ) is called connected if a path exists from N to N ′ . Consequently, a graph G is connected if any pair of distinct nodes is connected. The largest connected component of a graph G = (N , E) is the largest subgraph G′ = (N ′ , E ′ ) with N ′ ⊆ N and E ′ ⊆ E such that all pairs of nodes in N ′ are connected. In practice, graph topology may change over time due to churn. To keep track of these changes, we index the graphs with a discrete-time counter t: Gt = (Nt , Et ).2 We capture churn via the churn rate c, which represents the fraction of nodes that may leave and rejoin the network, with each node’s online and offline durations drawn from a specified distribution.

2.2. Gossip Protocol The goal of a gossip protocol is to disseminate data across the network as thoroughly and rapidly as possible. To evaluate the effectiveness of such a protocol, we must track how quickly information spreads among the nodes. To this end, we model each node as being stateful. We denote by S the set of all possible states of nodes and by State(N, t) ∈ S the state of node N at point in time t. Moreover, we denote by Nt,s the set of all benign nodes in Nt that are in state s at time t. S contains two special states: sinit and sfinal . The initial state sinit characterizes nodes that are completely unaware of the data being disseminated. In contrast, a node is in the final state sfinal if it knows the full content of that data. When the gossip protocol starts at time tstart , typically N ∗ marks the origin of the gossip to be disseminated, while all other nodes are not informed (yet). Formally, this means that Ntstart ,sfinal = {N ∗ } and Ntstart ,sinit = Ntstart \ {N ∗ }. Then, at subsequent epochs t > tstart , the following two actions take place at each node N . First, N updates its state from State(N, t − 1) to State(N, t), based on the messages it received in the previous epoch t − 1. Then, it sends some messages to its peers Peers(N ), depending on its state State(N, t). Here, we assume that each node N knows which of its peers are in a final state already. If this holds for 2 When the time t is clear from the context or the graph does not change for the period considered, we may omit the parameter t.

all peers, N will stop sending any messages in this protocol run, but still may receive messages from other nodes if N is not in a final state yet. This allows us to capture different transmission strategies, such as direct push. We say that the run of the protocol π is completed at point in time t if no further changes happen, that is State(N, t − 1) = State(N, t) for every node N . We denote the first point in time at which the protocol is completed by tend . The gossip protocol is successful if, upon completion, all benign nodes are informed, that is Ntend ,sfinal = Ntend . Intuitively, a protocol is more effective the more nodes are informed in a shorter time. To quantitatively evaluate this, we capture the fraction of benign nodes being informed after time t, Quality(t), and define it as: Quality(t) =

|Nt,sfinal | . |Nt |

(1)

3. Security Model & Analysis In this section, we lay down the foundation for evaluating the security of gossip protocols by specifying the attacker model (Section 3.1) and the notion of security (Section 3.2). In particular, we define the notion of robustness as a means of evaluating the effectiveness and impact of various adversarial strategies.

3.1. Attacker Model We start by modeling possible adversarial (i) actions and (ii) knowledge. Adversarial Actions. We adopt the common model used in distributed systems [17]–[19], in which the attacker can control a fraction β of the nodes to affect the protocol’s execution. That is, for any point in time t, the set of nodes Nt is the disjoint union of the corrupted nodes Ntcor and honest nodes Nthon. . Node corruption is modeled through the attackers invocation of the method Corrupt. Specifically, given a graph Gt = (Nt , Et ), calling Corrupt(N ∗ ) for some node set N ∗ results in all nodes in Ntcor := Nt ∩ N ∗ being corrupted and placed under the attackers control, while all remaining nodes remain honest. Notice that corrupting nodes can be subject to some restrictions: Bound: The fraction of corrupted nodes is } bounded by { cor |N | parameter β ∈ [0, 1] with maxt |Nt t | ≤ β . An attacker is naturally most effective when it corrupts as many nodes as its budget allows. Unless stated otherwise, we therefore assume that the attacker exhausts its budget and corrupts a fraction β of nodes. Static vs. mobile: A static (or monotonic) adversary fixes its set of corrupted nodes at the outset, whereas a mobile adversary may adaptively change this set at any time, subject to all other constraints. As churn reshapes the topology, nodes corrupted early lose relevance, so static corruption converges to random corruption.

Unless stated otherwise, all references to adaptive adversaries therefore denote the more realistic mobile adversary. Delay: Corrupting nodes may not happen instantaneously but can be delayed by some value δcor . That is, if an attacker issues Corrupt(N ∗ ) at epoch t, the set of corrupted nodes remains unchanged until epoch t+δcor so cor cor that Nt+δ = Nt+δcor ∩N ∗ . Note that Nt+δ ⊊ N∗ cor cor ∗ can happen if some of the nodes in N have been removed due to churn. Corrupted nodes are fully controlled by the attacker and may deviate arbitrarily from the prescribed gossip protocol, e.g., by selectively withholding messages from peers or leaving the network altogether. Conforming to the BFT model, our model also accounts for nodes that unexpectedly crash during consensus realization. We say that a node is crashed if it remains offline throughout an entire consensus round. The prevalence of such failures is governed by a churn rate c and a distribution over nodes’ offline and online durations, both of which we instantiate in Section 4 using empirically derived values from real-world deployments. For instance, β = 0 and c > 0 capture a graph free of active corruption yet still subject to churn and crashes. In this work, we focus on two specific adversarial behaviors upon receiving a rumor message: Eclipsing: The node ignores all received messages and does not forward them. This effectively eclipses its neighbors from ongoing message propagation. Passive non-responsive: The node advertises receipt of a message but withholds its content [9], increasing latency. This is especially effective in protocols that use timeouts to save bandwidth, as a well-connected corrupted node that is among the first to advertise can significantly delay delivery to its neighbors. Adversarial Knowledge. We assume an attacker who knows the deployed gossip protocol, the churn parameters, and the full node set N , and who may additionally hold (partial) knowledge of the graph topology, as described below. Our analysis deliberately targets the robustness of the gossip layer itself, i.e., its behavior once peers have been discovered and the overlay topology has been established. Namely, peer discovery determines how a topology comes about. Gossip robustness determines what that topology can withstand. We treat these as separate concerns for three reasons. First, the two layers compose rather than interact: whatever discovery mechanism is in use, its output is a topology, which our analysis takes as input. Second, this makes our results agnostic to the peer discovery protocol in use: they hold for any protocol that yields a given topology, rather than being tied to a particular design. Third, attacks on discovery itself, such as eclipse attempts that bias neighbor selection, are therefore not excluded but subsumed: their effect is captured by the adversarial topology they produce, which our model can evaluate directly. Minimum knowledge refers to the attacker knowing only the connections of the corrupted nodes, while full knowledge means that the attacker knows the topology of the full graph.

The third, intermediate category is referred to as partial knowledge. This setting is more realistic than the other two: we assume that the adversary can directly communicate with a subset of nodes—for example, those that can be inferred through active probing, such as address advertisement or transaction isolation [20]–[23]—but does not necessarily know their peers or their connections. In Section 4.1, we justify the assumed attacker knowledge for each of the concrete blockchain systems we consider.

3.2. Robustness In Section 2.2, we introduced Quality(t) as a quantitative measure of a gossip protocol’s effectiveness. Intuitively, robustness captures the protocol’s ability to maintain Quality(t) under attacks. However, two issues arise. First, these values fluctuate due to protocol randomness and effects such as churn; hence, Quality(t) refers to expected values. Second, comparing all individual values is often uninformative, as transient performance is less relevant. Instead, we focus on key metrics, motivated by the principle that a gossip protocol should inform as many nodes as possible in the shortest time, captured by the following two notions: Coverage: Ω = maxt≥tstart {Quality(t)} denotes the highest possible fraction of benign nodes that eventually will be informed. Ideally, Ω should be equal to or at least close to 1. 3 Delay: ∆ = min{δ ≥ 0|Quality(tstart + δ) = Ω} is the minimum time it takes until the maximum coverage is achieved. Note that these two metrics are both security-critical. Lower coverage means some nodes remain uninformed, potentially breaking consensus (see also the examples given in Section 1). Similarly, increased delay is known to undermine security, e.g., see [10], [19]. An attacker targeting a gossip protocol would therefore aim to disrupt its operation by reducing Ω and/or increasing ∆. In other words, we say that an adversary A successfully disrupted the coverage if Ω′ < Ω. On the other hand, the protocol provides robust coverage if Ω − Ω′ is not too large. Similarly, an attack against the delay is successful if ∆′ > ∆, and the protocol provides robust delay if ∆′ − ∆ is small.

3.3. Analysis: Random Graphs with BFT We now leverage our model to analyze strategies for preventing honest nodes from receiving messages, thereby circumventing quorum formation. We consider a system built from a straightforward combination of gossip-based dissemination and classic BFT consensus protocols4 . Random Corruption. A straightforward strategy consists of randomly corrupting ncor nodes, with the additional effect 3 Note that while a static adversary limits coverage to at most Ω ≤ 1 − β , the coverage can reach up to Ω ≥ 1 − β against an adaptive adversary that can reassign its corrupted nodes during propagation. 4 An analogous analysis can be derived for Nakamoto-style protocols with minimum NS quorum size = 21 (n + 1) instead.

100

60

80

80

40 20

≈ 66.6

60 40 20

0 0.0

≈ 0.33

0.2

0.4 0.6 0.8 Malicious node share β

(a) Varying centrality metrics, n = 500 and d = ln(n) = ln(500)

n = 50 n = 100 n = 200 n = 500 n = 800 n = 1000

0 0.0

1.0

Coverage Ω (%)

≈ 66.6

Coverage Ω (%)

80 Coverage Ω (%)

100

degree betweenness eigenvector closeness random

60

≈ 66.6

40 β = 0.10 β = 0.20 β = 0.30 β = 0.33

20 ln(n) n

0

≈ 0.33

0.1 0.2 0.3 Malicious node share β

0.4

2

) (b) Varying n, d ≈ ln(n) (p = ln(n) n

4

6

8 10 Average degree d

12

14

(c) Fixed n = 500 and varying d

Corrupted node fraction β

Figure 2: Coverage Ω under node corruption in ErdősRényi graphs without churn. The black diagonal in Figures 2a and 2b denotes the upper bound of the coverage given the malicious node share, i.e., 1 − β .

1 3

0.33 0.32 0.31

Classic BFT bound Random corruption

0.30 5

10

15 20 Degree d

25

30

Figure 3: β in the peer-corruption strategy (cf. Eq. (4)) as a function of the (minimum) node degree d ∈ [3, 30] in a network of size n = 1,000. of isolating further nodes, beyond those directly compromised, in an untargeted manner. By isolated, we refer to a non-corrupted node that shares no connections with other honest nodes [9], [24]. Recall that, in classic BFT protocols, forming a quorum is not possible when: n − (ncor + niso + ncr ) ⇔

1 1 (1 − ) 3 n

2n + 1 3 niso ncr < β+ + , n n <

(2)

where ncor denotes the number of actively corrupted (noncrashed) nodes, ncr the number of crashed nodes, niso the number of nodes additionally isolated by the adversary (but that did not otherwise naturally crash), and β the fraction of corrupted nodes. Eq. (2) reduces to the classic BFT condition when niso = 0. Assuming a uniform d = |Peers(N )| , ∀N ∈ N , the probability for any non-corrupted node N of being isolated equals the probability that all of its d peers are corrupted, which is approximately β d . Hence, the expected fraction of d isolated nodes is niso n = β · (1 − β). Plugging this into Eq. (2) shows that the expected coverage would not be enough for quorum formation when:

( 1−

1 n

) < β + β d · (1 − β) +

ncr . n

(3)

We can also see that an increase of d (towards a fully connected graph) reduces the risk of nodes getting isolated. Greedy Strategies. We note that adversaries with partial or full knowledge of the graph topology can mount even more effective strategies to corrupt nodes for preventing messages from being received by a larger set of honest nodes, as illustrated in the example in Fig. 1a. For instance, one could randomly select nodes to be isolated and then compromise all their peers. In this case, it holds that niso ≥ ncor (peer sets of distinct nodes may d overlap). Even if we assume to the disadvantage of the attacker that ncr = 0, Eq. (2) provides the following sufficient criterion that this strategy, dubbed peer-corruption-strategy, prevents quorum formation in classical BFT protocols: ( ) d 1 β> · 1− . (4) 3d + 1 n d Since 3d+1 < 31 for any d ≥ 1, we can see that corrupting less than 1/3·(1−1/n) of the nodes can already be sufficient to prevent quorum formation in this context (see Figure 3). More generally, a strategy could be to compromise nodes based on their placement/centrality within the network, for instance, according to their degree, eigenvector, betweenness, or closeness centrality (see [25] and Section A for details). Importantly, estimating node centrality does not require complete topological knowledge. Public nodes, for example, naturally serve as entry points to the network and are therefore expected to have higher centrality than nonpublic nodes. We demonstrate how feasible such topology inference is in practice for Ethereum, Solana, and Polkadot in Section 4.1. In Figure 2, we analyze the coverage Ω under the greedy strategy when an adversary iteratively corrupts a fraction β of nodes as follows: at each step, the adversary removes the currently most central node under the selected metric, updates the graph accordingly, and recomputes centrality

scores on the remaining network—matching the procedure used in Section 4. To this end, we generate 20 ErdősRényi (ER) graphs with sizes n ∈ [50, 1000] using the NetworkX [26] Python library and numerically compute the average Ω for each parameter configuration. Unless otherwise specified, we consider a dynamic connectivity parameter5 p = ln(n) (d = ln(n) − ln(n) ≈ ln(n)). As our primary n n interest here is the relationship between the number of corrupted nodes ncor and the number of isolated nodes niso , we assume ncr = 0 in our analysis in Figure 2. Section 4 extends these results to more realistic settings, using empirically grounded churn rates under which a subset of nodes may appear offline or crashed. Figure 2a illustrates the impact of the chosen centrality metric for a fixed network size of n = 500. Note that given nβ corrupted nodes, the ideal coverage is (1 − β) (represented in Figure 2a by the straight, solid line), achieved when the honest subgraph remains fully connected. We clearly see that greedy strategies that leverage knowledge of node placement consistently achieve lower coverage than the random corruption strategy. Among the evaluated metrics, betweenness centrality yields slightly lower coverage than degree centrality or closeness centrality, but its computation is expensive and requires detailed knowledge of pairwise network latencies. We therefore base most of our analysis (cf. Section 4.2) on degree centrality, which relies only on local degree information that is more realistically available to an adversary. Figure 2b quantifies the average Ω as a function of the fraction β for varying network sizes, using the same connectivity as in Figure 2a and assuming a degree centrality metric. Given a fixed connectivity parameter p = ln(n)/n, smaller network sizes in ER graphs are associated with weaker subgraph connectivity, e.g., d ≈ ln(n) = 3.9 for n = 50 compared to d ≈ 6.9 for n = 1000. This results in a faster decline of Ω below the classical BFT quorum threshold (cf. Figure 2b). Finally, Figure 2c evaluates Ω for networks with a fixed size of n = 500 and varying average degrees d ∈ [2, 15]. To achieve a target average degree d d, we set the edge probability to p = n−1 . Our results indicate that sufficiently dense networks—specifically those with an average degree of d ≥ 12—are highly resilient in ER graphs with n = 500 nodes. On the other hand, in an ER graph with average degree d = 6, an adversary that corrupts β = 0.3 of nodes can reduce the coverage to 62.8%, effectively preventing quorum formation in this context.

4. Robustness Evaluation In this section, we extend our analysis and empirically evaluate coverage Ω and delay ∆ in real-world deployments across different gossip protocols, including random graphs, Polkadots grid topology, Ethereums Gossipsub protocol, and Solanas dynamic trees protocol, with varying capabilities as 5 Erdős and Rényi [13] have shown that p = an ER graph to be almost surely connected.

ln(n) is a threshold for n

defined in Section 2 and real-world deployment artifacts, such as churn.

4.1. Methodology & Setup We conduct our empirical measurements using SimBlock [10], [16], an event-based blockchain network simulator implemented in Java. SimBlock models block propagation with configurable network topologies, inter-node latencies, and dissemination protocols. Building on this open-source framework, we implement further extensions to model four case studies inspired by gossip protocols used in Nakamoto-style blockchains (Bitcoin and Altcoins), Polkadot, Ethereum 2.0, and Solana: random graphs, grid topologies, GossipSub, and dynamic trees. These extensions add richer transmission models, diverse topologies, and more powerful adversaries employing multiple corruption strategies. Our simulator takes as input the network topology that emerges once peer discovery completes and evaluates its resilience to attack. Because the simulator depends only on this final topology, our results extend to any peer discovery mechanism that produces it. Moreover, since our focus is solely on message dissemination, we abstract away block mining and instead generate messages at fixed intervals from randomly selected honest nodes. Note that evaluating our attacks on live blockchain networks is ruled out by the ethical implications of affecting real users. Moreover, such an evaluation could not provide the evidence behind Figures 6–11, for two reasons. First, we do not control the messages sent in live networks, so comprehensive end-to-end delay measurements are infeasible. Second, parameters such as network size and churn rate cannot be varied in a controlled way on live blockchains, which makes it impossible to evaluate robustness across them. Simulator Validation We build on SimBlock [16], a widely adopted blockchain simulator that is calibrated with realworld parameters and has been validated against real-world deployments [10], [16]. Our implementations faithfully follow the specifications of the respective systems, including message sizes and protocol parameters. This grounds our results in realistic conditions, in line with prior simulationbased studies [9], [10], [17], [18], [27]. We validate our simulator extensions in two ways. First, we show that our empirical results agree with the analytical results of Section 3.3. Second, we compare the simulator against the real networks themselves: for each considered blockchain, we check the simulated message-arrival latency against the latency distribution observed by unmodified nodes running on the live network. Our results (see Appendix B) confirm that the simulator faithfully reproduces the real-world behavior of the considered blockchains. Communication & Messages. Communication is simulated via events stored in a global priority queue ordered by execution time. The simulator processes the earliest event, advances simulated time, and schedules follow-up events

as needed. For example, processing a message-reception event schedules forwarding events to neighboring nodes with delays determined by the propagation model. We record the time when a message arrives on each node and use that to derive Quality(t), coverage Ω, and delay ∆. Messages are issued every 100 s for a total of 1,000 messages, resulting in roughly one day of simulated time. Unless stated otherwise, each data point is averaged over 10 independent runs. Nodes’ Locations & Latencies. Recall that our network setup follows the empirically measured characteristics of Bitcoin, as calibrated in prior work [9], [10], [17], [18], [27]. Specifically, we adopt their distribution of nodes across geographic regions, their inter- and intra-region latencies, and their bandwidth values. Messages are transmitted sequentially, with transmission time equal to the message size divided by the bandwidth plus the link latency. Number of Nodes & Churn. Note that the number of reachable full nodes in Bitcoin is approximately 5000 [9], 512 for Ethereum (active committee)6 , 600 for Polkadot7 , and 1,200 for Solana [28]. Motivated by this, 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.8 These nodes repeatedly join and leave the network. Their online durations are drawn from a loglogistic distribution (αdistr. = 11.0, βdistr. = 0.771), while their offline durations are drawn from a Weibull distribution (λ = 0.64, k = 0.183), consistent with empirical Bitcoin measurements [29]. After each period expires, a node toggles its online-offline state. Note that in our experiments, we ensured that quorum formation remains possible even when nodes crash (due to churn) and the attacker uses its corruption budget. Notably, even at large churn rates c ≥ 30%, the fraction of simultaneously online benign nodes remains sufficiently high to form a BFT/NS quorum. For instance, in the benign setting (β = 0), a churn rate of c = 50% leaves an average of approximately 83.4% of nodes that are both benign and online. This is because our simulator reflects real-world churn patterns, where online periods are significantly longer than offline periods, with medians of approximately 20.41 hours and 7.37 hours, respectively (a ratio of 2.77×). Given the same churn rate, even when β increases to β = 0.2, we still have a majority of 66.8% of all nodes being both benign and online, sufficient to form a functional quorum in classical BFT protocols. Topologies. We consider undirected network graphs9 , and evaluate three topology classes as follows: • Random Graphs (unstructured topology): As explained in Section 2.1, these are modeled by ErdősRényi graphs 6 See the Sync Aggregation field in block https://beaconcha.in/block/ 22431860. 7 https://polkadot.subscan.io/validator 8 In Bitcoin, up to 97.6% of the nodes are affected by churn [29]. 9 Although gossip protocols distinguish inbound and outbound links, messages are forwarded across all established connections, making propagation effectively undirected.

Network Settings Message size 80KB (2KB) Average degree d 8,15,20 Random graph, Grid, Topology Dynamic tree 50 to 5000 Network size n Churn rate c 5% - 50% churn nodes Message rate 0.01 (1, 10, 120) msg/s

Adversary Settings Node corruption 0.1, 0.2, 0.3, budget β 0.32, 0.33, 0.5 Adversary Static, adaptiveness Adaptive None, Corruption Random, strategy Greedy Degree cent., Greedy corruption Closeness cent., centrality metrics Eigenvalue cent., Betweenness cent. 10ms to 10s Corruption delay

TABLE 1: Summary of parameters evaluated in our setup.

G(n, p). Dynamic Trees (semi-structured topology): Inspired by Solanas Turbine [15], where messages are encoded into chunks for more efficient propagation (Section 4.5), we model a dynamic tree that is reshuffled for each message chunk. Message chunks traverse different tree paths, and the full message is reconstructed once all parts arrive. • Grid Matrix (fully structured topology): We also model the grid topology used in Polkadot [14], where nodes connect to all others in the same row and column. This topology exhibits uniform degree and minimal clustering, similar to random graphs. •

Note that topologies handle churn differently: random graphs resample peers for offline nodes and assign fresh connections upon return; structured topologies (grids and trees) preserve their logical structure by disabling and reactivating affected links; and GossipSub bootstraps randomly then evolves via peer scoring (Section 4.4). Adversaries. We implement various adversarial strategies by scheduling attack events that compromise nodes either statically or adaptively. The adversary can select targets based on assumed topology knowledge and multiple strategies, such as random selection or greedy selection using node centrality metrics. For simplicity, in our evaluation, we assume that the complete set of nodes is known to both honest participants and the adversary. We vary the corruption bound over β ∈ [0.1, 0.5) (cf. Table 1)10 , and consider both static adversaries, which initially fix corruption targets, and adaptive adversaries, which adjust targets over time, subject to a nonzero corruption delay. Overall, our evaluation spans the corruption strategies introduced in Section 3.3 and the parameter configurations summarized in Table 1. Practical Considerations. The adversarial strategies that we consider assume two capabilities: (i) the ability to compromise β of the nodes, and (ii) partial or complete knowledge of the network topology. The former is standard in consensus protocol research [13], [30] and rests on the attacker’s ability to compromise nodes by exploiting zero-days or other vulnerabilities. The latter is equally justified for several reasons: First, in committee-based blockchains like 10 To ease presentation, β = 0.5 denotes the case where the adversary compromises as many nodes as the NS-bound permits.

(a) Snapshot of the Solana (b) Topology of the largest testtopology in slot 423812556 net of Ethereum, Goerli, leveraging and for chunk 1. Nodes with the transaction isolation approach by less stake are smaller. work [20]. Nodes with a higher degree are bigger and brighter.

Figure 5: Snapshots of the graph topologies in Solana and Ethereum testnet. Solana and Polkadot11 , validators must know one another in order to communicate, and the protocols explicitly define these communication relationships. In both systems, validator addresses are publicly discoverable by construction. Solana’s gossip layer publishes contact information tied to node identity, while Polkadot’s authority discovery protocol has validators publish resolvable address records for intervalidator communication. Consequently, any entity can infer the global topology simply by accessing the ledger state. For instance, Figure 5a illustrates the resulting tree structure captured on Solana in Slot 423812556, for data chunk 1. One can query the VoteAccounts, LeaderSchedule, and ClusterNodes ledger data, which gives information on the validator set, the leader of each slot, and the validator stake. The tree for each data chunk index j in slot i is fixed and predictable one epoch (about 2 days) in advance and can then be reconstructed from a shuffled validator set using the seed (i, j, leaderi ), the validator stakes as weights, and the ChaCha20-Poly1305 [31] RNG. Ethereum differs from these committee-based systems in that validator identifiers are deliberately decoupled from node addresses at the protocol level. Nevertheless, discv5, the UDP-based peer-to-peer discovery protocol used by Ethereum, makes the set of beacon nodes readily enumerable. Alternatively, the topology can be inferred without direct participation through probing techniques such as address advertisement or transaction isolation [20]–[23], [32]. Recent measurement studies demonstrate that an unprivileged adversary can recover the remaining validator-to-node mapping in practice. For instance, Figure 5b depicts the topology of Goerli, Ethereum’s largest testnet12 . With 1355 nodes, Goerli exhibits a pronounced skew in node degree 11 In Polkadot, given any session index, one can retrieve the SessionRandomness and the corresponding ValidatorSet from the ledger state; the grid topology can then be reconstructed from the validator set using the SessionRandomness as seed and the Fisher-Yates shuffle algorithm coupled with ChaCha20 RNG. 12 For ethical reasons, we opt to only show the Ethereum Testnet topology, as reconstructed via transaction isolation by [20].

distribution. Note that Figure 5b retains only nodes with degree d ≥ 8, yet many already exceed 100 connections under the default setting of d = 8, with some super-nodes reaching upwards of 700 connections. As we demonstrate in Section 4.4, a greedy adversary that compromises these nodes would considerably reduce coverage in Ethereum. Moreover, most validators are nowadays cloud-hosted, allowing cloud providers to easily infer the topology. Bitcoin differs from committee-based settings in that a portion of its relay population operates from behind NAT and is therefore not directly reachable by an adversary. This limitation does not materially affect our analysis, however, because the nodes most beneficial to target are those holding mining power, which are necessarily reachable and publicly identifiable to participate effectively in mining. Concretely, a miner that cannot be reached can neither obtain work nor propagate its blocks competitively, and mining pools openly advertise their infrastructure. Non-mining nodes, by contrast, hold no validation power and are therefore less attractive targets. Moreover, since such nodes relay blocks and transactions over their own outbound connections, they become visible to an adversary present in the network even when they cannot be contacted directly [20], [21], [23]. Their residual effect is therefore confined to the propagation delay they add along paths between miners, which prior work [18] quantifies as negligible for Bitcoin. Finally, note that our adversarial strategy does not require validators to be publicly identifiable or deanonymized. It only requires knowledge of the topology and node IP addresses. Even when the latter are not publicly available, an adversary that compromises a validator can directly learn the IP addresses of its neighbors, thereby obtaining partial topology information and, through repeated compromises or observations, expanding its view of the network.

4.2. Robustness of Random Graphs We evaluate the parameter combinations listed in Table 1 assuming a direct push transmission model. Networks are instantiated as ErdősRényi graphs G(n, p) with an average d degree d ∈ {8, 15, 20}, where p = n−1 (cf. Section 2.1). Simulator Validation. We validate the simulator by comparing empirical results with the analytical bounds from Section 3.3. Greedy corruption strategies significantly outperform random corruption (Figures 2a, 6a). Targeting high-degree or high-betweenness nodes is most effective, followed by eigenvector and closeness-based strategies. Degree-based corruption consistently yields lower coverage than betweenness-based attacks, while being computationally cheaper; we therefore focus on degree-based adversaries. Higher average degree improves robustness, leading to higher coverage and shorter delays (Figure 2c, Figure 14 in Appendix D). For n = 5,000 and β = 0.5, coverage increases from 36% to 49.98% and delay drops from 6.3 s to 4.8 s as d grows from 8 to 20. Overall, the simulator faithfully reproduces the effects described in Section 3.3. Impact of Adversarial Strategy. We now compare random corruption (emulating minimum knowledge about the graph

1

67

4

BFT bound

3.5 0.8

Quality(t)

0.6

0.4 none random degree betweenness closeness eigenvector

0.2

0

0

0.5

1

1.5

2

2.5

3

3 65 64

3.5

(a) Impact of adversarial strategy (n = 1000)

4

2.5 2 1.5

63

Propagation Time t (s)

Delay (s)

Coverage Ω (%)

66 BFT bound

none random degree betweenness closeness eigenvector

62 20

random degree betweenness

closeness eigenvector

100

1000

1 5000

Network Size (n)

(b) Impact of adversarial strategy on the coverage

0.5 20

100

1000

5000

Network Size (n)

(c) Impact of adversarial strategy on the delay

Figure 6: ER graphs: Impact of different adversarial strategies with β = 0.33 when d = 8. topology) and greedy adversarial strategies (emulating partial/full knowledge). We compare the impact of the adversarial corruption bound β on the coverage required by the minimum BFT quorum size ( 13 (2n + 1)) or the Nakamotostyle quorum size (NS quorum size) ( 12 (n + 1)). As shown in Figure 6, degree- and betweenness-based attacks most strongly degrade coverage and delay. For n = 1,000 and β = 0.33, degree-based corruption doubles delay (from 1.49 s to 3.12 s) and reduces coverage to 64.17%. By varying β , we observe that for a fixed node degree of d = 8, coverage is largely independent of network size (Figure 6b), but decreases nonlinearly as β increases (Figure 7a and Figure 13a in Appendix D), consistent with known partitioning behavior in ER graphs. For n = 1,000 and d = 8, coverage drops from 68.15% at β = 0.3, which is sufficient for the BFT quorum size, to 65.51% at β = 0.32, falling below the required threshold. At β = 0.5, coverage further declines to only 35.61%, well below what is necessary for safe consensus. We also note that delays grow logarithmically with network size and increase sharply with β (Figure 13b in Appendix D). For β = 0.5, delay rises from 1.08 s to 2.88 s in a 50-node network and from 1.88 s to 6.03 s in a 5,000-node network, indicating that larger networks suffer disproportionately higher latency under attack. Impact of Node Degree. Higher node degrees improve robustness (Figure 7b and Figure 14 in Appendix D). For β = 0.32, networks with d ∈ {15, 20} significantly improve the robustness compared to d = 8. This trend continues under stronger attacks (β = 0.5), where degree becomes decisive: in a 5,000-node network, coverage rises from 36.04% to 49.98% and delay falls from 6.27 s to 4.8 s as d increases from 8 to 20. However, even for adversaries with β = 0.5, d = 15, 20 still achieve comparable performance. Thus, beyond a threshold of d ≈ 15, additional edges yield little robustness benefit. Impact of Adversarial Capability. We evaluate the impact of adaptive adversaries that corrupt nodes predicted to receive messages, after a delay δcor from 10 ms to 10 s (Figure 7c and Figure 15 in Appendix D) and we observe that adaptive adversaries consistently increase delay

and achieve varying coverage as δcor grows. With a very short corruption delay δcor = 10 ms, adaptive attacks fully suppress propagation in all cases, confirming known impossibility results. As δcor increases, coverage improves and may exceed the maximum achievable coverage by a static adversary; e.g., with β = 0.3 and δcor = 100 ms in a 1,000-node network, coverage approaches 92%. This occurs because an adversary that repeatedly releases and corrupts different nodes over time can cause the message to traverse more nodes than under a static strategy. However, as δcor increases (≥ 5 s), the coverage decreases and converges to the static case. Therefore, under a smaller adversarial bound β , an adaptive adversary must corrupt nodes very rapidly to reduce coverage below the BFT quorum size. In our simulation settings, this requires corruption delays of approximately 20 ms for β = 0.2 and 40 ms for β = 0.3. Our results further confirm that the mobile adversary is a more appropriate model for our analysis. As churn reshapes the topology, nodes corrupted early gradually lose their strategic value, so monotonic corruption converges toward random corruption. Figure 7c captures this transition by varying the corruption delay δcor : long delays approximate a monotonic adversary. Coverage plateaus once δcor ≥ 1 s, showing that a monotonic adversary is markedly less effective than its mobile counterpart. Impact of Churn. We model network churn affecting up to 5%–50% of nodes (Figure 8a) and used empirically observed patterns from [29] to simulate the nodes’ online and offline behavior. Since message propagation completes within approximately 5 s—significantly shorter than the typical duration for being offline—nodes that go offline miss dissemination and must rely on the consensus protocol for recovery. Even in the absence of an adversary, churn observed in 50% of nodes reduces coverage to approximately 85%. When β = 0.2 and churn reaches c = 40%, coverage drops further to approximately 65%, falling well below the BFT quorum size. This occurs despite the fact that 75% of benign nodes remain online under these conditions, a fraction that would be sufficient to form a BFT quorum if all such nodes were mutually reachable (cf. Table 4 in Appendix D). More generally, the maximum β that allows benign

1

0.8

β=0.32, d=8 β=0.32, d=15 β=0.32, d=20

0.8

Quality (t)

Quality (t)

0.6 NS bound 0.4

0

β=0.3 β=0.32 β=0.33 β=0.5 0

1

2

3

4

80 BFT bound

BFT bound

0.2

100

β=0.5, d=8 β=0.5, d=15 β=0.5, d=20

Coverage Ω (%)

1

0.6 NS bound 0.4

6

0

0

1

Propagation Time t (s)

(a) Impact of β for node degree d = 8.

BFT bound 60 NS bound 40

20

0.2

5

80%

2

3

Propagation Time t (s)

(b) Impact of d and β .

4

5

0 0.01

β=0.2 β=0.3 β=0.5 0.1

1

10

Corruption Delay (s)

(c) Impact of δcor for node degree d = 8.

Figure 7: ER graphs: Impact of β , d, and δcor on quality for n = 1,000 nodes. online nodes to satisfy a given quorum threshold decreases as churn increases. For example, satisfying the minimum BFT quorum size requires β ≤ 0.2 at c = 30% churn (with ≈ 72% of nodes being benign and online), whereas satisfying the minimum NS quorum size requires β ≤ 0.33 at c = 50% churn (with ≈ 58% of nodes being benign and online). In these dynamic settings, average node degree has little effect on the outcome (cf. Figure 8a).

4.3. Robustness of Grid Topologies (Polkadot) Polkadot uses a nominated Proof-of-Stake protocol in which a fixed validator set is elected at the start of each 24hour era based on stake drawn from the finalized ledger state. To disseminate messages, validators are organized into a grid topology: √ their IDs √ are randomly permuted and arranged into a ⌊ n⌋ × ⌈n/⌊ n⌋⌉ matrix [33], where each validator connects to all others √ in its row and column, resulting in a degree of ≈ 2 n. Messages are forwarded to row and column neighbors, with eight randomly selected nodes additionally included to improve robustness. Unpredictability stems only from node churn and per-message random neighbors, since the validator set and topology are globally known and fixed within each era, and all validators have nearly identical degrees. We therefore model a static adversary with global knowledge that corrupts nodes uniformly at random. Here, messages are disseminated via direct neighbor pushes, supplemented by eight additional random peers per message.13 Impact of Adversarial Bounds β . Figures 10a10c show propagation coverage and delay for varying network sizes and adversarial bounds in static networks. Coverage is always at the respective bound (1 − β ), indicating that the remaining honest nodes stay connected despite corruption. This robustness stems from the grids √ high connectivity, with each node maintaining roughly 2 n links. The delay increases with the adversarial bound β , as corrupted nodes effectively remove edges and lengthen 13 Figure 17 in Appendix D varies the number of randomly selected nodes that each node contacts in addition to its row and column neighbors, and reports the resulting coverage and delay. The trends observed in Figure 10 hold across all values of this parameter, showing that it does not affect our findings.

paths, mirroring trends in random graphs (Figure 13b in Appendix D). For example, in a 500-node network (comparable to Polkadots number of validators) delay increases from about 1.55 s without attacks to 2.28 s with corruption β = 0.33. We also observe that delay grows logarithmically with network size, contradicting the claim that any message traverses at most two hops [33]. While any two nodes are indeed within two hops, full dissemination still requires sequential transmissions over individual connections, with the overall delay constrained by node bandwidth. High connectivity also increases message duplication and marginally raises delays. Compared to random graphs (d = 15, β = 0.33), grid topologies show slightly higher delays without adversaries but become more efficient under attack. For example, at n = 50, delays are 1.08 s vs. 0.96 s without corruption, but 1.63 s vs. 1.79 s at 33% corruption; at n = 2,000, the corresponding figures are 2 s vs. 1.68 s and 2.69 s vs. 2.77 s. Impact of Churn. Figure 8b shows that churn reduces coverage, consistent with results for random graphs. Due to its higher degree and additional random propagation (e.g., d = 64 for n = 1,000 versus d = 20 in ER graphs), the grid achieves slightly higher coverage, especially in the presence of higher dynamics: from about 0.45% improvement for β = 0.2 and a churn rate of c = 5%, and up to 4.5% for β = 0.3 and c = 50% churn rate. Overall, results from both static and dynamic networks show that the grid topology’s high connectivity provides strong resilience against adversarial behavior. However, at high churn rates, it fails to guarantee the required coverage against strong adversaries (β ∈ [0.25, 0.33]).

4.4. Robustness of GossipSub Ethereum 2.0, Filecoin, and Algorand all use GossipSub [12], a publish/subscribe protocol in which nodes subscribe to topics and receive only the messages published to them. We abstract away topics by considering a single topic to which all nodes subscribe. GossipSub maintains two types of connections: full-message links, over which messages are eagerly pushed to form the mesh network, and metadata-only links, over which message identifiers are periodically advertised in batches and full messages may be

100

100

100

90

90

90

80

80

80

100 90

60 NS bound

50

β=0 β=0.2, d=8 β=0.2, d=20

40 30

0

5

10

30

BFT bound 60 50 NS bound

70 BFT bound 60 NS bound

50

70 BFT bound 60 50 NS bound 40 30 20

β=0.3, d=8 β=0.3, d=20 20

70

Coverage Ω (%)

70 BFT bound

Coverage Ω (%)

Coverage Ω (%)

Coverage Ω (%)

80

40

40 β=0

40

30

50

0

5

Churn Rate (%)

10

β=0.2 20

β=0.3 30

β=0 40

50

Churn Rate (%)

(a) ER Graphs

30

0

5

10

β=0.2 20

30

Churn Rate (%)

(b) Grid topologies

(c) GossipSub

β=0 β=0.2 β=0.3

10

β=0.3 40

50

0

0

5

10

20

30

40

50

Churn Rate (%)

(d) Solana (d = 200)

Figure 8: Impact of churn rate c on the coverage of different topologies with n = 1,000 nodes. 100

67

Coverage Ω (%)

Coverage Ω (%)

80 BFT bound 60 NS bound 40

λ=0.01,β=0 λ=1,β=0 λ=10,β=0 λ=0.01,β=0.33 λ=1,β=0.33 λ=10,β=0.33 λ=0.01,β=0.5 λ=1,β=0.5 λ=10,β=0.5

20

0 20

100

1000

Network Size (n)

66.5

66

ξ=1/2 ξ=1/3 ξ=1/4 ξ=1/5 ξ=1/6

65.5

5000

65 50

100

ξ=1/7 ξ=1/8 ξ=1/9 ξ=1/10 1000

5000

Network Size (n)

(a) Impact of message rate λ on (b) Impact of ξ on coverage coverage (80KB) (λ = 120 tx/s, 2KB)

Figure 9: GossipSub: Impact of λ and ξ with β = 0.33. lazily pulled on demand. Each node targets a fixed mesh degree, dynamically maintained within predefined bounds: connections are added when the degree falls below the lower bound and pruned when it exceeds the upper bound. In Ethereum’s default configuration, the target mesh degree is d = 8, and batched metadata are periodically sent to 12 additional random nodes14 , yielding a combined effective degree of ≈ 20. Nodes also maintain per-peer scores based on live statistics, pruning peers with negative scores; further details on peer scoring are provided in Appendix C. Our evaluation follows the parameters used in the GossipSub evaluation report [34] (see Table 3 in Appendix C), which uses the libp2p Go implementation [35] at a rate of sending 2 KB messages of λ = 120 transactions per second. In addition, we evaluate block-sized messages of 80 KB and vary the message rate among 0.01, 1, and 10 messages per second over a 10,000-second simulation, corresponding to 100, 10,000, and 100,000 blocks. This allows us to study how peer scoring parameters behave under different workloads. Impact of Message Rate. We first analyze a static network with large messages (80 KB) and low message rates (Figure 9a). For small networks (n ≤ 200), coverage drops to nearly 10% when the message rate is 0.01 msg/sec, even with no adversaries (β = 0). This occurs because the peer scoring function penalizes honest nodes. In particular, one indicator (see P3a in Appendix C) in the peer scoring function expects each connection to relay known messages 14 We also vary Dlazy , the number of randomly chosen nodes in GossipSub’s lazy pull mechanism (see Figure 18 in Appendix D). The results are highly consistent across all settings, showing that this parameter does not affect our findings.

within a short window. Given the default parameters used in GossipSub (Table 3 in Appendix C), each peer must relay at least 10 known messages per second, each within 5 ms, to avoid penalties. At low message rates and with larger message sizes, this condition is often violated, causing honest peers to be pruned. Over time, nodes exhaust replacement candidates and eventually lose all connections, leading to poor coverage. Although coverage improves for n ≥ 500, this is only because unscored peers remain available near the end of the simulation; ultimately, connections are still exhausted. As the message rate increases, coverage improves and reaches optimal levels when λ ≥ 10. Impact of Adversarial Strategy. These observations reveal that adversaries can exploit the peer scoring mechanism by selectively dropping messages rather than dropping all of them. To evaluate this strategy, we simulate the original setting in [34] with 2 KB messages at 120 msg/s and adversarial bound β = 0.33. We vary the adversarial drop rate ξ between 1/10 and 1/2 (every 10th message and every 2nd message is dropped) and show the minimal achieved coverage of those dropped messages in Figure 9b. We observe that coverage lies at the margin of the required BFT quorum size, and occasionally drops below the required threshold in certain cases. In particular, for small networks with n = 100 (Ω = 66%) and n = 200 (Ω = 65%) at a drop rate of 0.5, a small number of honest nodes can be isolated, failing to meet the required coverage and preventing the formation of a quorum. Even in larger networks, the measured coverage often falls below the BFT quorum size. Note that an adversary that drops all messages (ξ = 1) triggers detection and subsequent pruning in GossipSub. All other evaluated drop rates, ξ ∈ [1/10, 1/2] incur little impact on coverage (Figure 9b). Impact of Churn. Figure 8c shows that coverage decreases as network churn increases, leading to violations of the BFT quorum size for β = 0.33 at churn rates of ≥ 20%. Despite employing a random mesh with degree d = 8, GossipSub outperforms a pure random graph under identical conditions, where the BFT quorum size is violated for any churn rate ≥ 5% when β = 0.33. This improvement is attributable to GossipSubs lazy pull mechanism, which periodically advertises recent message metadata to a random set of Dlazy = 12 peers. As a result, coverage under churn is comparable to that of a grid topology, while avoiding excessive message overhead.

1

Quality(t)

BFT bound 0.6 0.4 0.2 0

β=0 β=0.33 β=0.5 0

0.5

1

1.5

2

2.5

3

3.5

4

β=0 β=0.33 β=0.5

90 80 70 BFT bound

3 2.5

60

2

50

1.5

40 20

Propagation Time t (s)

(a) Impact on quality (n = 1000)

3.5

Delay ∆ (s)

Coverage Ω (%)

0.8

4

β=0.33 β=0.5

100

100

1000

Network Size (n)

(b) Impact of β on coverage

5000

1 20

100

1000

5000

Network Size (n)

(c) Impact of β on delay

Figure 10: Polkadot (grid topologies): Impact of β on the robustness under random corruption.

4.5. Robustness of Dynamic Trees (Solana) Solanas gossip protocol, Turbine [15], uses a dynamic tree topology with chunk-based push dissemination. When a block is generated in an epoch, it is encoded into multiple chunks. For each chunk, a random seed derived from the slot number and chunk index constructs a new spanning tree with degree 200. The block15 producer sends each chunk to the root of its tree, which then propagates it further. To tolerate failures, Turbine applies Forward Error Correction (FEC) with a 32:32 rate, encoding each block into 32 data and 32 recovery chunks, doubling the transmitted data. Chunk sizes are capped at 1,232 bytes, derived from the IPv6 MTU and Solanas QUIC-based transport. We adopt the same chunk size and adjust the FEC rate to 64:64 for our 80 KB messages. Under this setting, a node successfully receives a message once it obtains any 64 chunks, allowing up to 50% chunk loss. Given that the Solana mainnet has roughly 1,000 nodes and a fanout of about 200, we simulate both d = 200 and a smaller fanout of d = 50 to capture more conservative and bandwidth-efficient configurations (Figure 11). For d = 50, the dissemination tree has height 2 when 100 ≤ n ≤ 2000 and increases to 3 at n = 5000. For d = 200, the tree height remains 2 for all n ≥ 500. In our evaluation, we deliberately assume uniform stake distribution across nodes. This setting fits our study: with equal stake, no node is more attractive, whereas any skew concentrates influence and makes it easier for the adversary to corrupt nodes (corrupting high-stake nodes drives coverage to zero). It is also a fairer basis for comparison as our main aim is to compare the robustness of gossip layers, not consensus mechanisms, and the pairing is sometimes incidental: Bitcoin could in principle run GossipSub, and Solana an ER overlay. Nevertheless, we also validate our findings under Solana’s real-world stake distribution, as reported by [36] (see Figure 16 in Appendix D). In this setting, coverage is measured as the fraction of total stake held by nodes that received the data. Random corruption (orange in Figure 16) yields a trend similar to the equal-stake 15 Solana does not define explicit blocks; instead, it produces a stream of transaction entries. We treat a batch of entries as a block.

setting (green), whereas stake-weighted corruption (in blue in Figure 16), which prioritizes high-stake nodes, prevents dissemination entirely. This confirms that our findings are not an artifact of the equal-stake assumption. Rather, equal stake represents a favorable setting for dissemination, since it removes the adversary’s ability to exploit stake concentration when selecting nodes to corrupt. Figure 11b shows that under a weak adversary (β ≤ 0.2), coverage remains healthy until the network size reaches n = 5,000 nodes for d = 50, potentially due to the increase in tree height. In contrast, for β = 0.3, coverage drops sharply as soon as n ≥ 50 and approaches ≈ 0% (d = 50), indicating that more than half of the chunks are lost, and ≈ 36% (d = 200) for n ≥ 5,000 (i.e., tree heights ≥ 3). As shown in Figure 11c, dynamic trees with chunkbased push achieve consistently low latency when coverage is high. For β = 0.1, dissemination delay stays around 0.3 s across all network sizes, matching the no-adversary baseline. With β = 0.2 and 80% coverage, dissemination in a 5,000node network takes only 0.75, s for d = 200, compared to at least 2 s in other configurations. Once coverage degrades under stronger adversaries, latency becomes highly variable. Figure 11a shows a stair-shaped quality curve for n = 1,000, where the tree height is 2 for both fanouts. Flat regions correspond to periods in which chunks are propagating, but nodes have not yet received enough chunks to reconstruct the message, while sharp increases occur when many nodes simultaneously cross the reconstruction threshold. Impact of Churn. Figure 8d shows that dynamic trees with chunk-based propagation are highly sensitive to churn when β ≥ 0.2. With 30% churn nodes, coverage already falls below the BFT threshold 1/3·(1−1/n). Since offline nodes behave, in terms of coverage, equivalently to corrupted nodes, this result is consistent with the static-network findings in Figure 11b, indicating that Solana becomes insecure once the corruption bound exceeds 0.2. Impact of Network Size. With a fixed degree, coverage is affected by network size as the tree grows taller. Although the protocol mitigates hierarchical effects—where nodes closer to the root are more influential—by randomizing the propagation tree for each chunk, Figure 11b still shows a

1

100

3

90

0.4

0 0.1

β=0, d=50 β=0, d=200 β=0.1, d=50 β=0.1, d=200

β=0.2, d=50 β=0.2, d=200 β=0.3, d=50 β=0.3, d=200

1

70 60

BFT threshold

50 40 30 20 10

10

0 20

β=0.1, d=50 β=0.1, d=200 β=0.2, d=50 β=0.2, d=200 β=0.3, d=50 β=0.3, d=200

2 1.5

β=0, d=50 β=0, d=200 β=0.1, d=50 β=0.1, d=200 β=0.2, d=50 β=0.2, d=200 β=0.3, d=50 β=0.3, d=200

1 0.5

100

Propagation Time t (s)

(a) Impact on quality (n = 1,000)

Delay ∆ (s)

Coverage Ω (%)

Quality (t)

BFT bound 0.6

0.2

2.5

80

0.8

1000

5000

0 20

100

Network Size (n)

(b) Impact of β on coverage

1000

5000

Network Size (n)

(c) Impact of β on delay

Figure 11: Solana (dynamic trees): Impact of β on the robustness. strong correlation between coverage and tree height. Specifically, for d = 50, the height first increases at n = 100, leading to insufficient coverage once n ≥ 200 given β = 0.3, and increases again at n = 5,000, causing another coverage drop for β = 0.2. Similarly, for d = 200, coverage decreases at n = 500 when the tree height rises from 1 to 2 (the tree height in Turbine is determined as h = ⌈logd (n)⌉).

5. Interpretation of Findings In the following, we interpret our findings through the lens of our research questions.

5.1. RQ1: When are Gossip Protocols Insecure? Across all evaluated settings, several consistent trends emerge in coverage and delay under adversarial conditions. For ER graphs, coverage is largely independent of network size (Figure 6b and Figure 13a in Appendix D), whereas delay grows with it (Figure 6c). Increasing the node degree notably improves robustness for large adversarial bounds β , but has little impact for small ones. For networks of up to 5,000 nodes, this gain saturates at approximately d ≥ 15, well above ln(5,000) ≈ 8.5. Beyond this point, higher degrees yield no meaningful improvement in coverage and only add bandwidth overhead (Figure 14). For production deployments, the saturation point thus marks a practical upper bound on the connectivity worth investing in. Churn reduces coverage additionally under otherwise identical network and adversarial parameters. Structured grid topologies, in contrast, keep coverage above the bounds in all considered configurations owing to their high connectivity. This makes them best suited to production deployments in which node bandwidth is not the limiting constraint. We note that GossipSub exhibits insufficient coverage at low transaction rates, even without adversaries. Its peerscoring mechanism implicitly assumes more than one transaction per second and predictable link latencies: honest nodes are expected to relay a certain number of messages within a short delivery window or incur penalties. Deploying GossipSub in blockchains with lower transaction rates therefore requires carefully tuning parameters such as the

score refresh interval, the penalty weight, and the delivery window (see Table 3), so as to remain fair to honest nodes while still detecting misbehavior. Moreover, GossipSub is vulnerable to selective dropping: an adversary that forwards some messages but drops others can push coverage below the BFT quorum size, while its score remains largely unaffected. Overall, GossipSub’s scoring function depends heavily on network assumptions, which makes it inflexible and leaves the network vulnerable to adversaries with faster connections. Interestingly, its delays are largely insensitive to both network size and β . For dynamic trees with double recovery chunks, coverage is ideal (1 − β ) for β = 0.1. For β = 0.33, however, it degrades sharply, from 67% at n = 200 to at most 15% at n = 5,000. Chunk-based dissemination with FEC 32:32 over dynamic trees thus cannot guarantee sufficient coverage for any network size or fanout satisfying n > d when β = 0.33. Consequently, if one third of the approximately 1,000 nodes in Solana’s mainnet crash, only about 30% of nodes can reconstruct messages via Turbine, which is insufficient to form a quorum in Solana’s consensus protocol. Finally, churn substantially weakens the robustness of all four gossip protocols, often violating the coverage required for consensus.

5.2. RQ2: How Do Gossip Protocols Compare? The best coverage is achieved by ER graphs with 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, Solana’s dynamic trees are the least reliable protocol: increasing the network size or decreasing the node degree markedly reduces coverage. GossipSub is highly sensitive to the transaction rate, but at sufficiently high λ, its coverage matches that of grids and random graphs with only about half the node degree, since its peer scoring preferentially disconnects underperforming peers. Under churn, grids consistently outperform ER graphs, with about 1% higher coverage for β = 0.1 and churn rate c = 0.05, and up to 4.1% higher coverage for β = 0.3 and c = 0.5.

β

0 0.1 0.2 0.33 0.5

Random Graphs (d = 15) 685 645 595 515 387

Grid (Polkadot) 2969 2798 2599 2299 1835

GossipSub (d = 8) 337 304 269 225 167

Dynamic Trees (Solana d = 200) 142 120 100 – –

TABLE 2: Transmitted data (MB) to gossip an 80 KB message in a 1,000-node network (results for dynamic trees with β ≥ 0.33 are omitted due to insufficient coverage). Without an adaptive adversary, ER graphs (d = 15), GossipSub (d = 8), dynamic trees (d = 200), and grids achieve comparable coverage in a 1,000-node network. Dynamic trees are the most bandwidth-efficient, as erasure coding keeps duplication low, and transfer about 142 MB in total (Table 2). They are followed by GossipSub (337 MB) and ER graphs (685 MB). Grids are the least efficient, requiring about 2.97 GB to disseminate a single 80 KB block. At Polkadot’s rate of one block every 6 seconds, this amounts to 41.75 GB per node per day. At β = 0.33, with corrupted nodes not relaying messages, total bandwidth drops to about 226 MB for GossipSub, 515 MB for ER graphs, and 2.3 GB for grids, i.e., 67%, 75%, and 77% of the benign volume, respectively. We exclude dynamic trees here, since they no longer provide sufficient guarantees at this bound. The higher relative volume of ER graphs and grids reflects data lost along paths through corrupted nodes, whereas GossipSub actively excludes poorly performing peers from dissemination paths. This efficiency, however, comes at the cost of sensitivity to parameter tuning: if the expected message rate or network latency is misestimated, or if an adversary selectively drops messages, GossipSub’s coverage can degrade severely. Taken together, these findings indicate that none of the modern gossip protocols we study achieves a markedly better tradeoff between robustness, performance, and bandwidth than a simple Erdős–Rényi (ER) random graph, a structure whose properties are well understood. The added protocol complexity (e.g., of Dynamic Trees and GossipSub) does not necessarily translate into added security. Random graphs instantiated with a sufficient degree (d ≥ 15) thus emerge as a practical choice for production deployments, offering a strong balance between robustness and performance while remaining simple to analyze and implement.

6. Related Work Almost all consensus protocols, including traditional BFT protocols and Proof-of-Work or Proof-of-Stake protocols, are designed under the assumption that message delivery is eventually guaranteed among all honest available nodes. Our work shows that existing gossip protocols [12], [14], [15], [37] fail to provide that guarantee in practice, and we introduce adversarial strategies that exploit this observation and are not captured by existing models. Efficient Gossip Protocols for Blockchains. A substantial body of work improves the efficiency of gossip-based block

dissemination by optimizing bandwidth, latency, and routing [12], [38]–[41]. Bitcoins compact blocks [38] reduce bandwidth by sending short transaction identifiers instead of full blocks, at the cost of an extra round-trip for reconstruction. Erlay [39] further reduces overhead via set reconciliation, trading bandwidth efficiency for higher latency. Other systems optimize routing rather than message format. BlockP2P [42] exploits geographic locality to accelerate intra-cluster propagation, but increases vulnerability to partitioning if adversaries target inter-cluster links. Mercury [41] uses virtual coordinate systems to estimate efficient paths and applies a high initial fanout to speed up early dissemination, though its security degrades if coordinates are spoofed. Perigee [40] constructs an optimized routing graph based on peer scoring and observed block arrival times; however, such adaptive routing is susceptible to eclipse attacks by well-connected adversaries. Kumar et al. [43] formally analyze GossipSub’s scoring function and show that its correctness hinges on the choice of weights, which corroborates our findings. We significantly extend their analysis by measuring GossipSub’s effective coverage alongside three other gossip protocols, enabling a direct comparison of their security. Robust Gossip Protocols. Despite their importance, the robustness of gossip protocols under adversarial conditions has received limited attention. Early work by Karp et al. [37] and Kermarrec et al. [44] analyzes rumor spreading on dynamic or random graphs under benign failures, characterizing the trade-off between fanout and reliability while largely abstracting away Byzantine behavior and adversarial membership manipulation. To address Byzantine faults, Corretti et al. [45] propose a gossip layer for proof-ofstake blockchains that samples neighbors using VRFs and stake-weighted connections, providing Sybil resistance but remaining vulnerable to eclipse attacks under sufficient adversarial stake. More recently, Albrecht et al. [10] studied the impact of gossip behavior on NS-blockchains, but only consider a static adversary that randomly corrupts edges, and do not consider adaptive or targeted network attacks. Network Attacks on Blockchains. A complementary line of work examines attacks on blockchain network layers. Eclipse attacks [24], [27] exploit weaknesses in peer discovery to isolate victims with adversarial peers, enabling message filtering or delay; Gervais et al. [9] show that this can substantially slow Bitcoins propagation without full partitioning. Routing-level attacks further exacerbate these threats. Apostolaki et al. [46] demonstrate that BGP hijacks can partition Bitcoin or severely delay propagation, while stealthier variants [47] poison routing paths via spoofed IPs. To counter routing-level attacks, Apostolaki et al. [48] proposed SABRE, which mitigates such attacks by leveraging a coexisting relay network with secure channels. However, this approach requires trust in the relay nodes. In this paper, we show that an adversary can simply exploit the topology adaptively to achieve partition without exploiting vulnerabilities in node discovery protocols, and without requiring additional resources such as compromised ASs or IPs.

7. Conclusion In this paper, we analyzed the robustness of the gossip protocols used in popular decentralized platforms. Our analysis and extensive measurements reveal a notable gap between the guarantees classical BFT protocols require and those these gossip protocols provide against realistic network adversaries. Specifically, we evaluated random graphs, Polkadot’s grid topology, Ethereum’s GossipSub, and Solana’s chunkand tree-based protocols. Polkadot is the most robust under adaptive attacks, combining consistently high coverage with stable delays, albeit at a very high bandwidth cost. Random graphs achieve similar robustness with a sufficiently high degree (d ≥ 15). In contrast, Bitcoin’s degree of 8, which coincides with the recommended connectivity for random graphs [13], and Solana’s dynamic trees prove unreliable under attack, particularly at scale. GossipSub yields more variable performance and is highly sensitive to parameter tuning. Overall, despite their simplicity, random graphs with a sufficient degree emerge as a practical choice for decentralized deployments, offering a strong tradeoff between robustness and performance. To ensure reproducibility, the simulator code and the data for all experiments are available at [49].

Acknowledgments The authors thank the reviewers for their helpful feedback. This work has been partly funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – EXC 2092 CASA – 390781972.

References [1]

[2]

[3]

[4] [5] [6] [7] [8] [9]

B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-Efficient Learning of Deep Networks from Decentralized Data,” in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April, Fort Lauderdale, FL, USA, 2017. X. Lian, C. Zhang, H. Zhang, C. Hsieh, W. Zhang, and J. Liu, “Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent,” in Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, Long Beach, CA, USA, 2017. H. Tang, X. Lian, M. Yan, C. Zhang, and J. Liu, “D2 : Decentralized Training over Decentralized Data,” in Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018. Mastodon, “Join Mastodon.” https://joinmastodon.org/, accessed on January 2026. Mastodon, “Mastodon GitHub Repository.” https://github.com/ mastodon/mastodon/, accessed on January 2026. IPFS.tech, “IPFS.” https://ipfs.tech/, accessed on January 2026. Odysee, “Odysee.” https://odysee.com/, accessed on January 2026. Open Audio Foundation, “Audius.” https://audius.org/, accessed on January 2026. A. Gervais, H. Ritzdorf, G. O. Karame, and S. Capkun, “Tampering with the Delivery of Blocks and Transactions in Bitcoin,” in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, ACM, 2015.

[10] J. Albrecht, S. Andreina, F. Armknecht, G. Karame, G. Marson, and J. Willingmann, “Larger-scale Nakamoto-style Blockchains Don’t Necessarily Offer Better Security,” in 2024 IEEE Symposium on Security and Privacy (SP), IEEE, 2024. [11] A. Gervais, G. O. Karame, V. Capkun, and S. Capkun, “Is Bitcoin a Decentralized Currency?,” IEEE Secur. Priv., 2014. [12] D. Vyzovitis, Y. Napora, D. McCormick, D. Dias, and Y. Psaras, “GossipSub: Attack-Resilient Message Propagation in the Filecoin and ETH2.0 Networks,” arXiv preprint arXiv:2007.02754, 2020. [13] P. Erdos and A. Renyi, “On the Evolution of Random Graphs,” Publ. Math. Inst. Hungary. Acad. Sci., 1960. [14] Polkadot, “Polkadot source code of the grid topology.” https://github.com/paritytech/polkadot/blob/master/node/network/ protocol/src/grid topology.rs, accessed on 9th September 2025. [15] Solana Documentation, “Turbine block propagation.” https:// docs.anza.xyz/consensus/turbine-block-propagation/, accessed on 9th September 2025. [16] Y. Aoki, K. Otsuki, T. Kaneko, R. Banno, and K. Shudo, “SimBlock: A Blockchain Network Simulator,” in IEEE INFOCOM 2019 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 325–329, 2019. [17] I. Eyal and E. G. Sirer, “Majority Is Not Enough: Bitcoin Mining Is Vulnerable,” in Financial Cryptography and Data Security - 18th International Conference, FC 2014, Christ Church, Barbados, March 3-7, 2014, Revised Selected Papers, Springer, 2014. [18] A. Gervais, G. O. Karame, K. Wüst, V. Glykantzis, H. Ritzdorf, and S. Capkun, “On the Security and Performance of Proof of Work Blockchains,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, ACM, 2016. [19] A. Dembo, S. Kannan, E. N. Tas, D. Tse, P. Viswanath, X. Wang, and O. Zeitouni, “Everything is a Race and Nakamoto Always Wins,” in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, CCS ’20, 2020. [20] K. Li, Y. Tang, J. Chen, Y. Wang, and X. Liu, “TopoShot: uncovering Ethereum’s network topology leveraging replacement transactions,” in IMC ’21: ACM Internet Measurement Conference, Virtual Event, USA, ACM, 2021. [21] C. Zhao, Y. Zhou, S. Zhang, T. Wang, Q. Z. Sheng, and S. Guo, “DEthna: Accurate Ethereum Network Topology Discovery with Marked Transactions,” in IEEE INFOCOM 2024-IEEE Conference on Computer Communications, IEEE, 2024. [22] S. Delgado-Segura, S. Bakshi, C. Pérez-Solà, J. Litton, A. Pachulski, A. Miller, and B. Bhattacharjee, “TxProbe: Discovering Bitcoin’s Network Topology Using Orphan Transactions,” in Financial Cryptography and Data Security - 23rd International Conference, FC 2019, Frigate Bay, St. Kitts and Nevis, February 18-22, 2019, Revised Selected Papers, Springer, 2019. [23] T. Cao, J. Yu, J. Decouchant, X. Luo, and P. Veríssimo, “Exploring the Monero Peer-to-Peer Network,” in Financial Cryptography and Data Security - 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10-14, 2020 Revised Selected Papers, Springer, 2020. [24] E. Heilman, A. Kendler, A. Zohar, and S. Goldberg, “Eclipse Attacks on Bitcoin’s Peer-to-Peer Network.,” in USENIX Security Symposium, USENIX Association, 2015. [25] D. Koschützki, K. A. Lehmann, L. Peeters, S. Richter, D. TenfeldePodehl, and O. Zlotowski, Centrality Indices. Springer Berlin Heidelberg, 2005. [26] A. Hagberg, D. Schult, and P. Swart, “NetworkX Python Library.” https://github.com/networkx/networkx, 2004. [27] Y. Marcus, E. Heilman, and S. Goldberg, “Low-Resource Eclipse Attacks on Ethereum’s Peer-to-Peer Network,” IACR Cryptol eprint Arch, 2020. [28] Solana Compass, “Solana’s Decentralization In Numbers – How have the number of validators grown over time?.” https:// solanacompass.com/statistics/decentralization, accessed on 7th May 2025. [29] M. A. Imtiaz, D. Starobinski, A. Trachtenberg, and N. Younis, “Churn in the Bitcoin Network,” IEEE Transactions on Network and Service Management, 2021.

[30] C. Matt, J. B. Nielsen, and S. E. Thomsen, “Formalizing Delayed Adaptive Corruptions and the Security of Flooding Networks,” in Annual International Cryptology Conference, Springer, 2022. [31] Y. Nil and A. Langley, “RFC8439 - ChaCha20 and Poly1305 for IETF Protocols.” https://datatracker.ietf.org/doc/html/rfc8439, 2018. [32] L. Heimbach, Y. Vonlanthen, J. Villacis, L. Kiffer, and R. Wattenhofer, “Deanonymizing ethereum validators: The P2P network has a privacy issue,” in 34th USENIX Security Symposium, USENIX Security 2025, Seattle, WA, USA, August 13-15, 2025, USENIX Association, 2025. [33] Polkadot SDK Documentation, “The Polkadot Parachain Host Implementers’ Guide – Grid Topology.” https://paritytech.github.io/ polkadot-sdk/book/node/backing/statement-distribution.html#gridtopology, accessed on 7th May 2025. [34] D. Vyzovitis, Y. Napora, D. McCormick, D. Dias, and Y. Psaras, “Gossipsub-v1. 1 evaluation report,” Protocol Labs, Tech. Rep., 2020. [35] github.com, “go-libp2p-pubsub.” https://github.com/libp2p/golibp2p-pubsub/, accessed on 19th December 2025. [36] Solana Beach, “Stake Distribution of Validators in the Solana Network.” https://solanabeach.io/validators, accessed on 23rd August 2026". [37] R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking, “Randomized Rumor Spreading,” in Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 565–574, IEEE, 2000. [38] M. Corallo, “Compact Block Relay.” https://github.com/bitcoin/bips/ blob/master/bip-0152.mediawiki, 2016. [39] G. Naumenko, G. Maxwell, P. Wuille, A. Fedorova, and I. Beschastnikh, “Erlay: Efficient Transaction Relay for Bitcoin,” in Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, 2019. [40] Y. Mao, S. Deb, S. B. Venkatakrishnan, S. Kannan, and K. Srinivasan, “Perigee: Efficient Peer-to-Peer Network Design for Blockchains,” in Proceedings of the 39th Symposium on Principles of Distributed Computing, ACM, 2020. [41] M. Zhou, L. Zeng, Y. Han, P. Li, F. Long, D. Zhou, I. Beschastnikh, and M. Wu, “Mercury: Fast Transaction Broadcast in High Performance Blockchain Systems,” in IEEE INFOCOM 2023 - IEEE Conference on Computer Communications, IEEE, 2023. [42] W. Hao, J. Zeng, X. Dai, J. Xiao, Q. Hua, H. Chen, K.-C. Li, and H. Jin, “BlockP2P: Enabling Fast Blockchain Broadcast with Scalable Peer-to-Peer Network Topology,” in Green, Pervasive, and Cloud Computing, Springer International Publishing, 2019. [43] A. Kumar, M. von Hippel, P. Manolios, and C. Nita-Rotaru, “Formal Model-Driven Analysis of Resilience of GossipSub to Attacks from Misbehaving Peers,” in 2024 IEEE Symposium on Security and Privacy (SP), IEEE, 2024. [44] A.-M. Kermarrec, L. Massoulié, and A. J. Ganesh, “Probabilistic Reliable Dissemination in Large-Scale Systems,” IEEE Transactions on Parallel and Distributed systems, 2003. [45] S. Coretti, A. Kiayias, C. Moore, and A. Russell, “The Generals’ Scuttlebutt: Byzantine-Resilient Gossip Protocols,” in Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, 2022. [46] M. Apostolaki, A. Zohar, and L. Vanbever, “Hijacking Bitcoin: Routing Attacks on Cryptocurrencies,” in 2017 IEEE Symposium on Security and Privacy (SP), IEEE, 2017. [47] M. Tran, I. Choi, G. J. Moon, A. V. Vu, and M. S. Kang, “A Stealthier Partitioning Attack against Bitcoin Peer-to-Peermo Network,” in 2020 IEEE Symposium on Security and Privacy (SP), ieeexplore.ieee.org, 2020. [48] M. Apostolaki, G. Marti, J. Müller, and L. Vanbever, “SABRE: Protecting Bitcoin against Routing Attacks,” arXiv [cs.NI], 2018. [49] GitHub, “Gossip Protocol Simulator for Blockchains.” https:// github.com/RUB-InfSec/gossip protocol robustness. [50] T. Neudecker, P. Andelfinger, and H. Hartenstein, “Timing analysis for inferring the topology of the bitcoin peer-to-peer network,” in Proceedings of the 13th IEEE International Conference on Advanced and Trusted Computing (ATC), 2016. [51] PolkaWatch, “Polkadot Geography.” https://polkawatch.app/ geography. [52] https://ethpandaops.io/, “Xatu data.” https://github.com/ethpandaops/ xatu-data.

[53] EthPandaOps, “EthPandaOps.” https://ethpandaops.io/. [54] Maria Silva, “An analysis of attestation timings in a 6-s slot.” https://rig.ethereum.org/post/an-analysis-of-attestation-timings-in-a6-s-slot. [55] ProbeLab Analytics, “ProbeLab – GossipSub.” https://probelab.io/ ethereum/gossipsub/. [56] bitfly explorer gmbh, “Ethereum Mainnet Statistics.” https:// www.ethernodes.org/countries. [57] Solana, “Solana Metrics.” https://metrics.solana.com/.

Appendix A. Centrality Metrics Our analysis (cf. Sections 3.3 and 4) uses the four most common centrality metrics: Degree centrality captures a node’s one-hop connectivity as its degree normalized by the maximum possible degree, deg(N ) n−1 . Eigenvector centrality accounts not only for a node’s links but also for the centrality of its neighbors. It is given by the corresponding entry of the principal eigenvector x of the adjacency matrix A, i.e., Ax = λx. Betweenness centrality measures how often a node acts as a bridge, which is especially relevant in clustered networks. ∑ σ (N ) It is defined as N1 ,N2 ∈N \{N } Nσ1NN2N , where σN1 N2 is 1 2 the number of shortest paths from N1 to N2 and σN1 N2 (N ) the number of those passing through N . Closeness centrality reflects a node’s proximity to the rest ′ of the network as ∑ ′ n−1 ′ , where dist(N, N ) is N ̸=N dist(N,N ) the shortest-path length between N and N ′ .

Appendix B. Simulator Validation As mentioned earlier, we cannot conduct our evaluation on live networks directly. Doing so would disrupt real users and put funds at risk, and it would also be infeasible, since we cannot control parameters such as the size of an existing network. One of the few workable means to validate our results is therefore to show that our simulator faithfully reproduces the behavior of the real networks in the benign setting. To this end, we compare the message-arrival-time distributions observed by our simulated nodes with those observed by unmodified validator nodes in each of the blockchain networks we consider (as the availability of such measurements varies widely across blockchains, we obtain them through network-specific means). For each network, we compare both the CDF and the PDF of message latencies and check whether the simulated distributions match those observed in practice. Bitcoin. For Bitcoin, we use block propagation delays publicly reported in [50] and derived from block announcements by unmodified Bitcoin nodes. Among the collected network statistics, we use the time between the first reception of an INV message announcing a new block and its subsequent receptions from other peers, retrieved on 2022-09-11. To faithfully compare with our simulator, we simulate 10,000

1.0

Real-world Network Simulator

0.0020

Cumulative probability

Probability density (per ms)

0.0025

0.0015 0.0010 0.0005 0.0000

0

0.6 0.4 0.2 0.0

500 1000 1500 2000 2500 3000 3500 4000

Real-world Network Simulator

0.8

Block propagation latency (ms)

0

0.003

(b) Bitcoin CDF

0.002 0.001 0.000

0

200

400

600

800

1000

Block propagation latency (ms)

0.6 0.4 0.2 0.0

1200

Real-world Network Simulator

0.8

0

0.004

0.002 0.001 0

500

1000

1500

2000

Cumulative probability

Probability density (per ms)

0.003 0.002 0.001 100

200

300

400

500

600

700

Block propagation latency (ms)

(g) Solana PDF

1200

0.6 0.4 0.2 0

500

1000

1500

2000

2500

Block propagation latency (ms)

(f) Ethereum CDF

0.004

0

1000

1.0

Real-world Network Simulated

0.005

0.000

800

Real-world Network Simulator

(e) Ethereum PDF 0.006

600

0.8

0.0

2500

Block propagation latency (ms)

0.007

400

Block propagation latency (ms)

(d) Polkadot CDF

0.003

0.000

200

1.0

Real-world Network Simulator

Cumulative probability

Probability density (per ms)

(c) Polkadot PDF 0.005

Block propagation latency (ms)

1.0

Real-world Network Simulator

Cumulative probability

Probability density (per ms)

(a) Bitcoin PDF 0.004

500 1000 1500 2000 2500 3000 3500 4000

800

0.8

Real-world Network Simulated

0.6 0.4 0.2 0.0

0

100

200

300

400

500

600

Block propagation latency (ms)

700

800

(h) Solana CDF

Figure 12: CDF and PDF of block propagation latencies observed in Bitcoin, Polkadot, Ethereum, and Solana vs. those produced by our simulator. nodes with a message size of 1.6 MB, matching the Bitcoin network configuration. Figure 12a and Figure 12b show the PDF and CDF, respectively, of the latency distribution produced by our simulator and of the block propagation distribution measured from Bitcoin nodes. The two distributions are highly similar, with a Pearson correlation coefficient of ρ = 0.93. Polkadot. We measure block propagation delays using the public Polkadot telemetry service, a collector to which Polkadot nodes stream operational events such as block imports in real time. Since the stock Polkadot client reports to this service by default, telemetry offers a passive view of propagation as experienced by unmodified nodes on the live network, without requiring us to deploy or instrument any nodes ourselves. We subscribed to the telemetry feed (wss://feed.telemetry.polkadot.io/feed) for the Polkadot chain, identified by its genesis hash 0x91b171bb..., and recorded every block-import report over a 1-hour window on 2026-09-21. Each report contains a propagation time computed by the collector as the interval

between the first report of a block in the network and the reception of that block by each node. We retain only nodes that publish a validator stash address and discard reports with a propagation time of zero, which correspond to the node that first announced the block, as well as reports exceeding 6 s, which stem from nodes that are resyncing or stalled. Since telemetry participation is self-selected and over-represents nodes hosted in European infrastructure relative to the actual validator set, we compare against a simulator configuration with validators placed predominantly in Europe [51], with 600 nodes and an 80 KB message size. This way, the simulated population mirrors the measured sample’s scale and geographic composition. For Polkadot, the block-arrival-time distribution in our simulator closely matches that measured from unmodified validator nodes, for the PDF (Figure 12c) and the CDF (Figure 12d), with a Pearson correlation coefficient of ρ = 0.99. Ethereum’s GossipSub. For Ethereum, we obtain block arrival times from Xatu [52], a public collection of beacon-chain events released by ethPandaOps [53]. Contributors run a Xatu sentry sidecar alongside their unmodified beacon node, which records the node’s event stream and publishes it as daily Parquet files. We use the mainnet libp2p_gossipsub_beacon_block table from 2026-09-01 to 2026-09-28, whose field propagation_slot_start_diff gives the time in milliseconds between the start of a block’s slot and its observation at the P2P layer. Since this interval also includes block preparation time, which typically exceeds one second on average [54], [55], we instead reference each block to its earliest observation across all sentries. We remove repeated events for the same block, e.g., caused by reorgs or client restarts, and discard observations exceeding 12 s. We then compute the time from the block’s earliest observation until 95% of its observing sentries have reported it. As libp2p_ events reflect only the network layer, we further retain only blocks that were validated and imported by the consensus layer, as recorded in beacon_api_eth_v1_events_block. Since the observing sentries are concentrated predominantly in Europe, we adjust the regional distribution of our simulator accordingly and simulate a network of 6,000 nodes (see consensus-layer validators in [56]). with a message size of 180 kB. The simulated and observed distributions closely match (Figures 12e and 12f), with a Pearson correlation coefficient of ρ = 0.95. Solana’s Dynamic Trees. We obtain observed metrics from Solana’s public cluster telemetry [57], to which unmodified validator nodes can opt in to report timestamped data points for internal events such as block production stages and shred propagation. Since reporting is built into the client and requires no changes to the node software, these metrics reflect propagation as experienced by nodes running on the live network. The reports are collected in a shared InfluxDB instance that backs the public dashboards at metrics.solana.com. From this database, we extract the fetch_shred_insert_is_full met-

P3b Degree

Interval

0.0027 0.664 0.9916 -0.25 10 1 min -0.25 8 6 1 sec

cap1 cap2

3600 1500

cap3 decay3a DeliveryWin3 decay3b Dlazy Dhigh DecayInterval

2 0.997 5 ms 0.997 12 12 1 sec

TABLE 3: GossipSub simulation parameters ric, which records, for each slot, the time between a node’s receipt of the first and the last shred. Unlike the other systems we consider, Solana does not disseminate a block as a single unit. Instead, the leader streams data continuously throughout its slot. With a slot duration of 250 ms and data emitted every 50 ms, the first shred a node receives belongs to the batch emitted at offset 0 ms, and the last shred to the batch emitted at offset 200 ms. To reproduce this, we configure our simulated chunk- and tree-based protocol to emit a 100 KB message every 50 ms in a 700-node network. We then derive the slot-level distribution from the per-message latency distribution: we shift the latter by each emission offset from 0 ms to 200 ms, sum the shifted distributions, and truncate all mass below 200 ms. Our validation results show that the simulator closely matches the measured real-world data for both the PDF (Figure 12g) and the CDF (Figure 12h), with a Pearson correlation coefficient of ρ = 0.94.

P3b (mesh message delivery failures) Number of failed deliveries in lazy-pull mode, with weight w3b < 0, decaying over time. Scores are updated at every DecayInterval, and peers with negative scores are pruned. Upon pruning, P1 and P2 are reset, whereas P3b is retained and incremented by any active P3a penalty, discouraging the re-grafting of poorly performing peers. Consequently, only two behaviors are rewarded: remaining in the mesh for a long time and delivering messages promptly.

Appendix D. Additional Plots β=0.1 β=0.2

100

7

β=0.33 β=0.5

6

90 5

80

Delay ∆ (s)

P3a

w1 w2 decay2 w3a threshold3 ActivationWin3 w3b D Dlow HeartbeatInterval

Coverage Ω (%)

P1 P2

70 BFT bound 60 50 NS bound

3

1

30 20

100

1000

0 20

5000

100

Network Size (n)

1000

5000

Network Size (n)

(a) Impact of β on coverage

(b) Impact of β on delay

Figure 13: ER graphs: Impact of β (degree-based greedy adversary) on coverage and delay.

100

7

70 60 50

Delay ∆ (s)

Coverage (%)

80 BFT bound NS bound

40

β=0, d=8 β=0.3, d=8 6 β=0.3, d=15 β=0.3, d=20 5 β=0.5, d=8 β=0.5, d=15 β=0.5, d=20 4

3 2

30 20 10 20

β=0.3, d=8 β=0.3, d=15 β=0.3, d=20

β=0.5, d=8 β=0.5, d=15 β=0.5, d=20

100

1000

1 0 20

5000

100

Network Size (n)

1000

5000

Network Size (n)

(a) Impact on coverage

(b) Impact on delay

Figure 14: ER graphs: Impact of d and β (degree-based greedy attacker) on the coverage and delay. β=0.32,δ=10ms β=0.32,δ=40ms β=0.32,δ=50ms

100

β=0.5,δ=10ms β=0.5,δ=40ms β=0.5,δ=50ms

14 12

80

β=0.32,δ=40ms β=0.32,δ=50ms β=0.5,δ=40ms β=0.5,δ=50ms

10 BFT bound

Delay (s)

Coverage (%)

GossipSub’s security rests on its peer scoring function. Each node scores each ∑6of its mesh peers based on live statistics as score = k=1 wk Pk , where Pk is a scoring indicator and wk its weight (P1 –P4 are topic-specific in the original design; we assume a single topic). Indicators are either capped or decay at every DecayInterval, in which case they are rounded down to zero once below DecayToZero. Since we do not simulate invalid messages, we ignore P4 (invalid messages) and P5 –P6 (application-specific scores, e.g., IP co-location penalties) and focus on the following indicators: P1 (time in mesh) Time the peer has spent in the mesh, capped at cap1 . P2 (first message deliveries) Number of messages the peer delivered first, capped at cap2 and decaying at rate decay2 . P3a (mesh message delivery rate) Penalizes slow relaying. Once the peer has been in the mesh for ActivationWin3 , messages (including duplicates) it delivers within DeliveryWin3 are counted, up to cap3 and decaying at rate decay3 . If the count falls below Threshold3 , then P3a = (Threshold3 − count)2 with weight w3a < 0; otherwise, P3a = 0. The short delivery window prevents replay-based attacks.

4

2

40

90

Appendix C. Peer Scoring in GossipSub

β=0 β=0.1 β=0.2 β=0.33 β=0.5

60 NS bound

8

40

6

20

4

0 20

100

1000

5000

Network Size (n)

(a) Impact of δcor on coverage

2 20

100

1000

5000

Network Size (n)

(b) Impact of δcor on delay

Figure 15: ER graphs: Impact of corruption delays of adaptive adversaries (d = 8).

Stake Coverage Ω (%)

80

Churn rate

Solana stake, random adversary Equal stake, random adversary Solana stake, stake-weighted

BFT bound 60

Fraction of nodes that are online and benign β = 0.0 β = 0.2 β = 0.3 β = 0.5

c = 5% c = 10%

NS bound 40

98.3% 96.8% 93.5% 90.0% 86.9% 83.4%

c = 20% c = 30%

20

c = 40% c = 50%

0 0

1000

2000 3000 Network Size (n)

4000

78.6% 77.3% 74.9% 72.1% 69.3% 66.8%

68.8% 67.7% 65.3% 63.1% 60.5% 58.4%

49.2% 48.4% 46.7% 44.9% 43.6% 41.7%

5000

40 30

0

2

4

6

8

0.5 10

12

14

0.0 16

Number of additional peers

70 BFT bound

2.0

60

1.5

50

NS bound

1.0 Default value

1.0

Delay (s)

1.5

NS bound

Default value

Coverage Ω (%)

2.0

60 50

2.5

Coverage Ω (%)

Polkadot

70 BFT bound

40 30

0

2

4

6

8

10

12

Delay (s)

TABLE 4: Impact of churn on Figure 16: Coverage in quorum formation: BFT and Solana under real-world NS quorums (blue), NS only (peach), neither (gray). stake distribution.

0.5

14

0.0 16

Number of lazy pull nodes Dlazy

Figure 17: Impact of ad- Figure 18: Impact of the ditional randomly selected number of lazy pull nodes nodes in Polkadot. Dlazy in GossipSub.

Appendix E. Ethics Considerations

Appendix F. Meta-Review The following meta-review was prepared by the program committee for the 2027 IEEE Symposium on Security and Privacy (S&P) as part of the review process as detailed in the call for papers.

F.1. Summary This work compares the gossip and topology of several major blockchain protocols including an Erdos-Renyi random graph for Bitcoin, Polkadot’s grid network, the Gossip Sub protocol used by Ethereum and a few other protocols and Solana’s dynamic tree-based gossip protocol. Through simulations of several network parameters, the paper compares how much of the network receives new messages and the maximum delay to get a message to these nodes. They also present various adversarial models (random corruption and selective corruption given different observability) with the goal of delaying announcements, or not participating in gossip at all.

F.2. Scientific Contributions •

This work investigates the robustness of widely deployed gossip protocols under realistic adaptive adversarial strategies, with the overarching goal of advancing the security and resilience of existing decentralized platforms. While our findings indicate potential limitations in the robustness of Solanas gossip protocol and GossipSub to adaptive attacks, all experiments were conducted exclusively within a controlled simulation environment. We did not interfere with the operation of any live Solana or GossipSub network nodes. Namely, all data used to validate our simulator (in Section 4.1 and Appendix B) was obtained from publicly available trackers and telemetry services. Some of our results depend on partial knowledge of the underlying network topology. Where topology information is not publicly available, we rely exclusively on methods established in prior work, rather than introducing new topology extraction techniques, a deliberate choice given the ethical considerations involved. Note that Ethereum’s network topology, unlike Solana’s, is not publicly disclosed, though it can be inferred through active probing. Accordingly, Figure 4 presents the Ethereum Testnet topology as reconstructed via transaction isolation by prior work, rather than the live Ethereum mainnet. Nevertheless, we disclosed our findings to the relevant stakeholders: in particular, to Solana to highlight the lack of robustness in their gossip protocol, and to the GossipSub developers to inform them of its sensitivity to misconfigurations.

•

Creates a New Tool to Enable Future Science Provides a Valuable Step Forward in an Established Field

F.3. Reasons for Acceptance 1) Provides a Valuable Step Forward in an Established Field: Important issue for all blockchains that is often overlooked; By covering the gossip protocols of the most important protocols in the blockchain space, the research is relevant for many real-world systems. The approach is cross-layer studying the impact of network on consensus. 2) Creates a New Tool to Enable Future Science: The authors present a new simulation framework. In-depth experimental study of the trade-offs faced with regard to gossip in terms of efficiency and robustness in the face of various adversarial models.

Related documents

• On the Robustness of Gossip Protocols in Modern Blockchains#1356862
• Proof-of-Stake Consensus Mechanisms for Future Blockchain Networks: Fundamentals, Applications and Opportunities#199658
• Decentralized by Design, Centralized by Necessity: The Blockchain-Surveillance Dilemma.#678494
• Breaking Cycles for Scalable Fair Ordering in Blockchain Systems#820842
• Hierarchical consensus: A horizontal scaling framework for blockchains#476217