ZK Whiteboard Sessions - S2M7: FRI and Proximity Proofs (Part.1) with Dan Boneh

Transcript

Introduction and What is FRI?

Hi everyone. In this lecture we will talk about FRI and proximity proofs, what they are, how they are used to build SNARKs and the future of code-based SNARKs. There are lots of elegant ideas in this area, so let's get started. First, I wanted to show you on one slide all the papers that we'll be discussing in this lecture. So on the top here, I listed the papers that build SNARKs based on Reed-Solomon codes, and on the bottom, I listed papers that build SNARKs using codes that go beyond Reed-Solomon. These are all clickable, so you can read these papers later on if you want to learn more about what we'll be discussing in the lecture. So what is FRI?

FRI basically stands for Fast Reed-Solomon IOP of Proximity. So what does that mean? Let's fix a finite field F, let's say pick some prime and the finite field will just be the number of 0, 1, 2 up to p minus 1, where addition and multiplication is done modulo to this prime and let's L be some subset of the field. Now suppose we fix some function Y from the domain to the finite field, and suppose this is a committed function. So this means that the verifier actually has a commitment to this function. What FRI allows you to do, is it allows the prover to prove that Y is close to a Reed-Solomon codeword.

Yeah. That's all FRI is trying to do. So now you're probably wondering, so what? Who cares about proving that things are close to Reed-Solomon codewords? And what does this even mean? What is a Reed-Solomon codewords? What does it mean to prove that something is close to a Reed-Solomon codeword? That's exactly what we're going to talk about in this lecture. So let's get started. As I said, there are lots of beautiful ideas in this area. But before I actually show you what FRI is, I have to give you some background. And so let's start with kind of background material on what are codes, what is an interactive oracle proof, and what is a polynomial Interactive oracle proof. I'll try to go through this material quickly, but of course, you have the slides and you can view them later if you want to review anything I said.

Background on Linear Codes

So first of all, for a vector u in F to the n, we define the Hamming weight of the vector, sometimes this is denoted by the 0 norm of the vector, as basically the number of coordinates in the vector u that happen to be non zero. A nice way to write this is basically it's the sum of all the elements of the vector u raised to the power of 0, where we define 0 to the 0 to be 0. So you can see this means that if we're summing over an element that's not 0, the element would contribute 1 to this sum. And if we're summing over an element that is 0, it would contribute 0 to the sum. So really, what the Hamming weight is measuring is just the number of elements in the vector u that happen to be non zero.

Now, this happens to be a norm, as we said, it's called a zero norm, and it satisfies a triangular inequality just like regular norms do. So given that, we can now define what is a linear code C. So a linear code is parameterized by three values, n, k and l, and it's defined over a finite field of size p. Here, n is the length of the individual codewords. k is the dimension of the space that defines the code C, and l is the minimum Hamming weight of the code. So again, C is a linear subspace of F to the n. Its dimension is k, and a space of dimension k has p to the k words in it.

So that means the code has p to the k codewords in it. And the main property is that every codeword other than 0 has Hamming weight at least l. Okay? So I want you to remember these parameters. n, k and l. The length of the codewords, the dimension of the space that defines the code, Now, it turns out it's more convenient to talk about the relative Hamming distance between vectors. So we'll say the relative Hamming distance between u and v is the Hamming weight of u minus v, which basically counts the number of coordinates where u and v differ from one another, and we normalize that by the length of the code, so we divide by n.

So we get a number between 0 and 1. So again, the relative Hamming distance between two words is just a number between 0 and 1. And here we have a simple example. The relative Hamming weight between these two words is 3 over 5 because they differ in 3 positions and the total length is 5. Similarly, we're going to use Mu (μ) as the minimum weight of the code divided by n. This is sometimes called the relative minimum weight of the code is basically the minimum Hamming weight of the code divided by n. And again, this is a number between 0 and 1. So let's recall a few basic facts about linear codes. So first of all, for all distinct codewords u and v in the code, it must be that the relative distance between u and v is at least l over n.

And this is because if the codewords were closer than l over n, then really their difference would have weight less than l, and their difference, of course, is also in the code, and this would violate the minimum distance property of the code, which has to be at least l. So in a linear code, every two codewords are properly separated in that their relative Hamming distance is at least l over n. The second fact, which is called the singleton bound, is that the dimension of the code is at most n minus l plus 1. So in other words, the number of words in the code is at most p to the n minus l plus 1. And again, you can see that the larger the minimum distance is, yeah, the further away the codewords are from one another, the lower the dimension of the code, which means that there are

fewer codewords in the code. Now, the singleton bound is actually very easy to prove. All you do is you basically notice that if you take every codeword in the code, and you remove the first l minus 1 coordinates of that codeword, you must end up with distinct codewords, they will be now of length n minus l plus 1. And since they all have to be distinct, they can be at most p to the n minus l plus 1 of them. That's the whole proof. Okay. So again, we have this bound that says the larger the minimum distance of the code is, the smaller the number of codewords in the code or the dimension of the code has to be.

Now, if a code satisfies the singleton bound with equality, so the dimension of the code is equal to n minus l plus 1, this means that it's the largest possible linear code in F to the n, then this code is called an MDS code. Yeah. We cannot add any more words to this code because that would violate the singleton bound. And so, if the code is as large it can be, it's called an MDS code. MDS stands for Maximum Distance Separable. And the classic MDS code is called the Reed-Solomon code, which we will say more about in just a bit. Now, messages can easily be encoded into a linear code.

So since C is a linear subspace of F to the n, we can look at a basis of the code. Let's call those basis codewords C1 to Ck. There are k of them because the code has dimension k. And then for a message of length k -- we'll treat messages as vectors of length k. For a message of length k, we can encode that message as a codeword simply by taking a linear combination of the basis elements in the code. You notice that what this does is it expands the message a bit in that we started with a vector of length k and we ended up with a vector of length n, which is a little bit bigger.

In fact, we can treat a linear code as a linear map that maps messages in F to the k into codewords of length F to the n, where n is bigger than k. So this map basically expands the messages a little bit to encode them into the code. Because of this, we define the rate of the code to be basically k over n. Again, this is a number between 0 and 1, and the rate of the code denotes basically how much expansion is happening as we encode messages. So 1 over Rho(ρ) is the expansion rate from the message to the corresponding codeword. For example, in code-based SNARKs, people typically use a rate of 1/2, which means that the codeword is twice as long as the message that's being encoded.

Now, of course, we'd like to set Rho to be as large as possible, because the larger Rho is, the less expansion there is that's introduced by the code, and that also means that we will have a faster algorithm for encoding messages as codewords. So again, Rho equals 1/2 is a good compromise. The codeword is twice as big as the message, so encoding runs in a reasonable speed. The next thing we need to talk about is the unique decoding distance. So imagine we have two codewords in the code, we'll call them u and v. We know by the property of the code that their relative distance is at least Mu. Yeah. Mu is the minimum relative distance of the code.

And since these are distinct words, we know that their relative distance is at least Mu. Now let's look at some other word, w in F to the n. This is not a codeword, it's some word in F to the n, and there's a simple fact that says that there is at most 1 codeword u in the code that's at distance Mu over 2 from w. So if we look at a Hamming ball around the word w of radius Mu over 2, there will be at most 1 codeword in that ball. And this is quite easy to see, it follows directly from the triangular inequality in that if there were two words, say u and v, a distance Mu over two from W, then by the triangular inequality, we know that the distance between u and v will be less than Mu over 2 plus Mu over 2,

and that would contradict the fact that u and v have to be separated by at least a distance of Mu. Okay. So this basically shows that if we look at the word w and we look at the codewords at distance Mu over 2 from w, there is at most 1 such codeword. This is why Mu over 2 is called a unique decoding distance, and it's again, some number between 0 and 1/2. Now, one thing that's important to understand is that, in fact, most of the words in F to the n are not uniquely decodable. And the way to see that is if we basically take the union of all the balls of radius l over 2 around all codewords, this union is going to be the set of all uniquely decodable words.

If we just calculate the sum, the size of a Hamming ball of radius l over 2 is basically n choose l over 2 times p to the l over 2. Right? Because we choose l over 2 coordinates to change, and in those l over 2 coordinates, we can put whatever element of the finite field that we want. So we sum the size of a Hamming ball over all possible codewords. The number of codewords is bounded by the singleton bound, which I wrote over here. And so if we just work it out, we see that this number is much, much less than p to the n, which is a size of F to the n. So again, this means that the number of words that are uniquely decodable is much smaller than p to the n, which means that most words are actually not uniquely decodable.

So that introduces the concept of List decoding, which suggests the following notion. So, for word w and F to the n, we'll denote by List w, C, delta(δ) as the set of all possible codewords in the code C whose distance from w is at most delta. Okay. So given w, we're looking at all the words in the code that are at distance at most delta from w. So by what we just said, if we set delta to be less than the unique decoding distance, then we know that the List has at most 1 element in it.

It could have zero elements, if w is further than Mu over 2 from all possible codewords, and if w is uniquely decodable, then this word will have at most 1 element in it. So a natural question to ask is, how big is this List for other values of delta? And for this we have the Johnson bound, the very famous Johnson bound, that says the following; As long as delta is less than this function of the minimum distance, then it so happens that there's a very good bound on the size of the List. The size of the List is going to be at most 1 over epsilon delta(ε δ), where epsilon delta is defined as this funny expression here.

Now, this bound here is called the Johnson bound. It's always bigger than the unique decoding distance. So that says that again, up to the unique decoding distance, the size of the List will be at most 1. And then up to the Johnson bound, which is what we wrote here, the size of the List is bounded by 1 over epsilon delta for this epsilon delta. Now you notice that as delta approaches the Johnson bound, this expression here, this term here will tend to 0, and so 1 over epsilon delta will blow up and become infinity. So this bound on the size of the List is only meaningful as long as delta is less than this Johnson bound.

And as delta gets closer and closer to the Johnson bound, this bound and the size of the List blows up and goes to infinity. So let's plot the size of this List as a function of delta. So again, between 0 and Mu over 2, we know that the size of the List is at most 1. We know that between Mu over 2 and the Johnson bound, the size of the List is nicely bounded by 1 over epsilon delta. Above the Johnson bound, it turns out we don't really know much. It turns out the size of the List actually depends on C, all the way up to what's called the capacity bound. The capacity bound is actually Mu, the minimum weight of the code.

And above the capacity bound, we actually know that this List blows up. So this List becomes exponentially big. In particular, when delta is equal to 1, every codeword is in the List. So really, when delta is equal to 1, this List contains the entire code. One thing I'll say is that the proof of the Johnson bound is also not that difficult. It's a good exercise to try and prove this bound yourself. If you can't, then there are lots of online resources that give the proof. The proof is about half a page. Now, there are a couple of convenient terms that we'll use throughout the lecture. So let me quickly define what those are.

So for a word w and F to the n, we'll say that w is delta-close to the code. If there is some codeword in the code that happens to be a distance delta from w, and we'll write that the distance between w and the code is less than delta. Again, this means that there is some codeword whose distance is at most w. And similarly, we'll say that the word w is delta far from the code, if all the words in the code are at least distance delta from w. And again, we'll write that the distance between w and the code is greater than delta. Again, this means all the words in the code are of distance greater than delta from w.

So that's all I wanted to say about general linear codes. And now let's look at the classic MDS code called the Reed-Solomon code. Okay. So this is a very specific linear code. So let's just introduce some notation So, first of all, when we look at polynomials over a field F, I'll denote by F superscript less than d, the set of all bounded degree polynomials whose degree is less than d. The one thing that I want you to remember is that this is a linear space, and the dimension of the linear space is d because there are d coefficients in polynomials of degree less than d. Right?

↳ The classic MDS Code: Reed-Solomon

The constant term up to the coefficient of X to the d minus 1. d coefficients overall. Now, a polynomial f over the finite field defines a function from the finite field onto itself. But we will be interested in restricting these functions to a subdomain of the finite field. So let L denote a subset of the finite field. I'll call L the domain of the code. And I'm going to denote by f bar, the restriction of the function f to the domain L. Yeah. So again, F is a function over the entire field, and f bar is the same function just restricted to the domain L.

Now, what I want you to remember is that a function from the domain L to the finite field, where n is the size of the domain, can actually be viewed as a vector. We can just evaluate the function w at all the points of the domain, and as long as the points of the domain have a natural ordering to them, then basically we convert the function into a vector of length n. So I'm going to move back and forth between functions and vectors, but really those two are the same. We can always take a function and write it out as a vector by simply enumerating all the evaluations of the function over the domain. And we can take a vector and treat it as a function in the obvious way.

Okay. So now that we have our terminology, we can define the Reed-Solomon code. So the Reed-Solomon code defined over a field F using an evaluation domain L in the field, and then some parameter, which is the degree d, it's basically a linear code that's a set of all bounded degree polynomials restricted to the domain L. So I like to think of the codewords in the Reed-Solomon code as functions, but you can also think of them as vectors, where basically we evaluate the function F at all the points of the domain. So we get a vector of length n, where n is the size of the domain. So the degree bound that we're going to use is always going to be less than the size of the domain n, and as a result, a Reed-Solomon code is an n, d, l linear code where l is n minus d plus 1.

And this falls from the fact that a non zero polynomial of degree at most d minus 1 can have at most d minus 1 roots, and that means that the minimum weight of the code is n minus d plus 1. So again, because the minimum weight is equal to n minus d plus 1, it means that the Reed-Solomon code is in MDS code and therefore it has p to the d codewords. One codeword for every polynomial of degree less than d. Similarly, we can define the rate of the code just as before, as the dimension of the code, which happens to be d divided by the length. So this is a number between 0 and 1. And I wanted to also mention that an explicit encoding of a message would be done by treating the message as the coefficients of a polynomial of degree at most d minus 1.

And then we evaluate this polynomial at all the points in the domain, and that gives us a vector of length n which is the encoding of the message. So again, if the rate, for example, is 1/2, then we're evaluating a polynomial of degree at most d minus 1 at 2d points, and that gives us the codeword that corresponds to that polynomial. Now, when we talk about Reed-Solomon codes, it's convenient to restate the facts that we saw before in terms of the rate of the code, rather than the minimum distance of the code. So I'm, again, going to define this List, w, d, delta, as the List of all codewords in the Reed-Solomon codes that happen to be a distance at most delta from w.

The only thing I change is that instead of writing the code C here, I'm going to write the degree of the code, because that actually already defines what the code is. So we're going to use this notation quite a bit. So List, w, d, delta means the set of all Reed-Solomon codewords that are a distance at most delta from w. And now we can just restate everything in terms of the rate. So let's restate the unique decoding distance in terms of the rate. So when delta is less than Mu over 2, we know that the List has at most 1 element in it by the same argument that we saw before. But Mu we can express as l over n, l for an MDS code we know is n minus d plus 1.

So remembering that Rho is d over n, we see that this term here is roughly 1 minus Rho over 2. And it turns out it's more convenient to state things in terms of Rho than in terms of Mu. So we'll do that from now on. So we can restate the Johnson bound in terms of Rho. So as long as delta is less than 1 minus square root of Rho, we know that this List is bounded by this fraction 1 over epsilon delta. And again, you can see that as delta approaches the Johnson bound, as delta approaches 1 over square root of Rho, this term here goes to 0, and so epsilon delta will go to 0, and therefore 1 over epsilon delta will explode and become infinity.

But below the Johnson bound, we have a good bound on the size of the List. So again, just to remind you, we can plot the size of the List as a function of delta. Where we're below the unique decoding distance, the size is less than or equal to 1. up to the Johnson bound, the size has a nice bound 1 over epsilon delta. Above the Johnson bound, it's interesting. For Reed-Solomon code, there is a very specific question. You can ask how does the size of the List behave when delta is between the Johnson bound and the capacity bound? And it's interesting that this is actually an open question. It's really unknown.

I'll say more about that in a minute. But we know that above the capacity bound 1 minus Rho -- remember, 1 minus Rho is about Mu, the minimum distance of the code. So above the capacity bound, the List becomes exponentially big, and in particular, when delta is equal to 1, the List becomes the entire code. So I want to talk a little bit more about this unknown region here. What's interesting is that there is a conjecture that in fact, even in this region, the size of the List is only polynomial in n, so it's nicely bounded. And in fact, what is known, this is a result from 2024 is that if we choose the domain of the code at random, then in fact the size of the List really is polynomial in n, so there's a good bound for it.

Unfortunately, in our case we're not going to use a random L, we're going to use a very structured domain. And so this result doesn't apply to us. And for structured domains, it's still unknown how List decoding behaves when we're above the Johnson bound. Maybe one of you can actually resolve this question. It's a very interesting question. So finally, let's plug in real numbers. Let's say that we use a rate of 1/4. So this means that the codewords are 4 times bigger than the encoded messages. So you can see that the unique decoding distance is 3/8. The Johnson bound becomes 1/2.

So all the way from 0 to 1/2, we have Above 1/2, we don't really know what happens to the List. People conjecture that the List might still be well behaved in this interval, but we don't know that for a fact. So everything that we'll do in this lecture is going to be based on proven bounds, and so we'll stop everything at the Johnson bound. As we'll see later on, all the SNARKs that we build will become more and more efficient the larger delta becomes. So there's a natural tendency to use the largest possible delta that we can, and in this lecture we'll say that the Johnson bound is actually the largest delta we can use, where we know that the List has a nice bound on its size.

Okay. So this concludes our quick crash course in linear codes. These are all the facts that we'll need for this lecture. And the next thing we're going to look at is interactive oracle proofs. So let's quickly define what they are and see how they are relevant to SNARKs. So what is an interactive oracle proof? An interactive oracle proof is actually a nice information theoretic object that lets us develop proof systems without worrying about the underlying cryptographic primitives. So let's fix some relation R which consists of pairs of X, W. X is often called the instance, W is called the witness. For example, just to think of one simple relation, suppose X is equal to the hash of W would be one example of a relation.

Background on IOPs

But you can think more generally of maybe X is some commitment, and W is an opening of that commitment. And we'll say that they're in a relation if in fact W is a valid opening of X. So the only property we care about is that this relation is polynomial time computable, which means that given X and W, there's an efficient algorithm to test whether X and W are in the relation. So now, an IOP for the relation R is basically a proof system for the relation R, but it's a very abstract proof system. So let's see what I mean by that. Basically, an IOP for the relation R is a pair of algorithms, a prover and a verifier. The prover takes both the instance and the witness's input.

The verifier only has the instance X as input, and the prover is trying to convince the verifier that it knows the W such that X, W is in the relation. Now, the proof proceeds as follows. So the prover will send some string over to the verifier, the verifier is going to send a random challenge, the prover will send another string, the verifier will send another random challenge, and so on and so forth until the prover is done. And then the verifier is going to run this algorithm V, which is given all the random challenges, and the instance as input, and it's allowed to access the strings that the prover sent to it as oracles. Yeah. So what do I mean by that?

What I mean is that the verifier, this algorithm V can query these strings at individual cells. For example, the verifier can ask for the third cell of Pi(π)0 or the fifth cell of Pi1, and so on and so forth. So what it's allowed to do is query the strings at as many cells as it wants, and based on all that information, it decides whether it believes the prover -- that the prover knows a W such that X, W is in the relation, or it doesn't believe the prover. So it outputs yes or no. And of course, our goal is to design verifiers that make as few queries into these strings as possible. So we say that an IOP for the relation R is complete if in fact, when V interacts with the honest prover, the verifier will always accept the resulting interaction.

We say that it's sound, if -- when V interacts with a dishonest prover -- So for all P star, if X is actually not in the language of the relation, which means X is such that there is no W for which X, W is in the relation, then the verifier will reject X with very high probability. Yeah. We'll say that the probability that the verifier accepts is less than 2 to the minus 128, which is for us, a negligible value. So the IOP is sound, if no prover can convince the verifier to accept a false instance. We'll say that the IOP is knowledge sound, if a malicious prover is able to convince the verifier to accept X, that means that the prover actually knows W such that X, W is an R.

I'm going to keep this definition informal. You can look up some of the papers to see how to formally define what knowledge soundness means. So, given these three requirements, there's a trivial IOP system where the prover just sends the witness to the verifier and the verifier checks the witness by itself. The fourth condition says that the verifier needs to be succinct, which means that its running time must be very small compared to the time to evaluate the relation R. So the poor verifier doesn't have time to evaluate the relation R by itself because it has to run in time that is much, much smaller than the time to evaluate R. Now, the fact that the verifier has to be so fast means that the number of queries that it can make to these oracles has to be very small.

Yeah. So somehow the prover needs to convince the verifier that X is in the language of the relation, while the verifier is only making a very small number of queries to the strings sent by the prover. Now, why are these interactive oracle proofs interesting? It turns out that an IOP for relation R immediately gives us a SNARK for the same relation R through what's called the BCS compiler. Yeah. So the BCS compiler is very simple, works in two steps. In the first step, what we do is instead of sending the strings over to the verifier, we send Merkle commitments to those strings to the verifier.

↳ IOP to SNARK: the BCS compiler

Yeah. So you can see here, all I did is I replaced the strings by Merkle commitments to these strings. Everything else works as before. We send Merkle commitments, the verifier sends challenges, and finally, the prover sends the last Merkle commitment. and now the verifier needs to decide whether to accept or reject. So then, whenever the verifier queries the string Pi i at some cell j, the prover will respond with a Merkle proof for cell j. Yeah. So this will convince the verifier that in fact, the j cell of Pi i really is the value that the prover is providing. So again, we replace sending the strings by sending Merkle commitments, and we replace queries to these oracles by Merkle proofs that the strings really contain the correct values.

Of course, security of the resulting system is no longer unconditional. Security of the resulting system now depends on the collision resistance properties of the Merkle hash function. And the result of all of this is we actually end up with an interactive proof, an IP. There's no longer oracles involved, this is a really concrete interactive proof system. But we'd like to make it non interactive, and we make it non interactive using the Fiat-Shamir transformation. So here again, everything stays the same. We send Merkle -- the prover sends Merkle commitments to the verifier, but instead of having the verifier send the challenges, the prover generates the challenges by itself by hashing the Merkle commitments to generate the appropriate challenges.

And finally, the prover will run the verifier on its own, and every time the verifier makes a query, the prover will send a Merkle proof corresponding to that query. Yeah. So the entire SNARK proof becomes the commitments, plus the Merkle proofs at the points where the verifier queried the oracles. Then the SNARK verifier can run the verifier on its own now and confirm that the verifier accepted the proof. So that's it. That's the whole SNARK. And then there's a theorem that says that if the IOP has a property called round-by-round soundness, which I'm not going to define here, then the resulting system is either a SNARG or a SNARK for the relation R.

And I'll mention that there is a recent book by Chiesa and Yogev. The entire book is devoted to proving that the BCS transformation is secure. So this book gives all the precise definitions for all the terms we looked at so far, and it proves that this transformation really does give a secure SNARK. So let's talk about the efficiency of the resulting SNARK system. So, first of all, how hard does the prover have to work? Primarily, the prover has to commit to all the strings that it sends to the verifier, so it has to compute Merkle commitments to all these strings. So if we want the prover to work faster, we want to minimize the size of these strings, and that's going to be one of our primary goals when designing code-based SNARKs.

How do we minimize the size of these strings? And furthermore, if we want to reduce the proof size, we, of course, have to reduce the number of strings that are being sent over, because every one of those strings corresponds to a commitment. But more importantly, we want to reduce the number of verifier queries. And most of what we're going to spend our time on is how to reduce the number of verifier queries, because every query introduces a whole Merkle proof. And so the fewer queries that the Verifier makes, the fewer Merkle proofs we have to include in our SNARK proof, and as a result, the entire SNARK proof will be shorter. The next concept we need is a slight generalization of an IOP, which is what's called an IOP of Proximity or an IOPP.

↳ IOP of Proximity

So in an IOPP, the relation is actually made of triples, x, y and w. x and y are called the instance, and again w is called the witness. But this time y is one of those strings that the prover could have sent to the verifier. The difference is that y is now given, of course, to the prover, but y is given as an oracle to the verifier. So the verifier can query y wherever it wants, but it's not given y as an explicit input. Only x is given as an explicit input. Now, an IOPP works just as before, by the prover sends strings to the verifier, the verifier sends challenges.

And finally the verification algorithm V is given all the challenges, alpha 1 to alpha k, along with oracle access to the strings Pi0 to Pik and oracle access to this input y. So really what an IOPP allows us to do is allows us to prove properties of x and properties of some committed string y. And again, the verifier only interacts with y by asking for particular cells of y. So the point of an IOPP beyond this committed input y is that we also slightly change the notion of soundness.

So to do that, let me first give an auxiliary definition. So we'll say that the pair x, y is delta far from the relation R, if in fact, for every y prime that happens to be at most distance delta from y, the triple, x, y prime, w, is not in the relation. Okay. So this means that if you replace y by any y prime that's close to y, the result is not going to be in the relation. And if so, then we'll say that the pair, x, y, is delta far from R. And now we can define what does it mean for an IOPP to be complete and sound. Completeness is just as before, if the verifier interacts with an honest prover, then it will always accept triple x, y, w.

However, soundness is defined a little bit differently. So for delta in the interval 0 to 1, we'll say that the IOPP is delta sound, if for all x, y that are delta far from the relation R, the verifier will only accept x, y with negligible probability. So if x and y are delta far from the relation, the verifier is very likely to reject. So this is a relaxed notion of soundness in that the verifiers only require to reject when x, y are delta far from the relation. When x, y actually are delta close to the relation but not in the relation, then there is no guarantee on the output of V.

We don't really care what V does. It can either accept or reject. So to summarize again, if there is a w such that x, y, w is in the relation, the verifier must accept the interaction with the honest prover. If x, y are so that they are delta far from the relation, the verifier will reject with high probability. And if x, y is in neither case, then there's no constraint on the output of the verifier. Now, the most important IOPP for us is what we call the Reed-Solomon IOPP, which is the way to prove that a word u is close to the Reed-Solomon code. So the relation we'd be interested in is where the instance is just the Reed-Solomon code, C, the committed word y is going to be some arbitrary function from L to F, the verifier has access to the committed word y,

and it knows what code of course we're dealing with, and we say that u is in the relation if u happens to be in the code. So what does it mean to build delta IOPP for this relation? The IOPP has to be complete, meaning that if u really is in the code, then the verifier will always accept the interaction with the honest prover. But if the distance of u from the code is greater than delta, then the verifier will accept only with negligible probability. In other words, the verifier will almost always reject. So again, a Reed-Solomon IOPP makes it so that given a committed word, if the word is in the code, the verifier will always accept the interaction with an honest prover.

But if the word is delta far away from the code, then the verifier will almost always reject that word. And now FRI is basically one example of an efficient Reed-Solomon IOPP. So we'll see how FRI works in just a minute, but the first question to ask is why is this useful? Why do we care about Reed-Solomon IOPPs? Why does it help to prove that a committed word is close to a Reed-Solomon codeword? To answer that, I need to define a special type of interactive oracle proof called a Poly-IOP. So a Poly-IOP works the same way as an IOP. The one difference is that what the prover actually sends to the verifier are basically bounded degree polynomials.

So rather than sending arbitrary strings, the prover is sending bounded degree polynomials, and everything else continues the same way. So the verifier responds with challenges, the prover sends more bounded degree polynomials, and then at the very end, the verifier basically can query these polynomials at arbitrary points in the finite field, and then decide whether it wants to accept x or reject x. So this is a special case of an IOP in that the strings that the prover sends to the verifier must be polynomials of bounded degree. So completeness and soundness is defined for a Poly-IOP, just as for an IOP.

So why are Poly-IOPs important? It turns out we can compile a Poly-IOP into a SNARK, and most SNARKs are constructed in this way. So then the question we're left with is how to compile a Poly-IOP into a SNARK, and it turns out that is exactly where a Reed-Solomon IOP of Proximity is going to come up. And this is actually one of the most important application for a Reed-Solomon IOPP. So the question is how to compile a Poly-IOP into a SNARK. So, just as in the BCS compiler, we do this in two steps. The first step is we replace the polynomials sent by the prover by a polynomial commitment to the same polynomials.

Compiling a Poly-IOP to a SNARK using a Reed-Solomon IOP of Proximity

We talked about polynomial commitment schemes in the previous season of the Whiteboard Sessions. So you can see there what are polynomial commitment schemes, but fundamentally, a polynomial commitment scheme allows you to commit to a polynomial, and later on, the verifier can ask you to evaluate the committed polynomial at a given point x, and you can prove that the committed polynomial evaluates to y at the given point x. So we replace the polynomials that the prover sent by commitments to those polynomials, and later on, when the verifier wants to query the polynomials, the prover will provide polynomial evaluation proofs for those openings.

So that turns the Poly-IOP into an interactive proof, and then we make the interactive proof non interactive, using the Fiat-Shamir transformation. Now, again, I want to stress that in fact, many SNARKs are derived from Poly-IOPs. Poly-IOPs can use univariate polynomials like Plonk, or they can use multilinear polynomials like HyperPlonk. And what we've observed in recent years is that SNARKs that are derived from multilinear Poly-IOPs are more efficient than SNARKs that are derived from univariate Poly-IOPs. So slowly, the world is shifting towards multilinear Poly-IOPs. But nevertheless, in this lecture, we're going to focus on Poly-IOPs that use univariate polynomials.

So really, in a picture, the transformation looks like this. We start from a Poly-IOP, we use a polynomial commitment scheme to replace the polynomials by commitments to those polynomials and replace queries to the polynomials by evaluation proofs. This gives us an interactive proof, and then we apply the Fiat-Shamir transformation to get a SNARK. And what I want to show you in the next few minutes is that in fact, an IOPP for Reed-Solomon codes gives us a way to build polynomial commitments. And so it gives us a way to instantiate this transformation. And so, in a bit more detail, the picture when we use IOPPs looks like this.

We start from a Poly-IOP. It turns out we can use a Reed-Solomon IOPP to convert this to an IOP. And once we have an IOP, we can use the BCS compiler to convert that into a SNARK. So the interesting step in this process is how do we convert a Poly-IOP into an IOP? And doing so is going to make us develop some very interesting tools. So let me explain why this is such an interesting problem. So, in the world of Poly-IOPs, remember, the prover is sending polynomials over to the verifier, and then the verifier asks the prover to evaluate these polynomials at various points of the verifier's choosing.

Yeah. And then the prover basically sends evaluations of these polynomials at the required points. Now, in the world of IOPs, we can't do this. In the world of IOPs, the prover just sends strings, it doesn't send polynomials. And what the verifier can do is open those strings at arbitrary cells. So the challenge for us is how do we build a polynomial evaluation oracle, which is needed on this side of the world, just given a cell lookup oracle that's available in the world of IOP. So the first question we have to answer is how do we represent polynomials as strings? And hopefully, given all the tools we've developed in this talk, this is now a natural thing to do.

What the prover will do is, rather than sending the polynomial to the verifier, it's going to send to the verifier an encoding of the polynomial. Okay? So we fix a domain L, which is made up of elements a1 to a n in the finite field. And what the prover will actually send to the verifier is the corresponding Reed-Solomon codeword, namely the evaluation of the polynomial at all the points in the domain. Yeah. And as we said, this is a Reed-Solomon codeword of length n. And just for simplicity, we're going to treat the string Pi that the prover sends to the verifier, we're going to treat it as a function from l to f.

But really, you should be thinking of it as a string that contains the codeword. And so this compiler, from a Poly-IOP to an IOP uses the Reed-Solomon code to represent a polynomial as a string. But you should be asking yourself also, why is so special about the Reed-Solomon code? Why can't we use other codes to encode polynomials as strings? And maybe those codes actually have benefits beyond Reed-Solomon? And in fact, as we'll see, this is where the research is focusing these days, on other codes beyond Reed-Solomon that might actually have better performance and better properties when we build SNARKs out of them.

But for now, we're just going to focus on the Reed-Solomon code, and we'll see how to make that work. So the prover encoded the polynomial as a Reed-Solomon codeword, but now immediately we run into a problem. The problem is that in the world of Poly-IOPs, the prover could only send bounded degree polynomials to the verifier. The problem is that now there is no constraint on the prover. The prover could send to the verifier arbitrary strings. Yeah. A malicious prover could try to send things that are not codewords and therefore do not represent any polynomial. So the question is, how do we prevent that?

Can the verifier confirm that the string that the prover sent to it really is a codeword in the Reed-Solomon code, but can it do that only by opening a very small number of cells in the string Pi? And of course, that can't be done, because what if the prover sent a string that's equal to a Reed-Solomon codeword everywhere except in one cell? What's the likelihood that a verifier will open exactly that cell? That is very unlikely. And as a result, the verifier will never detect that the string that the prover sent is not actually a Reed-Solomon codeword. But what the verifier can do, is it can use a Reed-Solomon IOPP to test that the string the prover sent is delta close to some codeword in the Reed-Solomon code.

And in fact, if it can do that for a delta that's less than the unique decoding distance of the Reed-Solomon code, then that means that the string represents some unique polynomial as was required. So how do we check that the string that the prover sent to the verifier in fact is delta close to a codeword? That's exactly what a Reed-Solomon IOPP will do, and that is exactly what FRI does. So the point is that the verifier will run the Reed-Solomon IOPP. If the Reed-Solomon IOPP accepts, the verifier is guaranteed that with very high probability the string that the prover sent is delta close to some codeword in the Reed-Solomon code.

And as we say here, if delta is less than the unique decoding distance, that means that there's at most one such codeword. Okay. So we're making progress. We can bind the prover to a particular polynomial, but this is still not a polynomial commitment scheme because we need to be able to create evaluation proofs for that polynomial at arbitrary points x. So to see how we use this idea to build a polynomial commitment scheme, we have to introduce a new tool called quotienting. Okay? So this is a very important tool in the world of Reed-Solomon based SNARKs. And so let's explain what quotienting is. So let's fix some values a and b in the finite field.

↳ Quotienting

The only thing that I'm going to require for now is that a is not in the domain of code. And let's suppose that we have some function u from L to F. Now, if it's easier, you can think of u as a vector of size n, where n is the size of L, but for convenience, it's actually better for us to think of u as a function from L to F. Now, given such a function, we can define the quotient function q(X) as applying this division to the values of u. So in other words, given the little a and little b, we define q at some point X as u(x) minus b divided by x minus a. Okay? And we'll see why that makes sense in just a second.

This is another function from L to F. In fact, this is defined at every point of the domain L, and this is because a is not in L, that the denominator is never going to be 0. So this is well defined at every point in the domain L. Okay? So we'll call this the quotient function. This is called quotienting, because given any function u, we can define its quotient. And now there are these two amazing facts about this quotienting operation which are really quite pretty. The first one says that if u is in fact a Reed-Solomon codeword, it's equal to the restriction of some bounded degree polynomial, and it so happens that b is equal to f of a, then in fact the quotient function is also going to be a Reed-Solomon codeword, but in a code of degree 1 less than the original.

So if the prover is honest and is really sending us a Reed-Solomon codeword and b really is equal to f of a, then in fact the quotient word is also going to be -- The other more interesting fact, is that if we look at all the polynomials that are delta close to the word u, and for all these polynomials, b is not equal to g of a, then it so happens that q necessarily is delta far from this Reed-Solomon code of degree d minus 1. Okay? So we have two cases. If b is equal to f of a, then q will be close to the Reed-Solomon code, and if b is not equal to f of a for all polynomials that are delta close to u, then in fact q is going to be far away from the Reed-Solomon code.

Yeah. These are two beautiful facts. I wrote down the proof for fact two here. I'm not going to go through this proof here. It's basically a proof by contradiction. If you're interested, you can review this proof yourself. It's actually a very simple proof that basically shows that if q happens to be delta close to this Reed-Solomon code, then there must be a g bar in the List for which b is equal to g of a, violating the assumption. Okay. So we're making progress towards giving evaluation proofs of committed polynomials by quotienting. You can see if the evaluation is correct, we're close to the codeword. If the evaluation is not correct, then we are going to be far from the code, so therefore a Reed-Solomon IOPP will help us test whether b really is equal to f of a or not.

Now it turns out this actually generalizes, and we can quotient by a few more values if we wanted to. So, for example, let's set a1 to ak be the points where we want to evaluate our polynomial and b1 to bk be the purported evaluations of the polynomial. Okay. Again, I'm going to insist that all a1 to ak are not in the domain of the code. Let's define these two auxiliary polynomials. One is called the vanishing polynomial and one is called the interpolation polynomials. These are polynomials of degree at most k. The vanishing polynomial basically vanishes at all the ais and the interpolation polynomial basically interpolates ai to bi, so the interpolation polynomial is going to be a polynomial of degree at most k.

And now we're just going to do exactly the same thing we did before, except we're going to quotient by these polynomials rather than by fixed values. So we define the quotienting map that maps a word u into a quotient word q by defining it as I wrote here. So we do u(x) minus i(x) divided by v(x). And again, this is well defined on the entire domain L because none of the evaluation points are in the domain L. All right. So we defined a slightly more generalized quotient map where we quotient by more values than just one value, as we did before, and the same facts hold.

So if u is a Reed-Solomon codeword and bi is equal to f of ai for all i and k, then the resulting quotient word is in fact in a Reed-Solomon code of degree d minus k. And the corresponding fact says that if every codeword that is d close to u violates the evaluation property, then the quotient word will be delta far from the code of degree d minus k. Okay. So the same properties as we saw before, just now, holding for multiple values rather than just one value. The proof is basically the same as the proof in the previous slide, and I'm going to point to the STIR paper if you want to see the proof spelled out.

So now we have a way to test if the string that the prover sent us really is a Reed-Solomon codeword. Then we can evaluate corresponding polynomial at many points at once, by quotienting by the interpolation and vanishing polynomial. And if the prover is lying, it's sending us some word u that happens to not evaluate the correct values for all polynomials that are delta close to u, then the resulting quotiented word will be far away from the relevant Reed-Solomon code. This quotienting mechanism will now allow us to convert a Poly-IOP into an IOP.

↳ Poly-IOP to IOP

So let's see how we do it. the Poly-IOP prover is going to send some bounded degree polynomial to the verifier. In the IOP world, the prover will send some word to the verifier where what the honest prover will do, is it will actually send the Reed-Solomon encoding of the polynomial f. But again, remember, the malicious prover can send whatever string it wants. It's only the honest prover that sends a Reed-Solomon codeword. Now, in the Poly-IOP world, the verifier will want to query this polynomial at some point a1 and receive back the evaluation of f at a1. In the IOP world, the prover now is to convince the verifier that b1 is equal to f of a1.

How do we do this? This is exactly where we're going to use a Reed-Solomon IOPP. So what the prover and verifier will do is they will run the interactive oracle proof of proximity to prove that this quotient here is actually close to the Reed-Solomon code of degree d minus 1. And what do we mean by close? This is for some delta in 0,1 that we'll define a little bit later. So the cool thing is that the honest prover actually sent a Reed-Solomon codeword to the verifier, so the honest prover can easily convince the verifier that q1 really is a Reed-Solomon codeword in this code, the dishonest prover is going to have a -- if b1 is not equal to f of a1, for every polynomial f that's delta close to Pi, then q1 will be delta far from this code,

and as a result, the IOPP will reject this quotient. Now, I want you to notice that the function q1 is actually quite easy to calculate from Pi. Simply, the prover and verifier do this division for every point where the IOPP verifier wants to open the string Pi. Sometimes we call this a virtual oracle in that this oracle for q1 is derived from the oracle for Pi. The prover doesn't actually send q1 to the verifier, it just computes it from Pi, and this is why q1 is sometimes referred to as a virtual oracle. So next, the Poly-IOP verifier might want to open the polynomial f at some other point a2, and again, on the IOP side, what they'll do is they'll run this RS-IOPP, this time with b2 and a2 as

the numerator and denominator, and prove that the resulting quotient is again close to the Reed-Solomon code of degree d minus 1. So what does the verifier learn from this? What the verifier can conclude is that there are some polynomials f1 and f2 that are delta close to the function Pi. And because of the two facts that we proved, we know that f1 of a1 is equal to b1 and f2 of a2 is equal to b2. Because if either one of these conditions were violated, then q1 and q2 would not be delta close to the function Pi. So this is nice.

The verifier learned that the evaluations are correct for some polynomials f1 and f2. The problem is that the List Pi, d, delta, might contain more than one polynomial, and these might be distinct polynomials, and in fact, the IOP prover was not committed to a unique polynomial, whereas on the Poly-IOP side, when the prover sends the polynomial over to the verifier, that commits the prover to a unique polynomial. So this is not a valid compilation, because on the left the prover is committed to the polynomial f, whereas on the right the prover is not committed to the polynomial f, it could use either f1 or f2, whichever is more convenient to the malicious prover.

But fortunately, there's easy fix for this. This fix uses a very simple observation called DEEP. DEEP stands for Domain Extension for Eliminating Pretenders. It says the following; Basically, before sending any evaluation queries, what the verifier will do is it will sample one element R out of the domain L. Yeah. This is called an out-of-domain sample. And the prover will send back an s such that s is equal to f of r for some polynomial f. And my claim is that r, s is going to commit the prover to only one polynomial that's delta close to the function Pi.

Why is that true? Let's define the bad event to be an event where there are two polynomials f1 and f2 that are delta close to the function Pi such that both of them happen to evaluate to s at the point r. What is the probability that this bad event happens? Well, we know that f1 and f2 are both polynomials of degree less than d. And that means that they can agree under most d positions because otherwise their difference polynomial would have more than d roots. And so that says that if we choose one particular f1 and f2 in the List, they will both evaluate to s at the point r with probability at most d over F minus L, they agree, and at most d points.

So the probability that r happens to be one of those d points is at most d over F minus L. So now we can just union bound over all possible f1 and f2, and that gives us a nice bound on the probability of the bad event. Okay. And this is where we're going to use the Johnson bound. So when delta is less than a Johnson bound, we know that the List has bounded size. And therefore, if our field is sufficiently large, this denominator is going to dominate d, and it's also going to dominate this term here, because the size of the List is bounded and actually relatively small. So we're just going to assume that F is sufficiently large so that the probability of the bad event is negligible.

And even if F is not sufficiently large, if F is small, we can still make the probability of the bad event be negligible by simply choosing multiple r's rather than just one r. And so the bottom line is, when delta is less than the Johnson bound, because the size of the List is small, with high probability, there's going to be only one polynomial F in the List that's delta close to Pi that satisfies f(r) is equal to s. And so when the prover sends us back the value s, it's committing to one polynomial in this List that now it has to use. And so now we can actually build our full compiler, which is as follows; Every time that the Poly-IOP verifier makes a query to the polynomial, what will happen on the IOP side is that they're

going to run a Reed-Solomon IOP of Proximity for a modified quotient. The quotient is going to be for two values to prove that the encoded polynomial evaluates to b1 at a1 and 2 evaluates to s at r. Okay? And so what they'll do is they'll run a proximity test that this quotient is now close to a Reed-Solman code of degree d minus 2. If the IOPP accepts this proof, what the verifier can conclude is that there is some polynomial f1 that's delta close to Pi, such that f1 of a1 is equal to b1, and f1 of r is equal to s.

Again, this follows from this fact 2 that we saw two slides ago. And now when the Poly-IOP verifier makes a second query, we're going to do exactly the same thing, except this time we're going to use a2 and b2. It still use r and s. So they're going to run the IOPP again, this time with these modified quotients, and the prover again will prove that q2 is close to the Reed-Solomon code of degree d minus 2, from which the verifier can conclude that there's some other function f2 bar that's delta close to Pi such that f2(a2) is equal to b2 and f2(r) is equal to s. But the cool thing is, as long as when f1 and f2 agree on the point r, we know that they must be equal with high probability.

So now the verifier learned exactly what it needs to learn. It learned that there is one polynomial f that the prover committed to, and that polynomial evaluates to b1 at the point a1 and evaluates to b2 at the point a2. So to summarize, the way the compilation works is when the Poly-IOP prover sends a polynomial f, the IOP prover is going to encode F using the Reed-Solomon code. And as we said, other linear codes are also possible, and they actually might be even faster than the Reed-Solomon code. This is something that we'll discuss a little bit later. Now, when the Poly-IOP verifier needs to evaluate this polynomial f, what the IOP prover and verifier will do is, they'll run a Reed-Solomon IOPP to prove that this quotient is close to a Reed-Solomon code of degree d minus 2.

This proves to verify that the encoded polynomials in fact evaluate to the claimed values. And finally, we said that when delta is less than a Johnson bound, this single out-of-domain query r, s ensures that the prover is bound to one unique polynomial with very high probability. So this is pretty elegant and allows us, again, to compile a Poly-IOP into an IOP. So again, going back to our picture, it shows that the Reed-Solomon IOPP is the key ingredient in compiling a Poly-IOP into an IOP. And remember, what the Reed-Solomon IOPP is actually being applied to are these quotient polynomials.

They are the ones that convince the verifier that the evaluations it requested in fact are the correct evaluations. And then again, once we have an IOP, we can simply use the BCS compiler to get a SNARK. So, just to conclude this section, I want to make two more comments. The first one is, everything we did so far assumed the evaluation point is outside of the domain of the code. But what if the Poly-IOP verifier actually wants to evaluate the polynomial at a point in the domain of the code? What happens then? The problem is that when we defined our quotient, we divided by x minus a, and if a is in the domain of the code, then we're dividing by 0, and as a result the quotient is undefined.

This was not a problem when the evaluation points were always outside of the domain of the code. But it turns out there's a very simple solution to this. Basically, you just need to remember that if in fact f of a is equal to b and f of r is equal to s, then this quotient is of polynomials is just another polynomial of bounded degree d minus 2. In other words, this denominator actually divides the numerator as a polynomial. So we can define little q at the point a as this quotient polynomial evaluated at a. And this quotient polynomial is just a polynomial, so we can actually evaluate it at a.

From the honest prover's point of view, this little q is really going to be the Reed-Solomon encoding of this quotient polynomial. So this quotienting technique that we just talked about also provide evaluation proofs where a is in the domain L. The second comment I want to make is that as we described it so far, things are really quite inefficient. The IOP has to use one IOPP for every query of f. Running these Reed-Solomon IOPPs is not cheap. And so we'd like to basically compress all these Reed-Solomon IOPPs into a single Reed-Solomon IOPP.

And it turns out we can do that using a batching technique that allows us to batch many Reed-Solomon IOPPs into a single one. And so that's the thing I want to show you next, but to do that, we first have to develop some tools. So the last topic before we break is an important collection of tools. These are called Distance Preserving Transformations, and these are the key tools that will allow us to build an efficient Reed-Solomon IOPP. So let's walk through this quickly and then we'll take a break. So a distance preserving transformation is a transformation that takes as Input some functions u1 to uk along with some random value r, and it outputs some other function u.

Distance Preserving Transformations

Now, the functions u1 to uk are defined over a particular domain, whereas u might be defined over a slightly different domain, which I'll denote by L prime. Now, the property of this transformation is that If u1 to uk are codewords in a Reed-Solomon code, then the result of the transformation is going to be an honest codeword in another Reed-Solomon code, possibly with a different domain and possibly with a different degree. And this should be true for all values of r. In the dishonest case, if some of the uj's happen to be delta far from the original Reed-Solomon code, maybe even if one of the uj's happens to be delta far from the original Reed-Solomon code, then the result of the transformation u is going to be delta from the resulting Reed-Solomon code with very high

probability over the choice of r. Okay. So we call it distance preserving, because if we start with things that are close, we end up with something that's close. And if we start with even one thing that's far, we end up with something that's far. So I want to give you two examples of distance preserving transformations. These are critical examples for what's coming. So let's start with the first one. The first one is what we call batch Reed-Solomon IOPP, where the prover is committed to a bunch of words u0 to uk, and it wants to convince the verifier that all of them are delta close to our Reed-Solomon code.

↳ Example 1: Batch RS-IOPP

The naive way to do it is basically to run the Reed-Solomon IOPP for each one of those committed words, but that would require k Reed-Solomon IOPPs. We'd like to do something that's much better, and we do that by batching them into a single function u. And then we're just going to run the RS-IOPP once on this word u. How do we do that? The verifier is going to sample a random r in the finite field, and send that to the prover. The prover is going to define the batched word as basically a linear combination of all those words, where the linear combination is defined by powers of r. As we just wrote here.

You notice this is just another function from L to F. And then as we said, that they're going to run the RS-IOPP just over the word u. This u is a virtual oracle, so every time the verifier wants to open u at a particular cell, what the prover will actually do is it will open all of u0 to uk at that cell and then the verifier can do the linear combination of those to get u at a point a. So the question is why is this distance preserving? And that's a really interesting question. So in the case of an honest prover, this is obvious.

If u0 to uk are in the Reed-Solomon code, because the Reed-Solomon code is a linear code, the linear combination of u0 to uk is also going to be in the Reed-Solomon code, and that's going to be true for all r and F. The interesting case is what happens if one of the uj's happens to be delta far from the Reed-Solomon code. Now we need to argue that u is delta far from the Reed-Solomon code with high probability over the choice of r. Now this is a highly non-trivial question about polynomials, and it took some time to actually work out this result. This is a non-trivial result, but it's been worked out when delta is less than a Johnson bound and it follows from the famous BCIKS proximity gap theorem.

↳ The BCIKS Proximity Gap Theorem

So what does the theorem say? Again, this is a very important theorem in the space. It was only proved in 2020 and it shows what we want. If we have functions u0 to uk, and we have some value delta that's less than the Johnson bound, let's define u superscript r as the linear combination of u0 to uk, and the theorem says that suppose that u superscript r is delta close to the Reed-Solomon code for just a small number of r's, then in fact, all the uj's have to be delta close to the Reed-Solomon code. So you're probably wondering what this err is, so let me just write it out for you.

The theorem is very explicit about it here, I'm just going to write it in a way so that you'll have a clean idea of what the err looks like. So basically, when we're below the unique decoding distance, the err grows linearly in the length of the code. When we're between the unique decoding distance and the Johnson bound, the err grows quadratically in the length of the code. Yeah. And again we're going to assume that our field is big enough so that this err is actually negligible. And if that's not true, we're simply going to have to use multiple r's. Yeah. Not a single r, but we're going to have to use multiple r's and prove that all of those u superscript r's are close to the Reed-Solomon code.

So again, what this says is that if u superscript r is delta close to the Reed-Solomon code with non negligible probability, then already we know that all the uj's I want to write out the contrapositive of this theorem, which says that if even one of the uj is delta far from the Reed-Solomon code, then u superscript r must also be delta far from the Reed-Solomon code with high Now it turns out actually the proximity gap theorem is a little stronger than what I said, and this strengthening is actually quite important for what's coming.

So actually what the theorem says is that not only do we know that if u superscript r is delta close to the code, then all u0 to uk are delta close, in fact we know that there is a subset of positions in the code that's sufficiently large, it's bigger than 1 minus delta times the domain of the code, such that every uj matches a codeword at every element of S. Yeah. So not only are u0 to uk delta close to the Reed-Solomon code, they're in fact delta close on the same positions identified by the set S. This is called correlated proximity because it shows that all these words are delta close using exactly the same positions in a large enough set S.

Okay. And the fact that we have correlated proximity is going to be really important for what's coming. So you might be wondering, why is this called a proximity gap? You notice what the theorem implies is that once we know that u0 to uk are all delta close on the same positions S, that means that all their linear combinations are also going to be delta close to the code on all positions in S. Again, because the code is a linear code. So if all of u0 to uk match codewords on positions in S, it must be that they're linear combination also matches codewords on positions in S for every r in the finite field.

So really what this says is that this probability of how likely is ur to be delta close to the code exhibits a gap, meaning we can only be in one of two worlds. Either u superscript r is delta close for a negligible number of r's, or ur is delta close for all Rr It's not possible to be anywhere in the middle. Yeah. There's a gap between these two worlds. Either u sub r is hardly ever close, or it's always close to the code. And this is why it's called a proximity gap, and it turns out this is an incredibly important tool for all hash-based codes. Okay. So far we saw that if we have k vectors that we're trying to prove are close to a code, we can do that by taking a linear combination of all of them, and proving that the linear

combination is close to the code. And the reason this works is because of the proximity gap theorem for Reed-Solomon code, at least as long as delta is less than the Johnson bound. So to do that, basically we showed that taking a linear combination of a bunch of words is a distance preserving transformation. The second example of a distance preserving transformation is called folding, and this is going to be directly relevant to FRI. So let's briefly explain how this works and then we'll break. So from here on, I want the domain of the code to be a set of roots of unity in the finite field. So in fact, I'm going to assume that the length of our code is going to be a power of 2, and that the domain is just going to be all the 2 to the nth roots of unity in the finite field.

↳ Example 2: Folding

Now, omega is an nth primitive root of unity. This implies that n has to divide the size of the finite field minus 1, which means that everything that I'm going to say from now on only applies to specific fields that -- where F minus 1 is divisible by n. This is actually one of the limitations of FRI in that it only works in fields where n divides the size of the field minus 1. When we talk about IOPPS for other codes, we'll be able to eliminate this restriction. Nevertheless, there are two important points about this specific domain of roots of unity. The first one is, because n is a power of 2, we know that omega to the power of n over 2 is equal to minus 1, and that means that if x is in the domain,

then minus X is also in the domain. Yeah. So the domain naturally splits into pairs of x, minus x. The other thing we're going to need is to define the notation L squared, which is basically the set of all powers of elements in the domain. And when we square, both minus a and a will both map to a squared. What this means is the squaring is a 2 to 1 map, and therefore the size of L squared is half the size of L. Yeah. In particular, since we always use n to denote the size of L, the size of L squared is going to be n over 2.

Similarly, we can define L to the 4th, which is going to be the set of 4th powers of elements in the domain, and the size of L to the 4th is going to be n over 4, and so on and so forth. So now let's define the folding transformation, and I want to start by defining it for an example. So let's look at this specific degree 5 polynomial. It has 6 coefficients. And what we will do is given this polynomial f, we can break it up into two polynomials. I'm going to call one the even polynomial, and the other one the odd polynomial. So the even polynomial is going to contain all the coefficients of monomials of even degree. You can see here it's 1, 3 and 5.

Yeah. So you can see, actually, we took all the even monomials from the polynomial f, and we built another polynomial -- since there are only three such monomials, this polynomial is going to be quadratic. And similarly, we can define the odd polynomial to be all the coefficients of the monomials of odd degree inside of f. Okay. So when we break the polynomial in this way, it's not difficult to see that in fact the original polynomial is simply the even polynomial evaluated at X squared plus the odd polynomial evaluated at X squared and shifted by X. Yeah. If we do this addition, we get the original polynomial.

So now we can define the folding of the polynomial f, and the folding is simply defined with respect to some element r in the finite field. It's simply a random linear combination of f even and f odd. And you notice this is a quadratic polynomial because f even and f odd are both quadratic. So it's not a surprise that in fact, if we start from a polynomial of bounded degree 6, we end up with a polynomial of bounded degree half of 6, which is 3 in this case. So more generally, we can define folding as follows. We can fish out the even monomials out of the polynomial by computing f of x plus f of minus x.

If you think about what that does, all the odd degree monomials will cancel out. For example, x plus minus X is going to be 0. But all the even degree monomials, like X squared and minus X squared, the minus will cancel out and we'll get 2x squared out of that. So the even monomials will be counted twice. So we divide by two and we end up with the f even polynomial evaluated at the point X squared, and similarly, if we want to fish out all the odd degree monomials from f, what we can do is we can look at f(x) minus f(-x), This will cancel out all the even degree polynomials and leave in the odd degree polynomials.

And if we divide that by 2x, we'll end up with the odd polynomial. The polynomial that contains the coefficients of all the odd degree monomials. And we define the folding as a random linear combination of f even and f odd. And you notice this, we started with a polynomial of bounded degree d, and we end up with a polynomial of bounded degree d over 2. Now, again, we have our relation that f of x can be evaluated using f even and f odd evaluated at X squared. In addition, because of the relations on top here, we see that for a given element a in the finite field, if we evaluate f of a and f of minus, we can evaluate the even and odd polynomials at a squared by simply plugging f of a

and f of minus a into these relations. This would allow us to evaluate the folded f at a squared, again, just given the evaluation of f at a and minus a. The other thing that's easy to see is if we start with a Reed-Solomon codeword, and we fold that codeword using these relations, then we end up with a Reed-Solomon codeword defined over the domain L squared, because we can only define the folded polynomial over squares, and the degree will be half the degree of the original polynomial. What this means is that folding actually doesn't change the rate of the resulting code.

As we fold the polynomial, we move to a different Reed-Solomon code, but it's a Reed-Solomon code that has the same rate as before. So now that we know how to fold polynomials, we can similarly fold arbitrary functions from L to F in exactly the same way. We define u sub e, u sub o and u sub fold, just like we did before. Right? For every a in the domain, we defined ue, u sub e at a squared and u sub o at a squared as before, we define the folding as their linear combination, and you notice the folding is defined over the domain L squared.

So if the original function was defined over L, the folded function is defined over L squared. And we have a distance preservation lemma for this folding operation. This is a surprising result, but nevertheless it's true. It says that as long as delta is less than the Johnson bound, then if u happens to be in the Reed-Solomon code, the folding of u happens to be in this compressed Reed-Solomon code for every r and f. This we already saw in the previous slide. This is trivial. The interesting fact is that if u happens to be delta far from the Reed-Solomon code, then in fact folding of u will give something that's delta far from the compressed Reed-Solomon code.

And this happens with extremely high probability. So if we start from a function that's delta far, we end up with a function that's delta far with very high probability. Now I wanted to just write down the contrapositive of the statement, which is to say that if the folded function is delta close to the compressed code, then the original function must be close to the original code. This is just a contrapositive of the original statement. And this contrapositive is not that difficult to prove. I wrote down the proof of why this is true. I'm not going to go over why this is true. I'll just tell you that the key ingredient for proving this fact is in fact the proximity gap theorem.

And this is what makes it possible to prove the distance preservation property up to the Johnson bound. Now there's an important corollary of these two facts, which is the main corollary that we will use in the analysis of FRI. And so the corollary says as follows; Let C be the original code and let C prime be the compressed code, then the corollary says that in fact folding does not decrease distance to the code. What does that mean? It means that if you give me an arbitrary function from L to F, if this function happens to be within the Johnson bound of the code, then the distance of the folding function to the compressed code is not going to be smaller than the distance of the original function from the original code, again, with very high probability.

And if the word happens to be above the Johnson bound, then the folded word is not going to go below the Johnson bound, with very high probability. You can try to prove this corollary based on the lemma that we just stated. It's actually a fairly simple argument, but I'll leave it to you to think about that. But this is the main corollary that we will use in analyzing the FRI IOPP. Okay. So now, just like we have 2-way folding, we can also do a 4-way folding, right? The way 4-way folding works is instead of using a and minus a, we use a fourth root of unity. In other words, we need to use a square root of negative 1, which of course we'll denote by i.

And the way 4-way folding works is as follows. We are given a function u from L to F, and we're going to define its folding by defining four auxiliary functions, u0, U1, U2, U3, u0 basically will fish out all the monomials whose degree is divisible by 4, u1 will fish out all the monomials whose degree is 1 mod 4, u2 will be monomials whose degree is 2 mod 4, and so on and so forth. And the way u0, u1, u2 and u3 are defined is as follows. Basically, we're going to evaluate u at 4 points, i, ia, i squared a, and i cubed a.

We're going to apply this matrix which we'll discuss in just a second, and that's going to define for us what u0 will be at a to the 4th, u1 at a to the 4th, and so on and so forth. And if you think about this for just a little bit, you'll see that in fact u0, u1, u2 and u3 do what I just said. They fish out the different monomials depending on the degree of the monomial, modulo 4, all the ones divisible by 4 will go into u0, all the ones that are 1 mod 4 will go into u1, and so on and so forth. Now, interestingly, you might recognize this matrix.

This matrix is just a degree-4 Fourier transform matrix. And so once the function u is evaluated at four points, we can evaluate u0, u1, u2 and u3, simply by applying this degree-4 Fourier transform. And then we define the 4-way folding of u, which I'll denote by u sub 4fold, simply as a linear combination of u0, u1, u 2 u3 using r as the linear combination coefficient. And again, remember this u4fold is defined only on L to the 4th. So evaluating u4fold at some point in L to the 4th requires evaluating u of x at four points in L. And the fact is that the same distance preservation corollary holds for u4fold as well.

So if u happens to be a codeword in the Reed-Solomon code, u4fold will be a codeword in a Reed-Solomon code of degree d over 4. And if u happens to be delta far from a Reed-Solomon codeword, then so will u4fold. And we can keep going. We can define 8-way folding. This is going to require an 8th root of unity or even a higher degree folding, in particular, we can define a 2 to the w folding for whatever w we want, as long as we have a 2 to the w root of unity in our finite field. So given a map from L to F, we can define its 2 to the w folding the same way we defined before.

This basically will require a degree 2 to the w FFT, and evaluating this folded function at the point b will require evaluating u at 2 to the w points. And again, the same distance preservation corollary will hold also for the 2 to the w fold. So to summarize what we saw so far in this segment for linear code C, and some word u, the set of codewords that are delta close to u is small as long as delta is below the Johnson bound. This played a critical role in all our distance preservation lemmas and even in our compilers from Poly-IOPs to IOPs.

Summary of Part 1

The way we compiled a Poly-IOP to an IOP is, basically, the prover commits to a polynomial f by sending its encoding to the verifier. We evaluate this polynomial f using a Reed-Solomon IOPP on the quotient word, and we use an out-of-domain evaluation to commit P to a unique polynomial in the List of polynomials that are delta close to the sent word u. And finally we talked about folding. The main property that we're going to use is that when we take a function from L to F, and we fold it into a function from L squared to F, we showed that this is a distance preserving map, and we're going to use this in a critical way to build FRI.

And so now that we've built all this machinery, I think we all need a break. And we're going to put all this machinery to use in part 2, where we actually build FRI and its variants, as well as other IOPPs for other codes. Okay? So we'll see you in part 2.