Consensus under adversary majority

A specter is haunting consensus protocols — the specter of adversary majority. Dolev and Strong in 1983 showed an early possibility for up to 99% adversaries. Yet, other works show impossibility results for adversaries above 50% under synchrony, seemingly the same setting as Dolev and Strong’s. What gives?

In this talk, Joachim Neu (a16z crypto research) pinpoints a key culprit for this ostensible contradiction: the modeling details of clients. Are the clients sleepy or always-on? Are they silent or communicating? Can validators be sleepy too? We systematize models for consensus across four dimensions (sleepy/always-on clients, silent/communicating clients, sleepy/always-on validators, and synchrony/partial-synchrony), and tightly characterize the achievable safety and liveness resiliences for each of the sixteen models. To this end, we unify folklore and earlier results, and fill gaps left in the literature with new protocols and impossibility theorems.

Paper: https://eprint.iacr.org/2024/1799, a joint work with Srivatsan Sridhar, Ertem Nusret Tas, Dionysis Zindros, and David Tse.

About the presenter Joachim is a postdoc Research Associate at a16z crypto research. He earned a PhD at Stanford, advised by David Tse. His current research focus is blockchain-era consensus and decentralized-systems security. His broader interests include distributed computing and systems, applied cryptography, and networking and communications.

About a16z crypto research a16z crypto research is a multidisciplinary lab that works closely with our portfolio companies and others toward solving the important problems in the space, and toward advancing the science and technology of the next generation of the internet.

More about us: a16z.com/2022/04/21/announcing-a16z-crypto-research

More from the a16z crypto team S

ubscribe to our ‘web3 weekly newsletter’: a16zcrypto.substack.com

Listen to our ‘web3 with a16z’ podcast: a16zcrypto.com/web3-with-a16z-podcast/

Read more of our work: a16zcrypto.com