EE374 Internet-Scale Consensus in the Blockchain Era

Winter 2021

Consensus protocols are at the core of distributed systems to enable multiple participating nodes to agree on a common record of history. Traditional consensus protocols are designed for the closed setting with 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 composing them can yield best-of-both-worlds protocols.

Homeworks

• Homework #1, due Fri, 22-January-2021, 11:59pm PT
• Homework #2, due Tues, 2-February-2021, 11:59pm PT
• Homework #3, due Fri, 12-February-2021, 11:59pm PT
• Take-Home Assessment, due Tues, 2-March-2021, 1:00pm PT

Syllabus

1. Introduction and course overview (1 lecture)
2. Basic building blocks: (4 lectures)
   Basic cryptography: hash functions and signatures. Two consensus protocols: Nakamoto’s longest chain protocol and Streamlet. Their key security properties and their contrast: safety, liveness, dynamic availability vs finality, unpredictability vs predictability, probabilistic vs deterministic confirmation.
3. Fast confirmation: (2 lectures)
   Hybrid consensus. Parallel chains. Synthesis of the two approaches.
4. Finality and Accountability: (3 lectures)
   Checkpointing and finality gadgets. The availability-finality dilemma and its resolution via ebb-and-flow protocols. Compositional solutions. Accountability via the finality layer.
5. Throughput Scaling: (4 lectures)
   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.
6. Energy-efficiency: (4 lectures)
   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.

Paper Critique Topics

Tentative Schedule

Prerequisites and relationship with CS 251

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).

Previous offering of EE 374 focuses on the scalability aspects of blockchains. This offering covers a broader set of challenges.

Evaluation

• 3-4 homeworks (30%)
• 1 take home assessment (25%)
• Paper critique (35%)
• Lecture scribing (10%)

Administrivia

• Lectures: Mon+Wed, 11:30am - 12:50pm PT, Winter 2021 (first class: Mon, 11-January), via Zoom (see Canvas: https://canvas.stanford.edu/courses/130460)
• Piazza: https://piazza.com/stanford/winter2021/ee374
• Gradescope: https://www.gradescope.com/courses/219303, entry code: N8XV23
• Instructor: David Tse, office hours: Mon, 4-5pm + Wed, 1:30-2:30pm (via Zoom, see Canvas)
• TA: Joachim Neu, office hours: Tue, 5-6pm (via Zoom, see Canvas); Srivatsan Sridhar; Zucks Liu; Ertem Nusret Tas
• Zoom etiquette:
  • Do not record the Zoom meetings. It is against Stanford rules and applicable law.
  • Please keep your mic muted unless you are speaking, to minimize background noise.
  • Please keep your video on. We would like to make our online class experience as close to a regular in-person class as possible. You would not want to be invisible to the instructor and your classmates if you were attending a regular in-person class.
  • Feel free to use the Zoom chat. The TA and other students can answer questions during the lecture. The instructor may not be able to monitor the chat in real time.
  • Raise your hand (physically) to signal that you have a question. Should the instructor overlook your raised hand, unmute your mic, then say “question”.
  • An example of a viable Zoom user interface configuration can be found here.