Course Offering : Fall 2017
Room : Gates 405
Instructor: Elaine Shi
Instructor Office Hours: By appointment
TA: Abhinav Aggarwal (aa2538 at cornell dot edu)
TA Office Hours : Mondays, 5-7PM, Gates 441
Grading :
Scribes: 35%
Homework: 20%
Final project (groups of 2): 45%
(Tentative) Course Outline :
Synchronous Consensus
- Dolev-Strong
- Byzantine agreement through herding
- Lamport’s lower bound
- State machine replication
- Synchronous byzantine agreement to state machine replication
Partially synchronous/asynchronous consensus
- FLP lower bound
- Dwork-Lynch-Stockmeyer lower bound
- Rabin/Ben-Or binary agreement
- Partially synchronous binary agreement
- State machine replication: PBFT
Permissionless setting and blockchains
- The permissionless model and lower bounds
- Blockchain definition
- Nakamoto analysis
- Selfish mining and Fruitchains
Lectures:
-
Dolev-Strong Protocol
- Date : Aug 28, 2017
-
Helpful Readings :
- Dolev, Danny, and H. Raymond Strong. “Authenticated algorithms for Byzantine agreement.” SIAM Journal on Computing 12.4 (1983): 656-666. [ link ]
-
Byzantine Agreement Through Herding
- Date : Aug 30, Sept 6, Sept 11, 2017
-
Lamport’s Lower Bound
- Date : Sept 13, 2017
-
Helpful Readings :
- Fischer, Michael J., Nancy A. Lynch, and Michael Merritt. “Easy impossibility proofs for distributed consensus problems.” Distributed Computing 1.1 (1986): 26-39. [ link ]
- Pease, Marshall, Robert Shostak, and Leslie Lamport. “Reaching agreement in the presence of faults.” Journal of the ACM (JACM) 27.2 (1980): 228-234. [ link ]
-
State Machine Replication
- Date : Sept 18, 2017
-
Blockchain Definition and Analysis of Nakamoto Consensus
- Date : Sept 20, Sept 25, Sept 28, Oct 2, 2017
-
Helpful Readings:
- Pass, Rafael, and Elaine Shi. “Rethinking Large-Scale Consensus.” Computer Security Foundations Symposium (CSF), 2017 IEEE 30th . IEEE, 2017. [ link ]
- Pass, R., Seeman, L., & Shelat, A. (2017, April). Analysis of the blockchain protocol in asynchronous networks. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 643-673). Springer, Cham. [ link ]
-
Selfish Mining and Fruitchains
- Date : Oct 4, 2017
-
Helpful Readings :
- Pass, Rafael, and Elaine Shi. “Fruitchains: A fair blockchain.” Proceedings of the ACM Symposium on Principles of Distributed Computing . ACM, 2017. [ link ]
- Eyal, Ittay, and Emin Gün Sirer. “Majority is not enough: Bitcoin mining is vulnerable.” International conference on financial cryptography and data security . Springer, Berlin, Heidelberg, 2014. [ link ]
- Carlsten, Miles, et al. “On the instability of bitcoin without the block reward.” Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security . ACM, 2016. [ link ]
-
GradeCast
- Date: Oct 11, 2017
- Helpful Readings:
-
Partially Synchronous Model, FLP and DLS Lower Bounds
- Date: Oct 16, 2017
-
Helpful Readings:
- Dwork, C., Lynch, N., & Stockmeyer, L. (1988). Consensus in the presence of partial synchrony. Journal of the ACM (JACM) , 35 (2), 288-323. [ link ]
- Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. “Impossibility of distributed consensus with one faulty process.” Journal of the ACM (JACM) 32.2 (1985): 374-382. [ link ]
-
PBFT Protocol
- Date: Oct 18, 2017
-
Helpful Readings:
- Castro, Miguel, and Barbara Liskov. “Practical Byzantine fault tolerance.” OSDI . Vol. 99. 1999. [ link ]
-
Asynchronous Binary Agreement – Ben-Or’s Protocol
- Date: Oct 30, 2017
-
Helpful Readings:
- Aguilera, Marcos K., and Sam Toueg. “The correctness proof of Ben-Or’s randomized consensus algorithm.” Distributed Computing 25.5 (2012): 371-381. [ link ]
- Large-scale Consensus
- Date: Nov 6, 2017
- Helpful Readings:
- Rafael Pass, and Elaine Shi. "Rethinking large-scale consensus." Computer Security Foundations Symposium (CSF) (2017). [ link ]
- Large-scale Consensus Cont'
- Date: Nov 8, 2017