Document Open Access Logo

Optimal Error-Free Multi-Valued Byzantine Agreement

Author Jinyuan Chen

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.17.pdf
  • Filesize: 0.99 MB
  • 19 pages

Document Identifiers

Author Details

Jinyuan Chen
  • Louisiana Tech University, Ruston, LA, USA

Funding

  • Chen, Jinyuan: This work was supported in part by the NSF under Grant OIA-1946231 and in part by the Louisiana Board of Regents under Grant 32-4121-40336.

Cite As Get BibTex

Jinyuan Chen. Optimal Error-Free Multi-Valued Byzantine Agreement. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DISC.2021.17

Abstract

Byzantine agreement (BA) is a distributed consensus problem where n processors want to reach agreement on an 𝓁-bit message or value, but up to t of the processors are dishonest or faulty. The challenge of this BA problem lies in achieving agreement despite the presence of dishonest processors who may arbitrarily deviate from the designed protocol. In this work by using coding theory, together with graph theory and linear algebra, we design a coded BA protocol (termed as COOL) that achieves consensus on an 𝓁-bit message with optimal resilience, asymptotically optimal round complexity, and asymptotically optimal communication complexity when 𝓁 ≥ t log t, simultaneously. The proposed COOL is a deterministic BA protocol that is guaranteed to be correct in all executions (error free) and does not rely on cryptographic technique such as signatures, hashing, authentication and secret sharing (signature free). It is secure against computationally unbounded adversary who takes full control over the dishonest processors (information-theoretic secure). The main idea of the proposed COOL is to use a carefully-crafted error correction code that provides an efficient way of exchanging "compressed" information among distributed nodes, while keeping the ability of detecting errors, masking errors, and making a consistent and validated agreement at honest distributed nodes. We show that our results can also be extended to the setting of Byzantine broadcast, aka Byzantine generals problem, where the honest processors want to agree on the message sent by a leader who is potentially dishonest. The results reveal that coding is an effective approach for achieving the fundamental limits of Byzantine agreement and its variants. Our protocol analysis borrows tools from coding theory, graph theory and linear algebra.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Byzantine agreement
  • information-theoretic security
  • error correction codes

Metrics

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

Related Versions

References

  1. I. Abraham, S. Devadas, D. Dolev, K. Nayak, and L. Ren. Efficient synchronous Byzantine consensus. Available on ArXiv: https://arxiv.org/abs/1704.02397, 2017.
  2. I. Abraham, D. Dolev, and J. Halpern. An almost-surely terminating polynomial protocol for asynchronous Byzantine agreement with optimal resilience. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 405-414, 2008. Google Scholar
  3. S. Ahmed. A performance study of Hyperledger Fabric in a smart home and IoT environment, 2019. Available on https://www.duo.uio.no/handle/10852/70940. Google Scholar
  4. Z. Amsden et al. The libra blockchain. Libra White Paper, 2019. Google Scholar
  5. E. Androulaki et al. Hyperledger fabric: a distributed operating system for permissioned blockchains. In Proceedings of the Thirteenth EuroSys Conference, 2018. Google Scholar
  6. E. Berlekamp. Nonbinary BCH decoding (abstr.). IEEE Trans. Inf. Theory, 14(2):242-242, 1968. Google Scholar
  7. P. Berman, J. Garay, and K. Perry. Bit optimal distributed consensus. Computer Science, pages 313-321, 1992. Google Scholar
  8. V. Buterin. A next-generation smart contract and decentralized application platform. Ethereum White Paper, 2015. Google Scholar
  9. C. Cachin and S. Tessaro. Asynchronous verifiable information dispersal. In IEEE Symposium on Reliable Distributed Systems (SRDS), 2005. Google Scholar
  10. N. Cai and R. Yeung. Network error correction, II: Lower bounds. Communications in Information and Systems, 6(1):37-54, 2006. Google Scholar
  11. R. Canetti and T. Rabin. Fast asynchronous Byzantine agreement with optimal resilience. In 25th Annual ACM Symposium on the Theory of Computing, pages 42-51, 1993. Google Scholar
  12. F. Casino, T. Dasaklis, and C. Patsakis. A systematic literature review of blockchain-based applications: Current status, classification and open issues. Telematics and Informatics, 36:55-81, March 2019. Google Scholar
  13. B. Chan and E. Shi. Streamlet: Textbook streamlined blockchains. In 2nd ACM Conference on Advances in Financial Technologies(AFT), pages 1-11, October 2020. Google Scholar
  14. J. Chen. Fundamental limits of Byzantine agreement. Available on ArXiv: https://arxiv.org/pdf/2009.10965.pdf, 2020.
  15. B. Chor and B. Coan. A simple and efficient randomized Byzantine agreement algorithm. IEEE Transactions on Software Engineering, 11(6):531-539, June 1985. Google Scholar
  16. B. Coan and J. Welch. Modular construction of a Byzantine agreement protocol with optimal message bit complexity. Information and Computation, 97(1):61-85, March 1992. Google Scholar
  17. T. Courtade and T. Halford. Coded cooperative data exchange for a secret key. IEEE Trans. Inf. Theory, 62(7):3785-3795, 2016. Google Scholar
  18. M. Demir, M. Alalfi, O. Turetken, and A. Ferworn. Security smells in smart contracts. In IEEE 19th International Conference on Software Quality, Reliability and Security Companion (QRS-C), July 2019. Google Scholar
  19. D. Dolev and R. Reischuk. Bounds on information exchange for Byzantine agreement. Journal of the ACM, 32(1):191-204, 1985. Google Scholar
  20. D. Dolev and H. Strong. Authenticated algorithms for Byzantine agreement. SIAM Journal on Computing, 12(4):656-666, 1983. Google Scholar
  21. P. Feldman and S. Micali. An optimal probabilistic protocol for synchronous Byzantine agreement. SIAM Journal on Computing, 26(4):873-933, August 1997. Google Scholar
  22. M. Fischer and N. Lynch. A lower bound for the time to assure interactive consistency. Information Processing Letters, 14(4):183-186, June 1982. Google Scholar
  23. M. Fitzi and M. Hirt. Optimally efficient multi-valued Byzantine agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 163-168, 2006. Google Scholar
  24. C. Fragouli, D. Lun, M. Medard, and P. Pakzad. On feedback for network coding. In 2007 41st Annual Conference on Information Sciences and Systems, March 2007. Google Scholar
  25. C. Ganesh and A. Patra. Optimal extension protocols for Byzantine broadcast and agreement. In Distributed Computing, July 2020. Google Scholar
  26. J. Garay and Y. Moses. Fully polynomial Byzantine agreement for n > 3t processors in t + 1 rounds. SIAM Journal on Computing, 27(1):247-290, 1998. Google Scholar
  27. G. Goodson, J. Wylie, G. Ganger, and M. Reiter. Efficient Byzantine-tolerant erasure-coded storage. In International Conference on Dependable Systems and Networks, June 2004. Google Scholar
  28. C. Gorenflo, S. Lee, L. Golab, and S. Keshav. FastFabric: Scaling Hyperledger Fabric to 20,000 transactions per second. In IEEE International Conference on Blockchain and Cryptocurrency (ICBC), 2019. Google Scholar
  29. W. Halbawi, T. Ho, H. Yao, and I. Duursma. Distributed reed-solomon codes for simple multiple access networks. In Proc. IEEE Int. Symp. Inf. Theory (ISIT), 2014. Google Scholar
  30. M. Hammoudeh, I. Ghafir, A. Bounceur, and T. Rawlinson. Continuous monitoring in mission-critical applications using the internet of things and blockchain. In 3rd International Conference on Future Networks and Distributed Systems, July 2019. Google Scholar
  31. T. Ho, B. Leong, R. Koetter, M. Medard, M. Effros, and D. Karger. Byzantine modification detection in multicast networks using randomized network coding. In Proc. IEEE Int. Symp. Inf. Theory (ISIT), June 2004. Google Scholar
  32. D. Huang and D. Medhi. A Byzantine resilient multi-path key establishment scheme and its robustness analysis for sensor networks. In 19th IEEE International Parallel and Distributed Processing Symposium, April 2005. Google Scholar
  33. Hyperledger. Hyperledger-fabricdocs documentation, 2020. Google Scholar
  34. S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, M. Medard, and M. Effros. Resilient network coding in the presence of Byzantine adversaries. IEEE Trans. Inf. Theory, 54(6):2596-2603, June 2008. Google Scholar
  35. J. Katz and C. Koo. On expected constant-round protocols for Byzantine agreement. Journal of Computer and System Sciences, 75(2):91-112, 2009. Google Scholar
  36. S. Kim, T. Ho, M. Effros, and S. Avestimehr. New results on network error correction: Capacities and upper bounds. In Proc. Inf. Theory and App. Workshop (ITA), 2010. Google Scholar
  37. R. Koetter and M. Medard. An algebraic approach to network coding. In Proc. IEEE Int. Symp. Inf. Theory (ISIT), June 2001. Google Scholar
  38. M. Krohn, M. Freedman, and D. Mazieres. On-the-fly verification of rateless erasure codes for efficient content distribution. In IEEE Symposium on Security and Privacy (SP), May 2004. Google Scholar
  39. L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3):382-401, July 1982. Google Scholar
  40. S. Li, R. Yeung, and N. Cai. Linear network coding. IEEE Trans. Inf. Theory, 49(2):371-381, February 2003. Google Scholar
  41. G. Liang and N. Vaidya. Error-free multi-valued consensus with Byzantine failures. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 11-20, June 2011. Google Scholar
  42. A. Loveless, R. Dreslinski, and B. Kasikci. Optimal and error-free multi-valued Byzantine consensus through parallel execution. Available on : https://eprint.iacr.org/2020/322, 2020. Google Scholar
  43. A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song. The Honey Badger of BFT protocols. In 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016. Google Scholar
  44. B. Mohanta, D. Jena, S. Panda, and S. Sobhanayak. Blockchain technology: A survey on applications and security privacy challenges. Internet of Things, 8, 2019. Google Scholar
  45. Y. Moses and O. Waarts. Coordinated traversal: (t + 1)-round Byzantine agreement in polynomial time. Journal of Algorithms, 17(1):110-156, July 1994. Google Scholar
  46. A. Mostéfaoui, H. Moumen, and M. Raynal. Signature-free asynchronous binary Byzantine consensus with t < n/3, O(n²) messages, and O(1) expected time. Journal of the ACM, 62(4), 2015. Google Scholar
  47. A. Mostéfaoui and M. Raynal. Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with t < n/3, O(n²) messages, and constant time. In Proc. 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO'15), July 2015. Google Scholar
  48. K. Nayak, L. Ren, E. Shi, N. Vaidya, and Z. Xiang. Improved extension protocols for Byzantine broadcast and agreement. In International Symposium on Distributed Computing (DISC), October 2020. Google Scholar
  49. R. Pass and E. Shi. Thunderella: Blockchains with optimistic instant confirmation. In Advances in Cryptology - EUROCRYPT 2018. Lecture Notes in Computer Science, volume 10821, pages 3-33, March 2018. Google Scholar
  50. A. Patra. Error-free multi-valued broadcast and Byzantine agreement with optimal communication complexity. In International Conference on Principles of Distributed Systems (OPODIS), pages 34-49, 2011. Google Scholar
  51. A. Patra and P. Rangan. Communication optimal multi-valued asynchronous Byzantine agreement with optimal resilience. In International Conference on Information Theoretic Security, pages 206-226, 2011. Google Scholar
  52. 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
  53. X. Qi, Z. Zhang, C. Jin, and A. Zhou. BFT-Store: Storage partition for permissioned blockchain via erasure coding. In IEEE 36th International Conference on Data Engineering, April 2020. Google Scholar
  54. M. Rabin. Randomized Byzantine generals. In 24th Annual Symposium on Foundations of Computer Science, November 1983. Google Scholar
  55. I. Reed and G. Solomon. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8(2):300-304, June 1960. Google Scholar
  56. R. Roth. Introduction to coding theory. Cambridge University Press, 2006. Google Scholar
  57. E. Shi. Streamlined blockchains: A simple and elegant approach (a tutorial and survey). Advances in Cryptology - ASIACRYPT 2019, Lecture Notes in Computer Science, 11921:3-17, November 2019. Google Scholar
  58. J. Sousa and A. Bessani. From Byzantine consensus to BFT state machine replication: A latency-optimal transformation. In 2012 Ninth European Dependable Computing Conference, May 2012. Google Scholar
  59. J. Sousa, A. Bessani, and M. Vukolic. A Byzantine fault-tolerant ordering service for the Hyperledger Fabric blockchain platform. In 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), June 2018. Google Scholar
  60. The Hyperledger White Paper Working Group. An introduction to Hyperledger. Hyperledger White Paper, 2018. Google Scholar
  61. M. Yan and A. Sprintson. On error correcting algorithms for the cooperative data exchange problem. In 2014 International Symposium on Network Coding (NetCod), June 2014. Google Scholar
  62. H. Yao and T. Ho. Distributed reed-solomon codes for simple multiple access networks, September 2015. US Patent 9,148,173. Google Scholar
  63. Z. Yu, Y. Wei, B. Ramkumar, and Y. Guan. An efficient signature-based scheme for securing network coding against pollution attacks. In IEEE International Conference on Computer Communications, April 2008. 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