COMPSCI 461/661 Secure Distributed Systems

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

 

Multimodal Class

This course will make use of a multimodal classroom model. Students meet once a week in person and also watch pre-recorded lectures online and complete readings. In-person meetings are mandatory and carried out assuming that students have not only completed readings and assignments, but that the pre-recorded lectures have been viewed. There may be some work assigned and completed during discussions (included in the written assignments portion of the grade, if graded).

The pre-recorded lectures are 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, and 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.

 

Credits: 
3
Date: 
Tuesday, January 21, 2020 to Thursday, May 7, 2020
Tuesday, January 22, 2019 to Wednesday, May 22, 2019
Monday, January 22, 2018 to Thursday, May 10, 2018
Class meets on: 
Monday
Online
Instructor: 
G. Andrew Stone
Infosec
CompSci
Graduate
Undergraduate
January, 2020