Document Open Access Logo

Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols

Authors John Augustine , Valerie King, Anisur Rahaman Molla , Gopal Pandurangan , Jared Saia

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.31.pdf
  • Filesize: 0.61 MB
  • 19 pages

Document Identifiers

Author Details

John Augustine
  • Dept. of Computer Science & Engg, Indian Institute of Technology Madras, Chennai 600036, India
Valerie King
  • Department of Computer Science, University of Victoria, Vancouver BC V8P 5C2, Canada
Anisur Rahaman Molla
  • Computer and Communication Sciences, Indian Statistical Institute, Kolkata 700108, India
Gopal Pandurangan
  • Department of Computer Science, University of Houston, Houston, TX 77204, USA
Jared Saia
  • Department of Computer Science, University of New Mexico, NM 87131, USA

Funding

  • Augustine, John: Research supported in part by an Extra-Mural Research Grant (file number EMR/2016/003016) and a MATRICS grant (file number MTR/2018/001198), both funded by the Science and Engineering Research Board, Department of Science and Technology, Government of India and by the VAJRA faculty program of the Government of India.
  • King, Valerie: This work is supported by an NSERC Discovery Grant.
  • Molla, Anisur Rahaman: Research supported by DST Inspire Faculty research grant DST/INSPIRE/04/2015/002801 and ISI DCSW/TAC Project (file number E5412).
  • Pandurangan, Gopal: Research supported, in part, by NSF grants CCF-1527867, CCF-1540512, IIS-1633720, CCF-BSF-1717075, BSF award 2016419, and by the VAJRA faculty program of the Government of India.
  • Saia, Jared: This work is supported by the National Science Foundation grants CNS-1318880 and CCF-1320994.

Cite As Get BibTex

John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia. Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DISC.2020.31

Abstract

The last decade has seen substantial progress on designing Byzantine agreement algorithms which do not require all-to-all communication. However, these protocols do require each node to play a particular role determined by its ID. Motivated by the rise of permissionless systems such as Bitcoin, where nodes can join and leave at will, we extend this research to a more practical model where initially, each node does not know the identity of its neighbors. In particular, a node can send to new destinations only by sending to random (or arbitrary) nodes, or responding to messages received from those destinations. We assume a synchronous and fully-connected network, with a full-information, but static Byzantine adversary. A major drawback of existing Byzantine protocols in this setting is that they have at least Ω(n²) message complexity, where n is the total number of nodes. In particular, the communication cost incurred by the honest nodes is Ω(n²), even when Byzantine node send no messages. In this paper, we design protocols for fundamental problems which are message-competitive, i.e., the total number of bits sent by honest nodes is not significantly more than the total sent by Byzantine nodes. 
We describe a message-competitive algorithm to solve Byzantine agreement, leader election, and committee election. Our algorithm sends an expected O((T+n)log n) bits and has latency O(polylog(n)) (even in the CONGEST model), where T = O(n²) is the number of bits sent by Byzantine nodes. The algorithm is resilient to (1/4-ε)n Byzantine nodes for any fixed ε > 0, and succeeds with high probability. Our message bounds are essentially optimal up to polylagarithmic factors, for algorithms that run in polylogarithmic rounds in the CONGEST model.
We also show lower bounds for message-competitive Byzantine agreement regardless of rounds. We prove that, in general, one cannot hope to design Byzantine protocols that have communication cost that is significantly smaller than the cost of the Byzantine adversary.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Mathematics of computing → Probabilistic algorithms
  • Mathematics of computing → Discrete mathematics
Keywords
  • Byzantine protocols
  • Byzantine agreement
  • Leader election
  • Committee election
  • Message-competitive protocol
  • Randomized protocol

Metrics

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

Related Versions

References

  1. Ittai Abraham, TH Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Communication complexity of byzantine agreement, revisited. In PODC, pages 317-326, 2019. Google Scholar
  2. Atul Adya, William J. Bolosky, Miguel Castro, Gerald Cermak, Ronnie Chaiken, John R. Douceur, Jon Howell, Jacob R. Lorch, Marvin Theimer, and Roger P. Wattenhofer. FARSITE: Federated, Available, and Reliable Storage for Incompletely Trusted Environment. In 5^th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 1-14, 2002. Google Scholar
  3. A. Agbaria and R. Friedman. Overcoming byzantine failures using checkpointing. University of Illinois at Urbana-Champaign Coordinated Science Laboratory technical report no. UILU-ENG- 03-2228 (CRHC-03-14), 2003. Google Scholar
  4. Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, and Jared Saia. Sending a message with unknown noise. In Proceedings of the 19th International Conference on Distributed Computing and Networking (ICDCN), pages 8:1-8:10, 2018. Google Scholar
  5. Yair Amir, Claudiu Danilov, Jonathan Kirsch, John Lane, Danny Dolev, Cristina Nita-Rotaru, Josh Olsen, and David John Zage. Scaling byzantine fault-tolerant replication towide area networks. In Proceedings of International Conference on Dependable Systems and Networks (DSN), pages 105-114, 2006. Google Scholar
  6. D. P. Anderson and J. Kubiatowicz. The worldwide computer. Scientific American, 286(3):28-35, 2002. Google Scholar
  7. Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). John Wiley Interscience, 2004. Google Scholar
  8. John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia. Scalable and secure computation among strangers: Message-competitive byzantine protocols. CoRR, abs/1907.10308, 2019. Google Scholar
  9. Michael Ben-Or, Elan Pavlov, and Vinod Vaikuntanathan. Byzantine agreement in the full-information model in o(log n) rounds. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 179-186. ACM, 2006. Google Scholar
  10. Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Maxwell Young. How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness. In Proceedings of the 27^th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 636-654, 2016. Google Scholar
  11. Michael A. Bender, Jeremy T. Fineman, Mahnush Movahedi, Jared Saia, Varsha Dani, Seth Gilbert, Seth Pettie, and Maxwell Young. Resource-Competitive Algorithms. SIGACT News, 46(3):57-71, September 2015. Google Scholar
  12. Bitcoin. Bitcoin website https://bitcoin.org/. Google Scholar
  13. 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 Proceedings of the IEEE Symposium on Security and Privacy (SP), pages 104-121, 2015. Google Scholar
  14. Nicolas Braud-Santoni, Rachid Guerraoui, and Florian Huc. Fast byzantine agreement. In Proceedings of the 2013 ACM symposium on Principles of distributed computing, pages 57-64. ACM, 2013. Google Scholar
  15. Christian Cachin and Jonathan A. Poritz. Secure Intrusion-Tolerant Replication on the Internet. In Proceedings of the International Conference on Dependable Systems and Networks (DSN), pages 167-176, 2002. Google Scholar
  16. Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance. Operating Systems Review, 33:173-186, 1998. Google Scholar
  17. 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
  18. Allen Clement, Mirco Marchetti, Edmund Wong, Lorenzo Alvisi, and Mike Dahlin. Byzantine Fault Tolerance: The Time is Now. In Proceedings of the Second Workshop on Large-Scale Distributed Systems and Middleware (LADIS), pages 1-4, 2008. Google Scholar
  19. Allen Clement, Edmund Wong, Lorenzo Alvisi, Mike Dahlin, and Mirco Marchetti. Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults. In Proceedings of the Sixth USENIX Symposium on Networked Systems Design and Implementation (NSDI), pages 153-168, 2009. Google Scholar
  20. Varsha Dani, Tom Hayes, Mahnush Movahedi, Jared Saia, and Maxwell Young. Interactive Communication with Unknown Noise Rate. Information and computation, 261(Part):464-486, 2018. Google Scholar
  21. Varsha Dani, Mahnush Movahedi, Jared Saia, and Maxwell Young. Interactive Communication with Unknown Noise Rate. In Proceedings of the Colloquium on Automata, Languages, and Programming (ICALP), pages 575-587, 2015. Google Scholar
  22. Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for byzantine agreement. J. ACM, 32(1):191-204, 1985. Google Scholar
  23. Ethereum. Ethereum website https://ethereum.org/. Google Scholar
  24. Ittay Eyal, Adem Efe Gencer, Emin Gün Sirer, and Robbert Van Renesse. Bitcoin-NG: A Scalable Blockchain Protocol. In Proceedings of the 13^th USENIX Symposium on Networked Systems Design and Implementation (NSDI), pages 45-59, 2016. Google Scholar
  25. Uriel Feige. Noncryptographic selection protocols. In Proc. of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pages 142-153, 1999. Google Scholar
  26. Paul Feldman and Silvio Micali. Byzantine agreement in constant expected time (and trusting no one). In FOCS, pages 267-276, 1985. Google Scholar
  27. Freenet. Freenet website https://freenetproject.org/author/freenet-project-inc.html. Google Scholar
  28. Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling Byzantine Agreements for Cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP), pages 51-68, 2017. Google Scholar
  29. Seth Gilbert, Valerie King, Seth Pettie, Ely Porat, Jared Saia, and Maxwell Young. (Near) Optimal Resource-Competitive Broadcast with Jamming. In Proceedings of the 26^th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 257-266, 2014. Google Scholar
  30. Seth Gilbert, Valerie King, Jared Saia, and Maxwell Young. Resource-Competitive Analysis: A New Perspective on Attack-Resistant Distributed Computing. In Proceedings of the 8^th ACM International Workshop on Foundations of Mobile Computing, page 1, 2012. Google Scholar
  31. Seth Gilbert and Maxwell Young. Making Evildoers Pay: Resource-Competitive Broadcast in Sensor Networks. In Proceedings of the 31^th Symposium on Principles of Distributed Computing (PODC), pages 145-154, 2012. Google Scholar
  32. Shafi Goldwasser, Elan Pavlov, and Vinod Vaikuntanathan. Fault-tolerant distributed computing in full-information networks. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 15-26. IEEE Computer Society, 2006. Google Scholar
  33. Sergey Gorbunov and Silvio Micali. Democoin: A Publicly Verifiable and Jointly Serviced Cryptocurrency. Cryptology ePrint Archive, Report 2015/521, 2015. http://eprint.iacr.org/2015/521. Google Scholar
  34. Jim Gray. The cost of messages. In PODC, pages 1-7. ACM, 1988. Google Scholar
  35. Diksha Gupta, Jared Saia, and Maxwell Young. Proof of work without all the work. In Proceedings of the 19th International Conference on Distributed Computing and Networking, pages 1-10, 2018. Google Scholar
  36. Diksha Gupta, Jared Saia, and Maxwell Young. Peace through superior puzzling: An asymmetric sybil defense. In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 1083-1094. IEEE, 2019. Google Scholar
  37. Diksha Gupta, Jared Saia, and Maxwell Young. Resource burning for permissionless systems. arXiv preprint arXiv:2006.04865, 2020. Google Scholar
  38. Vassos Hadzilacos and Joseph Y. Halpern. Message-optimal protocols for byzantine agreement. Mathematical Systems Theory, 26(1):41-102, 1993. Conference version in PODC 1991. Google Scholar
  39. Valerie King, Steven Lonargan, Jared Saia, and Amitabh Trehan. Load balanced scalable byzantine agreement through quorum building, with full information. In International Conference on Distributed Computing and Networking, pages 203-214. Springer, 2011. Google Scholar
  40. Valerie King and Jared Saia. Breaking the O(n^2) bit barrier: Scalable byzantine agreement with an adaptive adversary. J. ACM, 58(4):18:1-18:24, 2011. Google Scholar
  41. Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Scalable leader election. In Proceedings of the Seventeenth annual ACM-SIAM Symposium on Discrete Algorithm, pages 990-999. Society for Industrial and Applied Mathematics, 2006. Google Scholar
  42. Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Towards secure and scalable computation in peer-to-peer networks. In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on, pages 87-98. IEEE, 2006. Google Scholar
  43. Valerie King, Jared Saia, and Maxwell Young. Conflict on a Communication Channel. In Proceedings of the 30^th Symposium on Principles of Distributed Computing (PODC), pages 277-286, 2011. Google Scholar
  44. Jiejun Kong. Anonymous and untraceable communications in mobile wireless networks. Citeseer, 2004. Google Scholar
  45. Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva: Speculative Byzantine Fault Tolerance. In Proceedings of 21^st ACM SIGOPS Symposium on Operating Systems Principles, pages 45-58, 2007. Google Scholar
  46. Dariusz R. Kowalski and Achour Mostéfaoui. Synchronous byzantine agreement with nearly a cubic number of communication bits: synchronous byzantine agreement with nearly a cubic number of communication bits. In Panagiota Fatourou and Gadi Taubenfeld, editors, PODC, pages 84-91. ACM, 2013. Google Scholar
  47. Harry C Li, Allen Clement, Edmund L Wong, Jeff Napper, Indrajit Roy, Lorenzo Alvisi, and Michael Dahlin. Bar gossip. In Proceedings of the 7th symposium on Operating systems design and implementation, pages 191-204, 2006. Google Scholar
  48. Na Li, Nan Zhang, Sajal K Das, and Bhavani Thuraisingham. Privacy preservation in wireless sensor networks: A state-of-the-art survey. Ad Hoc Networks, 7(8):1501-1514, 2009. Google Scholar
  49. Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek Saxena. A Secure Sharding Protocol For Open Blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 17-30, 2016. Google Scholar
  50. Nancy Lynch. Distributed Algorithms. Morgan Kaufmann, 1996. Google Scholar
  51. Dahlia Malkhi and Michael K. Reiter. Unreliable intrusion detection in distributed computations. In Proceedings of the 10th Computer Security Foundations Workshop (CSFW), pages 116-125, 1997. Google Scholar
  52. Michael Mitzenmacher and Eli Upfal. Probability and computing: randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017. Google Scholar
  53. Hector Garcia Molina, Frank Pittelli, and Susan Davidson. Applications of Byzantine Agreement in Database Systems. ACM Transactions on Database Systems (TODS), 11:27-47, 1986. Google Scholar
  54. Oceanstore. The Oceanstore Project. http://oceanstore.cs.berkeley.edu. Google Scholar
  55. Gopal Pandurangan. Distributed Network Algorithms. https://sites.google.com/site/gopalpandurangan/dna, 2018. Google Scholar
  56. Marshall C. Pease, Robert E. Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228-234, 1980. Google Scholar
  57. D. Peleg. Distributed Computing: A Locality Sensitive Approach. SIAM, 2000. Google Scholar
  58. Nuno Preguiça, Rodrigo Rodrigues, Christóvāo Honorato, and Joāo Lourenço. Byzantium: Byzantine-Fault-Tolerant Database Replication Providing Snapshot Isolation. In Proceedings of the Fourth Conference on Hot Topics in System Dependability, page 9. USENIX Association, 2008. Google Scholar
  59. Sean C. Rhea, Patrick R. Eaton, Dennis Geels, Hakim Weatherspoon, Ben Y. Zhao, and John Kubiatowicz. Pond: The oceanstore prototype. In Proceedings of the FAST '03 Conference on File and Storage Technologies, pages 1-14, 2003. Google Scholar
  60. Elaine Shi and Adrian Perrig. Designing secure sensor networks. IEEE Wireless Commun., 11(6):38-43, 2004. Google Scholar
  61. Sabrina Sicari, Alessandra Rizzardi, Luigi Alfredo Grieco, and Alberto Coen-Porisini. Security, privacy and trust in internet of things: The road ahead. Computer networks, 76:146-164, 2015. Google Scholar
  62. SINTRA. SINTRA - Distributed Trust on the Internet. http://www.zurich.ibm.com/security/dti/. Google Scholar
  63. Tor. Tor website https://www.torproject.org/. Google Scholar
  64. Rolf H Weber. Internet of things-new security and privacy challenges. Computer law & security review, 26(1):23-30, 2010. Google Scholar
  65. Alex Wright. Contemporary approaches to fault tolerance. Commun. ACM, 52(7):13-15, 2009. Google Scholar
  66. Hiroyuki Yoshino, Naohiro Hayashibara, Tomoya Enokido, and Makoto Takizawa. Byzantine agreement protocol using hierarchical groups. In Proceedings of the 11th International Conference on Parallel and Distributed Systems (ICPADS), pages 64-70, 2005. Google Scholar
  67. Mahdi Zamani, Jared Saia, and Jedidiah Crandall. TorBricks: Blocking-Resistant Tor Bridge Distribution. In International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 426-440. Springer, 2017. Google Scholar
  68. Wenbing Zhao. A Byzantine Fault Tolerant Distributed Commit Protocol. In Proceedings of the 3^rd IEEE International Symposium on Dependable, Autonomic and Secure Computing, pages 37-46, 2007. 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