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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> parties, including at least one honest party, can achieve an agreement more efficiently than relying on all n parties, where $$n=3f+1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>=</mml:mo> <mml:mn>3</mml:mn> <mml:mi>f</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> 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 $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>⌊</mml:mo> <mml:mfrac> <mml:mi>n</mml:mi> <mml:mn>3</mml:mn> </mml:mfrac> <mml:mo>⌋</mml:mo> </mml:mrow> </mml:math> Byzantine failures and achieves optimal performance, with an expected runtime of O (1), message complexity of $$O(n^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , and communication complexity of $$O((l+\lambda )n^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>l</mml:mi> <mml:mo>+</mml:mo> <mml:mi>λ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , where n is the number of parties, l is the input bit length, and $$\lambda $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>λ</mml:mi> </mml:math> is the security parameter.