- Location and Hours:
- TBD, Wednesday 15:00 - 18:00
- Instructor:
- Nir Bitansky
- Reception Hour:
- Thursday 15:00 - 16:00. Please inform by moc.liamg|yksnatibn#liame if you plan to come.
- Teaching assistant:
- Eliad Tsfadia
- Reception Hour:
- Sunday 17:00-18:00. Please inform by moc.liamg|aidafstdaile#liame if you plan to come.
Overview
Since the emergence of Bitcoin, blockchains have taken the world by storm, giving rise to multi billion dollar industries and leading to talks of a new internet. So what are they exactly? Typically, the term blockchains refers to distributed public ledgers, where digital transactions are shared and managed by the users. A remarkable feature of modern blockchains, and the reason for much of the excitement, is that they are completely decentralized; namely, they do not depend on any form of central authority, nor require users to trust any such authority. Rather, the soundness of blockchains is guaranteed using cryptography. Originally driven by the concept of decentralized currency, it is now clear that the potential of blockchains goes way beyond.
The course will cover the basics of blockchains, with focus on the theoretical concepts (mostly from cryptography but also other areas of TCS) on which blockchains are founded today, as well as concepts that could play an important role in the future development of blockchains. Along the way we will get familiar with Bitcoin and other existing blockchains, and aim to identify some of the future challenges in the area.
Disclaimer: the topic of blockchains is extremely broad. It raises intriguing questions that span different areas of CS such as distributed computing, systems security, programming languages, and algorithmic game theory, as well as area beyond CS, such as economics, law, and sociology. We will not be able to touch all of these, but may occasionally touch on some of them as time permits.
Tentative Syllabus
- Introduction
- The problem of digital currency (in broad strokes)
- Cryptographic concepts: digital signatures, collision-resistant hashing
- Consensus
- lower bounds, protocols for a fixed set of parties
- The Sybil attack
- TCS concepts: Byzantine agreement
- Reinventing consensus
- Consensus in Bitcoin (protocol and analysis)
- Cryptographic concepts: proofs of work (PoW), random oracles and cryptographic hash functions
- Reinventing consensus again
- Proofs of space
- Proofs of stake
- Bitcoin: under the hood
- P2P Network, Transactions, Mining, Attacks
- Anonymity in blockchains
- Cryptographic concepts: zero-knowledge proofs, commitments, blind signatures
- Scalability
- Cryptographic/TCS concepts: succinct proofs, probabilistically-checkable proofs, proof composition.
- Smart contracts
- Additional blockchain applilcations
- Timestamping, common randomness, fair secure computation
Prerequisites
The course is generally meant for undergrad students in their third year of studies (or M.Sc. students). Students should be comfortable with the basic concept of efficient computation and asymptotics (polynomial-time algorithms, big O notation, etc.), basic probability theory, and basic linear algebra. Prior knowledge in cryptography (such as introduction to cryptography 0368.3049) is helpful but not mandatory. Perhaps the most important prerequisite is mathematical maturity: the ability to read, understand, and write mathematical proofs.
Requirements
- Homework assignments (20-30%): 5-6 problem sets.
- A final exam (70-80%).
Slides and Lecture Notes
Most lectures will include an introductory slide-based part and a more technical whiteboard-based part. The slides and lecture notes will be posted regularly on this webpage.
Text Books
- A. Narayanan, J. Bonneau, E. Felten, A. Miller, S. Goldfeder, Bitcoin and Cryptocurrency Technologies, 2016, Draft available online.
- J. Katz and Y. Lindell, Introduction to Modern Cryptography, Chapman & Hall/CRC Press, 2007.
- D. Boneh and V. Shoup, A Graduate Course in Applied Cryptography. Draft available online.
Online Resources
- Here you can find links to several courses on Bitcoin and lecture videos (all following the NBFMG book).
- Blockchains and Cryptocurrencies, Abhishek Jain
- Cryptography, Boaz Barak
- Introduction to modern cryptography, Benny Chor
