FLIP-and-prove R1CS - Carla Ràfols

Transcript

okay okay so I think we can start then people can can join afterwards not an issue so well first of all thank you Carla for for coming here to present I know you are here with nikitas and also anesco who is in the chat uh so thank you you all for coming um today you're going to speak about flip and proof uh think one of your latest papers uh where if I understand correctly you propose a new folding scheme and also a way to proof relax want CS in a much more uh let's say optimal way uh thank you very much for you all uh to attending and the floor is yours so feel free to start um

thank you very much Carlos um I will uh present this this work and um I will have distinguish two parts like first I will start with an overview where you will see like these beautiful slides they are when you see beautiful slides they are from Anka um which I like messed around so there's if there's something that is no longer iic about the slides is because I modified the beautiful slides from Anka and then since I understand that uh you want to hear also like a bit more in depth um for the more technical part I would use like some other um slides like say more mathy

slides um okay so what let's start with the overview so what is our motivation and when we started like we had a concrete application in mind which was the the filecoin um um proofs of storage and there we have like storage providers and they have they are really regularly proving sto storage and they have to um so they they keep like regularly making um snug proofs that they are really um have are keeping sufficient um space for for the data they have to store and as you probably know like in this

application it's like as far as I know um currently one of the largest instance like where we're like regularly proving like many many R1 CS uh doing many R1 CS proofs okay so the situation was something like that so for each unit of space there was like something like 10 snarks and these were like submitted on chain This was um the original um solution which of course course like you know that this require um lots of space right um for this um to minimize the cost of like storing these large proofs also maybe the cost of verifying them the cost of proving um there was like a previous

solution so um yes sorry um and all these Nars they are for R1 CS um proof so like maybe the general idea is to that our results are also for other types of um constraint system but in this particular case this um providing these proofs requires doing lots of R1 CS proofs as you know R1 CS um which are rank constraint systems it's like a characterization of NP and it's commonly used to as an abstraction to describe the kind of um some the kind of constraints the kind of thing you need to prove to to do asars so the topic of

this talk motivated by this application but I think it's like a general case right where you want to prove many R1 CS instanes is to um study how to prove many of multiple R1 CS instances um in different ways so how can you save on different parameters of course like the first solution that you can do is like just to prove naively right like like you have many statements many are 1cs statements and you just prove individually each of them what else can you do well there's another like classical thing to do which is like save and verification you just

compute individual proofs but you just can do some probabilistic techniques to do a a random linear combination of the proofs or something so that you are saving on verification but you're of course not saving on either storage or Pro time other approaches is to have aggregation okay so what is the difference on aggregation so here we're are not saving on proof or time because we're still Computing the individual proofs but we're saving on storage because we find a way to um store all these proofs in a compact way finally another um another way of achieving this is to recurse okay so

like the idea is as you very well know um the idea is like you keep sequentially like making proofs and in each step you prove that you have a that the new statement is true and also that you have a proof that the previous statement is true um as you know this has like many advantages and as you know this is like why is this so popular and like um the advantages are that you save a lot on Pro memory um you the the verifier essentially has the cost of like verifying one instance and um and um and like the proof doesn't grow right of course you also know that

um this recursion um comes with a lot of engineering challenges including for instance the need to use cycles of elliptic curves to make proofs of proes that that are correct so you need to somehow arithmetization verifier and to avoid doing not native arithmetic you need to to move to some cycle of elliptic curves or something like this so This solution although it's like um fantastic and it's very interesting it comes with lots of engineering challenges and also there's like some kind of prover overhead because you're arithmetization as instance but you also need to prove

um that the verifier would accept the the previous proof so um then in this setting of recursion as you probably also know very well there was this idea of folding statements which is the idea of um so what is a folding protocol like it's a an interactive um protocol between approver and a verifier where they reduce two different statements um with their witnesses to a single um to a single statement okay so the verifier is like a public going verifier who's like um changing and sending just some

challenge the approver is sending some cross terms and at the end together they manage to reduce this to a single instance this has been used like in the context of folding and the idea is that the same idea of recursion but like now each of the steps um is very cheap right because instead of doing a proof that the previous step was would be so doing the full proof so proving with a snark that um there was a satisfying instance what you do is just you just keep a running instance of all the commitments and you show at the end that they satisfy some relation um this has like the same it

this is much better from the point of view of approver as you know because first for two reasons first because each of these steps um is essentially much cheaper than Computing a full snack proofs and also because the verifier of the folding relation is also usually um much smaller than the verifier of a full snar but we are in the same situation right like this is still difficult to realize um apart from other issues like um maybe privacy see right depending on who who verifies this um so in the case there's more than one PR although this is also the setting that we will consider in this

talk so um when we have something like recursion via folding usually we think of folding as like this step of um reducing these multiple instances to a single one and usually then we have at the end to a single a single instance of something called um relax our ons um that I will tell you more about later although I'm sure also that you know and um the what we have here um when we're using recursion with fault Ling is that usually this last step um as as it's currently currently

implemented there are like two solutions to prove this one step like what or three so one solution is like you do nothing at all right like you don't create approv because like maybe your your fault statement is so small it doesn't pay off but if you want to approve it you maybe use um as in the Nova paper you can use Spartan or if not um you can also use Gro 16 but then you have to adapt Gro Gro 16 um for um for proving um this so you have to create a circuit that proves that this relax are 1cs instant um is um so that you have a witness for this thing so it's not

really native like you're doing some arithmetization here um so another option that you can use is like using option with folding without Cycles right what at the end what is uh folding well is just a way of reducing two statements to to a single one right so like you don't really need to prove that the folding was correct but you could also just keep um reducing like many statements to um to less and less and less okay so you can start with two statements reduce it to one then get another statement reduce it to a single statement and so on and you don't need to prove that you've done this correctly

you just can let the verifier check that okay what's the problem with this approach is that the verification is linear in the number of statements right somebody has to verify that you're doing all these folding steps correctly I'm I'm emphasizing this because although folding was uh proposed in the context of recursion and maybe this is how it's most often used in reality this is um you can just do folding in any curve and without any need of cycles and and you can just thinking think of it as a way to reduce um several statements to a single one um then we when we do when we follow this approach we're still in the same

situation right like we have we are folding many we are doing um several steps of folding and we end up with a single one relax at one CS statement okay and again we have the same issues here so we have to think how to prove it um we have to so this is the same as in the recursion setting okay you have to think how you want to prove this last step but what's different let me emphasize what's different from using recurs um folding with recursion or without recursion is that here if you're not using any cycle of Curves you still need to to read and check that all the statements have been folded correctly what do we propose we propose

something called that we call flip and proof which can be summarized as simple communication efficient folding what's the idea why I say do I say it's simple because it avoids some of the complexity because it doesn't go through um through cycles of elliptic curves and um but it doesn't incur into this problem that if you don't use Cycles you need to verify all the steps um compared to previous approaches like aggregation um you still have the benefits of folding so you are not doing any fora transform in all these parts and um

and the second part of our contribution is this uh a protocol for this last step a specific uh a sort of like gr 16 to prove this this step but where you're not like trying to write uh so you not really modifying the circuit um that you're proving so like essentially um it's a Gro 16 that allows you to prove this step but for the same circuit as the original R1 CS instance okay okay so in summary the the advantages uh of what we propose is compared to batch verification in batch verification we had large proof size but we are reducing the pro time but also um large proof time in aggregation we are

increasing the proof time because apart from doing the individual proofs we are um Computing the proof um aggregated um and we reduce we also have like reduced verification and reduce uh storage proofs and what we propose is to to keep this uh this like low communication cost so to we have it's like in aggregation we somehow make all the proofs compact um we also keep this H short verifier time compared to so equal like in aggregation but we massively reduce the um proving time because of following this folding approach right where we are

essentially um reducing many instances to to one and then the expensive step which is folding uh sorry which is proving with a snark we only do it once um note also the difference with recursion okay in recursion you have like some overhead for the prer because of verifying the the of because of verifying the the so arith matiz in the verifier circuit but of course like you have like other very good advantages okay so the main advantage with respect to recursion is the complexity so it's like a really simpler

solution okay so let me review very quickly so um for this particular application we had in mind which is pro proving multiple R1 CS instances and in particular um this file coin application there was like a solution that was designed for for this setting which was snar pack okay and this is a paper of Nicolas gayi Mary Maller and an nesi where um what they achieved is uh getting like many different snar groups like gr 16 proofs and from this they created a single aggregated proof of size logarithmic in the number of

statements um like what I want to emphasize about this solution is the techniques that they used so how did they achieve this shorter um proof size how did do they achieve this reduced communication complexity um well they used um something called um two-tier um commitments and the starting point is the observation that if you want to verify many uh snarks so if you have many growth 16 proofs um and growth 16 essentially is like the proof consists of three elements and you have like many of those what you need to make sure is that these group elements satisfy like different

pairing based equations how can you do this compactly where there is this um technique um called proofs for ining products which is a paper of B Mal Mishra tag and belli where they suggest what they do is like they sort of build like a bulletproof um proof system so um so it has all the features of bulletproof so like logarithmic Communication lmic number of rounds um where um the idea is that you're committing to these group elements okay so you have to prove that many of these type of equations are satisfied and somehow you manage to

communicate all the um all the terms that are all these group elements succinctly and this is Achi by a tool called algebraic commitments to group elements okay so um so you have many so how does it work you have like many snark proofs so this means you have many terms a many terms B and many terms C and you create a commitment to those with these algebraic commitments so that you get something that is suin and then in a Lo in logarithmic number of rounds you might managed to prove that these things that are inside the commitments are um satisfying all the groad 6tin

verification equations um so you never really send the proofs but you just prove that these proofs exist and that they verify what I want to emphasize here as because we will also be using um similar techniques is that in this context we are um thinking of these proofs for inner pairing products as a tool to prove the satisfiability of many pairing equations okay so we have these pairing equations which are the verification equations and we are proving in a succin way that we know a solution of all these equations okay so with this um basic

solution that already exists we now move to present our solution um for this very quickly because I think most of you already know that um we talk about how to do folding for R1 CS instances and this is something that comes from Nova a a very wellknown paper um um byal um Siti and salala and the idea is that um we have an R1 CS instance and we are trying to fold it so what we're trying to do is from these are 1cs instance to in a probabilistic way from this one and another one reduce

it to a single instance um so we start from this is our starting point we have two different instances and we what uh the Nova introduces is a new Rel relation which is relax R1 CS okay that um it's relax R1 CS because if you you can see that it's a R1 CS is a special case of relax R1 CCS right if you take that the error Vector is zero and this normalizing Factor U is one then you get exactly an instance of r1s

um what uh so why is this useful well the idea is that if you fold to R1 CS instance you get a relaxed R1 CS instance and then you can continue the process right and then if you get two different R1 CS instances um you get a new R1 CS instance so this is R1 CS let's say it's not foldable but we relax R1 CN um is amenable to folding wait okay um sorry um okay so we will see this in in more detail um in a second okay so this was the the basic um motivation okay the basic concept so

also to how to do relax R once yes and now I move to do a more uh technical deep deep dive [Music] um so so we have the ingredients we have um we have talked about folding R1 yes and we have talked about these commitments to commitment um now I will tell you a bit more in detail how these commitments to commitments work so our point of comparison is the pson U Vector commitment okay that you all know so we have we are in a group of

prime order and we have like a key that is just a group of um a vector of uh group elements um I don't specify the distribution you can Define this key in different ways okay so it's let's say it's just some distribution and then as you know when you want to commit to a vector in um on integers modu of P what you're doing is essentially an inner product but in the exponent okay so you're doing a random linear combinations with this key and these coefficients that are the vectors why is this binding well the idea is like if you manage to find two

different op openings then you are able to find a vector of scolars such that the inner product um with the commitment key is zero this is actually um so this is actually a hard problem for many for many G's not so as for any reasonable G you can think about this is a hard problem which is actually equivalent to the discrete logorithm problem it's some some kind sometimes called the find rep problem or discrete block relations problem okay so examples of distribution for which this is hard it would be like for instance a uniform distribution or also um powers of tow like you can also take a structured um commitment key okay

everybody knows this like why am I telling you about this because you can make a parallel um and to see how you commit to group elements okay what's different in the case you want to commit to group elements um so what you have here is that you have a a group key okay so you're now not in a just a a group but you also have like a bilinear pairing I'm using additive notation for all groups maybe not not very useful and not very usual um but I think that um is better for illustrating the linear algebra that you you're using so um the difference now is that you're commit key is actually a

vector um of group elements but in the second source group okay so and to commit you're committing to vectors of group elements in um in the first s group source group okay so what you have is here's the commitment key um which is in this group and here's the vector and again the commitment is just an inner product except now the this inner product what it means is that you're doing like this linear operation which is like this Bel linear operation which is the pairing instead of exponentiation so you're doing the inner product of the message with a group element so your final commitment is just

a Target group group element how do we argue about binding here so if we have we manage to find two different openings so again this means we managed to find like um some vector of group elements in source group one such that their inner product with a commitment key is zero again so so this is the hard problem right so you find you have to find a vector of group elements in source group in the First Source group such that the inner product with G is zero okay it should be a zero um is this a hard problem for different chees let let's see what let's

F try to find examples of these um when this is a heart problem um for this let me see a a small example of a commitment to group elements when um when my the length of the messages that I'm committing is just two okay so in this case um imagine I just pick as a commitment key um the again the powers of Doubt so I this I have P2 which is a generator of group two and I have T * P2 um how do I commit well I just do this linear combination is this binding unfortunately this is not

binding if the adversary also receives the the key G in group one so if it receives also these powers of to in the other source group we don't have a binding commitment okay why is this well look at this two at at this message so if I take take this message M Prime and I just Define it like that okay if I commit to this one what you can observe that the uh result is zero so essentially I'm able to construct um a commitment for which the commitment is zero okay so in particular this means that I can find for any message that I want more than one way to open it okay

because the commitment to to this message M can also be open open to the message M plus M Prime this is more General than that also if I choose mul like it's not only this message and Prime so I can randomize this this this fact right so if I choose this message which is like a randomization of uh the previous one this is also a commitment to zero so in particular I can find many different ways of opening a commitment this is something that was also a problem and for instance in snark pack and the Sol the solutions they suggested was just to move to using

double so like using two different commitment Keys okay so now the idea is like you get two different um commitment Keys um with same structure or actually it could be in I'm not using anything in particular about in this example you could also talk about uniform distribution okay it's in general it's an example it's a problem if you have the key that you're committing like you have it in both groups okay so the solution out of the box let's say is to get uh to do double commitment so you commit the same me to the same message with respect to do different Keys okay so this is the commitment to the message with respect to C1 and C2 what's the

problem about this with well obviously the problem is um much higher communication costs okay um this is a hard problem so it's sound but you get very high communication cost the another the efficient solution that we use which is avoids this problem is um a solution proposed by aong a paper called a but amona atal in 2022 and the idea is to avoid this growth of the commitment so the double increase on communication length the idea is to to use to think of this not only as commitment to group elements but

also as commitments to commitments okay so so here we really using the fact that these are two tiers commitments so we are not just using the scheme to commit to random group elements but we are really using this scheme to commit to commitments okay so the situation that we have is we have a Bel linear group of prime order and we are committing to this group elements and we have the adversary receives this key in both groups okay um okay so then the our the solution is just to commit normally to it but um in the soundness analysis what we show is that

if you can open this commitment to another um commitment key so if you can open M1 with respect to another commitment key CK and M2 with respect to another commitment key CK that is independent of this key that you're using for commitment for committing to to the Target group then um this is still a hard problem okay so it's hard to find a vector of elements in G1 such that they break by so that the inner product with the commitment key um G is zero and at the same time um open each of these uh vectors in in the

first group with respect to another commitment key okay so what's the intuition the intuition is that um this is the only way to break sounds okay the only way to break SAS is is somehow used that you have the key in the other group so the only way way to break soundness is to put things here that are related to the commitment Key C Capital CK okay so if you are committing to things that you know for sure they don't open to anything relate to Capital CK then your scheme is still V okay so this is like an important technique that I hope gets more attention from this paper a long that I think is quite

useful and I wanted to show you this technique okay so and what our contribution is to also give a different um formalization or writing of this technique okay so um then um remember we so the key our key idea is to use folding um in combination with these uh two tier commitments okay and as I I already gave an overview of how um does folding look like and in particular a bit more technically the folding protocol looks like that okay we have approver that has two different

statements that are committed relax R1 CS so they are like relax R1 CS where you have um a public statement a scaler factor a commitment to error terms and and the witness and um the verifier just knows these two statements and the we and the approver also know knows a a witness to them um the important thing here is like the verifier is sending these cross terms and it gets them a challenge from the um from the verifier okay and the result is just that the prover gets a single witness and the verifier gets a single

statement um the things the two things to notice is that um the approver is sending this cross terms and second that um the way we are building the new statement okay e and w we are using like different linear combination so in for the new error term we are having um the previous error term the second error term and then um these uh cross terms in the middle but the coefficient we're using for the error terms is um C square and which is different that from the other part okay nothing new here now we move to talk about our solution so what's our

solution so first observe um that you can fold R1 CS instances in parallel okay so imagine now that you have um four different statements that you want to prove and you can essentially run the same protocol for a um R1 CS um in which you are folding w 1 with W3 and W2 with W4 right that you can do them both in parallel so how well you just have to send across terms 1 three two four right that you're mixing one with three two with four and um and then you

you do the linear combination for each of the terms okay at the end what you get is that the verifier the prover gets two different Witnesses the verifier gets two different okay so the um in general so this applies of course in general let's say you want you have different so K different instances and you can like fold them in parallel right I can fold W1 with a WK half plus one WK half with WK and this means this involves sending K half PRS okay each um I'm mixing this with this so I need to send the cross

terms with this okay so now I use this idea for doing parallel efficient folding of R1 Cs and the idea here is that instead of sending all this um so I the prover and the verifier now no longer have many different R1 CS instances but instead what they have is a commitment to many r1c relax r once CS instances okay so the verifier does not know all the individual statements that um so the we the so it knows the individual statement so it knows XI and UI but it doesn't know the commitment to

all the witnesses and it doesn't know the commit it sorry it doesn't know the commitment it doesn't know all the commitments to the witness instead it knows a commitment to all the commit m ments to the witnesses okay so you're reducing sending um all the all the commitments to W1 W2 to W3 to W4 instead you're sending a single Target group commitment and same thing for the error terms um and here you would need to send um two error terms instead you also the idea is also to send a commitment um to all these um cross terms um in in the

Target group okay if we do that well the verifier can no longer obviously construct the new error terms with this and because it doesn't know all the error terms it doesn't know all the witnesses and the idea is to um have something related it's it like actually looks very close to Bullet proofs so the idea is um now the witness is split in two with the left part and the right part part the commitment to the error terms is split in two the left part and the right part and the prover is just sending these halves of the commitment right so that um folding can be done in parallel so you're folding um you're

folding like that so the left terms so the same linear combination you were doing before now you're doing it in parallel with the commitments um to the first half and the second second half right so if if you check that like what is this so this is the commitment to E1 and E2 um plus a challenge which is a commitment to one two so 13 and to four and this is a commitment to um three and four okay and you can check that what you're doing with this is getting um a commitment so what you're doing is

actually you're folding W1 with W3 and W2 with W4 and you're just doing it in parallel in a suy way um okay and so what do you get as a result um of this process so you get that the witness the the prover has these two witnesses no we have four instances they get reduced to two witnesses and the verifier has this um keeps uh a commitment but it's a commitment to a vector of half the size okay so he has folded W1 with W3 W2 with W4 and same thing for the aotrs um so what we're using here is the

homomorphic are theomorphic commitments of these two tier commitments so if you compare with a Nova like if you were trying to flip without Cycles sorry trying to flip without Cycles um what you would be doing is something like that right like you would you can also build um a tree of things that you want to fold but you still need to to check every step right a verifier needs to know that these two commitments and check they are folded together in a new commitment and same thing for air drums what we are doing is like somehow like um we are doing a single commitment for each step of the folding okay so that in each step I'm

folding this one with this this one with this and same thing for the ARs um so this is like a I want to emphasize that this is like a a novel we use of in this inner pairing product um um equation um inner pairing products argument at least that's the how I see it because usually as I said you think of this inner brain product as a way to prove that many pairing products equation are satisfied instead you you're you're thinking of the of this uh inner bearing product uh argument as a way to um to to fold many things in parallel um with very um in a very

communication efficient way okay so um in reality so a few more details how does the protocol work as I said like you send essentially one commitment to the witness and one commitment to to the to the error term per um per level right like you you're sort of like building a tree of statements that you're folding in the base level like at the leaf level you have to check that this you start folding our oncs instances so you really have to check that this is well formed so you will check that all the um all the terms U are equal to one and the cross terms are zero so this you check at the leaps and then when you get to

the to the root um what you get is a target group element and what you do is like you open this target group element so at the end when you finish your folding you have ah a group element in so something in group one and something also there are terms also in group one so that you really have like a new statement that it's a committed relax R1 CS like it has exactly the same shape as if you had been folding this thing on Parallel [Music] um so there are there are a few things that I didn't really tell tell you so there's like a

few extra details that are um related to the commitment Cas like that you probably know if you have worked with bullet proofs uh before um so the the so let's say a few things about these extra details like the first thing is that I think this is the important thing to understand and highlight about this protocol is that what you get in the last step is like a commitment um to a a group element which is actually a linear combination of all the previous commitment so it looks like exactly like folding except that the randomness you're using has really like tensor structure okay which corresponds

to really like folding things in parallel so it's some kind of derandomization that where you're like folding but with um fewer uh rounds and and all the error terms and everything is consistent with that okay so we're getting like the Earth terms with that correspond to folding like that the other thing to note is that um what we get in the last round when we are opening at the root so because we end up with a Target group element and we open it so it means that we have to to give some some W and some W um Prime such that this is holds so we have to open

this with a certain specific commitment key in the in the source second source group okay and this commitment key as um you know from bullet proofs looks like that okay and as you know this like it's a problem because this means in fact that if ck1 ck2 ck3 and ck4 is the original commitment key um this requires a a linear number of operations in in the number of statements you want to aggregate um and same thing for the error terms okay if like if you are like to compute this key you would actually need to um do a linear number of operations luckily there's like since we

are in a pairing group okay we have not moved from the same um pairing group from the beginning when we are aggregating all the statements there's this technique from Doris where that um tells us that if we are using um this commitment key that are structured we can achieve um logarithmic communication okay so this was the flip protocol um what I think is interesting about the flip protocol is that um it's to open the door for folding other relations um also with this uh inner bearing product so that that is actually you get something that's communication efficient and it probably cannot

substitute recursion in many settings but for there are settings where probably it's sufficient and it's much a much simpler solution you don't need you can use parent groups nothing special about these parent groups you can use BLS 12 381 or whatever you need finally Carla can I ask a question I I just can answer it to myself can we have non-uniform folding with flip because if you are proving that you have commitments to commitments that open to correct places this argument is just so generic that I don't see why you could have nonuniform folding working in

flip like is there anything that prevents this from happening or in fact you can just fault anything that you want so actually I I think that's actually the the thing to that I want to look next like I didn't really look at it because but I I'm I'm quite sure that you can do so that you can like again what you're using is the amorphicity right and I don't see a reason why you cannot do it with other um relations I didn't explore this yet because of the time um but I think that it it probably works and I think that's actually um that's the nice question to look for okay and one other question that I have

is when you say folding in parallel can we assume that you can plug in the PCD compiler from Bon at all into your construction or parallel here means I mean there's some level of parallelism I see that but uh usually when I when I assume that you can fold in parallel it means you can just plug in the PCD compiler there and have likeing basically yes but like we are in a very different setting from folding right like um in so in in folding like um so so here you still have to verify all the steps you're doing like and I

can there's no way um I I don't know like there's no way I can prove that this was done correctly from another Pro and so on so like I I wouldn't know that's fair that's fair I see okay okay yeah that answers it thank you very much yeah yeah so it's really like I think the setting of recursion is like out for this for this talk um so because it's like sort of the point right that we are going to something that is like not recursion but maybe simpler for many uh occasions sure that that makes complete sense and I mean if I can ask one more question so for I I prefer to get us um so one of the like tricks is that you

are you are basically getting like you are haling the costs of uh the things that you are passing between Prov and verifying let's say like you showed it with the cross terms for example um my question is you like the does the arity affect like do you get a blow up factor in the cross terms the more instances you want to fall in together like instead of doing one with three and two with four if you have now eight instances and you want to just like eat that up at the same time do you get a blow up as it happened in Nova or not yes yes you do because it's like the technique is the same right like so for here like the cross terms

are like that so it's essentially the the Nova sorry I it's essentially the Nova cross term so naively is this now again the question is um and that's the work that I think is interesting is to get all these techniques no that as as you said Nova had this blow up Factor then some papers um found solutions for that like probably you can move these solutions to this setting and then let's see what you get sure sure sure sure that makes sense and the the last one that I have is um also about this uh haling of the communication cost you are in fact halving the communication cost in in these areas I completely agree but

when you are passing the commitments forward those commitments are much bigger as we are in GT rather than in G1 uh of many of the curves that we will be in Nova so how do you account for that is it still worth it uh so but I so what I don't really get is why do you say it's haling the communication cost because it's actually making it logarithmic right like you get something like that um so so so this is the situation so again I'm doing full I'm doing Nova but with that like I'm comparing to no okay I see I see what you mean so here you need to read all the statements

and verify they hold correctly so it definitely makes it worth it then to send GT elements around like you just don't care about it it's worth it like for sure okay that makes sense I think so I think so that makes sense thank you very much okay so okay so now we want to talk about the last step so which is how do you proof um Road 16 for relaxer so how do you prove relaxer 1cs and you want to do it um so you in the most communication efficient way okay so you can optimize um when you're designing a snar you can optimize for different parameters and what I try to

do here in this design is to get something that is as communication efficient as possible okay so let's start so I will just give the the idea so the idea is let's start with gr 16 what's the overview as you know gr 16 like the it's not so you don't have to read everything but you you probably have seen gr 16 before and it looks uh the the structure reference string looks something like that right like you have um many of these linear combinations that include Alphas betas and so on you also have these terms uh with involved and T of X which is the vanishing polinomial at

some group of roots of unity and uh why is uh so um gr 16 so special well it's because it's super has very very short um um very very short proof it's just three group elements two in group one and one in group two and to verify it you just just do three pairings okay so the verification equation looks like that um so as you know like one of the draw so one of the drawbacks of drop 16 is that the setup is relation dependent really so if you change the circuit you really have to change completely um the structure reference string because

actually as soon as information about this Delta can be is leaked then you can prove like arbitrary thing so you really need to to get like a new Delta for every time you do a circuit okay so so if that gr 16 is like um relation dependent like maybe it's strange that we can like sort of adapt it to prove relax our oncs right so why does this work why can we relax so why can we modify it a little bit grow 16 and still able and be able to prove relax at oncs instances um well because if you the the thoughts so at least that's how I understand it

um for grow 16 there are like two parts okay so essentially um grow 16 is a way to prove very compactly um two different relations ignoring um the fact that you also have to prove things about the public input so on the one hand you're like adding these terms because you are proving like a hadamar relation so you're proving that there are some vectors A B and C such that the component wise product is equal to another vectors o sorry my cser um okay so and this is related to some quo you have to to compute for this hadamar relation on the other hand you

have these terms which are thought to prove linear relations and this is what these terms are what make like um somehow um gr 16 not Universal because this way of proving linear relations so you're trying to prove that this Vector ABC that satisfies that hadam relation they all have implicitly here the same Vector Z okay um so so so okay so this is the the building blocks of proxin the main ideas behind it the rest is just trying to pack everything um in as short as possible um in a prove that is as short as possible and so now um why can we

generalize this to something like relax our ons um where our statement is something like that right like we have a scaler we have a public input and we have um the commitment to the error terms and the commitment to this uh witness so the idea is that actually now what we need to prove is a different hadam relation so we are trying to prove that there are some vectors A B such that U * C plus some Er terms are uh um holes right so but since this like hadamar relation um is like sort of universal actually that we can actually um prove that without really changing the SRS we just have to change how we verify stuff on the other

hand for the RAR relations um we are trying to prove something like this but we also need to prove that this commitment that we are given as input so the w Really matches that the same Z that is used for a and C so here we really need to change the the structure reference string okay because we are proving a new linear relations and as I told you these linear relations are not Universal so you you need to adapt the SRS to prove these kind of things this is similar to changes you need to make if you uh want to make your snark commit and proof because at the end this is essentially what you're doing okay now you want to prove that ABC satisfi this

and that you have a commitment to this uh to this Z not that that this so you're giving this as an input so you're giving a committed witness and you have to prove that this committed witness is also the one you're using for the relations okay so essentially that's it so we add like you could design your snark by adding um some trapdoor to prove one extra linear ation and uh you and then the hadam relations like sort of you get this for free unfortunately um there are additional complications because um one because this like uh the statement e and

w is created by the prover so it can be adversarial right so it doesn't need to be uh correctly computed commitments to to some to the error terms so there are like additional trap doors that I need to put in the SRS that we need to put in the SRS so that uh we can also make sure that they are more or less correctly computed okay the final result is we get something like that so we have uh the SRS includes the commitment keys that I'm using for committing to e and w it adds this extra term which is essentially proving this extra linear relation that I need for making the scheme commit and proove and there are these other trap

and and these commitment keys that are thought um the role that play is to make sure thatan W are extractable and are correctly computed okay the verification equation that you get is this so you can check that the proof size is the same but of course now um you have that it includes the statement so there are two extra group elements that you don't have in go 16 okay because your statement just has two group elements and the and you also need to to do through ex appearance there is an exponentiation in in the Target group but in fact well this is a bit of aesthetic reason like if you divide everything by you then you don't have this exponentiation in in in

the Target group and um that's it so that's the the end of the talk thanks I don't know if it's there are more questions uh so first of all thank you very much for the presentation I think it was crystal clear so it's appreciated when when this happens uh I have one question Rel related to the relaxer one CS Pro and it's do you foresee any improvements that could happen like when you wrote the paper did you find any ideas as we discussed previously

with with flip that you were like okay this is something that has potential and we could continue looking forward so as I said like what I want to look for now is like um different folding different instances for relaxer ones yes um so for the last step I find it so I think you can um probably reduce communication complexity by using techniques like uh that have been recently so there's this paper of Lima polyma and there's this I thing there's this recent paper also um and probably it's Pari or guda but um from this new paper um as far as I understand um these

papers are using have shorter communication complexity but the price that they pay is that you're arithmetization size for relaxer 1cs as well well the the question is how is if this tradeoff is interesting to you I have difficulties seeing what can you do better with this growth 16 although as I said like when you design such a snark there's not a single tradeoff possible Right like in fact I this took us some time because we had like different possible ways of building it like do we want to put a random Oracle but maybe

then you change the the setup in less right like we were concerned about changing the setup because we know that from an engineering point of view it's complicated yeah we we know that I think you cannot avoid it related to this C in a certain sense you cannot avoid it so you cannot avoid somehow to have this oh to have this extra term to prove this extra relation because it's related to make it commit and proof the question is how many extra trap doors and how special do you want your commitment key to be um I forgot to mention that we analyzed uh the when we did the security

proof of this narc we also analyzed it in a model that takes into account the the do do the powers of town ceremony that you would uh run to generate the setup so I don't know like for GR 16 right as you know there was this paper of uh powers of to yep where they showed that actually grow 16 is still sound if you publish some intermediate values right like this uh mu this U times beta this V times Alpha and so on right so we did the same analys so our security pro proof is like in this stronger model where we show that these intermediate

values that you would need to to run the sumary wouldn't affect soundness but of course like we understand that this is like in practice an it can be an issue that makes sense mainly asking that because of the fact that as you correctly say if you need to constantly let's say modify the SRS it's not just just the challenge of you need to have you need to hold a lot of memory in your device to be able to keep modifying it but also the fact that once you want to run the decider amongst all of this communication you need to redistribute new verifying keys to whoever wants to verify this computation because the SRS was just

changed is is that correct or am I like just missing something which could definitely I think you're I I don't know if we're understanding each other completely because this does not depend on the relaxer onc as instance is is this so so when do so we it uh well I'm not sure we okay so this this is the same key when you fix ABC yes uh I see okay it's not like a key for okay okay okay okay I was still in the in the setup of since we are proving commitments of commitments we we can just go with whatever but you're completely right

that makes sense makes sense okay uh I think there's a question in the chat from Pier also uh thank this is really cool uh is there any reference implementation um no we don't have any implementation no we we don't I'm we are not in a we don't have the capacity any of us three but we would be happy to to talk um if somebody is interested cool okay good to know y I agree um is there any other question questions from

anyone I'll take it as a no so once again thank you very much Carla for for doing this presentation it was really nice to be honest I really liked it um and thank you everyone for for attending and spending the time here uh I'll see you I'll see you around thank you Carlos goodbye cheers byee thank you everyone bye