Deep dive into Protostar paper & protocol - Binyi Chen

Transcript

nice so hello everyone and welcome to another uh learn and share session uh so they would have uh Hindi who has been one of the authors of protostar which is one of the latest improvements or or papers in the folding schemes landscape he will be giving us a few words through uh across the the entire protocol uh and then we will have like an extensive q a session where if anyone has any questions or anything like that he will be able to respond to any of our dots

so yeah I hope please ask to not interrupt during the presentation and then once we go to the Q a session uh I mean you will be able to share also the paper and make notes on top of it or whatever it is so that we can all uh ask for our jobs and get some some replies so so when you thank you very much for for attending and joining us and being able to share all of your knowledge on that topic whenever you want feel free to start yeah thank you Carlos thanks for introduction my name is pingi and today I'm gonna present protostar which is a new generic but also efficient IVC schemes and this is a joint work with Benedict from espresso systems and also

I heard that like most of the audience today are already familiar with a lot of a lot of backgrounds our only require recap background really quickly and focus more on the details broadstar so the men the main goal or the main problem this paper one study is to try to prove the correctness of some iterative computations so you can think about there is a step function f and we want to prove that some iterative computation executions of f for running many times are correct so basically there's a one final output and there's an original input and in each intermediate step we run this F function on the previous input and with some online witness W Here and Now formally

the prover wants to prove that given the this final output and the original input there exists some intermediate weakness such that each intermediate execution of the step function is correctly executed so this model of computation captures a lot of scenarios that can be very useful in the blockchain field like verifiable delay functions and succinct blockchains like Mina and more recently the zkevm or ckvm applications where you approve that certain evm transactions are correctly executed which consists it consists of a lot of op code executions so that's the background and to to solve this kind of problem actually already

back to 2008 core villains already introduced a really elegant notion called incrementally verifiable computation so now instead of directly sending all this intermediate witness and the to the very file and will verify just do recommutation and which will be really expensive what we do here is that prover will iteratively generate some proofs like this Pi M here given the previous proof and previous input as well as the intermediate witness here and after that the verify instead of receiving all this witness only needs to now receive this final output and this small proofs here and check if it's a exception not and we if it's acceptable

then the verifier will be confident that all the previous execution are done correctly so we need that for a if the proof are honest meaning that all the previous approvers are correctly generates the computation and the proof they must be the case they can they can actually generate a correct proof that can pass the check on the other hand we require that if the verifier can accept some proof some IBC proof that means the corresponding prover should actually know the valid witness this is not just some intrusive definition but this is the intrigued idea what the knowledge soundness is and this is you see that here we only consider a chain of computation

but more generally the proof com the proof or the computation doesn't need to be your chain you can consider like a tree of computation or even more or uh like more General topology of computation like a diag of computation and this is this generalization is called proof carrying data which covers the IVC example and we know that all the techniques in this paper can generalize to PCD but for Simplicity let's just focus on IVC in this talk okay okay so it is well known that this IVC scheme can be constructed from snarks at the ideas just to let the IVC proofer to generate a snack proof proving the

statements that the last execution the last step function execution is correct and the previous IBC proof is correctly verified but it's not verify so this is basically a recursive snark and the idea is quite simple however this kind of scheme is not very practical the main reason is that the first is because of the use of snark and snack verification is usually not that's not friendly so it's it can have a really expensive recursive verified circuits and also because of the use of the snark you might need some electricity setup or use some parent-friendly Cycles which might be slow so given this many researchers are

trying to explore whether it is possible to construct an IVC scheme without the use of snarks and one of the most I think one of the most popular Direction recently is exactly the folding scheme or the equivalent equivalent notion of split accumulation scheme proposed by Nova and another paper uh this paper from TCC which also introduced some very similar notion and some similar results so what is a folding scheme or a accumulation scheme uh the idea is the following so we have like given some MP relation R which consists of some like small instance parts and a large weakness part

the goal here is to try to do the following so given two different instances with the Spheres we want instead of directly checking the two instances are satisfiable we want to First reduce the task of proving two instances into one so basically we'll just merge them into a single one and now we can it's sufficient to just verify the single instances and folding is exactly the intermediate step of of like merging these two instances and it consists of the following three algorithms the first is so-called accumulation prover well given two different instances with transpares the prover will try to fold them fold them into a single instance with this pair X

and w okay and the second algorithm is an accumulation verify which will check that this folded instance is correctly is the correct one so he will be take input of two instance X1 X2 and he might also get some info some metadata from the accumulation approver and check that the output instance is the correct is the correct folding instance from these two uh instance and we note the Highlight here is that usually the accumulation variable can be much much more efficient than the snock verifier and this is the key reason why the IBC from it can be really really efficient and finally after folding these two

instances with spare and well we get a final folded with instance witness pair the decider will just finally check this xw is inside the relation so the complete requires that as long as the original instances are satisfiable the folded one must be also satisfiable and second is that as as long as the prover generates some weakness that pass the check it must be the case that he also know the original two witnesses for the original two instances so that's the intuition of the property that the folding scheme is to satisfy uh so it is well like some previous work like Nova and also BCM LMS 20 they

already mentioned uh and like IVC compiler from the accumulation scheme so I won't talk too much about this part so the main idea is now to in a circus instead of uh embedding a snark circuit you only need to embed an accumulation verifier circuit inside which is much much more uh efficient and has a much smaller circuit and that's the key reason why we have we will have much more efficient IVC approver if we're using accumulation scheme so because this is not the main topic of our paper is already done by Nova and bcomms I won't talk too much but I want to mention one small thing here is that in the IVC verify we will run the final decider

which is not necessarily succinct so it may not be very the complexity might be linear to the size of these circuits so that means uh we can never guarantee that I receive verify is like constant size but this is fun usually because we can delegate the computation of decider to prover as well and add on add another snark on top of it and the the verification will be still succinct and this is also mentioned in the Nova paper okay so uh given this we already know there's a Nova and it's quite efficient already like the I think the request circuit only takes like two group exponentiations so why why do we want to

have a new paper and the main motivation here is to try to support for example ckevm application which we think Nova is not sufficient yet because of there are there are two missing features there first is that in Nova they are using r1cs constraint system which is a traditional constraint system that supports degree 2 Gates however is much less expressive compared to someone's recent Advanced case like high degree custom Gates and look up Gates and while we are writing this paper we also sorry we also are aware of that there are some several follow-ups like um

which is really cool like sangria and origami they also say that they can support like Planck and look up case but it turns out that it's not efficient enough if you want to support really high degree Gates the main reason is that if you want to support like degree decades the approver and the verify complexity will be proportional or linear to the to the gay degree so there will be a factor of D of e complexity here that means that will cancel out the advantage of using using this kind of hydrogates on the one in the one first place so that's not sufficient I we think we do need to solve this issue well we won't have IVC proofer whose

complexity is independence of the gay degree in particular the number of group operations should be independent on the gay degree so that's the first missing feature and the second missing feature is that for most of the current state of the Arts they do not support efficient circuit branching except for a previous work called supernova so what does it mean so you can think about in like in evm at each step usually what you can do is you can pick one of the op codes to execute right there are hundreds of op code in the in the instruction set of BM but if we are using Nova for example what you have to do is that in a recursive circuit you have to embed all those circuits for

every op code and that means the the circuit size can be blow up like if there are hundreds of optical that means the hundreds of factor blow up so what we want is that we want to have be able to select this step function or this op code at runtime but the circuit itself should be only proportional to the size of this single op code not the entire set of op code so that's the second feature that's missing in the Nova and we know that this uh these two features are exactly very essential and important for having a practical Decay evm applications and uh before uh beyond that we also know that the for previous constructions

they are usually having different proofs different constructions it would be great to have a unified framework for that and our paper is actually trying to achieve the both the Target and both goals so first we have come up with a general recipe for constructing IVC scheme and more precisely for constructing the folding scheme or accumulation scheme and in particular it can this framework can fold any special sound protocols that is interactive as long as the this special sound clockwise for some certain relation can be completed relation and moreover besides the modularity it doesn't sacrifice efficiency in particular the efficient normal scheme is just one very special

case in this framework and after that we combine this General recipe with several special sound protocols for for the relation that we have interest and by after combining that we can instantiate and construct an IVC scheme that supports really highly expressive Gates like high degree gaze lookup and the non-moon form computation and we also note that because of this modularity it turns out to be very easy to extend to some reasons like advancement on constraint system like CCS which is basically a generalization of r1cs to the degree D Gates and one sentence if like what I want to remember you to remember one sentence is

that in in this scheme the dominance IVC proving course now is only a one MSM of the size of the weakness of the computation and a recursive circuit well the circuit size is dominated by only three group operations so in particular this three code preparation is is constant it's there's no Independence no dependence on the gay degree or even the lookup table size which is we think is a great feature here and we also note that there is a concurrent work called hypernova which also achieved some similar results however we think that for lookup I think they have to Polo cup they need to work more a lot more and complexity is

slightly higher in comparison our lookup support is almost for free so that you don't need to pay a lot like almost negligible overhead for supporting Luca and on the other hand in the recursive circuits uh in terms of the number of hashes and also knowledgeable operations we have a factor of log n smaller compared to hypernova so that means when the number of case in this step function can be a lot the product star can be really advantageous okay so that's the background now let me come to the meat um so I will explain what is the general recipe for constructing folding schemes okay so recall that what we want to do

like what's the goal of the following scheme is that given several instances we want to fold them into a single instances of MP relation R and we follow some framework below the first step is to build some interactive and information theoretic special sound protocols for this relation are which turns out to be usually quite easy and we'll talk about why it is easy later but before that let's talk about step two and step three first uh so first we given this interactive protocol which is special sound for which I will explain what special sound means later uh given this protocol we can transform this interact

protocol into a non-interocument non-interactive argument of knowledge through some standard tricks standard confirmation transformation and after that one of the Innovation here is we have a generic and efficient transform for the knock verifier of this uh not arguments and we can build a folding scheme for this uh what is not proof okay which is essentially a floating scheme for the relation R because an arc proof is just proving the relation uh some some instances are in relation are however this is actually not enough okay because we still suffer from the same drawback of sangria where the complexity of the prover for high degree Gates is

large so given that we need to add one more step in order to make the efficient for high degree gain support so what we do is that after having some interactive protocol for relation R will add one more step and transform it to be another interactive protocol that's special sound however the set of the set of verify equations to be checked can be much more compressed and simpler and after that we use the same transformation here and obtain a folding scheme for this uh transform or the CV Pi here this transform interact protocol and it turns out the the final flowing scheme is quite efficient so even if the

gate degree is high the number of group operations for the proverb and verify are all independence of the degree of the of the gates or the degree of the verifier equations to be checked so that's the general idea and now let's be more specific okay so before going to the transformation let me quickly uh reminds you what a special sound protocol is so special sample is some kind of interactive protocol that might have multiple runs and by case special sound it means that are given K difference accepting transcript of this protocol we will be able to extract from this transcript of valid witness of this

relation and let's talk take a very very nice example here which is doesn't quite make sense but just for illustration when the prover wants to show the verify that he knows three vectors three witness vectors ABC such that they satisfied certain headmount product relation in particular for every so every Vector is of length n and I want to show that for every eye from 1 to n a i times bi equals the app so what is the protocol that what kind of product we can prove we can use to prove it and there's one very straightforward but also naive protocol that actually works in this scenario so what we do is that we just let approver

directly sends the witness the ABC vector and the verifier will directly check that this Vector is correct it's valid by checking all these n equations here and it's trivial to see that it's actually a one special sound protocol because every valid transcript is exactly one valid witness for the relation okay and there are three for every interact protocol or for every protocol we have three important parameters for this protocol first is the number of runs number of prover runs in this protocol for example R here equals one because proofer only sends one times

message so like only sends one round of message to verify so R equals one here and second is the maximal degree of the each equations being checked by verify so you see that verify here checks n equations where each equation is just multiplication so that means the degree D equals two here and the third parameters L which is basically the number of constraints or number of equations being checked that verify and here L equals n because verify are checking and different equations and you can see that usually for a relation is usually pretty easy to construct a a special sound protocol threads the

main reason that is easier than directly constructing IVC scheme for relation R is that first we don't have any uh requirements on the size of the communication or the complexity verifier so here you can directly send a really large weakness to the verifier and the verify can also run a lot of a set of a lot of number of constraints equations checked for it and second we don't need it needed to be non-interactive so this makes the design and Analysis of this kind of protocol much easier so given that's the post will read for some MP relation are we already have some special sum protocol for it there's a standard trick to make it a non-interact arguments the first step is

to try to compress all this proven messages M1 to Mr which might belong to some short commitments using some Vector commitment scheme and we can obtain cr1s to CR and only at the last step the proverb will out open these commitments using the original message and which is still large so it doesn't seem quite make sense but you'll see later why why we want to do this and after having this committed protocol the the proverb the scheme will use the Via Shamir to make it non-interactive so basically instead of letting verify to generate the random randomness we will

use a hash function and the general random challenges through the trans using this transcript so now you can see finally we have transformed into nine direct Arguments for the same relation R well the not proof or the not transcript consists of two parts the first part is some small parts which only consists of some commitments and also possibly some challenges and second part is the original proverb messages in the interact protocol which might be large and we call it a w or the proof witness inside of it so now we already have for this relation R we already have a knock proof for it and we want to fold a lot of knock instances and we have reduced this

problem to for the many knock instances and you see that this this knock proof has the following format it consists of some short commitments and short challenges and also it consists of some long possibly long proven messages and this knock proof is valid or if and only if certain set of constraints or certain set of equations are satisfied namely there are all different equations to be checked well each of the equations are some algebraic degree D formula which we write it down into t plus one Parts because like this formula might have different terms some terms might have

degree D some terms might have degree one some terms might have a degree two so we split them into D plus one part where the J's part FJ is satisfying that every term in this FJ formula or exactly have the same degree J so it's quite General so you can have arbitrary degree D equation and we just rewrite into this form okay so given this we want to fold many instances of narcs and so once you first Define water accumulator or like or folded instance means and that actually is quite quite similar to a knock proof so in the accumulator we also have commitments challenges and Improvement

messages but here are there are two key differences the first is that there is a slack variable here being used which is also used in Innova and second there's a arrow Vector commitment which commit to some lens L Vector inside and accumulator instance with transparent is satisfiable if and only if the following set of equations are are satisfied and this is also quite similar to knock verifier check except first that will pad every term into exactly degree d so how do you do that so for every term in FJ which has degree J we all multiply the power of slack variable here U to the D minus J so that this term now now

have degree D instead of degree J anymore that's the first uh change that will make the it a homogeneous equation where every term is the same degree D and second is that for every equation we doesn't need to be exactly to be evaluative zero it's okay to have some relaxed Arrow here so long as this Arrow Vector is consistent with the commitments being committed in this accumulated instance okay so that are the two key differences here and now our goal is to fold like suppose we already have accumulator and every time when we are having a new coming knock proof one to fold is not proof into the

accumulator to become an updated accumulator okay and so that's the new as long as new accumulator is satisfiable the original two accumulator are also satisfiable okay um so that's that's the problem statement let's see how we can fold these two checks and fold these two accumulator schemes and the idea to solve this problem is to stare at this accumulated check equation for five for five minutes but for now let's just there for five seconds and uh you see that key here is that you want to merge these two equation checks

so that the new as long as the new equation check uh holds these two equation check also holds so the natural idea here is to fold them using a polynomial interpolation so what does uh it mean so let's consider these polynomials which looks quite like the accumulator checks except that for every message we replace replaced it with the interpolation or a linear polynomial that interplays the message in the accumulators and the mastering the knock verify for example the message here becomes x times M plus M Prime well M Prime is the message in the accumulator and M is the messaging knock similarly we followed the challenges and the slack

variable similarly so why do we care about this polynomial the main reason is that the constant coefficient if you expand it we see that a const coefficient exactly matches those equations being checked in the accumulator original formulas check and the degree D coefficient is exactly the not verified check so then that means we can use some polynomial identity check later to prove that these two tags are correct but before that let me show an example to see why exactly this is the case so you can believe me more that this is I'm not lying and this is the case and let's prove by a very simple example

so let's suppose for instance simplistically there's only one equation to be checked so L equals one so all the vectors are with length one and the degree D of the gate is 2 and the the knock verifier check is just the R1 plus R1 Square so that is splits into three parts well F zero equals zero F1 equals R1 and up two equals L1 Square and let's see what the polynomial looks like so we expand this F0 F1 F2 using using this linear polynomial and we expand them and collect them according to the power of X and we see that exactly here the constant degree is exactly the

accumulus check well we've had the r Prime 1 here using the slack variable U so that every term exactly degree 2. and similarly the degree 2 coefficient is actually the original not verified check so you can you might believe me that this this property is actually host and now let's see how given this how we can have a following scheme so imagine like recall that our goal is to try to check these two two equations first is that the cost coefficient exactly equals this Arrow Vector being committed in the accumulator instance and the degree D coefficient exactly are zero so how to do that the idea is just

to let the prover send a coefficient form of some polynomial right and uh basically you just want to prove that's the polynomial equals this polynomial and this polynomial is degree D minus 1 meaning the degree D coefficient is just zero and the constant coefficient is just the the vector being committed in the original commitment so what approval does is to just first commit all these intermediate coefficient of this polynomial and we also know because this EJ are actually a vector of length L and they're quite long so we also need to commit them to make it short and after that we can reduce this polynomial identity check to some random evaluation check and this is

just some very standard trick well the verify just sends some random scalar and now instead of checking this program identity in order to check these two equations are holding true it's equivalent to check that this uh this this new evaluation check is correct basically you can see this is just another new accumulation check with the same structure except that every message now are replaced with some linear combination random linear combination right here so U is replaced by Alpha plus u m is replaced by Alpha M plus n Prime and the challenge also combined so this gives us a very natural way to fold the scheme and fold a new instance we

are now the proofer and verifier just updates the message they got so they'll just update commitments homologically and their instance homomorphically using random linear combination and more approver also needs to update the witness as well because as we see before the definition the approver also needs to follow the weakness so this gives us a folding scheme well in practice what you actually need to do is using via Shamir to make it non-interactive but this is General the idea okay and also I on here I only mentioned the program verify but this either is Trivial you just after having some accumulator you just

uh apply this trick these checks and also check that commitments are consistent so this is the folding scheme however this is not efficient enough for a high degree why because here the prover um performs DL group or group exponentiations because it has to commit this D minus one intermediate across the vector terms where each term a vector has a length of L and their D D minus one of them and similarly the verifier also needs to apply a deep group operation in order to fold the error to commitments using the power of alpha so that was not very good

when the degree D is really really large right because we have a factor of t uh complexity here in terms of number of group operations so we try to solve this issue and make sure that the number of cooperation is independent of the gate degree and let's see how to do that recall the reason that we have this kind of complexity is mainly because in every intermediate cross error term each error term Vector has a length L well L is the number of constraints you can think about normal constraints if you think about a smart circuit language but also um guessing about the number of equations that verified check this can be a lot right

but what if L is small suppose L is small for example L is just one there's no need to use the vector commitment to commit it to a short element right because it is already a short element and that means we can just use the trivia identity function as a commitment rather than using the palace and commitments so now the goal here is to try to compress this L difference constraints into just a single constraint and how to do that that's actually quite easy just using randomly combination again so for example let's say there is a verifier who will check two equations being holding holding true what we can do is that we introduce a new variable

beta which is random and do a randomly combination of them and now we have a new equation to be checked now which is X1 plus X2 plus beta X1 times X2 and it's just a single equation check over the inputs X1 X2 and beta and more generally supposed to have L equations over the input of e m Prime and R Prime we can merge them using the power of data well beta is the newly introduced variable That's That Is Random okay and now we only have we can like even if before there are L different checks now there's only one check being uh being

done by the verify however this idea has some issues first is that the degree of this verifier check is actually much larger because in the last term we are multiply this uh verifier check by some power beta to the L which has degree l so the K degree now becomes D plus L and L is usually pretty or very very large might be even much larger than D so it makes the scheme even more less efficient and second is that all the terms in this in this check are not homogeneous and anymore for example because different terms will multiply by different power of beta so they'll have different degree so we can

no longer use the folding scheme we had before because we had requirements that this check should be should be homogeneous in order to make sure that the degree D coefficient exactly matches the knock verify and the constant coefficient exactly matches the accumulator but this is actually pretty easy to uh to fix the idea is to replace all this power of beta by some other different variables right so basically we can make this power of beta by some other messages sent by the prover and now each space actually J is just a single variable rather than the power of beta and and now everything will be solved so this gives us following idea

we are given the original interactive protocol which is special sound we add one more round here with a verify our example or challenge an improver will send the all the power of beta as his last message okay so basically here pi equals beta to the I and the probability will send all of them and now the new verifier check becomes this we replace beta to J to be BJ and the degree of this check is just the D plus one and every term is exactly having the same degree so we can now reuse the idea we had before so you may wonder why why we want proverb to send these messages why not just let the verify how to send this

power of beta as some new messages and the idea the reason is the following we can definitely let you to do that however that will increase um increase the number of elements in the accumulated instance and usually I will see that we want the instance to be short and succinct so we don't want to do that like for example to add like ol elements in the in the short instance of course you can add smaller elements like login instance and but that also has some other issue in terms of the degree increase so what we finally choose is to let the prover send messages and because the program message anyway will be committed later using a palace and

commit to make a short element so it's fine to be relatively long well however as we see because anyway the proverb still needs to commit one more thing here one more message here that means more complexity for the approver so basically the proverb need to additionally commit to some ol terms here which can be large because L is usually a large number but this is also solvable the idea is that instead of representing a power of beta as a single variable a single message we can represent as a product of two variables okay for example um for every Power of beta that's data to the I plus J square root L we can

represent as a product of bit bi plus beta Prime J where beta Prime J is just the power of like beta to the J square root l okay so now the degree doesn't increase much it's still degree D plus 2 but the good thing here is that The Proven messages now is much shorter it's not only square root number of terms here is only square root l so the commitment complexity is much less it's only square root L rather than L and usually it's it's uh it's not very large compared to the complexity lab here already uh like paste in the previous runs however so now in summary what we have done is that uh initially we have

L difference degree D equations to be checked and of this transformation we only have one degree the equation to be checked so we don't need to use a passing commit for for it however we also introduce some other checks on the verify because the verify needs to check all this bi and bi Prime are computed correctly so that means We additionally introduced squared L more degree 2 checks for checking Corrections of bi and bi Prime but that's actually fine and key observation is that all these checks are with low degree basically degree 2 and that means now finally we'll get we'll get what we get is one single equation that has degree D and square root L

degree equation that's degree of two and we can separate them up like separate them into two parts in the one part we use still use the same Technique we will have D minus 1 cross Arrow terms which every field which every term is just a field elements and in the second part we will have a commitment for the intermediate term which is uh which is uh is a commitment it's a group element but there's only one of them so it's also independent of a degree I think is there any questions B plus k and the case root of L yes yes exactly uh so that's uh more generally you don't need to use degree two uh there's a one

question in the in the chat saying more generally you can use degree K which is correct uh and there's a trade-off where the degree will increase more but the proverb complexity can be much smaller but we find that usually sweet spot is degree 2 so we just use set k equals 2 here uh yes and yeah as we said before that's now we only need one more commitment here and I add one side one more separate commitment for the error Vector of this length squared L here and finally the accumulative verifier only is to perform R plus two group operations basically the this plus two one is exactly the final message that being

added and the other one is exact one separate commitments for this Arrow Vector of length squared l so when R equals one this means three good preparations that's exactly the number of good preparation in the product star and we note that when we want to support lookup actually there will be no overhead the main reason is that in lookup there's no high degree Gates and they are all just degree two gates and because sticker 2 Gates we can batch them together right we can batch all degree two guys together into this additionally introduced Gates here so we don't need to introduce any more cost here we just need to reuse these commitments and the number of operational accumulation

accumulator verifier won't change so that's the main reason we claim that lookup is just for free okay so in summary the general recipe works as follows given some MP complete relation we can we start with some step for some protocol threads and we transform into some another interact protocol that has much more compressed check and for which the checks are much simpler so we can have a much simpler IBC skin and after that we use standard trick to make a non-interact arguments and we use the trick we mentioned before to construct a folding scheme for that and use the traditional like typical a classical IBC compiler in the previous

work to making IBC skin so that's a general form framework and we've reduced this problem to a much simpler problem now so basically the key problem we want to solve is just to give some empty completed relation and we'll just provide some interactive special sound protocol for these relations and it turns out to be quite easy actually in particular we obtain a one move special sound protocol for permutation relations high-degregated check relation non-uniform circular selection relax relation and also CCS relation and all this protocol or four in the same trivial pattern and the pattern is just very similar to the naive protocol we

mentioned before where P just send all the weakness and the verified just check all these set of algebraic equations corresponding to these relations for example in the high degree check what we do is prove that after proofers and weakness the verified just re rewrite or recheck all the high degree gates in this in these constraint systems and because it's algebraic so it it points to the category of its special sound protocol so that's a justification that's building a market runs Better Sound protocol for many relations are actually pretty easy however there's one exception where the lookup relation because the low calculation is not algebraic basically

given the weakness itself is hard to represent a lookup relation using a set of algebraic equations over this weakness but it turns out because we we allow the protocol to be interactive this I can actually we can actually have a pretty simple protocol for lookup relation as well and the power is just inside the interaction and maybe also Randomness so let's let me quickly recap what the loop calculation is so here in the loop calculation there are a list of online lookup values you want you want to check that the or inside some pre-processed table T of of T elements and uh we are inspired by our previous work by public called log derivative for

lookup and it turns out that this lookup relation holds if and only if this this sum holds true that means if and only if there exists some multiplicity MI such that these two sum are are the same and these two some are just some sum of fractional identities the first is one over X Plus w i or wi is online witness and the second is MI over X Plus t i and you see basically intuitively Mi is just the the number of appearance of TI in this set of wi and which is also quite easy to compute so given this it turns out that we can have a really simple two-round protocols

for proving this relation so in the first round the approver just compute this witness and this multiplicity and send it to the very file and now once we have already committed all this wi TI and MI again we are just checking some polynomial identity and we can use the same trick here we'll replace this formal variable with some random scalar and check the evaluation identity here and now the approval will be responsible for computing this fractional identity evaluation and send it back H and G here to the verify and now suppose the hng are computed honestly then the only check we need to do is just check this two sum are equal right

these are are some degree one check here but however we cannot guarantee that it's always honestly computed by approver so the verify also needs to check that all hi energy are computed correctly and this gives us some more checks which has degree two okay and given this we can have a really efficient special sound protocol and we can have a coding scheme for Loop calculation as well and one great feature of this protocol is that the program message are actually pretty sparse in particular you see that even though this Vector M and this Vector G are of lens T but only at most L of them are non-zero that means when you commit

to them you don't need to pay all the like T the complexity of T we only need to do L difference group exponentiation in order to commit them into the palacing commitments so that gives us way to have a much more efficient fold improver with approver only is to do work proportional to T however there's one subtle key here because in the folding scheme remember the proverb not only needs to commit all these messages they also need to come compute an arrow Vector right compute this intermediate Arrow vector and those error Vector is actually dependence not only on the knock proof messages but also the original accumulator messenger and the original error Vector

commitments in the instance and those things are not sparse at all okay so that means uh you you do need to pay like OT complexity for computing the intermediate cross error term that is not good meaning that complexity now is dependent on t but however a good observation key observation here is that what the folding proofer actually want to Output finally is just the commitment of these intermediate terms but it turns out that those terms can be updated homomorphically given only the accumulators message commitments and the accumulative error Vector commitments and those things can be keep track of efficiently and

and that means instead of recomputing that Vector we can just directly compute the commitments and that can be required quite uh quite efficient so that's the general idea we refer to the paper for more details about this trick okay uh and finally I want to mention that this this trick can be extended to Vector lookups as well where each elements of the table can be a vector and this is super helpful for some bit arithmetic circuits like 32-bit uh xor or or some other bit operations and is heavily used I think in the CK ebm applications okay so in summary we have a lot of special sound sub protocol for some building block relations and now in

order to obtain special sound protocol for some MP complete relation like plan cop uh we just compose all this sub protocol that's it so it's very easy and it's very easy to analyze as well okay so that's basically it the key takeaway here is that we come up with a new general recipe for constructing a efficient folding schemes is not only General is without but without sacrifice the efficiency and on the other hand we also propose some simple spell protocol for some expressive relations and combine them these two gives us a protostar which is an IVC scheme in which the recursive circuit is only

dominates by three group operations but it can support absolutely High degree Gates can support arbitrary in large Blue Cup tables and can support arbitrarily many opticals in the VM instruction set and that's it thank you so much and now I can I'm happy to take even more further questions yeah that's it I see there's another question here Halo 2's they allows you to combine the costumes that's what I just need okay so in the chat there's a question called the say Halo 2's arithmetization allows you to combine the lookup with the custom Gates but that's fine just

I see let's see yeah great yeah great to know that I think yeah yeah well you you were saying that the degree of uh um uh look up words always two which is not the case in hello but it doesn't matter that um yeah it's so bad I see thank you thank you for the comments okay now do you yeah Carlos uh do I do I need to switch to the paper or I can you can like feel free to to show whatever it's called for to you to explain or to refer to your questions yeah maybe I can okay maybe I can switch to the paper I

can switch to my iPad and answer any questions perfect if anyone has any questions like just yourself first of all I I'd just like you to congratulate you on this work it's um kind of a lot conceptually simpler than um a lot of other work unfolding um so yeah uh the this looks really implementable um thank you I'm enthusiastic about about trying that thank you so much okay let me first stop Sherry and then share again okay so this is the paper and this is

the slice and I'm happy to take any questions for now yeah I could uh ask one about this selectability of which op code you use at a given step of computation could you comment on uh where the where the cost of having many op codes to select from appears or like you know as I make it more non-uniform what I can do at each stage of computation where do I where do I see the cost of that oh yes so you are saying that suppose the number of op code is large right what would be the cost usually that will be migrated to the final deciding decision

phase so basically I think uh the the cost in the following step is almost really really small uh because the first you can see this uh the searching selection step you see that this circuit selection uh maybe this one is better yeah let me show the protest star so basically we change all the all the text original permutation check to be a sum of check by multiplying some BJ so the degree only increased by one so there are mostly the the degree of the or this equation only increased by one

and there are some other low degree term like constraint you need to add so I think the folding step is usually um quite efficient uh because you see that in every step in every folding step the the witness is still only the weakness of a single circuit rather than multiple op codes but this this this equation still is like the computation right before we only need to check wi minus WC dot j i equals zero but now we need to check this sum but this sum is will be absorbed later in the decide decision phase that means the final instance of witness pair you want to check is more expensive like uh so that this that means that this deciding

complexity is more is more expensive yeah so that's the cost being absorbed but the good Advantage here is that in the each intermediate folding step the complexity is not large it's still approximately the same to that without a circuit selection yeah thanks that's helpful yeah thank you so so just to clarify that the the decision complexity is still just basically the sum of the complexity of the gates that you have to verify yes it's the kind of like some of them yeah

okay whereas the complexity at a given stage is uh only I guess proportional to the largest of this okay yes yes yeah yeah I I expect you you wouldn't expect any better than that that's pretty much upcoming that would be miraculous I suppose um I think there's another question in the chat go back to look up okay they're already answer that one right that's correct

how error terms and slack variable look like how to apply the beta trick uh yeah so that's basically the same right so you see that's oh sorry so there's another question in the chat well how error terms and slack variable will look like after we apply the beta trick so you see that actually we are not applying that track before what we do is you see here uh you see here that the first step is to transform the protocol into a new protocol that applied the CV tricks so after that we already have a new

interactive protocol okay with with a new set of equations and we just use the same trick we had before uh yeah we had before for for dealing with uh for dealing with the slack variable and and the cross Arrow terms so basically you just use the same trick so whenever you have some algebraic equations you just pad or coordinate to make it uh make it uh exactly the same degree and now it's just the this original set of knock verify check already changes after the beta trick being applied is that answering question or owner okay thank you

I can see on that slide that it says um ignore public input for Simplicity yeah um does the public input how much does that complicate things uh actually not not very complicated for example first we can assume the public input is with constant lengths using some hash tricks and then you can just see sync it as one part of the instance so you can check the paper here basically everything is the same except you add public inputs inside the uh inside the check let me see where is the just check one Escape

and check the this this verify here you see that in acc.x you just ask Pi Prime here and everything else is the same the vector is just adding Pi inside and all the folding is the same so it doesn't change uh the complexity much okay thanks yeah in the bib I'm structured in so like variable length depending on the highway system that I am in uh sorry can you repeat yeah can the the pi effect or be like EI vectors oh yeah so the public input Vector can it be like variable lens independently of the IV system that we are at Oh you mean the pi can Pi be variable yeah

because you said we can apply some cash in tricks yeah so so the idea is that we assume it to be some fixed lens but if it's public lens you can add one more circuit one more Gadget in the original step function by hashing it inside the circuit and just output the hash of it right okay so does this what does this imply for the for the folding verifier do you also need to include the check for the pi hash inside of it now yes so basically you just add more constraints for for describing this hash but that's not for the that's for not verify right that's not for folding verifier it's just for knock verify not farewell can be can be not succinct can

have a lot of constraints but the floating verify is is efficient I say thank you I had a question about the uh accumulation verifier um when you compute the alpha is it possible to with like I know this official is pretty purple but it's possible to use the uh the same cash function or for because uh it seems to me like your passion side of X twice one sometimes any broken Arc and once in Europe so accurate uh sorry I cannot hear really clearly sorry yeah yeah uh is it possible to like reuse the output of Rowan R so when

the hash function has been initialized with all of Pi dog X and then kind of chain that uh with PF because in this case you end up hashing Pi dot X twice once in with Row north and once with row X so you're saying can we just reuse a single hash function and also uh let Alpha to be like a sponge yeah yeah exactly like like um yeah you'd extract the Alpha from like the States from having hashed already the pi and Pi dot X I think at least you want to append the accumulation information inside like an example this acc.xpi and Pi dot X mpf otherwise there might be some uh attack

like for example you can reuse I think yeah I think you can just reorder the argument so that um you can compute that by that row act efficiently as an extension of the um the Ron art uh yes I think pretty extension yes yeah you can write as long as you include this information in the sponge then should be sufficed I guess yeah may I ask a question mm-hmm um sorry I missed the the front part I just noticed there's a uh there's a talk

related to protostar so I really wonder um maybe that the question is stupid but uh what what actually is the difference between the um uh scary uh sangria and protostar oh yeah so actually I mentioned that in the talk we are like you see so I I noticed that sangria also kind of supports High degree Gates that have like a proposed the uh like uh solution even though there's no like formal proof yes but there there are one key difference uh between protostar and and sangria in terms of high degree support So in sangria the number of group operations

being done by the proverb as well as by the verifier is engineer to 2D to the gate degree D so basically you have to multiply a D in this complexity so you kind of actually cancel out the feature or the advantages of using the high degree Gates so you may not use aggregate High degree getting this scenario may just use r1cs which is actually more efficient however in this in this product style we we solved this issue meaning if you even if you are supporting High degree Gates the proving complexity and verify complexity for folding is like the is still independent on the gay degree in terms of the number of group operations yeah

okay that's the answer question yeah like uh do could you like mention the the paper that like that shows this method or it's uh of course of course let me so it's this section compressing verification checks for high degree verifiers so this is one of the uh one of the most important section for you to see the tricks here I think yeah I see I see okay thank you you're welcome

in relation to the complexity that you mentioned at the end which comes from the fact that there is or apparently there's no possible representation for like the initial uh um could you like explain it a bit more because like you seem to say that you will generally pay uh only for the only for the things that are not zero basically which should be L rather than P but you end up paying D because there's no postgrespondentation for them and I understood the initial IVC instance which we give started but maybe I misunderstood them yeah so let me let me maybe first come come back

to the protocol here so you see here the folding proof the folding prover uh first he needs to come compute all the commitments for the program message in an arc that's the first thing which is actually fine right because that those those vectors are sparse so you can commit them easily usually operation but here the main main issue is here is the EJ here the vector EJ here you need to compute the the coefficient of this polynomial right and it's folded for polynomial X Plus U D minus J this one so the prover needs to come compute every Vector Arrow Vector EJ here right

and his EJ is is correlated to both the uh the Knox message as well as the accumulators message an accumulated message is not sparse for example so that means in order to do the compute this EJ you actually need to pay like T number of field operations for example right yeah but uh remind us what she was again OT is the table size yeah but we have a trick that we don't need to compute this Vector you just need to homomorphically update the corresponding commitments so you never need to know those EJ

and then you can you can make it much more efficient yeah also uh if no one else jumps into asking I I want to spend another question which is um taking into account that lookups are between codes for career at least very cheap uh have you considered to basically um try to do wrongful arithmetic for the new certified and half lookups to actually prove the the native arithmetic yeah that will helps yeah the because now we're kind of in a constraint system we can use to cover already right that

can help which is the non-native operation so that it can further improve the circuit size for those nonline field operations and I think that's one another uh advantage of using product star I think oh I think maybe you are you're asking yeah I'm asking internally like I'm asking can you get rid of the curved cycle and instead I've used this uh lookup cheap lookup properties I think even if you are using single cycle where you basically now the group operation also needs to do non-native field operations exactly right but even if you look you have lookup I think that can still be quite expensive because in for knowledge of operations even if you have

no copies remember it still takes like 20 or something 20 for a multiplication for example for just a field of multiplication and I I do think that the group operation can be really large might be really large if we don't use cycle curves I do believe if using cycle curves is always uh is always more efficient because uh still if you're using cycle curves you still need to do non-in field operations for those field operations but you don't need to do non-native operation arithmetics for group operations uh and the for the for those non-native field operation part you can still use lookup so that's why I think cycle curves can make it very

efficient but if we are not using cycle curves only single curve and then everything should be done in the non-native arithmetic Fields And even with lookup as I still think there might be some blow up so it might be still I don't know the exact number but it's just the feeling that it can be expensive but might be is fun yeah that I cannot say it because I haven't experimented yet yet yeah yeah I think so it depends on whether you've reduce the number of group operations enough that it's still okay to pay that overhead um which is kind of dependent on the exact circuit size and constants and stuff um it's it's definitely worth experimenting with yes

like I often another question which is related to like the final decider assuming you want to basically collect uh you want to basically decide you have you fulfill your ABC you have done many folding rounds and now I want to basically have a snack that is probing the entire correctness of the IBC is there anything that you foresee that is much better than any other stuff to actually prove the sum check in the case that you go that way or whatever you because first of all you have the girls or the ibcs at the same time one in each side of the cycle so you need to do double the work

um what kind of technique do you think would be the most efficient one or at least the best one um is the question that is it possible to optimize the complexity for for the final chat exactly when you delegate computation exactly business narc uh yeah I have installed very deeply on this question but I think for example hyperplunk can be useful in some sense because like after this CV tricks right you can see that the final statements of this uh this decision phase is actually just some commitment opening right plus one sum check because this this randomly you know combined the equation is just

the sum check some check uh claim right so that is really fit and compatible with some subject based uh snarks like Spartan or hyperplunk and that part might be useful if you use a hyperplunk but I haven't think about another question you mentioned which is a really good cool question like how to dealing with these cycle curves of stuff that's something I need to think more about I think yeah so so my intuition on this also simplifies things is that if you minimize the um the size of the circuit on one of the curves and you you basically just have it as a wrapper around the other proof um just doing the accumulation then that

turns out um especially for the decider to be less expensive overall um rather than just treating each curve as um sort of equivalent you still fall into the issue that if you want to have a baiting based proof at the end you kind of need to get the decider whether you're doing I don't know like IBA something whatever it is and you need to put that on the other proof so that people if I not only the decider but actually the the other could have decided natively inside foreign remember that

um if you're using pairing based curves on both sides then um that ends up being really expensive because 800 yeah half pairing um yeah that will probably work you have pairing is fun and I don't I don't quite uh understand what you mean by uh you have to prove the pairing circuits you don't have to improve any parent searches in the final step right no definitely like what I meant is if at the end I want to have a snare that it's proving the ABC uh accumulated in both parts of the cycle I I let's say I have two ibcs to actually prove inside of us yeah finally I think you will have two

proofs right one is exactly but if I want to put that for example in the ABM or something like this where in reality I want is to have one failing based proof so I don't know whatever it is yes that's one way exactly which will work for example with data curves glucose for example yes yes yes yeah I think that's one issue one approach where you have two proofs first and then you aggregate again using grossing so that you can put it on on evm on point zero yeah um but by the way Pluto Eris are quite conservative um because um I went with a I think it's 400 and something

um bits um so it is possible to do it in um a smaller curve I was trying to go for uh for strictly 128 bit security but if you're happy with BLS 12 um straight one then um you can get away with something smaller I I should really do the work and and um yeah propose the concrete care for that moving forward [Music] [Music] we lose privacy right against other

Solutions like speed accumulation for example because we need to basically say no witnessing clear so that we can fall on the top of it in the ABC uh the University or which are your thoughts on for example committing to the witness and then doing some kind of Delegation of the probing in the cloud for example so that we can enable mobile phones or devices like this to actually use uh folding schemes yeah that's something I actually have thinking about uh so the intuition here is like for example instead of doing committing what I'm thinking is that you can do some secret sharing over this witness over multiple servers and I believe that it can be quite efficient

because all the all these operations in the following step is actually pretty linear right with just some random new combination so it might be I think it can be quite efficient and the assumption is that over this service that secret shared is witness like a majority of them are honest then you can you can guarantee that this witness will like never review any information of the of the original weakness yeah that's exactly that's the intuition yeah thank you thank you so much yeah thank you okay does any one company of the questions

um I have one more I'm sorry but uh uh maybe you also like answered this previously in the top but um will the recent uh Nova attack affect protostar also uh I think no because uh uh the normal attacks mostly about the IVC compiler we are just using that as a black box so we you can use the new paper from danbone and Wilson the dead compiler for IVC so so like this paper is only talking about folding scheme or accumulation scheme and we'll just use the IVC compiling black box so that won't affect the product Star as long as you're using the right IVC compiler yeah

which paper you mentioned uh there's a new paper that's exactly mentioned the attack for for for uh Nova is uh I think the name is revisiting Nova right but yeah revisiting yeah yeah that paper already mentioned an IVC compiler like you can just use that compiler there so basically the compiler means that the given sound following scheme how we can construct an uh secure IVC scheme and we can reuse that in process as well yeah do you know if that um generalizes to PCD in the same way uh we mean so first so the the paper that fixes the problem with um Nova does does

it go into any detail about how you would apply it to um I don't know because because I think Novi only works for IVC right they don't measure any one dollar for PCD only the PCC paper the PC or Ms they have the compiler PCD but then that is less I guess it's less efficient than the novel one but Nova doesn't mention anything about PC PCB compiler it's probably relatively straightforward but I think maybe yeah it deserves the paper and properly formalizing yeah on how how the ABC should be done with the

graph cycle so they faced the paper on the implementation um yeah this this has been an issue with a lot of papers but there's a little bit of handwriting about how to apply it to care Cycles um and a lot of these papers um yeah so it rarely someone has to to do the work of implementing it and then writing up what they've implemented I had one final question about implementation if we were to implement it would you go for the current like espresso systems uh type back end what would be the best place to start uh that I don't know it can yeah there are many uh backend which are all pretty

good like jellyfish from espresso system and artworks and also uh maybe even more others I think I don't I'm not an expert on this you I'm not authoritative to say which one is the best but I think most jellyfish and because jellyfish has some implementational hyperplunk and also know the PSE design Foundation they already have some really good implementation about it I don't know if it's open sourced yet though like colors maybe you can add more it is and it's based on the CK crypto Primitives so that also gives it a bit more quality awesome

okay so if no one else has any questions uh I will tell you a lot of indeed for coming here and explaining to us you know how productive Works in answering all of the questions uh thank you so much uh okay the name of everyone and yeah hope to hope to see you soon in another session like this one thank you by the way I also want to uh Echo the comments Nicole made I think like the attack mentioned it's just mostly about the some flow of vulnerability of the implementation yes and I think the paper is all right yeah okay thank you and I I mean maybe the papers should have gone into more detail about that that's true

that's also true yeah yeah yeah because it it when things like that are missing from papers that's when you you get a text because people get the wrong one including the original office original office yes totally agree nice uh we will leave it here thank you everyone and especially for the time yeah bye-bye thank you bye-bye he's really yeah