DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2021.39

The Power of Random Symmetry-Breaking in Nakamoto Consensus

Authors: Lili Su, Quanquan C. Liu, and Neha Narula

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

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.

Cite as

Lili Su, Quanquan C. Liu, and Neha Narula. The Power of Random Symmetry-Breaking in Nakamoto Consensus. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.DISC.2021.39},
  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}
}

Search Results

Documents authored by Narula, Neha

The Power of Random Symmetry-Breaking in Nakamoto Consensus

Abstract

Cite as

Thanks for your feedback!

Could not send message