The University of Chicago
Department of Computer Science

MPCS 56600 Course Syllabus

Introduction to Blockchain

Summer 2018


Instructor:        Mark Shacklette
Office:               Young 208B
Office Hours:    Thursdays 3:30 PM - 5:30 PM and by Appt.

email:    mark@cs.uchicago.edu (read hourly or so)
              mshack@post.harvard.edu (read hourly or so)

Teaching staff: 

Lead TA:          Paul Bossi
Focus:               Class Operations and Lead TA
Office Hours:   T.B.D.
email:     T.B.D.

TA:            John Hadidian-Baugher
Focus:        Networking, Docker, Team Organization & Facilitation
Office Hours:    T.B.D.
email:     T.B.D.

TA:            Terry Lynch
Focus:        Algorithms & Math
Office Hours:    T.B.D.
email:     T.B.D.

Piazza signup here.

 
SUBJECT COURSE TITLE TIME BUILDING
324 56600 Introduction to Blockchain:  Concepts, Technologies, Implementations Thursday, 5:30pm Ryerson 276

I. TEXT AND MATERIALS 

Texts: Required

Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction, Narayanan, et. al. Princeton, 2016.  ISBN: 978-0691171692

Mastering Bitcoin:  Programming the Open Blockchain, 2nd ed., Antonopoulos, O'Reilly, 2017.  ISBN:  978-1491954386

Texts: Highly Recommended

Docker Cookbook, Miell & Sayers, Manning, 2016, ISBN: 9781491919712

Docker in Practice, Sebastien Goasguen, O'Reilly, 2016, ISBN: 9781617292729

Recommended Reading

A Design Principle for Hash Functions, Damgard.  Cluster pub directory:  ~/mark/pub/56600/pfds/Damgard.A.Design.Principle.for.Hash.Functions.pdf

Is Bitcoin a Real Currency?  An Economic Appraisal (download linked file):  http://www.nber.org/papers/w19747

PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric, Donald Morrison, Journal of the ACM, 15(4):514-534, October 1968

Bitcoin and The Age of Bespoke Silicon.  Taylor.  http://cseweb.ucsd.edu/~mbtaylor/papers/bitcoin_taylor_cases_2013.pdf

Majority is not Enough: Bitcoin Mining is Vulnerable.  Eyal et. al.  http://www.cs.cornell.edu/~ie53/publications/btcProcFC.pdf

Measuring the Longitudinal Evolution of the Online Anonymous Marketplace Ecosystem.  Soska et. al.  https://www.usenix.org/system/files/conference/usenixsecurity15/sec15-paper-soska.pdf

March 2013 Chain Fork Post-Mortem.  https://github.com/bitcoin/bips/blob/master/bip-0050.mediawiki

Bitcoin-NG: A Scalable Blockchain Protocol.  Eyal et. al. https://www.usenix.org/system/files/conference/nsdi16/nsdi16-paper-eyal.pdf

Zerocoin: Anonymous Distributed E-Cash from Bitcoin.  Miers, et. al.  http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf

Zerocash: Decentralized Anonymous Payments from Bitcoin.  Ben-Sasson, et. al.  http://zerocash-project.org/media/pdf/zerocash-extended-20140518.pdf

A Next-Generation Smart Contract and Decentralized Application Platform.  https://github.com/ethereum/wiki/wiki/White-Paper

Ethereum:  A Secure Decentralised Generalised Transaction Ledger.  Wood.  http://gavwood.com/paper.pdf.

Ethereum Background.  https://solidity.readthedocs.io/en/develop/introduction-to-smart-contracts.html

The Hard Fork: What's About to Happen to Ethereum and The DAO. Castillo.  https://www.coindesk.com/hard-fork-ethereum-dao/

To fork or not to fork.  Wilcke.  https://blog.ethereum.org/2016/07/15/to-fork-or-not-to-fork/

Scanning Live Ethereum Contracts for the "Unchecked-Send" Bug.  Wen et. al.  http://hackingdistributed.com/2016/06/16/scanning-live-ethereum-contracts-for-bugs/

Enabling Blockchain Innovations with Pegged Sidechains.  Back, et. al.  https://blockstream.com/sidechains.pdf

A Fast and Scalable Payment Network with Bitcoin Duplex Micropayment Channels.  Decker, et. al.  http://www.tik.ee.ethz.ch/file/716b955c130e6c703fac336ea17b1670/duplex-micropayment-channels.pdf

Introduction to post-quantum cryptography.  Bernstein.  https://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf

Mimblewimble.  Poelstra.  https://scalingbitcoin.org/papers/mimblewimble.pdf

Ripple Consensus Whitepaper https://ripple.com/files/ripple_consensus_whitepaper.pdf

Exploiting Ripple Transaction Ordering For Fun And Profit http://availableimagination.com/exploiting-ripple-transaction-ordering-for-fun-and-profit/

II. PREREQUISITE:

All students in this course are required to have passed core programming.  No exceptions.

Additionally, the following courses are suggested prerequisites for taking this course.  Those with this or equivalent background will find this course easier going:

Mathematics for Computer Science: Discrete Mathematics (MPCS 50103 or equivalent)
Algorithms (MPCS 55001 or equivalent)
Networks (MPCS 54001 or equivalent)

Solid comfort with one (or more) of the following programming languages:  Java (Javascript), C/C++, Python, Ruby, C#, Go, Objective-C/Swift.   If you have familiarity with any Lisp dialect (i.e., CLOS, Scheme, etc.), we can talk.

For those university students not enrolled in the MPCS:

If you are interested in taking this class, please fill out the MPCS course request form for non-MPCS students:

https://masters.cs.uchicago.edu/content/course-request-form

Please note that, at this point, we do not expect any spots to be available for non-MPCS students. Even if any do open up, the decision to admit non-MPCS students into the class is made by the MPCS administration and requires taking a programming placement exam (https://masters.cs.uchicago.edu/page/placement-exams-0) to ensure students have a sufficient technical background.

For those students wishing to audit this course:

The MPCS has a strict no-auditors policy for current students. If you are interested in taking this class, you would need to register for the class and, to do so, you will need to fill out the MPCS course request form for non-MPCS students (see above).

III. COURSE DESCRIPTION

This course concentrates on three major themes: Blockchain concepts, associated technologies and software implementations.

This course is a comprehensive technical introduction to relevant topics in the wider ecosystem surrounding blockchain, using Bitcoin as a reference model. Our technological focus will include substantive topics in fundamental problems that blockchain is attempting to solve (and is generating), including algorithms, cryptography, security and trust, peer-to-peer networking, distributed ledgers, double spending, proof of work and ownership issues, decentralized applications, smart contracts, and supporting technologies.  With that said, this is not a course in economics or monetary theory, trading or arbitraging cryptocurrencies, whether it be bitcoin, ether, litecoin, or cryptokitties, etc., nor is it a course on regulatory or legal issues surrounding blockchain, although we will touch on many of these topics throughout the course.  We will also cover broader applications of blockchain technology beyond cryptocurrencies and ICOs including use cases from finance, insurance, science, healthcare, pharmaceuticals.
 
We will cover cryptocurrencies and will focus on bitcoin as our introduction to the problem space.  Students may leverage a number of technologies including containerization (Docker), as well as the MEAN stack or Ruby on Rails for the more ambitious.  Students may work in whatever languages they know best and make the most sense in context.  These may include Java/javascript, C++, python, ruby, C#, Golang, and others.  Students should note that bitcoin core APIs will vary in quality the further they get from C/C++/Java/Python/, etc.
 
Homework will be offered each week to reinforce a fundamental understanding of the core topics.  These assignments, aka "Labs," will reinforce central concepts and are designed to offer students hands-on experience in building their own blockchain.
 
A final student project will be delivered by teams of students targeting a specific blockchain use case of the team's choice (teams will be given options).


IV. LEARNING OBJECTIVES

Upon completion of this course the student will:

A. Fundamentally understand central Blockchain concepts and terminology.
B. Come to understand central cryptographic and algorithmic foundations of Bitcoin
C. Understand Bitcoin Transactions and Blocks
D. Understand Mining and Consensus Algorithms
E. Become conversant with the Bitcoin Core APIs

V. ACADEMIC INTEGRITY

Students are expected to have read and understood the University's policy on Academic Integrity. This policy is detailed in the Student Manual of University Policies and Regulations, available online at https://masters.cs.uchicago.edu/page/program-policies.
 

VI. METHOD OF INSTRUCTION

Methods include lecture and project-related assignments. Your team work should be stored using a version-control system that allows us to easily view files and folders that you create.
 

VII. OTHER COURSE INFORMATION

Attendance:

No formal attendance taken. Absences will affect your team and likely impact your peer evaluation.  There may be information presented in class that is not in the texts. You will find the lectures helpful in doing the laboratory exercises.

Make-up Work:

Students are expected to read the assigned texts before class in order to be able to full participate in the discussions and course activities.
 

VIII. METHOD OF EVALUATING STUDENT PROGRESS

Assigned work evaluated as follows:

7 Labs (5.0 points each)
35%
Project Faculty Evaluation
40%
Team Peer Evaluation (Instructions here)
25%
Total:
100%    

Grading scale:
 
95-100:     A
90-94:       A-
87.6-89:    B+
83-87.5:    B
80-82.9:    B-
76-79:       C+

A separate peer grading scale is implemented in addition to the above.  Every student is responsible for knowing and understanding this additional scale that will be used in the Team Peer Evaluation.  The separate peer grading scale is described here.

Lab Deliverables will be graded on a 5-point basis.  Deliverable due dates are noted on the lab pages.  All labs and homework are due by 5:00 pm on the due date. For instructions about how to submit your lab work using svn/Subversion, see this page

All assignments are due as specified on this syllabus and lab and other deliverables.  This includes the final project deliverables.  Each team will be evaluated on the basis of the presentation of iteration deliverables and the final deliverable.  Any and all lateness will suffer penalties.  The penalty for late labs will be .50 points off for each 24-hour period the lab is late, through ten days late (10*.50=5.0).  After ten days delay, the lab will no longer be accepted for grading and will receive a 0.

The course project will be presented by all teams on August 23, 2018 for all students.  The requirements for the course project are described here.

NB:  The end of the quarter is the time at which the final grade you have earned through your work in the quarter is recorded with the registrar.  There is no extra credit offered in this course, either at the beginning or at the end.  If you are dissatisfied with the grade you have earned at the end of the quarter, your only options will be to retake the course the next time it is offered, or accept the grade you earned.

NB: The instructor reserves the right to alter the course contents, dates, times or percentage of credit based on time allowed and class progress through the course material. The instructor also reserves the right to curve grades if he deems it in the best interest of the majority of students.

IX. COURSE SCHEDULE

The following abbreviations reference the following works (see esp. Required Reading under Schedule below):
 
Abbreviation Referenced Text
BCT Bitcoin and Cryptocurrency Technologies.  Narayanan et. al.
MB
Mastering Bitcoin, Antonopoulos

Articles* (Abbreviations Key for Required texts (see esp. Required Reading under Schedule below):

Abbreviation
Title & Author
Location
H&S
How to Time-Stamp a Digital Document, Haber & Stornetta
How to Time-Stamp a Digital Document
Menger
On the Origin of Money, Menger
On the Origin of Money
Nakamoto
Bitcoin: A Peer-to-Peer Electronic Cash System.  "Satoshi Nokamoto"
Bitcoin: A Peer-to-Peer Electronic Cash System
KOB
Neal Kin, Vladimir Oksman, Charles Bry Patent, August 15, 2008 Patent Pub. No.: US2010/042841A1
Merkle1
A Digital Signature Based On A Conventional Encryption Function, Merkle A Digital Signature Based On A Conventional Encryption Function
Luciano
"Cryptology: From Caesar Ciphers to Public-Key Cryptosystems," Luciano and Prichett, The College Mathematics Journal, Vol. 18, No. 1 (Jan., 1987), pp. 2-17
Cluster pub directory:  ~/mark/pub/56600/pfds/Luciano.Cryptology.pdf
Kumar
Microsoft Word - 91. A CRYPTOSYSTEM BASED ON VIGENERE CIPHER BY USING MULITLEVEL ENCRYPTION SCHEME A Cryptosystem Based On Vigenere Cipher By Using Mulitlevel Encryption Scheme
Sanjeev Kumar Mandal1, A.R Deepti
Cluster pub directory:  ~/mark/pub/56600/pfds/Vigenere1.pdf
Wiki1
Wikipedia article on letter frequency analysis
Wikipedia Link
Bonneau1
On Bitcoin as a public randomness source.  Bonneau et. al.   On Bitcoin as a public randomness source
Rogaway

Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance, Rogaway & Shrimpton, 2004

Cryptographic Hash-Function Basics

Kim
Updating and Distributing Encryption Keys, Neal Kin, Vladimir Oksman, Charles Bry.
Patent Pub. No.: US2010/042841A1
Eyal
Majority is not Enough: Bitcoin Mining is Vulnerable.  Eyal et. al. 
http://www.cs.cornell.edu/~ie53/publications/btcProcFC.pdf
Boehm
Bitcoin: A First Legal Analysis with reference to German and US-American law.  Boehm, et. al.   http://fc14.ifca.ai/bitcoin/papers/bitcoin14_submission_7.pdf
Raskin*
Raskin & Yermack, Digital Currencies, Decentralized Ledgers, and the Future of Central Banking
Cluster pub directory:  ~/mark/pub/56600/pfds/DIGITAL CURRENCIES, DECENTRALIZED LEDGERS, AND THE FUTURE OF CENTRAL BANKING.pdf
Hooper*
Bitcoin:  Digital Currency or Digital Tulip, Hooper
Cluster pub directory:  ~/mark/pub/56600/pfds/bitcoin-digital-currency-or-digital-tulip.pdf
Katsenelson* Bitcoin-Millennial's Fake Gold, Katsenelson
Cluster pub directory:  ~/mark/pub/56600/pfds/bitcoin-millennials-fake-gold.pdf
Kahn*
Cryptology Goes Public, Kahn
Cluster pub directory:  ~/mark/pub/56600/pfds/CryptologyGoesPublic.pdf
DiffieHellman*
New Directions in Cryptography, Diffie & Hellman
Cluster pub directory:  ~/mark/pub/56600/pfds/Diffie.Hellman.Original.Paper.pdf
Economist1*
The Economist:  The great chain of being sure about things
Cluster pub directory:  ~/mark/pub/56600/pfds/Economist_The great chain of being sure about things - Blockchains.pdf
Economist2*
The Economist:  The trust machine
Cluster pub directory:  ~/mark/pub/56600/pfds/Economist_The trust machine The promise of the blockchain.pdf
Back*
Hashcash - A Denial of Service Counter-Measure, Back
Cluster pub directory:  ~/mark/pub/56600/pfds/hashcash.pdf
Damgard*
A Design Principle for Hash Functions
Cluster pub directory:  ~/mark/pub/56600/pfds/Damgard.A.Design.Principle.for.Hash.Functions.pdf
Lamport*
The Byzantine Generals Problem, Lamport
Cluster pub directory:  ~/mark/pub/56600/pfds/lamport.byzantine.generals.problem.pdf
Merkle2*
One Way Hash Functions and DES, Merkle
Cluster pub directory:  ~/mark/pub/56600/pfds/Merkle.One.Way.Hash.Functions.and.DES.pdf
Szabo1*
Secure Property Titles with Owner Authority, Szabo
Cluster pub directory:  ~/mark/pub/56600/pfds/Nick.Szabo.Secure Property Titles with Owner Authority.pdf
Dobbertin* RIPEMD-160:  A Strengthened Version of RIPEMD, Dobbertin et. al.
Cluster pub directory:  ~/mark/pub/56600/pfds/RipeMD-160.pdf
Lebowitz*
Salt, Wampum, Benjamins - Is Bitcoin Next?, Lebowitz
Cluster pub directory:  ~/mark/pub/56600/pfds/salt-wampum-benjamins-is-bitcoin-next.pdf
Shamir*
How to Share a Secret, Shamir
Cluster pub directory:  ~/mark/pub/56600/pfds/shamir.how.to.share.a.secret.pdf
 Leibowitz
Coindesk:  Bitcoin Explained
https://www.coindesk.com/bitcoin-explained-global-currency-wall-street-veteran/
Bonneau2
SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies.  Bonneau et. al.
http://www.jbonneau.com/doc/BMCNKF15-IEEESP-bitcoin.pdf
Hussman*
Three Delusions:  Paper Wealth, a Booming Economy, and Bitcoin
three-delusions-paper-wealth-a-booming-economy-and-bitcoin.pdf
Bryan
Island Money
Cluster pub directory:  ~/mark/pub/56600/pfds/IslandMoney.pdf
BIP-37
BIP-37 Peer Services
https://github.com/bitcoin/bips/blob/master/bip-0037.mediawiki
Bloom
Burton H. Bloom,  "Space/Time Trade-offs in Hash Coding with Allowable Errors"
http://astrometry.net/svn/trunk/documents/papers/dstn-review/papers/bloom1970.pdf
Decker
Decker, Wattenhofer, Information Propagation in the Bitcoin Network
Cluster pub directory:  ~/mark/pub/56600/pfds/InformationPropagationInBitcoinNetwork.pdf
Demers
Demers et. al., Epidemic Algorithms for Replicated Database Maintenance
Cluster pub directory:  ~/mark/pub/56600/pfds/demers.epidemic.algorithms.pdf

*Articles starred may be found on the cluster under my pub directory (~mark/pub/56600/pdfs).  All numbers refer to chapters in texts, not pages, unless otherwise noted (as "pp. xxx").


 
Class/Date Lecture Topics
Required Reading
Guest Speakers
Homework Assignments & Other Due Dates
Class 1

June 21

What is Blockchain and why does it matter?
Course Introduction
Fundamental concepts:
Money, Currency, Ledgers
Foundational Background
Bitcoin Core



BCT:  Forward
MB: Introduction
H&S
Nakamoto
KOB
Menger
Bonneau2
Bryan

Lab 1 - Environment Setup & Tools Installation
Class 2

June 28

Introduction to Cryptography
- Classic ciphers
Symmetric Cryptography:
- Hash functions
- Hash pointers
Asymmetric Cryptography: 
- Keys & Digital signatures
BCT: Chapter 1
MB: Chapter 2
Luciano
Kumar
Wiki1
Rogaway
Damgard


Lab 2 - Brute Force Cryptanalysis and Letter Frequency Cryptanalysis

Class 3

July 5

Algorithms
- Binary Trees
- Merkle trees
- Elliptic curves
- SHA-256
- RIPEMD-160
- Base64 & Base58
Bitcoin Cryptocurrency:
- Introduction to Transactions & Blockchain
Merkle1
BCT: Chapter 2
MB: Chapters 3, 6, 9
Kim
Bonneau1
Lamport
Dobbertin



Lab 3 - Tamper-Proof Merkle Tree of Hash Pointers

Team Formation Deadline

Class 4

July 12

Bitcoin Cryptocurrency:
- Transactions & Blockchain
- Wallet Technology

BCT: Chapter 4
MB: Chapters 4, 5
Raskin
Hooper
Lebowitz


Lab 4 - Your Own Blockchain
Class 5
July 19
Mining & Consensus


BCT: Chapter 5
MB: Chapter 10
Eyal
Boehm
Back
Andrew Gordon, Gordon Law, 7:15 PM
Lab 5 - Mine Your Blockchain
Class 6

July 26

Bitcion
- Scripts
Docker Interlude

BCT: Chapter 6
Hussman
Kim Trautmann, Head, DRW Venture Captial, 5:30 PM
Lab 6 -  Docker and Compose

Team Final Project Proposal Due
Class 7

August 2

Networking background
Sockets & RPC
Docker Build & Compose
MB: Chapter 8
Jordan Kruger, Director of Research and Operations - Bloq Inc.
Lab 7 - Distribute Your Blockchain
Class 8

August 9
Distributed Systems & Peer-To-Peer Networking
Bitcoin Networking

MB: Chapter 7
BIP-37
Bloom
Decker
Demers

No Lab - Project Prep
Class 9

August 16
Wallets
Bloom Filters & Merkle Proofs
The Whole Enchilada
Apres moi, le deluge...
BCT: Chapters 8, 9, 10
MB: Chapter 12
Matt Roszak, Co-Founder and Chairman, Bloq Inc. No Lab - Project Prep
Class 10

August 23

Student Team Project Presentations




EVERYONE:  Sign up on Piazza here