Stanford EE374, Spring 2022
# Blockchain Foundations

## Basic Info

## Office hours

## Lecture Notes

## Problem Sets

## Solutions

## Exams

## Overview

## Spring 2022 Schedule

### Lecture 1: Money

### Lecture 2: The adversary

### Lecture 3: Primitives

### Lecture 4: Transactions

### Lecture 5: Blocks

### Lecture 6: Chains

### Lecture 7: Chain Virtues

### Lecture 8: Attacks

### Lecture 9: Variable Difficulty, Pools, Wallets

#### Lecture 10: Accounts and Balances, Merkle Trees

#### Lecture 11: Light Clients; Backbone warmup

#### Lecture 12: Security in Earnest (I)

#### Lecture 13: Security in Earnest (II)

#### Lecture 14: Security in Earnest (III)

### Lecture 15: Longest Chain Proof of Stake (I)

### Lecture 16: Longest Chain Proof of Stake (II)

### Lecture 17: BFT Proof of Stake (I)

### Lecture 18: BFT Proof of Stake (II)

## Who is this course for?

## Problem Sets

## Grading

The grade for the course will be determined according to the following breakdown:
## Bibliography

## Comparison to Other Courses

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?

- Wed/Fri 3:15-4:45pm
**Location**: 200-034**Instructors**: Prof. David Tse, Dr. Dionysis Zindros**Teaching Assistants**: Kamilla Nazirkhanova, Srivatsan Sridhar**Grader**: Cynthia Liu- Canvas • Piazza

- 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

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

Develop your own full node of the Marabu Protocol.

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?

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

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

- 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

- 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

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

- 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

- 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

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

- Healing
- Macroeconomic supply
- Selfish mining
- Mining pools

- 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

- 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

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

- 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

- 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 δ

- 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, δ

- 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

- 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

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

- The Streamlet protocol and its proof of safety

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

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.

**Programming Exercises**: 40%**Midterm**: 20%**Final**: 35%**Scribe**: 5%

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:

- Nakamoto's Bitcoin pape
- The Bitcoin Backbone (up to and including the Analysis section)
- The Selfish Mining
- Streamlet (excluding the liveness proof)
- Everything is a Race and Nakanomoto Always Wins

Some optional related readings we discussed in class:

- The Bitcoin Brain Drain
- On the Instability of Bitcoin Without the Block Reward
- SmartPool: Practical Decentralized Pooled Mining

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.