Thread by @RiscZero

This week’s RISC Zero Study Club is focused on FRI!

For real-time FRI learning, join us Wednesday 10am PST/5PM UTC at zoom.us/j/99200763534

If you'll be at #ZKSummit, you can also catch @Paul_Gafni's workshop on this topic.

For async learning, read on!
[1/]

The FRI protocol, first published in 2018, is the backbone 🦴of all implementations of STARKs – and some newer SNARKs.
risczero.com/docs/reference…
[2/]

First, some background:
The crux of RISC Zero’s technology is an argument of computational integrity that lives on a RISC Zero receipt. 📜
risczero.com/docs/explainer…
[3/]

When our zkVM executes a RISC-V binary, the receipt contains a cryptographic argument that allows third-parties to verify that the purported output was generated via a fully compliant RISC-V execution of that particular binary. 💻📜✅
risczero.com/docs/explainer…
[4/]

Over the past few years, there has been a 🦕Cambrian Explosion🦕 of these arguments of computational integrity. Ours is a STARK: a Scalable, Transparent ARgument of Knowledge.
risczero.com/docs/reference…
medium.com/starkware/the-…
[5/]

Everything about STARKs is framed in terms of polynomials: the circuit, the execution trace, and the computational integrity check. The whole problem space is ➕arithmetized➕ into a bunch of interconnected polynomials.
medium.com/starkware/arit…
[6/]

In a STARK, the Prover is committing polynomial evaluations to Merkle trees. 🌳
nakamoto.com/merkle-trees/

The Verifier says, “if you can convince me the leaves of these Merkle trees correspond to polynomial evaluations, I’ll believe your assertion of computational integrity.”
[7/]

So – a natural question arises:

How can we efficiently convince a third-party that a Merkle commitment corresponds to evaluations of a polynomial? 🤔
[8/]

One approach would be to reveal all of the leaves 🌿and let the Verifier interpolate the data themselves. This is horribly inefficient (for the Verifier), but it’s actually the best we can do if we insist on a perfect test.
[9/]

But if we allow for a test of proximity, we can do much better.
guyrothblum.files.wordpress.com/2014/11/rvw13.…
[10/]

What’s proximity, you ask?

The polynomials involved in STARKs are expressed as Reed-Solomon codewords, which have a notion of ‘proximity;’ if something isn’t a valid codeword, we can ask if it’s ‘close’ to a valid codeword.📏📐
risczero.com/docs/reference…
[11/]

A test that shows proximity to a valid Reed-Solomon codeword is called a Reed-Solomon Proximity Test (RPT).🥼🧪

Put succinctly, the FRI protocol is an efficient solution to the RPT problem.

Here’s the original paper: drops.dagstuhl.de/opus/volltexte…
[12/]

The full title is the ‘Fast Reed-Solomon Interactive Oracle Proof of Proximity.’ We’ve discussed the words ‘Reed-Solomon’ and ‘Proximity’ — but what’s with the word ‘fast’ and the term ‘interactive oracle proof’ (IOP)? 🤔
[13/]

⏱️‘Fast’ is a nod to the similarity between FRI folding and the FFT algorithm.
en.wikipedia.org/wiki/Fast_Four…
[14/]

An ‘IOP’ is an idealized mathematical version of the protocol, where the Verifier can request information from an “oracle.” In practice, we use Merkle branches rather than oracles, which turns the proof into an argument.
en.wikipedia.org/wiki/Interacti…
iacr.org/archive/tcc201…
[15/]

🌟Curious how FRI solves the RPT problem? We recommend the explainers from Vitalik and Alan Szepieniec:
vitalik.ca/general/2017/1…
aszepieniec.github.io/stark-anatomy/…
[16/]

🌟We’ve also got a concrete numerical example of FRI folding in our STARK by Hand explainer.
risczero.com/docs/explainer…
[17/]

🌟For a more technical overview, the Summary on the FRI Low Degree Test from @UHaboeck and the sequence diagram from @EllipticHector are fantastic resources.
eprint.iacr.org/2022/1216.pdf
[18/]

https://twitter.com/EllipticHector/status/1639698732064165893

🌟If you’re interested in the cryptographic security of the FRI protocol, the Proximity Gaps paper contains the state-of-the-art analysis. 📈
eprint.iacr.org/2020/654
[19/]

Happy reading! 📚🤓📚
[20/]