Paper 2020/277

Full Analysis of Nakamoto Consensus in Bounded-Delay Networks

Juan Garay, Aggelos Kiayias, and Nikos Leonardos

Abstract

Nakamoto consensus, arguably the most exciting development in distributed computing in the last few years, is in a sense a recast- ing of the traditional state-machine-replication problem in an unauthenticated setting, where furthermore parties come and go without warning. The protocol relies on a cryptographic primitive known as proof of work (PoW) which is used to throttle message passing with the PoW difficulty level being appropriately adjusted throughout the course of the protocol execution. While the original formulation was only accompanied by rudimentary analysis, significant and steady progress has been made in abstracting the protocol’s properties and providing a formal analysis under various restrictions and protocol simplifications. Still, a full analysis of the protocol that includes its target recalculation and timestamp adjustment mechanisms which equip it to operate in its intended setting of bounded communication delays, imperfect clocks and dynamic participation, has remained open. This paper’s main result fills this gap presenting a proof that Nakamoto’s protocol achieves, under suitable conditions, consistency and liveness in the above setting. A number of technical tools and techniques are introduced that may be of independent interest in the analysis of blockchain protocols.

Note: This version significantly extends the analysis to include clock adjustment and blockchain timestamp validation mechanisms consistent with Nakamoto's implementation.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
bitcoin
Contact author(s)
nikos leonardos @ gmail com
akiayias @ inf ed ac uk
juan a garay @ gmail com
History
2021-10-05: last of 3 revisions
2020-03-04: received
See all versions
Short URL
https://ia.cr/2020/277
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/277,
      author = {Juan Garay and Aggelos Kiayias and Nikos Leonardos},
      title = {Full Analysis of Nakamoto Consensus in Bounded-Delay Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2020/277},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/277}},
      url = {https://eprint.iacr.org/2020/277}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.