COMS 6998-006: Foundations of Blockchains
- Sept 2: Welcome to COMS 6998-006!
- Sept 15: Notes for Lecture 1 posted.
- Sept 15: HW1 posted.
- Sept 20: Lecture room changed to CSG 451 (starting with lecture 4).
Roughgarden (Office hours: Tuesdays 5-6pm by Zoom. Email: firstname.lastname@example.org.)
(Office hours: Mondays 3-5pm and Wednesdays 12:30-2:30pm, in the CS TA room on the first floor of Mudd.)
Time/location: 8:40-9:55 AM Tue/Thu in
Mudd 834 CSB 451.
Discussion site: ed.
Prerequisites: Undergraduate algorithms (COMS 4231) or equivalent mathematical maturity. The intended audience is first-year graduate students
with a strong interest in and affinity for theoretical computer science.
Course outline (subject to change):
Textbook: There is no required textbook for the course;
lectures are the sole required source of content.
Supplementary reading will be posted as part of the lecture schedule, below.
- Classical permissioned consensus.
- Types of adversaries and synchrony models, Dolov-Strong Byzantine broadcast protocol, FLP impossibility result for asynchronous consensus, tight fault-tolerant bounds in the partially synchronous model.
- Permissionless consensus.
- Nakamoto (longest-chain) consensus, guarantees for the Bitcoin backbone protocol, committee-based reductions to BFT-type permissioned protocols, the CAP theorem.
- Proof-of-work, difficulty adjustment, selfish mining; proof-of-stake, VRFs and VDFs, etc.
- Bitcoin deep dive.
- Block structure, Merkle trees, UTXOs, light clients, scaling Bitcoin via payment channels and the Lightning network.
- Ethereum deep dive.
- Block structure, gas and the EVM, the EIP-1559 transaction fee mechanism, scaling Ethereum via optimistic and zk-rollups, plans for ETH 2.0.
- Newer-generation layer-1 consensus protocols (e.g., Solana and Avalanche).
- The multi-chain vision: interoperability and bridges.
- DeFi (decentralized finance) primitives.
- DeFi applications.
- Borrowing, lending, trading via automated market makers.
- Miner extractable value (MEV) and interactions between the consensus and application layers.
- (Time permitting) Approaches to protocol governance.
- (Time permitting) A look ahead: DAOs, NFTs, Web3, etc.
Lecture notes: (posted only sporadically)
- Lecture 1 (Introduction and Overview) [unedited 0th draft]
- Problem Sets (60%):
There will be a number of problem sets, around 8-9 in total.
Problem sets can be completed in pairs.
- Problem Set Policies:
- To be submitted in groups of 2 (all students of the group receive the same score).
- You can form different pairs for different exercise sets.
- You can discuss exercises with students from other groups verbally and at a high level only.
- Except where otherwise noted, you may refer to your course notes, the
textbooks and research papers listed on the course Web
page only. You cannot refer to textbooks, handouts, or
research papers that are not listed on the course home page. If you
do use any approved sources, make you sure you cite them
appropriately, and make sure that all your words are your own.
- You are strongly encouraged to use LaTex to typeset your write-up.
Here's a LaTeX template that you can use to type up solutions.
here are good introductions to LaTeX.
- Honor code: We expect you to abide by the computer science department's
policies and procedures regarding academic honesty.
- Submission instructions:
We are using Gradescope for the homework submissions. Go to
www.gradescope.com to either login or create a new
account. Use the course code 6PN7NP to register for this class. Only one group member
needs to submit the assignment. When submitting, please remember to
add all group member names onto Gradescope.
- One late day equals a 24-hour extension.
- Each student has three free late days.
- At most two late days can be applied to a single assignment.
- Each late day used after the first two will result in a 25%
- Example: a student had one free late day remaining but their
group uses two late days on a Problem Set. If the group's write-up
earns p points, the student receives a final score of .75*p points
for the assignment.
Research project (40%): To be completed in teams of 3-4
students. The project can be theoretical or application-focused, and
should relate to the course content but otherwise can be on a topic of
your choosing. A single report of 15-20 pages will be due shortly
after the final lecture.
- Lecture 1 (Thu Sept 9): Course overview and main themes.
The blockchain stack and its layers.
Ideal digital signature schemes.
The SMR (state machine replication) problem.
Defining consensus, consistency, and liveness.
- Lecture 2 (Tue Sept 14): The synchronous model and the Dolev-Strong protocol for Byzantine broadcast.
- Lecture 3 (Thu Sept 16): Necessity of PKI for synchronous consensus with dishonest majority. Proof themes: simulation and indistinguishability.
- M. Pease, R. Shostak, and L. Lamport, Reaching Agreement in
the Presence of Faults, Journal of the ACM, 1980.
- M. J. Fischer, N. A. Lynch, and M. Merritt, Easy Impossibility Proofs for Distributed Consensus Problems, Distributed Computing, 1986.
- Lecture 4 (Tue Sept 21): The asynchronous model. Start proof of FLP impossibility theorem.
- Lecture 5 (Thu Sept 23): Finish proof of FLP impossibility theorem. The partially synchronous model.
- Lecture 6 (Tue Sept 28): Tendermint and its properties in the partially synchronous model.
- Lecture 7 (Thu Sept 30): Nakamoto/longest-chain consensus.
- Lecture 8 (Tue Oct 5): Proof-of-work sybil resistance.
- Lecture 9 (Thu Oct 7): Selfish mining.
- Lecture 10 (Tue Oct 12): Proof-of-stake sybil resistance.
- Lecture 11 (Thu Oct 14): The economic security of blockchains.
- Lecture 12 (Tue Oct 19): Deep dive on Bitcoin (UTXOs, Merkle trees, light clients, etc.).
- Lecture 13 (Thu Oct 21): Scaling Bitcoin via payment channels and the Lightning Network.
- Lecture 14 (Tue Oct 26): Deep dive on Ethereum.
- Lecture 15 (Thu Oct 28): EIP-1559 and Ethereum's transaction fee mechanism.
- [no class on Tue Nov 2 --- academic holiday]
- Lecture 16 (Thu Nov 4): Scaling Ethereum I (sidechains, optimistic rollups).
- Lecture 17 (Tue Nov 9): Scaling Ethereum II (zk-rollups).
- Lecture 18 (Thu Nov 11): Layer-1 upstarts.
- Lecture 19 (Tue Nov 16): Interoperability and bridges.
- Lecture 20 (Thu Nov 18): Stablecoins.
- Lecture 21 (Tue Nov 23): Oracles.
- [no class on Thu Nov 25 --- academic holiday]
- Lecture 22 (Tue Nov 30): DeFi: borrowing, lending, and trading.
- Lecture 23 (Thu Dec 2): Deep dive on automated market makers.
- Lecture 24 (Tue Dec 7): Miner extractable value (MEV).
- Lecture 25 (Thu Dec 9): DAOs and on-chain governance.