Everything is a Race and Nakamoto Always Wins
Amir Demboa b, Sreeram Kannanc d, Ertem Nusret Tasa b, David N. C. Tsea b, Pramod Viswanathe f, Xuechao Wange f, Ofer Zeitounig h
- aStanford University, Stanford, CA, USA
- bStanford Univ., Stanford, CA (USA)
- cUniversity of Washington, Seattle, WA, USA
- dUniv. of Washington, Seattle, WA, USA
- eUniversity of Illinois at Urbana-Champaign, Champaign, IL, USA
- fUniversity of Illinois at Urbana Champaign , Champaign , IL , USA
- gWeizmann Institute of Science, Rehovot, Israel
- hWeizmann Institute of Science , Rehovot , Israel
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
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.