The archived course website of the Spring 2020 offering of EE374 can be found here.
Consensus protocols are at the core of distributed systems. Traditional consensus protocols are designed for the closed setting where consensus is maintained by a fixed and typically small set of permissioned nodes in a single organization. Blockchains were invented by Nakamoto in 2008 to achieve consensus in the open permissionless setting at Internet-scale, where nodes can freely join and leave the network. Existing blockchains like Bitcoin and Ethereum have an excellent track record in operating securely in such a challenging environment, but suffer from several significant drawbacks: 1) high confirmation latency; 2) low transaction throughput; 3) lack of finality guarantees; 4) lack of accountability for misbehaving participants; 5) high energy consumption due to Proof-of-Work. This course discusses recent solutions to overcome each of these drawbacks while maintaining the security properties of Nakamoto’s consensus protocol. Techniques from traditional Byzantine fault tolerance theory, probabilistic analysis, cutting-edge cryptography and error-correction coding are used. A recurring theme is that Nakamoto’s longest chain protocol and traditional BFT protocols have complementary strengths, and best-of-both-worlds protocols can be built by composing them.
CS251 (Cryptocurrencies and Blockchain Technologies) provides a broad coverage of blockchain technologies and applications, while this course focuses on the consensus layer and studies recent advances building on Nakamoto’s longest chain protocol and classical BFT protocols. This course can be taken as a sequel to CS 251 but can also be taken on a stand-alone basis. The only prerequisite is a solid undergraduate course in probability such as CS 109 or EE 178.
For a comprehensive introduction to blockchains, you can consult the textbook Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction by Narayanan, Bonneau, Felten, Miller and Goldfeder (preprint edition available for free online).