The Generals’ Scuttlebutt: Byzantine-Resilient Gossip Protocols

Sandro Coretti, Aggelos Kiayias, Alexander Russell, Cristopher Moore

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 barebone point-to-point networking, majority of honest stake, and a verifiable random function.
Original languageEnglish
Title of host publicationProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery (ACM)
Pages595-608
Number of pages14
ISBN (Electronic)978-1-4503-9450-5
DOIs
Publication statusPublished - 7 Nov 2022
EventThe 29th ACM Conference on Computer and Communications Security - Los Angeles, United States
Duration: 7 Nov 202211 Nov 2022
Conference number: 29
https://www.sigsac.org/ccs/CCS2022/home.html

Conference

ConferenceThe 29th ACM Conference on Computer and Communications Security
Abbreviated titleCCS 2022
Country/TerritoryUnited States
CityLos Angeles
Period7/11/2211/11/22
Internet address

Keywords

  • proof of stake
  • gossiping
  • Byzantine-resilience

Fingerprint

Dive into the research topics of 'The Generals’ Scuttlebutt: Byzantine-Resilient Gossip Protocols'. Together they form a unique fingerprint.

Cite this