Improving Round and Communication Metrics in Consensus

Abstract

Byzantine Consensus protocols, aka Byzantine Agreement (BA), Byzantine Broadcast (BB), allow a set of n mutually distrusting parties to share input values and agree on the same output value. Notable practical applications of consensus in blockchains and MPC require efficient, practical implementations of consensus protocols. The rise of blockchain systems and the general trend towards decentralized services, which inherently utilize consensus, as well as the increased demand of consensus as a primitive for implementing other cryptographic protocols (e.g. in MPC), brought once again this topic in the forefront of research.

A recurring trilemma of consensus when utilized in practice is striking the balance in order to construct protocols that are: i) efficient, ii) resilient under harsh adversarial conditions, and iii) with minimal assumptions for the corresponding setting. These properties are usually negatively associated; efficient protocols often either require stronger assumptions, or are less resilient to strong adversaries.

In this dissertation we aim to improve the efficiency of consensus protocols under harsh adversarial conditions and weak assumptions. We explore directions towards improving the two major metrics of efficiency of such protocols; i.e. their communication and round complexities. We focus on protocols operating in a synchronous communication network, and show how to achieve efficiency of either rounds or communication under different assumptions, against weakly adaptive adversaries with high corruption threshold. We will construct i) (Parallel) Broadcast protocols with improved state of the art communication, ii) the first Broadcast protocol with sublinear rounds without trusted setup, and iii) the first Deterministic Byzantine Agreement protocol with adaptive O(n·f) communication.