The multi-valued byzantine agreement protocol (MVBA) in the authenticated setting has been widely used as a core to design atomic broadcast and fault-tolerant state machine replication protocols in asynchronous networks. Originating from the seminal work of Cachin et al. \cite{CACHIN01}, subsequent research endeavors have sought to optimize protocol efficiency in terms of communication complexity. Notable advancements following Cachin's contributions include: i) VABA \cite{BYZ17}, requiring multiple protocol instances to achieve agreement on a party's request, and ii) Dumbo-MVBA \cite{LU20}, employing a cryptographic asynchronous dispersal and recovery methods to manage communication complexity alongside additional computational and communication rounds overheads. Our objective is to devise an MVBA protocol that achieves agreement in each instance without extra computation and communication rounds while maintaining the optimal metrics. Central to our design approach is the introduction of the committee in the classic MVBA protocol, wherein a randomly selected subset of ($f+1$, where $n=3f+1$) parties get selected and simultaneously broadcast their requests (transactions) to gather verifiable proofs. Successive distributions of these proofs afford us the necessary properties to employ the asynchronous binary Byzantine agreement (ABBA) protocol for reaching an agreement on a selected party's requests. By integrating the committee and ABBA protocols, we devise the optimal MVBA protocol, termed pMVBA (Prioritized-MVBA). This protocol exhibits resilience to tolerate up to $\lfloor \frac{n}{3}\rfloor$ Byzantine failures, with an expected runtime of $O(1)$, optimal message complexity of $O(n^2)$, and optimal communication complexity $O((l+λ)n^2)$ .

翻译：在认证环境下的多值拜占庭共识协议（MVBA）已被广泛用作异步网络中设计原子广播和容错状态机复制协议的核心。自Cachin等人开创性工作\\cite{CACHIN01}以来，后续研究致力于在通信复杂度方面优化协议效率。Cachin贡献后的显著进展包括：i）VABA \\cite{BYZ17}，需要多个协议实例以实现对参与方请求的共识；ii）Dumbo-MVBA \\cite{LU20}，采用密码学异步分发与恢复方法来管理通信复杂度，同时带来额外的计算和通信轮次开销。我们的目标是设计一种MVBA协议，能在每个实例中达成共识，无需额外计算和通信轮次，同时保持最优指标。我们设计方法的核心是在经典MVBA协议中引入委员会机制，其中随机选取（$f+1$，满足$n=3f+1$）个参与方组成子集，并同时广播其请求（交易）以收集可验证证明。这些证明的连续分发为我们提供了必要特性，从而可利用异步二进制拜占庭共识（ABBA）协议对选定参与方的请求达成共识。通过整合委员会与ABBA协议，我们设计了最优MVBA协议，称为pMVBA（优先化多值拜占庭共识协议）。该协议能容忍最多$\\lfloor \\frac{n}{3}\\rfloor$个拜占庭故障，具有$O(1)$的期望运行时间、$O(n^2)$的最优消息复杂度以及$O((l+λ)n^2)$的最优通信复杂度。