DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2023.31

Gorilla: Safe Permissionless Byzantine Consensus

Authors: Youer Pu, Ali Farahbakhsh, Lorenzo Alvisi, and Ittay Eyal

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

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.

Cite as

Youer Pu, Ali Farahbakhsh, Lorenzo Alvisi, and Ittay Eyal. Gorilla: Safe Permissionless Byzantine Consensus. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.DISC.2023.31},
  URN =		{urn:nbn:de:0030-drops-191579},
  doi =		{10.4230/LIPIcs.DISC.2023.31},
  annote =	{Keywords: Consensus, Permissionless, Blockchains, Byzantine fault tolerance, Deterministic Safety}
}

Document

DOI: 10.4230/LIPIcs.DISC.2022.33

Safe Permissionless Consensus

Authors: Youer Pu, Lorenzo Alvisi, and Ittay Eyal

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

Nakamoto’s consensus protocol works in a permissionless model, where nodes can join and leave without notice. However, it guarantees agreement only probabilistically. Is this weaker guarantee a necessary concession to the severe demands of supporting a permissionless model? This paper shows that, at least in a benign failure model, it is not. It presents Sandglass, the first permissionless consensus algorithm that guarantees deterministic agreement and termination with probability 1 under general omission failures. Like Nakamoto, Sandglass adopts a hybrid synchronous communication model, where, at all times, a majority of nodes (though their number is unknown) are correct and synchronously connected, and allows nodes to join and leave at any time.

Cite as

Youer Pu, Lorenzo Alvisi, and Ittay Eyal. Safe Permissionless Consensus. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{pu_et_al:LIPIcs.DISC.2022.33,
  author =	{Pu, Youer and Alvisi, Lorenzo and Eyal, Ittay},
  title =	{{Safe Permissionless Consensus}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.33},
  URN =		{urn:nbn:de:0030-drops-172246},
  doi =		{10.4230/LIPIcs.DISC.2022.33},
  annote =	{Keywords: Consensus, Permissionless, Nakamoto, Deterministic Safety}
}

Search Results

Documents authored by Pu, Youer

Gorilla: Safe Permissionless Byzantine Consensus

Abstract

Cite as

Safe Permissionless Consensus

Abstract

Cite as

Thanks for your feedback!

Could not send message