COMS 4995-001: The Science of Blockchains, Spring 2025
- Jan 22: Welcome to COMS 4995-001!
Instructor:
-
Tim
Roughgarden (Office hours: Mondays/Wednesday after class (until 10:45am), in Mudd 410. Email: tim.roughgarden@gmail.com.)
Course Assistants:
-
Naveen Durvasula
(Office hours: Mondays 11am-12:30pm, Tuesdays 1:30-2:30pm, and Wednesdays 1-2:30pm, in Mudd 416. Email: nkd2126@columbia.edu.)
-
Yuval Efron
(Office hours: Tuesdays 10am-noon, in CSB 522.
Email: ye2210@columbia.edu.)
Time/location:
- Required lectures: 8:40-9:55 AM on Mondays and Wednesdays in CSB 451.
- Optional sections: 8:40-9:55 AM on selected Fridays in CSB 451.
Discussion site:
ed.
Prerequisites:
Familiarity with computer science systems and theory at the level of COMS W3261 and COMS W3827.
The intended audience is advanced undergradates and beginning graduate students in computer science and adjacent fields.
Course description: Principles and practice of blockchain
protocol design. Consensus, execution, virtual machines, smart
contracts. Rollups and other approaches to scalability, authenticated
data structures, light clients, bridges, optimistic and SNARK-based
designs. Transaction fee mechanisms. Data
availability. Mempools. Proof-of-work, proof-of-stake, incentives for
validators. Application of these principles in practical protocols such as
Bitcoin and Ethereum.
Coursework
- Project (50%): To be completed in teams of 3-4
students. Further details TBA.
- Deadline for project proposal: Friday, March 14.
- Deadline for final deliverables: TBD.
- Course participation (10%): Based on attendance and participation in
lecture and office hours. We reserve the right to have occassional
in-class pop quizzes. Attendance at Friday sections is optional,
though we reserve the right to award a small number of extra credit
points for attending them.
- If you need to miss a class (for legitimate reasons), notify the TAs at least 24 hours in advance.
- Homeworks (40%):
There will be a number of homeworks, around 8-9 in total, which may
include theory, reading responses, small coding exercises, etc.
Homeworks can be completed in pairs.
- Homework 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.
The course code is 957287. Only one group member
needs to submit each assignment. When submitting, please remember to
add all group member names into Gradescope.
- Late Days:
- Late days cannot be applied to project deadlines (only to homework).
- 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.
Lecture Schedule
Note: Everything below is subject to change!
Part I: Building a Shared Global Virtual Machine
- Lecture 1 (Wed Jan 22):
Course overview and main themes. Introuduction to the "computer
in the sky." Analogies with the operating system of a computer
and the IP layer of the networking stack. Decentralization and property rights for digital assets.
Supplementary reading and additional resources (optional unless otherwise noted):
-
[no optional section on Fri Jan 24]
- Lecture 2 (Mon Jan 27):
The SMR (state machine replication) problem.
Defining consensus, consistency, and liveness.
Degrees of faulty validators and asynchrony.
Security thresholds.
General resources on blockchain consensus:
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 3 (Wed Jan 29):
Solving the SMR problem with crash faults and a synchronous network.
Supplementary reading and additional resources (optional unless otherwise noted):
- Bonus Lecture 1 (Fri Jan 31):
The FLP theorem: on the impossibility of consensus in asynchrony.
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 4 (Mon Feb 3):
The partially synchronous model.
Limits on what is possible.
Solving the SMR problem in partial synchrony with crash faults (via
Paxos/Raft).
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 5 (Wed Feb 5):
The challenges of Byzantine faults. Digitial signature schemes. Limits
on what is possible in partial synchrony.
Supplementary reading and additional resources (optional unless otherwise noted):
- Bonus Lecture 2 (Fri Feb 7):
Digital signature schemes in a blockchain context (part 1 of 2).
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 6 (Mon Feb 10):
Tendermint: Solving the SMR problem in partial synchrony with
Byzantine faults.
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 7 (Wed Feb 12):
The CAP principle. Longest-chain consensus.
Supplementary reading and additional resources (optional unless otherwise noted):
- Bonus Lecture 3 (Fri Feb 14):
Digital signature schemes in a blockchain context (part 2 of 2).
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 8 (Mon Feb 17):
Virtual machines and the execution layer.
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 9 (Wed Feb 19):
Virtual machines and the execution layer (con'd).
Supplementary reading and additional resources (optional unless otherwise noted):
-
[no optional section on Fri Feb 21]
Part II: Scaling Up a Shared Global Virtual Machine
- Lecture 10 (Mon Feb 24): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 11 (Wed Feb 26): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
-
[further Friday optional sections TBD]
- Lecture 12 (Mon Mar 3): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 13 (Wed Mar 5): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 14 (Mon Mar 10): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 15 (Wed Mar 12): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
-
[spring break, no lectures week of March 17--21]
- Lecture 16 (Mon Mar 24): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 17 (Wed Mar 26): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 18 (Mon Mar 31): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 19 (Wed Apr 2): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
Part III: Permissionless Validation
- Lecture 20 (Mon Apr 7): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 21 (Wed Apr 9): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 22 (Mon Apr 14): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 23 (Wed Apr 16): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 24 (Mon Apr 21): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 25 (Wed Apr 23): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 26 (Mon Apr 28): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 27 (Wed Apr 30): TBD
Supplementary reading and additional resources (optional unless otherwise noted):
- Lecture 28 (Mon May 5): TBD
Supplementary reading and additional resources (optional unless otherwise noted):