LIPIcs.OPODIS.2020.11.pdf
- Filesize: 466 kB
- 16 pages
Document
Information Theoretic HotStuff
Authors
-
Part of:
Volume:
24th International Conference on Principles of Distributed Systems (OPODIS 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Principles of Distributed Systems (OPODIS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2021-01-25
Cite As Get BibTex
Ittai Abraham and Gilad Stern. Information Theoretic HotStuff. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.OPODIS.2020.11
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed algorithms
Keywords
- byzantine agreement
- partial synchrony
- bounded space
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. Asymptotically optimal validated asynchronous byzantine agreement. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC ’19, page 337–346, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3293611.3331612.
- Charles H. Bennett, François Bessette, Gilles Brassard, Louis Salvail, and John Smolin. Experimental quantum cryptography. Journal of Cryptology, 5(1):3-28, January 1992. URL: https://doi.org/10.1007/BF00191318.
- Gabriel Bracha. Asynchronous byzantine agreement protocols. Inf. Comput., 75(2):130-143, November 1987. URL: https://doi.org/10.1016/0890-5401(87)90054-X.
- Ethan Buchman. Tendermint: Byzantine fault tolerance in the age of blockchains. http://knowen-production.s3.amazonaws.com/uploads/attachment/file/1814/Buchman_Ethan_201606_Msater%2Bthesis.pdf, 2016.
- Ethan Buchman, Jae Kwon, and Zarko Milosevic. The latest gossip on bft consensus, 2018. URL: http://arxiv.org/abs/1807.04938.
- Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget, 2017. URL: http://arxiv.org/abs/1710.09437.
- Christian Cachin. Yet another visit to paxos. https://cachin.com/cc/papers/pax.pdf, 2010.
-
Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. In Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, CRYPTO ’01, page 524–541, Berlin, Heidelberg, 2001. Springer-Verlag.
- Miguel Castro. Practical byzantine fault tolerance. https://www.microsoft.com/en-us/research/wp-content/uploads/2017/01/thesis-mcastro.pdf, 2001.
- Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance and proactive recovery. ACM Trans. Comput. Syst., 20(4):398–461, November 2002. URL: https://doi.org/10.1145/571637.571640.
-
Miguel Castro, Barbara Liskov, et al. Practical byzantine fault tolerance. In OSDI, volume 99, pages 173-186, 1999.
- Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. J. ACM, 35(2):288–323, April 1988. URL: https://doi.org/10.1145/42282.42283.
- Rati Gelashvili. On the optimal space complexity of consensus for anonymous processes, 2015. URL: http://arxiv.org/abs/1506.06817.
- Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. Sbft: a scalable and decentralized trust infrastructure, 2018. URL: http://arxiv.org/abs/1804.01626.
- Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva: Speculative byzantine fault tolerance. SIGOPS Oper. Syst. Rev., 41(6):45–58, October 2007. URL: https://doi.org/10.1145/1323293.1294267.
-
Leslie Lamport et al. Paxos made simple. ACM Sigact News, 32(4):18-25, 2001.
- Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Comput. Surv., 22(4):299–319, December 1990. URL: https://doi.org/10.1145/98163.98167.
- Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. Hotstuff: Bft consensus with linearity and responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, page 347–356, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3293611.3331591.