Everything is a Race and Nakamoto Always Wins

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

doi:10.1145/3372297.3417290

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 proceeding › Conference contribution

21 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 language	English (US)
Title of host publication	CCS 2020 - Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security
Publisher	Association for Computing Machinery
Pages	859-878
Number of pages	20
ISBN (Electronic)	9781450370899
DOIs	https://doi.org/10.1145/3372297.3417290
State	Published - Oct 30 2020
Externally published	Yes
Event	27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020 - Virtual, Online, United States Duration: Nov 9 2020 → Nov 13 2020

Publication series

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

Conference

Conference	27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020
Country/Territory	United States
City	Virtual, Online
Period	11/9/20 → 11/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

Access to Document

10.1145/3372297.3417290

Cite this

Dembo, A., Kannan, S., Tas, E. N., Tse, D., Viswanath, P., Wang, X., & Zeitouni, O. (2020). Everything is a Race and Nakamoto Always Wins. In CCS 2020 - Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (pp. 859-878). (Proceedings of the ACM Conference on Computer and Communications Security). Association for Computing Machinery. https://doi.org/10.1145/3372297.3417290

@inproceedings{3a5f282bbdd44deca0815bce44fc85c1,

title = "Everything is a Race and Nakamoto Always Wins",

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.",

keywords = "proof-of-space, proof-of-stake, proof-of-work, security analysis",

author = "Amir Dembo and Sreeram Kannan and Tas, {Ertem Nusret} and David Tse and Pramod Viswanath and Xuechao Wang and Ofer Zeitouni",

note = "Funding Information: Amir Dembo and Ofer Zeitouni were partially supported by a US-Israel BSF grant. Ertem Nusret Tas was supported in part by the Stanford Center for Blockchain Research. This research is also supported in part by NSF under grants CCF-1705007, DMS-1954337, 1651236 and Army Research Office under grant W911NF-14-1-0220. We thank the reviewers for the helpful comments. Publisher Copyright: {\textcopyright} 2020 ACM.; 27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020 ; Conference date: 09-11-2020 Through 13-11-2020",

year = "2020",

month = oct,

day = "30",

doi = "10.1145/3372297.3417290",

language = "English (US)",

series = "Proceedings of the ACM Conference on Computer and Communications Security",

publisher = "Association for Computing Machinery",

pages = "859--878",

booktitle = "CCS 2020 - Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security",

}

Dembo, A, Kannan, S, Tas, EN, Tse, D, Viswanath, P, Wang, X & Zeitouni, O 2020, Everything is a Race and Nakamoto Always Wins. in CCS 2020 - Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. Proceedings of the ACM Conference on Computer and Communications Security, Association for Computing Machinery, pp. 859-878, 27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020, Virtual, Online, United States, 11/9/20. https://doi.org/10.1145/3372297.3417290

Everything is a Race and Nakamoto Always Wins. / Dembo, Amir; Kannan, Sreeram; Tas, Ertem Nusret et al.
CCS 2020 - Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, 2020. p. 859-878 (Proceedings of the ACM Conference on Computer and Communications Security).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Everything is a Race and Nakamoto Always Wins

AU - Dembo, Amir

AU - Kannan, Sreeram

AU - Tas, Ertem Nusret

AU - Tse, David

AU - Viswanath, Pramod

AU - Wang, Xuechao

AU - Zeitouni, Ofer

N1 - Funding Information: Amir Dembo and Ofer Zeitouni were partially supported by a US-Israel BSF grant. Ertem Nusret Tas was supported in part by the Stanford Center for Blockchain Research. This research is also supported in part by NSF under grants CCF-1705007, DMS-1954337, 1651236 and Army Research Office under grant W911NF-14-1-0220. We thank the reviewers for the helpful comments. Publisher Copyright: © 2020 ACM.

PY - 2020/10/30

Y1 - 2020/10/30

N2 - 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.

AB - 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.

KW - proof-of-space

KW - proof-of-stake

KW - proof-of-work

KW - security analysis

UR - http://www.scopus.com/inward/record.url?scp=85096184495&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85096184495&partnerID=8YFLogxK

U2 - 10.1145/3372297.3417290

DO - 10.1145/3372297.3417290

M3 - Conference contribution

AN - SCOPUS:85096184495

T3 - Proceedings of the ACM Conference on Computer and Communications Security

SP - 859

EP - 878

BT - CCS 2020 - Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security

PB - Association for Computing Machinery

T2 - 27th ACM SIGSAC Conference on Computer and Communications Security, CCS 2020

Y2 - 9 November 2020 through 13 November 2020

ER -

Everything is a Race and Nakamoto Always Wins

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Cite this