Document Open Access Logo

Blockchain Consensus Protocols in the Wild (Keynote Talk)

Authors Christian Cachin, Marko Vukolic

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.1.pdf
  • Filesize: 0.48 MB
  • 16 pages

Document Identifiers

Author Details

Christian Cachin
Marko Vukolic

Cite As Get BibTex

Christian Cachin and Marko Vukolic. Blockchain Consensus Protocols in the Wild (Keynote Talk). In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.1

Abstract

A blockchain is a distributed ledger for recording transactions, maintained by many nodes without central authority through a distributed cryptographic protocol. All nodes validate the information to be appended to the blockchain, and a consensus protocol ensures that the nodes agree on a unique order in which entries are appended. Consensus protocols for tolerating Byzantine faults have received renewed attention because they also address blockchain systems. This work discusses the process of assessing and gaining confidence in the resilience of a consensus protocols exposed to faults and adversarial nodes. We advocate to follow the established practice in cryptography and computer security, relying on public reviews, detailed models, and formal proofs; the designers of several practical systems appear to be unaware of this. Moreover, we review the consensus protocols in some prominent permissioned blockchain platforms with respect to their fault models and resilience against attacks.

Subject Classification

Keywords
  • Permissioned blockchains
  • consensus
  • Byzantine fault-tolerance
  • snake oil
  • protocol analysis

Metrics

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

References

  1. Elli Androulaki, Christian Cachin, Konstantinos Christidis, Chet Murthy, Binh Nguyen, and Marko Vukolić. Next consensus architecture proposal. Hyperledger Wiki, Fabric Design Documents, available at https://github.com/hyperledger/fabric/blob/master/proposals/r1/Next-Consensus-Architecture-Proposal.md, 2016.
  2. Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics. Wiley, second edition, 2004. Google Scholar
  3. Pierre-Louis Aublin, Rachid Guerraoui, Nikola Knezevic, Vivien Quéma, and Marko Vukolic. The next 700 BFT protocols. ACM Transactions on Computer Systems, 32(4):12:1-12:45, 2015. Google Scholar
  4. Algirdas Avizienis, Jean-Claude Laprie, Brian Randell, and Carl Landwehr. Basic concepts and taxonomy of dependable and secure computing. IEEE Transactions on Dependable and Secure Computing, 1(1):11-33, 2004. Google Scholar
  5. Leemon Baird. The Swirlds hashgraph consensus algorithm: Fair, fast, Byzantine fault tolerance. Swirlds Tech Report SWIRLDS-TR-2016-01, available online, http://www.swirlds.com/developer-resources/whitepapers/, 2016.
  6. Alysson Bessani and João Sousa. From Byzantine consensus to BFT state machine replication: A latency-optimal transformation. In Proc. 9th European Dependable Computing Conference, pages 37-48, 2012. Google Scholar
  7. Alysson Neves Bessani, João Sousa, and Eduardo Adílio Pelinson Alchieri. State machine replication for the masses with BFT-SMaRt. In Proc. 44th International Conference on Dependable Systems and Networks, pages 355-362, 2014. Google Scholar
  8. Gabriel Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75:130-143, 1987. Google Scholar
  9. Ethan Buchman. Tendermint: Byzantine fault tolerance in the age of blockchains. M.Sc. Thesis, University of Guelph, Canada, June 2016. Google Scholar
  10. Ethan Buchman and Jae Kwon. Private discussion, 2017. Google Scholar
  11. Christian Cachin. Distributing trust on the Internet. In Proc. International Conference on Dependable Systems and Networks (DSN-DCCS), pages 183-192, 2001. Google Scholar
  12. Christian Cachin. Yet another visit to Paxos. Research Report RZ 3754, IBM Research, November 2009. Google Scholar
  13. Christian Cachin. Architecture of the Hyperledger blockchain fabric. Workshop on Distributed Cryptocurrencies and Consensus Ledgers (DCCL 2016), 2016. URL: https://www.zurich.ibm.com/dccl/papers/cachin_dccl.pdf.
  14. Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to Reliable and Secure Distributed Programming (Second Edition). Springer, 2011. Google Scholar
  15. Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols (extended abstract). In Joe Kilian, editor, Advances in Cryptology: CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, pages 524-541. Springer, 2001. Google Scholar
  16. Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography. Journal of Cryptology, 18(3):219-246, 2005. Google Scholar
  17. 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
  18. Christian Cachin and Marko Vukolić. Blockchain consensus protocols in the wild. e-print, arXiv:1707.01873 [cs.DC], 2017. URL: https://arxiv.org/abs/1707.01873.
  19. 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
  20. Chain protocol whitepaper. Available online, https://chain.com/docs/1.2/protocol/papers/whitepaper, 2017.
  21. Tushar D. Chandra, Robert Griesemer, and Joshua Redstone. Paxos made live: An engineering perspective. In Proc. 26th ACM Symposium on Principles of Distributed Computing (PODC), pages 398-407, 2007. Google Scholar
  22. 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
  23. Gregory V. Chockler, Idit Keidar, and Roman Vitenberg. Group communication specifications: A comprehensive study. ACM Computing Surveys, 33(4):427-469, 2001. Google Scholar
  24. Allen Clement, Edmund L. Wong, Lorenzo Alvisi, Michael Dahlin, and Mirco Marchetti. Making Byzantine fault tolerant systems tolerate Byzantine faults. In Proc. 6th Symp. Networked Systems Design and Implementation (NSDI), pages 153-168, 2009. Google Scholar
  25. Sisi Duan, Hein Meling, Sean Peisert, and Haibin Zhang. BChain: Byzantine replication with high throughput and embedded reconfiguration. In Marcos K. Aguilera, Leonardo Querzoni, and Marc Shapiro, editors, Proc. 18th Conference on Principles of Distributed Systems (OPODIS), volume 8878 of Lecture Notes in Computer Science, pages 91-106. Springer, 2014. Google Scholar
  26. 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
  27. 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
  28. Juan A. Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. In Advances in Cryptology: Eurocrypt 2015, volume 9057 of Lecture Notes in Computer Science, pages 281-310. Springer, 2015. Google Scholar
  29. Gideon Greenspan. Multichain private blockchain - White paper. http://www.multichain.com/download/MultiChain-White-Paper.pdf, 2016.
  30. Rachid Guerraoui, Ron R. Levy, Bastian Pochon, and Vivien Quéma. Throughput optimal total order broadcast for cluster environments. ACM Transactions on Computer Systems, 28(2):5:1-5:32, 2010. Google Scholar
  31. Vassos Hadzilacos and Sam Toueg. Fault-tolerant broadcasts and related problems. In Sape J. Mullender, editor, Distributed Systems (2nd Ed.). ACM Press &Addison-Wesley, New York, 1993. Google Scholar
  32. Mike Hearn. Corda: A distributed ledger. Available online, https://docs.corda.net/_static/corda-technical-whitepaper.pdf, 2016.
  33. Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, and Benjamin Reed. ZooKeeper: Wait-free coordination for internet-scale systems. In Proc. USENIX Annual Technical Conference, 2010. Google Scholar
  34. Flavio Junqueira, Benjamin Reed, and Marco Serafini. Zab: High-performance broadcast for primary-backup systems. In Proc. 41st International Conference on Dependable Systems and Networks, 2011. Google Scholar
  35. Martin Kleppmann. Designing Data-Intensive Applications. O'Reilly Media, 2017. Google Scholar
  36. Leslie Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133-169, May 1998. Google Scholar
  37. Leslie Lamport. Paxos made simple. SIGACT News, 32(4):51-58, 2001. Google Scholar
  38. Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382-401, July 1982. Google Scholar
  39. Butler Lampson. The ABCD’s of Paxos. In Proc. 20th ACM Symposium on Principles of Distributed Computing (PODC), 2001. Google Scholar
  40. Barbara Liskov. From viewstamped replication to Byzantine fault tolerance. In Bernadette Charron-Bost, Fernando Pedone, and André Schiper, editors, Replication: Theory and Practice, volume 5959 of Lecture Notes in Computer Science, pages 121-149. Springer, 2010. Google Scholar
  41. Barbara Liskov and James Cowling. Viewstamped replication revisited. MIT-CSAIL-TR-2012-021, July 2012. Google Scholar
  42. Dahlia Malkhi and Michael K. Reiter. Byzantine quorum systems. Distributed Computing, 11(4):203-213, 1998. Google Scholar
  43. Will Martino. Kadena - The first scalable, high performance private blockchain. Whitepaper, http://kadena.io/docs/Kadena-ConsensusWhitePaper-Aug2016.pdf, 2016.
  44. 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
  45. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. Whitepaper, 2009. URL: http://bitcoin.org/bitcoin.pdf.
  46. Brian M. Oki and Barbara Liskov. Viewstamped replication: A new primary copy method to support highly-available distributed systems. In Proc. 7th ACM Symposium on Principles of Distributed Computing (PODC), pages 8-17, 1988. Google Scholar
  47. Diego Ongaro and John K. Ousterhout. In search of an understandable consensus algorithm. In Proc. USENIX Annual Technical Conference, pages 305-319, 2014. Google Scholar
  48. 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
  49. Michel Raynal. Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems. Synthesis Lectures on Distributed Computing Theory. Morgan &Claypool, 2010. Google Scholar
  50. George Samman. Kadena: The first real private blockchain. http://sammantics.com/blog/2016/11/29/kadena-the-first-real-private-blockchain, November 2016.
  51. Giuliana Santos Veronese, Miguel Correia, Alysson Neves Bessani, and Lau Cheuk Lung. Spin one’s wheels? Byzantine fault tolerance with a spinning primary. In Proc. 28th Symposium on Reliable Distributed Systems (SRDS), pages 135-144, 2009. Google Scholar
  52. 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
  53. Alexander Shraer, Benjamin Reed, Dahlia Malkhi, and Flavio Paiva Junqueira. Dynamic reconfiguration of primary/backup clusters. In Proc. USENIX Annual Technical Conference, pages 425-437, 2012. Google Scholar
  54. João Sousa and Alysson Bessani. Separating the WHEAT from the chaff: An empirical design for geo-replicated state machines. In Proc. 34th Symposium on Reliable Distributed Systems (SRDS), pages 146-155, 2015. Google Scholar
  55. Tim Swanson. Consensus-as-a-service: A brief report on the emergence of permissioned, distributed ledger systems. Report, available online, April 2015. URL: http://www.ofnumbers.com/wp-content/uploads/2015/04/Permissioned-distributed-ledgers.pdf.
  56. Robbert van Renesse, Nicolas Schiper, and Fred B. Schneider. Vive la différence: Paxos vs. viewstamped replication vs. zab. IEEE Transactions on Dependable and Secure Computing, 12(4):472-484, 2015. Google Scholar
  57. Robbert van Renesse and Fred B. Schneider. Chain replication for supporting high throughput and availability. In Proc. 6th Symp. Operating Systems Design and Implementation (OSDI), 2004. Google Scholar
  58. Marko Vukolić. Quorum Systems: With Applications to Storage and Consensus. Synthesis Lectures on Distributed Computing Theory. Morgan &Claypool, 2012. Google Scholar
  59. Marko Vukolić. Rethinking permissioned blockchains. In Proc. ACM Workshop on Blockchain, Cryptocurrencies and Contracts (BCC'17), 2017. 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