Tuesdays and Thursdays, 12:30pm-1:50pm, 2017, Electrical & Computer Eng Bldg
Prof. Pramod Viswanath, pramodv@, 118 Coordinated Science Laboratory (CSL), 244-8999
Ranvir Rana, rbrana2@ and Gerui Wang, geruiw2@
The basic technical prerequisites are a background in probability and algorithms. Decent amount of software programming background is essential. At Illinois, the prerequisites are met by: Probability (ECE 313), a strong programming course (eg: ECE 390), algorithms (CS 473) and networking (ECE/CS 438)
Blockchains are decentralized digital trust engines and are a potential replacement to "digital platforms" that we encounter in today's world. Digital platform companies occupy 7 of the largest companies in the world based on market capitalization (eg: Apple, Google, Microsoft, Amazon, Alibaba, Tencent). Blockchains came into prominence through Bitcoin, a cryptocurrency, introduced in 2009. In the decade since its inception, blockchain designs have evolved significantly, although the corresponding evolution of applications (beyond cryptocurrencies) have not caught up yet. In this course, we study a full-stack design of blockchains: we view the blockchains as a whole integrated system involving networking, incentives, consensus, application layer support. The course is structured into two parts: in the first part (5 weeks) we study the Bitcoin design in detail. Although very secure and remarkably incentive compatible in the real world, Bitcoin has very poor performance in many ways: throughput, latency, energy, compute, storage and communication. In the second part (8 weeks) we study the various efforts to scale the performance of Bitcoin in all the different dimensions, while maintaining the incentive compatibility and security of Bitcoin. In the spirit of Nakamoto (who implemented and tested the Bitcoin client before writing the white paper), this course will be implementation-heavy. We will use the Rust programming language for our assignments and projects. By the middle of the course, you will implement a bitcoin client in Rust and test it out internally. In the final project you will implement features for scaling the Bitcoin client developed earlier. The homework assignments will help you in these implementation efforts by leading you along. Example: the first assignment is on getting you used to Rust and the second assignment lets you build and use basic crypto primitives (hash functions, Merkle trees, signatures) in Rust. In the project at the second part of the course you will select one of the scaling solutions we will discuss and implement on top of your Bitcoin client and verify the resulting improvement.
Prof. Viswanath - Fridays 1-2pm, 118 CSL
Ranvir Rana - Wednesdays 4-5pm
Gerui Wang - Mondays 3-4pm
Assignments - 30%
Midterm Project - 30%
Final Project - 40%
Lecture 1 : Introduction In this introductory lecture, we talk about Blockchains are, how they are a potentially disruptive force in the digital platform economy of today. We also cover some history of Bitcoin (the first blockchain) and set up the outline for a detailed study of Bitcoin in the next 9 lectures. [ Slides ]. Supplementary reading: Module 1 on "History: money, the cypherpunks, and Satoshi Nakamoto" by Haseeb Qureshi.
Lecture 2 : Cryptography on a need to know basis (part 1) In this lecture and next, we study basic cryptographic primitives that underpin Bitcoin and all other blockchain designs. There are a few cryptographic techniques that we will look into later in the course, again on-a-need-to-know basis. Cryptography is not a prerequisite to this course, and we will use battle tested crypto libraries in all our implementations. This lecture covers cryptographic hash functions and its use in basic data structures: hash pointers and linked list (creating a block chain) and a hash accumulator known as a Merkle tree (for low complexity membership proofs). [ Slides ]. Reading: Chapters 1.1 and 1.2 of PUP book.
Lecture 3: Cryptography on a need to know basis (part 2) In this lecture we study the basic cryptographic primitives of digital signatures and public key cryptography. Public keys serve as identities of users in a blockchain and we see two designs efforts of a cryptocurrency with basic features (ownership of a coin, transferring the ownership, verifying ownership efficiently). The resulting design involves a blockchain data structure to maintain the ledger of transactions, but involves a central authority to sign and order the blocks within a chain. This sets the stage for decentralizing the role of signing and ordering the blocks within a chain, which will be the focus of the next lecture where we study the Nakamoto longest chain rule. [ Slides ]. Reading: Chapters 1.3, 1.4 and 1.5 of PUP book.
Lecture 4: Longest Chain Protocol: Bitcoin's Consensus Algorithm In this lecture we study the longest chain protocol of Nakamoto, and use it to construct the basic consensus mechanism of Bitcoin. We combine this selection rule with the basic cryptographic primitives from the last two lectures to complete Bitcoin's cryptocurrency design. We abstract the mining operation in this lecture by an oracle that can provide a unique random proposer of the block roughly once in ten minutes. In a later lecture we will introduce the mining process underlying Proof of Work (PoW) which will enable the duties of this random oracle proposer. In an even later lecture we will see formally why the longest chain rule allows consensus among honest parties as long as they control a majority of the mining power. [ Slides ]. Reading: Chapter 2 of PUP book.
Lecture 5: Bitcoin Network: P2P, Gossip In this lecture, we study various network architectures and overlay networks and reason out the design choices for the Bitcoin p2p network. We study the basics of expander graphs to understand why communication in the bitcoin network will take O(log N) steps. We later study the implementation of the network in the bitcoin core, including network bootstrap, block and transaction broadcast. We discuss the cons of the p2p network and give a brief overview of FRN and Falcon. We end this lecture by discussing the information eclipse attack on the p2p network [ Slides ]. Supplementary reading: P2P Network guide.
Lecture 6: Proof of Work and Mining In this lecture, we look at the role of Proof of Work (PoW) plays in the Bitcoin protocol. It provides resistance to denial of service attacks, spam generation/propagation, acts as a leader election mechanism, and also provides enables incentive mechanism designs. Further more, the computational hardness of the proof of work can be varied over time, all in a distributed manner. PoW is a central part of the Bitcoin system and this lecture ties together all these various threads. [ Slides ].
Lecture 7: Bitcoin System: Putting it all together In this lecture, we put together the full Bitcoin system by tying together all the different threads. We do this in the context of the Bitcoin client the students are building as part of their midterm project. The midterm project is completed over the course of 6 weeks, with key components (block data structures, mining, networking, transaction handling and state updates and validation) completed over the six week period. We also cover a few features of the Bitcoin system that the students will not build in their client: simple payment verification (light) clients, scripting language support and bootstrapping facility. [ Slides ].
Lecture 8: Bitcoin Security Thus far we have discussed the Bitcoin protocol (the longest-chain mining rule and k-deep confirmation rule) and the overall cryptocurrency system around the protocol. However adversarial miners could deviate from the protocol, "looking for trouble". The security of the protocol is characterized via two properties: liveness (i.e., adversarial action does not lead the protocol to stall or deadlock) and safety (i.e., adversarial action does not lead honest miners (i.e., those that follow protocol) to reverse prior confirmation of a block). In this lecture, we study these key security properties in the context of a formal cryptographic model. We prove mathematically that liveness and safety are strongly satisfied as long as the adversarial mining power is strictly less than 50% and the block broadcast occurs within a constant propagation delay. [ Notes (to be provided) ].
Lecture 9: Bitcoin Incentives Bitcoin incentivizes participants via transaction and block rewards. In this lecture we study the block reward incentive mechanism in a game theoretic context. We see that rational miners will deviate from the longest-chain protocol to reap block rewards beyond what is expected if they followed protocol (which is proportional to their mining hash power). We see a specific "selfish mining" policy and the optimal deviation policy via a Markov decision process stochastic analysis. Reading: "Majority is not Enough: Bitcoin Mining is Vulnerable" by Eyal and Gun Sirer. "Optimal Selfish Mining Strategies in Bitcoin" by Sompolinsky and Zohar.
Lecture 10: Scaling Bitcoin: Payment channels In this lecture, we give a brief introduction of various ways to scale Bitcoin's throughput and latency, categorizing them as layer 1 and layer 2 solutions. We discuss payment channels, the building block of the Bitcoin lightning network. Several cryptographic primitives like MultiSig, Timelock, and Hashlock used for locking and unlocking transactions that enable these channels. We explain the construction uni-directional and bi-directional payment channels using these primitives. The channel can be extended over multiple-hops using HTLC. [ Slides ].
Lecture 11: Increasing Mining rate in Bitcoin One way to improve the performance of Bitcoin is by simply increasing the mining rate (set by the hardness of the PoW puzzle). Increasing the mining rate improves both throughput and latency, but we will see that this comes at the cost of decreased security (i.e., the fraction of adversarial hash power that can be tolerated while still ensuring safety is strictly reduced from 50%). The main challenge is forking that is caused by increasing the mining rate; because of forking the longest chain grows more slowly thus allowing attacks (eg: private attack) to occur with lesser hash power. In the context of a concrete synchronous network model of block broadcasts, we study the precise dependence of the fraction of adversarial hash power that can be securely tolerated on the mining rate; the worst case synchronous network broadcast delay also plays a crucial role. Just as with no network delay (analysis in Lecture 8), we see that there is a sharp threshold of adversarial hash power: below this threshold, security is assured (confirmation probability goes to 1, as the confirmation depth is chosen large); above the threshold, the confirmation probability goes to 0, as the confirmation depth is chosen large). [ Notes (to be provided) ].
Lecture 12: Tradeoff between Throughput, Latency and Security Threshold for Bitcoin Another way to potentially improve the throughput of Bitcoin is to simply increase the block size. Incorporating the block size parameter into the synchronous network model allows us to calculate the fundamental tradeoff between throughput, latency and security threshold for Bitcoin. This calculation also indicates the appropriate choices of the parameters of mining rate and block size, as a function of the desired security threshold (adversarial hash power than can be securely tolerated). [ Notes (to be provided) ].
Lecture 13: Changing the longest chain rule: GHOST An alternative way to improve the throughput of Bitcoin is to change the fork choice rule (i.e., different from the longest chain rule). The goal is to consider a fork choice rule that is unaffected by the high forking created by increasing the mining rate In this lecture we see the GHOST (greedy heaviest observable sub tree) fork choice rule that can tolerate high forking, but only with respect to the private attack. We show an alternative adversarial strategy, known as the balance attack , that strictly limits the adversarial hash power that can be securely tolerated. This in turn reduces the throughput of GHOST, to be almost nearly the same as that of Bitcoin. [ Notes (to be provided) ]. Reading: "Secure High-Rate Transaction Processing in Bitcoin" by Sompolinsky and Zohar.
Lecture 14: Decoupling transactions from the fork choice rule: Prism 1.0 In this lecture, we see a different approach to scaling throughput of Bitcoin: we retain the longest chain fork-choice rule for the (proposer) blocks but allow transactions to be separately blocked and broadcasted. The proposer blocks have hash pointers to new transaction blocks ; thus the longest chain of the proposer block tree allows one to securely form a ledger of ordered list of transactions . The proposer blocks are mined at the slow Bitcoin rate but transaction blocks are allowed to mine as fast as the network can support. The adversary is limited from attacking only transaction blocks or proposer blocks via cryptographic sortition. [ Notes (to be provided) ]. Reading: "Deconstructing the blockchain to approach physical limits" by Bagaria, Kannan, Tse, Fanti and Viswanath. "Fruitchains: a fair blockchain" by Pass and Shi.
Lecture 15: Decreasing latency of confirmation Decoupling transactions from proposal blocks (as in the last lecture) increases throughput but leaves the latency of confirmation unchanged: the proposal block mining rate is unchanged (slow) and we need to wait for the proposal block to be buried k-deep in the longest chain for it to be confirmed. In this lecture, we continue the decoupling principle to allow the implicit voting of being buried k-deep to be done in parallel , thus speeding up the time to confirmation. This lecture covers in detail a protocol called Prism that enables fast confirmation and high throughput. The adversary is limited from attacking only transaction blocks or proposer blocks or voting blocks via cryptographic sortition. [ Notes (to be provided) ]. Reading: "Deconstructing the blockchain to approach physical limits" by Bagaria, Kannan, Tse, Fanti and Viswanath.
Lecture 16: Prism, Confirmation rule and Security In this lecture, we see in detail the confirmation rule of Prism. We see that fast confirmation is enabled for "honest" transactions (i.e., transactions that are not conflicted or double-spent) while still guaranteeing ordering of all transactions (including double spends). The protocol provides an ordering service of transactions; the validation or semantic consistency of the transactions is decoupled from the consensus algorithm -- a ledger sanitization procedure operating on the confirmed list of ordered transactions completes this step. [ Notes (to be provided) ]. Reading: "Deconstructing the blockchain to approach physical limits" by Bagaria, Kannan, Tse, Fanti and Viswanath.
Lecture 17: Proof of Stake (PoS): Longest Chain In this lecture, we look to replace the PoW module in Bitcoin with an energy efficient alternative. We focus on proof of stake (PoS) and look to a simple implementation directly in the context of the longest chain protocol. PoS is energy efficient for honest participants, but also for adversaries -- this allows a significantly enhanced class of actions for the adversary. We look at the private "Nothing at Stake" (NaS) attack in detail and use that to calculate an upper bound on the fraction of stake the adversary could control without compromising security. A careful security analysis for PoS protocols, including the longest chain one, involves sophisticated mathematics; that the the upper bound calculated via analyzing the NaS attack turns also to be sufficient -- so no attack would succeed to break security -- is the result of a recent paper. [ Slides ]. [ Video of Lecture ]. Reading: "A Scalable Proof-of-Stake Blockchain in the Open Setting" by Fan and Zhou. "Proof-of-Stake Longest Chain Protocols: Security vs Predictability" by Bagaria, Dembo, Kannan, Oh, Tse, Viswanath, Wang, and Zeitouni.
Lecture 18: Improvements to Proof of Stake Longest Chain (PoS-LC) In this lecture, we work to improve two aspects of the PoS-LC protocol from last lecture. (a) We consider how to allow stake to change throughout the protocol, thus allowing dynamic stake to reflect in the proposer election mechanism, as the stake changes due to transactions or incentives (block/transaction rewards). Key grinding attacks are devastating to straightforward adaption of PoS-LC to dynamic stake (even if the stake is stale). We study a fix to the fork choice rule (a truncated variant of longest chain rule) that is secure under dynamic stake condition. (b) We study variants to how the PoS lottery (proposal election mechanism) refreshes the randomness from the blockchain over time. In PoS-LC this randomness was from the parent block (tip of longest chain) and this allowed adversaries to at most hold 1/(1+e) fraction of stake. If the randomness is not varying at all (i.e., borrowed from the genesis block) then the security threshold improves all the way to 50%. But this comes at a total (non causal) prediction of the winners of the PoS proposal election mechanism. More generally, letting the randomness to come from an ancestor block (deeper in the main chain than the immediate parent block), allows us to tradeoff predictability with security threshold. [ Slides ]. [ Video of Lecture ]. Reading: "Proof-of-Stake Longest Chain Protocols: Security vs Predictability" by Bagaria, Dembo, Kannan, Oh, Tse, Viswanath, Wang, and Zeitouni and "Ouroboros Genesis: Composable Proof-of-Stake Blockchains with Dynamic Availability" by Badertscher, Gazi, Kiayis, Russel and Zikas.
Lecture 19: Sharding (Part 1) Thus far, we have improved the longest chain protocol to Prism, which achieves throughput and latency at the physical limits of the underlying network. We have also replaced PoW by the energy efficient PoS, where the mining procedure is eliminated. In this lecture, we work to improve a complementary aspect in Bitcoin: increasing throughput as the number of participants increases. This is the focus of sharding, which roughly corresponds to each of the nodes only storing, computing (validating) and communicating subsets of all the blocks in the blockchain. In the first of a 3 part series, we study a natural sharding scheme where the blockchain is divided into multiple shards, with each shard maintained only by a subset of the nodes (participating nodes are allocated randomly to each shard; the randomness is cryptographically secure and verifiable and also refreshed at periodic intervals). This sharding scheme (popularized as Omniledger) scales throughput linearly in the number of participating nodes, but requires relatively large sizes and even then is not secure against a fully adaptive adversary (where nodes turn adversarial after they have been assigned to a shard). [ Slides ]. [ Video of Lecture ]. Reading: "OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding" by Kokoris-Kogias, Jovanovic, Gasser, Gailly, Syta and Ford.
Lecture 20: Sharding (Part 2) In this lecture, we work to improve the limitations of the Omniledger sharding scheme. We study Zilliqa (where only compute scaling is possible and no storage scaling (all nodes maintain the full blockchain ledger), Polyshard (where only storage scaling is possible via maintaining coded pieces of the blockchain) and finally Trifecta sharding (where both storage and compute sharding is achieved by decoupling validation from consensus and conducting consensus only in a single main chain). [ Slides ]. [ Video of Lecture ]. Reading: "PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously" by Li, Yu, Yang, Avestimehr, Kannan and Viswanath. "Zilliqa Whitepaper" by Zilliqa team.
Lecture 21: Sharding (Part 3) In this lecture, we model a basic building block towards communication scaling of sharding algorithms: the data-availability problem. We see how coding the data in the blockchain can aid the efficacy of the solutions to this problem and study in detail a near optimal procedure called the Coded Merkle Tree . [ Slides ]. [ Video of Lecture ]. Reading: "Coded Merkle Tree: Solving Data Availability Attacks in Blockchains" by Yu, Shahraei, Li, Avestimehr, Kannan and Viswanath. "Fraud Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Ma jorities" by Al-Bassam, Sonnino and Buterin.
Lecture 22: Privacy (Part 1) In this lecture, we study how to link public key of the source of a transaction to its' network IP address, a strong form of deanonymization. We discuss updates to the networking protocol, focusing on a protocol called Dandelion, that provides network-wide statistical anonymity guarantees. [ Slides ]. [ Video of Lecture ]. Reading: "Dandelion: Redesigning the Bitcoin Network for Anonymity" by Venkatakrishnan, Fanti and Viswanath. "Dandelion++: Lightweight Cryptocurrency Networking with Formal Anonymity Guarantees" by Fanti et.al. "Bitcoin Improvement Proposal: Dandelion: Privacy Enhancing Routing" and "Dandelion++ for Monero".
Lecture 23: Permissioned Blockchains (Part 1) In this lecture, we study the hyperledger fabric, a permission blockchain developed as open source by an industry consortium led by IBM and Linux Foundation. [ Slides ]. [ Video of Lecture ].
Lecture 24: Permissioned Blockchains (Part 2) In this lecture, we study the consensus algorithm behind Libra, a permission blockchain developed as open source by an industry consortium led by Facebook. The consensus algorithm is called HotStuff and we have a guest lecturer speaking about it: Prof. Ling Ren. [ Slides ]. [ Video of Lecture ].
Lecture 25: Inside Smart Contract Virtual Machine Smart contract applications in blockchains such as Ethereum are written in high level programming languages. The job of virtual machines is to provide an environment for the execution of these applications and update the state storage with respect to the execution outputs. In this lecture, we study the underlying structure and mechanism of smart contract virtual machines. [ Slides ]. [ Video of Lecture ].
Lecture 26: Blockchain Privacy (part 2) In this lecture we study data privacy by encrypting the transactions on the blockchain in a manner that still allows validation to be conducted. We look at the cryptographic primitives of ring signatures and zksnarks and how to use these cryptographic libraries to implement a private version of the Bitcoin client. Guest lecture by Prof. Andrew Miller. [ Slides ]. [ Video of Lecture ].
Assignment 1 - In this introductory assignment, you will get to learn the basics of Rust programming language and useful libraries. The assignment will be accessed and completed on Gitlab, available here: [ Assignment 1 ]. Due date: 12:30PM, Jan 28, 2020.
Assignment 2 - In this assignment, you will get to learn to basic cryptographic primitives (hash functions and signatures) and build fundamental data structures that form the core of blockchains: block chains and Merkle trees. The assignment will be accessed and completed on Gitlab, available here: [ Assignment 2 ]. Due date: 12:30PM, Feb 6, 2020.
Assignment 3 - In this assignment, you get to implement some basic adversarial strategies to the longest chain protocol and contrast their efficacies. The assignment is available here: [Assignment 3 ] and should be uploaded on Compass. Due date: 12:30PM, April 16, 2020.
Assignment 4 - In this assignment, we continue to explore adversarial strategies to the longest chain protocol and contrast their efficacies. The focus here is on how best the adversary can turn the network delay to its advantage. The assignment is available here: [Assignment 4 ] and should be uploaded on Compass. Due date: 12:30PM, April 23, 2020.
We are going to build a simplified bitcoin client with full node functionality. Students will create a private test net amongst their team members(groups of 2) and have fun changing various parameters of layer 1. The project will be a continuation of the code used in Assignment 2. The project will be split into 6 weeks with checkpoints every week as listed below.
Week 1: Block and Blockchain structure - Create block and blockchain struct and add some functions related to it. More detailed instructions can be found at [ Midterm Project Week 1 ]. Due date: 12:30PM, Feb 13, 2020.
Week 2: Mining - Implement a mining module of the bitcoin client. The mining module(miner) will produce blocks by solving the proof-of-work puzzle. More detailed instructions can be found at [ Midterm Project Week 2 ]. Due date: 12:30PM, Feb 20, 2020.
Week 3: Network - Implement the network module of Bitcoin client. The network module is in charge of communicating with other nodes/clients. It forms the peer-to-peer (p2p) network and uses gossip protocol to exchange data, including blocks and transactions. More detailed instructions can be found at [ Midterm Project Week 3 ]. Due date: 12:30PM, Feb 27, 2020.
Week 4: Putting together a data blockchain - Combine last 3 week's work to make a functioning data blockchain. Most of this week's work will be combining mining, network, and blockchain modules. You will need to add PoW validation and a block buffer to handle orphan blocks. More detailed instructions can be found at [ Midterm Project Week 4 ]. Due date: 12:30PM, March 5, 2020.
Week 5: Transactions - Include transactions in the codebase. Integrate the transaction structure inside the block content, add network functionality to transaction propagation and adding a transaction mempool to be used by the miner to include transaction content in the block being mined. More detailed instructions can be found at [ Midterm Project Week 5 ]. Due date: 12:30PM, March 12, 2020.( Suggested due date, no submission required.)
Week 6: State transition and validation - This is the last part of midterm project, and you are going to finish the Bitcoin client. You need to maintain a state for the ledger that the blockchain creates and add all the necessary checks related to it. More detailed instructions can be found at [ Midterm Project Week 6 ]. Due date: 12:30PM, March 26, 2020. (Please submit a report on Compass2g and register for a demo slot)