RISC Zero Profile picture
Mar 28 20 tweets 8 min read Twitter logo Read on Twitter
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/] Image
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/]
🌟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
 

Keep Current with RISC Zero

RISC Zero Profile picture

Stay in touch and get notified when new unrolls are available from this author!

Read all threads

This Thread may be Removed Anytime!

PDF

Twitter may remove this content at anytime! Save it as PDF for later use!

Try unrolling a thread yourself!

how to unroll video
  1. Follow @ThreadReaderApp to mention us!

  2. From a Twitter thread mention us with a keyword "unroll"
@threadreaderapp unroll

Practice here first or read more on our help page!

More from @RiscZero

Feb 21
Over the past week, we've released two important pieces to support our zkVM:

- a whitepaper with a formal description of our proof system
- a Lean4 repo for our formal methods work

Deets & links in 🧵👇

[1/]
Release #1: a formal description for our proof system

The proof system is STARK-based, using DEEP-ALI & FRI. For all the details, you can check out the draft here:

risczero.com/proof-system-i…

[2/]
Looking for a gentler introduction to the proof system? We've got a number of reference docs and explainers on the website.

risczero.com/docs/explainers

[3/]
Read 12 tweets
Jan 30
We’re excited to announce another round of RISC Zero's Study Club!

Feb 1 & 15
Mar 15 & 29
9am PST / 12pm EST / 5pm UTC

Zoom Link: zoom.us/j/99200763534

[1/]
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.

[3/]
Read 9 tweets
Nov 21, 2022
Looking for more digestible introductions to FRI and/or finite fields?

We just dropped a bunch of 2-3 minute youtube videos explaining various conceptual building blocks!

[1/ ] Image
e.g., here's a super brief introduction to the Prover-Verifier interactions in the FRI protocol
and here's one that introduces the term "polynomial commitment scheme"



[3/]
Read 7 tweets

Did Thread Reader help you today?

Support us! We are indie developers!


This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3/month or $30/year) and get exclusive features!

Become Premium

Don't want to be a Premium member but still want to support us?

Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal

Or Donate anonymously using crypto!

Ethereum

0xfe58350B80634f60Fa6Dc149a72b4DFbc17D341E copy

Bitcoin

3ATGMxNzCUFzxpMCHL5sWSt4DVtS8UqXpi copy

Thank you for your support!

Follow Us on Twitter!

:(