Everything is a Race and Nakamoto Always Wins

Amir Dembo, Sreeram Kannan, Ertem Nusret Tas, David Tse, Pramod Viswanath, Xuechao Wang, Ofer Zeitouni

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

10 Scopus citations

Abstract

Nakamoto invented the longest chain protocol, and claimed its security by analyzing the private double-spend attack, a race between the adversary and the honest nodes to grow a longer chain. But is it the worst attack? We answer the question in the affirmative for three classes of longest chain protocols, designed for different consensus models: 1) Nakamoto's original Proof-of-Work protocol; 2) Ouroboros and SnowWhite Proof-of-Stake protocols; 3) Chia Proof-of-Space protocol. As a consequence, exact characterization of the maximum tolerable adversary power is obtained for each protocol as a function of the average block time normalized by the network delay. The security analysis of these protocols is performed in a unified manner by a novel method of reducing all attacks to a race between the adversary and the honest nodes.

Original languageEnglish (US)
Title of host publicationCCS 2020 - Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Pages859-878
Number of pages20
ISBN (Electronic)9781450370899
DOIs
StatePublished - Oct 30 2020
Externally publishedYes
Event27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020 - Virtual, Online, United States
Duration: Nov 9 2020Nov 13 2020

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Conference

Conference27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020
Country/TerritoryUnited States
CityVirtual, Online
Period11/9/2011/13/20

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications

Keywords

  • proof-of-space
  • proof-of-stake
  • proof-of-work
  • security analysis

Cite this