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