RAMenPaSTA: Parallelizable Scalable Transparent Arguments of Knowledge for RAM Programs

Transcript

[Music] hi everyone welcome to today's Lear and share we are very excited to have today Kong from Nan Technological University who is going to present his work Ramen pasta uh Kahan has also worked has worked on a while uh on cryptography he's done a few papers on Multi party computation and code-based cryptography we are really happy to have you here today thanks a lot for joining us and the floor is yours okay so uh hi everyone my name is Kang and I am currently working as a resarch fellow in interview Singapore so uh today we res R Basta uh is the parable

scalable transparent arum knowledge for R RAM and this work is in the CH with m in original works and okay so uh this is the outloud of my talk first I will uh talk about the motivation and the contribution of my work and then next I will talk something about aary especially for homomorphic scheme and then I will discuss the our new definition about conditional foring scheme including is in St and uh security requirement and then uh after this new intruction of conditional scheme we construct a generic construction of uh conditioning scheme so for short icon is CF

scheme and uh after after the gener construction of C scheme we construct Ramen Basta is it a s name of parable scalable transparent arents of knowledge for round Ram okay so uh now I start the the first part of my talk about motivations and contributions okay so uh the motivation is uh we would like to construct a Zer no group for R so for R is is a up comput steps with a memory supported and uh the aim is to construct a generate and UniFi framework for verifiable Ram so uh it should achieve

the following property the first one is uh highly realizable so uh in this case when proceeding in in intive group uh we can reduce the proving time and the verier time and uh in some case it may reduce the time the proing time uh about sub comparing to the size of the ram so uh and because our work is try to construct a generate construction so uh we can instant instant our Construction in different assumption and group techniques and here we we try to move our construction outside con of s snack including snack and uh s

s and our work try to leverage uh just minimal assumption including the the homm commment scheme and uh in this case uh we first try to f everything into a a single a single step so uh for example so uh the ramam is a SE up step like like this and until uh until last step so we try to f everything into a small a small instance so it this process the the fing process just Leverage The hopm of command scheme and therefore at the final step we just through at the end and this is the most version of

Nova and the final thing is that because our construction generic so we achieve uh the plug and play paradigms it mean that uh when running uh the our protocol we can plug anything uh suitable with our protocon such as the the homo scheme and the the zero FL into the construction okay so uh so related work uh at least a few Rel Works to our works so uh before there uh two reason Works uh this is must proof the first work is uh must proof and the second work is supp they

are the the two works are closely related to Rambo RAM and uh however that that construction is not generic because uh they instant their protocon in uh in some check arguments and uh it should be uh based on as group model in short we call it NGM and the order Works uh this is the first one uh from the order Works uh for it Max or we can call this thetic verer thetic verer zero and this the second two work uction generic however uh in that construction you need to grow every step of the of

the construction of the group I mean every step of a ram from step one to up to step n so need to Pro every step so uh so here we we provide a different approach we try to to prove everything into a small a small Pro a small instant and then at this step I will make the FR so this this way we follow no Nova par uh we follow Nova okay so uh from this one okay so uh from this one because we

try to move out the contest up Nova folding schem and uh Z SN then we fa a few difficulties uh the first one is that when we try to when we try to move out uh the contest of Nova this mean we try to avoid the recursion horis this mean uh we try we we try to avoid uh realizing the random Oracle model as the random Oracle as a circuit and in that way in that way uh in NOA uh for example in NOA uh in NOA they they F the two instant into a new instant yeah so uh this folding step uh incurs uh that

there's no connection between the two instant if if you f uh the new fold the new F instant has no connection this mean is the not inl any connection between the two for instance however in R because you try to to an end step B like this up to the end then between every two step there must be some condition some condition between them so therefore the the for instance here must U must must be F sucessfully if this condition how so this is the reason uh so uh regarding uh this condition uh for example the input and

output must match in I would match in some other situation like uh the access to memory also uh have some connection between the two instance so therefore uh we propos the new construction oh sorry the the new notion conditional cing scheme and then uh then in in this notion it allow us to F to instant some condition between them into a new one and uh the second one is generate construction of our conditional foring scheme u in this one we try to lever the homomorphism of commitments

homomorphism of commitment and uh after this gener construction we try to addapt it to make it a zero proof for R RAM and in this way uh we on is RAM and Basta like what we already introduced okay so now I'm move to the the next level of stock so uh this is a preliminary uh for the for my talk uh it it's also called the background so uh in this one I need to use the in this talk I need to use the notion of homomorphic commitment scheme so uh in a homic commitment scheme there there is a

temple including prms uh set up commit and verify so uh the setup algorithm here uh when you run it with uh some security parameter one to the Lambda it return a commitment key CK and uh and this is the setup algorithm so with this CK so I assume that the CK is implicit in the commit algorithm so uh the commit algorithm here receive and two things the first thing is a message and the second thing is the random M and it returns um a commitment C so uh from this commitment C here we can verify whether C is a correct

commitment of uh a mtic and Randomness by by running a verify Alm to return zero and one uh so one means uh C is the valid the valid opening of M&R so basic commitment scheme must satisy two property the first one is the hiding property this mean that um so uh the hying is that uh we can think like we put the Mage C the Mage M into a box and it return C so this box protect the mic inside uh the box so uh C here completely High theic m this mean the privacy of M is not L from the public

from the public and and the second property is sping this mean that when you commit the message M here you cannot change M to mam so that so that uh the verification still must this mean that you cannot change M to or more specifically from M to M Prim R Prime short dot short do verify M Prime R Prime and C is still satisfied this mean you cannot do that okay so uh here we have additional property of commment scheme uh we call it the homomorphism or homomorphic

property so uh usually we only require the line homic property this mean that um so uh we have the following things uh first if we have the the commment C to some M&R then when you multiply the commment C by by Alpha you multiply the randomness by Alpha and multiply M by Alpha this one still satisfy this mean uh it's still satisfy and the second thing is that if you have a two commment scheme for example C is a valid commitment scheme to M with r and uh C1 is a valid commitment commment to M1 and

R1 then uh when you take addition of them m0 plus M1 r0 plus R1 and c0 plus C1 then the the algorithm also return one so here um so because um everything uh usually they go together for example uh we have a commitment C is the commitment of M with r r so everything usually to go together so we use this notion to PR send a commitment to B this mean when we this we understand that when we write understand that there is a commitment C together with some m m with a m m

here uh and the randomness are short do the verification of c m here is satisfied so uh this tle we WR like this it just to imply that uh m is committed so uh in such a way then when we when we price I times M here so we understand that the the M alha time M here is committed and when we take addition m0 plus M1 then we understand that the Mage m0 plus M1 is committed and uh additionally I need to I need to use the some additional protocol it's mean the commitment protocol that on a m m the two party for example

Pro and verifier so in this approver uh commit the message commit the message M and send the comm c to to verifier so here C is committed by M&R so it mean that the pro sample R by himself and then uh commit to M with with r and return C and then the pro send C to ver so very or here we assume that he keep the commment C and the approver keep C M and R okay so uh this is whatever I would to use in my talk uh for commitment

scheme so next so now I I start to discuss the conditional fing scheme our new proposed uh folding scheme in in our res R pasta so uh in in this conditional for scheme so uh as prly I said uh we have two instant for example c0 for example uh we have to instance c0 uh w0 satisfy relation R and Z1 W1 satisfy relation R so we would like to fold them into a new instant here see and do also satisfy relation R here so uh in such a

case we require that the condition between um z0 uh z0 and Z1 must satisy by having uh this relation our condition this mean that uh there is some connection between z0 Z1 with the with respect to the witness w0 W1 and some a witness W Prime here such that when folding together not only these two things satisfy but uh this one also satisfy then uh then if if this one satisfy less R this mean if the 4 instant here belong to R then the the reverse the reverse here

also also satisfy that uh the first instance belong to R the second inst belong to R and the condition between them satisfies okay so from this in intuition we propose the the syntax for conditional fing scheme by having uh the to the TR algorithm actually is see the the algorithm C set up and the protocol for and protocol R so uh in this in in this uh syntax the setup algorithm just return some public parameter really now insult by BB and uh and uh for the protocol F when we F two

instant z0 Z1 with respect to w0 W1 and and and some aary witness W PR then it return a new for the instant ZW so it's match our requirement here and the W PR here is the supported witness for for the condition and the finally finally when you fold two thing together to achieve the new instance if you can Pro that uh CW here you can run the pro to to imply that the 40 instant is satisfied this mean that uh the here can be think like some groups that return zero or one to indicate whether the 40

instance satify or not so uh the security requirement for our our scheme including include to three things the first one is completeness this mean that uh the first one is that if the two instant the two original instant satisfy and the condition also satisfy then uh then the 4 instant also satisfy so here we assume that the pro and the ver in our protocol is they are po Hest um the second property sness in this case we assume if the 4 instant house I mean if the for the instant is satisfi the relation R then uh it's

imply with some propability with some probity that the two original instance satisfy and the condition also so satisfy this condition here is understand to be the condition between uh z0 and Z1 here and uh the thisal property is the on for Zer property in this case uh this property just protect the the original witness the witness for for condition and the f is witness okay so uh next so now I present the uh gener construction of our notion

conditional folding scheme so uh so to present uh the gener construction of our conditional foring scheme we recall the notion of Nova folding so uh in this case uh Nova folding no folding from kts KSD uh 22 in crypto so in in this paper they they present a new relas R1 CS constraint so R1 CS here is mean the rank one conference system and in this paper they they relas this cont system

so that in this system there are three public Matrix a b and c and uh we slightly modify their witness in the in the system so that uh the witness in in this rela relax r1s has the following things the first one is the the the unit element uh or the public element of of the r r constraint and then we have the the witness B into C vectors uh from Z1 to zc and um we have some additional error Vector so uh we we say that uh this vector this vectors satisfy the the

relax R1 CS with structure structure s here s equal to a BC here if and only if um a Time the the matric a Time Z here this is the the entty wise multiplication multiply with B time Z it should be equal to U * C * Z here and E plus some error E so the the vector Z we use here is the concatenation of Z1 to zc that I introduce here so uh this is the the notion of Rel i1 introduced in Nova and uh in this way we we would like to commit this uh so

usually we we emlo the commited verion of mple this mean that uh the public values including uh you and some public information they are public information so we don't we don't try to commit but for all the part of the of this including from Z1 to zc and the error E here we commit one of them and hand we price the the committed version of uh this s to be to be this form and uh we get a notion that if this committed c s here satisfies some relation R1 CS here then we understand that the the the witness s inside this

one also satified relax R1 with some structures s here equal to ABC as introduce okay so uh next so with this Rel R1 CS I recall the Nova folding so in the Nova folding we are given two instant S1 and S s0 and S1 so here we have two instant s s0 and S1 so ioun by small here to indicate a two instant and after folding after running no folding we obtain the new the new instant s here such that um on on the things here they are the

for the instant of the the the about two things so in the Nova folding um they have uh they have some comutation of some garbage G this G we call it the garbage garbage term so in this grait term um this is uh this is computed by the pro and uh based on this term the pro commit to this to it and uh in this case the very first sample and send a random Chan Alpha so by using this ch alha po can compu the comp component Instant by folding uh by

of 10 suu here from SI IU this mean suu from s0 and S1 uh together with some Alpha in the in between and next uh the appr also obtain uh s do uh sorry uh the instant here from our found so and uh he also modify he also combine the isi for on i z this mean the things he combine by alha and he he achieved the uh Z this mean the the ter in in the 4 instance and he also modify the the eror term from the first instance the second

instance together with some gab here by matching with Alpha so only thing here we uh the the author just use some random linear combination where the combination is based on the CH Alpha from the verifier and then after the things here he he achiev this one this one the things and the things so finally he obtained the the final instant uh s here so next uh now from the from the Nova folding I just now I I present the ination and the construction for my for our generic construction of CF schem our new near

sign so uh regarding the intuition we we use the bra technique from uh accumul accumulation and folding technique from the the V paper including Nova and accumulators in previous paper then uh iuss iuss something about the Chan so uh like previous we have Nova folding uh I mean this one the Nova folding is this protocol here so in this one Nova try to fold two instant uh si si including s0 and S1 here into the new One

S so so uh the observation is that there is no connection between the the two instant uh like at rly so in Nova uh when they use this one to construct the implemental verifi computation they they try to uh delegate this the this one to the checkup condition into another cups into new cups sorry so uh so in because uh they try to move into new cups here they need to to do something like uh using the the aristic this mean a random Oracle a model random

Oracle as a circle and they they try to to make everything uh into another cup so therefore if we would like to move out of the contest of uh ristic and um and just uh deal with one Cur and no no jump into new cup we we need to um we need to form an additional constraint here so in our ination we use an accumulator here this uh this this is that we desde a NE B that contain a n here that contain accumulator Exar so this accumulators play a r of accumulating the condition accumulating the condition

so uh in this case uh the Z also have the the original instant and we also have the the two other component input and output so this component uh input it contain something that uh that is the inbut to the for example in the ramble Ram like we have a step right uh so the input is something uh before the the current step so this is the current step so this uh this the inut and this is the output so I and uh I split this one into the first one is the main part the input

the output and then here we have the accumulator for the um for the condition and then we have uh some additional component including s and I here so s s here is to accumulate some linear constraint uh the first one is the to comu some linear constraint and second thing is uh for accumulating okay so uh by this structure uh so this is the purpose for Designing this structure because uh when you when we F by Nova we just only F the the first things but if we F the first

thing then the input and output uh is not correct anymore so therefore we we uh extract the input and the output into to other independent components and hence uh later on when we when we F things together we can use this accumulator to accumulate the input and output and their constraint I mean the the St the satisfaction of their constraint together and uh in other in other problem we still need to to to make sure the linear constraint and the some the line constraint to satify and we use a is to accumulate in order to to extract

later with respect to this linear contraints so from this design um from this design then uh we would like we in specifically we would like to F that to instance in uh z0 and Z1 that's how the structure I discussed and we F the two thing together to uptain the new 40 instance here Z that's have the similar structure like this and uh here we would like to capture the condition between them by having this relation so is for condition and G G and G here is for Generate so um this this to cap this is to capture

the condition between the the two instance z0 and Z1 so when folding together uh when folding uh the first two thing together into the the second things then uh if the second thing satisfy this reation then the condition how and the first instant the second instance also satisy the respective relations okay so uh so now we have the the design and the the purpose of folding and then uh then we we now we I explain how to F this one so first um oh I'm sorry this one is the F Nova this is the B Nova

folding i1 CS pH so uh in our design um s0 and S1 uh they they follow the or original NOA folding and uh we have additional um additional uh witness Vector W here and when uh when folding the condition we uh we F the three three things the first one is the the accumulator of is Instant s0 Star and S1 star and the second thing is that we we form the condition between this the the three things together and we F them uh we F them with the in the outut

of the first step and in then the inut the Second Step so um we have to instant right so we have uh let me WR more specifically so we have two instant s0 and S1 so we have the input uh i z we have the output i o Zer and then we have the input i1 and we have the output uh R1 so here we between i i z and i1 uh I I set a PO sorry I set previously uh between o0 and i1 it's mean the outb of the first step and the INB of the Second

Step then need satisy some condition so we have uh some additional witness you here so um so from the three thingss we from the new the new the the new triple and this triple on so a of relux R1 CS triple relux R1 CS triple it's mean the the rest1 set instant so we have the first instance the commitment of instance commment of the second instance to be the accumulators and we have the the third instance to be the combination of the things and we follow them together into the new so uh to follow like this we we

first for we first for the first to is first to obtain the 40 instance and then secondly we F on the three together on the 40 instant and then we it continue to follow the second thing together so we follow two times for this one to obtain the the condition the accumulator for the condition St okay so this is uh the the idea for folding the condition so um for the remaining things okay so you already F s0 S1 into s SAR by using o z and in1 so uh remaining thing we have i i z and o1 they are the input they are the input

and output of for the instant so here we have a two for the instant the two two three4 instant here and you fall into a new instant so i z here and i1 uh i z here And1 here they are the input and output for the instance so I set the input to be i z and the output to be 01 and for other other constraint like we we still need to have some additional linear constraint so I set s equal to s0 plus S1 and uh we need to to be able to extract so I use a z and A1 and we we continue to fold uh a z and A1 together with some relationship here so that

later we can extract back this mean uh we can extract um from this mean we if if we have this uh s0 and S1 together with uh s equal to the sum then we can extract back s0 S1 so this is for the purpose of knowledge soundness and instruction so I I don't discuss uh too much in detail it's my M loss so I just assume that the additional instant a here the additional component a here is for structing in in knowledge soundance improving knowledge soundance so um so from now I already finished the the folding process of our conditional folding scheme so uh when we

have this folding uh up the St instant then for for a long string for example for a long string up up step like s S1 S1 S2 up to some SN and we just uh f f them a binary three oh sorry I don't have much SP so for example like we have uh the step one the step two up to the step end here so uh the idea just to fold them into a like a structure binary gr so because of this structure uh into okay into the structure gr then at the end we

have a 4 instance here so in this for the instant we can make a proof so um so because we use the this structure binary degree uh then we can parize our construction this mean uh for example we can follow we can do two things at the same time if we have multiple track in the in the machine okay so that's the idea of our generate conditional foring scheme and then now I move to the the next part uh so from gener reconstruction of our conditional foring schem then now I would like to to to discuss how is

extend to construct R Basta uh it's mean uh is it a zero knowledge group or we can think like a zero knowledge argument for for R RAM and it achieves the some property like Parable scalable and transparent so uh like like I said about because we follow by binary tree then we can make it parallelizable and uh and we notice that uh the construction our construction is generate so uh this mean that uh is in natively Parable is mean um whenever we put some Pro technique or assumption into uh it's still be

Parable and uh for scalable so uh if you on so for example if you already have a computation a computation step like this and then we have another step for example they are the three of R and another two step then after you f into the new one like this then you can continue to follow so this mean uh you can extend them you can extend the the construction into more instance so um into more more other arguments so uh it's here we say it's scalable and transparent so because we are we are generic our construction is generate so

uh if we instant is by some transparent assumption then uh the resulting construction is also transparent okay so uh with this name now I I discuss um in detail about a structure of a r Ram so uh in the ram ram we have an instruction set F and we this instuction set you can think like uh in our machine like they can S Sub moon or something so uh you you may notice the thing they are the up cost in something like uh etherum uh virtual machine and like Z

Wim and we also have a register of constant number of address so in this one we can think like uh uh they they just keep a few instant a few um a few SP up memory so that we can plug directly into the instruction uh in the first step then we also have the memory so this one is extremely huge for example in uh in E virtual machine I said evm in evm the memory can you can think like um the the memory the storage and the speack in evm here and we also have the ram

counter so how it run how this Ram run so uh at the beginning right we have we have theity of component including the first PR counter the register uh the the index some some the index some value and some memory access okay so uh based on this so based on this pram counter here we can look up from the instruction set the the next instruction uh look up instruction that instruction by uh using by Computing the f fbz z f r bc0 so uh based on this next instruction

you can run the input you can run on the input like the ining including the right register the index of memory access and the the memory access uh to return for the the component for the next step for example uh after you running the first things then uh it return like bc1 register one and one one one value one and um memory of asset one so uh the instruction so like like I told you the instruction is uh sorry the the the program C is to select the instruction

and then from the instruction it is the inbut and return the new output and it's continue to repeat this one until the the step end so here I I I told uh I already discussed about the thing but this not explain so far so uh the the triple the triple here is we can't use the the memory asset Tri so that um the the final component is the memory operation so in this memory operation we have the two things uh it has uh to I two values either read or right in the case of right it set the memory at the index II to be equal to the the value I so in this L here is

here and the second thing is uh is that if the memory operation is great then it set the value one I to be equal to the memory at the index okay so uh this is how the ramam work um it SP on BC to select the instruction for executing and is sp all the things uh A1 I and memory operation I to access to the memory either r or right okay so now we would like to construct a zkb for Ram Ram uh so is it a s name so it's uh in more General we

would have to construct master so uh our task is first we need to prove that we correctly select the instruction from the instruction set this mean uh the instruction s step I is uh selected by using the BC of R step the the program counter prever step and we select the f f bcus one from from the instruction set here and we after we select correctly fi then we need to Pro that with ex secure correctly is instruction fi and finally we need to Pro that we have the memory access uh consistence uh

so what's the memory consistency uh in such a case so for for memory right we have a memory m equal to m one up to some M this mean we have a access then uh for example at at the some address like m i if you if you pry some value V if you pry out some value V then the next time when you read from this one it should be also V and you cannot change it to some V Prime so here that's see why we call is the the memory

consistency so uh if we so uh because uh we we are using the folding scheme conditional folding scheme so we try to boost on on these task into the context of foring conditional foring scheme here so um our initial solution our prop solution is first we try to realize uh each instruction in the instruction set by the the plan structure so I will discuss more detail about how we really like this one blond structure and um in every step we need to correct so uh in this way after we realiz by plan structure then in every step we need to do two

things the first one is that we need to look up instruction so equivalently we try to look up the plan structure according to the previous uh program counter and then after we have a plan structure then we can Pro the correct execution s stepi so we we should Mark that uh fi priv because uh because we are Pro in zkb so the prev is priv so we can make Mi priv too we Mi priv too and regarding so this one is for for execution and regarding memory we use the memory technique from the memory checking technique from

reverse paper R result here okay so now I will discuss in more detail about the three thing I just discuss the first one is the look up um look up the structor the second thing is uh proving the the execution of the plan and then the last one is to prove the memory uh memory consistency and only things we try to put into the context of conditional fing scheme so um so I Recon the plan uh so the original plan paper um they try to realize every instruction every circuit see here by the following

two components the first one is the S selectors and the second thing is uh a unique peration for for the circusy here sorry this permit is not unique it can be some permit that guarantee the the connection or the wi so regarding the selectors the purpose is to try to to ensure that the the competition of every gate in the circus is correct and uh secondly for the peration it ensure that the the circuit it competed correctly throughout the wires this mean they can try to connect the wires like input and output must match together so uh by using this BL structor we can encod every every instruction in

the instruction set here into into the for PL structure so um so um this PL it contains the so this one is what we we dence B so um sorry let me so this one will know by thect is in this one it contain the bation and the selector of the cor corresponding FZ here and we have an additional in this Z here is to to make sure that uh this is the we concatenate the pl struct with the index so that later on we can look up them and the index also make the everything in in the instruction set unit because uh we we have the index

different from different instruction and this is for the instruction in the instruction set so for instruction during the execution of our Ram our uh propos RAM we KN by fi and we also have uh we also encod them into the form of BCM one this mean we try to put the BC uh the program cter into this form and the plan structure corresponding structure of this one so by on this BC we can we can make a look up this mean that the the pl structure of every instruction here belong to the set of instruction here so in general we are doing a look up argument that we try to

show that uh the the instruction during execution on the Constructor must belong to the set of uh induction set so to to do this one uh in f i i just talked uh in F that we can apply the result from H because uh in h we can uh transform the this relation uh we can transform the look relation here into the form of the sum into the form this sum so pay on this sum because uh we have the sum so uh are so that we can make it into the concept of folding easily we can adapt uh the every every long

structure I here from this one into the contest of folding easily by having every up to every instance of the conditional fing scheme so that's just a PR discussion for proing look up in folding so the next one is for proving execution of instruction so uh it because we you plan mization so uh in pl we need to prove that the the two things the the G constraint sorry G constraint and a Cy constraint together so uh so from here

we we can construct a universal circuit that realize that tech tech as in both the blun structure together with some witness and return the correct combination of the function fi that has the corresponding BL structure here so uh the purpose of this uh this cir is to guarantee the two things the G constraint the copy constraint so um so by this sey we can encod it into the the form of R1 CS structure by having the structure ABC here and uh and because we can enor into the R1 structure then we isable for us to make into the fing scheme so uh

next so the last thing is to prove the memory consistency so uh so for proving memory consistency I I just talk briefly that we we use the constraint from the prev result uh the r forone here in in the for result they specify the constraint for memory consistency by the following thing so I just uh write more here I explain details so uh in here they need to they need to guarantee uh a permutation here so in this proving memory consistency they need to guarantee this peration so uh therefore we need to deal

with this one in in fing to in conditional fing G to so in this case um so in this case we also to prove the bation of this one and this one we also transform into this some live rever and then buting everything of them into the the every instance winess SP of the conditional foring scheme so that later on we can follow and then we pro at the end so uh I I just uh discuss already the three things the first one is the the local instuction the second thing is for for proving a secution of instruction and the last thing is for memory consistency so

finally uh I I collect one of them all of the component together in this in this one and then from the components I uh partition them into the following uh smaller components from zi1 zi2 Z3 Z I4 and Z5 so the things for the things for an ex step so uh II is mean that the def is for the I uh execution steps execution step of the rram so from here uh so from here I Recon the the commic of conditional pting scheme so in this

commic uh we have the first the the instance the input and output with respect to this instance and then we have the condition accumulator we have the uh the variable for computing the linear constraint and the the support variable for for instruction later so I as after proing them I separate them into the following things so first I set the input to be i z i1 this mean this is the input to the computation I set the output to B2 so this is the output of the and uh this sum is for for here so I you remember that uh we need to take the sum

up on the things so that later on we can guarantee the look up and uh and the permutation so I put them into here for for handling the linear constraint and uh this one is for instruction so I don't discuss in detail and uh for the instant of every step for the in of every step we we put uh we put by using the following structure this mean on the zi1 to zi2 zi3 C4 and Z5 we put all of them together into SI so here we and and uh the final thing is the the component

for for cating so uh I just put is some random table so finally after this setting we we obtain uh Z for with with the with this component so uh we just so then at this step we just follow the follow the gener Construction Construction to to f on of the T from is me Z is mean uh for I from I from one to n one to end here so uh we we follow the generate

construction to F on the on the end instant here on the end instant witness PA here together into the final one and we construct the proof at the at the last step so uh finally after doing like this after partitioning and then set the component like this one and after folding and proving then we obtain the final thing the ra master is see the the generic construction for for proving in R Ram in parallel and also uh scalable and transparent if we use AO Pro technique that have the transparent set up and the folding here follow binary spru so because this par structure then we is highly

parallelizable so um so regarding the efficiency of our construction um I I give the following notation so for CK I assume that this is the commitment size the size of the commitment of the M of K up l k and uh MZ is the L of every instance z i uh this one um sorry this H H this one ci1 to C C5 here so uh MC the the length of them the L of each of them for or NE and Ne

Z NE Z in one to5 and uh we also have the length of the arrow term of each inst spare for S and also the arrow term for the accumulator so here we have the two instant the two R1 s instant so we have the two run two corresponding error so iote them by eii andr so we have a length of the two arrows here too and we also have the group size of the final inst winess it's mean when we follow by binary structure like this or sometime like this here so at the at the final step we need

a proof so B here is the the proof side of the of the final Pro so in our protocol uh we achieve we achieve the final thing uh this commiss communic communication cost for for folding and this one for the pro uh for here uh because we need to deal with the memory constraint H sorry we need to deal with the lookup so we it incur some uh a factor of the okay so um so in our construction we

we uh we try to move out of the Z and we can install in different assumption and uh and if you if you see here that the folding uh the folding process here only employ the the homy commitment scheme and the pro is at the end so uh so on the folding here they are independent with the pro so uh they just depend on the comment scheme that we use so now we uh so because this construction then we can instant this one into multiple contest uh the first one is the compressive protocol this one is the the later

result after buet and uh we also have we also can install in mode winess inable this is from Pro high and we can also install the hand from uh e side on and or some other like design VAR there from it so uh I just uh sign here this is the varable okay so uh so I already finished the discussion of efficiency and instantiation so uh thank you um so now I can think I think can

start a FAL and answer Q&A thanks Kahan for the presentation uh I don't see any written questions on the chat so everyone if you have any questions feel free to to ask them I have a few on my own forever so I start with this um so you using PL lookups uh I was wondering if you had a look at other lookup schemes because the research has been quite active the the past few years uh to uh instead uh look up here the look up right yes this one yeah so

uh you uh can you ask again the question sure sure here you are talking about using uh plunk lookup arguments uh so lookup I assume I was wondering if you had a look at all lookup schemes um so for instance uh log um I from uh it's mean in h um would like to Pro yes yeah yeah no no sorry I'm I'm listening I'm listening okay okay so I look up Hab here so in Hab uh they uh he has the the set SI and he would like to Pro that uh SI belong is the subset of Yi here so um so in this case you

transform the the lookup argument into the form um 1 plus S Plus s i here equal to um some multiplicity yeah y z y MZ S Plus YZ so uh the purpose so this is the H up and uh my is because we just do the we just do the uh we just look up the a string instead of the the single value so we has the single values and then we apply the H this one and finally we we obtain this sum actually this is the sum yeah yeah interesting uh thanks a lot

another question I had was about um the the condition that you have so here you want do IVC so you basically uh ensureing the condition that uh the previous output equal the the current input I was wondering if uh you could uh modify uh if you had flexibility in this condition and you could modify it uh so for instance uh imagine that you we are working on a zkm uh you want to make sure you want to fold on valid transactions uh on transactions uh but you're only going to fold you only want to fold on actually valid transactions

so a condition could be uh that the current inputs are uh represent a valid transaction and not an inval transactions that's just an example among many users but my question is um to go back to the question uh can the can you have anything in the condition is it flexible um so your question means that for example in uh in blockchain right you have multiple transaction and you would like to follow the verification of on transaction into a single one right so in fact uh uh actually as understand so for every transaction you

need to to make it go through a like a smart contract right yeah so in my view point this smart contract is a r for example this actually my construction cannot achieve uh to Pro Smart contract because it quite strong but uh we can do this at a par and uh and then from this you see the we when we de compose this one into the like something like for example evm right so we have a set up uh in a set up step here a small step here by that so uh the purpose is to

this mean I approve the the correct execution of this contract by proving the correct execution up the S one up step here so if you have the other transaction like uh then you have another S one up up up step right like this right so you you can just f f them together uh you f all of them into a single thing and then you f the two thing here together is still possible so is is it your point uh yeah yeah thanks a lot uh the last questions I have I don't want to take the mic but too long in case other people have questions uh so here you are you are following uh Nova Nova paper in that you are using relax U

hour constraints I was wondering if you I was wondering if you had a look or sorry had photes at uh CCS constraints customizable constraint uh constraint systems from uh citya and W which is a generalization R1 CS Yes actually we we have a look up of that one but I think all result already already handle those things and because my my my result is quite too many Techni so I I did not recur much into CCS conference from uh from set yeah yeah innocent uh just because you are you are using PL structures and so on I thought

that's uh looking at CCS could be quite interesting to have a generalizations of all constraint systems and so there might be an easier integration of the lookup arguments and of the the design of all uh BR this ariation uh yeah thanks a lot thanks thanks for your comments um see if anyone has questions okay I guess no one has questions uh thanks a lot for this talk K it was very interesting uh I'm part of the zkm team and uh I really want to

delve much deeper in your paper to be honest uh so I'm really excited to learn some of your ideas and more U of your work uh thanks a lot again for presenting today Ramen pasta and uh thanks everyone for attending I hope you had a good session and see you next week thanks Raa