Cryptology ePrint Archive: Report 2020/601

Everything is a Race and Nakamoto Always Wins

Amir Dembo and Sreeram Kannan and Ertem Nusret Tas and David Tse and Pramod Viswanath and 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.

Category / Keywords: applications / Blockchain

Original Publication (in the same form): Arvix

Date: received 21 May 2020

Contact author: nusret at stanford edu

Available format(s): PDF | BibTeX Citation

Version: 20200522:151824 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]