KiloNova: Non-Uniform PCD with Zero-Knowledge Property from Generic Folding Schemes - Tianyu Zheng

Transcript

okay hello everyone uh welcome to another Lear n CH session uh today we have uh tan Yu Zen with us uh he's going to present uh his latest work on kilonova uh kilonova is basically a nonuniform PCT system uh with general knowledge properties derived uh from genetic folding schemes in particular it has been inspired uh by the work of uh kpali at all uh in hypernova and what tan is going to present us today amongst his work is how it specifically uh kilonova ensures that we have zero knowledge properties uh satisfied within our uh folding scheme

proposal so thank you very much for coming uh today tianu and the floor is yours you can start whenever you want okay thank you thank you for the host uh hello everyone it is a great honor to be here to share you with my with our recent work kilon NOA and the authors of this paper included me and Dr shal drug and Dr B and this paper is now published on theint so you can check it there okay uh today I will present my uh work maining in five parts okay the first

part let let's begin with the first part of the background so in recent years there is an exciting breakthough uh on the research of recursive not uh and this scheme is also called the folding scheme or the accumulation schemes we use them uh interchangeably and a large number of papers are published since the 2019 when the first scheme called Halo is proposed here okay the

Halo and Bas on Halo booms and other authors sther summarize a theoretical model for the construction of Halo and propose the concept of the accumulation scheme in 2020 and here the Paper bcms 20 so before H people build a recursive snars by directly checking the proof in the recursive circuit so this construction has very low efficiency because the uh the nonnative operations is very expensive for example we need to implement the pairing or the scalar multiplications in the recursive

circuit and Halo introduces us an idea of folding and deferring this costly verifications to the end of the computations so at each recursive step it only checks the validity of the folding scheme instead of the proof okay and another work I want to highlight here is the Nova Nova published in 2022 so for the from the perspect perspection of the serious work of Halo nova seems to be a very aggressive idea so in NOA not only the proof it uh it almost defers everything

in a in in a n okay so specifically it directly folds the committed R1 CS instances instead of the proof so therefore their recursive circuit is extremely small and resulting in a better performance so the following work of Noah we listed main FKS on adding some uh appealing features uh for the IVC or the PCD so for example uh the Supernova tried to achieve nonuniform circuits or and uh the work like hypernova and the protar and Proto Galaxy try to use more

expressive constraints than rncs for example the pl okay so usually this work aim to build a primitive uh called the incrementally verifiable computation okay abbreviated as IVC so uh they build IVC from this folding scheme and uh uh claim that this IVC is as their main contribution so some other work further proposes a more generalized one called the tcd the proof caring data okay these two Primitives have many important applications in our

real work such as the Z and building virtual machines and so on okay next let me further explain more concrete lay on these two parameters okay first uh the incrementally verifiable computation IC enables us to producing the proof of a statement that a long R sequential computations uh as we depicted in the first figure uh okay the the IVC produce the proof that the this computation is correctly

executed okay so this is the statement and the main purpose of IVC so we can see uh in the figure here I put here that uh an incremental commutation it actually uh includes uh multiple stats and for each step for the N step and the number n step as an example in this step uh it's take the input of uh a value here is ZN minus one and we have an output as ZN and it will also takes an input a secret input uh as the WM

okay it's optional so for this single step in IVC the prover needs to to compute uh the above the above computation we denote it as the function f so this F function will take ZN minus one w n as the input and output a value as ZN so in IVC theover computes this step by step so on and so forth and uh so theoretically it is it can be an infinite computation and we can stop just at any anywhere for example at here and produce a proof that

shows that the previous two step has been executed correctly so this is the function of the IVC okay so you can see here IVC is actually a a simple sequential competition okay it's just like a chain so what is PCD the proof of car data is a gener it actually generalize this the simple structure of IVC into a directed effectly graphs so in the graph uh each node may have multiple inputs and multiple

outputs for example the number ear node we depicted here here it will have multiple inputs and it it also it it will also have uh multiple outputs okay so I just draw one here so in the definition of PCD uh we don't use a function f but alternatively uh this definition gives uh a predicate denoted as five here and this predicate will output a

bit of zero or one Z1 denotes that the denotes that at this step the prover has correctly uh compute this computation so so actually the the the F function in the IVC can also be represented by the predicator okay so and another difference uh I want to highlight here is in the PCD we we usually will consider a situation that multi parties will participate in the computation here uh the each node uh may not denote as a step it may also denotes

that a particular uh party who participate in the system so the so here uh for example the the first node may run by uh user a and the second node may run by user B and they are mutually untrusted party so uh while the in the IVC in the in the IVC we usually consider there is just one Prov who who will continue the computation of of this series of of this series of functions so uh in PCD we are more temp to consider uh the

multi party situation and this situation may raise some privacy concerns we will mention later okay so in a word PCD is more complex uh with a wider range of applications but relatively uh designing a tcd is harder than designing an IVC okay so uh here I try to summarize the our research topic okay so current research on IBC or PCD are Ming based based on the Fus games okay we can

divide them as two directions the first here is to build is we aim to build IVC or PCD with better performance so basically we can measure the performance of a PCD in three dimensions okay the First Dimension is the prevere native cost and the second is recision overhead okay these two uh measurement this two measurement is actually all executed by the appr but differently uh in the recus not theover will compute do some

operations locally but he will also do some operations in the uh recur recursive circuit and uh produce a proof for this recursive circuit and send it to them to the next step so uh on to this reason we separate uh these two parts and regard them as two two measurements so uh if we consider if uh for the IC and PCD we consider their function f or the predicate five as uh they can be arbitrary

computations so the main fact that will uh affect the whole performance of our system uh is dominated by the folding scheme so here for the pro native cost uh it is mainly dependent on the folding scheme Pro cost okay and for the recursions overhead uh it is mainly depends on the folding scheme verifier cost okay and another measurement I want to mention is the decider cost okay the the

decider okay decider is actually a denotation used in some uh PCD papers uh so in IVC we don't use thiser but uh actually they they are uh the same things for example in an IVC if the appr wants to run a series of competition and after uh execution after finishing this computation he needs to provide a proof P to uh so-called the IVC verify okay so in in PCD we call this IVC verifier or the PCD verifier as the

desider okay so the descided cost is uh also matter also matters okay okay so this is the first res direction for IVC and PCD the second uh we are interested at uh is to add our current IVC or PCD with more appealing features in our real world implementations okay uh so in general the these features can be uh summarized as as this four okay the first is to

implement PCD with more expressive constraints as we mentioned above so for Nova it is based on the R1 CS relations but uh r1s relations is a quadratic relation it does not support the High degree constraints nor the look up argument so in the in the following work such as hypernova it Tred to replace our NCS with more expressive constraints we also call the CCS we will introduce it

later okay uh the second feature uh we are interested in is called the multi folding so actually uh in the previous slide I have introduced the PCD the construction of PCD so you can see that the PCD requires a multi folding as as a default option right because in a d graph this graph uh each node will take input uh multiple instances so uh to build a PCD we need to First build a multi folding schemes okay but IVC does not need

multi but as mentioned in in prot Galaxy I remember uh the author also argues that the multi folding scheme implementing a multi folding scheme is also meaningful in the IVC system okay this is because we can use this multi folding to scale the performance of our system Okay the third feature is the non-uniform circuit okay uh this is a very popular uh features because if we try to uh Implement virtual machines such as dkm or risk we have to uh we

have to achieve this property because those virtual machines may have a a reach instruction set okay the fin the the last feature I want to mention is the uh zero knowledge so as we we mention in PCD since the PCD needs to consider the situation that multi party the mutually untrusted multi party uh will participate in our system so to provide the Privacy we need to add the zero knowledge property we need to provide this privacy preserving techniques for

our users okay so for for generality of our discussion uh we will mainly focus on the design of PCD instead of IVC because uh you know we need to include the multi folding property here but and also the IVC is a specific example of PD so uh our work if we can present a construction for PCD we can also present uh this apply this Con construction to the uh to IVC

okay so in summary we uh upon this uh resarch topics uh we develop our motivations in two thoughts the first is the question that can we build an efficient nonuniform nonuniform multi-folding schemes for those High degree constraints okay this uh this includes the features we mentioned the first feature and second and third and uh if we can uh if we can realize the first uh the first then we can further construct

a zero knowledge PCD from this folding scheme we proposed okay so here we try to achieve the force features as zero knowledge for our okay uh uh so we got our motivs but there is some realistic challenges that we we may encounter in our implementations so so uh let me introduce the them to

you so so when we con try to construct a PCD system we will make face it various of challenges okay the first problem is that uh although we got a a lot of e very efficient soling scheme or cumulation schemes in recent years but uh after our uh investigation we found that most of this soing schemes are in incompatible with PCB okay one main reason for this problem is that those multi folding uh will introduce cross

terms especially for those High degree constraints okay let me show you a case for this problem okay uh as sh here if we try to fold two sorry there's a typle we try to fold two quadratic relations so what is a quadratic relation for example we got a input as X1 and we compute the square of X1 and to check it whether equals to y1 okay s simly we got another instance with the input of X2 and also the square

of X2 should equal to the result of Y2 so uh usually if we try to fold these two instances we uh we prefer to use a linear combination for example we can compute a new fed input as X prime it equals to the uh first input X1 plus uh C time a random C time the second input X2 and then we we need to compute the square of the this folded

input but unfor fortunately if we directly do this we will find that we will find that the square of the folded instance does not produce uh the same the same folded result as we expected so you can see on the right hand side uh here if we directly fold the the results y1 and to the result as Y2 this equation will not hold so to make this equation home previous papers introduced some

techniques to send some EXT crosss okay this cross ts are additional cost that we need to need to pay in the soling scheme so here for the quadratic relation to make the equation hold we need to send an extra uh cossom s X1 times X2 right this is our C and the the verifier need to add this additional Coss and times C time to the right hand side to make the equ

hold so uh in some low degree uh relations for example the RCs is only include quadratic relations so we need only to send several CS uh it does not seems to be a very severe severe problem but if we take the high degree constraints into consideration for example if we try to fold multiple instances okay totally in in s instances and for each incidence it contains a relation of the highest degree of

D then how many crosss we have to say Okay according to a previous paper that we need to send uh a very very large number of the C which is dependent on the D to the power of s so this actually is a very severe problems that it will make our the the obtained system at totally impractical in the real world right so this is the first challenge you with in encountered when we try to construct a PCD uh for especially for uh

from the those folding schemes and the second and the third challenges is about the appealing features we mention the first is the non uniform and the second is zero knowledge so um they all encounter the similar problems uh in the first case okay let's first see the case two uh so if we try to achieve the nonuniform property it means that uh not only the uh the input the circuit input X1 and X2 here they are different but

and also the circuit itself their constraint for in R has write in The Matrix so these matrices are also different right so in in previous uh in previous scheme we only consider that we fold a times X1 and a * X2 so uh and equal to y1 Y2 since uh each of this equation is linear of the input X1 and X2 so we can directly fold them together and there is no Coss time but if we consider the nonuniform

circuit then our equation will becomes actually the degree is is increasing right so for this uh since the A1 and X1 they can all be regarded as the variables okay so this constraint has two variables and this constraint has two variables and their degree is actually uh two their total degree is two right so if we use a linear combination to fold these two equations uh there will be cross terms so actually this problems also hinder us to build a nonuniform for the

things and for the non uniform T and the third problem is about the zero knowledge okay we UST this problem in case three so uh again we consider a quadratic relation as we imagine is one for example the X1 square of X1 equals to y1 so if we try to provide zero knowledge for ouring what the common method we use okay is mkting value right to uh here the X1 may contain some

uh private informations we we also denote as the witness right the witness W so if the Prov do not want to lead the information of the witness okay has to sample another random VOR that with the same length of the witness with the same length of the witness witness W and mask the witness W with this random sampled Vector okay and also add a challenge c as a weight here the random samples Vector is denoted as WR so let's look at this form of the Mask

uh witness so actually it is an another linear mination right so if we put this linear combination of of w into the quadratic relation okay we we compute the square of this Mass witness then what will happen we will gain an another cross ter right so uh in summary uh when we try to construct a PCD system we we have to solve this challenges to make make our system uh truly practical uh in the real world so upon the above problems uh I

summarize our contributions as follows so uh in general our paper uh can be divided into three parts the first part is called the relaxed CCS relations uh so typically there are two pathes to solve cross problem okay uh the first is that a series of paper from protar and Proto Galaxy they uh try to reduce the number of the costoms after they already generated in the folding sche and they try to use some some this

makeup approaches such as the lag range basis and to try to aggregate this Coss ter up and so that it reduce their number and the second T is to First transform our relation into a linear forms okay since our relation becomes linear forms if we directly add uh fold them up there uh will uh there will be no crosss and through this PA we can totally avoid uh this problem so in this paper we choose the the second pass okay

following the idea of hypernova so to to to design a relax CCS relations uh our first step is to uh is to build a early stopping version of the super spant okay and then the super Spartan will yield some linear claims and we call them the relax CCS relations okay this those relax CCS relation only contains the linear constraints on both the circuit structures and the instance with mispair okay this is essentially uh here

is the Matrix we mentioned in our example Matrix a A1 and A2 and the instance witness pair is essentially the vector Z we mentioned in our example okay so with this relaxed CCS relations uh we can further build a folding scheme based on it and so the next part of our paper introduces a nonuniform multi folding schemes from those CCS relations and also the folding scheme does not have crosss and also our floing scheme is

very efficient and its performance is comparable with uh cutting age work Ty NOA compulation in 2023 okay so uh now actually the the first two parts uh solve the first question that we we now we obtain a non uniform multi and it is very efficient so our final goal is to build a zero knowledge PCD from this holding speed so in the in the final part of our paper we introduce a new construction for zery PCD okay to achieve this uh we need to

First the trans form the generic folding scheme into a ZK version okay and from the DK folding scheme we can build a z DCd so actually there is some technical gap between this statement uh so the second uh subtask we made here is to introduce is to propose a new theoretical model for the construction of rpcd okay and it can be regarded as a thetical distribution of our Pap so and the third point is that uh we also uh consider some potential problems that we we will me in

our building for the for the PCD okay in in the in the real world implementations so uh against this uh efficiency problem we further propose an optimization technique called the PC delegation okay so this PCD delegation can enhance the the performance of our whole system okay uh so far do you have any questions about about the first part there's nothing in the chat so it

seems that for now everything is clear okay okay uh so if there is no question let's move on to the second part the relaxed Rel CCS relations okay uh to uh to introduce our relax the Cs relations we need to first introduce give a quick recap of the Spartan and the super Spartan property okay so generally uh a Spartan is a polinomial interactive Oracle proof the P for the RCs relations okay it is proposed in 2020 okay and it has some uh good

properties such as the the fast appr and and other things okay so for the spart we generalize the the whole process of a Spartan protocol and and into three main main steps the first step we call it as encoding okay this encoding actually help us uh to transform the R1 CS relations into the polom forms Rel okay why we need to do this is to this is because we want to use the Su check protocol uh for to prove this relation

so we have to um made our instance into polinomial form okay which is compatible for some Che okay so upon this polinomial we need to execute two rounds of some check protocols this is because in the r1s relation as we mentioned there is there are some matrices okay a b and c and this uh matrices actually has two Dimensions so we need to encode this two Dimension matrices with a multivarious polinomial and this this polinomial have two uh dimensions of variables for example uh the polom is denoted as F and

it h it has two Dimensions variables as the vector X and Vector y so our remain task is to separately or iteratively to run the Su protocol on each dimension of the of our variables so the second step is to run some protocol on Vector X and the third step is run some protocol on Vector y uh so uh to explain our problem clear clearly we we need to further uh dive into the the the concrete step uh

of this each part okay so uh first let me introduce the first part okay in the first part uh we need the Prov need to encode R1 CS to polinomial so um upon this problem uh the first thing he needs to have is a is R R1 CS relation right and the R1 CS relation uh includes maining four elements uh there are three matrices A and B and C and also a vector Z denote as the instance withness

pair so the RCs relations uh is an equation that contains the computation of this these four four elements and here the circle denotes the hardar product also denoted as the entrywise product and after the computation of this elements and uh the right hand the right hand side uh it us a zero Vector a zero Vector here Den not here so uh our main purpose is to transform or encode

this relation into a multivariated polom form so how to do that okay let's take the Matrix a as an example so here is the Matrix a and it is of the size of M * m * n okay so to transform it into a polinomial uh what we do is to use uh two dimensions of vectors the vector sorry the vector X and the vector y to separately encode encode the row and

encode the column okay actually they encode the the index of the row and the index of the column so Tak examp example uh those uh uh those vectors these vectors are actually binary vectors so if if the vector x equals to zero everywhere okay it is a zero vector and V yals zero everywhere okay this means that we select we select the first row and the First Column element in the

Matrix right actually we select this Matrix uh this element and this element uh uh is actually the evaluation of the Pol so here this the f is evaluated on x and y and x and y equal to zero vectors actually it will uh equal to the elements of the of the first the first element of the Matrix S a11 okay or a z z it is more okay so with this

technique we can write the Matrix into the polinomial so we can derive this form into the uh very complicated uh equation the expression below uh but actually it is very easy to understand it so if we look at the first sum here okay what does it mean okay uh as I already told the Matrix a is encoded as a polinomial uh on the variables of vector X and Vector

y so similarly we can also encode this uh Vector Z the vector Z with just one dimension of the vector y okay so the polinomial Z has the one dimension variables as Vector one so what uh so what does this sum on the vector y means okay so uh we back to our example here here is the Matrix a we use and in the according to the R1 CS

relation we have to uh multiply The Matrix a with the vector Z right so if we specified uh an index X for example we we specified the second the second uh index of the Y then we actually pick the second row of the Matrix right and in the multiplication this second row is multiplied with this uh Vector

Z okay and actually we are compute an inner product between the second row and the Matrix and the vector Z so how to express this inner product okay since inner product inner product in inner product we multiply each element in the vector one by one one by one multiply the first the first element to the first element of B and the second element to the second element right so we actually can use the vector y as a selector to select this element for each uh value of y is select

one element in the vector uh since we need to compute the inner product we need to select every element in the vector so here uh this inner product computation can be WR as a a sum actually a sum on the on the field of the the Y of the vector y okay so similarly with this transformation we transformed a * Z into the first part uh of this expression and to Z to the second part C to Z to the third part

right and we also Compu T them with the corresponding coefficient so but there is one more question since we transform this we will actually we will obtain um multiple inner product uh results right here in the R1 CS Rel the right hand side is actually a vector of zero okay so we will got uh here the vector uh the the the length of the zero Vector is is n i uh is m is M okay so we will got M constraints in the polinomial

form so uh but our goal is to build a uh build a polinomial for for the sum for the sum check so we have to aggregate this m constraints into one into one constraint to achieve this uh the previous uh task actually introduced another uh in equivalent functions uh and multiply it to the to the polinomial instance so this equivalent function actually uh it will output on output one only one only one his two inputs

here the vector rpha and the vector X they are equal if they are equal this function will output one and in other cases uh it will only output zero so we we will we won't talk too much about this this operations because it's unrelated to our discussion so I here I just write it here and it is meaning for the AG aggregation of of the zero Vector okay to the zero V so uh so far I have introduced the the

first part of the spart and we use encoding to encode the RS to the multivar polinomial okay so next what we going to do uh the second part of this spon is to run a some check on this polom we obtained the first obtain a polom of X and the prover claims that if the [Music] sum if the sum of the polinomial f equals to zero then we can uh obtain that the RCs relation is hold right so the verify the the verifi task is to

check whether the prover tell the truth okay so the verifier needs to check whether this sum holds so uh what he use is a s protocol so I don't talk about the details of some protocols okay so generally speaking this Su check protocols takes log and rounds interactions and to to check this uh some claim this claim on the on the SL right so in this log n in this log n interactions uh each interaction the

verifier needs to send a challenge to the pr so in total there are log n Challenger and this Challenger forms a challenger Vector we denoted as the vector RX okay and at the final step the prover needs to uh present an evaluation an evaluation of the polom F on the challenge vector or vector RX so in the right side the pro send the claim this claim to the verify and it claims that the polinomial F evaluates on the vector r x equals to

the result to a value CX okay okay so so this claim okay for this claim for this claim the verifier doesn't believe the pro so he needs to further to check whether this final claim is correct right so to do this the verifier can uh further reduce this this claim uh to several sub claims okay as we presented

here okay so this part is actually uh we mentioned before the the inner product right the inner product so to check the the previous claim uh the verifier ask the prover to separate to reduce this claim and uh send again some this three sub claims and this sub claims uh each contains a result as Sigma m okay the M can be uh can be a matrix as a matrix a matrix b or Matrix C so uh in total the prer will send uh

three claims with the claimed the value as Sigma a sigma B and sigma C to the verify so what we need this uh reduction actually this reduction uh gives us a new instance and this new instance is also a sub check a su check instance right so before this is an evaluation of F and the the don't know how to do it so uh after the reduction this evaluation becomes three claims on the Su so now the verifier knows oh I can use another

s check on this subcl right and this this Su check is wrong on the vector y so uh here I present our uh the third part of this SP okay uh the verifier the verifier will run the S check the second S Check protocol on those claim and uh those uh this s protocol will produce another polinomial G okay so uh so here one thing I I forgot to mention that uh although we got three claims here actually uh the approver and the verifier can aggre

aggregate them into one and this yields a new claim about a polinomial g polom g okay the sum of polom g equals to a value Sigma okay so in the second S Check protocol uh uh after after log rounds of interactions the Prov at the final step will send an evaluation a claim of the evaluation about G so again the verifier runs the same reduction process and he can reduce this this evaluation into another four Su

claims okay this four Su claims contains three claims on The Matrix on the matrices The Matrix a b and c and there are they are claim the value as Theta and another new claim of the vector Z okay this evaluation of Z actually equals to Absolute okay here the M actually takes input as RX and okay and evaluat on uh so this is the general process of

Spartan okay but as we talked Spartan is mainly built for the R1 CS instance the r1s relation but the R1 CS relation is not expressive enough so here is a new protocol called the super spart it is a p a piop for the CCS relations and so uh the CCS relation means the customizable constraint system and uh which can simultaneously generalize the current relations such as the plish r1s and the

air the air is the uh the constraint system used in stock okay so uh as we know the CCS relation is actually a very expressive relation so uh what does it exactly looks like okay so I present the polinomial form here for the CCS for the CCS relation U but I think it will be it will be simple if we compare it directly with the RCs okay so let me further introduce on the on the below

okay so the CCs in the CCS relation uh actually we got a set of matrices for example we got a a matrix set included elements of M1 M2 dot do dot m to Mt and this is the set that include all the matrices we will use and besides we also need to uh need some selectors as S1 S2 uh SQ

SQ so what does the selector do is that it will uh it contains the index of the matrices and and if we uh according to the selector for example according to S1 it will select some uh matri matrices for us for example the S1 May select the Matrix M1 and M2 and then according to the matrices selected uh we can we can compute a product according to the matrices a product okay and the product may include the the M1 M2 and the vector

Z okay and finally each selector will produce a product and to construct a CS relation uh we sum this product together and for each product we add another coefficient as ccii C1 C2 and CQ yeah and we sum them out so so it is also abstract right um but we can compare it with R1 it will be clear so in R1 CS relation we also have have a matrix set this set include the

Matrix three matrices a b and c and to build an RCS relation we have two selector S1 and S2 here the S1 selector will will Select A and B and produce a product as AZ C product through bz okay this is a product and and for the selector S2 it will only select one Matrix S C and produce a product only contains c times Z and finally we add this we add this product into

one and for each product we uh we also attach coefficient for the first product we attach a positive one and for the second product we tach a a negative one okay and this sum this sum will finally equals to to a zero Vector Z so uh so this this is actually uh take the R1 CS as a specific example as the CCS relations right

okay so uh the CCS relation I write here is actually encoded relation it is uh not in the vector form it is in the polinomial form but it is uh quite quite similar similar to the r1s relation we measure okay so you can you can regard this m MJ as a or b or c so it is more clear and you uh you do do not need to remember uh this relation because uh we only consider we will only focus on uh

the results produced in the Super Spot okay so what Super Spot do is actually uh replace the RCs relations in the sparta in Sparta with the new relations as CCS so similarly the super spart first runs an encoding and the second it runs the some check protocol on the vector on the vector X and third it write and wrun another some protocol on the vector y okay because uh the whole process is to complex so I did not present here and

we only need to focus on uh those two claims here okay similarly as we mentioned uh the Su check protocol will take an input as a multivarious polinomial here we write it again as the polinomial F till there okay and the pro and verifier WR a su check protocol to check that whether the sum of f uh x equal to equal to zero equals to zero okay so after running this first some check protocol on Vector X the prover will present several claims to

the verify okay those sub CL that we already reduced them right okay so after the first SU protol it present us with the first first class of claims okay those claim are mainly uh about another some check protocol problem right it's a problem is a su check uh on the vector Y and the polinomial includes the The Matrix polinomial the MJ and the those the next

Z polom and the prover claims that the sum of this polinomial equals to a value as Sigma okay since there are t matrices in total so the prover actually sends the verifier T claims and each claim contains the value Sigma Sigma one to Sig 2 okay so upon this uh sub claims okay uh it actually brings a a new some check problem for the verifier so the prover and the verifier uh again they repeated

repeatedly to run the second some check prot and on this time they run run the protocol on the vector y to check that whether the first claims are correct okay so after the second Su protocol uh the verify will obtain a class of new claims so this time this claims contains the evaluation of the a matrix polinomial MJ and and T claims in total right and another claim this claim contains uh the evaluation uh on the vector

Z and the claimed value we denoted as the F so this is the general process of the Super Spot okay we explain it uh with the Spartans for better understanding so uh so now we uh here we only focus on those those claims generated in the super St smart and protocol so why are we going to do that actually it it introduced some insights for us uh about how uh do we apply our folding

scheme for the instances that generated in the spot okay so now uh to understand this this question uh we can take two examples uh here the first example is uh you can try to consider uh if what if we fold two ccs instances with the same same circuit here okay the same circuit means that uh for each instance there are Matrix M1 to Mt are the same the only difference is

that uh the Z Vector of the first instance is different from the Z Prime of this like instance so if we wna if we want to fold those two instances how do we do the naive idea is to we directly fold them at the beginning of the super SL right uh okay after after this after the first part of the super SP okay we already encoded them as a as a multivariate polinomial f right so uh at this

position can we fold them into one okay it is theoretically feable but uh but uh you need to notice that this polinomial F it has the highest degree of d right if we directly fold this two polinomial into one polinomial then they will generate a large amount of crosss for us so how to solve this question okay is there any question uh okay uh

start hello yeah uh everything okay can you uh okay I heard someone someone's voice so so I think maybe there are some questions so uh no no no just someone say that they

had to go uh but you can continue okay okay uh so I just continue okay so I just talk about the question that we want to fold two ccs instances with the same circuit and the problem is that if we directly fold uh the encoded polinomial uh this two polinomial into one we will F the encounter the problem of the uh the larger amount of cost terms okay because this polom F has the of

D so what's the solution is uh introduce the hypera right uh and they also present us an idea that we can uh continue running the super sparton right until the uh right until we finish the first Su prot so so what is the advantage of running uh around of some check so we can focus on the CL here if we uh so before the Su check protocol we

got a pomal of degree of D and after the Su protocol we the Prov will present some new claims okay this new claims is only contains the Matrix one Matrix one Matrix MJ times a vector Z right so uh by doing this the the Prov and the verifier actually reduce the previous High degree polinomial into some new uh new new instances and this new instances only contains polinomial uh with the degree of

one so if we stop if we run the Su spart and stop here and we reg the new claims as our new CCS instances actually they call this uh relaxed CCS instances then it is feasible for us to directly fold this in instance with another in okay we for example if we directly compute uh compute an instance include MJ times Z and another instance contains MJ times Z Prime okay with a linear

combination okay since both of them are linear to the vector of Z so there will be no cross T right if we again we we fold this Z Vector together and we only need to compute the Z polom plus c times the V Prime Pol and we also multiply them with MJ Pol okay so there will be no extra elements we need to send to keep the original equations hold because uh it

naturally hold so this is our first case we we know that we consider two ccs instances with the same circuit so what if their circuits are different so here the second case if we consider the nonuniform situation and those two ccs instances they have different uh Vector Z here and Al they have different matrices from M1 to Mt and the second instance has M1 Prime to Mt

Prime so in this case can we still use the hypernova so unfortunately the answer is no right because uh under this situation those M and the the vector Z they can both be regarded as the variables of our pols as right so the total degree of the constraint is two and if we try to fold them together you will find that cost terms will appear right if we for the

MJ combined with MJ Prime and you need to multiply it with another folded Z it's Z plus c times Z Prime Okay C * Z Prime so this is a quadratic relation right so how to solve this question question how to solve this problem okay so again we can uh inspired by the hypernova uh the authors introduce

another a new round of some check protocol for the high degree High degree polinomial and linearize it into a claim so can we uh further run another round some prot here we continue running the Suess Buton and stop it right until the the second S Check protocol on Vector y finish is finished so with this technique we will obtain a new claims and this new claims as as I uh right here

it contains an evaluation of the uh Matrix M and an evaluation of the vector Z so what's the point is that the new claims will change totally linear on the on both the matrics and the so uh even though we take input as two CS instance with different circuits the non uniform C we uh we won't uh need to uh worry about the cross term problem

because we got totally linear claim on on each variable and if we fold them together there will be no custom so if we fold the first claim second claim here MJ times uh plus C * mg Prime right and the second equation is z plus C * Z Prime okay so and the right hand side of the equation uh can also be linear combined and the equation still holds

so through this through this technique we solve the question we solve the problem the cross term problem and when we try to fold two ccs instances with non uniform set okay uh as a summary uh as a summary uh as I show here uh by this Technique we run the super sparton for each CCS instances and stop the protocol right early stop the pro just after we finish the second Su

right and so in the original Super bot protocol after the sum the second Su protocol we need need to do another polinomial Oracle query right to query on this evaluation so we just sub here okay and we do not instantiate this oracles and the verifier want to query the pro and that so it's an early stopped version and uh what we obtain is a relation is a new relax relation this

relation we called the atomic ccss and this new relation contains uh these elements so the first line of elements is actually the same to the uh previous C assimilation and the second line contains those elements that are generated among the sub protocols and we need to also take them as a part of our new CCS relation so to check this accs relation uh actually we just compute the claims that we generated then we

generated here right here so first we comput the evaluation of the Matrix M on the on the vector RX and r y and obtain the result of C J and uh also we need to compute the evaluation of the polinomial Z and compare it with the result Epsilon okay uh so with this Atomic CCS relation we can directly folding these uh two claims right with another instance and there will uh they they don't produ

produce any cost temps okay so this is the first part of our paper and uh next we introduce how to build a generic folding schemes based on the Rel the relax CCS relations we introduced okay uh So based on the accs uh relations uh it is uh simly very simple for us to fold CS instan right if we want to fold the the input CCS instance is what what we need to do it's just two step first we we run

the super spart right we transform the those CCS into our new accs right we we just run and encoding and two Su protocols and we can obtains and since since SS is linear so we can efficiently fold them up but uh here is a a problem okay so uh the first okay the first process I introduce only focus on folding the CCS instances but this is not sufficient for us to building an IVC

or a PCD why uh okay let's review uh the IVC and the PCD structure here for the IVC for the IVC it actually computes a sequential of computations right so at each step to express press the function f uh we will generate a CCS instance but what's more is that on the previous step on the pre

previous step okay this is the number I step and this is I minus one on the I minus one step okay there will be a folding right there happens a folding and this folding will will produce a ccs and AC CCS instance the ACs instance and this accs instance is passed to the next step and in The Next Step the prover needs to fold the CCS instance uh with the E actually I make it more clear is that

uh here is a running instance that is a accs instance at this instance is updated uh every time after the step here is the ccs and the CCs is folded in the ECS and in The Next Step there is a new ccs and this new CCs is also need to be folded into the running accs okay and the accs is updated so here we encounter a situation that we have uh we have never considered right since it's before we just consider

folding the CCS inst we do not consider uh what if we take inputs of one accs and one CCS right so the first case we need to consider is that our folding scheme also uh needs to be able to fold a CCS instance and a accs instance so the second case is also important uh this only happens in PCD structure right so remember that PCD is actually uh a d right a a graph and for

each node for each number I note it will take inputs as multiple instances and those instances may also contains the folded the already folded instance generated by the previous step okay for example the IUS one and I minus 2 Step uh they separately generated two accs instance and at the I step the prover needs to fold them together and produce a new one so this case is also not not

considered not included in our protocol right so we also need to uh solve the problem that what if we take input as one accs and another accs how to solve them together okay uh so uh before introduce our Solutions uh about to solving this two case uh we first uh give a quick uh overview of the uh the folding of only CCS instances right so uh this process is very similar to the super spart

introduced so at the beginning of the folding scheme the approver and verifier will take input as the CCS okay multiple CCS instances and the first step they do is to encoding they will encode this okay CCS okay CCS this CCS instance and encode them into the multivariate PO form here as the F1 to F S1 we assume there is S1 number of instances in total as the input so we after the in coding we got

S1 number of polinomial okay and according to the spon we need to run uh some check protocol for each of the polinomial right so um this means that we need to uh in total run S one some check protocols right it is too expensive but uh thankfully those Su check protocol R in parallel can can be aggregated into one sub protocol so the Prov and a verifier uh upon this uh upon this multiple pooms they only need to run one

round of su check protocol and this Su check protocol will produce the first claims the first claims we mention and for for those first claims again the ver the pro and verify encode them to the new polinomial g s g and uh similarly the round the second round of some check on the polom G on those polom right and they obtain the final claims those claims are linear so we can uh directly fold them up into only

one accs instance okay so consider now consider the case we fold the accs instances so what's what is the problem if we try to fold fold this instances right the technical Gap is that uh we consider here uh also in the PCD situation if then if the I node takes two instances from from another two right another two since this IUS one node and I minus 2 node they are uh totally uh

independent process that that's running by maybe different parties right so uh it is nearly impossible that they will use the same challenges for the S Check protocol okay that's the point that we have to s for the node I the instances he take as he takes as input are evaluated on different challenge vectors RX and r y for

example we may got the different Matrix polom polom M and M Prime and M is evaluated on RX1 r y1 to the value of theta and M Prime is evaluated on rx2 and R Y2 and obtain the value of CA Prime so if we take this two instances we cannot fold them into one okay so how to solve this question uh this problem okay our solution is that if we have the ability to update

this RX and R Y at the node uh I here right then we can uniformize this this RX1 ry1 and rx2 r r Y2 into into a same into the same vectors as RX star and r y star okay so that we can fold this uh two two instances into one right it makes less things feasible okay two so now our task begin

uh uh becomes that how to update the challenging Vector so uh to achieve this there is already a technique that uh frequently used in previous work so what does that technique is about uh so we take an example now we assume there is a polinomial a multivari polinomial that only has one dimension of variables that is the vector vector X we we right now we don't consider the

vector y here only consider the simple case okay and for the uh for the verifier now he has a claim that the polinomial F evaluates on RX Vector equals to a value as V so now the verifier wants to wants the approver to update this claim okay he wants the approver to update the vector RX into a new Vector RX Prime okay and also the value as a new value

V so to do that the verifier will uh the verify and the Prov they will write a new polom as the GX denoted as GX and this GX uh is actually multiply the original polinomial FX with uh with an equivalent function okay and this equivalent function takes one input as the challenge Vector the old challenge vector and the Y input as the vector X so you can see that uh for the new polinomial GX it equals it equals to zero right it

equals to zero uh when the input of the vector X is not equal to RX so these two inputs if they are not the same then the GX will evaluate on zero so the GX uh evaluates to non zero only one the inputs are2 RX right this new equivalent function okay in such case this equivalent

function is equal to one and uh the GX is equal to F RX FX so the new polinomial evaluates to non zero only at one point and and it evaluates it vanishes of zero uh in any any any other way okay so now we the pro and verify a new some check protocol on this uh polinomial GX right and if they run this uh sum check

protocol to show that uh to to check that whether the sum of GX equal to the value V so a this claim uh will hold because as we uh deduced before as we talked about before the GX only only has one point of nonzero value the value is V right the value okay so it's a sum is definitely but with this Su protocol as uh we we can achieve another Target is that the some prot actually in the

interaction it will use some new challenge vectors right we denote the new challenge Vector used in the sum protocol as the uh Vector RX so after running of the S Check protocol the prover send a new clim about G and this G evaluates on RX and it equals it should equals to a new value of V Prime okay so now we got a new new claim this new claim is a new challing

vector and more over what more the polom f is contained in the polom G right so actually we through this technique we update the challenge Vector of F into a new one okay as a conclusion we got this uh this polinomial G evaluate on RX Prime and it should equals to A V Prime so uh so how what is the expression of the PO

G and according to the the constraint the polom G contains a multiplication between equivalent function EQ and a and another polinomial F right and so the EQ is public so the verifier can compute the EQ uh function by by himself and the pro also present uh the final claim re so to compute the new evaluation of f the verifier only needs to move the uh

the value of EQ to the right hand side so just let the V Prime divide the the EQ function okay divide the EQ function then we obtain the update is CL so by applying this technique iteratively uh twice okay one is for the vector X and one is for the vector y we can update our accs instance with some new challenge Vector RX and r y so and what's more this process is almost uh run the same step the similar

process with the folding of the CCS right because we we apply the technique we need to run a su check and we apply twice for two some checks and in the folding of the CCS instances we also need to run two some checks so okay this gives the overview of our uh folding scheme right we only need to care about uh those uh main process of this folding scheme so the right part uh the left part is is takes is the folding of the C CCS instances right and it takes some

check one and some check two and for those ECF instances we need to run an update protocol right this this updating protocol updates the challenging vectors and we also need to run uh one the S check the first round of s check and the second round of s check so all those Su check are WR in parallel and we can aggregate them into one process so in total uh no matter no matter how many uh instances no matter the CCS instance or

the accs instances we take the input in total uh we only need to run two round of some check and then after this process we can fold them up into one instance as the final fold okay so this is our uh final schem and also note that uh this instances we do not require their C are the same so our Sol scheme is actually a non-uniform Sol scheme okay and we also compare is you just

yeah sorry just one thing uh we are we are over time it's completely fine you can continue like there's no issues with it uh but just to just to let you know as I see you are in slide 20 of 36 uh so just for you to to take into account of course there's no issues like we can we can continue I'm happy to because it's it's been exciting so far but but just to let you know I'm sorry I'm not clear so I don't have time right no no you can you can continue like it's it's not an issue but from the hour theory that uh that this was supposed to to last we are we are already over time I was just like pinging you basically but it again it's

not an issue we can we can just continue oh okay just for you to to let you know okay I got it okay so so I just continue and there is the last part of our our paper okay uh so so I quickly compare the performance of uh the folding scheme we proposed okay so uh our folding scheme compared to the NOA uh we actually have the same sympotic performance with hypernova but concretely uh since we stops the SM Buton later than the hypernova so we we run another round of

some check protocol uh so so constantly we will uh take another log n interactions okay if we use the F here uh we need another log in random Oracle like hes but uh with this cost we achieve the features that the hypernova does not provide that is the nonform c f okay and compared to another paper that recently published just last year and uh the pr Galaxy uh so uh so theoretically the prot galaxy has lower

uh recursion overhead because in its folding scheme uh they only need the constant size of random orles and but as we as I mentioned just before the proty they try to solve the cross terms another idea just uh Z try to reduce the number of the costs so uh to to achieve this they have to apply some other uh optimization technique some makeup techniques and this technique uh are quite expensive so the proval cost of

the prod Galaxy is qu linear while our proval cost is linear right because some check the pral cost of some check is a linear so uh besides I would also like to mention uh uh another optimization that we made for our for our generic R soling actually this is a bonus property that we observed in in in our design right so uh what our what I try to express here uh uh since we have already run to run

the some check protocols for our uh CCS relations and obtain uh those linear claims right we obtain the linear claim on each Matrix M1 and to Mt right so so theoretically these claims are in in dependent uh of each other so can we batch those claims the verification of those claims together right this is uh this idea is uh mainly because since in the real world

implementation we have to com compute the commitment of this Matrix right and with some uh primitive such as the based on the D assumption right so if they there are committed keys are independent that means that their DL uh they they satisfy the DL Independence right then it is secure and totally feasible for us to multiply all these commitment of matrices into one so now this gives us a very a very

exciting result that uh our new optimized accs instruments only contains two claim the first claim is an aggregated Matrix and we need to compute it evaluation and the other is the about the vector Z VOR Z okay so what's the advantage of this optimization okay uh so the most the most significant uh influence of this optimization is that uh our IVC

proof or the PCD proof okay does not need to uh uh does not need to those T Matrix right it only need to contains one Matrix okay uh so let's move to the uh final part is the construction for our Z knowledge BCD okay two uh as we mentioned above there is actually a technical problem for us to building a zero knowledge folding scame okay since a z kpcd requires uh a basic primitive

building block as the ZK folding spe right it needs to build on this uh peret so right now a common method for the ZK folding scheme is to mask the winess with a random Vector okay for example we just uh take the Vector Z as an example uh we must the vector Z with another random sample Vector VR okay and with a challenges and this linear combination if we directly put them into the high degree relations it will uh bring us the

cross terms the first problem is cross terms and another cross term and another problem is is that we need to uh recompute our relations for this Mass witness so it introduces EXT computations for our program okay uh therefore uh our main idea is that we don't use we try to avoid using the masking value for uh the Zer knowled property we try to use some more specific and fine green uh technique to uh to guarantee the privacy of a of our

witness among the the process that we run the super SP okay so to do this a quick recap of the gener generic folding sche we proposed okay uh this time we only fold uh focus on this uh blocks and we trying to find those blocks that will leak the information of our winess so uh so basically there are three parts that we need to care we need to uh concern the first part is the Su check part okay those two rounds of some check protocols uh they uh they actually run the interactions between the Prov and

the verifier and the approver will send uh some response to the verifier those response contains the information of our witness okay and the second part is the claim part right those claims as we mentioned is actually the evaluation of the PO right for example the the second claim it contains the uh the polinomial Z and it contains the evaluation on Vector y equals maybe to an ABS right so this uh value Epson uh it contains the information

about the vector Z and also the witness so we have to random randomize this uh value of f so the third part uh we mentioned it actually is not uh be regarded in the process of the super sparton okay it's uh so the third part May leak the information of the witness is the F folded accs the folded accs so if we run the folding scheme correctly and with some zero knowledge property the obtained accs will not

leave the information of the weakness but uh we need to notice that after after we produce the ECS the verifier needs to carry out some polinomial queries to the oracles right so so in this in this Cruise in this C the C is upon the feds and this c will uh inevitably contains the information about the about the weakness right so we have to make the folded AC as itself to be Z knowledge okay we solve this problem in

meing three techniques the first uh techniques is a technique for uh providing zero knowledge for claims and the second is providing zero knowledge for our some check protocols and the third is the Zer knowledge for our folded instance so let's talk about the first technique that guarantee the zero knowledge property of uh of the claims of the claims okay so as we uh as we mentioned those claims uh actually if we directly mask the witness and it will introduce the cross terms so our main idea is to how

to avoid those cross terms uh generated uh among among process so uh our idea is from a previous work uh published in in 20120 and this technique is is actually uh already frequently used in the uh in the in the in the development right uh in the real world implementation so um the general idea is is true is that instead of masking this witness with random this we we use a padding

technique for this weakness so how how do we do that for a vector z uh we just uh P it with another Vector another random vector v r here so in our scheme we only needed uh random Vector r with less of two okay I will explain this later so we just remember that we pad we extend the length of our Z with two xual random values as R R1 and R2 okay and correspondingly to make the equation

well formed we have to extend the Matrix that multiply with with Z right we also need to extend the Matrix to a bigger one okay and here we add it with an uh ident identif identity Matrix with the size of two * two and now the here we take the RCs as an example the R1 CS the R1 CS relation becomes in this forms right this FSE okay for the CCS uh the same situation

happens so for this simple padding technique there are some several facts I want to mention the first fact is that the padding technique different from the musing technique uh we don't we don't mask uh this our witness with r b we just uh enlarge them so with this enlarged space there will be no cross terms if we if we try to fold them with another instance okay so for this new RS instance if it is folded to another one there will be no

cust so definitely we need to round the but first right uh and the second factor is that uh is that this padding scheme uh this padding scheme uh the number of what we need to pad it uh actually it has a a regulation right so the number we pad it must be larger uh than than the than the queries that we will send to the Oracle okay if we queries the Oracle two times then two

extra random values need to be paded okay so that's why we use uh lens of two because we we in total we got two claim right and each claim contains a query to the vector Z so to protect the uh Witness uh among the claims we need to add extal two random values in R okay okay this is this is actually the factor three so for the factor two uh that uh the padding technique that it cannot be used in uh uh in any cases

that we encounter uh so it has some limitations the limitation is that uh for the query for our Oracle that the uh the query response must be a linear combination that including each element in the witness okay each element in the witness W but thankfully uh the claim that we are try to protect uh they are all linear combinations of with this Vector okay and the fact the factor four

actually uh introduce uh optimization okay that's an OP optimization okay so in the Imp in the real world implementations we there is no need for us to add random values to the vectors Z so why is that this is because in in the implement implementations we need uh already pad our Vector that into to the length of the exponentiation of two right because since we got a vector of Z

we need to pad it to the length of the uh two to the power of K right so uh this uh previous zero padding technique right already gives us some some this place to insert our random values into into right so we can just directly replace some of these zits with our random values okay so actually uh this tting technique will uh add an um add a little cost to the our

hosting and the second technique is a zero knowledge technique for the S check prot so actually it is optional so let me explain why it is optional first uh uh this is because for the somech protocols there are log and rounds of interaction right so in each interaction in each interaction actually we can regard the verifier is sending a query to the prover and the prover gives a response back so so in fact we can apply the same technique that we we used for the claims

to the uh s prots but uh what our cons uh concern here is that uh in the previous Technique we only need to add two random values but in the S protocol we got two some protocol and in total we need to add log M plus log n uh random values to to as the padding right right so uh so in case of that uh we will encounter the condition that we run out of this uh zero zero bits right the

log n plus log n number is larger than the derit that we we have so under this situation we have to double we have to double the length of our Vector okay we need to double two to the power of K to two to the k + one right actually it will enlarge our circuit and add ex uh extra cost so uh for this uh situation actually we provide an alternative technique to Pro to provide zero knowledge for some Che protocols okay we

can also apply and of the shell uh primitive that is called Zony Su check uh given by K at [Applause] 2017 right so it's uh technique is very simple we just need to uh mask the polinomial that we need to prove with another random polinomial of the same size okay and since we we mask this polinomial in the Su check protocol instead of the CCS checking the CCS relations so this technique will not introduce cross

terms and the third technique is the terminology technique for our final fold dat instance okay and uh to achieve this is quite simple we only need to uh add exra random sample the accs instance to uh to the list of our input instances okay for example we uh got K uh instances to be fold we only need to add another random sample the ACC instance okay to this Cas and the way total for in total for the K plus one

instances okay and also this the knowledge technique is very efficient uh and easy to to implement so finally uh through this three techniques we obtain a zero knowledge generic sing schemes at us so now we can construct our ZK PCD but there is still a theoretical gap for us uh when we try to design this so uh mentioned uh and proposed by bcms 21 uh bones has introduced a serum and for the construction of a zero

knowledge PD so simply it states that if we try to build a PCD scheme we can compile any knock any n system with an efficient accumulation speem so and uh s it is interchangeably to the sing schem so we can compile any n with sing scheme and obtain a PCD and if we try to achieve the zero knowledge for our PCD then there are two unnecessary conditions the first is that the KN is zero knowledge and the second is that

the folding scheme is also thege so according to our previous uh techniques we only build a zero knowledge accumulation speed we uh is we didn't uh uh we didn't achieve a zero knowledge in do system okay to further explain this uh problem we need to first uh CL clarify that what is the KN mean what does the KN mean in the novas construction okay the following figure presents the IVC construction uh for

each step uh in uh in the Nova right okay so briefly speaking in this uh step the the Yellow Block the yellow box we draw here uh is the recursive circuit and the recursive circuit uh mainly includes two part of computation the first part of computation is about the function f that is the the function for the IVC and the second part is the verif verification algorithm for the folding scheme right the fold. V right and to run this uh to run this IVC step with first the prover needs to run

uh the approver the folding scheme approver algorithm and it will produce a pro Pi okay in NOA this Pi is actually the cost term T right and send this pi to the recursive circuit and the recursive circuit will will check that whether the approver has correctly folded the instances with the p right and output the final folded instance as the uh the big U i+ one okay we de here so uh at the same time the prover

in the recursive circuit will execute the function for the IC right and after all these two two circuits are uh are finish it then the approver will write write the circuit into a new instance here a new instance with Miss pair here okay so this instance withness pair is expressed in a CCS s relation okay the folded instance here is actually in accs instance so okay so what is the n uh for the

construction in in Nova okay so actually the N specifies specifies the the uh the argument systems for our recursive circuit so what does it mean it means that what the uh what the argument system the V the approver tries to transform the recursive circuit okay into the CCS okay is the KN okay so for the CCS incidence uh

generated it can be the witness it can be directly regarded as a proof for the KN because we don't need to succinct and z z right the witness is actually the proof and for the and a verify of this Mar it just take the witness and check whether this CCS instance is satisfy okay this is just the verification algorithm from but the question is that here we only realize the zero knowledge property of our folding scheme but but for the for the N for the CCS we generated it is

not zero knowledge but this CCS must be sent to the next step and if the next step is executed by another party then the witness will be leaked right so then our task becomes uh very clear is that we need to get guante the Zer of the CCS instance generated here okay uh here is a n example for for the CCS I just mentioned okay the proof for a CCS instance the prover just send the

witness directly to the verifier and the verifier takes the witness and check the Cs but uh so our main goal is to achieve the zero knowledge for this ccs and we need to build a z knock for those CCS relations but here again we encounter the same dilemma as we mentioned if we directly transform this Mar into a zero knowledge verion for example we use the M value this will

evitably introduces cost terms for us right also uh if we try to use another for example the Ping techniques or other things uh anyway uh anyway we need to uh intiate a new process a totally new process for this Z for this Z proof for the not right and this new process introduces expensive cost for the pram and we are not even sure uh whether this cost can be optimized uh in the uh through other optimization

techniques for example in the producty right before because this KN actually it happens before our sing scen right we need to uh first transform the knock into Z version and then we execute this Sol so we are not sure whether the costom generated in this step can be optimized uh after the uh the fing spe so we try to uh uh uh we try to solve this problem in another way so uh after review the construction of

our sing scheme we have found very inspiring observations the OB uh this observation is is that actually our early stopping super sparton okay it's the encoding we execute and the two rounds of some check we execute right this early something Su spon it already provides as a transformation technique right from a knock to a zy KN why is that okay so what is the here as I mentioned the is the

CCS right is a CCS Rel is for the Cs Rel so after we execute the super Spartan protocol what we have obtained we obtained is accs relations okay so actually we transform the old KN for the CCS into a new KN for the accs and more and what's more we have Implement zero knowledge for our for our sing scheme the super SP right we have Implement uh add some zero knowledge

technique for it and the ACC as we obtained is already zero knowledge so the conclusion is that we do not need to to introduce another new process for achieving the Zer knowledges for the mar we can directly reuse use our folding screen to transform the KN into the KN okay how do we do that okay the

conclusion repeated uh we can obtain a zero knowledge not by utilizing our zero knowledge folding scheme okay to achieve this we can split the recursive circuit into two parts okay remember the recursive circuit I have presented okay it includes two uh subcircuits the first is the function s the second is the fold the verification for the folding SC so we do not integrate them together we separated them the first circuit include a function

f or a predicator anyway in the PTV and the second circuit is for the folding verification then what we going to do what we do is that we first produce a in an instance witness pair of the first circuit okay this circuit actually produce an instance winess pair in CS and then we take this CCS instance as an input for the folding spin of the second circuit right we feed them we

feed this CCS instance into the folding scheme verication and by uing the zeron knowy of the fing we can transform the CCS into a z key HS right a z key so before I introduce the Concrete Construction uh let me give you the new theorem we have developed this theorem state that there is an efficient transformation that compiles any KN with an efficient zero knowled folding scheme into a zero knowled PCV okay re we

removes the requirements of a z kn we only zero knowledge holding scheme then we can compile any not into this okay so uh this figure compares the our new construction with the old construction given in IVC uh in the no IVC so I I have already uh Illustrated the the left figure just before right and for the right figure we only need to uh notice two points the first point is

that we separate the recursive circuit into uh two part the part one only contains the function f and the set part two only contains the fing the verification of fing speed then the pro first execute the first circuit the circuit one circuit one here and the circuit one will output will output a CCS instance this CCS instance is not zero knowledge and we denote it as the U Prime and W Prime okay and this U Prime and W Prime is

then fed as the input of our folding scheme here we folded the U Prime and W Prime together into the ZK folding the appr algorithm and fold the instance the public instance U Prime into the verification algorithm and guaranteed by the zero knowledge of our folding scheme we uh the prover further writes the second circuit into a new accs into a new CCS instance right and the folding scheme will fold

our previous CCS into a folded accs here the accs so since the folding scheme is z knowledge the output accs is zero knowledge and where is the previous CCS where is this CCS it actually is folded into the SS so we do not need to worry about the wi is laked from the uh the instance we output because we output a ZK ISS okay so this is our new construction

so uh zero knowledge uh of IVC and PCD okay so actually this new construction okay this is the last the last point I want to introduce is the delegation part okay uh I just quickly introduce my uh basic idea uh so we have already obtained a ZK

PCD and it can support nonuniform circuit but uh when we try to implement it it uh we have encountered some potential practical problems okay the first problem is that uh if we keep fold right in the phon scheme we need to fold the Matrix we need to fold MJ with another uh MGF Prime right then before the folding the Matrix may be uh some sparse Matrix with with only

uh with only several positions of nonzero terms right but after we folded with a linear combination our folding Matrix may not be this uh may not be Spar it will be this right so it it prevents us from using some optimization technique such as the pre-processing like the holographic setting to to optimize uh the uh the cost for for each for expressing this Matrix right

so each time we send the matrices we cannot uh just just send the nonzero terms we need to send the the whole matri because it is yes and also when we try to uh do some operations on the matrices uh there will be a larger cost for the pr and the second problem is that uh since we build PCD in a in a potentially multi- uh party system and those parties are independent uh users so from the user one to the user

two if we if they try to carry out the computation then the user one has to send the message the necessary messages to the user to and in the message uh there will be a large part of the matrices right here is the m is the no the user a and the user B then the user a after he has finished his computation he has to send the instance uh to the user and this instance includes the circuits

information the matrices right so sending the matrices will uh contribute to a larger communication cost okay so what we observed here is that uh the linear claims the accs instance right that generated from our folding SC they only contains two claims the first claim is about the Matrix and the second claim is about the vector Z so in fact those two claims can be checked

independently okay uh at the first glance it seems uh a little bit doubtable right uh but uh after we actually do a security proof about this property we have found that as long as we ensure that the the challenge we used for the linear combination the challenge is c for example for the linear combination between different Matrix and z are the same then we can independently check the matrix and check

the claim on the vector Z so uh and and another point is that those Matrix they are all public informations right they just represents the instruction set in the virtual machine and the in other examples right so everyone in the network access to the this public information so we can securely delegate the cly work of folding this matrices to a third party okay

okay so this is the idea the main idea of our delegation and based on this idea we also develop a new construction for those uh delegation right uh and briefly speaking we or we what we only need to do is uh is to keep that the challenge C we used for the fold of Z and the fold of fold of M uh are the thing right so uh with only this with this limitation we can ensure that the H

system is secure and so we can safly run the folding the original folding of z uh the computation in a PCD system and we can delegate the costly uh folding of the of the matrices to a third party and the third party only needs to run an IVC okay the point is that by this technique we can shift right we can shift the costly work through a more powerful third party and what's

more since they third party here only runs an IVC okay he is a individual an independent individual it keeps track the computation in the PCB and folds The Matrix corresponding and he does not need to send extra messages to other parties right because here the IVC we do not consider the multi party situations right and the third party do not to share those matrixes to others he just sold it by

himself so uh this point actually eliminate the communication cost uh for the folding for the matrices okay and uh all those advantages will we believe will make our pcdc system more practical uh okay okay lastly let me give you a brief summary so in this paper uh we actually proposed two uh cryptographic Primitives the first is a an in efficient General generic folding schem and it supports nonuniform circuits and multi folding

and the second primitive is kilon NOA and it is a zero knowledge in uniform PCD and we also contribute to a new theorem that it is uh actually efficient construction for the ZK IVC and PCB we remove uh a limitation that exist in the previous Ser okay as for the future future work we try to uh first build a prototype for our zero knowledge PCB system and we also try to find more applications and uh a more long-term work is to further optimize or enhance the performance uh

of our PCD constructions right and we uh actually we got some ideas for this optimizations okay uh so that's all all of my sharing okay so uh thank you for your listening thank you very much thank you very much uh uh I think we don't have much time for Q&A as we are uh over time quite a bit uh but the the presentation was like really really no no worries about that no worries about that no worries at all it was really nice and the the presentation and explanations were

really extense and really deep so I think it everything was quite quite clear um I mainly wanted to say uh thank you very much for coming here today and and going through through the entire protocol and paper and and explaining Us in great detail uh all of these topics and aside from that uh I yeah just wanted to to uh to basically thank you again and and in case uh you are okay with it we will upload uh this talk to YouTube so that all of the people that missed it wants to review some details or parts of the explanations can can access it and and review it again

online if that's okay with you how how does this sound is it is it okay from your side uh okay can you hear me yeah yeah yeah I can hear you is it okay from your side if we if we upload the presentation yeah yeah sure okay okay thank you very much man uh uh thank you so much for for coming here today and and and explain all this and and talk to you soon