How to reduce the number of steps for (multi-valued validated) Byzantine agreement?

Multi-valued validated Byzantine agreement (MVBA), a notion of Cachin, Kursawe, Petzold, and Shoup (CKPS), is a core primitive in fault-tolerant distributed computing and can be used to build asynchronous Byzantine atomic broadcast, Byzantine fault-tolerant state machine replication, and asynchronous distributed key generation protocols. Recently, a major breakthrough by Abraham, Malkhi, and Spiegelman (AMS) improves the CKPS construction with optimal word complexity and on average 19.5 steps. Lu, Lu, Tang, and Wang propose Dumbo-MVBA using erasure coding to reduce the communication of AMS MVBA and Dumbo-MVBA* which is a self-bootstrap framework transforming any MVBA into a communication-efficient implementation. This paper introduces a new way of building MVBA that shares the same communication as Dumbo-MVBA but has about 7/25 as many steps as Dumbo-MVBA. A central building block for our MVBA is a new distributed computing primitive—verifiable and validated asynchronous consistent information dispersal (VVCID) that is of independent interest. We provide two instantiations, one being based on fingerprinted cross-checksum (Hendricks, Ganger, and Reiter), and the other relying on erasure-coding proof systems (Alhaddad, Duan, Varia, and Zhang). We further show that in the case where n>4f, we can build even more efficient protocols. In particular, we present the first asynchronous binary agreement (ABA) protocol that has strictly 2 steps in each round and achieves optimal word complexity, while prior such protocols require n>5f. Our ABA additionally has a new biased validity property allowing us to optimize our MVBA framework further: our new MVBA for n>4f has about one fifth as many steps as Dumbo-MVBA.