LIPIcs.DISC.2021.51.pdf
- Filesize: 0.52 MB
- 4 pages
Document
Brief Announcement: Revisiting Signature-Free Asynchronous Byzantine Consensus
Authors
-
Part of:
Volume:
35th International Symposium on Distributed Computing (DISC 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-10-04
Cite AsGet BibTex
Christian Cachin and Luca Zanolini. Brief Announcement: Revisiting Signature-Free Asynchronous Byzantine Consensus. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 51:1-51:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.DISC.2021.51
https://doi.org/10.4230/LIPIcs.DISC.2021.51
Abstract
Among asynchronous, randomized, and signature-free implementations of consensus, the protocols of Mostéfaoui et al. (PODC 2014 and JACM 2015) represent a landmark result, which has been extended later and taken up in practical systems. The protocols achieve optimal resilience and take, in expectation, only a constant expected number of rounds and have quadratic message complexity. Randomization is provided through a common-coin primitive. However, the first version of this simple and appealing protocol suffers from a little-known liveness issue due to asynchrony. The JACM 2015 version avoids the problem, but is considerably more complex.
This work revisits the original protocol of PODC 2014 and points out in detail why it may not progress. A fix for the protocol is presented, which does not affect any of its properties, but lets it regain the original simplicity in asynchronous networks enhanced with a common-coin protocol.
Subject Classification
ACM Subject Classification
- Theory of computation → Cryptographic protocols
- Software and its engineering → Distributed systems organizing principles
Keywords
- Randomized consensus
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Christian Cachin, Rachid Guerraoui, and Luís E. T. Rodrigues. Introduction to Reliable and Secure Distributed Programming (2. ed.). Springer, 2011.
- Christian Cachin and Luca Zanolini. From symmetric to asymmetric asynchronous byzantine consensus. CoRR, abs/2005.08795v3, 2021. URL: http://arxiv.org/abs/2005.08795v3.
-
Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of BFT protocols. In Proc. ACM CCS, pages 31-42, 2016.
-
Achour Mostéfaoui, Moumen Hamouma, and Michel Raynal. Signature-free asynchronous byzantine consensus with t < n/3 and O(n²) messages. In Proc. PODC, pages 2-9, 2014.
-
Achour Mostéfaoui, Hamouma Moumen, and Michel Raynal. Signature-free asynchronous binary byzantine consensus with t < n/3, O(n²) messages, and O(1) expected time. J. ACM, 62(4):31:1-31:21, 2015.
-
Michael O. Rabin. Randomized byzantine generals. In Proc. FOCS, pages 403-409, 1983.
-
Pierre Tholoniat and Vincent Gramoli. Formal verification of blockchain byzantine fault tolerance. In 6th Workshop on Formal Reasoning in Distributed Algorithms (FRIDA'19), 2019.