Document Open Access Logo

Oracular Byzantine Reliable Broadcast

Authors Martina Camaioni, Rachid Guerraoui, Matteo Monti, Manuel Vidigueira

PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.13.pdf
  • Filesize: 1.1 MB
  • 19 pages

Document Identifiers

Author Details

Martina Camaioni
  • Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Rachid Guerraoui
  • Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Matteo Monti
  • Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Manuel Vidigueira
  • Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland

Cite As Get BibTex

Martina Camaioni, Rachid Guerraoui, Matteo Monti, and Manuel Vidigueira. Oracular Byzantine Reliable Broadcast. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.DISC.2022.13

Abstract

Byzantine Reliable Broadcast (BRB) is a fundamental distributed computing primitive, with applications ranging from notifications to asynchronous payment systems. Motivated by practical consideration, we study Client-Server Byzantine Reliable Broadcast (CSB), a multi-shot variant of BRB whose interface is split between broadcasting clients and delivering servers. We present Draft, an optimally resilient implementation of CSB. Like most implementations of BRB, Draft guarantees both liveness and safety in an asynchronous environment. Under good conditions, however, Draft achieves unparalleled efficiency. In a moment of synchrony, free from Byzantine misbehaviour, and at the limit of infinitely many broadcasting clients, a Draft server delivers a b-bits payload at an asymptotic amortized cost of 0 signature verifications, and (log₂(c) + b) bits exchanged, where c is the number of clients in the system. This is the information-theoretical minimum number of bits required to convey the payload (b bits, assuming it is compressed), along with an identifier for its sender (log₂(c) bits, necessary to enumerate any set of c elements, and optimal if broadcasting frequencies are uniform or unknown). These two achievements have profound practical implications. Real-world BRB implementations are often bottlenecked either by expensive signature verifications, or by communication overhead. For Draft, instead, the network is the limit: a server can deliver payloads as quickly as it would receive them from an infallible oracle.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Byzantine reliable broadcast
  • Good-case complexity
  • Amortized complexity
  • Batching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

  • The full version of this paper, which includes all detailed proofs and pseudocode, is available online.
  • Full Version https://arxiv.org/abs/

References

  1. Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. Good-Case Latency of Byzantine Broadcast: A Complete Categorization. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC'21, pages 331-341, New York, NY, USA, 2021. Association for Computing Machinery. Google Scholar
  2. Nicolas Alhaddad, Sisi Duan, Mayank Varia, and Haibin Zhang. Succinct erasure coding proof systems. Cryptology ePrint Archive, 2021. Google Scholar
  3. Elli Androulaki, Artem Barger, Vita Bortnikov, Christian Cachin, Konstantinos Christidis, Angelo De Caro, David Enyeart, Christopher Ferris, Gennady Laventman, Yacov Manevich, Srinivasan Muralidharan, Chet Murthy, Binh Nguyen, Manish Sethi, Gari Singh, Keith Smith, Alessandro Sorniotti, Chrysoula Stathakopoulou, Marko Vukolić, Sharon Weed Cocco, and Jason Yellick. Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains. In Proceedings of the Thirteenth EuroSys Conference, EuroSys '18, New York, NY, USA, 2018. Association for Computing Machinery. Google Scholar
  4. Alex Auvolat, Davide Frey, Michel Raynal, and François Taïani. Byzantine-tolerant causal broadcast. Theoretical Computer Science, 885:55-68, 2021. Google Scholar
  5. Paulo S. L. M. Barreto, Hae Y. Kim, Ben Lynn, and Michael Scott. Efficient algorithms for pairing-based cryptosystems. In Moti Yung, editor, Advances in Cryptology - CRYPTO 2002, pages 354-369, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. Google Scholar
  6. Michael Ben-Or, Ran Canetti, and Oded Goldreich. Asynchronous secure computation. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 52-61, 1993. Google Scholar
  7. Joseph T.A. Birman K.P. Reliable communication in the presence of failures. ACM Transactions on Computer Systems, 5(1):47-76, 1987. Google Scholar
  8. Gabriel Bracha. An asynchronous [(n-1)/3]-resilient consensus protocol. In Proceedings of the third annual ACM symposium on Principles of distributed computing, pages 154-162, 1984. Google Scholar
  9. Gabriel Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75(2):130-143, 1987. Google Scholar
  10. Gabriel Bracha and Sam Toueg. Asynchronous Consensus and Broadcast Protocols. JACM, 32(4), 1985. Google Scholar
  11. Christian Cachin. State machine replication with byzantine faults. In Replication, pages 169-184. Springer, 2010. Google Scholar
  12. Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to reliable and secure distributed programming. Springer Science & Business Media, 2011. Google Scholar
  13. Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. In Annual International Cryptology Conference, pages 524-541. Springer, 2001. Google Scholar
  14. Christian Cachin and Jonathan A. Poritz. Secure Intrusion-tolerant Replication on the Internet. In DSN, 2002. Google Scholar
  15. Christian Cachin and Jonathan A Poritz. Secure intrusion-tolerant replication on the internet. In Proceedings International Conference on Dependable Systems and Networks, pages 167-176. IEEE, 2002. Google Scholar
  16. Christian Cachin and Stefano Tessaro. Asynchronous Verifiable Information Dispersal. In Proceedings of the 24th Symposium on Reliable Distributed Systems - SRDS 2005, pages 191-202, October 2005. Google Scholar
  17. Martina Camaioni, Rachid Guerraoui, Matteo Monti, and Manuel Vidigueira. Oracular Byzantine Reliable Broadcast (Extended Version), 2022. Google Scholar
  18. Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems (TOCS), 20(4):398-461, 2002. Google Scholar
  19. Daniel Collins, Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, Andrei Tonkikh, and Athanasios Xygkis. Online payments by merely broadcasting messages. In 2020 50th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 26-38, 2020. URL: https://doi.org/10.1109/DSN48063.2020.00023.
  20. Thomas Cover and Joy Thomas. Elements of Information Theory, Second Edition. John Wiley & Sons, 2005. Google Scholar
  21. Tyler Crain, Christopher Natoli, and Vincent Gramoli. Evaluating the Red Belly Blockchain. CoRR, 2018. Google Scholar
  22. Tyler Crain, Christopher Natoli, and Vincent Gramoli. Red belly: A secure, fair and scalable open blockchain. In 2021 IEEE Symposium on Security and Privacy (SP), pages 466-483. IEEE, 2021. Google Scholar
  23. George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. Narwhal and tusk: a dag-based mempool and efficient bft consensus. In Proceedings of the Seventeenth European Conference on Computer Systems, pages 34-50, 2022. Google Scholar
  24. Sourav Das, Zhuolun Xiang, and Ling Ren. Asynchronous data dissemination and its applications. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pages 2705-2721, 2021. Google Scholar
  25. Haitz Sáez de Ocáriz Borde. An overview of trees in blockchain technology: Merkle trees and merkle patricia tries, 2022. Google Scholar
  26. Xavier Défago, André Schiper, and Péter Urbán. Total Order Broadcast and Multicast Algorithms: Taxonomy and Survey. ACM Comput. Surv., 36(4):372-421, December 2004. Google Scholar
  27. Danny Dolev and Rüdiger Reischuk. Bounds on Information Exchange for Byzantine Agreement. J. ACM, 32(1):191-204, January 1985. Google Scholar
  28. Sisi Duan, Michael K. Reiter, and Haibin Zhang. BEAT: Asynchronous BFT Made Practical. In CCS, 2018. Google Scholar
  29. Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos Seredinschi. The Consensus Number of a Cryptocurrency. In PODC, 2019. Google Scholar
  30. James Hendricks, Gregory R Ganger, and Michael K Reiter. Verifying distributed erasure-coded data. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, pages 139-146, 2007. Google Scholar
  31. Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. All you need is dag. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pages 165-175, 2021. Google Scholar
  32. Klaus Kursawe and Victor Shoup. Optimistic asynchronous atomic broadcast. In International Colloquium on Automata, Languages, and Programming, pages 204-215. Springer, 2005. Google Scholar
  33. Petr Kuznetsov, Yvonne-Anne Pignolet, Pavel Ponomarev, and Andrei Tonkikh. Permissionless and asynchronous asset transfer. In 35th International Symposium on Distributed Computing (DISC 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  34. D. Malkhi, M. Merritt, and O. Rodeh. Secure reliable multicast protocols in a wan. In Proceedings of 17th International Conference on Distributed Computing Systems, pages 87-94, 1997. Google Scholar
  35. Dahlia Malkhi and Michael Reiter. A High-Throughput Secure Reliable Multicast Protocol. Journal of Computer Security, 5:113-127, 1996. Google Scholar
  36. Dahlia Malkhi and Michael Reiter. A high-throughput secure reliable multicast protocol. Journal of Computer Security, 5(2):113-127, 1997. Google Scholar
  37. Ralph C Merkle. A digital signature based on a conventional encryption function. In Conference on the theory and application of cryptographic techniques, pages 369-378. Springer, 1987. Google Scholar
  38. Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of bft protocols. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 31-42, 2016. Google Scholar
  39. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. Decentralized Business Review, page 21260, 2008. Google Scholar
  40. Kartik Nayak, Ling Ren, Elaine Shi, Nitin H Vaidya, and Zhuolun Xiang. Improved extension protocols for byzantine broadcast and agreement. In 34th International Symposium on Distributed Computing (DISC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  41. James S Plank and Lihao Xu. Optimizing cauchy reed-solomon codes for fault-tolerant network storage applications. In Fifth IEEE International Symposium on Network Computing and Applications (NCA'06), pages 173-180. IEEE, 2006. Google Scholar
  42. HariGovind V Ramasamy and Christian Cachin. Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast. In International Conference On Principles Of Distributed Systems, pages 88-102. Springer, 2005. Google Scholar
  43. Irving S Reed and Gustave Solomon. Polynomial codes over certain finite fields. Journal of the society for industrial and applied mathematics, 8(2):300-304, 1960. Google Scholar
  44. Michael K. Reiter and Kenneth P. Birman. How to securely replicate services. ACM Transactions on Programming Languages and Systems (TOPLAS), 16(3), 1994. Google Scholar
  45. Nuno Santos and André Schiper. Optimizing Paxos with batching and pipelining. Theoretical Computer Science, 496:170-183, 2013. Distributed Computing and Networking (ICDCN 2012). Google Scholar
  46. Victor Shoup. Practical threshold signatures. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 207-220. Springer, 2000. Google Scholar
  47. Chrysoula Stathakopoulou, Matej Pavlovic, and Marko Vukolić. State machine replication scalability made simple. In Proceedings of the Seventeenth European Conference on Computer Systems, pages 17-33, 2022. Google Scholar
  48. Andrew Chi-Chih Yao. Some Complexity Questions Related to Distributive Computing. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, pages 209-213, New York, NY, USA, 1979. Association for Computing Machinery. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact