SEASON 2 MODULE 7
FRI and Proximity Proofs (Part.1) w/ Dan Boneh
In this module (Part.1), Prof. Dan Boneh, applied cryptography and computer security professor at Stanford University, provides a comprehensive overview of FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity) and its foundations in cryptography. Prof. Boneh begins with essential background on linear codes and Interactive Oracle Proofs (IOPs), then demonstrates how to compile a Polynomial-IOP into a SNARK using Reed-Solomon IOP of Proximity, before diving into distance preserving transformations with detailed examples of batch RS-IOPP and folding.
What you’ll learn:
- 0:00:00 – Introduction and What is FRI?
- 0:01:45 – Background on Linear Codes
- 0:13:40 – ↳ The classic MDS Code: Reed-Solomon
- 0:21:10 – Background on IOPs
- 0:25:12 – ↳ IOP to SNARK: the BCS compiler
- 0:28:42 – ↳ IOP of Proximity
- 0:33:53 – Compiling a Poly-IOP to a SNARK using a Reed-Solomon IOP of Proximity
- 0:40:42 – ↳ Quotienting
- 0:46:05 – ↳ Poly-IOP to IOP
- 0:56:50 – Distance Preserving Transformations
- 0:58:20 – ↳ Example 1: Batch RS-IOPP
- 1:00:20 – ↳ The BCIKS Proximity Gap Theorem
- 1:04:30 – ↳ Example 2: Folding
- 1:16:00 – Summary of Part 1
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: