EE374 Scaling Blockchains

EE374 Scaling Blockchains

Spring 2020

Blockchains were invented by Nakamoto in 2008 to achieve large-scale decentralized consensus in the permissionless setting. Existing blockchains like Bitcoin and Ethereum have excellent security against adversarial attacks but suffer from low throughput and poor latency. The focus of this new course is to ask and answer the question: how can one design blockchains that are decentralized and secure but at the same time have scalable performance? In particular, we are interested in achieving: 1) vertical scaling with the communication, compute and storage resources of the network nodes; 2) horizontal scaling with the number of nodes; 3) energy scaling to maintain consensus power-efficiently.

In addition to cryptography and distributed computing, we will draw on ideas and techniques from stochastic analysis, networking, coding and information theory.

Administrivia

  • Lectures: Tue+Thu, 10:30-11:50am, via Zoom (please access through Canvas), room 200-202
  • Piazza: https://piazza.com/stanford/spring2020/ee374
  • Gradescope: Entry Code: 92J6Y3
  • Instructor: David Tse, office hours: Wed+Fri, 9:30-10:30am, via Zoom (please access through Canvas)
  • TA: Joachim Neu, office hours: Mon, 10-11am, and Fri, 5-6pm, via Zoom (please access through Canvas)
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.
  • 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 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.
Homeworks

Syllabus

Material
  1. Basics: Nakamoto’s longest chain protocol. Security analysis. Scaling issues.
  2. Vertical Scaling: Physical limits to scaling: communication bandwidth and network delay. Decoupling transaction processing and security. Using the decoupling principle to design blockchain protocols to attain physical limits. System implementation.
  3. Horizontal Scaling: The blockchain trilemma. Attempts to solve the trilemma via sharding. Applying the decoupling principle to solve the trilemma. The data availability problem. Efficient data availability via coding. Coded Merkle trees.
  4. Energy-Efficient Scaling: Proof-of-stake vs Proof-of-Work. Scalable Proof-of-Stake blockchains. BFT vs. longest-chain based protocols. The nothing-at-stake problem.
  5. Guest lectures and project presentations
Tentative Schedule
Required Background

The required background is a good understanding of basic probability at the level of EE178 or CS109 or equivalent. All other material will be taught as required. CS251 (Cryptocurrencies and Blockchain Technologies) is not a required prerequisite, but students who have taken CS251 will benefit from a more in-depth coverage of several topics in this class.

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

Grading

  • Project (1-2 persons per team, 60%)
    • Brainstorming/feedback/discussion video chat with course staff (before proposal deadline)
    • Proposal (1 page, due 8-May, 10%)
    • Midterm check-in video chat with course staff (week of 25-May)
    • Presentation (~15min, 9-/11-June, 20%)
    • Report (5 pages, due 12-June, 30%)
  • 3-4 homeworks (25%)
  • Lecture scribing (10%)
  • Class participation (5%)

As of 3-April, the grading details are tentative and will be finalized in the first week of the quarter.

Project Ideas/Topics

Below is a list of project ideas and potential topics, including references that provide a first glimpse into the material/literature. All topics are (very close to) topics of active research. This list will be updated and extended over time. Students are welcome to propose their own project ideas as well.

Description

Blockchains is a breakthrough technology invented by Satoshi Nakamoto in 2008. Originally conceived to maintain a decentralized ledger for Bitcoin, it is now viewed more broadly as a technology for maintaining decentralized trust without the need for a central authority. Nodes in the network maintain trust by contributing compute power to solve hard cryptographic puzzles.

Nakamoto’s original blockchain protocol is very simple but yet has a very strong security guarantee: as long as the adversary controls less than 50% of the compute power of the entire network, the system is secure. That is, transactions that are confirmed in the ledger cannot be reversed by the adversary. However, the protocol suffers from several problems. First, the transaction throughput is very low: Bitcoin only processes 5 to 7 transactions per second. Second, the confirmation latency is very poor: transactions require hours to confirm. Third, each node in the network has to communicate, compute and store all the transactions in the ledger. Thus, the protocol suffers from a scaling problem.

The focus of this new course is to ask and answer the question: how can one build blockchains that have high throughput and low latency with each node having limited communication, compute and storage resources? This is one of the biggest challenges in blockchains research, both in academia and in industry, in the past few years. In fact, a well-known, but unproven, conjecture, called the Blockchain Trilemma, states that it is impossible to build a blockchain system that is simultaneously decentralized, secure and scalable. We will take a first principle approach to attempt to resolve the conjecture in this course.

We will also invite one or two guests from the blockchain industry to discuss scalability efforts in the blockchain industry, eg. Ethereum 2.0.