Paper 2020/601

Everything is a Race and Nakamoto Always Wins

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

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.

Note: A shorter version of this paper will appear in the 2020 ACM Conference on Computer and Communications Security (CCS).

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Arxiv
Keywords
Blockchain
Contact author(s)
nusret @ stanford edu
History
2020-08-30: last of 3 revisions
2020-05-22: received
See all versions
Short URL
https://ia.cr/2020/601
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/601,
      author = {Amir Dembo and Sreeram Kannan and Ertem Nusret Tas and David Tse and Pramod Viswanath and Xuechao Wang and Ofer Zeitouni},
      title = {Everything is a Race and Nakamoto Always Wins},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/601},
      year = {2020},
      url = {https://eprint.iacr.org/2020/601}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.