Stanford EE374, Spring 2022

Blockchain Foundations

Blockchains are a new field of computer science which combines cryptography, distributed systems, and security. In this course, we go deep in understanding the fundamentals: What are blockchains, how do they work, and why are they secure?

Basic Info

Office hours

  • David Tse: By appointment
  • Dionysis Zindros: Wed 5-6pm & Thu 11am-noon, Packard 106
  • Kamilla Nazirkhanova: Tue 10-11am, Packard 106
  • Srivatsan Sridhar: Thu 1-2pm, Packard 106

Lecture Notes

  1. Lectures 1-2
  2. Lecture 3
  3. Lecture 4
  4. Lecture 5
  5. Lecture 6
  6. Lecture 7
  7. Lecture 8
  8. Lecture 9
  9. Lecture 10
  10. Lecture 11
  11. Lecture 12
  12. Lecture 13
  13. Lecture 14
  14. Lecture 15
  15. Lecture 16
  16. Lecture 17
  17. Lecture 18

Problem Sets

Develop your own full node of the Marabu Protocol.

  1. Problem set 1
  2. Problem set 2
  3. Problem set 3
  4. Problem set 4
  5. Problem set 5
  6. Problem set 6

Solutions

  1. Problem set 1
  2. Problem set 2
  3. Problem set 3
  4. Problem set 4
  5. Problem set 5

Exams

  1. Midterm with solutions
  2. Practice problems on Streamlet
  3. Final exam with solutions

Overview

This graduate-level course teaches you about blockchain foundations. The course focuses on the first principles and foundations behind blockchains with the aim of understanding how and why blockchain technology works and is secure. We do not focus on Bitcoin or Ethereum engineering peculiarities, but we explore the general concepts of the blockchain field. However, the course is heavy on both engineering (writing code) and theory.

The course focuses on three questions:

  • What are blockchains?
  • How do they work?
  • Why are they secure?

Spring 2022 Schedule

The topics of the course include proof-of-work (in static and variable difficulty), proof-of-stake, transactions in the UTXO and accounts model, authenticated data structures such as Merkle Trees, and simple payment verification. A central topic of the course is understanding why blockchains are secure. We treat the question in theoretical depth using the cryptographic backbone model.

The full syllabus is as follows (we may still make small revisions).

Lecture 1: Money

  • Administrivia
  • Money as a social construct
  • The network model
  • The non-eclipsing assumption
  • The gossip protocol

Lecture 2: The adversary

  • The adversary A
  • The security parameter κ
  • The honest protocol Π
  • The adversarial model
  • Probabilistic polynomial-time adversaries
  • Negligible functions
  • Game-based security
  • Security proofs by computation reduction
  • Proofs by contradiction and forward proofs

Lecture 3: Primitives

  • The hash function: H
  • Preimage resistance, second preimage resistance, collision resistance
  • Collision resistance implies preimage resistance
  • Preimage resistance implies second preimage resistance
  • Public/private keys
  • Signature schemes
  • Signature correctness
  • Existential unforgeability
  • Ledgers

Lecture 4: Transactions

  • Transactions
  • Inputs and outputs
  • The transaction graph
  • Change
  • Multiple inputs
  • Multiple outputs
  • The UTXO model
  • The law of conservation
  • Verifying a transaction

Lecture 5: Blocks

  • Views in disagreement
  • Double spending
  • The network delay Δ
  • Simple ideas don't work!
  • Rare events
  • Blocks
  • Proof-of-work
  • The mining target T
  • The proof-of-work equation
  • The mining algorithm
  • Block freshness
  • The genesis block G
  • Chains

Lecture 6: Chains

  • Hash chains
  • The number n of parties
  • The number t of adversarial parties
  • The hashing power q
  • Rare events are irregular
  • Convergence opportunities and periods of silence
  • The honest majority assumption
  • The longest chain rule
  • Coinbase
  • Fees
  • Mempools

Lecture 7: Chain Virtues

  • Temporary forks
  • Convergence
  • The Nakamoto race
  • Chain Growth, Common Prefix, Chain Quality
  • Censorship
  • Majority attacks

Lecture 8: Attacks

  • Healing
  • Macroeconomic supply
  • Selfish mining
  • Mining pools

Lecture 9: Variable Difficulty, Pools, Wallets

  • CPU, GPU, ASIC mining
  • Incentive compatibility
  • Block size limits
  • Transaction prioritization by fees
  • Macroeconomic policy, reward adjustment
  • The difficulty adjustment equation Τ_{j+1} = T_{j} (t_2 - t_1) / (mη)
  • Mining pools, the light PoW equation: H(B) ≤ 2^z T
  • The pooled mining protocol
  • Cold, hot, and hardware wallets
  • Wallet seeds, deterministic wallets

Lecture 10: Accounts and Balances, Merkle Trees

  • The account model
  • Transactions in the account model
  • Balances
  • Nonces
  • The generic transition function δ
  • Blockchain as a State Machine Replication mechanism
  • UTXO vs accounts
  • The file storage problem
  • The Merkle Tree: compress, prove, verify
  • Proofs of inclusion, succinctness
  • Merkle Tree security proof by reduction from collision-resistant hashes

Lecture 11: Light Clients; Backbone warmup

  • The problem of scalability in blockchains: Scaling computation, communication, and storage
  • From x-bar to x using Merkle Trees
  • The Simple Payment Verification (SPV) protocol
  • The header chain
  • Miners, Full Nodes, Light Nodes
  • Chain virtues for light nodes
  • Privacy concerns for light nodes
  • Random Oracles, formally
  • The synchrony assumption Δ = 1. The round.

Lecture 12: Security in Earnest (I)

  • The Environment and the Execution
  • The Rushing Adversary
  • The Sybil Adversary
  • The Network model, the gossiping model
  • The Non-Eclipsing Assumption
  • The honest backbone protocol
  • Maintaining, adopting, and having chains
  • Proof-of-work
  • The q-bounded Random Oracle
  • The Static Difficulty assumption
  • Chain validation; the δ* function
  • Successful rounds
  • Convergence opportunities
  • Formal definition of Chain Virtues
  • Common Prefix, the parameter k
  • Chain Quality, the parameters μ and ℓ
  • Chain Growth, the parameters τ and s
  • The formal honest majority assumption: t < (1 - δ)(n - t)
  • The honest advantage δ
  • Convergence Opportunities are useful: The Pairing Lemma and its proof

Lecture 13: Security in Earnest (II)

  • Ledger Safety and Liveness, formally. The liveness parameter u.
  • Proof of Safety from Common Prefix
  • Proof of Liveness from Chain Quality and Chain Growth; u = max((ℓ + k) / τ, s)
  • The Chain Growth Lemma and its proof
  • The successful round indicator X
  • The convergence opportunity indicator Y
  • The adversarial success indicator Z
  • The expectations of X, Y, and Z
  • Bernoulli's inequality
  • Lower and upper bounds on the expectation of X
  • Lower bounds on the expectation of Y
  • Good things converge: The Chernoff bound
  • The world is good, usually: Typical executions
  • The Chernoff duration λ
  • The Chernoff error ε
  • Proof of Typicality Theorem
  • The Balancing Equation: 3ε + 3f ≤ δ
  • A plot of X, Y, and Z with 3f, 3ε and δ

Lecture 14: Security in Earnest (III)

  • Reminder of bounds on the expectations of X and Y
  • Upper bound on the expectation of Z
  • Typical bounds, and proof that Z ≤ Y
  • Chains grow: The Chain Growth theorem and its proof
  • The Patience Lemma and its proof
  • The Common Prefix theorem and its proof
  • Discussion on the relationship between ε and λ
  • You can't have it all: Discussion on the parametrization options for ε, f, δ

Lecture 15: Longest Chain Proof of Stake (I)

  • Proof of Work's perils and environmental impact
  • Proof of Work vs Proof of Stake
  • Dangers of Proof of Stake
  • The Proof of Stake equation

Lecture 16: Longest Chain Proof of Stake (II)

  • Proof of Work's perils and environmental impact
  • Proof of Work vs Proof of Stake
  • Dangers of Proof of Stake
  • The Proof of Stake equation

Lecture 17: BFT Proof of Stake (I)

  • Everything is a Race and Nakamoto Always Wins
  • Verifiable Random Functions
  • VRF correctness
  • The unpredictability game
  • Towards instant finality

Lecture 18: BFT Proof of Stake (II)

  • The Streamlet protocol and its proof of safety

Who is this course for?

This is a new course for graduate-level students in computer science, electrical engineering, or related fields or as an advanced elective course for interested undergraduate students. The prerequisites for the course are a professional knowledge of at least one programming language (for implementing the node), a basic knowledge of networking (TCP/IP), basic understanding of probability theory (probabilities, expectations, distributions), discrete mathematics (graphs, proof techniques). A very basic understanding of cryptography (hashes, signatures, proof techniques) is helpful but not required.

Prerequisites

  • CS106A, CS106B, or CS106X, or relevant programming experience
  • CS103, or CS103B or related course on discrete math
  • CS109, MATH151, STATS116, or EE178 or related course on probability

Problem Sets

The problem sets are the most important part of this course. The problem sets are about implementation. They involve building our own blockchain, Marabu. It is a proof-of-work UTXO blockchain designed for educational purposes to be simple to implement and debug. As a student, you will implement your own Marabu full node from scratch. Your node must connect to the nodes of other students and maintain a common blockchain with them. You will implement the protocol by following through the problem sets. The protocol is a simplified, educational protocol easy to debug and implement designed especially for this course. Even though it is simple, it implements a full blockchain which follows the same principles as a full blockchain such as Bitcoin and Ethereum, albeit with limited features (it allows only for simple payments and is not very efficient). You can use whatever programming language you know well for your implementation. We recommend using TypeScript. We have seen successful implementations in Python, TypeScript and Go. The problem sets guide you through implementing your node in a step-by-step fashion, so each problem set builds on top of the previous one to augment your node slowly adding new features until it is complete. Students can collaborate to solve all problem sets in groups of up to 3 students. Only one submission is required per group.

Grading

The grade for the course will be determined according to the following breakdown:
  • Programming Exercises: 40%
  • Midterm: 20%
  • Final: 35%
  • Scribe: 5%

Bibliography

There are limited textbooks in the field. Therefore, we refer you to the lecture notes as the main reference point.

We have used excerpts from the "Introduction to Modern Cryptography" book. In particular:

  • The introduction, in particular the importance of definitions, assumptions, and proofs.
  • The section on hash functions.
  • The definition of signatures and the existential unforgeability game.
  • The section on the Random Oracle model.

We have also read a small part of Harari's Sapiens book and the fictional nature of money (Chapter 16).

In addition, the following papers have been given in the readings:

Some optional related readings we discussed in class:

Comparison to Other Courses

This course is a good follow-up course on CS 251. CS 251 studies blockchains very broadly and covers a lot of material. It talks about consensus, smart contracts, Solidity, decentralized finance, zero-knowledge, BFT, and more. It also talks about Bitcoin-specific and Ethereum-specific details. In this course, we focus on the foundations of blockchains and speak only about the very basics concepts, in particular transactions and consensus, but in more detail and depth. We don't speak about engineering for Bitcoin and Ethereum specifically. On the engineering side of things, we implement consensus and transactions, and so these are explored in depth. On the theory side of things, we devote a couple weeks on proving the security of blockchains mathematically.

CS251 is not a prerequisite, but if a student has taken CS 251, they will find this course easier to follow.

If you have taken EE 374 any previous year, this is a completely new course, with a different syllabus and different psets.