Paper 2022/541

The Generals’ Scuttlebutt: Byzantine-Resilient Gossip Protocols

Sandro Coretti, IOG
Aggelos Kiayias, University of Edinburgh, IOG
Cristopher Moore, Santa Fe Institute
Alexander Russell, University of Connecticut, IOG

One of the most successful applications of peer-to-peer communication networks is in the context of blockchain protocols, which—in Satoshi Nakamoto's own words—rely on the "nature of information being easy to spread and hard to stifle." Significant efforts were invested in the last decade into analyzing the security of these protocols, and invariably the security arguments known for longest-chain Nakamoto-style consensus use an idealization of this tenet. Unfortunately, the real-world implementations of peer-to-peer gossip-style networks used by blockchain protocols rely on a number of ad-hoc attack mitigation strategies that leave a glaring gap between the idealized communication layer assumed in formal security arguments for blockchains and the real world, where a wide array of attacks have been showcased. In this work we bridge this gap by presenting a Byzantine-resilient network layer for blockchain protocols. For the first time we quantify the problem of network-layer attacks in the context of blockchain security models, and we develop a design that thwarts resource restricted adversaries. Importantly, we focus on the proof-of-stake setting due to its vulnerability to Denial-of-Service (DoS) attacks stemming from the well-known deficiency (compared to the proof-of-work setting) known as nothing at stake. We present a Byzantine-resilient gossip protocol, and we analyze it in the Universal Composition framework. In order to prove security, we show novel results on expander properties of random graphs. Importantly, our gossip protocol can be based on any given bilateral functionality that determines a desired interaction between two "adjacent" peers in the networking layer and demonstrates how it is possible to use application-layer information to make the networking-layer resilient to attacks. Despite the seeming circularity, we demonstrate how to prove the security of a Nakamoto-style longest-chain protocol given our gossip networking functionality, and hence, we demonstrate constructively how it is possible to obtain provable security across protocol layers, given only bare-bone point-to-point networking, majority of honest stake, and a verifiable random function.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM SIGSAC Conference on Computer and Communications Security (CCS ’22)
proof of stake blockchains gossiping Byzantine-resilience expander graphs universal composability
Contact author(s)
sandro coretti @ iohk io
Aggelos Kiayias @ ed ac uk
moore @ santafe edu
acr @ uconn edu
2022-11-03: last of 3 revisions
2022-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sandro Coretti and Aggelos Kiayias and Cristopher Moore and Alexander Russell},
      title = {The Generals’ Scuttlebutt: Byzantine-Resilient Gossip Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2022/541},
      year = {2022},
      doi = {10.1145/3548606.3560638},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.