COMS 6998-006: Foundations of Blockchains

submited by

Style Pass

2021-09-17 16:00:04

Announcements Sept 2: Welcome to COMS 6998-006! Sept 15: Notes for Lecture 1 posted. Sept 15: HW1 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 and Wednesdays 12:30-2:30pm, in the CS TA room on the first floor of Mudd.) Email: m.bahrani@columbia.edu.

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 Bitocin 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. Stablecoins, oracles. 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.

Coursework Problem Sets (60%): There will be a number of problem sets, around 8-9 in total. Problem sets can be completed in pairs. Homework #1 (Due Thu Sept 23.) 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.