2026 Theses Doctoral

Beyond Worst Case Consensus In The Era Of Blockchains

Efron, Yuval

This thesis discusses recent work in tackling the well known consensus task under models, settings, and security desiderata motivated by modern blockchain technologies. Blockchains aiming to support a myriad of applications over high demand networks face unorthodox challenges compared to traditional distributed systems: These include geographically decentralized parties, dynamic participation, and agentic behaviour from parties. Furthermore, the required latency is several orders of magnitude lower than obtainable by worst case guarantees.

In this thesis we present results advancing the state of the art on consensus in the context of these novel desiderata, and in the context of beyond worst case efficiency, aiming to circumvent worst case lower bounds by incorporating design principles from real world networks and party behaviors.

The second chapter of the thesis discusses work establishing a fundamental trade-off between the latency of consensus protocols and censorship resistance, a property of paramount importance in many applications. Specifically, we show that censorship resistant consensus requires 5 rounds, compared to the 3 rounds required in the traditional setting.

The third chapter of this thesis continues the study of good case latency, a metric measuring the latency of consensus protocols under favorable conditions, in a model that supports dynamic participation of parties. We provide a complete characterization of the good case latency of consensus in the dynamic participation setting.

In the fourth chapter, we enrich the study of consensus under dynamic participation, introducing a simple and clean model that allows proof-of-stake protocols to be as resilient to fluctuating participation as proof-of-work protocols.

In the fifth chapter, motivated by rethinking trust models around consensus and randomness generation, we discuss work characterizing the amount of randomness needed for secure consensus. Finally, in the sixth chapter, we discuss work studying crypto agnostic consensus protocols, which are protocols that enjoy enhanced properties endowed by cryptography, while remaining secure even if the underlying cryptography breaks.