ZK12: WHIR: Reed-Solomon Proximity Testing with Super-Fast Verification

Transcript

[Music] okay everyone welcome next up we have Elon from bar Elan University uh take it away okay thank you hi so first this is Joint work with my student garon and alesandro Kessa and Jak M fenzi and I'm kind of very excited to be here and this is a kind of present we this is the premier presentation of where uh last ZK Summit we presented the stir and this is kind of a new Improvement on top of that so where is Reed Solomon proximity test and it has super fast verification

and so I'm going to go slightly into technical details about that and we're also going to see benchmarks and uh yeah so let's start so first in the ZK Summit uh conference and what we what are our goals we want to construct snarks okay these are sucin non- interactive arguments of knowledge so we have approver we have a verifier the approver wants to convince the verifier that he knows a solution right he knows a witness to the to this instance and in our case the prover and verifier are going to share something's called a random Oracle as Anna discussed this morning so they both have access to this

random Oracle which they can query and get back a completely random answer and we want the proof of course to be kind of very small okay in particular much much smaller than the size of the witness itself okay so we're going to only have a random Oracle there's no other assumptions okay assumed in this talk once you have such a scheme you can replace the random Oracle with some concrete hash function okay so instantiate the random orle with a hash function and uh what you get is a snark that you can deploy in practice and the advantages of such snarks are that they have a transparent setup okay

so the only setup that they require is choosing this hash function they usually they usually are quite highly efficient so there's no public key crypto there's no elliptic curves and stuff like that there's only um hash functions and usually over small fields and stuff and so they're quite highly they're fast and they're also postquantum secure if you care about that of course today these snarks are used to secure billions of dollars in blockchain transactions I guess you know about this this is just a small subset of the companies using this stuff today okay so how do we construct hash based snarks what we do we do the following we

first construct an IOP and IOP is an interactive proof between aover and verifier where the verifier does this small number of queries to the proof these are the green locations here then you take this proof and you compile it using something called the BCS transformation okay um roughly speaking every message of the IOP you're going a mircle tree okay you're going to create a mircle tree and commit to it and then when the verifier wants to read something you're going to send the authentication path and all these long rounds of interaction you're going to use FM to compress to one message okay and the efficiency of the snark is mainly determined by the

efficiency of the IOP so the prover is roughly the same the verifier is roughly the same with additional hashes and if you have some proof lengths of length L and Q queries okay usually the proof length is kind of big this is the size of your computation let's say 2 to 24 and you have some number of queries this is going to affect the argument size at the end and the verify running time and so on okay so we want to construct more and more efficient iops okay for the relation you want to prove for i1 CS or something like that how do we construct these iops and this is the last slide before we go to steer to to we um what you do you construct these

polinomial iops okay so a polinomial IOP is just an IOP where we restrict the honest and malicious Prov to send only pols okay so they have to send pols and the verifier what can he can do he can query this polinomial you can evaluate them at any field element that he wants okay so the prover is going to send some polinomial Q then the verifier can query this PE this Q at some point x and then you have maybe some p and Q and and so on and once we have this polinomial IOP what we do we compile it to a standard IOP okay that is then later going to go to the BCS

transformation and how do we compile these polinomial iops what we do we either use a polinomial commitment scheme which is just a cryptographic way of enforcing the prover to really commit to a polinomial um but actually more generally I just want to take this slightly higher view as any compiler that takes a polinomial IOP and outputs an IOP okay so one way to do it is using a polinomial commitment scheme and then doing this function by function but any such compiler is is what we want uh and any such compiler is in particular actually a polinomial commitment schem okay um we have many examples many of the snars we know today use this uh

this blue print to construct snars and there's many examples not going to name all of them the polinomial commitment scheme that you use underneath could some could be kzg or something based on laes or or something like that or it could be something based on hash function so a hash based polinomial commitment scheme and this is going to be the focus today and I'm just giving a few example this could be fry based or steer based or a base fold based and this is the three examples I give because we're going to mainly compare to them because they're the most relevant to this work okay so the way these hash based Pol commitments can work we ask the prover

to kind of instead of sending a polinomial evaluate it at many points and then we kind of need to test what the approver do so this leads us to a result so in this work we're introduce a new polinomial commitment scheme that has a really super fast verification okay so more technically what we do I need to uh Define what the read Solomon code is so we recall what the readed Solomon code we had some finite field F okay we have some evaluation domain L and we have some parameter m m is going to be the the degree and then we're looking at the

read Solon code so these are all functions F from this domain L to the to the field okay so all evaluations of functions such that the function is univarate low degree polinomial of degree at most 2 to the m okay so m is going to be log log the degree in this example so this is the r Solon code and equivalently in this work we kind of have this dual view of the r Solon code where you can look at it as a universe polinomial or a multilinear polinomial so you can take the 2 to the m coefficients and you can view them as coefficients to a Univar polinomial okay of degree 2 to the m or a multilinear

polinomial okay that has M variables okay so we have this Duality between the two either we have M variables or just one variable with degree two to the m okay so what we do we're going to h define a constraint R Solomon code okay this is going to be very helpful for us H and this will allow us allow me to tell you exactly what we is H so a constrain read Solomon code is just a subset of the code words of read Solomon that has this additional sum constraint so there Su Check Line like constraint that you add upon it so my code now is

not on all code words okay but just a subset that satisfies some additional constraints so this W is going to be some some polinomial and sigma is some Target sum and then I'm looking at all the polinomial in the multilinear okay notation that satisfy this additional sum and this additional sum in particular is expressive enough um to express a constraint of evaluation of this polinomial F so I have F and I want to say oh but F on some point Z equals Sigma and there is a way to translate this to to such a constraint okay and this is what allows us to use we as a poal commitment

scheme okay so what is where where is an IOP and IOP of proximity for constrained read Solomon codes okay where Fry if you know fry fry is an IPP for read Solomon codes and steer is also an IPP for read Solomon code code uh where is going to be an IPP for this constrained with Solomon code okay or in other world in world of you know higher marketing world it's a polinomial commitment scheme for either univ or or multi-linear polinomial okay so it works for both um so for degree 2 to the m okay in the univ case or M variables with some

security Lambda and folding parameter 2 to the K this folding parameter is some parameter some trade of that we can play with it means that like in the fire protocol in every query you kind of read 2 to the K field elements okay the query complexity of we is this expression this is Lambda over K * log M okay and forget about this complicated expression we'll we'll see it in a second and we'll have Ben benchmarks also soon uh we kind of set K to be roughly log M and then what you get is the query complex is actually o of Lambda which is actually optimal the verifier running time The verifier running time is this query complexity well the verifier needs to do something

per query right times 2 the k + m so again 2 to the K is going to be the bigger term here and uh for every query the verifier reads two to DEC field elements this means that in terms of of field operation the verifier is actually linear in the number of field operation it reads from the proof okay what makes it makes the verifier very fast and uh not only that actually the verifier performs zero divisions okay so not divide by zero but doesn't perform any any divisions okay the alphabet is what I said you have you read two to the K kind of field elements in every query this is the round of complexity it's M over K

and the proof length is is linear okay so what does this mean how does this compare to Prior walk and what did it mean with the actual numbers okay so first let's compare the query complexity to to some prior work so base fold base fold is a multilinear polinomial commitment scheme their quer complexity is Lambda time M fry if you know the five protocol has qu complexity Lambda over K * m so Bas just just doesn't have this folding parameter built in so it's kind of fixed to one H stir stir is a uh polom scheme that we introduced last ZK Summit that

kind of improves the fry so you can see the Improvement here so the qu complexity is Lambda over K time log M instead of time M so it gains a huge Factor there and we just borrows the same query complexity as still okay so it has like the the small query complexity now in terms of the the running time base fold is actually linear in the number of queries so it's O of Q base fold okay that's good but kind of has a lot of queries H fry does this has a running time okay this is the verifi running time of O of Q fry time K * 2 to the K this makes a lot of sense because fry needs to do like this small fft of size 2 to the k for every query

that it reads and so this K to to the K is just the time of an fft of of size to to the K okay Ste has this H slightly even walls running time okay has this plus Lambda Square okay which sometimes is actually could be quite big and the the running time of our verifier is actually qwi which is the the smallest Square complexity time 2 to the k + m okay so we even shave off shave out this Factor K okay now it's really linear in the number of queries and not quasy linear okay so now benchmark implementation so

we did implement this scheme okay kind of academic level implementation not industry level implementation H we implemented using rust we use the arworks as a as a backend we took an extension field of the goldilux field I really want to thank Remco for helping us Remco from worldco for helping us with like a optimization of the of the p and verifier um what the Benchmark you're going to see today are like partially paralyzed so there's a lot of room for improvement for the P running time if you if you have a lot of CPUs and we compared it with fry and steer and base fold as a

polinomial commitment scheme so let me tell you about the the results so let's start so the we verifier typically runs in a few hundred micros seconds okay other verifiers even those that have a trusted setup kzg and other usually take several milliseconds if not more okay and we do this without like compromising or without some bad trade-off between the running time of the prover and the argument sides okay so it's like a true Improvement and not a tradeoff as an example okay as a polinomial commitment scheme for degree to 22 you can think of this as like

roughly equivalent to 4 million constraints with 100 bits of security I run this last week on my laptop I have a MacBook Air the Prov time took roughly 1 second uh the commit and open together were roughly 60 kilobytes okay and the verifier time to verify this opening was 207 microc so roughly 1 of a of a of a millisecond okay so this extremely fast verification ah sorry here's a slightly more comparison with other schemes so we have kzg here and liero and breakdown

and HX and you can see the numbers so usually these numbers are either large or a few milliseconds where where is the only one depending on parameters kind of go be below the millisec barrier okay once you have such a fast verifier can kind of think of new applications that that open or improve H so I just want to really You Know sketch two things that I think are interesting so first is on onchain verification and all of these are kind of you know this is the back of envelope computations that we did and you know to get exact numbers you have to really implement this and and see exactly how much you get but today we verify go 16

poofs okay on chain over the BN 254 curve and this takes roughly 280k gas okay uh possibly you know one future is where we use we uh to to verify this stuff over smaller fields and kind of U some estimates that we did said if you take a degree 2 to the 22 you're going to get roughly 50k uh gas okay and even if you go up to degree to to the 60 to to the 26 this should be 80k gas okay so this could be a big Improvement in the gas cost of of of very fine

PS okay H second of course is the recursive reification so if you use wear as the first step you know in a recursion and the the Second Step the p is going to run and prove the code of the verifier and uh here we did another another set of computation so here we went for 128 bits of security with degree two to the 28 so kind of a large computation then because the query the query complexity of we is small and the verifier is fast kind of what the we verifier is going to do is roughly 3.4k hashes okay this is to verify the mer hashes and if you kind of assume that

this hash is a posidon or most of it is Poseidon which is roughly 4 100 R1 CS constraints then you're going to get that the recursive circuit okay that you need to prove is of size 2 to the 20 okay so you start with a computation of size 2 to 28 okay and then you do you run one weird iteration okay and the next step you have something of size to do the 20 and then you can you know much smaller computation and everything is much faster and you can run whatever you want okay um comparison so here's a comparison to base fold I want to be fair and say

first that we are inspired by fry and base F and steer and kind of this work accumulates many ideas and new ones from all these books ER and also that uh to my best of understanding this these numbers from the bful paper are kind of not optimized in the most significant way and probably can be can be better um but okay let's see how how we compare so red is the base fold in blue we have Weir UD which is the unique decoding radius this is kind of without any conjectures and in green we have this Weir capacity bound so this is with this list decoding type

conjecture that is not the same but kind of similar to what happens in Fry and steer and all these kind of schemes um so you start with the argument size you can see that the basal argument size is kind of very big compared to both the the we unique decoding and capacity bound okay so even for quite large computations the argument size really is less than 100 kilobytes H the pver time you see so we didn't compromise in P time so the P time is roughly the same as as base fold here it's slightly better but I imagine you can also improve the bful po okay to make it better and you can also improve the wear P to make it better and so this

is kind of a competition um but for the verifier on time there's kind of you know there's not a lot to improve it's kind of a small piece of code which is usually kind of optimal and that's just what you get and uh so you can see that both the both version of rear are kind of nearly the 1 MC sometimes below maybe sometimes above if you don't assume the conjecture well the base fold one is kind of of high around 20 milliseconds uh let's compare if you are familiar with fine steer maybe I'll say this point that we is a you know drop in replacement to places where you use fire steer or base fold as a polinomial commitment

scheme okay so again if I compare that we can see that so steer what we introduced last Cas Summit okay is in blue now and in red is is fry so the argument size is much better than fry this is that was the main point of steer and we just you know gets roughly the same argument size H the PO time you can see is roughly the same in all schemes okay mainly the bottleneck of all these scheme is to do some big fft and this is kind of what they do anyway H the verifier hash complexity is much smaller in steer and and and Weir okay but in we also the field the field operation complexity is

much smaller so you can see here okay so the green one is where okay and the both steer and and Fire have like a much much much larger verified time okay how am I on time I have okay so a little more results okay so because we was not just a readed Solon proximity test but actually a constrained read Sol proximity test um what we can do with it we can compile not just polinomial commitment scheme but actually this sum check polinomial commitment scheme or as I denoted here just a sigma IOP so a sigma

IOP is going to be like a polinomial commitment scheme where I force the prover to send polinomial okay here I'm going to allow the verifier not just to do evaluation queries to this polinomial but actually some check queries to this polom okay so the the verifier can specify a polinomial w okay this weight polinomial w and you can get back this anel Sigma which is this sum okay so you can kind of do a a su like a query to these polinomial that theover specifies once you have this power then a lot of the effort is reduced from the

polinomial IOP itself okay because the verifier is much more powerful and all of this is encapsulated anyway into the whe L degree test that we run and so what we do we actually give a sigma IOP for generalized R1 CS which is a kind of has you know much more efficiency than other polinomial iops that you get and all of this is compiled and batched together to one we invocation at the end for some polinomial and uh and for some H constraint okay that kind of is a combination of all the constraints that the verifier

queries okay so this gives a an efficient way to go from from RS to iops uh we kind of didn't implement this yet and so I don't have like benchmarks for for this part um yeah okay so I think I have just one more minute so I'll going to we have something new called mutually correlated agreement um I have a just a quick minute on that so kind of the main technical tool that we use is this proximity gaps which roughly says the following oh I have many evaluation of

functions okay and I don't want to test each one individually so I'm going to take a randomly combination of them so I have C1 up to CL and I have the C star and I have this theorem by Bal okay in this proximity G paper and also Dan Carmon that should be here in the conference saying that if the SE star is close to Reed Solomon with high probability then all the CIS were actually also close to to to read Solomon so you see C star the green spots it's where it's close to read Solomon and every CI also has to be close to Solomon but actually what they proved is something much stronger they put something called correlated

agreement okay so they prove that this is not the right picture actually all the CIS are going to have a correlated agreement they're going to agree with Reed Solomon at the same domain okay so the picture is not like this but actually like this okay so all the C not only that they agree with with re Solomon but they have some shared domain where on it they agree with read someon and kind of what we do we uh introduce this new proximity gaps um where we say that it's not enough that the CIS have shared call it agreement but the C star should share the same domain as well okay so the picture should be like this where C star and all

the CIS have a so we call this mutually correlated agreement um so we prove that any time you have correlated agreement you have mutually correlated agreement up to the unique decoding radius and we kind of still leave it as an open problem to prove it Beyond um okay conclusion we introduce where where's an IOP for constrained read Solomon codes I think it can have other applications but the main one is of course using it as a polinomial commitment scheme we have verification time within milliseconds Prov time within seconds and the proof size is really tens of kilobytes we introduced

this new mutually correlated agreement proximity Gap ER we have this Sigma IOP where we combine it with our wear okay and then you apply the BCS transformation and all of these together give you a hash based snug this fast verifier can gain new application that's you know efficient onchain verification recursion and other stuff um yeah that's it thank you okay do we have any questions in the audience question this is where I get my cardio

in so surely I'm I'm just not understanding something I'm I'm trying to understand why this Mutual correlated agreement doesn't follow for free from from correlated agreement can't you in other words assuming that that the CIS are are have correlated agreement on some domain can you not always just take the the underlying code words combine those in the same way and then you get the same error domain for the C star why does that not come for free yeah good good excellent question so you're right so the CIS have correlated agreement which means that c star at that same domain which also be Co close to the the code word but what I don't get as a guarantee from the you know proximity

gaps paper is that c star might have additional domain which is which it's close to the read Solomon code where the CIS are do not agree on that domain okay so I want every place that sear agrees with the readed solomone the CI have correlated agreement on that on that domain I see so that that needs to be the only domain that the only way could be more than one could be more than one then the others have to also be CL if carar has 10 domains where it's Clos that's fine but all the CIS have also have 10 they need it to okay okay it's kind of a if and only if got it okay thanks that was great question any other questions okay brand of Applause for

Elan [Applause]