Short Paper: A New Way to Achieve Round-Efficient Asynchronous Byzantine Agreement
摘要
We translate the expand-and-extract framework by Fitzi, Liu-Zhang, and Loss (PODC 21) to the asynchronous setting. While they use it to obtain a synchronous BA with \(2^{-\lambda }\) error probability in \(\lambda +1\) rounds, we achieve asynchronous BA in \(\lambda +3\) rounds. At the heart of their solution is a proxcensus primitive, which is used to reach graded agreement with \(2^r+1\) grades in r rounds by reducing proxcensus with \(2s-1\) grades to proxcensus with s grades in one round. The expand-and-extract paradigm relies on proxcensus to expand binary inputs to \(2^\lambda +1\) grades in \(\lambda \) rounds before extracting a binary output by partitioning the grades using a \(\lambda \) bit common coin. However, this proxcensus protocol does not translate to the asynchronous setting without lowering the corruption threshold or using more rounds in each recursive step. Instead, we define validated proxcensus and show that it can be instantiated in asynchrony with the same recursive structure and round complexity as synchronous proxcensus. The main technique is to attach justifiers to all messages which forces the adversary to choose between only sending useful messages or being ignored.