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.
Outputs
A Lower Bound for Byzantine Agreement and Consensus for Adaptive Adversaries using VDFs (Published April 2020)
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.
Authors:
Thaddeus Dryja, MIT Media Lab
Quanquan C. Liu, MIT Media Lab
Neha Narula, MIT Media Lab
Conference PresentationsQuanquan Liu (PhD Student, MIT CSAIL) presenting on Consensus with Adaptive Adversaries in the Synchronous and Partially Synchronous Models: Binary Byzantine Agreement and Block Consensus at the The Simons Institute for the Theory of Computing Workshop Large-Scale Consensus and Blockchains. Oct. 24, 2019
Quanquan Liu (PhD Student, MIT CSAIL) presenting on consensus under adversarial conditions at the 2020 MIT Bitcoin Expo hosted by the MIT Bitcoin Student Club. April 6th, 2020
Quanquan Liu (PhD Student, MIT CSAIL) presenting on Verifiably Delaying Adaptive Adversaries in 1 Consensus at the 2020 Crypto Economics Security session with Vitalik Buterin. July 9th, 2020