This survey is essentially an outcome from studying the papers FRI, ProximityGaps, DEEP-FRI,Redshift and the ethSTARKdoc. It includes
- an overview to FRI and its soundness results, including example parameters for a plonky2-like setting;
- how FRI is turned into a commitment scheme (in the unique decoding regime), and why beyond a list-commitment model is not a good formalization if one targets tight soundness error bounds; (Although it still is a good intuitive approach.)
- the DEEP method, with an application to AIR-like arithmetization (for illustration purpose);
- and an appendix gathering basic facts on Reed-Solomon codes, Berlekamp-Welch and Guruswami-Sudan decoding.
This version of the document is more up-to-date than the one on IACR. Feedback and contributions are welcome!