{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T18:12:13Z","timestamp":1771611133947,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"NSF","award":["CNS-1561209"],"award-info":[{"award-number":["CNS-1561209"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,8,31]]},"abstract":"<jats:p>\n            Byzantine Broadcast (BB) is a central question in distributed systems, and an important challenge is to understand its round complexity. Under the honest majority setting, it is long known that there exist randomized protocols that can achieve BB in expected constant rounds, regardless of the number of nodes\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            . However, whether we can match the expected constant round complexity in the corrupt majority setting \u2014or more precisely, when\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(f \\ge n\/2 + \\omega (1)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            \u2014remains unknown, where\n            <jats:italic toggle=\"yes\">f<\/jats:italic>\n            denotes the number of corrupt nodes.\n          <\/jats:p>\n          <jats:p>\n            In this article, we are the first to resolve this long-standing question. We show how to achieve BB in expected\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O((n\/(n-f))^2)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            rounds. Our results hold under a weakly adaptive adversary who cannot perform \u201cafter-the-fact removal\u201d of messages already sent by a node before it becomes corrupt. We also assume trusted setup and the Decision Linear (DLIN) assumption in bilinear groups.\n          <\/jats:p>","DOI":"10.1145\/3748254","type":"journal-article","created":{"date-parts":[[2025,7,15]],"date-time":"2025-07-15T11:27:11Z","timestamp":1752578831000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Expected Constant Round Byzantine Broadcast under Dishonest Majority"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-6357-3515","authenticated-orcid":false,"given":"Jun","family":"Wan","sequence":"first","affiliation":[{"name":"Computer Science, Massachusetts Institute of Technology","place":["Cambridge, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3380-4518","authenticated-orcid":false,"given":"Hanshen","family":"Xiao","sequence":"additional","affiliation":[{"name":"Purdue University","place":["West Lafayette, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5605-1048","authenticated-orcid":false,"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University","place":["Pittsburgh, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8253-7714","authenticated-orcid":false,"given":"Srinivas","family":"Devadas","sequence":"additional","affiliation":[{"name":"Computer Science, Massachusetts Institute of Technology","place":["Cambridge, United States"]}]}],"member":"320","published-online":{"date-parts":[[2025,8,8]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331629"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32101-7_20"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.OPODIS.2017.25"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/844128.844130"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/3081770.3081773"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90054-X"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s001459910006"},{"key":"e_1_3_3_9_2","first-page":"173","volume-title":"Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI \u201999)","author":"Castro Miguel","year":"1999","unstructured":"Miguel Castro and Barbara Liskov. 1999. Practical byzantine fault tolerance. In Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI \u201999). USENIX Association, USA, 173\u2013186."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45388-6_9"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32101-7_2"},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1007\/978-3-319-78375-8_3","volume-title":"Proceedings of the Advances in Cryptology \u2013 EUROCRYPT 2018","author":"David Bernardo","year":"2018","unstructured":"Bernardo David, Peter Ga\u017ei, Aggelos Kiayias, and Alexander Russell. 2018. Ouroboros praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain. In Proceedings of the Advances in Cryptology \u2013 EUROCRYPT 2018, Jesper Buus Nielsen and Vincent Rijmen (Eds.). Springer International Publishing, Cham, 66\u201398."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/0212045"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/42282.42283"},{"key":"e_1_3_3_15_2","unstructured":"Ryan Farell. 2015. An analysis of the cryptocurrency industry. (2015). Retrieved from https:\/\/api.semanticscholar.org\/CorpusID:6943154"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.14"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62225"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790187084"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/1813164.1813222"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993832"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.61"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46803-6_10"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3566048"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132757"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220358"},{"key":"e_1_3_3_26_2","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1007\/978-3-642-13190-5_24","volume-title":"Proceedings of the Advances in Cryptology \u2013 EUROCRYPT 2010","author":"Hirt Martin","year":"2010","unstructured":"Martin Hirt and Vassilis Zikas. 2010. Adaptively secure broadcast. In Proceedings of the Advances in Cryptology \u2013 EUROCRYPT 2010, Henri Gilbert (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 466\u2013485."},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.08.001"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/279227.279229"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_3_3_30_2","first-page":"120","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS \u201999)","author":"Micali Silvio","year":"1999","unstructured":"Silvio Micali, Salil Vadhan, and Michael Rabin. 1999. Verifiable random functions. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS \u201999). IEEE Computer Society, USA, 120."},{"key":"e_1_3_3_31_2","unstructured":"Satoshi Nakamoto. 2009. Bitcoin: A peer-to-peer electronic cash system. (May2009). Retrieved from http:\/\/www.bitcoin.org\/bitcoin.pdf"},{"key":"e_1_3_3_32_2","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1007\/978-3-319-56614-6_22","volume-title":"Proceedings of the Advances in Cryptology \u2013 EUROCRYPT 2017","author":"Pass Rafael","year":"2017","unstructured":"Rafael Pass, Lior Seeman, and Abhi Shelat. 2017. Analysis of the blockchain protocol in asynchronous networks. In Proceedings of the Advances in Cryptology \u2013 EUROCRYPT 2017, Jean-S\u00e9bastien Coron and Jesper Buus Nielsen (Eds.). Springer International Publishing, Cham, 643\u2013673."},{"key":"e_1_3_3_33_2","volume-title":"Proceedings of the International Symposium on Distributed Computing","author":"Pass Rafael","year":"2016","unstructured":"Rafael Pass and Elaine Shi. 2016. Hybrid consensus: Efficient consensus in the permissionless model. In Proceedings of the International Symposium on Distributed Computing. Retrieved from https:\/\/api.semanticscholar.org\/CorpusID:1171104"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087809"},{"key":"e_1_3_3_35_2","volume-title":"Proceedings of the CSF","author":"Pass Rafael","year":"2017","unstructured":"Rafael Pass and Elaine Shi. 2017. Rethinking large-scale consensus (invited paper). In Proceedings of the CSF."},{"key":"e_1_3_3_36_2","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1007\/978-3-319-70697-9_14","volume-title":"Proceedings of the Advances in Cryptology \u2013 ASIACRYPT 2017","author":"Pass Rafael","year":"2017","unstructured":"Rafael Pass and Elaine Shi. 2017. The sleepy model of consensus. In Proceedings of the Advances in Cryptology \u2013 ASIACRYPT 2017, Tsuyoshi Takagi and Thomas Peyrin (Eds.). Springer International Publishing, Cham, 380\u2013409."},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64375-1_15"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3748254","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,8]],"date-time":"2025-08-08T12:48:57Z","timestamp":1754657337000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3748254"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,8]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,31]]}},"alternative-id":["10.1145\/3748254"],"URL":"https:\/\/doi.org\/10.1145\/3748254","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,8]]},"assertion":[{"value":"2021-01-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-02","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}