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/]
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.
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/]
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/]
🌟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/]
• • •
Missing some Tweet in this thread? You can try to
force a refresh
Feb 1: What RISC-V has to do with RISC Zero’s zkVM with Erik Kaneda
Ever wondered how a general purpose assembly language found its place in the zk landscape?
We’ll discuss compilers and interpreters and how we incorporate them into our zk world.
[2/]
Feb 15: Finite Field Implementations: Algorithms for Fast Multiplication and Modular Reduction with Victor Graf (@_subgraf)
We will discuss high performance implementations for finite field arithmetic based on Montgomery, Barrett, and Karatsuba techniques.