EE374 Internet-Scale Consensus in the Blockchain Era

EE374 Internet-Scale Consensus in the Blockchain Era

Winter 2021

The archived course website of the Spring 2020 offering of EE374 can be found here.

Consensus protocols are at the core of distributed systems. Traditional consensus protocols are designed for the closed setting where consensus is maintained by a fixed and typically small set of permissioned nodes in a single organization. Blockchains were invented by Nakamoto in 2008 to achieve consensus in the open permissionless setting at Internet-scale, where nodes can freely join and leave the network. Existing blockchains like Bitcoin and Ethereum have an excellent track record in operating securely in such a challenging environment, but suffer from several significant drawbacks: 1) high confirmation latency; 2) low transaction throughput; 3) lack of finality guarantees; 4) lack of accountability for misbehaving participants; 5) high energy consumption due to Proof-of-Work. This course discusses recent solutions to overcome each of these drawbacks while maintaining the security properties of Nakamoto’s consensus protocol. Techniques from traditional Byzantine fault tolerance theory, probabilistic analysis, cutting-edge cryptography and error-correction coding are used. A recurring theme is that Nakamoto’s longest chain protocol and traditional BFT protocols have complementary strengths, and best-of-both-worlds protocols can be built by composing them.

Syllabus

  1. Basic building blocks: Nakamoto’s longest chain protocol and its key security properties: safety, liveness, dynamic availability and unpredictability. A simple BFT protocol: Streamlet.
  2. Fast confirmation: Directed-acyclic-graph protocols. Hybrid consensus. Synthesis of the two approaches.
  3. Finality and Accountability: Checkpointing and finality gadgets. The availability-finality dilemma and its resolution via ebb-and-flow protocols. Compositional solutions. Accountability via the finality layer.
  4. Throughput Scaling: Vertical and horizontal scaling of transaction throughput under computing, communication and storage limits. Decoupling transaction processing and security to achieve scaling. Horizontal scaling via sharding. The data availability problem. Efficient data availability via coding and verifiable information dispersal.
  5. Energy-efficiency: Proof-of-Stake vs Proof-of-Work vs permissioned setting. Use of Verifiable Random Functions and Verifiable Delay Functions to provide unpredictability and dynamic availability in Proof-of-Stake protocols.
Relationship with CS 251 and prerequisites

CS251 (Cryptocurrencies and Blockchain Technologies) provides a broad coverage of blockchain technologies and applications, while this course focuses on the consensus layer and studies recent advances building on Nakamoto’s longest chain protocol and classical BFT protocols. This course can be taken as a sequel to CS 251 but can also be taken on a stand-alone basis. The only prerequisite is a solid undergraduate course in probability such as CS 109 or EE 178.

For a comprehensive introduction to blockchains, you can consult the textbook Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction by Narayanan, Bonneau, Felten, Miller and Goldfeder (preprint edition available for free online).

Evaluation

  • Projects
  • 3-4 homeworks
  • Lecture scribing
  • Class participation

Administrivia

TBD