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).
- Sept 28: HW2 posted.
- Nov 12: HW6 posted.
- Nov 12: Note the deadline for final reports is December 17th.
- Nov 19: HW7 posted.
Instructor:
-
Tim
Roughgarden (Office hours: Tuesdays 5-6pm by Zoom. Email: tr@cs.columbia.edu.)
Course Assistants:
-
Maryam Bahrani
(Office hours: Mondays 3-5pm by Zoom. Wednesdays 12:30-2:30pm in the CS TA room on the first floor of Mudd.)
Email: m.bahrani@columbia.edu.
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):
- 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.
- Sybil-resistance.
- 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.
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.
Lecture notes: (posted only sporadically, complete set should be ready in early 2022)
- Lecture 1 (Introduction and Overview) [unedited 0th draft]
Coursework
- 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 and
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.
Late Days:
- 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%
penalty.
- 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. Two example reports from last year:
Deadline: Friday, December 17.
Final Project Reports:
- Proof of Space with VDF:
An Alternative Permissionless BFT Consensus Protocol, by Yuxuan Luo.
- An Initial Framework for NFT Auction Mechanism Design:
Impossibility Results and Solutions, by Andy Arditi, Pranav Garimidi, Dean Hirsch, and Iason Milionis.
- Alternative Sybil Resistance Methods, by Marcus Daly, Nathan Cuevas,
Griffin Klett, and Lynn Zhu.
- A Review of Zero Knowledge Proofs, by Thomas Chen, Abby Lu, Jern Kunpittaya, and Alan Luo.
- A Survey of DeFi Lending, by Alex Brenebel, Lynsey Haynes, Vaibhav Kapur, and Jonathan Larkin.
- DAOs, by Utkarsh Sinha, Sofia Bianchi, Ian Macleod, and Imanol Uribe.
- Proof of Participation Voting for On-Chain Governance, by Terry Chung, Sandip Nair, Uttara Ravi, and Pranav Kajgaonkar.
- A Technical Deep Dive Into and Implementation of
Non-Fungible Tokens in a Practical Setting, by Julia Martin and Carrie Hay Kellar.
- Privacy when Everyone is Watching:
Anonymity on the Blockchain, by Nilaksh Agarwal and Roy Rinberg.
- MEV on L2 by FlashBabies (Huy Ha, Vasiliki Vlachou, Quintus Kilbourn, and Cesare De Michellis).
Lecture Schedule
- 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.
Supplementary reading:
- Lecture 2 (Tue Sept 14): The synchronous model and the Dolev-Strong protocol for Byzantine broadcast.
Supplementary reading:
Historical readings:
- Lecture 3 (Thu Sept 16): Necessity of PKI for synchronous consensus with dishonest majority. Proof themes: simulation and indistinguishability.
Supplementary reading:
Historical readings:
- 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.
Supplementary reading:
Historical readings:
- Lecture 5 (Thu Sept 23): Finish proof of FLP impossibility theorem.
Supplementary reading: same as Lecture 4, and also:
- Lecture 6 (Tue Sept 28):
The partially synchronous model. The Tendermint protocol.
Supplementary reading:
Historical readings:
- Lecture 7 (Thu Sept 30): Properties of Tendermint.
The CAP theorem. Supplementary readings same as above, and also:
- Lecture 8 (Tue Oct 5):
Longest-chain consensus.
Supplementary reading:
- The Bitcoin white paper, 2008.
- Nakamoto's Longest-Chain Wins Protocol (Decentralized Thoughts)
- Chapters 14 and 17 of Elaine Shi's book draft, Foundations of Distributed
Consensus and Blockchains.
- Lecture notes from David Tse's Internet-Scale Consensus in the Blockchain Era course
- I. Abraham and D. Malkhi, The Blockchain Consensus Layer and BFT, Bulletin of the EATCS, 2017.
- J. A. Garay, A. Kiayias, and N. Leonardos,
The Bitcoin Backbone Protocol: Analysis and Applications, EUROCRYPT, 2015.
- R. Pass, L. Seeman, and a. shelat, Analysis of the Blockchain Protocol in Asynchronous Networks, EUROCRYPT, 2017.
- Lecture 9 (Thu Oct 7): The permissionless setting. Proof-of-work sybil-resistance. Difficulty adjustment.
Supplementary reading:
Historical readings:
- Lecture 10 (Tue Oct 12): Cryptocurrencies, block rewards, and selfish mining.
Supplementary reading:
- Lecture 11 (Thu Oct 14): Proof-of-stake sybil resistance.
Supplementary reading:
- Lecture notes from David Tse's Internet-Scale Consensus in the Blockchain Era course: lecture 1, lecture 2, lecture 3
- J. Brown-Cohen, A. Narayanan, C.-A. Promas, and S. Matthew Weinberg, Formal Barriers to Longest-Chain Proof-of-Stake Protocols, EC '19.
- A. Dembo, S. Kannan, E. N. Tas, D. Tse, P. Viswanath, X. Wang, and O. Zeitouni, Everything is a Race and Nakamoto Always Wins, CCS, 2020.
- E. Deirmentzoglou, G. Papakyriakopoulos, and C. Patsakis, A Survey on Long-Range Attacks for
Proof of Stake Protocols, IEEE Access, 2019.
- Tezos and Cardano, two examples of proof-of-stake longest-chain-type blockchains.
- Algorand, an example of a proof-of-stake BFT-type protocol.
- Lecture 12 (Tue Oct 19): Transaction fees. EIP-1559.
Supplementary reading:
- Lecture 13 (Thu Oct 21): The economic security of blockchains.
Supplementary reading:
- E. Budish, The Economic Limits of Bitcoin and the Blockchain, 2018.
- J. S. Gans and N. Gandal, More (or Less) Economic Limits of the Blockchain, 2019.
- D. J. Moroz, D. J. Aronoff, N. Narula, and D. C. Parkes, Double-Spend Counterattacks: Threat of Retaliation
in Proof-of-Work Systems, 2020.
- R. Auer, Beyond the doomsday
economics of “proof-ofwork” in cryptocurrencies, 2019.
- Hasu, J. Prestwich, and B. Curtis, A model for Bitcoin’s security and the
declining block subsidy, 2019.
- G. Huberman, J. D. Leshno, and C. Moallemi, Monopoly without a Monopolist: An Economic Analysis of the Bitcoin Payment System, 2021.
- Lecture 14 (Tue Oct 26): Deep dive on Bitcoin (UTXOs, Merkle trees, light clients, etc.). Supplementary reading:
- Lecture 15 (Thu Oct 28): Scaling Bitcoin.
Payment channels, hash time lock contracts (HTLCs), and the Lightning Network.
Supplementary reading:
- [no class on Tue Nov 2 --- academic holiday]
- Lecture 16 (Thu Nov 4): Ethereum deep dive: Turing-completeness, gas, accounts, transactions, Merkle-Patricia trees.
Supplementary reading:
- Lecture 17 (Tue Nov 9): Consensus vs. compute. The EVM. Straegies for scaling.
Supplementary reading:
- Lecture 18 (Thu Nov 11): Layer-2's. Sidechains. Optimistic rollups: fraud proofs and dispute resolution.
Supplementary reading:
- Lecture 19 (Tue Nov 16): Rollups with validity (aka zk) proofs. SNARGs.
Supplementary reading:
- Lecture 20 (Thu Nov 18): SNARKs. Validium and off-chain transaction data.
Supplementary reading:
- Lecture 21 (Tue Nov 23): A multi-chain world. Cross-chain bridges. Scaling at layer 1. Brief introduction to Solana and Avalanche.
Supplementary reading:
- [no class on Thu Nov 25 --- academic holiday]
- Lecture 22 (Tue Nov 30):
Oracles. Introduction to DeFi. Overcollateralized lending.
Supplementary reading:
- S. Eskandari, M. Salehi, W. C. Gu, and J. Clark,
SoK: Oracles from the Ground Truth to Market Manipulation, AFT '21.
- Defi MOOC lecture on oracles by Ari Juels.
- Chainlink Docs and latest white paper.
- Defi MOOC lecture on lending platforms by Arthur Gervais.
- K. Qin, L. Zhou, P. Gamito, P. Jovanovic, and A. Gervais, An Empirical Study of DeFi Liquidations: Incentives, Risks, and Instabilities, IMC '21.
More on Maker, Compound, and Aave.
Lecture 23 (Thu Dec 2): Trading, crypto exchanges, automated market makers, Uniswap, divergence loss.
Supplementary reading:
Lecture 24 (Tue Dec 7): Deep dive on automated market makers.
Price impact. StableSwap. The space of constant-function market-makers. Capital efficiency. Supplementary reading:
Lecture 25 (Thu Dec 9): Interactions between the consensus and application layers. Abitrage between AMMs. Priority gas auctions. Miner/maximal extractable value (MEV). Flashbots.
Supplementary reading:
- P. Daian, S. Goldfeder, T. Kell, Y. Li, X. Zhao, I. Bentov, L. Breidenbach, and A. Juels, Flash Boys 2.0: Frontrunning, Transaction Reordering, and Consensus Instability in Decentralized Exchanges, April 2019.
- MEV and Me (Noyes)
- Flashbots docs
- Latest on mitigating MEV in Ethereum: PBS on Ethereum Roadmap (MEV Roast 15)
- Down the MEV rabbit hole: Interview with a searcher (Uncommon Core)