License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.39
URN: urn:nbn:de:0030-drops-148413
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14841/
Go to the corresponding LIPIcs Volume Portal

Su, Lili ; Liu, Quanquan C. ; Narula, Neha

The Power of Random Symmetry-Breaking in Nakamoto Consensus

pdf-format:
LIPIcs-DISC-2021-39.pdf (0.7 MB)

Abstract

Nakamoto consensus underlies the security of many of the world’s largest cryptocurrencies, such as Bitcoin and Ethereum. Common lore is that Nakamoto consensus only achieves consistency and liveness under a regime where the difficulty of its underlying mining puzzle is very high, negatively impacting overall throughput and latency. In this work, we study Nakamoto consensus under a wide range of puzzle difficulties, including very easy puzzles. We first analyze an adversary-free setting and show that, surprisingly, the common prefix of the blockchain grows quickly even with easy puzzles. In a setting with adversaries, we provide a small backwards-compatible change to Nakamoto consensus to achieve consistency and liveness with easy puzzles. Our insight relies on a careful choice of symmetry-breaking strategy, which was significantly underestimated in prior work. We introduce a new method - coalescing random walks - to analyzing the correctness of Nakamoto consensus under the uniformly-at-random symmetry-breaking strategy. This method is more powerful than existing analysis methods that focus on bounding the number of convergence opportunities.

BibTeX - Entry

@InProceedings{su_et_al:LIPIcs.DISC.2021.39,
  author =	{Su, Lili and Liu, Quanquan C. and Narula, Neha},
  title =	{{The Power of Random Symmetry-Breaking in Nakamoto Consensus}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{39:1--39:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14841},
  URN =		{urn:nbn:de:0030-drops-148413},
  doi =		{10.4230/LIPIcs.DISC.2021.39},
  annote =	{Keywords: Nakamoto consensus, Byzantine consensus, blockchain, symmetry-breaking, coalescing random walks}
}

Keywords: Nakamoto consensus, Byzantine consensus, blockchain, symmetry-breaking, coalescing random walks
Collection: 35th International Symposium on Distributed Computing (DISC 2021)
Issue Date: 2021
Date of publication: 04.10.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI