CS461/ CS661
Secure Distributed Systems

Prof. Brian Levine
3 credits; Spring 2019


461 Syllabus [pdf]
661 Syllabus [pdf]


This is a class devoted to the study of securing distributed systems, with decentralized digital currencies serving as our real platform of interest. Examples of such decentralized systems include Bitcoin and Ethereum, which are both open source, the subject of great academic interest, and supporting an enormous user base.

We'll start with the fundamentals of Lamport's, Fischer's, and Douceur's results that fence-in consensus systems, including blockchains. We'll also look at the efficiency of the network architectures for peer-to-peer communication and attacks on their security (e.g., eclipse and other denial of service attacks). And we'll review applied crypto such as elliptical curves (used to validate transactions). Other topics include privacy, economics, and finance.

In many ways, our goal is to explore this broad collection of topics in security, network, and distributed systems with blockchains being the common thread that allows a cohesive structure. You'll learn a lot in this class that is applicable well beyond blockchains.

There will be no textbook. There will be about 8 takehome assignments, many focused on programming but some focused on written exercises. We'll read a number of research articles, and several of my own in-class notes/memos. There will be small in-class assignments during the in-person discussion sections (see below about the flipped classroom model).

You must use Python for these assignments. Later in the semester, we’ll write Ethereum software contracts in a language called Solidity that I don’t expect you to have used before (it’s similar to java/python/C), and partially in javascript, which I also don’t expect you to have used. Honestly, the documentation for Solidity isn't the best, so be prepared to leverage past programming experience.

Here is a high-level overview of topics (not necessarily in this order).

  1. Applied cryptography
    • definition of security
    • hash functions
    • Merkle trees
    • public/private key crypto using elliptical curves
  2. Blockchains
    • Nakamoto consensus
    • Details of Bitcoin: transactions, blocks, p2p networking
    • Ethics
    • Doublespend attacks (including Gambler's Ruin)
    • Selfish mining attacks
    • Eclipse attacks
  3. Distributed Systems
    • Doucer's Sybil attack impossibility result
    • Clocks: NTP and Lamport clocks
    • Lamport's byzantine general's result
    • Fischer, Lynch, and Paterson's(FLP) impossibility result
  4. More Bitcoin Details
    • Bitcoin's scripting language
    • Difficulty adjustment algorithms and hashrate estimation
    • Transaction malleability
    • Lightning networks
    • Segwit
  5. Ethereum
    • Ghost
    • ETHASH
    • OP codes
    • Patricia Merkle Trees
    • DAPPS
    • Programming Ethereum with Solidity
  6. Finance
    • basic overview of economic metrics
    • basic overview of financial instruments (derivatives, etc)
    • Initial Coin Offerings
    • Using futures contracts to insure DAPPs
  7. Improving Blockchain performance
    • Bloom filters
    • Invertible Bloom Lookup Tables (IBLTs)
    • Compact Blocks
    • Graphene
    • Low variance mining with Bobtail
    • Proof of stake based blockchains
    • DAG-based blockchains

Flipped Classroom

This course will be making use of a flipped classroom model. Lectures will be pre-recorded and available online. We meet once a week for discussion only. Discussions are with Professor Levine, not a TA. Discussions will be carried out assuming that students have not only completed readings and assignments, but that the pre-recorded lectures have been viewed. There will be some work assigned and completed during discussions (included in the written assignments portion of the grade).

cs461 is not an online class --- it is a hybrid class. The discussion sections are once a week and attendance in discussions is mandatory.

Students in the CS MS degree must enroll in cs661 as a hybrid class. Non-matriculated students can enroll in the online class, and with permission MS degree students may do so as well (for example, if they are off campus for the semester). In either case, attendance in discussions is mandatory.

The pre-recorded lectures will be the same for 461 and 661, however we will go deeper into certain topics in 661 (e.g., Chernoff bounds). The discussion sections for 461 will focus more on practical topics, whereas the 661 sections will focus more on research papers but there will be overlap. Students are welcome to attend both discussions if there is room capacity. The assignments will be shared at their core, but the tasks may be slightly different.

Prerequisites

For 461: Students are required to have a "C" grade or higher in one of the following COMPSCI courses (or their equivalents): 326, 345, 377, 453, 460, 497P, 590CC.

For 661: Students must be graduate students in ECE or CS.

If you want in but you aren't in CS or ECE, we can talk. My first question will be about your programming background. Know that I rarely allow audits, but you are welcome to ask.