MS&E 339: Algorithms for Decentralized Finance

Autumn 2022-23

Tu, Th 1:30-2:50pm
Bldg 200, room 303

INSTRUCTOR
Ashish Goel
ashishg@stanford.edu, 650 814 1478
Office Hours: M 4-5:30 pm, Huang 359.
Class forum: We will use ed stem as a discussion forum. All HW submissions will be on gradescope. Sign up links available here.

Auditors: please sign on to the mailman list msande339-aut2223-guests and let the instructor know (the mailing lists may not be active till the second lecture). The class will be entirely in person.


DESCRIPTION
The advent of cryptocurrencies, NFTs, and more generally, online financial instruments that are not controlled by large governments or banks, has resulted in many new and innovative mechanisms for decentralized finance. This class studies these new mechanisms from the viewpoint of algorithms, optimization, and market design. While blockchains have been a primary motivation behind many of these new developments, the resulting algorithmic and market design issues are more general, and we abstract away the specifics of blockchains and the underlying cryptographic primitives. Topics include distributed and multi-asset exchanges, liquidity pools, automated market makers, credit networks, and rollups (off-chain transactions). We draw connections between these new market mechanisms and more well-studied directions such as prediction markets and Arrow-Debreu equilibria. Includes a research project and a discussion of open directions.
Prerequisites: algorithms at the level of CS 161 and optimization at the level of MS&E 111

This is not a class on blockchains. Blockchains represent elegant technology, and have focused attention on the problems of decentralized finance. Blockchains will inform which problems we study and how we motivate them. And of course topics such as blockchain governance and adversarial aspects of decentralized finance can not be divorced from technical details of underlying blockchain design. But many of the core theoretical ideas we discuss in this class are independent of whether the underlying computational substrate is centralized or distributed, i.e., defi (as we will treat it in this class) is about market primitives being decentralized, not necessarily the underlying computation.

The class will be divided into five modules: decentralized currencies; decentralized exchanges (the largest one, including basic market theory, multi-asset exchanges, automated market makers, liquidity pools, and roll-ups); decentralized lending and pricing (e.g. pricing NFTs and limited edition tokens, and micro-lending); adversarial aspects of decentralized finance (front-running and Miner Extractable Value); and blockchain governance and regulation. In each topic, we will start with motivation, and then spend much of our time making and analyzing mathematical models, and designing and understanding algorithms. Along the way, we will provide a self-contained (but fairly quick) introduction to the following building blocks: max-flows; Arrow-Debreu Markets; the method of Lagrange multipliers in convex optimization; VCG auctions and mechanism design; social choice.

REQUIREMENTS
The course requirements will be:

1. Two HWs, which can be done in groups of 2-3 (60% of the grade). Given Oct 16, and Nov 18. Due Oct 28, and Dec 1, before midnight.
2. All HW and project submissions and grading etc will be on gradescope.
3. A project report with optional presentation (30%).

   Each report should be done in groups of 2-3, and should involve a survey of an open problem, along with possible directions, and some progress for small special cases (or even the full problem). The project selection will be due at the end of the 4th week of classes (Oct 21st), but you are welcome to get an early start if you like. A preview of suggested open problems to study will be presented during the third week of classes.
   
   Preliminary report due: Nov 17th along with your preference regarding giving a presentation.
   Final report due: Dec 6, midnight
   Brief 10 minute presentations of selected projects: Dec 8.

READING LIST
Will be released topic by topic. We will also make sketch of each lecture's notes or slides available the week after the lecture.

Weeks 1-3

You can get started by reading a basic description of Lightning.
Liquidity in Credit Networks. Slides: Credit Networks , a very quick Introduction to Max-flow and Markov Chains ; Paper: liquidity in credit networks.
Strategic Network Formation. Slides . Read introduction and background from an empirical paper and a theoretical paper on credit network formation.
Scribed Notes Part 1 and Part 2

Weeks 4-5

Introduction to Fisher Markets: Slides
Design of a Distributed Exchange: Slides
HW1 , due 10/28/22.
Scribed Notes Week 4 and Week 5

Weeks 6-8

Slides on Optimum CFMM design (distributed over email since they contain unpublished material; paper available on request)
Optimum routing with CFMMs (guest lecture by Guillermo Angeris)
Paper on incorporating batch exchanges into CFMMs
Paper on optimum limits for liquidity
Paper on cost-liquidity tradeoff
Paper on Byzantine consensus (classic -- must read)
Sketch slides on block fairness to avoid front-running
Paper on block fairness

Weeks 9-10

Rollups (guest lecture by Pankaj Gupta)
Paper on competitive auctions
Paper on retaliation-based equilibria in blockchains