CS Paper Radar

On the Robustness of Gossip Protocols in Modern Blockchains

Wenting Li, Jannik Albrecht, Frederik Armknecht, Ghassan Karame

cs.CR ·submitted 2026-10-15 08:56 UTC · v1
top venue

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, Polkadot's grid topology, Ethereum's GossipSub, and Solana's chunk- and tree-based disseminations. Our results reveal surprising tradeoffs: Solana's dynamic trees are bandwidth-efficient in benign settings but fragile under adaptive attacks; Polkadot's grid achieves strong robustness at the cost of high bandwidth overhead; GossipSub is both bandwidth-efficient and resilient to adaptive adversaries, yet highly sensitive to parameter choices; and ER graphs provide a strong robustness-efficiency tradeoff, e.g., when the (average) fanout degree exceeds 15 for networks up to 5000 nodes.

Comment
Accepted at IEEE Symposium on Security and Privacy (IEEE SP), 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Attacking P2P Networks: Liveness Attacks on the GossipSub and DOG Gossip Protocols

cs.CR ·2026-11-02 ·Jiaheng Li, Anton Paramonov, Yann Vonlanthen
similarity 0.75
Abstract

Peer-to-peer (P2P) networks form the communication layer of large decentralized systems such as Ethereum, and the correctness of higher-level protocols depends on the gossip layer delivering messages to honest nodes. We study the robustness of two gossip protocols against adversaries whose only goal is to violate liveness, that is, to prevent honest nodes from receiving fresh messages, without forging, altering, or invalidating any message. For GossipSub, the publish-subscribe protocol used by Ethereum, we show that an adversary operating a constant number of geographically distributed nodes with a fixed latency advantage can take over the ``First Message Deliveries'' peer-scoring term and separate a constant fraction of nodes from the honest mesh. We analyze the attack under a geographical model, address the random-peer and outbound-connection mechanisms, and show that the separation can be maintained under realistic churn. For DOG, a transaction-dissemination protocol designed for CometBFT, we first give simple counterexamples in which route filtering disconnects the dissemination graph even without failures or Byzantine participants, and then present a practical attack that uses only a single physical node with a constant number of identities and legitimate actions to disable every forwarding route, separating the full network while allowing only direct publisher-to-neighbor delivery. We verify the attack in a simulated network and analyze its cost, assumptions, and possible mitigations.

0.11

Mitigating Front-Running Attacks through Fair and Resilient Transaction Dissemination

cs.DC ·2026-09-21 ·Wassim Yahyaoui, Joachim Bruneau-Queyreix, Jérémie Decouchant, Marcus Völp
publishedhighly cited similarity 0.68
Abstract

In modern blockchains, efficient, fair, and faulttolerant information dissemination is critical for performance and security. Several stages of the transaction lifecycle are affected, from the creation and dissemination of transactions to the dissemination of blocks in the consensus layer. Mempool protocols, such as L{Ø}, already address some of modern blockchains' security threats. However, others remain unless fairness is embedded most fundamentally in the dissemination layer used by these protocols to share transactions and blocks and to reconcile mempools. This paper introduces HERMES, a novel dissemination protocol for mempools that leverages robust minimal structures to optimize data propagation, balance load, and ensure fairness despite faults and Byzantine actors. Specifically, we address front-running attacks by randomizing the choice of an overlay structure while forcing nodes to prove adherence to the mempools' dissemination policies and the random choice made. Experimental results show significant performance improvements compared to traditional broadcast protocols for both permissioned and permissionless blockchains.

0.57

Improving the Robustness of the XRP Ledger Network via Edge Augmentation Strategies

cs.CR ·2026-08-26 ·Afonso Vilalonga, Orkun İrsoy, João S. Resende, Henrique Domingos, Osman Yağan
similarity 0.65
Abstract

The XRP Ledger allows its network participants to select a set of trusted peers within the network (i.e., the Unique Node List (UNL)) and communicate with them to reach consensus on which transactions should be included in the next ledger state. However, its consensus protocol requires significant overlap among participants' UNLs, along with a high agreement threshold among the nodes within each UNL (e.g., 80\%). Consequently, an attacker could disrupt the consensus process in such a network by targeting the nodes that form the network's connectivity backbone and reducing the number of trusted participants that can communicate with one another below the required threshold. In this paper, we evaluate strategies to improve the robustness of the XRP Ledger's existing topology, as measured by our formal definitions of quorum and network robustness, and compare them to a second strategy from prior work. The strategy we present is an addition/augmentation approach, in which new edges are added based on different constructions. The second strategy is a rewiring or edge-replacement approach, in which the overall number of edges is preserved but they are rearranged. For each strategy, we consider two different cases: one in which all nodes participate in the edge construction or rewiring process, and another in which only a subset of nodes participates. Our findings demonstrate substantial improvements in robustness when augmentation strategies are used over the default XRP Ledger topology and show that some augmentation strategies achieve robustness metrics equal to or exceeding the rewiring strategy, even when the number of edges added is small (e.g., three edges per node). Additionally, we show that the random K-out-based augmentation strategy maintains higher topological similarity to the original network than rewiring, as measured by Jaccard similarity.

0.20

Exploring Adaptive Byzantine Quorum Systems to Improve Latency in the WAN

cs.DC ·2026-09-30 ·Linus Gnan, Rüdiger Kapitza, Christian Berger
published similarity 0.65
Abstract · Accepted at LADC 2026, the 15th Latin-American Symposium on Dependable and Secure Computing. 15 Pages

Quorum systems enforce strict consistency in Byzantine fault-tolerant (BFT) state machine replication: Before a value is decided, a subset of replicas (called quorum) must exchange votes for the value. In wide-area networks, the size and composition of a quorum determines the speed at which replicas can make progress and thus impacts the latency perceived by clients. A variety of quorum constructions has been proposed, e.g., threshold, weighted, grid and others, but the literature offers little in the way of an apples-to-apples comparison. Each construction typically lives inside a different protocol implementation, so the influence of quorum design on client latency cannot be easily separated from other implementation effects, especially the use of optimization techniques. In this paper, we close that gap by extending BFT-SMaRt with a modular quorum-system abstraction that allows a variety of quorum constructions to live inside the same framework and interact with the same set of optimization techniques. Via our framework, we explore the impact of different quorum system constructions on client-observed latency in wide-area BFT replication using network simulation.

0.20

STAKE: Preventing a colluding majority from double spending

cs.GT ·2026-10-01 ·Zahra Naderi, Vincent Gramoli
similarity 0.64
Abstract

Blockchains typically operate in open networks where it is hard to control the delay of messages. While classic blockchain protocols assumed synchrony, newer protocols try to remain secure despite unexpected network delays. Unfortunately, in the traditional model where $n$ participants can either be honest or Byzantine, we need a supermajority, or $\lfloor 2n/3\rfloor + 1$, of them to be honest. Recent work have explored the question of reducing the number of needed honest nodes in a game theory model to a majority sometimes by introducing $k$ rational players and $t$ Byzantine players. Yet, to our knowledge, no blockchain protocol managed to reduce it further. In this paper, we offer a blockchain protocol called Secure and Tolerant Algorithm through ($k,t$)-robust Equilibrium (STAKE) that works with only $\lfloor n/3\rfloor + 1$ honest players. STAKE requires each consensus participant to stake a sufficiently large amount $s$ compared to their liquidity $\ell$. We show that the probability that a coalition manages to execute $ζ$ double spending attacks (we call them a $ζ$-uple attack) drops exponentially fast with $ζ$. This allows us to demonstrate that STAKE reaches a ($k,t$)-robust equilibrium, or that rational players do not collude with Byzantine, even with a relatively low $s/\ell$ ratio.

0.12

Fortress: Fork Resistant Transparency logs Relying on Social graph Structure

cs.CR ·2026-10-19 ·Anastasiia Kucherenko, Melissa Chase, Esha Ghosh
theory similarity 0.63
Abstract

Transparency systems -- such as Key Transparency (KT), Certificate Transparency, and binary transparency -- require that all honest participants see the same view of an untrusted server's directory, or, failing that, that the misbehaviour is publicly detected. Every existing design closes this gap with an external trust anchor: a publicly available bulletin board (BB), a blockchain, or an out-of-band (OOB) gossip network among auditors. We observe that transparency systems already have a built-in resource that has so far been overlooked: the social graph induced by the users themselves. We ask whether it can replace the bulletin board or the external gossip channel entirely, and answer in the affirmative (if occasional out-of-band interactions are allowed). We formalise a new primitive, Social-Graph based Forking-Resilient Transparency (sg-FORT), which captures the security guarantees of a BB-free transparency system and we construct Fortress Fork Resistant Transparency logs Relying on Social graph Structure, to our knowledge the first such protocol. In every epoch either all users output the same post, or at least one honest user produces a publicly verifiable Proof of Misbehaviour. Our guarantees hold against an arbitrary malicious server, including a snapshot adversary that may compromise a user and learn its secret state, as long as the server does not compromise close users. In honest executions, OOB interactions occur only when a user resets their secrets, so the total OOB cost approaches the natural lower bound of one call per reset -- dramatically below the full-gossip alternative. We prove security under standard cryptographic assumptions on signatures and dictionary commitment. Under simplifying assumptions (synchronous epochs, always-online users), we view this as a first feasibility result that opens up the design space of social-graph-based transparency systems.

0.23

Competition, Collusion, and Corruption: The Spectrum of MEV Attacks on DAG-Based BFT Consensus Protocols

cs.CR cs.DC ·2026-09-17 ·Iliya Mirzaei, Heer Patel, Chenyuan Wu, Mohammad Javad Amiri
similarity 0.62
Abstract · 26 pages, 8 figures, 4 tables

Byzantine Fault-Tolerant (BFT) protocols guarantee safety and liveness despite the malicious failure of nodes. However, they do not prevent adversarial manipulation of transaction order, where the order a proposer assigns diverges from the order in which clients submitted their transactions. Exploiting this discretion for profit is known as maximal extractable value (MEV), and it is intensified in DAG-based BFT protocols, where every replica proposes blocks concurrently rather than routing transactions through a single designated proposer each round. The proliferation of MEV attacks on DAG-based BFT protocols has made the resulting landscape difficult to navigate: attacks are reported individually, on different protocols, and under different metrics, making it unclear whether two attacks differ fundamentally or merely in how they are described. This paper closes that gap by presenting an attack space for MEV on DAG-based BFT protocols, organized around four families: the adversary, the protocol, the target, and the deployment. For each family, we identify the dimensions that shape an attack's impact. Each point in the attack space fixes one value per dimension, thereby representing a distinct, potential MEV attack, which can then be instantiated on a specific DAG-based BFT protocol. We perform a set of experiments, each isolating a single dimension where the protocol permits it, to empirically measure its effect on the success rate of MEV attacks against six production DAG-based BFT protocols. Our experimental evaluation reveals that every protocol we evaluate is vulnerable to at least a subset of the MEV attacks in this space, and that which attacks succeed is mostly dictated by the protocol's own design rather than by attacker effort.

0.20

Are Unreachable Nodes Truly Safe? Fully Eclipsing Monero's P2P Network!

cs.CR ·2026-09-09 ·Ruisheng Shi, Jiaqi Zeng, Lina Lan, Shihan Zhang, Bing Han +4 more
top venue similarity 0.62
Abstract · Accepted by ACM CCS'26 (The Hague, The Netherlands)

Eclipse attacks isolate a blockchain node by monopolizing its network connections. Existing attacks on Monero (NDSS'25), Bitcoin (USENIX'15/21, S&P'20) and Ethereum (WWW'26) implicitly assume that the adversary can establish inbound connections, thereby excluding a large and practically dominant class of nodes: \textit{unreachable nodes} operating behind NATs. Such nodes are widely believed to enjoy stronger networks. We challenge this assumption and show that unreachability does NOT imply the expected resilience! We present the first eclipse attacks tailored to unreachable nodes in Monero's P2P network. Our attacks require no inbound access to the victim. Instead, they first poison the peerlist of reachable nodes, which subsequently act as propagation relays to contaminate unreachable nodes' whitelists. The adversary then exploits Monero's built-in outbound connection refresh logic to evict benign neighbors and eventually monopolize all outbound connections. We instantiate this strategy in two attacks: Nyx, which targets long-running unreachable nodes and achieves a complete and persistent eclipse through network-wide poisoning; and Moros, a stealthier attack that exploits the bootstrapping phase to rapidly eclipse newly joined unreachable nodes. We ethically evaluate both attacks. Nyx is validated via large-scale simulations on a Monero network constructed using the SEED Emulator, while Moros is demonstrated on the Monero mainnet against controlled targets. Our results show that unreachable nodes can be reliably driven into stable, long-lived eclipse states. We also propose countermeasures.

0.43