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

Transcript

Part.1 review: RS-IOPP & Folding

Hello everyone. And welcome back to the second part of our lecture on FRI and proximity proofs. In this segment, we are going to use the machinery that we developed in part 1 to present FRI and its analysis. We will also look at some new variants of FRI and proximity proofs. First, let's review the goal of FRI. So, as we said, FRI is a Reed-Solomon IOP of Proximity. Let me quickly remind you what that means. So we fix a Reed-Solomon code with distance d and domain L. We have a particular function u0 from our domain to the finite field, and we have some parameter delta. A Reed-Solomon IOP of Proximity, then, is a proof system between a prover and a verifier, where the prover is given access to the function u0.

The verifier, of course, is only given oracle access to the function u0, and, of course, it knows what the code is. The goal is that if u0, in fact, is a codeword in the Reed-Solomon code, then the verifier will accept its interaction with the honest prover with probability 1. However, if u0 is delta far from the Reed-Solomon code, then the verifier will output reject with very high probability. And as usual, we don't really care what happens when u0 is between these two cases. We only want to make sure that when u0 is delta far, the verifier will reject. So if the verifier accepts, then we know that u0 must be delta close to the Reed-Solomon code, with high probability.

And why is a Reed-Solomon proof of proximity needed? Well, we saw in part one that this is actually the key tool that enables us to compile a Poly-IOP into an IOP, and then an IOP can be compiled into a SNARK using the BCS compiler. I also want to remind you that from now on, we're always going to assume that our domain is actually a set of nth roots of unity, where n is a power of 2, and we're also going to assume that the degree bound on the Reed-Solomon codewords is also a power of 2. But the main thing to remember is that our domain L is made up of all the nth root of unity in the finite field, where n is some power of 2. Now I'm going to denote by L squared the result of squaring all the elements in the domain,

and because n is a power of 2, we know that squaring is a 2 to 1 map, in particular, both a and minus a will be mapped to the same a squared, and as a result, the size of L squared is actually half the size of L. And since we use n to denote the size of L, the size of L squared is really n over 2. And similarly, if we look at 4th powers of L, the size of L to the 4th is going to be 1/4th the size of L, and so on and so forth. Now, in part 1, we also defined what it means to fold a word from the domain to the finite field. In particular, given a function u from L to F and some random value r, we can define u sub e and u sub o as functions from L squared to F,

and we define them formally as I wrote over here. So, u sub e is just defined as the sum divided by 2, u sub o is defined as this difference divided by 2a. And just to remind you, the intuition for what u sub e and u sub o are is, if u happens to be a Reed-Solomon codeword from some polynomial f, then u sub e is the codeword that corresponds to all the monomials in the polynomial of even degree, and u sub o corresponds to the codeword derived from all the monomials in the polynomial of odd degree. So that's the intuition for what u sub e and u sub o are, but formally they're defined as we just defined them over here.

One thing that's worth pointing out is because there's a division by 2 here, in both the definition of u sub e and u sub O, this folding operation is only defined when the characteristics of the finite field is not 2. In other words, we cannot apply folding to binary finite fields. We have to assume the fields are defined over a prime that's greater than 2. So once we have u sub e and u sub o, we define the folding of u, which is simply the linear combination of u sub e and u sub o, using the randomizer r. And what's important to remember is that, this folded function now is a function from L squared to the finite field. So its domain now is half the size of the original domain.

And we said in part 1 that we can actually define higher degree foldings where we don't just fold 2-ways, we might fold 4-ways or 8-ways and so on. And 8-way folding would be done, for example, using an 8th root of unity, and then U sub fold would be a combination of eight functions as opposed to just two functions. And evaluating those eight functions would require an 8-way FFT. But in the case of a 2-way fold, I want to remind you that evaluating the folded function at the point b can be done by evaluating the original function at the point square root of b and minus square root of b. So with two evaluations, we can get both u sub e and u sub o, and that allows us to evaluate the folded function.

Now, again, in part 1, we discussed this very important corollary that says that folding does not decrease the distance to the code with high probability. So again, let C be the Reed-Solomon code over domain L with degree d, and let C prime be the compressed code over domain L squared and degree d over 2. You notice both C and C prime have the same rate, but C prime is defined over a domain that's half the size. Now, the corollary says if we start from some function u from L to F, and it so happens that the distance of the function U to the code is less than the Johnson bound of the code, then in fact, with very high probability over the choice of r, the distance from the folded word to the compressed code is at least as big as the distance of

the original word to the original code. In other words, folding does not reduce the distance to the compressed code relative to the distance to the original code. Now, if the original function we were given is actually beyond the Johnson bound, then we can only make a weaker statement. But the statement would say that folding does not push us below the Johnson bound. If we start above the Johnson bound, we'll stay above the Johnson bound. And as we'll see, that's actually good enough for our applications. Okay. So given this quick review of what we saw in part 1, now we can actually dive into how FRI actually works.

How FRI works

Remember, FRI is this IOP of Proximity for Reed-Solomon codes. And so let's see how it works. The protocol itself was actually quite simple. So again, we have a code C with domain L and degree d. We've given some function u0 from L to F. And basically we want to build a protocol that if u0 is delta far from the code, then then the verifier will reject with high probability, while making as few queries as possible to the oracles sent by the prover. And again, I want to remind you, the prover is given the function u0 in the clear, while the verifier only has oracle access to the function u0.

↳ FRI phase 1: Commit phase

So FRI actually runs in two phases. The first phase is called the commit phase, the second phase is called the query phase, and the commit phase works as follows. It's actually as simple as can be. Basically, what happens is the verifier sends a random r1 and the honest prover will actually compute the fold of u0 relative to r1 and send back this folded function u1 to the verifier. Again, we can represent the folded function by its evaluations on L squared, so, really what the prover sends back to the verifier is a string whose length is the size of the domain L squared.

Now a dishonest prover, of course, will also send a function from L squared to F. But of course, for a dishonest proverbial, this function could be an arbitrarily malicious function. Okay. Then we just iterate this process. So then the verifier sends another r2, the honest prover will fold again, and we'll send another function to the verifier u2 now on the domain L to the 4th, which is 1/4th the size of the original domain, and this continues again and again for t rounds. Eventually the verifier will sample rt, the honest prover will fold one last time, and it will send the result back to the verifier. Okay. And I want to stress that actually this final word ut, is over a very small domain, since we did t rounds, the final domain is L to the power of 2 to the t, which is basically the original

domain divided by 2 to the t. So if t is around the log of the original domain, then this is really just a constant. And then we might as well have the prover send ut explicitly to the verifier. So that's the end of the commit phase. And so really at the end of the commit phase, what the verifier has is oracles to the original u0 as well as oracles to u1, u2 up to ut. So you can see here all the oracles that the verifier has. It can query for cells of those oracles. And then of course, it also has all the randomizers, and finally, I'm going to say that it also has the final function ut given to it explicitly, because this function is small enough that we can actually give it to the verifier explicitly.

↳ FRI phase 2: Query phase

Now, I want to remind you that after we apply the BCS compiler, what this translates to is that the prover is sending Merkle commitments to these oracles and the verifier can then ask for openings of cells of these Merkle commitments to do its job. Okay. So what do we do in the query phase? The verifier just needs to verify that each ui really is a folding of ui minus 1, folded using the randomness ri that the verifier sent. So how do we verify that these two functions are the same? What we're going to do is we're just going to spot check.

We're going to evaluate them at a few random points and make sure that they're the same in those points. If they ever differ at any of the spot checks, the verifier will reject the entire interaction. And if they're the same everywhere, then the verifier will accept. Okay. So by spot checking, the verifier has some confidence that the folding was actually done correctly. And finally the verifier will output, yes, well, except if the final word ut, actually is in the super compressed final code. Okay. So in the query phase, all the verifier is checking is that all the foldings were done correctly, and that the final word is in the super compressed code.

In fact, the number of rounds t that FRI runs for is chosen such that the resulting word, ut, is sufficiently small to be sent explicitly to the verifier. Yeah. So FRI terminate when ut is short enough to be sent explicitly. So we'll see in just a little bit how the spot checks work more precisely, but the first question you should ask is why is this framework even likely to be sound? Why is this a valid IOP of proximity? So let's see. So first of all, why is it complete? So let's say that u0 really is a codeword in the Reed-Solomon code, the honest prover, what it will do is it will honestly fold all these words over and over again.

And then if u0 is a codeword, then u1 will be a codeword, u2 will be a codeword, and ut will be a codeword. So all the spot checks will pass, and the verifier will accept the resulting interaction. Now, the more interesting case is what happens if u0 is delta far away from the code. In that case, we're going to rely on our corollary with respect to folding, right? So the intuition is if u0 happens to be delta far from the original code, because folding preserves distances, that means that u1 is about delta far from the compressed code, and U2 will be delta far from its compressed code all the way to ut being roughly delta far from the super compressed code.

I put this in quotes, because they're not exactly delta far, but because distances are more or less preserved, the final codeword will in fact be far from the super compressed code, and then the verifier will reject. So really, the only opportunity to cheat is by trying to mess with these spot checks. Basically, it wants ui to not be the folding of ui minus one, and nevertheless it wants these spot checks to all succeed. Okay? SO that's what a malicious prover is trying to do. And we'll see why spot checking prevents that in just a minute. So let's first of all look at how to do these spots checks.

↳ How to spot check: Method 1

You notice the prover here just went away, the only thing the verifier has is access to these oracles. So the first thing that comes to mind is what I call Method 1, which is just to try random spots and check whether the folding was done correctly at those spots. So what we'll do is, for every i from 1 to t, the verifier is going to run through the following process m times. Yeah. So what does it do? It chooses a random point s. It queries ui minus 1 at both s and at minus s, and it queries ui at s squared. Now, given ui minus 1 at s and at minus S, we know that we can compute the correct folding of ui minus 1 at s squared, right?

And we even wrote down what the formula is here. This z is simply computed by this simple formula here, and that computes the correct folding of ui minus 1 at the point s squared. And then, we can just compare and see if z is equal to ui s squared. And if the verifier ever encounters a spot check that doesn't verify, the verifier rejects the entire proof. So what we're doing here is choosing m random points. We're checking that the folding was done correctly by opening two points inside of ui minus 1 and comparing that to the corresponding point inside of ui, and if any of those checks fail, we abort and reject.

Yeah. And of course, we do this for each and every one of the oracles. So this process is repeated m times per oracle, and we do this for all t oracles. It's easiest to see this in a picture. So imagine we set m to be 2. So we spot check at two random points. So here you see the oracles that we were given. This is the original function u0. u1 has half the domain. u2 has half the domain of that. u3 has half the domain of that, and so on. Every time we fold, the domain shrinks by a factor of 2. And so how does spot checking work?

We choose two random places in u1. We open the corresponding points inside of u0, we compute the correct folding and we compare those to the points that we opened inside of u1. We do that using the formula that lets us compute the correct folding of u0. Now, one thing to notice is that in this process, the prover always needs to open s and minus s of u0 in order to evaluate the corresponding point in the folding of u0. What that means is that when we're creating the Merkle commitment to u0, we might as well put s and minus s in the same leaf of the Merkle tree.

That way we only have to provide one Merkle proof to prove that both u0 of s and u0 of minus s match the commitment to u0. So with one verifier query, the verifier is able to open both s and minus s. So this is why I grouped all these guys together, because we always commit in pairs. For example, here we would put the value of u1 at s squared and the value of u1 at minus s squared in the same Merkle leaf and only have a Merkle tree over 4 leaves. So the spot checking procedure continues. We're going to choose two random points inside of u2.

Here, the green points are the points where we're going to do spot checking on u2. We open the corresponding points inside of u1 and we verify that those two points were computed correctly. Then we choose two random points inside of u3. Here there's not much to choose from, but in general, if u3 was bigger, you could choose two random points inside of u3, and verify that those two points were computed correctly. And again, we reject if any of those spot checks fail. So, let's see. So how many queries does the verifier need to do in order to do the spot checking? You notice that to u1, it made m queries for checking that u1 is correct, and then it made another m queries for verifying that u2 is correct.

So there were 2 red queries for verifying that u1 is correct. And there are 2 green queries Yeah. Overall, we made 2m queries into u1. Similarly, we made 2m queries into u2. Really, we made 2m queries into each one of these inner oracles, plus we made m queries into u0, and we made m queries into u3. So overall, the number of queries is 2m times t minus 1. Okay. So we made a total of 2m times t minus 1 queries into all the oracles that the prover presented to us.

So then, as we said, the question is, why is this FRI protocol sound? Why is it really an IOP of Proximity? So let's walk through the analysis. It's not very difficult. For every one of the rounds, we'll say this is the code at round i. So for i equals 0, we end up with the initial code over the domain L of degree d. And then we'll denote by eta(η) i the distance of ui to Ci. In particular, eta0 is the distance from u0 to the original code C0. Now, the theorem that proves the soundness of FRI says that as long as eta0, which is the distance of u0 from the original code C0 is less than the Johnson bound, then the verifier will accept u0 with this negligible probability.

So if we make m spot checks per round, the probability of accepting a u0 that's eta0 away from the code is going to go down exponentially in m. Hence, the further away u0 is from the code, the less likely it is that the verifier will accept u0. Okay? So the further away u0 is from the code, the more likely it is to be rejected, at least up to the Johnson bound. Now, if u0 is further away from the code than the Johnson bound, so eta0 is greater than the Johnson bound, the verifier will accept with probability 1 minus the Johnson bound to the power of m. Okay? So up until a Johnson bound, the probability that the verifier accepts goes down with the distance from the code, and beyond the Johnson bound, the

probability of accepting becomes constant but still degrades exponentially in m. I should mention this is a slightly simplified bound. There's another small correction term in this bound that I'm not going to mention here, but it exists. So why is this theorem true? It's actually not very difficult to prove, and I'm just going to show you the proof idea here. So let's prove the case where the distance from u0 to the code is less than the Johnson bound. To do that, we're going to rely heavily on our corollary that folding does not decrease the distance to the code, and in fact, for simplicity, I'm going to assume that the folded word distance is always going to be greater than the original word distance for all ri's.

Now, of course, in reality we know this only holds with high probability over ri, but for simplicity, let's assume that it holds for all ri. The reason for the additional error term in the theorem that we ignored exactly comes from the fact that this inequality only holds with high probability but here, we're just going to assume that it always holds for all ri. Okay. So then we're asking what is the probability that the verifier will accept u0. It made independent spot checks in each round, so it better be that all those spot checks pass, and since all those spot checks are independent of one another, then the probability that the verifier accepts is simply the product of not rejecting in round i.

Now again, let's assume that m is equal to 1, so we only make a single spot check, for simplicity, the argument generalizes very easily for higher values of m, but let's for now assume m is equal to 1. So what's the probability that the verifier did not reject in round i? If it only made one spot check, how likely is it to catch a cheating prover? The answer is really simple in that we just look at the Hamming distance between the ui that the prover sent, and and the folded ui minus 1, which is the correct thing the prover should have sent, and whatever the Hamming distance between those two are is exactly the probability that a single spot check will catch the cheating prover.

If the prover is honest and ui really is the folding of ui minus 1, then the verifier will always accept, because all the spot checks will agree. But let's say that ui is different from the folding of ui minus 1 at half the coordinates, then a single spot check will detect that exactly with probability 1/2. This is why Hamming distance plays such an important role here, because the Hamming distance really measures the likelihood that a spot check will detect a cheating prover. Once we establish this fact, the rest of the proof is just some algebraic manipulations that I wrote here, but I'm going to leave to you.

I'll just mention that this inequality here that everything hinges on is used in one transition in the proof. And then finally at the end, the probability that a verifier accepts is at most 1 minus eta0 over 2. So I find this analysis really elegant because again, it shows the further away u0 is from the code, the more likely these spot checks are going to detect a cheating prover, and as a result, the higher the likelihood that the verifier will reject. Yeah. And this is captured very nicely in this transition here from one expression to the other, really shows why the success of spot checking depends on the Hamming distance between the words that are being checked.

But what I just showed you actually is not what FRI does. There's another way to do spot checking. And that's actually what FRI does, which is a little bit more efficient than what I just showed you, although introduces some complications later on. So what FRI actually does is not independent spot checks, but rather it does correlated spot checks between the rounds of the protocol. The way FRI actually does spot checking is it chooses a random point s in L, and then it just keeps squaring this point over and over again. It goes from s to s squared to s to the 4th to s to the 8th. Rather than choosing random spot checks at every iteration, it just chooses a single random value in L and then uses this single value for all the spot checks throughout the iterations.

↳ How to spot check: Method 2 (the FRI method)

And then if it needs to do two spot checks, it will do this process twice. It will choose s1 at random in L, and then it will choose s2 at random in L, and then square s1 over and over again, square s2 over and over again, and do these correlated checks across the iterations. So why is this correlated spot checking method that FRI uses, better than the decorrelated spot checking method that Method 1 did? If you think about this for a second, in this case we are spot checking s squared using s and minus s. But now when we want to spot check s to the 4th, we already opened minus s and s squared, so we don't have to open another random point.

So the verifier only has to query for s to the 4th of u2, and already use the values that it has from the previous spot check to verify that this s to the 4th is correct. And similarly, when we go to the next spot check, when it needs to spot check s to the 8th, it already has the values of u2 at s to the 4th and minus s to the 4th, and so it can quite easily verify that u3 at s to the 8th is correct, and so on and so forth. So now the total number of queries to the oracles, rather than being 2 times m minus t, is only m times t, right? The verifier only does m queries per round, as opposed to 2m queries per round in using Method 1.

So here I spelled out the FRI spot checking method more precisely. It samples a random s in the domain. It opens u0 at s and minus s. And now what it will do is it will basically keep on squaring this s over and over again. It will compute the correct folding value from the previously opened points. And then we'll query the ith oracle again at s and minus s and compare whether the results are the same. Yeah. The point is again, for every iteration, now we only make one query to the oracles. And remember again, the value of s and minus s are stored together in a single leaf of the Merkle tree.

So opening both of them counts as only one query to the oracle. So you should be wondering, why is this FRI method for doing the spot checks sound? Now, we're not using random points to do the spot checks, we're using correlated points to do the spot checks. So why is this going to detect a cheating prover? And it turns out you can actually quite easily argue the same way that the probability that the verifier accepts also decreases as the distance of u0 from the code increases. Okay. I wrote down the proof here. You can go over it if you're interested. And if you want to see the actual write up of it, it appears in this paper.

↳ Comparing spot check methods

Okay. So let's just compare again the two methods. When the distance from u0 to the code is below the Johnson bound, with decorrelated queries, the probability that a verifier accepts is 1 minus half eta. With correlated queries, oddly we get a better bound, it's 1 minus eta, which is a lower probability for the verifier accepting, which means that this is a better bounce. And not only is the FRI method more efficient, it turns out it actually also gives a better soundness bound than the decorrelated method, which we called Method 1. The benefit of Method 1 is that to obtain a SNARK using the BCS'16 compiler, we have to argue that the protocol is round-by-round sound.

It turns out with Method 1, where we have independent spot checks, it's quite easy to prove round-by-round soundness. With the FRI method because the spot checks are correlated, the proof is actually a little bit messy and it's harder to prove round-by-round soundness, it was worked out in this paper, but you see, this was only done in 2023. Okay. So Method 1 is less efficient and slightly has lower soundness, but its benefit is that its round-by-round soundness is much easier to argue. So the next question is how many spot checks do we actually need to do? So what is the value of m that we need for soundness of the FRI protocol?

So remember, we want to make sure that if u0 is delta far from the original code, the verifier will reject with high probability. Typically, what we mean by that is that the probability that the verifier accepts u0 is less than 1 over 2 to the 128. So if delta is below the Johnson bound, we know that when u0 is delta far from the code, the verifier will accept u0 with probability at most 1 minus delta to the m. That's what we just proved using the FRI method. So the number of spot checks m that we need to do is has to satisfy that 1 minus delta to the m is less than 1 over 2 to the 128. Right?

This will guarantee that the verifier accepts with probability at most 1 over 2 to the 128, which means that the number of spot checks needs to be greater than this expression over here, and here, I plotted it for you. You can see that the larger delta is, the smaller m becomes. For example, when delta is 1/2, then the log of 1 minus delta is minus 1, and then m is going to be 128, and we need to do 128 spot checks per round of FRI. Remember, every spot check requires a Merkle proof. So we would need 128 Merkle proofs per round of FRI.

But the key point I want to get across is first of all, the bigger delta is, the smaller m needs to be, and the smaller m is, the fewer spot checks we need to do, which means the fewer Merkle proofs the prover has to provide, and as a result, the shorter the proof becomes and of course, the faster the verifier. So this is why we want to use the largest delta possible, so that the number of spot checks is as small as possible, so that we end up with short proofs and a fast verifier. Okay. So what's the largest delta we can use? For various reasons that we developed in part 1, the largest delta we can use is something that's almost as big as a Johnson bound, namely 1 minus square root of the rate of the code.

Okay? So that's the delta that we're going to use. And what this says is the lower the rate of the code is, the larger delta max becomes. So let's look at two examples. Suppose the rate of the code is 1/2 versus the rate of the code is 1 /4. So first of all, the Johnson bound for the case of 1/2 is 0.29. The Johnson bound for 1/4 is 0.5. Yeah. The Johnson bound is much bigger for a 1/4 rate code than it is for a 1/2 code. The benefit of a 1/2 code is that the domain is much smaller, right? The domain is going to be half the size compared to the domain when the rate is 1/4. Okay. So now we get an interesting trade-off.

So first of all, when we use a lower rate code, delta max is larger, and as a result m is smaller, and as a result we get a shorter proof. When we use Rho equals 1/2, delta max is a little bit smaller, as a result m is larger and we end up with a longer proof. Okay. So the lower the rate of the code is, the shorter the proof becomes. However, the lower the rate of the code is, the more the prover has to commit. Now, it has to commit to words of length 4d, where here the prover has to commit only to words of length 2d, where, remember d is the degree of the polynomial that we're trying to commit to.

So a higher rate code means shorter codewords, which means less work for the prover. And so this is the trade-off that we have when it comes to choosing the rate of the code. Do we want to optimize for shorter proofs, or do we want to optimize for prover work? And I'll tell you, for example, that Plonky3 uses codes of rate 1/2. That's the sweet spot that they chose between prover work and proof length. The last point I want to make about the basic FRI is this question about security. So far we said that we choose m so that an invalid u0, namely, a u0 that's far from the code is less than 2 to the minus 128.

Now what does that mean? That means that if the adversary runs FRI over and over and over again 2 to the 128 times, every time it will choose, let's say, a different u1 and a different u2, so it's a different instantiation of the protocol every time, the prover will just try this over and over and over again until eventually it will get favorable queries. And we know that because the probability of rejection is 2 to the minus 128, if the adversary runs FRI in its head 2 to the 128 times, it will find some run of the protocol where it gets favorable queries despite u0 being invalid with probability about 1/2.

So trying the protocol 2 to the 128 times will allow the prover to create a false proof with about probability 1/2. That's okay, because running the protocol 2 to the 128 times is beyond what we can do with our current computing power. So this is fine. However, what if the prover only runs FRI 2 to the 80 times? Now, it will be able to find some run of the protocol where it gets favorable queries and therefore forge a proof with probability 2 to the minus 48. The soundness proof shows is that after 2 to the 80 runs, the probability of forging a proof is about 2 to the minus 48, which is a very small number.

Yes. Generally this is such a small probability that we don't actually worry about this. But what this says is really, you shouldn't be messing with the security balance. For example, if you used 80 bits of security, that means that an adversary that can run for 2 to the 80 times will be able to forge a proof with probability 1/2, even if you use 100 bits of security, an adversary that will run in 2 to the 80 time will be able to forge a proof with probability about one in a million, which is not great. So even though in practice people often use 100 bits of security to reduce the prover work and reduce the proof size, in reality it would be safest to use at least 120 bits of security, if not 128.

Four examples of FRI variants

Okay. So this is what I wanted to say about the FRI protocol itself. The next thing we want to talk about is a couple of variants of FRI. Particularly, I want to talk about four variants very briefly. These are very nice ideas, and so I hope you'll get excited by these ideas and maybe you'll come up with your own FRI variants that perform even better. So I listed the four variants I'm going to go through, and so let's get started. The first point I want to make is that even though the basic FRI protocol uses 2-way folding, in practice, it makes sense to use a higher-order folding, and in fact, all the FRI implementations use higher-order folding.

↳ Higher-order folding

So let me explain what I mean by this. So, in the original FRI protocol, if we wanted to shrink the domain size to L to the 8th, which is 1/8 the size of the original domain, we would have to do three 2-way foldings, as I listed here. And then for each spot check, I listed all the points that we would have to open. However, in part 1, we talked about higher-order foldings like a 4-way fold or an 8-way fold, maybe even a 16-way fold. The way this would work is given the original word u0, the honest prover will compute an 8-way fold of u0 and send u3 directly to the verifier, skipping u1 and u2.

Now how do we spot check this u3? The way the verifier would spot check this u3 is it would choose a random point s and then it would ask the prover to open u0 at all 8th roots of s to the 8th. Yeah. And there are eight of those 8th roots. They're simply s times all the 8h roots of unity. Okay. So the verifier would ask u0 to be opened at these eight points, and then to compute the correct folding of u0, it would need to do a degree 8 FFT. Right? So this is basically multiplying these 8 points by an 8 by 8 FFT matrix, which is fairly efficient to do.

And then it would get the correct folding of u0 at the point s to the 8. It would then ask the prover to open u3 at the point s to the 8. It would check that u3 at the point s to the 8 is in fact the correct value. So that's how we would spot check an 8-way folding. So let's compare the two methods. So first of all, since we skipped over u1 and u3, it means the protocol now only has log base 8 rounds, which is 1/3 of the rounds of the original protocol. Fewer rounds means this prover has to send fewer Merkle commitments.

Also, the prover has to compute 1/3 as many Merkle commitments, so it's less work for the prover, and also it's a shorter proof. However, if we just count the number of points that the verifier needed, you notice here it needs 2 from this level, 2 from this level, and 2 from this level. So 6 points overall. So it looks like the verifier needs to make 6 queries into the oracles u0, u1 and u2, whereas on this side, it looks like the verifier has to make 8 queries into u0. So this seems worse. 8 queries seems worse than 6 queries.

So it looks like we actually made the proof worse, but in reality we didn't, because what we do is we place all of these 8th roots of s to the 8th into a single Merkle leaf. And as a result, with 1 query, we can open all 8 of them at once. So if we do this leaf compression method, you'll notice that on the 2-way folding side, we have to make three Merkle proofs, namely for this pair and then for this pair. So there's three Merkle proofs overall, whereas on this side the prover only has to produce one Merkle Proof, namely for the entire coset of 8 values.

So this is much better. First of all, the prover has to commit to 1/3 as many oracles, and second of all, for every spot check, the prover is to provide only one Merkle proof, whereas in the original FRI protocol the prover would have had to provide three Merkle proofs. So this is why higher-order foldings make the protocol more efficient. The one downside is we do have to provide all these field elements in the proof, in this case it's 8 field elements. If we go to even higher-order, like 16 or 32-way folding, we would have to provide 32 elements in the proof, whereas on this side we don't have to provide as many field elements in the proof.

So we can't push this too high. But in fact, an 8-way fold, or even a 16 or a 32-way fold works quite well in practice, and that's actually what people use. So in practice, actually 2-way folding is not used as much. Okay. So that's the first variant using higher-order folding. The second variant I want to talk about is batch FRI. Now, I hope you remember that in part 1 we talked about how to batch proximity proofs when we have multiple codewords all for the same code. In practice, what the prover actually has is a bunch of functions defined over domains of different sizes.

↳ Batch FRI for varying degrees

But all of these functions are encoded using the same rate, for example rate 1/2. So these functions encode polynomials of different degrees. So the goal of batch FRI is to reject if any of these uj's is delta far from their respective codes. And again, I want to point out these are defined over different domains using different degrees. So we could run FRI separately for each one of these functions, but that would be quite inefficient. Our goal is actually to test all of them as a batch all at once. So again, I want to present two methods to do it. So here we have our examples, u1 to u4.

You can see they have varying domains, but they all have the same rate. So the degree of the corresponding codes actually match the size of the domain. So for example, u2 is defined over a domain that's 1/4 the size of the domain of u1. And indeed the degree of d2 is 1/4 the degree of d1. Okay? So again, the prover is trying to convince the verifier that all these four functions are delta close to their respective codes. Okay. So in method number one, what the honest prover will do is it will interpolate all these polynomials to the maximum degree. Yeah.

So just uses a polynomial interpolation and pads them all so that they're all defined over the same domain, Lmax, which happens to be the union of all the domains. But the degrees are still quite different, so we can't directly batch them. Instead, what the honest prover will do is it will combine them using a linear combination, but as part of doing the linear combination, it will also increase the degrees so that all the degrees match. So I wrote here the expression of how to do the linear combination. I don't think I want to spend too much time on this, but basically what's happening here is we're taking a linear combination of these functions multiplied by an appropriate power to make it so that they all have the same degrees.

I wrote down an example of how this process works here, and you can see that all we're doing here is we're taking a random linear combination defined by r, yeah? And what we're combining is shifts of these functions. Yes. So u1 here gets shifted by x squared, u2 gets shifted by x, and u3 is not shifted at all, and that basically ensures that their degrees line up and they all have degree 5. If you're interested in how this shifting works, you can look at the slide more carefully. But again, the idea is to use a random linear combination to combine all these functions into a single function.

But when we do the random linear combination, we appropriately shift the degree of all these polynomials so they all have the same degree. And you can prove that this specific transformation is in fact a distance preserving transformation. So if all of them are in their respective Reed-Solomon codes, then the combined word will be in its respective Reed-Solomon code. And in the dishonest case, if some uj is delta far from its Reed-Solomon code, then the combined word will also be far from its Reed-Solomon code with high probability over the choice of r. And interestingly, the proof of this lemma is quite cute.

Again, it falls directly from the Reed-Solomon proximity gap theorem just to show you how important that theorem is in this area. And now, once the prover has built v sub r, basically the prover and verifier can run a Reed-Solomon IOP of Proximity to prove that vr is close to its respective code, and that will prove that all the uj's are close to their respective codes. So this is what we call Method 1 for batching FRI proofs. There's another method for doing it called pipelining. And this method actually avoids all padding or interpolation. It's a lot simpler.

So let's imagine we're trying to do a proximity proof for u1, u2 and u3, where it so happens that the degree of u2 is half the degree of u1, and the degree of u3 is half the degree of u2. Now, what we're going to do is we're going to fold these polynomials into the steps of FRI itself. So remember, the commit phase of FRI starts by the verifier sending a random r1. What the honest prover will do now is it will fold u1 just as before, but in addition to combining u1 even and u1 odd, it will also fold u2 into this combination. So w1 really is a linear combination of both the folding of u1 and u2.

And because d2 is equal to d1 over 2, all of these polynomials have degree d1 over 2. So we're folding polynomials of equal degree. And then we're going to keep doing this again and again. So again, in the next round, the verifier sends a random r2 and the prover will fold u3 into this folding of w1. Yes. So batch FRI in this case is actually being done by directly folding the different functions into the different steps of the FRI protocol. And again, the proximity gap theorem will show that this is in fact a valid bash proximity proof for all of u1, u2 and u3.

So this is all I wanted to say about batch FRI. I should probably mention that Plonky3 actually uses this method for doing batch FRI. The third variant of FRI that I wanted to talk about is this trick called grinding to reduce the number of spot checks, and as a result, it allows us to reduce the size of the proof. So again, let's review how FRI works. The prover basically sends functions u1, u2, u3 over a smaller and smaller domain, but really what the prover is actually sending is Merkle commitments to those functions. And then in the query phase, the prover opens these functions so that the verifier can do its spot checks on all these Merkle commitments.

↳ Reduce proof size by grinding

Now, as we keep on saying, the way to reduce the length of the proof is to reduce the number of spot checks m. The problem is that if we drop m below the bound that we just computed, then that would allow a malicious prover to try lots lots and lots of Merkle commits until it finds one that has a favorable set of queries, which will allow the prover to create a proof even when u0 is far away from the code. So in other words, the prover would be creating a proof for a false statement. So we can't reduce M below our computed bound. So grinding is a trick that allows us to reduce the size of m and therefore shrink the proof without actually harming security.

So the idea is to introduce another phase between the commit phase and the query phase. This phase is called the grinding phase, where the point is, the prover has to find a grinding element G such that when you hash G with all the Merkle commitments and some nonce that's provided from the outside, you get, say, a hash value that starts with 64 zeros. Now this step is going to take the prover 2 to the 64 times for every set of Merkle commits. So every time the prover tries a certain set of Merkle commits, it has to grind to find G, and then it proceeds on to the query phase to actually generate a proof.

So an honest prover will just have to grind once to produce this G. And this is actually going to make proof generation take a little bit longer because the prover now has to find this G. But a dishonest prover would try to compute numerical commitments over and over again until it finds a set that gives it a favorable set of spot checks. But if it did that, it would have to resolve for G every time. So now every attempt would take the prover 2 to the 64 times. So that's greatly reduces the number of attempts that the prover can do in order to find a fake proof.

Now, I did want to mention that this nonce is important. The nonce is there to prevent the adversary from pre-computing the grinding value. And so the nonce has to be some current value. For example, it could be the head of the blockchain, which is unpredictable until the head is actually available. So the prover as a result cannot start to grind before the head of the blockchain is available. So now why does grinding help? So the adversary wants some false proof that some delta far u0 is actually close to the code. Without grinding, we set m so that the expected time to find such a proof would be at least 2 to the 128.

Now, with grinding, because every attempt is going to take the adversary time 2 to the 64, it means that we can actually set m such that the expected time to find favorable queries is only 2 to the 64. And that basically allows us to halve the number of spot checks, because now, if you remember our equation for the number of spot checks, it was 128 divided by minus log of 1 minus delta, the 128 now is replaced by 64, which means we can use only half as many spot checks and still maintain the same level of security, and this allows us to shrink the proof by about a factor of 2.

So this is the point of grinding. It's a cute trick for shrinking the size of the proof. The last variant I want to quickly go through is called STIR. This is a very recent result from 2024. And so let me explain the main idea of STIR. So, in the original FRI, as the prover commits to the different oracles, u1, u2, u3, u4, the number of spot checks per round is always the same. And also the distance that these oracles have to the corresponding code also always stays roughly the same. So, in particular, in the original FRI, what happens is the honest prover commits to a u0, which happens to be a codeword And then as we fold, the honest prover sends codewords to the verifier.

↳ STIR and WHIR variants

So in the honest case, the oracles that the prover sends to the verifier are always distance 0o from the code. In the dishonest case, let's say that the prover starts with some u0 that's delta far away from the code. And what happens in FRI is that the distances stay roughly the same. This is because folding does not decrease distance, right? So you can see that as the prover folds, the distances stay roughly the same. Because of that, the number of spot checks that we have to do per round remains the same, namely, m spot checks per round, where m was computed so that the probability of finding a false proof is 2 to the minus 128. Now, the idea behind STIR, which is cute, is this realization that we can reduce the rate of the code at every round and also increase the distance of u0 from

the code when the prover is malicious. And because now the distance from the code is going to increase from round to round, that means that the number of spot checks from round to round can actually be decreased. And as we decrease the number of spot checks, we also reduce the length of the proof. So what happens in STIR is when the Prover is honest, u0 will continue to be a codeword, namely distance 0 from the code. However, when we deal with a dishonest prover, we start from some u0 that's delta far away from the code. When we go to the second round of STIR, the rate of the code will decrease to Rho over 2.

If the rate falls by a factor of 2, that means that the Johnson bound is going to get bigger by a certain amount. And in fact what STIR will do is it will take u0 and map it to something that's almost as far as the Johnson bound from the code. So the distance from the code increased. Similarly, when we go to the next round of STIR, now the rate dropped to Rho over 4, so the Johnson bound got even bigger. And what STIR will do is it will move the point u0 to something that's even further away from the code. So what's interesting about STIR is that when the prover is honest, the distance from the code stays 0 all the time.

But when the prover is dishonest, and it's using a word that's far away from the code, the distance from the code keeps increasing from round to round. As a result, we can use a smaller and smaller number of spot checks from round to round. And again this reduces the proof size overall. So this is the main idea of STIR, but of course there are lots of complications in making this work. So let's walk through the mechanics of how STIR actually works. So here I wrote down the original word u0. It has a certain rate, d over L. Now in the first round what happens is we do say a 4-way fold.

So once we fold, we move to a domain that's 1/4 the size. But now the honest prover will interpolate the resulting polynomial into a domain that's twice as big. So this domain happens to be a coset of L squared, which means that it's only half the size of L. Yeah. So even though we did a 4-way fold, and normally we would end up with a domain that's 1/4 of L, here using interpolation, we end up with a domain that's only half the size of L And the prover will send this v0 to the verifier. And as we said, the honest prover basically will send an interpolation of the 4-way fold of u0. And now the recursive goal for the prover is to prove that v0 is delta close to this code that now has half the rate.

So the key point is because we're using a lower rate code, we can actually push v0 further away from the code and that allows us to reduce the number of spot checks overall. And, again, this gives a shorter proof. But, again, there are complications. The question is how do we spot check this v0? So as you remember, to do a spot check on v0, what we would have to do is we would have to open u0 at the 4th roots of this point, at 4 points, the 4th roots of this point, compute the folding of those 4 values and then compare it to the actual value in the cell of v0. The problem is that the 4th root of this point are not in our original domain L.

So we can't use this trick. We can only do spot checking on L to the 4th. We can't do spot checking on these other domains. So this is the second idea of STIR, that instead of doing spot checking directly by computing the folding and comparing it to cells of the committed oracle, what we'll do is we're going to use quotienting for doing these things. So quotienting here will do two things for us. It allows us to check that v0 is valid even though we can't do spot checking directly. And it's also going to increase the distance of v0 from the code when the prover is malicious. Okay. So let me give a little bit more detail in the hope that you understand at a high level how STIR actually works.

So once the prover sends v0, what the verifier will do is it will send its normal out-of-domain query, we'll call it t, in this case, this out-of-domain query forces the prover to choose one polynomial f in the list of polynomials that are close to this v0. Yeah. So the prover will send back the evaluation of the polynomial at the point t. And, again, this forces the prover to choose one polynomial from the set of all polynomials that are close to v0. Then the verifier will send its spot checkpoints in L to the 4th. Yeah. The verifier can only do spot checking over here.

So it will send its spot checks in L to the 4th, and the prover will send back the openings of this chosen polynomial at those points. And now the honest prover will actually quotient out v0 by the out-of-domain query along with all the spot checking points. Okay. So this is going to define a new u1 defined by quotienting by all these values. In particular, what the honest prover will do is it will define the vanishing polynomial and the interpolation polynomial and we will set u1 to be v0 quotiented by the interpolation and vanishing polynomial as normal. And the amazing thing is that what this does is it pushes u1 up to the Johnson bound away from the new code of rate Rho over 2.

So first of all, we're working with a code of a lower rate now. And second of all, this quotienting operation, what it does is it pushes u1 all the way to the Johnson bound of this new code. So now if u0 was delta far away from its own code, u1 will be even further away from its own code because of the lower rate. Right? So the Johnson bound is higher because of the lower rate. And quotienting basically pushes a malicious u1 all the way up to the Johnson bound away from the new code that we're dealing with. And since now the distance from the code is higher, that means we can use a smaller value of m.

Yes. So that's the idea behind STIR. For a malicious prover, the malicious word gets further and further away from the code, from round to round. That allows us to use a smaller number of spot checks for each round, and that overall shrinks the size of the proof. It turns out STIR will shrink the size of the proof by about a factor of 2 compared to the corresponding FRI proof. The downside is the prover has to work a little bit harder because it has to do interpolation and quotienting. The verifier has to work a little bit harder because it has to do quotienting on its own. So the prover and verifier are a little bit slower, but not by much.

And the other issue is that when we do batching using pipelining, STIR is a little bit harder to use because when we do batching, we are batching codewords over codes of the same rate, say rate 1/2. And this works very well with FRI, where the rate stays the same from round to round in STIR, because the rate changes from round to round. If we want to do batching using pipelining, that would require interpolation to make sure that the words that we're batching match the lower rate. And finally, I'll mention WHIR in just one point. In WHIR, the idea is we can get rid of quotienting altogether, and instead of quotienting, we can use sumcheck to do all of our spot checks at once.

So the spot checks are aggregated into a single sumcheck. As a result, there is no quotienting needed on the verifier, and as a result, the verifier is much, much faster than before. What's interesting is that there is a recent experiment that shows that because the verifier now is so fast, it's actually quite reasonable to post these proofs on-chain. On the EVM, it costs about 1.9 million gas to verify a WHIR proof. This is comparable to verifying a Groth16 proof. The difference, of course, is that this is post-quantum secure. So it's remarkable that these proofs actually now are sufficiently short and sufficiently fast to verify that the cost of pushing them on-chain is comparable to the cost of pushing a Groth16 proof on-chain.

But, of course, these proofs are post-quantum secure. WHIR has another benefit. Because of the use of sumcheck, actually it even is more general than FRI. It supports queries to multilinear polynomials, not just univariate polynomials. But how does this all work? Since this requires sumcheck and we're not talking about sumcheck today, I'm not going to explain how this works. I will say that this is using ideas from the BaseFold paper. And so in some sense WHIR is a combination of STIR and BaseFold to get the final result. Okay. So this is all I wanted to say about variants of FRI.

The future: Are there better codes than Reed-Solomon?

The last topic I want to quickly go through is basically the future of code-based SNARKs. And the main question to ask is why do we keep using the Reed-Solomon codes? Are there better codes to use that might be much better than Reed-Solomon for SNARKs? So when it comes to Reed-Solomon, actually there are three problems with the Reed-Solomon code. First of all, SNARKs that are derived from the Reed-Solomon code are not field agnostic. Remember, we always required an n-th primitive root of unity inside of the finite field where n is some large power of 2. This means we can only use fields where n divides the size of the field minus 1, and that prevents us from using primes, for example, like the ECDSA prime, which would be very beneficial for

↳ The problem with RS-based SNARKs

proving knowledge of an ECDSA signature. So whenever we use FRI, we're immediately prevented from using specific primes like the ECDSA prime or even binary fields, because 2-way folding is incompatible with binary fields. The second problem with Reed-Solomon codes is that encoding a message as a codeword requires an FFT and an FFT takes time, n log n, where n is the size of the codeword. So in particular, if n is large, let's say n is around a million, this increases the prover's work by a factor of 20 compared to using a code that did its encoding in linear time.

Yeah. So by using the Reed-Solomon code, we're paying this extra factor of 20 in work compared to codes that have linear time encoding. And finally, FRI as we currently described, is primarily used for compiling a univariate polynomial IOP into an IOP. However, in recent years we saw that multilinear polynomial IOPs where the prover sends over multilinear polynomials are much more efficient IOPs, and as a result we would like a multilinear Poly-IOP to IOP compiler, and that's more difficult to do with FRI. So the issue I'm bringing up here is that FRI gives us a commitment scheme for univariate polynomials, but it's harder to build a commitment scheme for multilinear polynomials from FRI.

So it turns out we can give a proximity proof for many other types of codes, and in fact, the FRI mechanism can be generalized to other codes as long as those codes have a nice sequence of the compositions. In particular, there's a sequence of codes C0, C1 up to Ct, such that each Ci is a linear code where the length of the code keeps on decreasing up until we get to nt, which is the shortest code of all, and nt is sufficiently small, so we can actually send the codeword in the clear to the verifier. That's the first property. And the second property we need is a distance preserving map from Ci minus 1 to Ci.

↳ FRI-like proximity proof for other linear codes

In the case of Reed-Solomon, we use folding as the distance preserving map, but other codes might have other distance preserving maps attached to them. So as long as we can take a code C and represent it as a tower of codes C0 to Ct whose lengths decrease as we move along the tower, and we have these distance preserving maps, we get an FRI-like mechanism. In addition, we also need a fast encoding algorithm that will take a message in F to the k and map it to an element in the code. This is so that when the prover needs to commit to a polynomial, it's actually quick to compute the corresponding codeword.

And finally, we need C0 to have a good minimum distance, so that we have a good bound on the number of spot checks that we need to do for each one of these maps. So as long as we can find a code that satisfies these properties, we immediately get an FRI-like proximity proof for that code. And this is something that's been done quite a bit. So for one thing, if we want a field agnostic proximity test that would work for any prime, there are lots of ways to do it. One way to do it is using what's called ECFFT. Here, we use FRI using functions over an elliptic curve where the order of the elliptic curve is divisible by n, even though the prime is not.

↳ A proximity proof for other linear codes

This allows us to run FRI over primes like the ECDSA prime. Unfortunately, this is not as fast as FRI. It's actually quite a bit slower. Another example is a paper from 2020 that gives a proximity proof for algebraic geometric codes. Here, polynomials are replaced with what are called "functions on a curve." Again, the same FRI mechanism basically can be made to work in this setting, and we get a nice proximity proof from these algebraic geometric codes. Circle Starks is another example of generalizing FRI to other codes. So in Circle Starks, we want to use a Mersenne prime.

In particular, we want to use the 11th Mersenne prime, which happens to be 2 to the 31 minus 1. The reason we like to work with Mersenne primes is that arithmetic modulo Mersenne primes is super fast. Computing a modulo reduction can be done just by one addition. It's really fast. The problem is that if you look at M11 minus 1, you get 2 to the 31 minus 2, and that's not divisible by a high power of 2. So we cannot use FRI when we work modulo M11. But if you think about it for one second, you realize M11 minus 1 is not divisible by a high power of 2, but M11 1 is divisible by a high power of 2, because that's just 2 to the 31.

So the question is there some way to run FRI using M11 plus 1 instead of M11 minus 1? And it turns out that's exactly the Circle Stark method. Basically, we're going to run FRI over what's called the projective line. And the projective line modulo M11 has M11 plus 1 points in it, and lo and behold, this is in fact divisible by a high power of 2. Now, the reason it's called a Circle Stark is because there's a classic way to represent a projective line as a circle. But I think I'm going to skip over that. The next generalization of FRI is this beautiful idea called BaseFold.

↳ BaseFold

And BaseFold defines the concept of a foldable code and generalizes FRI to any foldable code by showing that these foldable codes actually decompose into a tower of codes, as we saw three slides ago. The benefit is that we end up with a code that has a nice and efficient proximity test, but now we don't need a high power of 2. The proximity test is field agnostic. BaseFold also introduces another very important idea, which is a way to get away from quotienting. And rather than doing quotienting, we're able to do multilinear polynomial evaluations by absorbing those evaluations into a sumcheck protocol.

Since this depends on sumcheck, and we're not talking about sumcheck in this lecture, we're not going to go over this today. All I'll say is that this technique was then also adopted into WHIR. So WHIR is using the BaseFold technique for avoiding quotienting along with the STIR technique for reducing the number of spot checks overall. And it turns out there are even other codes that are very useful for building SNARKs. There are Spielman codes that were used for building Breakdown and Orion and other SNARKs like that. What's interesting about these Spielman codes is there's a very fast encoding algorithm. It's a linear time encoding algorithm, and so as a result we end up with a very fast prover.

↳ More SNARK-useful linear codes

The only downside is we end up also with very large proofs. And then there have been a couple works trying to improve it. For example, there's a work building on what are called Expand and Accumulate codes that are also field agnostic but reintroduce the n log n running time. And then there's a very recent work called Blaze based on RAA codes where we obtain a multilinear polynomial commitment. So this is appropriate for compiling multilinear Poly-IOPs into SNARKs. The scheme works over binary fields, which are great because computers are very good at arithmetic over a binary field. The code has a linear time encoder and as a result we end up with a linear time prover and a reasonably sized proof, which is still larger than what we would get from FRI, but much shorter than what

we would get from Breakdown. And again, this method is based on sumcheck, so we're not going to talk about this today. So I hope this final discussion shows you that we pretty well understand how to build good proximity proofs based on Reed-Solomon codes, including the recent improvements like STIR and WHIR and so on. When it comes to moving away from Reed-Solomon codes to more efficient and faster codes, there's still a lot more to do. And so I will leave you with this message of there's a lot more to do in the area of non Reed-Solomon based SNARKs, And I'm hoping that some of you will make important contributions in this area and I'm really looking forward to seeing that.

If you want to read more about any of the results, we discussed in these two lectures, I wrote down the list of papers to read here. These are all clickable links, so it's easy for you to get those papers and dive into them. I hope you enjoyed these lectures. Hopefully, they inspired you to use some of these SNARKs and even more so, I hope they inspired you to think about these constructions on your own, and hopefully in a future lecture I can include your papers in this reading list. So thank you all and I look forward to seeing you in a future lecture. Bye everyone.