Revisiting the Nova Proof System on a Cycle of Curves - Wilson Nguyen

Transcript

oh yeah preferences okay so I'm going to minimize oh sorry everybody you have it all good yeah so yeah just as introduction uh hello everyone uh we are in another learning situation session uh today we're gonna We have basically Wilson with us Wilson who's the author of one of the authors of visiting the Nova proof system or the Nova hack paper at least how some of us we call it uh he's gonna basically go through all of the review uh of the Nova proof system in the instantiation of the cycle of Curves on it uh give a detailed explanation over the entire protocol in

paper and the revision that they did and also kind of the IBC compiler or the structure that they have come up with uh after that as usual we're gonna have a q a session where anyone is free to ask any questions about the paper or the presentation so I headed to your Wilson thank you very much for being with us and feel free to start thank you for having me uh so today I'll be presenting our work revisiting the Nova proof system on a cycle of Curves this is Joint work with stamponee and SRI lassetti from Stanford and Microsoft research oops there so incrementally verifiable computation or IVC introduced by Valiant

in 2008 is a method to prove the outcome of some continuous iterative computation so you can imagine you have some a base element zero and some function f and you want to prove the claim that zi is the result of applying this function f i times on that original value so when would this actually be useful well some modern day examples are you want to prove the outcome of some verifiable delay function and so in this case f is just some slow to compute function and Computing at I times should take a certain amount of time also ZK EVMS so ZK VMS you can think about as state machines so now the Z's end up being States and F is some State

transition function so you want to prove that after I steps of some State transition you actually end up with that final state so our work how does this fit in the context of everything we describe a sound as vulnerability in the original implementation of the Nova IVC scheme we implement the attack generically for any choice of functions but to particular to demonstrate the vulnerability we generated a fake but accepting proof of 275 iterations of the minroob PDF in only 116 milliseconds so if this IVC scheme had actually been secure this would have taken thousands

of years so there was a natural vulnerability and in this work we also patch the vulnerability improve uh the patch is actually secure so we provide a secure compiler from folding schemes to IVC over a cycle of Curves so what should you take away from this talk we're going to give a brief intuition on folding schemes they're not the main focus of this work we're going to construct IBC over cycle of Curves from these following schemes and then we're just going to go over the original vulnerability in Nova so a brief detour to following schemes

uh but in order to discuss following schemes we'll have to know the structure of the elements and so I'm going to do a brief review of rncs hopefully this is a review so rmncs is a constraint system which consists of three matrices a b and c and an instance witness pair xw which are just vectors over a field uh satisfy this constraint system if they satisfy the equation on the right so the Matrix Vector product of a z uh hadamard product BC equals CZ so this is just a had more products just a component-wise product and so Nova introduces the notion of relaxed elements yes so this is a as a in the name a relaxed version of orange yes so instead of an instance when a

square x w we now have uh UW which also contain commitments and openings to commitments so U here contains two extra commitments over some group which is a witness commitment and now in an additional error commitment and so they satisfy a relaxed notion of rncs where you additionally shift by an error vector and you also scale this matrix product by a scalar s and so hopefully this is a hopefully this can be seen as a direct generalization of rncs just a more relaxed notion but because it's a direct generalization of rncs we can actually test whether a particular instance uh you satisfies

rncs about any error in particular we just check if this error commitment is a zero and if the scalar is just one furthermore since we have this option to scale and also add an error Vector it actually is Trivial to come up with um arbitrary pairs that satisfy a relaxed irons yes so think about these as just for any constraint system we can just generate these pairs and it'll just satisfy that constraint system so what are following schemes then the the main motivation is to be able to reduce the claim that a pair of incidents Witnesses satisfy rncs to a claim that a

single pair satisfies some constraint system so a falling scheme consists of a pair of algorithms this time a folding verifier which takes in two instances and reduces it to a single instance and also a folding prover which takes in addition the witnesses and reduces the pairs to a single pair now I've omitted some other items in the true folding scheme but I think the main gist is that you reduce the pairs down to a single pair someone's mic might be on yeah um okay so why do we care about a cycle

of Curves well in order to construct IBC we'll actually have to specify the the folding verifier in a constraint system itself and so the folding verifier consists of a random linear combination over a field but also a random linear combination of the group elements in the instance itself and so this will require a group operation and so expressing field operations and field constraints is is pretty simple but how do you actually represent group operations as field constraints so this will require us to actually take a non-black box look into the commitment scheme so zooming into those operations uh the

group is actually an elliptic curve group whose base field is a different field from the scalar field so this field is of order p and this group is of order P but now this field is of order q and so what is a base field well each group element can be represented as a pair of field elements that satisfy this elliptic curve equation here and so the concrete representation of the group element is over a different field than the actual scalar field of that group and so expressing group operations over their scalar field will actually end up reducing down into the problem of how do you represent uh foreign field operations as

um as the scalar field constraints and so the way I think about this is that you just perform a lot of non-native arithmetic so it's like representing a modular multiplication and addition but over a different field and so it turns out for each group operation this ends up being quite expensive but we just said that this group is represented as elements of ref Q so why not just Express those group operations over the base field instead um and so that motivates the need for two different constraint systems but also a cycle of curves so I'll explain what a cycle of Curves is in just a moment here so a cycle of Curves is a pair of groups

one group has its base field over fq but has a scalar field over FP so here so this group Has a Field a scalar field of order P but it's a base field is a different field so that the concrete representation of these group elements is actually over as a pair of these field elements and then another group uh whose scalar field is the base field of the other curve so now we represent oh yeah so this so this is a vorticube and this is a vorta q but now it's base field is the other group's scalar field so a cycle of Curves basically just reduces down to two elliptic curve groups where the scalar field of one

group is actually the base field of the other group now if this uh didn't make total sense I think the um the implication on the next slide is what's actually necessary but this cycle of Curves is just needed for basically the efficient folding scheme to work out so the core idea is that you have some constraint system over one field and we have their relaxed instance witness pairs to fold those pairs we can actually represent this folding verifier efficiently over some other constraint system over a secondary field now this constraint system has their own

relaxed instance with this pairs and to constrain that folding algorithm we can actually Express those as constraints over the primary constraint system so now the difference is we have two constraint systems over two different fields Each of which with their own relaxed instance witness pairs the folding of those pairs we can represent efficiently over the opposite constraint system so now the difference is we have two types of relaxed instance with spares and also two different constraint systems over two different fields so recap so far we described IVC as a

method to prove the outcome of some uh continuous iterative computation we discussed a rough intuition on what folding algorithms are as a pair of algorithms of holding verifier and a folding proverb and we discussed how to efficiently constrain folding verifiers over two different constraint systems so now we actually have enough to discuss our compiler from fulling schemes to efficient IVC over a cycle so what changes with the cycle now so I described a very simplistic version of

IVC but what does IVC over a cycle so this was standard IBC so we had one function we also had one constraining system over one field now as you can imagine we have two functions operating over two different fields and now we have two constraint systems operating over two different fields and a hint is these constraint systems will be actually the training systems that we saw prior foreign so now what is the claim of IVC in this in this new setting the claim is that we're actually going to prove I evaluations of the pair of functions over a pair of values and a

pair of claimed evaluations so I'll have two claimed evaluations two base case values and two functions the IVC verifier will take in this claim but also some IVC proof and accept or reject now we'll actually have enough to give a brief intuition on on how the IVC prover actually performs their steps so if we look at this diagram here the most natural interpretation of when IC approver does per step is they perform one step of both functions so here I describe this these are the different

IVC steps and each input is you know the function input and the function outputs now how do we actually approve one function execution in each of these steps will actually prove the satisfaction of two different constraint systems and these constraint systems contain in them the actual constraints which constrain the function so this constrained system applies one step of the function F1 and this Prime and the secondary constraint system uh proves one step of this secondary function so to reiterate what we're looking at is a diagram of the IVC prover execution

and at each step we're attempting to prove a set of executions one for F1 and one for F2 in order to do so we prove the satisfaction of two constraint systems now diving into the IVC construction a little further proving satisfaction of a constraint system doesn't end up proving all eye steps it only proves um a single step so how do we actually end up proving that we performed all I minus one steps appropriately

well the satisfaction of one of these constraint systems or the execution of one of one step of the function we can represent as a natural relaxed instance and then after I iterations we'll actually have I of these instances and so if we think back on our folding intuition we're reducing the claim that we have two satisfying instances to one satisfying instance so ultimately what we would like to do is to accumulate the satisfaction of all these constraint systems into instances which we'll label as these accumulators so if these accumulators are satisfied

then all of these individual instances were satisfied meaning that we actually applied I iterations of the function so that's uh the main goal is to produce these accumulators so zooming into the step further in addition to taking in the function inputs or the pair of function inputs each step will take in an accumulator or a pair of accumulators for all prior steps so this accumulator represents the satisfaction of all these constraint systems on the primary and this represents the satisfaction of all the

secondary constraint systems in addition to the accumulators and the function inputs we also take in a strict instance so this instance here will actually represent the satisfaction of the prior secondary constraint system so I've labeled in green what is a strict but satisfying instance so this constraining system so I lied a bit earlier it not only applies one step of the primary function but also does a folding step so it takes in the secondary accumulator and also the secondary strict instance

and folds them to produce the new accumulator so it does so this constraint system does a single step of the function but also folds the opposite instances now the satisfaction of this constraint system we can represent as another instance for the primary constraint system and similarly we apply one step of the secondary function and the secondary constraint system but fold the opposite instance plus the accumulator we have as input to this step

and now the satisfaction of this constraint system can also be represented as a strict instance a strict instance for the secondary constraint system and so if we look in at the inputs and the outputs of every IVC step they're the same function inputs function outputs a strict instance for the secondary constraint system a strict incidence for the secondary constraint system and these are the updated accumulators and these are the accumulators for the prior so if these accumulators were for the prior I steps these accumulators are for the prior steps plus the most recent constraint systems so we just updated the accumulator we

applied one step of the function and now we also have another strict instance here and that's basically what the irvc proof does at every step so it starts off with just the base case values some arbitrary beginning instance and some arbitrary accumulators and then just apply as the steps repeatedly so now that we have the rough structure of what the IBC proverb does every single step what actually are the constraints uh within this augmented constraint system so here I'll describe the primary uh constraint system which is over the first field but you can imagine the secondary constraint system

is actually just symmetric but you switch all the twos for ones and all the ones for twos so in addition to taking in the function input and both instances so this is the accumulator and this was the strict instance we saw earlier we also take in an index which will help us keep track of what index we're operating on but we'll also forward the original base value so at the very very end we at least know what the original base value was and now this instance here is now a little bit different so remember how a relaxed instance was comprised of two commitments but also some instance X so in this case our instance will be two

hashes so x0 you can think about x0 as constraining the input elements to each constrained system and X1 is constraining the output elements of every constraint system and so here the first check will actually be on x0 so the input instance it's x0 contains all of the elements in the witness so we can see here that this hash simply just constrains all of the input elements furthermore we just check if this instance we took in as input is actually strict so it actually is the satisfaction of the prior constraint system without any error

then we apply one step of the function and also we'd apply one folding step and now the instance checks so remember how I said X1 was used to constrain the outputs of each constraint system so the outputs are one increment on the index we forward the base value and then we also include the function evaluation and the new folded accumulator and so this structure here is actually the same structure as this x0 hash but now there's a special uh copy constraint here which is actually very essential for the the vulnerability but also the proof of security

so what does this copy constraint so this copy constraint copies the output hash of this prior instance into the input hash of this other of this next instance and so basically what this x0 X1 swapping does is it makes sure it makes sure that we're actually aligning the hash checks with the appropriate constraint System since we're swapping back from on cs1 to our own CS2 turn on cs1 we want to make sure that the inputs connect with the right outputs so uh I've I have a diagram in the next slide but I'll pause a little bit so that we can absorb this constraint system a little bit more

so we have input checks output checks and we apply one step of the function and the folding verifier cool okay so why is this uh copy constraint actually necessary I've labeled in purple um what is uh needed for the first constraint system and I've labeled an orange what is necessary for the secondary constraint system so each instance has two hashes x0 and X1 x0 and X1 x0 and X1 and x0 next to one

now what is this so first let's discuss the hashtags so this is just the uh hash check on the inputs for this constraint system and X1 is a hash check on the outputs for this constraint system and now ideally we would like to forward that to the next instance so here you can see this copying straight I've represented as an arrow if we follow the diagram here all this copy constraint does is it just makes sure that the output of rncs1 will end up being connected to the input of rncs1 but in a later step and similarly for the secondary constraint system this copying constraint make sure is that it makes make sure that we connect the output to

the input for the secondary constraint system so because we're swapping between two different systems we have to swap the input and output hashes cool so now we have enough to discuss uh what IVC verification does so the new proof uh for IBC is actually just the output of a single IVC step so it was both accumulators but also the last strict instance so this instance

here represents the the satisfaction of the last constraint system and then the accumulators represent the satisfaction of all the prior constraint systems so the verification algorithm takes in the claim as we described earlier but this IVC proof pi it checks if this last strict instance is actually strict it checks if all the pairs satisfy their respective constraint systems and then this is where the Special Report comes in we check that the x0 part is actually binding the outputs that we claim plus the accumulator that should have

been folded in the primary instance and then we check that the output of the secondary constraint system ends up being the last secondary evaluations plus the accumulator that we have in the proof so both these hashes bind both these accumulators but also binds the claimed evaluations and so the reason why we're checking the x0 instance here for all the primary values uh is because this constraint system has a copy constraint so this actually ends up being the X1 of the primary instance and so it turns out that uh this is actually secure and this actually was the fix that we applied so we proved

this secure in our paper as the secure verification algorithm now what went wrong in the original Nova implementation well the proof Pi didn't consist of those three elements the diagram for the prover is actually way different it includes an additional element um over the primary instance so this alone does not actually cause the vulnerability but it's sort of the way they had the intuition on the implementation that caused the verification algorithm to be a little bit different because this element is actually unnecessary so this is the vulnerable verification algorithm so the verification algorithm takes in this modified proof in addition

to all the checks so these are the checks I've labeled in Black it checks whether this instance is strict it checks additionally if this instance was despair are satisfy but now this is the key difference the very subtle change that caused the vulnerability so here we checked um the secondary instances x0 there was the hash of the following elements and similarly the hash of the primary elements but now we checked that this instance is X1 so this is the output hash for this constraint system were these elements now this seems reasonable right we have two constraining systems that were repeatedly proving the satisfaction of

and so you would expect that I can just provide um the primary instance and its output should actually just be the output evaluation um that isn't actually supposed to be there but it turns out that if you do this there actually ends up being no constraints on the x0 hashes and because there's no constraints on the uh the X ear hashes you can actually split this verification algorithm into two sets of independent checks and then that will allow us to actually generate a malicious IAC proof so now we can actually talk about the attack

foreign so what I've done here is I've just added a space so I've represented the vulnerable IVC proof and I've just segmented it into two halves so I just put one strict instance one accumulator one search distance and one accumulator and so it turns out that if you look closely on the um the vulnerable verifiers checks they actually can be split into two independent checks that are actually symmetric so we check if this strict instance is strict if both pairs are satisfying and if the X1 hashes a line with this accumulator here so here oh I think I might have a typo here

this should be oh okay so I have a minor type of here but it's okay we can we can run that for now um this should be oh sorry okay so the typo is that this should be over here and this should be over here sorry so I just check if this instance is strict and both pairs are satisfying and then that this accumulator is actually contained in the output hash of this so in a sense we claim that this accumulator was the result of some folding of this constraint system so the attack overview

um so we can actually claim and uh so we can actually claim evaluation for an arbitrary set of starting values so it doesn't you can just the attacker can just choose any starting values they want it won't matter in the end and you can also choose any arbitrary pre-images so these are pre-images uh to one function execution so the claimed evaluations that will prove I will claim I evaluations um of some evaluations AI which are just one function application of these and so these can actually just be any arbitrary pre-images so they don't have to be actual the results of I minus 1 executions of the function you can just choose arbitrary values and so the first step oh sorry the

Second Step will be to generate malicious pairs um from for half the proof and then since the checks are symmetric it turns out we can actually symmetrically generate malicious pairs for the SEC uh for the other side so all we have to do in the algorithm is actually just to flip all the twos to ones and all the ones to twos and it turns out everything works out and it's because these checks are actually symmetric and then finally we just output the malicious proof so we just concatenate the malicious pairs that we uh that we generated and this proof will end up being accepting so how do we actually generate uh these malicious pairs that align with these starting values

and and these pre-images so we'll actually end up running the honest prover for one IVC step but on maliciously crafted inputs so here we have a malicious uh strict instance where we it doesn't actually have to be satisfying and so this I've labeled in red all the non-satisfying instances I labeled in green instances that are actually satisfiable and so we basically just cook up this malicious input instance and so uh we don't actually don't care about the Commandments here and we don't

care about this scale here because we don't actually need this to be satisfying so I set x0 to be the hash of basically trash values it turns out that we won't actually end up caring about these trash values so it doesn't even have to be satisfying this accumulator and this Z value Humanity arbitracy value but what's important is that we cooked into this X1 hash the claim that we performed I minus 1 iterations and that we use the basic case value and also that we use the pre-image that we desired uh this accumulator here will end up being we'll just use um so at the very beginning of the of the presentation I said that you can just come up with arbitrary pairs that

satisfy the constraint system and so here we literally just have an arbitrary pair uh you bought that satisfies the primary constraint system and so we prove first the satisfaction of the first constraint system so remember the function inputs so here I have a strict instance I have some claims accumulator and also the function input from the prior step so we mod we uh sorry we cooked up this x0 hash so it actually passes the input hash check so this hash check is satisfied and then this X1 hash gets forwarded to the next instance so we just have this copy constraint here and then this output hash check is just

it's just trivial so it is satisfiable just because we've we made it satisfiable so I've labeled them Brown well we'll end up just throwing away because we won't actually care about it and so now we perform the the second half step of the IVC approver so now we take in as input the pre-image that we desire for the secondary function the um the satisfying accumulator you bought and then this actually ends up um satisfying the hash check sorry there is a typo here this should be U1 here and so because we satisfy the secondary constraint system

this hash of arbitrary junk values will end up being forwarded to this x0 element here but we don't actually have n the verifier checks don't check anything about the x0 elements and so this x0 element could just be trash so this hash doesn't really matter since we never even check it uh and so we engineered uh the X1 hash so when it's forwarded to the secondary and since it actually passes all the hashtags and now this secondary instance has a hash of all the desired elements in the verifiers check so we've claimed that we have had eye iterations we're using this base value we wanted this Z value and now what is

this accumulator here so remember the verifiers check only required that this accumulator is satisfiable well if we remember the what the constraint system actually does it folds into this accumulator the prior accumulator and the prior instance so since this instance here was actually um represents the correct satisfaction of this prior constraint system we actually did like you know execute this constraint system and here this is just some you know defaultly satisfiable accumulators this is some trivial element since we folded two green or two satisfying instances this accumulator is also just satisfiable and so if we look at all the checks so I

just pasted the rightmost side here is this a strict instance yes do both pairs satisfy ions yes yes by construction and then there's this hash end up being the hash of the claim and the accumulator yep we engineered it so it was just so and so all these checks end up passing and so now we just need to generate the malicious pair uh for the other half the proof and just paste them together and that ends up creating a false proof that the vulnerable verifier actually accepted and so we actually provide a generic

implementation of the attack and just to reiterate we generated a fake proof to the 75 iterations of the mineral vdf uh which in 116 milliseconds which would be impossible if the if the scheme was actually secure so in conclusion the moral of the story is to always make sure that you have a proof of security of what you meant or at least there exists some proof of security of what you implement and there's now an efficient compiler from folding schemes to IVC over a cycle of Curves and uh be happy to take questions oh

thank you very much Wilson this is these were really really cool um I guess I would start and break the ice a little bit um so how do you came up with that like what what was the like is that you looked at the paper or the implementation and like somehow you saw it directly did you what you're running like some kind of analysis over it then then it's how you catch the thing like how they spoke uh so I actually um wanted to write an sok um which is like a basically a summary of all the focus games out there um but there was one thing that was missing and so I was reading the Nova paper and I was like okay this this works out you know produce are all these

works but the one thing that was missing was an actual complete description of how um Nova was implemented over a cycle of curves so the original paper did provide a table of the number of constraints on each curve but didn't really um describe the operation of the of the prover at all and so I was like okay I don't I don't know what's happening uh and so I read Justin Baylor's textbook because he wrote a section on this um but it turns out that his discussion of the cycle of Curves was only a footnote but the footnote was like half it was like a half a page um but it didn't really provide an intuition on or okay maybe it does for some people but reading that I couldn't

really tell what was going on and so I was like okay you know what I have to just do the grunt work and so I just went through the code base and just reverse engineered every step until I was trying to figure out what was happening and then I was like okay there's no way this works like uh like there's no constraints on x0 and so I was just like trying to think of like you know why you know I was trying to do the extraction proof like the security proof and I was like there's no way this works out uh and so I was like okay you know what I'll just try to put junk values in x0 right and so then I just you know just coded up something really quick you know I of course my initial code was a little messy uh but then it just verified I was

like no there's no there's no way like maybe I like ran an old version of the file or something like that and so then I just kept on running it and I was like oh okay so it actually it actually does work and so then I reached out to srinath and then we were discussing about like you know what are potential patches and so we settled on the fact that um you could just remove the instance since it wasn't actually necessary but that came after some discussion of like how do you actually um prove a successful extraction and so this clean diagram sort of uh only came up like a little bit later thank you thank you very much um we have some questions in the chat if you want to read them yeah I'll I'll try to answer them uh in terms of uh ease

first and then and then I'll go to the little longer questions uh can you share a link to the slides so it's actually a keynote uh presentation so I'll figure out I'll coordinate with Carlos how to how to share the the slides um maybe I have to upload them to Google Slides or something um what was the name of the textbook you mentioned so Justin thaler uh has a textbook I think it's called proofs arguments and zero knowledge so Justin Taylor I'll just type in in the chat so if you search him up Bill show on his webpage uh is there an ongoing effort for implementing an IVC to cycle fold compiler uh I think you mean sorry do you mean foldings sorry do uh so cycle fold is a different compiler

from folding schemes to IVC over a cycle of Curves uh I am not sure if there's you know maybe you could speak more on this Carlos I'm not sure if there's people implementing it just yet but if you are going to implement something I guess uh I think cycle fold is a little bit cleaner so this was like the this paper is like probably the first iteration of those compilers but I think because if you only care about computation on one field then cycle fold like makes sense um if you want to do basically some Dynamic interaction between both constraint systems imagine you had some type of uh uh we call it a state transition function where you actually do the state

transition over both Fields then you know maybe there's a little bit more this our compiler is a little bit more generic um but you know there's trade-offs so it just depends on the use case wait did that did that make sense the the answer or yeah you can always ask follow-ups I guess since there's no other way to win um I have another question then which is so these yes yes so oh sorry uh srinath sorry yes yes that is true if you put the function inside of the cons the if you put the function inside of the actual uh other constraint system then you can actually execute the

function itself but plus um also defer the the group operations to the secondary constraint system and so oh you know what actually maybe you can handle State transitions too uh if you put the state input into the the secondary constraint system but then if you do that I think you have to make the secondary constraint system do hashing to make sure that you've compressed the state but uh I think cyclefold is just uh just better so people should just aim for recyclefold I don't think there's going to be real um other use cases for for this original compiler so I got another question which is um so being here in the previous uh

learnership uh said that your compiler was basically one that we can plug in in protostar and everything should work uh fine so in hypernova what this also what would this be be also a compiler that we can use for hypernova although we are folding end-to-one influences like does it make any difference at all or it doesn't because we make it inside okay okay so yeah if you if you want to fold uh multiple so if you want to do a tree style folding I think cycle fold is a little bit easier to reason about the logic um but if you wanted to use this style of compiler you basically have to alternate levels in the tree being

different um different curves it's like every level has like two levels basically but that becomes a pretty uh pretty intricate and so I think cycle is probably a little bit more I think they mentioned also in the paper that so it's more appropriate for that um yeah so Benny asked if the how do you compare the efficiency of this paper compiler to cycle fold so uh so what is the total computation so the primary instance in cycle fold has to fold um has to do with scalar a native scalar multiplication but then also fold instances on the opposite curve uh but also it has to do its own hash constraints and so what we so what cycle fold ends up doing is they actually

remove the need uh for non-native arithmetic for the primary curve but you so you have like one but you still need non-native arithmetic to fold um the secondary instances so it's like one non-native arithmetic and then uh one native scalar so yeah sorry one non-native arithmetic and then one uh group operation but sorry two group operations but both over their native constraint systems and so our compile also there needs to be a hash track but are so but our compiler we do two hash checks uh for the input and output instances and then we also do two non-native arithmetics and also uh but

two group operations over uh the native field and so cycle fold is cheaper in the sense that you don't have to do you don't have to do one non-native arithmetic but also you don't do the hashing the one one of the hash checks but the trade-off or I guess the point is it's a cycle fold like maximizes the amount of work on one uh over one constraint system and minimizes the work over the secondary constraint system I see things that means he's strictly better in any cases or not like because I saw that there's there's some trade-off in cycle curve in uh when you want to because you basically want to add some folding operations or or Nova

inside the inside the inside the circuit right uh yeah so what you so the trade-off is that um your primary instance is bigger wait sorry etching sorry no no it's not sorry the reference is that so it's not sorry sorry my bad the primary instance is not bigger because uh in our compiler we had to fold the opposite instance anyway so that was already present right I guess the from my understanding is that a cycle called removes all the non-native uh scale operations in the original uh folding uh verifier but it also adds another folding verifier for nobody in order to fold all those group operations right yes so you need to do

yeah so you do need to do non-native arithmetic for the Nova for the Nova folding folding in adapt involves some group operation as well right one one group operations no man oh sorry uh added some clarification so maybe this will help here uh to add a bit more psycho photos strictly better for flowing seams that have more finite field uh hash operations yeah so okay yep and then for no so just to reiterate uh for the recording because you know maybe the chat's not recorded uh srinath said to add a bit more cycle fold is strictly better for falling schemes that have more finite field operations and hash operations you know such as hypernova ProStar Proto Galaxy for Nova it moves the gates from the second curve to the first uh to the first curve

as yeah sure yeah so I I think in terms of Simplicity uh and concrete efficiency if you if you only care about like you know actually just doing an execution of a function on one field I think cycle curve is uh cycle fold is definitely probably the better approach also because it's a little easier than to reason about um the 3D folding also the design that leaves you with only one proof to to perform right like you just need to make one snack at the end not two uh no uh sorry uh you have to check that the folded instances

um in in the sorry this because there's there's still two instances you need to check oh but right because you I thought since it's within the folding step that you include that like Allah hypernova basically so subject here it was the same yeah genuine yeah so the the output of this of that constraint system will be um will have an accumulator and so even though you fold these accumulators you still have to check that the accumulators has viable so yeah so that's the yeah exactly yeah yeah I do also have another question uh which

is more like on your vision uh on split accumulation versus folding for me one thing that is clear is that we have a logarithmic ghost of aggregation in Split accumulation whereas we have a constant ghost for folding and the size of the things is constant in both places folding is also paralyzable while split regulation is not since the randomness that you need in order to fall in order to solve in order to aggregate into the folded instance you need to coordinate the randomness so you get a Randomness for the IBC you do whatever operations you want to do you put that it on the top of

the ABC and then the new Randomness is what someone else takes to build on the top again whereas in folding this doesn't matter like you can you can fall into one whatever you want just it might be more expensive or not or whatever is there any use case on which it makes more sense to actually use a split accumulation rather than folding in like in your perspective sorry I might be a little bit confused because um to me uh folding and split accumulation are just the same names for the same things but you could also be referring to the original original split accumulation yeah exactly yeah style basically

oh oh Halo 2. so I guess sorry uh so the Halo 2 stuff they call it um there's sorry there's the formalization of that is called accumulation yeah uh uh so I I don't I don't know how much I can uh uh comment on that so I don't know the uh the the OG accumulation schemes but I believe you just accumulate just all the you just batch all the pairing checks at the end right is that the is that the idea or yeah and at the end you do linear work in case you're using IPA for example this is what like the original Three logo that's in my understanding at the very least okay so uh yeah I'm not sure if I

uh cool are there any other questions that we have uh maybe in the chat or if someone wants to speak yeah yeah if somebody wants to also if sure if you want if you want to talk about a cycle fall as well you know this will also be a perfect opportunity um but yeah no pressure as well I'll leave 30 seconds for anyone to write or speak and otherwise we will either let's win at all or conclude the the presentation

whatever you prefer oh uh benchmarks uh so uh you can actually run the so the srinath implements the fix and so the fix is in the original Nova um it's in the original Nova code base and so if you search up uh Nova Microsoft GitHub you can just run it yourself but also make sure to compile it in um add the release option because uh the original um the original run of this paper I said 1.46 seconds to generate the fake proof but Trio point out that I ran it in debug mode not a not release mode so so now it's 116 milliseconds

uh I'm curious where major differences in between the performance before and after the Patch was applied yeah so if you so uh one is we remember how the the vulnerable proof had the extra pair so now the extra pair is not there um but the difference is that uh it depends on if you're checking the compressed proof or or the non-compressed proof right so the difference for the compressed proof is like negligible but then you cannot um you basically can't continue the IVC without doing recursive snarks but if you check the recursive snark by itself then we've removed uh one one of those pairs so it's like you cut it by one-fourth

and so it turns out that you can actually then because there was like a strict instance on the secondary and a strict and a strict accumulate sorry a strict instance on the secondary and an accumulator on the secondary you can actually fold those two together and so then you end up only with um two pairs instead of four pairs and this comes at the cost of an extra scalar multiplication right so you try you trade off memory by like CPU time basically uh no so the uh you can actually fold those um two instances without like not in a constraint system you just provide um yeah yeah you just fold them you just uh you give them okay thank you thank you

thank you thank you okay so we don't have any more questions so thank you very much for your dog Wilson thank you very much for being with us thank you for having me and nice work everyone and thanks for being the session cheers