More Web Proxy on the site http://driver.im/

research-article

Broadcast Extensions with Optimal Communication and Round Complexity

Authors:

Arpita PatraAuthors Info & Claims

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

Pages 371 - 380

https://doi.org/10.1145/2933057.2933082

Published: 25 July 2016 Publication History

Abstract

The problem of broadcast and Byzantine Agreement are of interest to both distributed computing and cryptography community. Often these primitives require prohibitive communication and round complexity. Broadcast extensions have been introduced to broadcast long messages at the cost of small number of broadcasts for bit. The latter are referred to as seed broadcasts.

In a setting with n parties and an adversary controlling at most t parties in Byzantine fashion such that t < n, we present a broadcast extension that is simultaneously optimal in terms of communication complexity and round complexity. Specifically, we achieve O(l n) bits of communication complexity for a message of length l bits and O(n) round complexity. The known broadcast extension protocol in the same setting was only communication optimal.

A concrete broadcast extension protocol is obtained when the seed broadcasts are instantiated with broadcast protocols for bit. Our optimal broadcast extension protocol in t < n setting leads to concrete extension protocols that improve the round complexity of existing concrete extension protocols by a factor of Ω(n). We also improve the state-of-the-art round complexity of the communication optimal concrete broadcast extension protocol in t < n/2 setting. The result comes as a corollary of a new extension protocol that improves both the round complexity as well as the seed round complexity of the existing extension protocols for t < n/2. The seed round complexity is defined as the number of rounds in which a broadcast for bit is invoked.

References

[1]

Piotr Berman, Juan A Garay, and Kenneth J Perry. Bit optimal distributed consensus. In Computer science, pages 313--321. Springer, 1992.

[2]

Zuzana Beerliová-Trubíıniová and Martin Hirt. Efficient multi-party computation with dispute control. In Theory of Cryptography, pages 305--328. Springer, 2006.

Digital Library

[3]

Ronald Cramer, Rosario Gennaro, and Berry Schoenmakers. A secure and optimally efficient multi-authority election scheme. In Advances in Cryptology - EUROCRYPT 1997, pages 103--118. Springer, 1997.

[4]

Brian A Coan and Jennifer L Welch. Modular construction of a byzantine agreement protocol with optimal message bit complexity. Information and Computation, 97(1):61--85, 1992.

Digital Library

[5]

Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for byzantine agreement. J. ACM, 32(1):191--204, 1985.

Digital Library

[6]

Danny Dolev and H. Raymond Strong. Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656--666, 1983.

Digital Library

[7]

Shimon Even, Oded Goldreich, and Abraham Lempel. A randomized protocol for signing contracts. Communications of the ACM, 28(6):637--647, 1985.

Digital Library

[8]

Matthias Fitzi and Martin Hirt. Optimally efficient multi-valued byzantine agreement. In Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 163--168. ACM, 2006.

Digital Library

[9]

Pesech Feldman and Silvio Micali. An optimal probabilistic protocol for synchronous byzantine agreement. SIAM Journal on Computing, 26(4):873--933, 1997.

Digital Library

[10]

Juan Garay, Jonathan Katz, Chiu-Yuen Koo, and Rafail Ostrovsky. Round complexity of authenticated broadcast with a dishonest majority. In Foundations of Computer Science, 2007. FOCS'07, pages 658--668. IEEE, 2007.

Digital Library

[11]

Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 218--229. ACM, 1987.

Digital Library

[12]

Martin Hirt and Pavel Raykov. Multi-valued byzantine broadcast: The( t<n) case. In Advances in Cryptology--ASIACRYPT 2014, pages 448--465. Springer, 2014.

[13]

Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. Extending oblivious transfers efficiently. In Advances in Cryptology-CRYPTO 2003, pages 145--161. Springer, 2003.

[14]

Jonathan Katz and Chiu-Yuen Koo. On expected constant-round protocols for byzantine agreement. In Advances in Cryptology - CRYPTO 2006, pages 445--462, 2006.

Digital Library

[15]

Leslie Lamport and Michael Fischer. Byzantine generals and transaction commit protocols. Technical report, Technical Report 62, SRI International, 1982.

[16]

Guanfeng Liang and Nitin Vaidya. Error-free multi-valued consensus with byzantine failures. In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 11--20. ACM, 2011.

Digital Library

[17]

Arpita Patra. Error-free multi-valued broadcast and byzantine agreement with optimal communication complexity. In Proceedings of Principles of Distributed Systems - 15th International Conference, OPODIS 2011, pages 34--49, 2011.

Digital Library

[18]

Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. Journal of the ACM (JACM), 27(2):228--234, 1980.

Digital Library

[19]

Birgit Pfitzmann and Michael Waidner. Information-theoretic pseudosignatures and byzantine agreement for t ≥ n/3. Technical Report RZ 2882, IBM Research, 1996.

[20]

R. Turpin and B. A. Coan. Extending binary Byzantine Agreement to multivalued Byzantine Agreement. Information Processing Letters, 18(2):73--76, 1984.

[21]

Andrew Chi-Chih Yao. Some complexity questions related to distributive computing(preliminary report). In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, pages 209--213. ACM, 1979.

Digital Library

Cited By

Ghinea DLiu-Zhang CWattenhofer RKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Communication-Optimal Convex AgreementProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662782(492-495)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662782
Dutta MGanesh CPatranabis SSingh N(2024)Compute, but Verify: Efficient Multiparty Computation over Authenticated InputsAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0938-3_5(133-166)Online publication date: 12-Dec-2024
https://doi.org/10.1007/978-981-96-0938-3_5
Lyu HXie SNiu JFeng C(2024)Byzantine Protocols with Asymptotically Optimal Communication ComplexitySecurity and Privacy in Communication Networks10.1007/978-3-031-64948-6_13(247-264)Online publication date: 13-Oct-2024
https://doi.org/10.1007/978-3-031-64948-6_13
Show More Cited By

Index Terms

Broadcast Extensions with Optimal Communication and Round Complexity
1. Theory of computation
  1. Computational complexity and cryptography
    1. Cryptographic primitives
    2. Cryptographic protocols

Recommendations

Optimal extension protocols for byzantine broadcast and agreement
Abstract
The problems of Byzantine Broadcast (BB) and Byzantine Agreement (BA) are of interest to both the distributed computing and cryptography communities. Extension protocols for these primitives have been introduced to handle long messages efficiently ...
$\sqrt{}^{}$
$^{}$
$\sqrt{}^{}$ $^{}$
Error-free multi-valued broadcast and byzantine agreement with optimal communication complexity
OPODIS'11: Proceedings of the 15th international conference on Principles of Distributed Systems

In this paper we present first ever error-free, asynchronous broadcast (called as A-cast) and Byzantine Agreement (called as ABA) protocols with optimal communication complexity and fault tolerance. Our protocols are multi-valued, meaning that they deal ...
Asymptotically Free Broadcast in Constant Expected Time via Packed VSS
Theory of Cryptography
Abstract
Broadcast is an essential primitive for secure computation. We focus in this paper on optimal resilience (i.e., when the number of corrupted parties t is less than a third of the computing parties n), and with no setup or cryptographic ...
$^{}^{}$
$^{}$ $^{}$ $^{}$ $^{}$ $^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing

July 2016

508 pages

ISBN:9781450339643

DOI:10.1145/2933057

General Chair:
George Giakkoupis
INRIA, France

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '16

Sponsor:

PODC '16: ACM Symposium on Principles of Distributed Computing

July 25 - 28, 2016

Illinois, Chicago, USA

Acceptance Rates

PODC '16 Paper Acceptance Rate 40 of 149 submissions, 27%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
209
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)3

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghinea DLiu-Zhang CWattenhofer RKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Communication-Optimal Convex AgreementProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662782(492-495)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662782
Dutta MGanesh CPatranabis SSingh N(2024)Compute, but Verify: Efficient Multiparty Computation over Authenticated InputsAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0938-3_5(133-166)Online publication date: 12-Dec-2024
https://doi.org/10.1007/978-981-96-0938-3_5
Lyu HXie SNiu JFeng C(2024)Byzantine Protocols with Asymptotically Optimal Communication ComplexitySecurity and Privacy in Communication Networks10.1007/978-3-031-64948-6_13(247-264)Online publication date: 13-Oct-2024
https://doi.org/10.1007/978-3-031-64948-6_13
Liu-Zhang CMatt CThomsen S(2024)Asymptotically Optimal Message Dissemination with Applications to BlockchainsAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58734-4_3(64-95)Online publication date: 1-May-2024
https://doi.org/10.1007/978-3-031-58734-4_3
Wan JMomose ARen LShi EXiang ZOshman RNolin AHalldorsson MBalliu A(2023)On the Amortized Communication Complexity of Byzantine BroadcastProceedings of the 2023 ACM Symposium on Principles of Distributed Computing10.1145/3583668.3594596(253-261)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3583668.3594596
Hou RYu H(2023)Optimistic Fast Confirmation While Tolerating Malicious Majority in Blockchains2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179323(2481-2498)Online publication date: May-2023
https://doi.org/10.1109/SP46215.2023.10179323
Damgård IRavi DSiniscalchi LYakoubov S(2023)Minimizing Setup in Broadcast-Optimal Two Round MPCAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30617-4_5(129-158)Online publication date: 15-Apr-2023
https://doi.org/10.1007/978-3-031-30617-4_5
Bhangale ALiu-Zhang CLoss JNayak K(2023)Efficient Adaptively-Secure Byzantine Agreement for Long MessagesAdvances in Cryptology – ASIACRYPT 202210.1007/978-3-031-22963-3_17(504-525)Online publication date: 25-Jan-2023
https://doi.org/10.1007/978-3-031-22963-3_17
Hou RYu HSaxena P(2022)Using Throughput-Centric Byzantine Broadcast to Tolerate Malicious Majority in Blockchains2022 IEEE Symposium on Security and Privacy (SP)10.1109/SP46214.2022.9833617(1263-1280)Online publication date: May-2022
https://doi.org/10.1109/SP46214.2022.9833617
Garay JKiayias AAnta AGeorgiou CHerlihy MPotop-Butucaru M(2022)A Consensus Taxonomy in the Blockchain EraPrinciples of Blockchain Systems10.1007/978-3-031-01807-7_2(27-68)Online publication date: 18-Mar-2022
https://doi.org/10.1007/978-3-031-01807-7_2
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents