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.2023.31
URN: urn:nbn:de:0030-drops-191579
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19157/
Go to the corresponding LIPIcs Volume Portal

Pu, Youer ; Farahbakhsh, Ali ; Alvisi, Lorenzo ; Eyal, Ittay

Gorilla: Safe Permissionless Byzantine Consensus

pdf-format:
LIPIcs-DISC-2023-31.pdf (0.8 MB)

Abstract

Nakamoto’s consensus protocol works in a permissionless model and tolerates Byzantine failures, but only offers probabilistic agreement. Recently, the Sandglass protocol has shown such weaker guarantees are not a necessary consequence of a permissionless model; yet, Sandglass only tolerates benign failures, and operates in an unconventional partially synchronous model. We present Gorilla Sandglass, the first Byzantine tolerant consensus protocol to guarantee, in the same synchronous model adopted by Nakamoto, deterministic agreement and termination with probability 1 in a permissionless setting. We prove the correctness of Gorilla by mapping executions that would violate agreement or termination in Gorilla to executions in Sandglass, where we know such violations are impossible. Establishing termination proves particularly interesting, as the mapping requires reasoning about infinite executions and their probabilities.

BibTeX - Entry

@InProceedings{pu_et_al:LIPIcs.DISC.2023.31,
  author =	{Pu, Youer and Farahbakhsh, Ali and Alvisi, Lorenzo and Eyal, Ittay},
  title =	{{Gorilla: Safe Permissionless Byzantine Consensus}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19157},
  URN =		{urn:nbn:de:0030-drops-191579},
  doi =		{10.4230/LIPIcs.DISC.2023.31},
  annote =	{Keywords: Consensus, Permissionless, Blockchains, Byzantine fault tolerance, Deterministic Safety}
}

Keywords: Consensus, Permissionless, Blockchains, Byzantine fault tolerance, Deterministic Safety
Collection: 37th International Symposium on Distributed Computing (DISC 2023)
Issue Date: 2023
Date of publication: 05.10.2023

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