ZK10: Recent Advances in Folding Schemes - Liam Eagen

Transcript

foreign [Music] so for the last part of this day we're gonna have Liam talking about latest updates in the folding schemes world so yeah thanks Liam hi um just yeah okay thanks for coming to my talk I'll be talking about um recent advances in folding schemes specifically protostar and proto-galaxy and how the folding works there uh yeah and so you know start out motivating folding then sort of a simple example and uh depending how it goes maybe some more details so just to start out uh you know what is a snark

um we have a circuit that encodes an NP relation and we want to prove that we know some input to the Circuit that uh satisfies it um so you could imagine that we just send the input to the verifier the prover wants to convince the verifier and uh that we can do better than that with a snark we can prove that we know a w succinctly and non-interactively so we can send much less information to the verifier than the total w and we don't have to talk to them at all we just produce proof send it to them snark stands for succinct non-interactive argument of knowledge so

succinct and non-interactive lots of different snark protocols that you probably are familiar with growth 16 Marlin Planck Starks and so on but all of these are monolithic snarks meaning that uh you have one witness and you produce one proof and just send it to the verifier but snarks can also be used recursively because they're non-interactive if you take the verifier circuit like the the program that actually the verifier would run you can encode it into the circuit and then put a proof into the witness and then if you prove the satisfiability of that circuit that proves that you've

verified a proof inside of a snark and so you can use snarks recursively this is a pretty powerful powerful idea and is sort of generically sufficient to construct incrementally verifiable computation proof carrying data and to distribute and parallelize the proving of snarks amongst multiple people and over time so you know just to define the terms incrementally verifiable computation is when you have a long-running computation and you want to prove it as you go and so with a recursive snark you can prove one bit of it and then in the next bit you prove

that you proved the previous bit and proved the next bit and so on PCD is very similar except instead of in a line you prove in a kind of dag so you might have multiple proofs that you verify in each step and um yeah so the these are examples of parallel and distributed proving uh and I mean you can you can even use this to just optimize proving a monolithic snark you don't need multiple people or to be doing it over time if you just want to spread it over multiple computers at the same time and so on and this is how a lot of people who have a production systems do it now [Music] um

but uh encoding the verifier in the circuit can be very expensive depending on the proof system it may not even be possible for example with bulletproofs the verifier might have a bigger circuit than the circuit you're proving and so that's that's obviously not going to work if you try and recurse so what can we do well maybe we don't have to verify the whole proof every time we recurse maybe we can fold multiple proofs into one new kind of composite proof so that when we finally verify the new folded proof we can check that all of the input proofs were valid okay so that is if the X Prime W Prime is valid then

all of the inputs are valid and it should be the case that we can check that we folded much more efficiently than we could check the individual proofs and so if if we had such a protocol then in order to do say IVC or PCD you could prove each step and then rather than proving the verifier for the previous step you just fold the next step into some accumulator you maintain this accumulator of proofs and then at the very end you do the expensive verification so this is kind of why folding schemes are interesting and what they're trying to do um yeah so

folding schemes were introduced a couple of years ago in Nova for rank 1 constraint systems just an arithmetization uh for circuits and since then there's been a ton of work extending the folding schemes to different kinds of arithmetizations like Planck and default lookup arguments and to fold multiple r1cs's so for example if you had a a processor in multiple instructions you might want to fold different operations in each step so that's what non-uniform IVC allows you to do it's been extended to CCS which is like r1cs but with high degree Gates

essentially in hypernova and then more recently and what we'll be talking about today it was generalized much much more in protostar to fold arbitrary polynomial verifiers so in all the previous examples the verifier computation or the decider computation had to be structured in some sort of way so r1cs or Planck or ccs and in protostar it's sort of the you know the maximal generalization of that where you're just verifying that you you're running a single polynomial the verifier is and then in proto-galaxy joint work of myself and Ariel gabazon uh we extend

protostar to fold multiple instances so that's the the field is continuing to progress um and so maybe maybe you've heard of Nova and you're wondering like what is the difference between Nova style and protostar style folding so in Nova style folding so that would be like Nova Supernova hypernova um each time the prover proves a new instance they run the some check protocol the some check protocol is a old recently had a big Resurgence but in order to do that uh well you you use log in hash functions in in

executing the some check protocol and so in verifying the folding the folding verifier also checks login hash functions um and this type of folding in order to use some check requires certain sort of structure to the statement that you're proving and CCs is kind of like uh just the superset of all of the different ways that this could work uh yeah and it lends itself well to certain kinds of snarks based on you know how the subject protocol works like Spartan which also uses some check for r1cs and could be generalized to ccs um so in contrast protostar and proto-galaxy do not use some check in

this way they're just going to take any degree D polynomial map that Maps some input Vector to an output vector and Fold It uh and so the number of random Oracle queries does not depend on the number of constraints here here n is like the number of rows in your r1cs so just to set up kind of the the details of how protostar Works we're going to have our polynomial F which is of degree D and uh homomorphic commitment scheme and that means that if you add the commitments then it adds the committed Witnesses so we'll let Omega be a witness just a

bunch of field elements and Phi be a commitment to that witness and we say that the witness is the instance is valid if it's a member of the relation which is defined there just f is going to be 0 on the witness um so yeah very very general um we want to fold two of these but first maybe it would help to make concrete some of the generality so we know that we can fold any F but like what's an example of an F that people might be interested in um so we have an r1cs instance say and we have three matrices we want to show that you know if we multiply the matrices by the witness and then multiply component wise

it all checks out we can just write a function like that which takes the witness and for each row checks that the r1cs equation holds and that's it given that function you can apply protostar and proto-galaxy to it do the same thing for um CCS where instead of having just this degree 2 thing we might have some sort of polynomial gate g that you evaluate over a bunch of different Matrix multiplications and so yeah if it helps you can keep this in mind as like an example f um so what do folding schemes do like why why are they able to avoid running the verifier the answer is they exploit the linearity

of the commitment scheme in a really fundamental way so as like a simple example imagine that the approver wants to convince the verifier that some commitment fee Prime is a linear combination of these Witnesses they could send the linear combination of the witnesses or the witnesses themselves and verifier computes the linear combination but exploiting the linearity of the commitment you can just simplify that expression and write it as a linear combination of commitments which the verifier can check in time independent of the size of Omega right so the goal of a folding scheme is that we want to be able to verify a folding independent of the size of Omega in some sense and this is sort of the

essence of how that that works that's why the folding verifier doesn't depend on M it's also why it doesn't work with fry because fry is not a homomorphic commitment scheme so how do we use this to actually construct a folding scheme um so this this is a pretty common technique actually it's not you know unique to protostar and it probably predates all of this work and just comes from math but you can construct a line between our two witnesses remember we're trying to fold two instances with Omega 0 and Omega one and then by linearity we can construct a kind of commitment to that linear

combination of witnesses and so if you evaluate Omega at any particular X you evaluate fee at any particular X then Phi at that value will be a commitment to Omega at that value so now that we have this kind of like line interpolating the witnesses how do we fold well what happens when we evaluate F our big polynomial on the line if you evaluate it at zero then you can see that the second term cancels and we're just left with f of Omega and if you evaluate it at one the first term cancels and we're left with Omega F of Omega one so what we need to do is check that F of Omega is equal

to this kind of expression you can see the same sort of property holds on the right hand side if we evaluate at x equals zero you're left with f of Omega 0 and if you evaluated x equals one you're left with f of Omega one and uh so if there exists some Q such that this equation holds then uh the uh well the well yeah we can simplify it first but if if some Q exists then then we know that F of Omega 0 is what we claimed it to be in F of Omega 1 is what we claimed it to be by simplifying even further right so each of those two terms should vanish and we're just left with this

quotient so if a quotient exists then both of the instances were valid and this is the sort of folding claim that we're interested in we want to be able to check one thing and then you know extract that the previous two instances were valid so to do that you just standard techniques right you can evaluate at a random value evaluate our Omega and our fee at Gamma but there's a problem because F of Omega of gamma is not zero so Omega Prime and V Prime is not a valid instance because we're left with this like error term solution we can use is to relax the

relation to allow an error term so instead of checking that f is equal to zero we check that f is equal to a particular error term and if we verify the error term is constructed correctly then we can you know verify that the folding was done correctly so here we can just Define the error term like that and easy to see that we have a valid relaxed randomized instance uh so now in this example we folded two regular instances but how would we fold if there were two randomized instances well now we have two error terms so we're going to do pretty much exactly

the same thing we did before construct the lines construct a line through the error terms now what happens when we evaluate f we're going to get the error terms and plugging all that back in we can see that now instead of these terms Vanishing they'll be multiplied by the error terms and so we obtain a valid randomized instance from two input randomized instances so I mean I think one important thing to take away here is the the algebra is pretty straightforward it's it's not nothing really crazy is going on um you're you're doing just evaluating F on a line and then checking that it

evaluates to what it's supposed to evaluate to so now we can get into some of the the details of how protostar is done sort of efficiently um here you'll notice that F outputs a vector so each of these error terms is a vector but we don't want to send a vector of error terms to the verifier because that's that's of size n we'd also prefer not to send a commitment to the error terms so you know can we just make it a scalar say and it turns out that we can if we take a random linear combination of the F's by powers of beta then you'll see that if the random

linear combination is zero then it follows that f is zero on that input and in the case of a randomized instance if we take the random linear combination of the error terms then we are left with only a scalar but how do we fold this new kind of thing we've added this this beta and beta seems like it has high degree so maybe that's that's a problem um it turns out that we can fold beta in much the same way we fold Omega by properly redefining F including beta as part of the instance so this is generally both protostar and proto-galaxy do this but they do it in different ways so we'll Define just some

Vector beta beta bold and some family and polynomials G that outputs the powers of beta so protostar we're going to have beta vector be two vectors of length square root n and then G will take one element from the first vector and one element from the second vector and multiply them to get beta to the I in proto Galaxy we have log n scalars and each GI will take some subset of those scalars and multiply them to get a beta to the I and so you can see like in in proto Galaxy you just take the bit decomposition of I and multiply the different betas to the two I or two two

two powers and so on um and so when we fold the these G polynomials are our polynomials they're both polynomials of relatively small degree two or log n and uh so in principle we can do more or less the same thing we did before right you have two randomized instances with two different betas and we want to linearly interpolate between them and then compute the error terms from G G's are just more polynomials so at least in principle it seems like it should work um with a little bit of work you can show that you can actually do this in linear time in the number of constraints which might not be obvious in the proto-galaxy

case because each of these GIS is going to be of degree log n so if you want to compute n degree log n polynomials that's maybe not obviously possible in oven time but it is and you know just to note that these sort of lie on this spectrum of things where you can instead of their sort of extreme versions right so like in the protostar case you could imagine three vectors of length cube root of n or in the proto-galaxy case you can imagine increasing the length of each of these login vectors and so you know anyway so we've described how to fold two instances and two accumulators but what

if we wanted to fold multiple instances and multiple accumulators well this straightforward generalization we just let Z is in the case of two accumulators we're going to have Z be this Vanishing polynomial which is just zero when X is zero or X is one and in that special case X and one minus X are the LaGrange polynomials of Z if we want to fold K instances then we can use a different C and just use the LaGrange polynomials for that Z and the previous equation where we were evaluating on a line now we'll evaluate on a degree K minus one polynomial and if you think about how the LaGrange

polynomials are defined for each root of Z and each LaGrange polynomial will be zero except for one of them so if you evaluate on each root of Z the left hand side all the terms in the sum will vanish and on the right hand side all the terms but one in the sum will vanish and you'll be left with exactly the same sort of equation we had before where you evaluated at zero and evaluated it one yeah and so protostar is also sort of a general compiler for special sound protocols into folding schemes so I've described so far is like a kind of particular view of a folding scheme but it's very easy to add multiple rounds of

interaction between the prover and the verifier uh so one reason you might want to do this is to do like a lookup argument and so look up argument like a log derivative lookup or pluck up or any any lookup arguments going to require some Randomness from the verifier and so you'll need rounds of interaction in the instance that you're folding and so the the way this basically works is the perver is going to send some messages and get some challenges from the verifier and and this is you know fairly simple and then then we're going to evaluate our F over all of it it'll evaluate over the challenges and over the messages and just have some

algebraic verifier that you want to check so if we do this we can just Define the witness to be all the messages and all the challenges and we can add the challenges to the instance and apply protostar directly to this everything works the same as before more or less plus the verifier has to check that the challenges were computed correctly so the one important caveat here is that in order to instantiate a folding scheme you have to instantiate your random Oracle because the verifier has to prove the execution or check the execution of the the random Oracle which is not sort of possible for random oracles generally but you know

that's the case for all folding seams that are in use like Nova and protostar um so now maybe just talk about some stuff that I haven't haven't addressed and if you're interested definitely check out the papers or I did another talk for PSE I had maybe some more detail um but there are some significant benefits to using these General polynomials so like I mean they're clearly powerful enough to encode structured computations but you can also very easily modify them to do lookups to do non-uniform circuits so Supernova for example does non-uniform IVC you can just sort of do that with protostar in

the way you'd hope where your your prover work does not depend on the total number of operations only the operation that you're folding each time um and another big question in practice is how do you actually compute the error terms I just sort of assumed that we could but it's maybe not obvious how um and so like in general if f is just some like arbitrary degree D polynomial it's going to be huge and impossible to work with so in practice f is almost always very structured Even If It Isn't So structured that it would fit into CCS it's definitely structured enough that we can take advantage of it so for example it might have mostly low degree

constraints which you can take advantage of and it might be written as a composition maybe not of a linear function but just a composition in general and you can use that to uh you know compute the error terms more efficiently and then finally in the Proto Galaxy paper we describe how to fold using some check over the instances instead of LaGrange polynomials and the big Advantage here is that we're able to avoid ffts and have uh sort of get rid of most of the log factors in the prover time note this is not the same thing that hypernova Anova style protocols do we're

doing some check to combine instances as opposed to some check to reduce Vector Matrix multiplications but anyway some check appears once again and uh yeah I think that's that's pretty much it um any questions thanks Liam so yeah you you asked the question any question come on don't be afraid um I think I would maybe just ask like

where do you see the research maybe going from here in terms of it's come a long way in the last three or four years what are the things that still need to be tackled what needs to be better and stuff like that in your opinion I think that a lot of these protocols need to be implemented and then benchmarked and compared um that's kind of lagged the research which makes sense given how fast it's moved in terms of open questions uh folding layered circuits so like gkr if there's a possibility to sort of fold that more efficiently than kind of the straightforward way um and uh

yeah I guess also exploring this like error term computation space like what was the best way to do that and and these sorts of things um yeah I think I think those are the big new directions um so I also maybe more foundational theoretical question I'm not aware of but what is the what is the soundness of the folding skin depend on so like what is the assumption that you use it's not like is it Interventional theoretic is it just for example or do you use some cryptographic assumptions um so the the main like different cryptographic assumption from a standard snark is this instantiating the random Oracle so you have to

instantiate the random Oracle as a hash function this is just a heuristic kind of argument there are works that attempt to get around this but they're sort of more theoretical on on like you know arithmetized random oracles um but the the assumptions I think will mostly come down to the commitment scheme that you use so if you use kzg or Pederson um I suppose you could probably do something with groups of unknown order but you know typically it's Casey dear Pederson because they have to be linear commitments so you can't use fry so it would be like discrete log that's on the that's on this step the folding schema still view it as an interactive process before we fetch a mirror okay and what about so the folding scheme itself is not zero

knowledge right so the error so the the there there's like nothing that hides anything there at all definitely it's a place to your case that's maybe another answer to the previous question is adding zero knowledge to folding schemes it's um not like impossible it's just uh I think something that probably needs to be done explicitly uh yeah like protostar and proto-galaxy don't don't deal with zero knowledge at all foreign thanks [Applause]