Document Open Access Logo

Non-Determinism in Byzantine Fault-Tolerant Replication

Authors Christian Cachin, Simon Schubert, Marko Vukolic

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2016.24.pdf
  • Filesize: 0.58 MB
  • 16 pages

Document Identifiers

Author Details

Christian Cachin
Simon Schubert
Marko Vukolic

Cite As Get BibTex

Christian Cachin, Simon Schubert, and Marko Vukolic. Non-Determinism in Byzantine Fault-Tolerant Replication. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.OPODIS.2016.24

Abstract

Service replication distributes an application over many processes for tolerating faults, attacks, and misbehavior among a subset of the processes. With the recent interest in blockchain technologies, distributed execution of one logical application has become a prominent topic. The established state-machine replication paradigm inherently requires the application to be deterministic. This paper distinguishes three models for dealing with non-determinism in replicated services, where some processes are subject to faults and arbitrary behavior (so-called Byzantine faults): first, the modular case that does not require any changes to the potentially non-deterministic application (and neither access to its internal data); second, master-slave solutions, where ties are broken by a leader and the other processes validate the choices of the leader; and finally, applications that use cryptography and secret keys. Cryptographic operations and secrets must be treated specially because they require strong randomness to satisfy their goals.

The paper also introduces two new protocols. First, Protocol Sieve uses the modular approach and filters out non-deterministic operations in an application. It ensures that all correct processes produce the same outputs and that their internal states do not diverge. A second protocol, called Mastercrypt, implements cryptographically secure randomness generation with a verifiable random function and is appropriate for most situations in which cryptographic secrets are involved. All protocols are described in a generic way and do not assume a particular implementation of the underlying consensus primitive.

Subject Classification

Keywords
  • Blockchain
  • atomic broadcast
  • consensus
  • distributed cryptography
  • verifiable random functions

Metrics

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

References

  1. Joseph Bonneau, Andrew Miller, Jeremy Clark, Arvind Narayanan, Joshua A. Kroll, and Edward W. Felten. SoK: Research perspectives and challenges for Bitcoin and cryptocurrencies. In Proc. 36th IEEE Symposium on Security &Privacy, pages 104-121, 2015. Google Scholar
  2. Thomas C. Bressoud and Fred B. Schneider. Hypervisor-based fault-tolerance. ACM Transactions on Computer Systems, 14(1):80-107, February 1996. Google Scholar
  3. Navin Budhiraja, Keith Marzullo, Fred B. Schneider, and Sam Toueg. The primary-backup approach. In Distributed Systems (2nd Ed.). ACM Press &Addison-Wesley, New York, 1993. Google Scholar
  4. Christian Cachin. Distributing trust on the Internet. In Proc. International Conference on Dependable Systems and Networks (DSN-DCCS), pages 183-192, 2001. Google Scholar
  5. Christian Cachin, editor. Distributed Cryptocurrencies and Consensus Ledgers (DCCL 2016), Online proceedings of workshop co-located with PODC, 2016. URL: https://www.zurich.ibm.com/dccl/.
  6. Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to Reliable and Secure Distributed Programming (Second Edition). Springer, 2011. Google Scholar
  7. Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols (extended abstract). In Advances in Cryptology: CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 524-541. Springer, 2001. Google Scholar
  8. Christian Cachin and Jonathan A. Poritz. Secure intrusion-tolerant replication on the Internet. In Proc. International Conference on Dependable Systems and Networks (DSN-DCCS), pages 167-176, June 2002. Google Scholar
  9. Christian Cachin, Simon Schubert, and Marko Vukolić. Non-determinism in Byzantine fault-tolerant replication. e-print, arXiv:1603.07351 [cs.DC], 2016. URL: http://arxiv.org/abs/1603.07351.
  10. Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4):398-461, November 2002. Google Scholar
  11. Miguel Castro, Rodrigo Rodrigues, and Barbara Liskov. BASE: Using abstraction to improve fault tolerance. ACM Transactions on Computer Systems, 21(3):236-269, 2003. Google Scholar
  12. Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225-267, 1996. Google Scholar
  13. Bernadette Charron-Bost, Fernando Pedone, and André Schiper, editors. Replication: Theory and Practice, volume 5959 of Lecture Notes in Computer Science. Springer, 2010. Google Scholar
  14. Allen Clement, Manos Kapritsos, Sangmin Lee, Yang Wang, Lorenzo Alvisi, Mike Dahlin, and Taylor Riche. UpRight cluster services. In Proc. 22nd ACM Symposium on Operating Systems Principles (SOSP), pages 277-290, 2009. Google Scholar
  15. Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, Ari Juels, Ahmed Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, Emin Gun Sirer, Dawn Song, and Roger Wattenhofer. On scaling decentralized blockchains. In Proc. 3rd Workshop on Bitcoin and Blockchain Research, 2016. Google Scholar
  16. Yvo Desmedt. Threshold cryptography. European Transactions on Telecommunications, 5(4):449-457, 1994. Google Scholar
  17. Assia Doudou, Benoit Garbinato, Rachid Guerraoui, and André Schiper. Muteness failure detectors: Specification and implementation. In Proc. 3rd European Dependable Computing Conference (EDCC-3), volume 1667 of Lecture Notes in Computer Science, pages 71-87. Springer, 1999. Google Scholar
  18. Sisi Duan and Haibin Zhang. Practical confidential state machine replication: How to process data privately in the cloud. In Proc. 35th Symposium on Reliable Distributed Systems (SRDS), 2016. Google Scholar
  19. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288-323, 1988. Google Scholar
  20. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374-382, April 1985. Google Scholar
  21. Zhenyu Guo, Chuntao Hong, Mao Yang, Dong Zhou, Lidong Zhou, and Li Zhuang. Rex: Replication at the speed of multi-core. In Proc. 9th European Conference on Computer Systems (EuroSys), 2014. Google Scholar
  22. Vassos Hadzilacos and Sam Toueg. Fault-tolerant broadcasts and related problems. In Distributed Systems. ACM Press &Addison-Wesley, New York, 1993. Google Scholar
  23. Tibor Jager. Verifiable random functions from weaker assumptions. In Proc. 12th Theory of Cryptography Conference (TCC 2015), volume 9015 of Lecture Notes in Computer Science, pages 121-143. Springer, 2015. Google Scholar
  24. Rüdiger Kapitza, Matthias Schunter, Christian Cachin, Klaus Stengel, and Tobias Distler. Storyboard: Optimistic deterministic multithreading. In Proc. 6th Workshop on Hot Topics in System Dependability, 2010. Google Scholar
  25. Manos Kapritsos, Yang Wang, Vivien Quema, Allen Clement, Lorenzo Alvisi, and Mike Dahlin. All about Eve: Execute-verify replication for multi-core servers. In Proc. 10th Symp. Operating Systems Design and Implementation (OSDI), 2012. Google Scholar
  26. Ramakrishna Kotla and Michael Dahlin. High throughput Byzantine fault tolerance. In Proc. International Conference on Dependable Systems and Networks (DSN-DCCS), pages 575-584, June 2004. Google Scholar
  27. Barbara Liskov. From viewstamped replication to Byzantine fault tolerance. In Replication: Theory and Practice, volume 5959 of Lecture Notes in Computer Science, pages 121-149. Springer, 2010. Google Scholar
  28. Anna Lysyanskaya. Unique signatures and verifiable random functions from the DH-DDH separation. In Advances in Cryptology: CRYPTO 2002, volume 2442 of Lecture Notes in Computer Science, pages 597-612. Springer, 2002. Google Scholar
  29. Silvio Micali, Michael Rabin, and Salil Vadhan. Verifiable random functions. In Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS), pages 120-130, 1999. Google Scholar
  30. Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of BFT protocols. In Proc. ACM Conference on Computer and Communications Security (CCS), 2016. Google Scholar
  31. M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, April 1980. Google Scholar
  32. Michael K. Reiter and Kenneth P. Birman. How to securely replicate services. ACM Transactions on Programming Languages and Systems, 16(3):986-1009, May 1994. Google Scholar
  33. Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys, 22(4):299-319, December 1990. Google Scholar
  34. Tim Swanson. Consensus-as-a-service: A brief report on the emergence of permissioned, distributed ledger systems. Report, April 2015. URL: http://www.ofnumbers.com/wp-content/uploads/2015/04/Permissioned-distributed-ledgers.pdf.
  35. Marko Vukolić. The quest for scalable blockchain fabric: Proof-of-work vs. BFT replication. In Open Problems in Network Security, Proc. IFIP WG 11.4 Workshop (iNetSec 2015), volume 9591 of Lecture Notes in Computer Science, pages 112-125. Springer, 2016. Google Scholar
  36. Michael Walfish and Andrew J. Blumberg. Verifying computations without reexecuting them. Communications of the ACM, 58(2), February 2015. Google Scholar
  37. Lidong Zhou, Fred B. Schneider, and Robbert van Renesse. COCA: A secure distributed online certification authority. ACM Transactions on Computer Systems, 20(4):329-368, 2002. 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