Pako: Multi-Valued Byzantine Agreement Comparable to Partially-Synchronous BFT
Xiaohai Dai, Zhengxuan Guo, Jiang Qing Xiao, Guanxiong Wang, Yifei Liang, Chen Yu, Hai Jin · IEEE Transactions on Computers · 2024
AsynchronousByzantine Fault Tolerance(BFT) consensus protocols are gaining attention for their resilience against network attacks. Among them,Multi-valued Byzantine Agreement(MVBA) protocols play a critical role, which accepts input values from each replica and returns a consistent output. The state-of-the-art MVBA protocol, sMVBA, has a good-case latency of$6\delta$and an expected bad-case latency of$12\delta$, with$\delta$representing the network delay. Additionally, sMVBA exhibits a communication of$O(n^{2})$in both good and bad cases. Although it outperforms other MVBA protocols, sMVBA still lags behind partially-synchronous counterparts. For instance, PBFT achieves a good-case latency of$3\delta$, and HotStuff boasts a good-case communication of$O(n)$. This paper introduces a novel MVBA protocol, Pako, aiming for performance comparable to partially-synchronous protocols. Pako leverages an existing MVBA protocol as a black box and introduces an additional view with an optimistic path to commit values efficiently. Two Pako variants, Pako1 and Pako2, provide a trade-off between latency and communication. To be more specific, Pako1 achieves a good-case latency of$3\delta$with$O(n^{2})$communication, while Pako2 reduces the communication to$O(n)$with a slightly higher good-case latency of$5\delta$. A series of experiments demonstrate Pako's significant outperformance of counterparts.