Prioritized-MVBA: A New Approach to Design an Optimal Asynchronous Byzantine Agreement Protocol

Abstract 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 $$f+1$$ f + 1 parties, including at least one honest party, can achieve an agreement more efficiently than relying on all n parties, where $$n=3f+1$$ n = 3 f + 1 , f 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 $$f+1$$ f + 1 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 $$\lfloor \frac{n}{3} \rfloor $$ ⌊ n 3 ⌋ Byzantine failures and achieves optimal performance, with an expected runtime of O (1), message complexity of $$O(n^2)$$ O ( n 2 ) , and communication complexity of $$O((l+\lambda )n^2)$$ O ( ( l + λ ) n 2 ) , where n is the number of parties, l is the input bit length, and $$\lambda $$ λ is the security parameter.