Quanquan Liu: A Lower Bound for Byzantine Agreement and Consensus for Adaptive Adversaries using VDFs

Consensus protocols have been studied in the 1980s as a method to provide fault tolerance for information stored in databases. Such protocols can achieve fault tolerance by distributing the data across many different machines, which are physically separated from one another, over a network. Recently, consensus protocols have been studied in the context of cryptocurrencies. Because of the demands of such applications (where failure could mean massive monetary gain for certain individuals and detrimental monetary loss for others), there has been recent focus on obtain consensus protocols that are robust against stronger forms of adversaries. In this talk, we explain the adaptive adversarial model in synchronous networks as well as past results in this domain. Then, we will talk about challenges and new approaches in extending these results to the partially synchronous model for the binary Byzantine agreement problem using sublinear number of multicast messages. We also present a new protocol for general block consensus using sublinear number of multicast messages in the synchronous model under adaptive adversaries.

Based on joint work with Neha Narula and Tadge Dryja.