Verifiably Delaying Adversaries in Consensus

Consensus is a fundamental problem in distributed systems. Historically, consensus protocols have been critical in the context of ensuring the consistency of replicated data, but they were typically deployed with only a few dozen replicas and only tolerated crash failures. More recently, consensus protocols have been studied in the context of cryptocurrencies to maintain a distributed public ledger. These applications introduce new demands: First, cryptocurrency networks operate with thousands or millions of participants, meaning having all participants speak to everyone in each step, resulting in large communication complexity, is unacceptable. Second, these ledgers support billions of dollars of economic activity, so they need to cope with a much stronger potential attacker. Our research seeks to look for various novel and unprecedented solutions to these problems.

Papers

Featured

The Future of Money at Consensus 2023

On April 27, DCI director Neha Narula spoke at Consensus 2023 on private and public money and the role of blockchain technology in future digital payment systems.

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

Abstract:

Large scale cryptocurrencies require the participation of millions of participants and support economic activity of billions of dollars, which has led to new lines of work in binary Byzantine Agreement (BBA) and consensus. The new work aims to achieve communication-efficiency---given such a large n, not everyone can speak during the protocol. Several protocols have achieved consensus with communication-efficiency, even under an adaptive adversary, but they require additional strong assumptions---proof-of-work, memory-erasure, etc. All of these protocols use multicast: every honest replica multicasts messages to all other replicas. Under this model, we provide a new communication-efficient consensus protocol using Verifiable Delay Functions (VDFs) that is secure against adaptive adversaries and does not require the same strong assumptions present in other protocols.

A natural question is whether we can extend the synchronous protocols to the partially synchronous setting---in this work, we show that using multicast, we cannot. Furthermore, we cannot achieve always safe communication-efficient protocols (that maintain safety with probability 1) even in the synchronous setting against a static adversary when honest replicas only choose to multicast its messages. Considering these impossibility results, we describe a new communication-efficient BBA protocol in a modified partially synchronous network model which is secure against adaptive adversaries with high probability.