Teaching
CSCI-GA.3033-107: Cryptography of Blockchains
Readings:
A Graduate Course in Applied Cryptography, Boneh Shoup (BS) https://toc.cryptobook.us/
Bitcoin and Cryptocurrency Technologies, Narayanan, Bonneau, Felten, Miller, Goldfeder (NBFMG)
https://d28rh4a8wq0iu5.cloudfront.net/bitcointech/readings/princeton_bitcoin_book.pdf
Homework
Syllabus
- Lecture 1 (1/22): Intro to Blockchains
- Slides
- What are blockchains
- Signatures and Hash Functions
- Building a simple blockchain from simple primitives
- SHA256
- Schnorr signatures
- BLS signatures
- Class overview
- Reading: BS Chapter 8,13; NBFMG Chapter 1
- Lecture 2 (1/29) Merkle Trees, Vector Commitments, Accumulators and Proof of Storage
- Slides
- BLS signatures (reading last lecture)
- UTXO vs Account model (transaction format)
- State Commitments
- Merkle Tree Inclusion Proofs
- Merkle Tree Updates
- Patricia Trees and exclusion proofs
- UTXO commitment
- Reading: BS 8.9 NBFMG Chapter 3
- Lecture 3: 2/5 Consensus, Aggregate signatures
- Slides
- RSA accumulators
- Proof of Work
- Proof of Stake
- Randomness
- Quorum Certificates
- Aggregate BLS for reducing communication
- Rouge Key Attacks
- Reading BS 15.5, BFS20 (Chapter 4 mainly), Compact certificates
- Lecture 4 (23/4): Aggregate signatures part 2, VDFs and Beacons
- Slides
- BLS rouge key defenses
- Hash-based certificate of quorum
- Committee sampling
- Randomness beacons
- Strawman construction
- VDFs abstractly
- Group based VDFs
- Reading Verifiable Delay Functions Sections 1-3, Survey of 2 VDFs
- 2/19 President’s day
- Lecture 5: 2/26 Optimistic Rollups and VID
- Lecture 6: 3/4 KZG, and Light Clients
- Lecture 7: 3/11 Threshold Cryptography and key security
- Slides
- Flyclient
- Key security
- HD Wallets
- Shamir Secret Sharing
- Threshold signatures
- Spring break
- Lecture 8: 3/25 Private Blockchains and Zero-Knowledge
- Slides
- Privacy on Blockchains
- Mixers
- Defining Zero-Knowledge
- Defining SNARKs
- Tornado Cash
- Lecture 9: 4/1 Zero-Knoledge Proofs part 1 (Sigma Protocols)
- Slides
- ZK-applications
- ZK-definitions
- Special Soundness
- Simulation
- Sigma protocols for circuits
- Reading: BS Chapter 19 and 20
- Lecture 10: 4/10 SNARKs part 2
- Slides
- ZK-Rollups
- Poly IOPs
- Plonk
- Lecture 11: 4/15 Post-quantum cryptography for blockchains (Guest lecture Nick Spooner)
- Lecture 12: 4/22 Recursive proofs and succinct blockchains
- Slides
- FRI
- Recursive proofs
- Succinct blockchains
- Lecture 13: 4/29 Recursive proofs part 2
- Slides
- zkEVM
- Circuit friendly hash functions
- Lookup arguments
- Memory checking
- Folding
- Reading: Vitalik Blog, Poseidon Hash, Lookup, Memory Checking, Folding 1, Folding 2
- Lecture 14: 5/6 Optional topic: Folding, MPC and future crypto