Tim Roughgarden

First Principles Ep. 7 with Noam Nisan More than 30 years ago, Gödel Prize winner @noamnisan helped develop a proof technique he never expected anyone to use in the real world. Today, the sum-check protocol sits at the heart of some of the fastest modern SNARKs. Nisan traces its unlikely journey from early work on interactive proofs and IP = PSPACE to practical systems for verifiable computation. But Nisan’s career also tells a broader story about how research responds to technological change. When the web arrived in the 1990s, he deliberately left a field in which he was already a leading researcher to understand a new problem: How do you get independent actors on the internet to cooperate when they have different incentives? That question helped give rise to algorithmic game theory — and, decades later, brought Nisan back to questions around blockchain fees, token economics, and protocol design. Hosted by @Tim_Roughgarden with @SuccinctJT 0:00 Intro 1:28 Noam Nisan and the origins of verifiable computation 2:58 Why Noam Nisan left complexity theory 7:52 POPcorn, distributed computing, and early blockchain-like ideas 11:10 The birth of algorithmic game theory 16:14 Justin Thaler discovers the sum-check protocol 25:05 From arithmetization to LFKN 27:06 The story behind IP = PSPACE 30:40 Why sum-check matters for modern SNARKs 31:15 What is a SNARK? 38:52 The key idea behind sum-check: turning two into one 44:03 When SNARKs went from theory to practice 46:03 Why blockchains were the breakthrough use case 50:36 Noam Nisan’s move into blockchain economics 56:15 EIP-1559, transaction fees, and efficient blockspace 1:02:07 From theoretical computer science to real-world systems 1:08:49 Boiling down the sum-check protocol: Two become one 1:10:58 Is the sum-check protocol optimal?

First Principles Ep. 6 with Shafi Goldwasser What if you could prove something is true without revealing why it’s true? Turing Award winner Shafi Goldwasser tells the origin story of zero-knowledge proofs: how a playful question about playing poker securely over the telephone led her, Silvio Micali, and Charles Rackoff to rethink what a mathematical proof could be. Goldwasser traces those ideas through interactive proofs, the sum-check protocol, SNARKs, and the systems now used to verify computation and preserve privacy on blockchains. She also reflects on why breakthrough ideas are often rejected at first, how toy problems can produce foundational theories, and whether AI systems should have to prove their answers. Hosted by @Tim_Roughgarden with @SuccinctJT 00:00 Intro 03:36 How mental poker inspired zero-knowledge proofs: Proving that something is true without revealing the underlying information 06:30 The simulation paradigm and the meaning of “zero knowledge” 08:33 Why the original paper was repeatedly rejected 10:33 How interactive proofs became more powerful than conventional proofs 13:36 The road to modern SNARKs 19:02 Why the sum-check protocol is so useful for verifiable computation 25:31 Why many so-called “zk proofs” are not actually zero knowledge 34:06 Why toy examples, playfulness, and narratives can produce deep theory 37:23 The role of rigor and computational assumptions in cryptography 42:44 Applying zero-knowledge proofs to law, evidence, and secret software 45:23 Training AI systems to provide proofs alongside their answers 54:27 Why genuinely new ideas are often difficult for experts to recognize

Day 3 lectures: @sourav1547 on Distributed Key Generation: Definitions, Constructions, and Applications: youtube.com/watch?v=3Lq54_iS… @guruvamsip on Encrypted Mempools and Batched Threshold Encryption: youtube.com/watch?v=sFy3xzpb… @alberto_sonnino on DAG-Based Consensus: Introduction and Practical Aspects: youtube.com/watch?v=Hm1dt9YW…

Day 2 lectures: @AndrewLewisPye on 2-round finality youtube.com/watch?v=dlvJRXrQ… @SashaSpiegelman on Everlasting BFT: How Changing Requirements Keep Reinventing Consensus youtube.com/watch?v=y_yiNkfJ… @fradamt and @yannvon on Introduction to Ethereum Consensus -Part 1: youtube.com/watch?v=6_EsGMv1… -Part 2: youtube.com/watch?v=VA_ukotk…

Day 1 lectures from the summer school are now posted: @ittaia on Many Variants of Simplex youtube.com/watch?v=Z68hfZe_… @TheWattenhofer on Reinventing Solana: Alpenglow and Constellation youtube.com/watch?v=Jp1_UZ5p… Dongning Guo on Longest-Chain Consensus: Safety under Network Delays youtube.com/watch?v=Hz7lI0qx… @maria__apo on The Network Beneath the “Computer in the Sky” youtube.com/watch?v=lIEi6s0Q…

Back in May the @cu_eth_research Center hosted a Summer School on Blockchain Consensus. So many awesome lectures, videos of which I'll be posting throughout the week. From my opening remarks: "So I think this is a really exciting time for consensus and blockchain consensus specifically. Unusually, I think just in the last couple of years, there's been some really interesting theoretical developments, some new larger scale and better engineered implementation deployments within blockchain protocols we already have, and I think a really healthy interaction between those two. Theory that's been developed has in large part been motivated by what better consensus protocols in practice would be. A lot of people doing the tech transfer and actually building these things out knew the theory extremely well. So having spent a career in theoretical computer science, it's kind of a wonderful moment in time. Both theory and practice doing innovative work allows us to have such a healthy conversation between the two. Honestly, this workshop in large part is meant to just capture that moment in time, too. It's very unique. The list of speakers, I think it's amazing. People will know many of their names from their research papers, but also many of the speakers have been deep in the trenches, really making this stuff work at large scale, very high impact applications in practice. So we'll be hearing all their perspectives. In addition to some academics, we've got representatives from Ethereum Foundation, Anza, Aptos, Mysten Labs, a lot of the people who are building the biggest, most widely used Layer 1s."