{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T09:58:51Z","timestamp":1776074331231,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T00:00:00Z","timestamp":1770681600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T00:00:00Z","timestamp":1770681600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int. J. Inf. Secur."],"abstract":"Abstract<\/jats:title>\n \n Multi-valued Byzantine agreement (MVBA) protocols are critical components in designing atomic broadcast and fault-tolerant state machine replication protocols in asynchronous networks. While these protocols have seen significant advancements, challenges remain in optimizing their communication and computation efficiency without sacrificing performance. In this paper, we address the challenge of achieving agreement in MVBA without incurring extra computation and communication rounds. Our approach leverages an analysis of message distribution patterns in asynchronous networks, observing that a subset of\n \n \n $$f+1$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n parties, including at least one honest party, can achieve an agreement more efficiently than relying on all\n n<\/jats:italic>\n parties, where\n \n \n $$n=3f+1$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n =<\/mml:mo>\n 3<\/mml:mn>\n f<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n f<\/jats:italic>\n maximum number of faulty parties. We introduce a novel protocol, Prioritized-MVBA (pMVBA), which integrates a committee-based selection process and the asynchronous binary Byzantine agreement (ABBA) protocol. In this design, a randomly selected subset of\n \n \n $$f+1$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n parties broadcast their requests, collect verifiable proofs, and utilize these proofs within the ABBA framework to reach an agreement. The proposed pMVBA protocol is resilient to up to\n \n \n $$\\lfloor \\frac{n}{3} \\rfloor $$<\/jats:tex-math>\n \n \n \u230a<\/mml:mo>\n \n n<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:mfrac>\n \u230b<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n Byzantine failures and achieves optimal performance, with an expected runtime of\n O<\/jats:italic>\n (1), message complexity of\n \n \n $$O(n^2)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and communication complexity of\n \n \n $$O((l+\\lambda )n^2)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n (<\/mml:mo>\n l<\/mml:mi>\n +<\/mml:mo>\n \u03bb<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , where\n n<\/jats:italic>\n is the number of parties,\n l<\/jats:italic>\n is the input bit length, and\n \n \n $$\\lambda $$<\/jats:tex-math>\n \n \u03bb<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is the security parameter.\n <\/jats:p>","DOI":"10.1007\/s10207-026-01214-4","type":"journal-article","created":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T12:19:02Z","timestamp":1770725942000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Prioritized-MVBA: A New Approach to Design an Optimal Asynchronous Byzantine Agreement Protocol"],"prefix":"10.1007","volume":"25","author":[{"given":"Nasit S","family":"Sony","sequence":"first","affiliation":[]},{"given":"Xianzhong","family":"Ding","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,10]]},"reference":[{"key":"1214_CR1","unstructured":"Nakamoto, S.: A peer-to-peer electronic cash system. (2008). http:\/\/bitcon.org\/bitcoin.pdf"},{"key":"1214_CR2","unstructured":"Buterin, V.: A next-generation smart contract and decentralized application platform. In: White Paper (2014)"},{"key":"1214_CR3","unstructured":"Cachin, C., Vukolic, M.: Blockchain consensus protocols in the wild (keynote talk). In: 31st International Symposium on Distributed Computing, DISC 2017, Vienna, Austria (2017)"},{"key":"1214_CR4","doi-asserted-by":"publisher","unstructured":"Abraham, I., Malkhi, D., Spiegelman, A.: Asymptotically optimal validated asynchronous byzantine agreement. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, Toronto, Canada, pp. 879\u2013888 (2019). https:\/\/doi.org\/10.1145\/3293611.33316","DOI":"10.1145\/3293611.33316"},{"key":"1214_CR5","unstructured":"Castro, M., Liskov, B.: Practical byzantine fault tolerance. In: OSDI, pp. 656\u2013666 (1999)"},{"key":"1214_CR6","doi-asserted-by":"crossref","unstructured":"Miller, A., Xia, Y., Croman, K.: Elaine Shi, and Dawn Song: The honey badger of BFT protocols. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communication Security, CCS\u201916. ACM Press, New York, NY, USA (2016)","DOI":"10.1145\/2976749.2978399"},{"key":"1214_CR7","doi-asserted-by":"crossref","unstructured":"Pass, R., Shi, E.: Rethinking large-scale consensus. (2017)","DOI":"10.1109\/CSF.2017.37"},{"key":"1214_CR8","doi-asserted-by":"crossref","unstructured":"Shrestha, N., Abraham, I., Nayak, K., Ren, L.: On the optimality of optimistic responsiveness. (2020)","DOI":"10.1145\/3372297.3417284"},{"key":"1214_CR9","doi-asserted-by":"publisher","unstructured":"Yin, M., Malkhi, D., Reiter, M.K., Gueta, G.G., Abraham, I.: Hotstuff: Bft consensus with linearity and responsiveness. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pp. 347\u2013356 (2019). https:\/\/doi.org\/10.1145\/3293611.3331591","DOI":"10.1145\/3293611.3331591"},{"issue":"2","key":"1214_CR10","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"MJ Fischer","year":"1985","unstructured":"Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374\u2013382 (1985). https:\/\/doi.org\/10.1145\/3149.214121","journal-title":"J. ACM"},{"key":"1214_CR11","doi-asserted-by":"crossref","unstructured":"Duan, S., Reiter, M.K., Zhang, H.: Beat: asynchronous bft made practical. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS. ACM, Toronto, ON, Canada (2018)","DOI":"10.1145\/3243734.3243812"},{"key":"1214_CR12","doi-asserted-by":"publisher","unstructured":"Guo, B., Lu, Z., Tang, Q., Xu, J., Zhang, Z.: Dumbo: Faster asynchronous bft protocols. In: Proceedings of the ACM Conference on Computer and Communications Security, pp. 803\u2013818 (2020). https:\/\/doi.org\/10.1145\/3372297.3417262","DOI":"10.1145\/3372297.3417262"},{"key":"1214_CR13","doi-asserted-by":"crossref","unstructured":"Lu, Y., Lu, Z., Tang, Q., Wang, G.: Dumbo-mvba: Optimal multi-valued validated asynchronous byzantine agreement, revisited. In: Proceedings of the 39th Symposium on Principles of Distributed Computing (2020)","DOI":"10.1145\/3382734.3405707"},{"key":"1214_CR14","doi-asserted-by":"publisher","unstructured":"Guo, B., Lu, Y., Lu, Z., Tang, Q., Xu, J., Zhang, Z.: Speeding dumbo: Pushing asynchronous bft closer to practice. Network and Distributed Systems Security (NDSS) Symposium, ??? (2022). https:\/\/doi.org\/10.14722\/ndss.2022.24385","DOI":"10.14722\/ndss.2022.24385"},{"key":"1214_CR15","doi-asserted-by":"crossref","unstructured":"Gelashvili, R., Kokoris-Kogias, L., Sonnino, A., Spiegelman, A., Xiang, Z.: Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback. (2021). arXiv:2106.10362","DOI":"10.1007\/978-3-031-18283-9_14"},{"key":"1214_CR16","doi-asserted-by":"crossref","unstructured":"Lu, Y., Lu, Z., Tang, Q.: Bolt-dumbo transformer: Asynchronous consensus as fast as pipelined bft. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (2021). arXiv:2103.09425","DOI":"10.1145\/3548606.3559346"},{"key":"1214_CR17","doi-asserted-by":"crossref","unstructured":"Keidar, I., Kokoris-Kogias, E., Naor, O., Spiegelman, A.: All you need is dag. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pp. 165\u2013175 (2021)","DOI":"10.1145\/3465084.3467905"},{"key":"1214_CR18","doi-asserted-by":"crossref","unstructured":"Cachin, C., Kursawe, K., Lysyanskaya, A., Strobl, R.: Asynchronous verifiable secret sharing and proactive cryptosystems. In: Proceedings of the 9th ACM Conference on Computer and Communications Security, pp. 88\u201397 (2002)","DOI":"10.1145\/586110.586124"},{"key":"1214_CR19","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s00236-016-0269-y","volume":"54","author":"A Mostefaoui","year":"2017","unstructured":"Mostefaoui, A., Raynal, M.: Signature-free asynchronous byzantine systems: from multivalued to binary binary consensus with $$t < n\/3$$, $$o(n^3)$$ messages, and constant time. Acta Inform. 54, 501\u2013520 (2017)","journal-title":"Acta Inform."},{"key":"1214_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2785953","volume":"62","author":"A Mostefaoui","year":"2015","unstructured":"Mostefaoui, A., Moumen, H., Raynal, M.: Signature-free asynchronous binary byzantine consensus with $$t < n\/3$$, $$o(n^2)$$ messages, and $$o(1)$$ expected time. J. ACM 62, 1\u201321 (2015)","journal-title":"J. ACM"},{"key":"1214_CR21","doi-asserted-by":"crossref","unstructured":"Cachin, C., Kursawe, K., Petzold, F., Shoup, V.: Secure and Efficient Asynchronous Broadcast Protocols. Cryptology ePrint Archive, Paper 2001\/006 (2001). https:\/\/eprint.iacr.org\/2001\/006","DOI":"10.1007\/3-540-44647-8_31"},{"key":"1214_CR22","doi-asserted-by":"crossref","unstructured":"Cachin, C., Kursawe, K., Shoup, V.: Random oracles in constantinople: Practical asynchronous byzantine agreement using cryptography. In: Journal of Cryptology (2000)","DOI":"10.1145\/343477.343531"},{"issue":"2","key":"1214_CR23","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/0217017","volume":"17","author":"S Goldwasser","year":"1988","unstructured":"Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281\u2013308 (1988). https:\/\/doi.org\/10.1137\/0217017","journal-title":"SIAM J. Comput."},{"key":"1214_CR24","doi-asserted-by":"crossref","unstructured":"Libert, B., Joye, M., Yung, M.: Born and raised distributively: Fully distributed non-interactive adaptively-secure threshold signatures with short shares. In: Theory of Computer Science, vol. 645, pp. 1\u201324 (2016)","DOI":"10.1016\/j.tcs.2016.02.031"},{"key":"1214_CR25","doi-asserted-by":"crossref","unstructured":"Boldyreva, A.: Threshold signatures, multisignatures and blind signatures based on the gap-diffie-hellman-group signature scheme. In: Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography. PKC \u201903, pp. 31\u201346. Springer, Berlin, Heidelberg (2003)","DOI":"10.1007\/3-540-36288-6_3"},{"key":"1214_CR26","doi-asserted-by":"crossref","unstructured":"Kate, A., Goldberg, I.: Distributed key generation for the internet. In: IEEE International Conference on Distributed Computing Systems, pp. 119\u2013128 (2009)","DOI":"10.1109\/ICDCS.2009.21"},{"key":"1214_CR27","unstructured":"Shoup, V.: Practical threshold signatures. In: Advances in Cryptology\u2013EUROCRYPT 2000: International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000 Proceedings 19, pp. 207\u2013220 (2000). Springer. https:\/\/link.springer.com\/chapter\/10.1007\/3-540-45539-6_15"},{"key":"1214_CR28","doi-asserted-by":"crossref","unstructured":"Cohen, S., Keidar, I., Spiegelman, A.: Brief announcement: Not a coincidence: Sub-quadratic asynchronous byzantine agreement whp. In: Proceedings of the 39th Symposium on Principles of Distributed Computing, pp. 175\u2013177 (2020)","DOI":"10.1145\/3382734.3405708"},{"key":"1214_CR29","doi-asserted-by":"crossref","unstructured":"Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: Scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles, pp. 51\u201368 (2017)","DOI":"10.1145\/3132747.3132757"},{"issue":"3","key":"1214_CR30","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L Lamport","year":"1982","unstructured":"Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382\u2013401 (1982)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"1214_CR31","unstructured":"Buchman, E.: Tendermint: Byzantine fault tolerance in the age of blockchains. PhD Thesis, University of Guelph (2014)"},{"key":"1214_CR32","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In: Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, 3 (1983)","DOI":"10.1145\/800221.806707"},{"key":"1214_CR33","doi-asserted-by":"crossref","unstructured":"Sony, N.S.: An efficient validated asynchronous byzantine agreement protocol using committee. arXiv preprint arXiv:2501.00717 (2025)","DOI":"10.1145\/3700838.3703660"},{"key":"1214_CR34","doi-asserted-by":"publisher","unstructured":"Sony, N.S., Ding, X.: A committee based optimal asynchronous byzantine agreement protocol w.p. 1. In: Proceedings of the 26th International Conference on Distributed Computing and Networking. ICDCN \u201925, pp. 282\u2013283. Association for Computing Machinery, New York, NY, USA (2025). https:\/\/doi.org\/10.1145\/3700838.3703660","DOI":"10.1145\/3700838.3703660"},{"key":"1214_CR35","unstructured":"Sony, N.S.: An Approach to Optimizing the VABA Protocol Using $$\\kappa $$-size Committee. arXiv preprint arXiv:2412.03789 (2024)"},{"key":"1214_CR36","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s44227-025-00071-2","volume":"13","author":"N Sony","year":"2025","unstructured":"Sony, N., Ding, X., Singhal, M.: Slim-ABC: An Optimized Atomic Broadcast Protocol. Int J Netw Distrib Comput 13, 27 (2025)","journal-title":"Int J Netw Distrib Comput"},{"key":"1214_CR37","unstructured":"Sony, N. S., Ding, X., Singhal, M.: Optimizing Communication in Byzantine Agreement Protocols with Slim-HBBFT. In: Euro-Par (2024). https:\/\/easychair.org\/publications\/preprint\/Zs8Mw\/open"},{"key":"1214_CR38","doi-asserted-by":"crossref","unstructured":"Kursawe, K., Shoup, V.: Optimistic asynchronous atomic broadcast. In: International Colloquium on Automata, Languages, and Programming, pp. 204\u2013215 (2005)","DOI":"10.1007\/11523468_17"},{"key":"1214_CR39","doi-asserted-by":"publisher","unstructured":"Cachin, C., Kursawe, K., Lysyanskaya, A., Strobl, R.: Asynchronous verifiable secret sharing and proactive cryptosystems. In: Proceedings of the 9th ACM Conference on Computer and Communications Security. CCS \u201902, pp. 88\u201397. Association for Computing Machinery, New York, NY, USA (2002). https:\/\/doi.org\/10.1145\/586110.586124","DOI":"10.1145\/586110.586124"},{"key":"1214_CR40","doi-asserted-by":"publisher","unstructured":"Gagol, A., Lesniak, D., Straszak, D., Swietek, M.: Aleph: Efficient atomic broadcast in asynchronous networks with byzantine nodes. In: Proceedings of the 1st ACM Conference on Advances in Financial Technologies. AFT \u201919, pp. 214\u2013228. Association for Computing Machinery, New York, NY, USA (2019). https:\/\/doi.org\/10.1145\/3318041.3355467","DOI":"10.1145\/3318041.3355467"},{"issue":"3","key":"1214_CR41","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/2402.322398","volume":"30","author":"L Lamport","year":"1983","unstructured":"Lamport, L.: The weak byzantine generals problem. J. ACM 30(3), 668\u2013676 (1983). https:\/\/doi.org\/10.1145\/2402.322398","journal-title":"J. ACM"},{"issue":"4","key":"1214_CR42","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O Goldreich","year":"1986","unstructured":"Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792\u2013807 (1986). https:\/\/doi.org\/10.1145\/6490.6503","journal-title":"J. ACM"}],"container-title":["International Journal of Information Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10207-026-01214-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10207-026-01214-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10207-026-01214-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T09:17:17Z","timestamp":1776071837000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10207-026-01214-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,10]]},"references-count":42,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2026,4]]}},"alternative-id":["1214"],"URL":"https:\/\/doi.org\/10.1007\/s10207-026-01214-4","relation":{},"ISSN":["1615-5270"],"issn-type":[{"value":"1615-5270","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,10]]},"assertion":[{"value":"19 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Financial interests:\n Author Nasit S. Sony receives salaries as a teaching assistant from the University of California, Merced. Author Xianzhong Ding receives salaries as a postdoctoral scholar from Lawrence Berkeley National Laboratory.\n Non-financial interests:\n none.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest\/Competing Interests"}},{"value":"The authors declare no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"50"}}