ZK11: STIR: Reed–Solomon Proximity Testing with Fewer Queries - Gal Arnon & Giacomo Fenzi

Transcript

[Music] hi hi everyone and thank you for being here so my name is jako and today I'm here with gal and we're going to be presenting stir Rich Solon proximity testing with fewer queries this is Joint work with Alexandro kza and Alon yev so let me start to give you some motivation on why like the clicker works some motivation on why you should at some point care about the result and the object of what we're trying to improve are what I affectionately call Stark and friends and by this I mean all these protocols which end up being constructed

by combining an interactive Oracle proof with a BCS transformation so roughly this yields snarks which are secure in the random Oracle model and can be instantiated with only Ash function so with no other cryptography this has some benefits one of them is that these snarks tend to have a transparent setup so no ceremony is needed they tend to have relatively fastring they can enable like using like fields which are not tied to to public key crypto primitiv such as elliptic curves and furthermore they're post post Quantum secure in the quantum random Oracle model all of these uh all of these uh benefits made like a star and friend to

be widely deployed in Practical applications such as rollups and z kvms and of course the list that we have here is by no means exive and looking at like how some of these snarks are deployed in practice they tend to follow a very like standard recipe you usually combine a polom IOP which might be tailored to some kind of arithmetization or 1 CS plong so like and then you this polom IOP is compiled into a standard IOP and the way that usually get this gets done is that the polinomial IOP gets uh as the messages replaced by read Solomon encodings of the messages then soundness is

conditional on the verifier being able to check that these Oracle messages that being sent are actually close to low degree functions and the way in practice that this is done is by the fry protocol so this overall IOP so the combination of this Rich Solomon encoded IOP and the fry protocol then gets compil via the BS transformation to give you a stark and when you look at like the argument size and the complexity features the C of the IOP roughly like we see that the fry protocol accounts for more than 80% of the argument size in our experiments so what we aim to improve with this work is exactly this part we want to give an an improvement on

Fry let me start by giving you some backgrounds of like the objects that we have in investigation so R Solomon codes and interactive Oracle proof of proximity so R Solomon codes which we denote like this in this talk are essentially one of the most um foundational codes that are known and they're parameterized over a field an evaluation domain and some degree the way that the encoding ofon code Act is that you interpret your message as the coefficient of a low degree polinomial of degree D and then you encode by evaluating over this larger valuation domain for the purpose of this talk you can think of like this evaluation domain to be around four

times larger than the than the degree and this ratio between the degree of the polinomial and the evaluation domain size is the rate of the code in particular if the evaluation domain has is move or has got some nice features this encoding can be done relatively efficient with a fast transform where Solon code and now an IOP an IOP of proximity for it Solomon codes the idea is that you really want the verifier to be able to determine whether some function which it has Oracle access to is a read Solomon code word or if it might be like far to from it the prover and the verifier they interact with each other sending Oracle messages and at the end you want that if

this function really a Solomon code the verifier accepts while if the function is Delta far from this R Solomon code in terms of having distance the verifier will project with very high probability and the reason that we want this um we can only give this like proximity guarantee compared to like a more traditional sound this notion is that we want the verifier to make few queries to both the Oracle function and to the proof oracles and this leads this essentially would lead to a more efficient argument down the line so what is the FR protocol uh you most people might have seen it I'm going to give a very brief uh refresher so for prot is exactly an IOP proximity for

this uh for this problem so roughly you have a function that you want to test for proximity and the pro and verifier interact the verifier sends some Randomness and the prover will send you some Oracle G1 and this Oracle is supposed to be the folding of the function around the randomness and by the verifier we will see more formally what this means later on in the talk roughly you can think of like this the read the fry to be recur ly reducing the the size of the problem being tested so at each step you like sorry you continue this process recursively at each step you recursively test a claim that like the a code word belongs to a smaller code and in particular this K is

the folding Factor at each step the degree of the polinomial and the degree and the size of De valuation domain grows down by a factor of K and at the end the pro the prover just sends a witness polinomial for it and the verifier needs to perform some consistency checks which can due to the smooth structure of domain it cannot perform at the end in what is called the query phase of fry this protocol has got like quite nice properties it only has logarithmic number of rounds the proof length is linear in the size of evaluation domain and the number of queries is also suitably small you can think of in this expression that like the number of uh um queries is roughly security parameters time log D

to get the lamb bits of security and in this case we're really talking about round by round soundness which is the notion that you really need if you want to have a sound IOP when compiled with BCS transformation so this is fry how do we improve this so our like result is St which stand for shift to improve rate and is a new protocol for uh an IPP for R Solomon codes with the same rounds and proof length as fry but with significantly better queries we will compare it in the next slide more accurately but essentially you you can see that the dependency on the security parameter changes from log D to log log D and this translate to a rather larger

practical Improvement and again this is still the round by round uh security so this is the comparison so the first thing I want to stress is that stir can be used wherever fry is and I argue that you should so stir is meant to be a drop in replacement for fry so wherever you use fry you you can use Stir so it has fewer queries than fry so you can see that if you look at these par parameters like the dependency on the security parameter is better in store compared to fry and this is really where the benefits of store really shine because fewer queries when you compile means that you have to send fewer authentification paths which lead to

smaller arguments and further if you have a fewer authentification path you have less Merle paths to verify so your verifier ends up performing less ashes and ends up being faster so to give you a rough query comparison if we look at targeting 100 bits of security with fry and stir and which can be boosted by Pro proof of work in both protocols fry makes around twice as many queries as a uh a St so this is rather a you know if you p on a joke a Stark Improvement so let me talk a little bit we know we make some claims so we decided to do the sensible thing and actually

implement it so we have an implementation of of stir which is open sourc on my GitHub so we use our course as the back end we used for The Benchmark our 192 bits field and we think that our implementation is you know reasonably optimized we've implemented both fry and stir in order to make sure that the comparison was as Fair as possible and our implementation is modular over both like the choice of field the choice ofir and the mirash and I claim that at least for academic standard is also additionally well written like implementation so you know feel free to have a look around and like you know let me know if you like what you see so you know maybe this light is what

you've been waiting for what what does this translate in terms of concrete efficiency so we're pleased to say that compare okay that fry the stir achieves better argument size and verifier R complexity compared to fry on every degree rate pair that we benchmarked this Improvement ends up to being larger uh as the degree increases and the rate increases so to give you like some concrete numbers for degre to to the 24 and rate one quarter like fry proofs are on an order of 170 kilobytes while stir are around 100 kiloby while in terms of Ashes the verifier of fry will perform around 3.5 thousand of ases while s draw is down to

1.8 if we increase the degree end rate you can see that fry proof ends up being around 500 kilobytes while store are around 200 so more than a 2 Improvement there the number of Ashes also drops down from 10,000 to around 38,000 which is almost a free x Improvement we we achiev this by only paying as very modest like a very small increase in Pro time in the non bottleneck part of the of the computation so we expect that when you're using when you're using fry in in when you're using um store in practice the not the difference in time is not noticeable because essentially you will be using store in a batch contents and the cost of the initial fft will dominate compared to where story is

slightly slower you can see that the argument size is sign significantly better so it's the verifier complexity and the verifier time is for larger degree is also improved not that in particular this is also because we use the Blake free as the ash function if you use as lower Ash function the verifier time of a stir is better across all parameters so I'm going to now lead it to G who's going to give you a round down of the techniques that we use in St thank you okay so now we're going to take a look uh at the technical level of how stir works so the main idea of stir is that a code with a smaller rate so uh um

larger U uh domain U is easier to test so the smaller your rate the fewer queries intuitively you should have so uh stir Works in iterations just like fry and a stir iteration uh reduces testing proximity uh to a code with degree D to uh testing proximity of a code to degree D over K just like fry but unlike fry uh the evaluation domain uh is smaller by a factor of two instead of K so in practice this means that uh the rate uh is now uh 2 over K times the original rate so the rate has improved if K is larger than two so think of K is equal four for example then the rate

improves by a factor uh of 1/2 in every iteration so uh after every iteration the next code is actually easier to test than the previous code uh so this iteration also amplifies distance in a sense so if the function is Delta far from the from its uh code then the new function fime is going to be far from the uh its code uh from the new code except with probability 1 minus Delta to the T where this the new distance is almost maximal uh this uh square root is uh can be turned into just row Prime by some assumption just like in Fry uh and T here is the number of queries

that we have we have a different number of queries for uh for every iteration so uh the round by round soundness errors if we do this thing recursively turn out to be uh 1 minus Delta to the t0 in the first round and then in every round so in round I you have row I to the ti Bas roughly uh and because uh so if we want uh Lambda bits of security uh we have to set uh so t0 is set with regards to Delta but the every TI is set with regards to row I so since this row I uh becomes smaller and smaller This Ti becomes smaller and smaller as well and then we can improve the number of queries done uh between

each iteration so in order to understand uh how the protocol Works we're going to have to introduce a few uh techniques the first uh technique that we have is folding those of you who know how fry works this is exactly the same folding that they have you start off wanting to test a function uh a rolman code of degree D and you end up with degree D over K and the evaluation domain is also smaller by a factor of K so it looks like this you have this function f that you want to test the verifier uh samples a random field element and this defines a function uh the folding of F at at Alpha the field element that the I chose and this folding has uh two significant

properties the first is that it's local so if we want to sample the folding at some location this uh and we only have access to F then uh we can query F at K locations and do some small computation and then uh derive the folding from that so we only need F in order to compute the fold the other property is that it's distance preserving so if f is Delta far from its code then with high probability uh the folding is also going to be far Delta far okay the second technique that we need is quotienting so this is a technique to roughly uh enforce constraints on uh a function and uh also

has this property of amplifying distance so we have a function f uh which is supposed to be a polinomial we have a set a function ANS which is a list of claimed evaluations of the extension of f as a polinomial on some set s and we Define the quotient of F at ants to be F minus the low degree extension of an over the vanishing polinomial at s The Vanishing polinomial is the low degree polinomial that is zero uh the nonzero L polom that's zero on S and this has two important properties uh it's local just like uh U folding was in the sense that if you have F and you know an and S you can compute this

quotient at any location and it also has a consistency property so if you take a look at F it might not be a polinomial it might be uh Delta close to a lot of polinomial there might be a whole list of pols that it's close to and uh the property that the quotient has is that if for every polinomial in this list this uh the polinomial does not agree on the set on the with the function answer so there's at least one point where they disagree then the quotient is going to be far from uh the read solement code word so uh if if all of the functions disagree on N then this quotient thing is going to be really far the last property that we need is or the last technique that we need is out

of domain sampling and this is a technique to uh at least intuitively uh move from list decoding to Unique decoding so uh imagine theover sends you some function uh it's claimed to be a polinomial but it might be very far far from one in fact it uh you might have only a list of pols that it's close to uh just like we had we saw before uh and we want to work with only one polinomial want to enforce that it works with one polinomial so the verifier is going to choose a random field element and the prover will send a field element back and uh because this list is not very large and by the fundamental theorem of

algebra there's going to be at most one polom uh in this list that has the property that it evaluates to Beta on Alpha so basically this means that the prover has to choose a specific single polinomial uh and it sort of commits to using that polinomial uh in in the future and the way that we enforce this uh sort of commitment uh is by quotienting on the uh uh by the point Alpha Beta so now that we have all these techniques we can build the S protocol uh so I'm going to describe one iteration we start off with the function that we want to test then the verifier is going to

choose folding Randomness and the prover will answer with a function G that is claimed to be uh equal to the extension of the folding but on L Prime which is some uh uh large some valuation domain of size L over2 size of L over two uh we're going to then uh because this thing might be close to a lot of polinomial and we want to constrain this uh the PR's actions we're going to do an outof domain sample we'll see how this affects U the protocol later uh and now we want to actually test that g really is the extension of uh the folding uh but the problem is that this L Prime is uh it's

even going to be disjoint from the F the valuation domain of the folding uh the folded function sorry um so how do we test consistency well we're going to do it with uh uh with quotienting the verifier is going to sample a bunch of locations and then uh quotient G by these locations uh in order to enforce uh consistency between the polinomial that is close to G uh and uh the folded function we're going to see exactly what this means uh in the next slide so just to reiterate the way that the uh protocol looks is you send a folding Randomness the verifier s folding

Randomness then the Prov answers with something claimed to be uh the uh extension of the folded function then we do an out of domain sample and the verifier samples a bunch of locations in the folded function queries it uh and quotients the function based on this this uh both the out of doain sample and these answers so let's have a very quick uh highle soundness analysis the claim is that if the original function is Delta far from the code then except with probability 1 minus Delta to the t fime is going to be really far from its respective code so first of all the the folding that we did at the beginning I already

claimed that this preserves distance with high probability uh and now we have the Prov send G which has a list of pols that are close to it uh and we do out of domain sampling so this uh sort of forces the pro to choose a single polinomial uh so there's a unique polinomial that agrees that has the property that uh it evaluates to y0 on x0 these These are the uh outer domain sample points then the verifier chooses a bunch of locations in the folding and then we're going to compare them to this single polinomial that that uh that the the approver committed to so uh if at

any point U we have uh the property that uh V on x i is not equal to Yi then by the quotienting property the the quotiented function which is f Prime is going to be really far from the code because the there's only one polinomial uh that uh V and it doesn't agree on this uh on at least one of the points that we're quotienting so we have this quotienting property so uh the folding we've already claimed is Delta far from the code and so because this uh polinomial is uh uh part of the code it's also Delta far from from the polinomial V and so the probability that

uh f is going to be f is close to the code is bounded by the probability that all of the points have agreement with polinomial which is at most uh 1 minus Delta to the T where T is the number of points that we chose and that that's a quick analysis of uh why stir Works uh okay so I'll conclude now uh so what did we see in this talk uh so we saw a few techniques that were used uh so folding uh quotienting and outof domain sampling and we put them all together to construct s and then we saw very quick soundness analysis and

there's a bunch of stuff that uh we haven't seen that exists in the paper so for example uh when we do this uh quotienting uh we actually mess up the degree of the polinomial and uh stir only works with uh pols of specific degrees so we actually have to correct the degree in some sense uh so we have a new way to uh do degree correction uh there's also in the paper a Honus compiler for polinomial IOP uh which is a uh Builds on a compiler that was uh not concretely efficient in a previous paper but now we have concrete efficiency and we also have uh round by round knowledge soundness for this compiler which is quite nice and uh talking about round around soundness uh

we have uh a clean analysis of round soundness for stir which I think is also we also worked very hard to make it uh be well written I I hope so uh uh this is this should be helpful for understanding it and is also very important for uh Security in the non-interactive setting uh so what's next for this uh these ideas uh um hopefully you know next time we have this Summit uh people will talk about stir with small Fields so there's the new uh Circle star work maybe it can work with stir uh maybe things with uh um smaller with for example binary Fields uh we're not sure

uh there's also questions about uh breaking the logd query barrier so there is a theoretical work that achieves log log D queries rather than log D queries but it's completely inefficient there's a question of maybe uh making that efficient somehow uh it would be very exciting if we managed to do that and uh we just want to see people use Stir as much as possible um so that's it uh thank you if you want to see the paper it's uh online on ePrint and there's also Jak's great blog post awesome great thank you guys um we do have a couple of minutes for questions

if anyone has a question you do have mics on the seats so please just raise your hand and I'll talk you through how to access that if there are no questions that's fine too Anna you've got a question just turn your mic on hello hello yes um not exactly a question but we actually just we recorded an episode of the show you guys are going to be on the show soon but I just sort of wanted to highlight something because even when we were going over it on the show folding in this context in the fry context is different from some of the other folding that we hear about and I just want to kind of double check that in a different kind of folding great okay yeah lovely one just behind

Anna as well so just turn on the button Anna if you can turn your off uh I I caught a very quick remark about poly IOP compilation what does uh what does that mean in this context what is the poly IOP uh you know fry and I assume stir is just a proximity test there's uh not a polinomial commitment scheme there unless you do extra stuff uh so did you do that extra stuff and uh just an explanation uh yeah we we did extra stuff so first of all when I say polinomial could I mean for univariate polinomial so polinomial IOP is for Univar polins uh and then we have a like a proper compiler where you give up uh

this is in the theory we don't have a like an implementation but uh where you you give a polinomial IOP where the prover sends univ polinomial and it just this compiler turns it into a proper IOP by combining it with a test so it's just a univariate scheme based on quotienting essentially yeah yeah but compared to previous compilers yeah achieves like a better soundness so the idea is that like it combine some of the tricks that you sen here to get like a better way to compile univ varat po iops into iops then you can like BCS yeah cool than great lovely thank you just turn your mic off any more

questions in here yeah cathic just turn yours on uh hi so if I were to use this for a small Fields uh I should just simply use the extension field for the challenge and then we it's the same level of soundness uh depending on which you might need to hold your mic closer to your mouth yeah so if I use small Fields then uh I I just need to use the verifier challenge with the extension fields and it's like there's no uh change if I want to use it for 64bit or 32 bit field yeah exactly so for like the if you want to use more field you can do everything as in Fry so you just sample the challenges over the extension field you'll be fine uh we believe that like you can also like apply some of the

techniques from the circle Works directly to stir like so but yes so in general like whatever you can do with fry you can usually also do with stir okay cool awesome thanks for the great talk great thank you I think we'll leave it there K if you turn your mic off that'd be great um thank you so much guys um we'll going move on thank you very much cheers thank you