SEASON 2 MODULE 8
FRI and Proximity Proofs (Part.2) w/ Dan Boneh
In this module (Part.2), Prof. Dan Boneh, applied cryptography and computer security professor at Stanford University, uses the machinery developed in Part.1 to present FRI and its analysis. He explains the protocol’s two-phase protocol (commit and query) and various spot-checking methods for verification. Prof. Boneh then goes on to cover several FRI variants including higher-order folding, batch FRI, and the STIR/WHIR protocols, before concluding with a discussion of potential alternatives to Reed-Solomon codes for future SNARK development.
What you’ll learn:
- 00:00 – Part.1 review: RS-IOPP & Folding
- 05:44 – How FRI works
- 05:59 – ↳ FRI phase 1: Commit phase
- 07:59 – ↳ FRI phase 2: Query phase
- 11:21 – ↳ How to spot check: Method 1
- 20:17 – ↳ How to spot check: Method 2 (the FRI method)
- 23:26 – ↳ Comparing spot check methods
- 30:20 – Four examples of FRI variants
- 30:42 – ↳ Higher-order folding
- 34:38 – ↳ Batch FRI for varying degrees
- 39:49 – ↳ Reduce proof size by grinding
- 43:24 – ↳ STIR and WHIR variants
- 52:51 – The future: Are there better codes than Reed-Solomon?
- 53:08 – ↳ The problem with RS-based SNARKs
- 54:49 – ↳ FRI-like proximity proof for other linear codes
- 56:12 – ↳ A proximity proof for other linear codes
- 58:12 – ↳ BaseFold
- 59:10 – ↳ More SNARK-useful linear codes
Find the presentation slides here.
Below is an accompanying reading list:
- Fast Reed-Solomon Interactive Oracle Proofs of Proximity, by Eli Ben-Sasson, Iddo Bentov, Yinon Horesh and Michael Riabzev, 2018.
- Worst-case to average case reductions for the distance to a code, by Eli Ben-Sasson, Swastik Kopparty and Shubhangi Saraf, 2018.
- DEEP-FRI: Sampling Outside the Box Improves Soundness, by Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, and Shubhangi Saraf, 2019.
- Proximity Gaps for Reed-Solomon Codes, by Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, and Shubhangi Saraf, 2020.
- Circle STARKs, by Ulrich Haböck, David Levit and Shahar Papini, 2024.
- STIR: Reed–Solomon Proximity Testing with Fewer Queries, by Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, and Eylon Yogev, 2024.
- WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification, by Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, and Eylon Yogev, 2024.
- Brakedown: Linear-time and field-agnostic SNARKs for R1CS, by Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler and Riad S. Wahby, 2021.
- Orion: Zero Knowledge Proof with Linear Prover Time, by Tiancheng Xie, Yupeng Zhang, and Dawn Song, 2022.
- BaseFold: Efficient Field-Agnostic Polynomial Commitment Schemes from Foldable Codes, by Hadas Zeilberger, Binyi Chen and Ben Fisch, 2023.
ZK Whiteboard Sessions is an educational series on all things zero knowledge. Presented by ZK Hack.
Get notified on the latest module’s release by signing up below: