License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2020.11
URN: urn:nbn:de:0030-drops-134969
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13496/
Go to the corresponding LIPIcs Volume Portal

Abraham, Ittai ; Stern, Gilad

Information Theoretic HotStuff

pdf-format:
LIPIcs-OPODIS-2020-11.pdf (0.5 MB)

Abstract

This work presents Information Theoretic HotStuff (IT-HS), a new optimally resilient protocol for solving Byzantine Agreement in partial synchrony with information theoretic security guarantees. In particular, IT-HS does not depend on any PKI or common setup assumptions and is resilient to computationally unbounded adversaries. IT-HS is based on the Primary-Backup view-based paradigm. In IT-HS, in each view, and in each view change, each party sends only a constant number of words to every other party. This yields an O(n²) word and message complexity in each view. In addition, IT-HS requires just O(1) persistent local storage and O(n) transient local storage. Finally, like all Primary-Backup view-based protocols in partial synchrony, after the system becomes synchronous, all nonfaulty parties decide on a value in the first view a nonfaulty leader is chosen. Moreover, like PBFT and HotStuff, IT-HS is optimistically responsive: with a nonfaulty leader, parties decide as quickly as the network allows them to do so, without regard for the known upper bound on network delay. Our work improves in multiple dimensions upon the information theoretic version of PBFT presented by Miguel Castro, and can be seen as an information theoretic variant of the HotStuff paradigm.

BibTeX - Entry

@InProceedings{abraham_et_al:LIPIcs:2021:13496,
  author =	{Ittai Abraham and Gilad Stern},
  title =	{{Information Theoretic HotStuff}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Quentin Bramas and Rotem Oshman and Paolo Romano},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13496},
  URN =		{urn:nbn:de:0030-drops-134969},
  doi =		{10.4230/LIPIcs.OPODIS.2020.11},
  annote =	{Keywords: byzantine agreement, partial synchrony, bounded space}
}

Keywords: byzantine agreement, partial synchrony, bounded space
Collection: 24th International Conference on Principles of Distributed Systems (OPODIS 2020)
Issue Date: 2021
Date of publication: 25.01.2021

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