CS 6432 (Distributed Consensus and Blockchains)

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:

  1. 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 ]
  2. Byzantine Agreement Through Herding
    • Date : Aug 30, Sept 6, Sept 11, 2017
  3. 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 ]
  4. State Machine Replication
    • Date : Sept 18, 2017
  5. 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 ]
  6. 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 ]
  7. GradeCast
    • Date: Oct 11, 2017
    • Helpful Readings:
      • Feldman, P., & Micali, S. (1997). An optimal probabilistic protocol for synchronous Byzantine agreement. SIAM Journal on Computing , 26 (4), 873-933. [ link ]
      • Micali, S., & Vaikuntanathan, V. (2017). Optimal and Player-Replaceable Consensus with an Honest Majority. [ link ]
  8. 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 ]
  9. PBFT Protocol
    • Date: Oct 18, 2017
    • Helpful Readings:
      • Castro, Miguel, and Barbara Liskov. “Practical Byzantine fault tolerance.” OSDI . Vol. 99. 1999. [ link ]
  10. 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 ]
  11. 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 ]
  12. Large-scale Consensus Cont'

    • Date: Nov 8, 2017