-
Notifications
You must be signed in to change notification settings - Fork 5
/
index.html
610 lines (516 loc) · 31.4 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
<html>
<head>
<TITLE>COMS 6998-006: Foundations of Blockchains, Fall 2021</TITLE>
<link rel="stylesheet" type="text/css" href="main.css">
</head>
<body>
<h1>COMS 6998-006: Foundations of Blockchains</h1>
<p>
<b><p class="header">Announcements</p></b>
<ul>
<!--
<li>4/3: The <a href="e/e1.pdf">first exercise set</a> has been posted.
Further exercises sets will follow on a weekly basis, posted
under "Coursework" below
on Thursday or Friday. (Remember these are not to be turned in.)
-->
<li>Sept 2: Welcome to COMS 6998-006!</li>
<li>Sept 15: Notes for Lecture 1 posted.
<li>Sept 15: HW1 posted.
<li>Sept 20: Lecture room changed to CSG 451 (starting with lecture 4).
<li>Sept 28: HW2 posted.
<li>Nov 12: HW6 posted.
<li>Nov 12: Note the deadline for final reports is December 17th.
<li>Nov 19: HW7 posted.
<!--
<li>Nov 7: The final (non-cumulative) exam will be in class during the last meeting time, Monday December 9, 10:10-11:25am.
-->
</ul>
<b>Instructor:</b>
<ul>
<li>
<A HREF="http://timroughgarden.org/">Tim
Roughgarden</A> (Office hours: Tuesdays 5-6pm by Zoom. Email: tr@cs.columbia.edu.)
</ul>
<p>
<b>Course Assistants:</b>
<ul>
<li>
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.
<!--
<li>
Chengyu Lin
(Office hours: Tuesdays 2-3pm.
Email: chengyu@cs.columbia.edu.)
-->
</ul>
<p> <b>Time/location:</b> 8:40-9:55 AM Tue/Thu in <strike>Mudd 834</strike> CSB 451.
<p> <b>Discussion site:</b> <a href="https://edstem.org/us/courses/13815/discussion/">ed</a>.
<!--We'll be using
<a href="https://piazza.com/class#fall2019/comsw49952">Piazza.</a>-->
<!--
<p> <b>Email address for PSet submissions:</b>
cs261submissions@gmail.com
-->
<p> <b>Prerequisites</b>: 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.
<!--
<p>
<b>Course description:</b>
Randomness pervades the natural processes around us, from the
formation of networks, to genetic recombination, to quantum
physics. Randomness is also a powerful tool that can be leveraged to
create algorithms and data structures which, in many cases, are more
efficient and simpler than their deterministic counterparts. This
course covers the key tools of probabilistic analysis, and
applications of these tools to understand the behaviors of random
processes and algorithms. Emphasis is on theoretical foundations,
though we will apply this theory broadly, discussing applications in
machine learning and data analysis, networking, and systems.
-->
<p>
<b>Course outline</b> (subject to change):
<ul>
<li>Classical permissioned consensus.
<ul>
<li>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.
</ul>
<li>Permissionless consensus.
<ul>
<li>Nakamoto (longest-chain) consensus, guarantees for the Bitcoin backbone protocol, committee-based reductions to BFT-type permissioned protocols, the CAP theorem.
</ul>
<li>Sybil-resistance.
<ul>
<li>Proof-of-work, difficulty adjustment, selfish mining; proof-of-stake, VRFs and VDFs, etc.
</ul>
<li>Bitcoin deep dive.
<ul>
<li>Block structure, Merkle trees, UTXOs, light clients, scaling Bitcoin via payment channels and the Lightning network.
</ul>
<li>Ethereum deep dive.
<ul>
<li>Block structure, gas and the EVM, the EIP-1559 transaction fee mechanism, scaling Ethereum via optimistic and zk-rollups, plans for ETH 2.0.
</ul>
<li>Newer-generation layer-1 consensus protocols (e.g., Solana and Avalanche).
<li>The multi-chain vision: interoperability and bridges.
<li>DeFi (decentralized finance) primitives.
<ul>
<li>Stablecoins, oracles.
</ul>
<li>DeFi applications.
<ul>
<li>Borrowing, lending, trading via automated market makers.
</ul>
<li>Miner extractable value (MEV) and interactions between the consensus and application layers.
<li>(Time permitting) Approaches to protocol governance.
<li>(Time permitting) A look ahead: DAOs, NFTs, Web3, etc.
</ul>
<b>Textbook:</b> 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.
<p>
<b>Lecture notes:</b> (posted only sporadically, complete set should be ready in early 2022)
<ul>
<li><a href="l/l1.pdf">Lecture 1</a> (Introduction and Overview) [unedited 0th draft]
</ul>
<p>
<h3>Coursework</h3>
<ul>
<!--
<li><b>Exercise Sets (0%)</b>:
Exercise sets will be handed out weekly and are meant to help
you keep up with the course material.
Do not turn in your solutions. Think about them and discuss with
fellow students or the course staff any that you cannot answer.
At least half of each exam will consist of
problems on these exercise sets or variations thereof.
<ul>
<li><a href="e/e1.pdf">Week 1 Exercises</A> (Posted Wed Sept 4)
<li><a href="e/e2.pdf">Week 2 Exercises</a> (Posted Wed Sept 11)
<li><a href="e/e3.pdf">Week 3 Exercises</a> (Posted Wed Sept 18)
<li><a href="e/e4.pdf">Week 4 Exercises</a> (Posted Wed Sept 25)
<li><a href="e/e5.pdf">Week 5 Exercises</a> (Posted Wed Oct 2)
<li><a href="e/e6.pdf">Week 6 Exercises</a> (Posted Wed Oct 9)
<li><a href="e/e7.pdf">Week 7 Exercises</a> (Posted Wed Oct 16)
<li>[No exercise set on Oct 23.]
<li><a href="e/e8.pdf">Week 9 Exercises</a> (Posted Wed Oct 30)
<ul>
<li>Typo in Exercise 37 fixed 12/2/19.
</ul>
<li>[No exercise set on Nov 6.]
<li><a href="e/e9.pdf">Week 11 Exercises</a> (Posted Wed Nov 13)
<li><a href="e/e10.pdf">Week 12 Exercises</a> (Posted Wed Nov 20)
<ul>
<li>Typo in Exercise 48 fixed on 12/5/19.
</ul>
<li><a href="e/e11.pdf">Week 13-14 Exercises</a> (Posted Mon Dec 2)
</ul>
-->
<p>
<li><b>Problem Sets (60%)</b>:
There will be a number of problem sets, around 8-9 in total.
Problem sets can be completed in pairs.
<ul>
<li><a href="hw/hw1.pdf">Homework #1</a>
<strike>(Due Thu Sept 23.)</strike>
(Due Mon Sept 27.)
<li><a href="hw/hw2.pdf">Homework #2</a>
(Due Thu Oct 7.)
<li><a href="hw/hw3.pdf">Homework #3</a>
(Due Thu Oct 14.)
<li><a href="hw/hw4.pdf">Homework #4</a>
(Due Tue Oct 26.)
<li><a href="hw/hw5.pdf">Homework #5</a>
(Due Thu Nov 4.)
<li><a href="hw/hw6.pdf">Homework #6</a>
(Due Thu Nov 18.)
<li><a href="hw/hw7.pdf">Homework #7</a>
(Due Tue Nov 30.)
<li><a href="hw/hw8.pdf">Homework #8</a>
(Due Thu Dec 9.)
</ul>
<p>
<li><b>Problem Set Policies</b>:
<ul>
<li>To be submitted in groups of 2 (all students of the group receive the same score).
<li>You can form different pairs for different exercise sets.
<li>You can discuss exercises with students from other groups verbally and at a high level only.
<li>Except where otherwise noted, you may refer to your course notes, the
textbooks and research papers listed on the course Web
page <b>only</b>. 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.
<li>You are strongly encouraged to use LaTex to typeset your write-up.
Here's a <a href="template.tex">LaTeX template</a> that you can use to type up solutions.
<a href="https://www.google.com/url?q=http://en.wikibooks.org/wiki/LaTeX&source=gmail-html&ust=1631719240228000&usg=AFQjCNEuNSY9l5DmktEemkib9jOF6hNgJA" target="_blank" rel="noreferrer">Here</a> and
<a href="https://www.google.com/url?q=http://tobi.oetiker.ch/lshort/lshort.pdf&source=gmail-html&ust=1631719240228000&usg=AFQjCNFkvPO2dK4cJeaIQzBPB4IPMgNMAg" target="_blank" rel="noreferrer">here</a> are good introductions to LaTeX.
<li><b>Honor code:</b> We expect you to abide by the computer science department's
<a href="https://www.google.com/url?q=https://www.cs.columbia.edu/education/honesty/&source=gmail-html&ust=1631719240228000&usg=AFQjCNFF7AD5veejv_lHVVwLEvJa79SHAg" target="_blank" rel="noreferrer">policies and procedures regarding academic honesty</a>.
<li><b>Submission instructions:</b>
We are using Gradescope for the homework submissions. Go to
<a href="https://www.google.com/url?q=http://www.gradescope.com&source=gmail-html&ust=1631719240228000&usg=AFQjCNH3W_zHT4L79CO2nAePE25WgsDbwg" target="_blank" rel="noreferrer">www.gradescope.com</a> 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.
</li></li></li></li></li></li></li></ul></li>
<p>
<li><b>Late Days</b>:
<ul>
<li>One late day equals a 24-hour extension.
<li>Each student has three free late days.
<li>At most two late days can be applied to a single assignment.
<!--;
after Friday (following the original due date) no solutions
will be accepted.
-->
<li>Each late day used after the first two will result in a 25%
penalty.
<ul>
<li>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.
</ul>
</ul>
<p>
<li><b>Research project (40%)</b>: 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:
<ul>
<li><a href="reports/BCJN.pdf">Large Ethereum Contracts and Gas Fee Non-linearity</a> by Maryam Bahrani, Miranda Christ, Daniel Jaroslawicz, Eric Neyman
<li><a href="reports/ZLRL.pdf">Decentralized Prediction Markets</a> by Jianxiong Zhan, Chi Wai Lau, Lawan Rahim, Quoc Le
</ul>
<li><b>Deadline</b>: Friday, December 17.
</ul>
<p>
<h3>Lecture Schedule</h3>
<p>
<ul>
<li><b>Lecture 1 (Thu Sept 9):</b> 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:
<ul>
<li><a href="l/l1.pdf">Lecture notes</a>
<li><a href="https://decentralizedthoughts.github.io/2019-10-15-consensus-for-state-machine-replication/">Consensus for SMR</a> (Decentralized Thoughts)
</ul>
<p>
<li><b>Lecture 2 (Tue Sept 14):</b> The synchronous model and the Dolev-Strong protocol for Byzantine broadcast.
Supplementary reading:
<ul>
<li><a href="https://decentralizedthoughts.github.io/2019-12-22-dolev-strong/">Dolev-Strong Authenticated Broadcast</a> (Decentralized Thoughts)
<li><a href="http://www.cs.umd.edu/~jkatz/gradcrypto2/NOTES/lecture26.pdf">Lecture notes</a> from Jonathan Katz's advanced crypto course (see Section 3).
<li>Chapters 3 and 6 of Elaine Shi's book draft, <a href="http://elaineshi.com/docs/blockchain-book.pdf">Foundations of Distributed
Consensus and Blockchains</a>.
</ul>
Historical readings:
<ul>
<li>L. Lamport, R. Shostak, and M. Pease, <a href="https://lamport.azurewebsites.net/pubs/byz.pdf">The Byzantine Generals Problem</a>, ACM Transactions on Programming Languages and Systems, 1982.
<li>D. Dolev and H. R. Strong, <a href="https://www.cs.huji.ac.il/~dolev/pubs/authenticated.pdf">Authenticated Algorithms for Byzantine Agreement</a>, SIAM Journal on Computing, 1983.
</ul>
<p>
<li><b>Lecture 3 (Thu Sept 16):</b> Necessity of PKI for synchronous consensus with dishonest majority. Proof themes: simulation and indistinguishability.
Supplementary reading:
<ul>
<li><a href="https://decentralizedthoughts.github.io/2019-08-02-byzantine-agreement-is-impossible-for-$n-slash-leq-3-f$-is-the-adversary-can-easily-simulate/">Byzantine Agreement Is Impossible for n≤3f if the Adversary Can Simulate</a> (Decentralized Thoughts)
<li><a href="http://www.cs.umd.edu/~jkatz/gradcrypto2/NOTES/lecture26.pdf">Lecture notes</a> from Jonathan Katz's advanced crypto course (see Section 2).
<li>Chapter 4 of Elaine Shi's book draft, <a href="http://elaineshi.com/docs/blockchain-book.pdf">Foundations of Distributed
Consensus and Blockchains</a>.
</ul>
Historical readings:
<ul>
<li>M. Pease, R. Shostak, and L. Lamport, <a href="https://lamport.azurewebsites.net/pubs/reaching.pdf">Reaching Agreement in
the Presence of Faults</a>, Journal of the ACM, 1980.
<li>M. J. Fischer, N. A. Lynch, and M. Merritt, <a href="https://groups.csail.mit.edu/tds/papers/Lynch/FischerLynchMerritt-dc.pdf">Easy Impossibility Proofs for Distributed Consensus Problems</a>, Distributed Computing, 1986.
</ul>
<p>
<li><b>Lecture 4 (Tue Sept 21):</b> The asynchronous model. Start proof of FLP impossibility theorem.
Supplementary reading:
<ul>
<li><a href="https://decentralizedthoughts.github.io/2019-12-15-consensus-model-for-FLP/">Consensus Lower Bounds via Uncommitted Configurations</a> (Decentralized Thoughts)
<li>Chapter 12 of Elaine Shi's book draft, <a href="http://elaineshi.com/docs/blockchain-book.pdf">Foundations of Distributed
Consensus and Blockchains</a>.
</ul>
Historical readings:
<ul>
<li>M. J. Fischer, N. A. Lynch, and M. S. Paterson, <a href="https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf">Impossibility of Distributed Consensus with One Faulty
Process</a>, Journal of the ACM, 1985.
<li>H. Völzer, <a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.221.7907&rep=rep1&type=pdf">A Constructive Proof for FLP</a>, Information Processing Letters, 2004.
</ul>
<p>
<li><b>Lecture 5 (Thu Sept 23):</b> Finish proof of FLP impossibility theorem.
Supplementary reading: same as Lecture 4, and also:
<ul>
<li><a href="https://decentralizedthoughts.github.io/2019-12-15-asynchrony-uncommitted-lower-bound/">The FLP Impossibility, Asynchronous Consensus Lower Bound via Uncommitted Configurations</a> (Decentralized Thoughts)
</ul>
<p>
<li><b>Lecture 6 (Tue Sept 28):</b>
The partially synchronous model. The Tendermint protocol.
Supplementary reading:
<ul>
<li><a href="andy.pdf">Notes</a> by <a href="https://lewis-pye.com/">Andrew Lewis-Pye</a>.
<li><a href="https://decentralizedthoughts.github.io/2019-06-01-2019-5-31-models/">Synchrony, Asynchrony and Partial synchrony</a> (Decentralized Thoughts)
<li>Also related: <a href="https://decentralizedthoughts.github.io/2020-11-29-the-lock-commit-paradigm/">The Lock-Commit Paradigm</a> (Decentralized Thoughts)
<li><a href="https://docs.tendermint.com/v0.32/spec/consensus/consensus.html#">Tendermint Core</a> documentation.
</ul>
Historical readings:
<ul>
<li>C. Dwork, N. Lynch, and L. Stockmeyer, <a href="https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf">Consensus in the Presence of Partial Synchrony</a>, Journal of the ACM, 1988.
<li>E. Buchman, J. Kwon, and Z. Milosevic, <a href="https://arxiv.org/abs/1807.04938">The latest gossip on BFT consensus</a>, 2018.
</ul>
<p>
<li><b>Lecture 7 (Thu Sept 30):</b> Properties of Tendermint.
The CAP theorem. Supplementary readings same as above, and also:
<ul>
<li><a href="https://www.the-paper-trail.org/page/cap-faq/">The CAP FAQ</a> (Paper Trail)
</ul>
<p>
<li><b>Lecture 8 (Tue Oct 5):</b>
Longest-chain consensus.
Supplementary reading:
<ul>
<li>The <a href="https://bitcoin.org/bitcoin.pdf">Bitcoin white paper</a>, 2008.
<li><a href="https://decentralizedthoughts.github.io/2021-10-15-Nakamoto-Consensus/">Nakamoto's Longest-Chain Wins Protocol</a> (Decentralized Thoughts)
<li>Chapters 14 and 17 of Elaine Shi's book draft, <a href="http://elaineshi.com/docs/blockchain-book.pdf">Foundations of Distributed
Consensus and Blockchains</a>.
<li><a href="https://web.stanford.edu/class/ee374/downloads/notes03.pdf">Lecture notes</a> from David Tse's Internet-Scale Consensus in the Blockchain Era course
<li>I. Abraham and D. Malkhi, <a href="https://dahliamalkhi.github.io/files/BlockchainBFT-BEATCS2017.pdf">The Blockchain Consensus Layer and BFT</a>, Bulletin of the EATCS, 2017.
<li>J. A. Garay, A. Kiayias, and N. Leonardos,
<a href="https://eprint.iacr.org/2014/765.pdf">The Bitcoin Backbone Protocol: Analysis and Applications</a>, EUROCRYPT, 2015.
<li>R. Pass, L. Seeman, and a. shelat, <a href="https://eprint.iacr.org/2016/454.pdf">Analysis of the Blockchain Protocol in Asynchronous Networks</a>, EUROCRYPT, 2017.
</ul>
<p>
<li><b>Lecture 9 (Thu Oct 7):</b> The permissionless setting. Proof-of-work sybil-resistance. Difficulty adjustment.
Supplementary reading:
<ul>
<li>The <a href="https://bitcoin.org/bitcoin.pdf">Bitcoin white paper</a>, 2008.
<li>Chapters 14 of Elaine Shi's book draft, <a href="http://elaineshi.com/docs/blockchain-book.pdf">Foundations of Distributed
Consensus and Blockchains</a>.
<li>R. Pass and E. Shi, <a href="https://eprint.iacr.org/2018/302.pdf">Rethinking Large-Scale Consensus</a>, 2018.
<li>A. Lewis-Pye and T. Roughgarden,
<a href="https://arxiv.org/pdf/2101.07095.pdf">Byzantine Generals in the Permissionless Setting</a>, 2021.
</ul>
Historical readings:
<ul>
<li>C. Dwork and M. Naor, <a href="https://www.wisdom.weizmann.ac.il/~naor/PAPERS/pvp.pdf">Pricing via Processing or Combatting Junk Mail</a>, CRYPTO '92.
<li>A. Back, <a href="http://www.hashcash.org/hashcash.pdf">Hashcash - A Denial of Service Counter-Measure</a>, 2002.
</ul>
<p>
<li><b>Lecture 10 (Tue Oct 12):</b> Cryptocurrencies, block rewards, and selfish mining.
Supplementary reading:
<ul> <li>Chapters 15 of Elaine Shi's book draft, <a href="http://elaineshi.com/docs/blockchain-book.pdf">Foundations of Distributed
Consensus and Blockchains</a>.
<li><a href="https://web.stanford.edu/class/ee374/downloads/notes04.pdf">Lecture notes</a> from David Tse's Internet-Scale Consensus in the Blockchain Era course
<li>I. Eyal and E. G. Sirer, <a href="https://www.cs.cornell.edu/~ie53/publications/btcProcFC.pdf">Majority is not Enough:
Bitcoin Mining is Vulnerable</a>, FC '16 (also CACM '18).
</ul>
<p>
<li><b>Lecture 11 (Thu Oct 14):</b> Proof-of-stake sybil resistance.
Supplementary reading:
<ul>
<li>Lecture notes from David Tse's Internet-Scale Consensus in the Blockchain Era course: <a href="https://web.stanford.edu/class/ee374/downloads/notes13.pdf">lecture 1</a>, <a href="https://web.stanford.edu/class/ee374/downloads/notes14.pdf">lecture 2</a>, <a href="https://web.stanford.edu/class/ee374/downloads/notes15.pdf">lecture 3</a>
<li>J. Brown-Cohen, A. Narayanan, C.-A. Promas, and S. Matthew Weinberg, <a href="https://arxiv.org/pdf/1809.06528.pdf">Formal Barriers to Longest-Chain Proof-of-Stake Protocols</a>, EC '19.
<li>A. Dembo, S. Kannan, E. N. Tas, D. Tse, P. Viswanath, X. Wang, and O. Zeitouni, <a href="https://arxiv.org/pdf/2005.10484.pdf">Everything is a Race and Nakamoto Always Wins</a>, CCS, 2020.
<li>E. Deirmentzoglou, G. Papakyriakopoulos, and C. Patsakis, <a href="https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8653269">A Survey on Long-Range Attacks for
Proof of Stake Protocols</a>, IEEE Access, 2019.
<li><a href="https://wiki.tezosagora.org/learn/baking/proofofstake/consensus">Tezos</a> and <a href="https://developers.cardano.org/docs/stake-pool-course/introduction-to-cardano/">Cardano</a>, two examples of proof-of-stake longest-chain-type blockchains.
<li><a href="https://algorandcom.cdn.prismic.io/algorandcom%2Fa26acb80-b80c-46ff-a1ab-a8121f74f3a3_p51-gilad.pdf">Algorand</a>, an example of a proof-of-stake BFT-type protocol.
</ul>
<p>
<li><b>Lecture 12 (Tue Oct 19):</b> Transaction fees. EIP-1559.
Supplementary reading:
<ul>
<li>M. Carlsten, H. Kalodner, S. M. Weinberg, and A. Narayanan, <a href="https://www.cs.princeton.edu/~arvindn/publications/mining_CCS.pdf">On the Instability of Bitcoin Without the Block Reward</a>, CCS '16.
<li>V. Buterin, <a href="https://ethresear.ch/uploads/default/original/2X/1/197884012ada193318b67c4b777441e4a1830f49.pdf">Blockchain Resource Pricing</a>, 2018.
<li>T. Roughgarden, <a href="https://timroughgarden.org/papers/eip1559.pdf">Transaction Fee Mechanism Design for the Ethereum Blockchain:
An Economic Analysis of EIP-1559</a>, December 2020.
(Related <a href="https://www.youtube.com/watch?v=ndNyx-Oj9Wk">talk</a> from an Ethereum meetup)
</ul>
<p>
<li><b>Lecture 13 (Thu Oct 21):</b> The economic security of blockchains.
Supplementary reading:
<ul>
<li>E. Budish, <a href="https://faculty.chicagobooth.edu/eric.budish/research/Economic-Limits-Bitcoin-Blockchain.pdf">The Economic Limits of Bitcoin and the Blockchain</a>, 2018.
<li>J. S. Gans and N. Gandal, <a href="https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3494434">More (or Less) Economic Limits of the Blockchain</a>, 2019.
<li>D. J. Moroz, D. J. Aronoff, N. Narula, and D. C. Parkes, <a href="https://arxiv.org/pdf/2002.10736.pdf">Double-Spend Counterattacks: Threat of Retaliation
in Proof-of-Work Systems</a>, 2020.
<li>R. Auer, <a href="https://www.bis.org/publ/work765.pdf">Beyond the doomsday
economics of “proof-ofwork” in cryptocurrencies</a>, 2019.
<li>Hasu, J. Prestwich, and B. Curtis, <a href="https://uncommoncore.co/wp-content/uploads/2019/10/A-model-for-Bitcoins-security-and-the-declining-block-subsidy-v1.02.pdf">A model for Bitcoin’s security and the
declining block subsidy</a>, 2019.
<li>G. Huberman, J. D. Leshno, and C. Moallemi, <a href="https://academic.oup.com/restud/advance-article/doi/10.1093/restud/rdab014/6169547">Monopoly without a Monopolist: An Economic Analysis of the Bitcoin Payment System</a>, 2021.
</ul>
<p>
<li><b>Lecture 14 (Tue Oct 26):</b> Deep dive on Bitcoin (UTXOs, Merkle trees, light clients, etc.). Supplementary reading:
<ul>
<li>The <a href="https://bitcoin.org/bitcoin.pdf">Bitcoin white paper</a>, 2008.
<li>Chapters 1-3 of the book <a href="https://d28rh4a8wq0iu5.cloudfront.net/bitcointech/readings/princeton_bitcoin_book.pdf">Bitcoin and Cryptocurrency Technologies</a>, by A. Narayanan, J. Bonneau, E. Felten,
A. Miller, and S. Goldfeder (draft from 2016).
</ul>
<p>
<li><b>Lecture 15 (Thu Oct 28):</b> Scaling Bitcoin.
Payment channels, hash time lock contracts (HTLCs), and the Lightning Network.
Supplementary reading:
<ul>
<li>J. Poon and T. Dryja, <a href="https://lightning.network/lightning-network-paper.pdf">The Bitcoin Lightning Network:
Scalable Off-Chain Instant Payments</a>, 2016.
<li>Lightning network in depth, <a href="https://medium.com/softblocks/lightning-network-in-depth-part-1-payment-channels-b943607950dd">Part 1</a> and <a href="https://medium.com/softblocks/lightning-network-in-depth-part-2-htlc-and-payment-routing-db46aea445a8">Part 2</a>, 2018.
</ul>
<p>
<li>[no class on Tue Nov 2 --- academic holiday]
<p>
<li><b>Lecture 16 (Thu Nov 4):</b> Ethereum deep dive: Turing-completeness, gas, accounts, transactions, Merkle-Patricia trees.
Supplementary reading:
<ul>
<li>Increasing order of detail:
<a href="https://ethereum.org/en/whitepaper/">white paper</a>; <a href="https://cryptopapers.info/assets/pdf/eth_beige.pdf">beige paper</a>; <a href="https://ethereum.github.io/yellowpaper/paper.pdf">yellow paper</a>
<li><a href="https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/">Merkling in Ethereum</a> (Buterin)
<li><a href="https://ethereum.org/en/developers/docs/">Ethereum docs</a>
</ul>
<p>
<li><b>Lecture 17 (Tue Nov 9):</b> Consensus vs. compute. The EVM. Straegies for scaling.
Supplementary reading:
<ul>
<li><a href="https://takenobu-hs.github.io/downloads/ethereum_evm_illustrated.pdf">Ethereum EVM illustrated</a> (Takenobu)
</ul>
<p>
<li><b>Lecture 18 (Thu Nov 11):</b> Layer-2's. Sidechains. Optimistic rollups: fraud proofs and dispute resolution.
Supplementary reading:
<ul>
<li><a href="https://vitalik.ca/general/2021/01/05/rollup.html">An Incomplete Guide to Rollups</a> (Buterin)
<li>P. McCorry, C. Buckland, B. Yee, and D. Song,
<a href="https://stonecoldpat.github.io/images/validatingbridges.pdf">SoK: Validating Bridges as a Scaling Solution for
Blockchains</a>, October 2021.
<li><a href="https://medium.com/plasma-group/ethereum-smart-contracts-in-l2-optimistic-rollup-2c1cef2ec537">Ethereum Smart Contracts in L2: Optimistic Rollup</a> (Floersch)
<li>Specific implementations of optimistic rollups:
<a href="https://community.optimism.io/">Optimism</a>
(see also
Konstantopoulos
(<a href="https://research.paradigm.xyz/rollups">Part 1<a> and <a href="https://research.paradigm.xyz/optimism">Part 2</a>)
and
<a href="https://medium.com/onther-tech/fast-withdrawals-in-optimistic-rollups-part-1-6fbb93abf1c3">Surendran</a>)
and <a href="https://developer.offchainlabs.com/docs/inside_arbitrum">Arbitrum</a> (see also <a href="https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-kalodner.pdf">Kalodner et al.</a>)
<li>More on dispute resolution in Optimism vs. Arbitrum:
<a href="https://insights.deribit.com/market-research/making-sense-of-rollups-part-2-dispute-resolution-on-arbitrum-and-optimism/">Simon</a>
and <a href="https://medium.com/@cpbuckland88/fraud-proofs-and-virtual-machines-2826a3412099">Buckland</a>
<li><a href="https://l2beat.com/faq/">L2BEAT FAQ</a>
</ul>
<p>
<li><b>Lecture 19 (Tue Nov 16):</b> Rollups with validity (aka zk) proofs. SNARGs.
Supplementary reading:
<ul>
<li>SNARGs and SNARKs via the PCP theorem: <a href="https://people.csail.mit.edu/vinodv/6892-Fall2013/efficientargs.pdf">Kilian</a> and <a href="https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/Computationally_Sound_Proofs.pdf">Micali</a>.
</ul>
<p>
<li><b>Lecture 20 (Thu Nov 18):</b> SNARKs. Validium and off-chain transaction data.
Supplementary reading:
<ul>
<li>More on modern constructions of SNARKs: <a href="https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/">Reitwiessner</a>,
<a href="https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6">Buterin (1)</a>, <a href="https://vitalik.ca/general/2021/01/26/snarks.html">Buterin (2)</a>, <a href="https://vitalik.ca/general/2021/11/05/halo.html">Buterin (3)</a>.
<li>More on <a href="https://www.buildblockchain.tech/newsletter/issues/no-99-validium-and-the-layer-2-two-by-two">validium</a>.
</ul>
<p>
<li><b>Lecture 21 (Tue Nov 23):</b> A multi-chain world. Cross-chain bridges. Scaling at layer 1. Brief introduction to Solana and Avalanche.
Supplementary reading:
<ul>
<li><a href="https://medium.com/dragonfly-research/secure-the-bridge-cross-chain-communication-done-right-part-i-993f76ffed5d">Secure The Bridge: Cross-Chain Communication Done Right</a> (Wan)
<li>A couple examples of bridges: <a href="https://blog.nil.foundation/2021/10/14/solana-ethereum-bridge">Solana-Ethereum</a> and <a href="https://near.org/blog/eth-near-rainbow-bridge/">NEAR-Ethereum</a>.
<li><a href="https://docs.solana.com/cluster/overview">Solana docs</a>; see also the <a href="https://solana.com/solana-whitepaper.pdf">white paper</a> and the
<a href="https://www.shinobi-systems.com/primer.html">Shinobi Systems primer</a>.
<li><a href="https://docs.avax.network/learn/platform-overview/avalanche-consensus">Avalanche docs</a>; see also the <a href="https://assets.website-files.com/5d80307810123f5ffbb34d6e/6009805681b416f34dcae012_Avalanche%20Consensus%20Whitepaper.pdf">white paper</a> and <a href="https://gyuho.dev/nakamoto-bitcoin-vs-snow-avalanche-consensus.html">Lee's primer</a>.
</ul>
<p>
<li>[no class on Thu Nov 25 --- academic holiday]
<p>
<li><b>Lecture 22 (Tue Nov 30):</b>
Oracles. Introduction to DeFi. Overcollateralized lending.
Supplementary reading:
<ul>
<li>S. Eskandari, M. Salehi, W. C. Gu, and J. Clark,
<a href="https://arxiv.org/pdf/2106.00667.pdf">SoK: Oracles from the Ground Truth to Market Manipulation</a>, AFT '21.
<li><a href="https://www.youtube.com/watch?v=vFcW18ZpPZ4">Defi MOOC lecture</a> on oracles by Ari Juels.
<li><a href="https://docs.chain.link/">Chainlink Docs</a> and <a href="https://research.chain.link/whitepaper-v2.pdf">latest white paper</a>.
<li><a href="https://www.youtube.com/watch?v=dKk9rGWDoTI">Defi MOOC lecture</a> on lending platforms by Arthur Gervais.
<li>K. Qin, L. Zhou, P. Gamito, P. Jovanovic, and A. Gervais, <a href="https://arxiv.org/pdf/2106.06389.pdf">An Empirical Study of DeFi Liquidations: Incentives, Risks, and Instabilities</a>, IMC '21.
</a>
<li>More on <a href="https://makerdao.com/en/whitepaper/#abstract">Maker</a>, <a href="https://compound.finance/documents/Compound.Whitepaper.pdf">Compound</a>, and <a href="https://github.com/aave/protocol-v2/blob/master/aave-v2-whitepaper.pdf">Aave</a>.
</ul>
<p>
<li><b>Lecture 23 (Thu Dec 2):</b> Trading, crypto exchanges, automated market makers, Uniswap, divergence loss.
Supplementary reading:
<ul>
<li><a href="https://timroughgarden.org/f16/l/l18.pdf">Lecture notes</a>
on continuous double auctions and automated market makers.
<li><a href="https://thecontrol.co/a-comparison-of-decentralized-exchange-designs-1deef249f56a">A Comparison of Decentralized Exchange Designs</a> (Chen)
<li>The <a href="https://blog.gnosis.pm/building-a-decentralized-exchange-in-ethereum-eea4e7452d6e">x*y=k curve</a> (Lu)
<li><a href="https://uniswap.org/whitepaper.pdf">Uniswap (v2)</a> (Adams, Zinsmeister, Robinson)
</ul>
<p>
<li><b>Lecture 24 (Tue Dec 7):</b> Deep dive on automated market makers.
Price impact. StableSwap. The space of constant-function market-makers. Capital efficiency. Supplementary reading:
<ul>
<li>G. Angeris and T. Chitra, <a href="https://web.stanford.edu/~guillean/papers/constant_function_amms.pdf">Improved Price Oracles: Constant Function Market Makers</a>, AFT '20.
<li>D. Engel and M. Herlihy, <a href="https://arxiv.org/pdf/2110.09872.pdf"> Loss and Slippage
in Networks of Automated Market Makers</a>, 2021.
<li><a href="https://curve.fi/files/stableswap-paper.pdf">StableSwap white paper</a> (Egorov)
<li><a href="https://uniswap.org/whitepaper-v3.pdf">Uniswap v3 white paper</a> (Adams, Zinsmeister, Salem, Keefer, Robinson)
</ul>
<p>
<li><b>Lecture 25 (Thu Dec 9):</b> Interactions between the consensus and application layers. Abitrage. Priority gas auctions. Miner/maximal extractable value (MEV). Flashbots.
Supplementary reading:
<ul>
<li>P. Daian, S. Goldfeder, T. Kell, Y. Li, X. Zhao, I. Bentov, L. Breidenbach, and A. Juels, <a href="https://arxiv.org/pdf/1904.05234.pdf">Flash Boys 2.0: Frontrunning, Transaction Reordering, and Consensus Instability in Decentralized Exchanges</a>, April 2019.
<li><a href="https://research.paradigm.xyz/MEV">MEV and Me</a> (Noyes)
<li><a href="https://docs.flashbots.net/flashbots-auction/overview">Flashbots docs</a>
<li>Latest on mitigating MEV in Ethereum: <a href="https://github.com/flashbots/pm/issues/98">PBS on Ethereum Roadmap</a>
<li>Down the MEV rabbit hole: <a href="https://www.youtube.com/watch?v=6jfSlDvH77k">Interview with a searcher</a>
</ul>
<p>
</ul>