Sublinear-Round Byzantine Agreement Under Corrupt Majority

Abstract

Although Byzantine Agreement (BA) has been studied for three decades, perhaps somewhat surprisingly, there still exist significant gaps in our understanding regarding its round complexity. A long-standing open question is the following: can we achieve BA with sublinear round complexity under corrupt majority? Due to the beautiful works by Garay et al. (FOCS’07) and Fitzi and Nielsen (DISC’09), we have partial and affirmative answers to this question albeit for the narrow regime f=n/2+o(n) where f is the number of corrupt nodes and n is the total number of nodes. So far, no positive result is known about the setting f>0.51n even for static corruption! In this paper, we make progress along this somewhat stagnant front. We show that there exists a corrupt-majority BA protocol that terminates in O(1ϵlog1δ) rounds in the worst case, satisfies consistency with probability at least 1−δ , and tolerates (1−ϵ) fraction of corrupt nodes. Our protocol secures against an adversary that can corrupt nodes adaptively during the protocol execution but cannot perform “after-the-fact” removal of honest messages that have already been sent prior to corruption. Our upper bound is optimal up to a logarithmic factor in light of the elegant Ω(1/ϵ) lower bound by Garay et al. (FOCS’07).