SNARGs Book Study Group - Week #3 with Guy Weissenberg

Transcript

um so hey everyone um uh my name is guy I'm a p student here at tfl um and um yeah let's uh I guess we can uh start um today we're going to talk about the third chapter of uh Al and alon's book about uh constructing um non interactive arguments in the r random Oracle model um and this is kind of going to be a up of whatever we did uh two weeks ago with Christian so uh back then we were doing um non interactive arguments from Sigma protocols and now we are going to do it from uh IP um and just looking at

the the content of this chapter so we are going to focus mostly on the first two uh parts of of the chapter um which are mostly definitional but um but I feel that if you understand them the rest is going to be some additional flavors and it's going to be uh pretty easy to to understand um we are not going to really cover much about the optimization or the additional security definitions but uh fine I guess as long as we have the the main ideas in place we we should be good um so okay any uh question about the the program more or less

um okay so uh let's just start so um proofs are um ubiquitous in comput computer science in particular in theoretical computer science and I'm I assume most of you have heard what they are and if you haven't you've probably heard the name Sam um which is um the most well-known um example of U of an interactive proof um and so in terms of definition uh an interactive proof is a tle of two algorithms right so we have an algorithm for prover and an algorithm for the verifier um so let's look at this diagram here uh I wrote basically all of

the terminology that we need um here so um like I said we have the two randomized algorithm algorithms we have the pro and the verifier we have some instance that's what we're going approver and the verifiers going are going to be talking about um and we have we have a witness as well um so you can think of it like uh the instance being like a program you want to run and um the witness being uh the intermediate steps so you can actually prove to the verifier that you uh um did the calculation According to some um to some program which is the instance um so in terms of uh ter ology

the number of fronts is going to be K and this is going to be consistent um Throughout the chapter and I guess also the rest of the book um the prover messages are going to be denoted by Alpha uh the verifier messages are going to be denoted by row um which is kind of kind of like why why why this choice of letters um so I don't know about the alpha but for the rows we're going to be mostly talking about what's known as public coin interactive proofs which I'll Define um shortly but um so the verifier messages are just going to be some random beats so row stands for random um okay so around is going to be uh a set of uh two uh interactions shall

we call you that so the prover is going to send um a message the verifier is going to respond and we are going to call these two uh messages uh around um okay some more definitions um the interactive proof is going to be um given for for some relation right so we have um a relation that is supposed to Define us a language right for example um uh if if you know about Theory computer science so maybe X is going to be s s s formula and W is going to be an assignment uh to the variables of the formula um and the language is going to be set right so like every

every instance uh that has a satisfying assignment such that uh the relation um contains the relation contains contains both of them um okay so finally after the can I put that another way this this idea of of relations so in the case you just gave right so X we have a formula X is that formula we want to know whether the formula is satisfiable or not to show that it's satisfiable we give a witness that witness being the set of assignments to the variables in that formula and so in this interactive protocol the goal is for the pro to show that X has a satisfying assignment and they do that by showing the existence of

a w yes um so actually like you can think about many flavors for that right uh so a trivial um thing that the the approver can do is just send W to the to the verifier right um and maybe in terms of uh the size of it you just don't want that to happen so maybe for a s formula it's not that problematic but if you want to uh I don't know prove to the verifier that you did a very long computation maybe it's not the best thing to just output the entire all of the steps you did in the computation so uh you would want to do some something more interactive that might be able to convince the verifier uh just with less uh with less bits communicated um does it make

sense yeah thank okay uh great so um now for um for interactive proofs we have two important definitions um the first one is completeness and here we are talking about perfect completeness so what I want to say is um to say that if x is in the language is described by this uh IP um the verifier is going to to be uh to accept and we want it to be to accept always right so we we call it a perfect completeness uh to denote um that um so in particular we are going to be talking most of the time about this definition right this notation right here this is

going to be um the random bit of decision for the verifier so the ver Pro and the verifier interacted the prover has X is the instance and the witness the verifier has just the instance um and they interact remember they are both randomized algorithms so this kind of um so they're interaction is is randomized and eventually the the um decision bit that the verifier outputs is also a random random bit so we are going to be uh seeing this notation a lot and this is by the way true for interactive protocols in general throughout throughout the book eventually will um get to more complicated uh terminology that uses

iops and and so on um and we use that to denote the the decision bit um good so basically what we want to say that if um X and W are in the relation the probability over the randomness of the prover and the verifier the probability that that the decision bit is one is one so we call this perfect completeness um sometimes people Define like uh this one is replaced with some other uh probability but uh in this book we are mostly interested with um um probility the probility being one that is perfect completeness um okay so the next definition uh which is going to be uh very important for us is the definition

of soundness and the definition of soundness means that for every X which is not in the language um and for every malicious Prov strategy right because X is not in the language so like there there shouldn't be a way for the pr uh and the verifier to interact and the verifier would say that X is in the language right this is by Design we want not to happen by much and quantify this uh our desire um we actually use the soundness um definition and we were we are saying that the probability that the prover and the verifier interact and the verifier uh decision bit is one and notice here by the way compared to

compared to this uh you don't have uh X and W here because it's a malicious prover right like there is no way um so it doesn't really matter um okay so we want to say that the probability that this thing is one is bounded by some uh Epsilon okay so we want it to be um small um any questions about the definition of completeness and soundness okay um so I I assume many of you have seen it and it's like uh ja and Christian also me mentioned this but it's important to mention and the most important thing in terms of uh what's new for for IPs is this notation

right like we are doing we have some interaction and and we get some bit after this uh interaction okay uh uh some additional uh efficiency measures that we need to maybe care about the first one is round complexity so want to say that round complexity shouldn't be uh much right like if if we design a very good interactive proof we don't want to veryify to to have like round complexity which is the size of the weakness right so round complexity is an important measure and like I said round contains U two messages one from the pro and the one from the verifier um second one is communication complexity uh same goes for uh for communication comp complexity in terms

of um us not wanting the verifier to be able to um extract the weakness in full we don't we don't want the verifier to read um um the we so most of the time um but that but but that's by that is not by definition required in IPS but I'm just like uming you for like what we would eventually want from from our IPS to satisfy um and finally we want we have some consideration for the pro runtime and the verifier runtime um if you're from the ZK Community I guess you you know that we care about um um prover approver runtime being linear

um and um yeah so so there are there is also some consideration in and in many of uh of the well-known uh protocols such as like vanilla samchuk that you will uh that you read about in complexity books that's actually not the case so for some Che the approver is is not efficient um okay so any definition as any questions before I go to definition of um public Co interactive proofs I don't see any in chat but just reminder that to to folks here that you are welcome to sort of pop in with questions you don't need to type them in chat if he yeah you you can you can unmute yourself and ask if you have

questions yeah umol um and I encourage you to do it to do it I mean maybe these definitions are not uh super difficult but they will become more and more difficult um as we uh continue um and and everything Builds on top of each other so if you don't understand these definitions now you'll have a bad time later sure um that is that is true um okay so uh so far we were talking about IPS in general uh and and a very important class of ips uh is public is the class of Ip a public coin inter IPS and what is public coin IP so a public coin IP is an IP which

basically the verifier messages are just its randomness so remember I said that the verifier and the prover are R randomized algorithms right so they have some uh Randomness U that they own and in public coin uh interactive proof basically what happens is that all of the messages from the verifier are going to be uh the verifier own random coins right um and we denote this by uh by that so basically the decision beit of the verifier is fully determined by the prover messages and the its Randomness that it shares with the prover and of course the the instance so notice that there is no other Randomness

uh in this uh in the decision of the verifier and I I don't know if it looks if it looks weird or not to you but in some sense it shouldn't look weird to you because in many protocols that we that we know and love like uh think of fry for example the proof the verifier is just all about um trying to catch the approver on a random point right so the verifier is going to send some random Challenge and um because it's random the the prover cannot prepare for it so the fact that the verifier messages are just random beats shouldn't be so surprising to us um and apparently it it captures a lot of the power of interactive proofs um

just with this uh definition of public coin um and from now on all of all of our interactive proofs are going to be um public coin and in particular it matters much when we talk about the fat transformation that we'll uh see next um we we can't really talk about that if if the verifier has some Randomness um that it that it uh doesn't share with theover um because eventually we would want to replace the randomness by some um random Oracle right uh so this is also why we think about um public Co interactive proofs and um and yeah so so it's like a very important class of interactive groups

and in particular this is going to be the only one that is interesting for us um I think also for the rest of the book um I have a question about the randomness the verifier needs to know the domain like where where they pick the randomness from is it like the normal domain or it's an extension or what what is it um yeah so you can assume the approver and the verifier know what what they're expecting and um so maybe like interactive proofs is is kind of like the rules of the game so like they interact According to some uh some rules which are the rules of the the interactive proof uh right and and in this the definition of interactive proof

you have the the setup right and and in that setup they they should they should know what they are suppos to send each other um and in particular they should know what they're talking about because otherwise how how the verifier can expect to be convinced and how can the approver expect to convince the verifier um so we we are going to assume that these things um are known to both sides um any any other questions okay so now we're going to talk about a couple of um more a couple of definitions uh related to properties we want from the IP okay and and one an important property that we want from an

IP is to have what we call Knowledge soundness right so if you remember before the definition of soundness basically said that if uh X and W are not in the relation that is there is no W such that X is in the language um the prover the verifier should reject so this bit of decision should be zero um but how can we quantify um the probability that the verifier how can we quantify the fact that we want that if the prover accepts it's because there exists a witness right we want to be able to say that acceptance from the from the verifier sorry um means that there was a witness um in mind so like

the prover cannot convince the verifier without having some W witness um and for that we're going to to define the notion of extractor right and this extractor is going to be um is going to have access to an interaction transcript and it's going to have a blackbox access to the prover um right because if it didn't have it if it wasn't black box maybe um the extractor could see the the weakness right so for that uh for for like the specific definition of um an extractor algorithm um let's define

the failure probability of some Pro strategy okay so for a specific prover this prover which is deterministic so there is nothing uh there is nothing crazy going uh going around in particular it's not related related to the witness or instance you can think of it as hard wire if you want um then the failure probability is uh this okay so the probability that the pro and the verify interact get um the decision with is zero then we can Define um the extractor algorithm um as follows so we're going to define the extractor um such that when you fit it they the

instance um Alphas which are the ver the verifier sorry the prover messages rows which are the verifier Randomness and a black a blackbox access to the approver we going to be able to extract a weakness right and we want to say that the probability that x that you extracted and the weakness sorry x that you get and the witness that you extracted proba that they are not in the language while you were able to convince the the the prover uh the verifier so like we have this B here right this b means that the pro and the verifier interacted and from the interaction you

get some some bit in this case it's uh it's B so in other words what we are saying here is that the probability that you are able to convince the the the verifier but W that the extractor um um outputs is not in the relation so like xw is not relation this probability is small okay and it's going to be related to the success probability or the failure probability depends on how you want to look at it um of the Prov that we are looking out okay um moreover we want to say that this extractor runs in uh expected time it is dependent on the failure probability of the approver

and the runtime of the approver because eventually uh the extractor might want to rewind or do crazy things with the blackbox access that it has so it needs to run the the approver um so yeah so this is what we we want to uh say about um about extractor um and let me just recap this definition and I know it's a bit technical but the most important thing uh to remember is that you want to have some algorithm okay this denoted by uh e that if the prover and the verifier interacted and the verifier accepts so

it outputs this B which is one there should be an extractor algorithm that outputs W such that X and W are in the language so we want to say that the probability that X that this W is not in the language is uh small so it's upper bounded by some uh probability um does it make sense do you have you have questions on this definition have you seen this uh previously like definition of extractors I think maybe Christian mentioned it [Music] um okay I'm going to assume it's uh clear we are not going to talk so much about uh this definition um it's

important to note that all of the definitions we all of the constructions we are going to see um soon have this have this property okay um so yeah let me just mention that there are a lot of flavors of extractors and they're used for for multiple um different use cases uh it's really an an active research area um and they give you uh better and better knowledge uh knowledge soundus guarantees um let me just mention this straight straight line extractor um definition in which the algorithm just receives the

input and uh the proval messages but not um the verifier messages or the access to the prover so the extractor basically gets almost nothing and from the interaction uh of the from just the Prov messages of an accepting uh transcript you should be able to um output a witness so that would be very very a very strong definition of knowledge extraction so that just by having the the Prov messages of an of an accepting transcript you are able to extract accepting witness uh so this is something that is usually very desirable to have like this straight line extraction uh which uh which will come up um in future

lectures um okay another very important uh notion for um interactive proofs is the notion of zero knowledge um we are in a ZK hack session now right so I I assume many of you know what is zero knowledge but let me just say that we are eventually working under the assumption that everything that is efficiently computable is uh free right so if we if if we see something that we could have done ourself we are going to say that we learned nothing so basically what the definition of zero knowledge says the following the pro and the verifier interact and they have some transcript and in the language in the

language of zero knowledge ter in the Ling of zero knowledge we're going to call this trans script A View okay so this view is going to be uh determined by the prover the verifier um the instance and the witness and um we want to say that an interactive proof is is zero knowledge if that view of a true prover and true verifier um interacting with with the presence of a witness notice here there is a witness here so like acces in the language and we have um a witness for it want to be able to say that there exist polinomial time algorithm

probalistic U maybe um that actually outputs transcript such that the output output of this um simulator and the view of the real um interaction are going to be statistically uh close and you can say uh a lot of things about whether we want this to be statistical whether we want the distribution to be actually the same or like computationally distinguishable um but um yeah so that's the definition of um zero knowledge um very briefly but I but I but I assume most of you have seen it before um do you have any questions

about uh that definition or if you haven't seen it before do you have any questions about that okay so so far we have um set the ground for the basic definitions of uh of Ip right we Define what is soundness we defin completeness soundness the some terminology about number of fronts and so on and um we said something about knowledge soundness which is also an important property that we want and zero knowledge now we're going to get to the main definition of of this session which is going to be a state restoration function uh State restoration sness sorry so the the quickest way I found how how

to explain it is that a state restoration soundness is a property of a public coin IP that quantify the how much the prover can learn about random function um that the verifier has um and it's kind of plays a game again against this random function to be able to uh fool the verifier eventually so I don't know if it makes it less or more cryptic but I hope that um once we are um we're done with this this uh explanation it will be um C so like I said we are talking about

public coin IPS right so the verifier only has um only shares its Randomness right so maybe you can say something like um okay let's let's assume that the verifier has some random function that it um just queries on something and then uh send the output of this random function uh to the to the prover because this is essentially what is happening right because the pro the verifier just shared its Randomness so now we can say okay let's say that it's not just a random function that the the prover the verifier has um by itself but maybe it's some random function that the prover can interact

with um and this kind of motivates us to think about random oracles but in any case if the prover can um I don't know ask a lot of things from from this uh from this function um maybe he can he has a better um chance of fooling the the verifier so this kind of intuition is what what is being formalized in this notion of straight restoration soundness so this notion is defined using what is known as a state restoration game tree okay so this tree is going to U be defined as walls so what we are going to have is that at

every um node of this um of this tree we're going to have a partial transcript and how do partial transcript look like um they contain um the instance this is X they contain the Prov messages at some point right we have we have the the number of uh um levels in this tree are going to be uh corated with the number of rounds and we're going to have some solt parameters um we're going to to add this Sol parameters because when we query a random function we maybe want it to be uh uh to to be unpredictable so we are adding this sols for for good measure and it's going to be uh useful when when

we want to um when we want some more security properties from our uh constructions so what the verif the approver is going to be um be doing is that the prover is going to try and Traverse this tree and eventually it gets to the leaf and what what is in the leaf the leaf contains a complete transcript so it contains X which is the the input and all of the prover messages along K RS of intruction as well as the salts for KRS of interaction okay um and the goal of the the prover would be to Output a

complete transcript much like we see here such that the verifier would accept on this complete transcript okay so uh let's look at the definition of uh so did did you say something okay um so let's look at um the the formal definition of State restoration soundness so State restoration game for interactive proof with salt size s and random functions remember this notation means that we sample a random function for every round uh we have K rounds and the length of the input is going to be

uh R um the stage restoration proof is is going to be um going to be doing the following so State restoration basically um runs a state restoration Pro which is an object that we don't really care how to it how it behaves but what we care about is what's the input and output inter interface of this uh uh prover and moreover how how much is it able to uh to fool the verifier so we're going to repeat um the following until this object decides to exit the loop and what are we going to do um the prover is going to Output some partial

transcript right so it has X it has Alphas which are the proval messages According to some until some round and sigmas which are Sal then we go we are as the game are going to um return um a random the random function value on X the input and um the pro messages and the salts we're going to send it to the to that box of State restoration prover and the prover is just going to continue so basically what is happening here the prover is trying to learn something about um the random function so you can think of it like at

every Edge the prover gets the value of the random function on that input right so like let's say the prover um wants to know what is just the random function applied to that F to that input it it queries that right in this definition um the the prover outputs uh this query and it receives back a Randomness so like you can imagine that here um there is actually some row which is the random function applied to uh to that okay so um the approver is is basically going to try to learn something about

the the random function and we can assume that the prover is kind of powerful right because it doesn't just guess as the entire transcript or whatever can Traverse the some interaction tree and um and try even to learn like let's say that the prover queried that and and that so maybe the prover learned um some something about correlated um statements or like correlated the transcript right um and eventually the prover outputs a complete transcript okay as like the the approver outputs uh that but eventually the game is going to Output the the randomness of

the verifier which is just applying um the the random function to every intermediate step of that computation okay we moreover say that this prover uh is a t- move prover if it can just query uh T edges along this uh tree right so if the prover is all powerful right you can discover the entire uh the entire state state restoration tree and by that gain information about The Run full information about the random function right and we we don't want that to happen because well if the prover can can break the random function and learn

it uh of course it can uh it can fool the the verifier because the verifier is no longer um randomized in a sense so what we want to say is that we want to say that uh this this uh thing is U restricted by by doing just t- moves along this uh this uh game tree we saw before and we are going to say that um an IP has State restoration soundness if for every salt for every salt site and for every uh move budget T um t- move malicious IP State restoration Prov

um and the and some bound right like we have some bound on the instant Sid that doesn't really matter what we want to say is this let's say that we start by picking out random functions uh for every R of interaction then we want to say that this game that uses uh this that receives the salt the random functions and the prover whatever uh it may be um we want to say that this game outputs um this tle here which we have the instance the the Prov messages the Sals and the randomness like I said before um we want to say that the probability that

the verifier accepts this thing so like it is indeed a correct execution a valid execution of the interactive Pro between the pro and the verifier on instance X notice also that X is not fixed here so like the game is free to choose X adaptively um the probability that this happens it's bounded by some by some parameter which is going to be the state restoration soundness so in a sense um this uh definition this complicated definition actually says something very simple the prover has t- moves to try to learn something about um the the the

random random functions right after these T rounds the prover should uh T moves prover should output something about what he learned he should he should output an entire transcript and we want to quantify how much did the prover learn and we want to say that it's not much so this is going to be bounded upper bounded by this uh State restoration sness um in some sense this definition um perfectly models what we expect when we uh talk about pH transformation right we're going to to see it uh um in a couple of minutes but it it should be very it should feel um

very natural because this is exactly what happens in the fature me transformation right the prover can query random Oracle several times on maybe interacted uh um sorry uh connected instan say um when I mean connected instances I mean I mean for example you are asking this as this Edge and this Edge right and because you as you have the value of the edges so far like you get maybe you get something by by asking this path and that path like I don't know maybe that's that's a good um strategy to learn anything about the function so basically it should it should feel

very similar to what uh to what security guarantee uh we actually hope to achieve for the future M transformation um so it would be good to uh stop here and ask if you have many question any question I'm ass you have many but um yeah let let me know um if you have any questions um okay um so I'm going to uh continue um I encourage you to read this definition um uh again and also uh that definition

here I wanted to think about um the syntax of what is actually going on here so at every round of this game the approver is going to output something that looks like this and it going to it's going to receive something that looks like the random function applied to whatever the prover um outputs and eventually we are going to uh output an entire a full transcript okay um this thing is uh is good to keep in mind because um eventually you're going to be we are going to be uh able to um use this

um um use this input and output to argue about uh what what what happens when we actually convert uh something to the F by using the fure miror uh transformation um okay so maybe let's uh I'll just skip about the notion of State restation sound as eror um but it actually um means something very similar to what we've seen before uh but let me just uh skip it uh for now I want to say something I I want to emphasize the differences between that notion of soundness of State restoration soundness and the usual definition of um soundness and uh for that we're going to

actually um see that um the state restoration function is not really tightly related to the to the definition of uh usual soundness okay so we're going to see that the State restation function is on the one hand an upper bound um for so it it's it's lower bounded Sorry by T * K T divided by K times the the original soundness error of the interactive proof so like remember T is the number of steps the prover can do in the state restoration game uh K is the number of rounds and we want to say that uh it's roughly bounded by that lower bounded which is yeah

maybe expected like it's not it's not too bad what is bad is um this thing here right so the state restoration soundness is bounded uh by T plus K CH k um the usual soundness right so if your your interactive proof had amazing soundness but it was constant it might not be uh so good or terms of State restoration function uh soundness sorry um because we have this exponential this huge exponential term here right so this is roughly t to the K so it kind of say says that if you want

some meaningful uh State restoration soundness for for your construction um your IP um better have like super super small um uh soundness or alternatively you can actually just go uh go about proving um the state restoration of your construction instead of like going through this uh um IP um because the what we basically saying here is that the transformation from State resoration function and the soundness um the soundness of the IP are actually not super correlated so um we usually don't go about proving um State

restoration uh State restoration by this uh kind of Black Box uh upper bound because it's just quite bad um and for that I want to emphasize this um this proof technique that we won't be able to go through all of the proofs in this um this chapter but um mostly when you want to when you want to do this kind of proof you're going to try to construct one prover using the other prover okay so um for the lower bound so now we want to say that the soundness error the state restation soundness error is lower

bounded by something that is roughly T over K times the original um IP soundness um what we are going to say is basically that's we have a budget of t- moves right um because we are saying that our um um State restoration approver has is is a t- move um appr so let's just run a t over k um full instances of the IP right each instance of the IP contains K rounds so let's just do uh complete executions of these and for each of them we get the error of um Epsilon I P right so we kind of we

can kind of say that the soundness error is at least that um that that should intuitively make sense right and the reason it makes sense is that um the soundness error should tell you uh how much you're going to be convinced even though you're not supposed to be convinced right and if your T here is so large that you can basically discover so much of the execution tree um it makes sense that the lower bound on the state restoration soundness is going to be very big so that your cannot be super small if you can read um read a lot from from the random

function um does it make sense do um do you have any questions about this argument here okay so let me just um repeat the idea the the idea is is um that we are using the state restoration function uh sorry State restoration prover um in order to prove something um sorry we are going to use um the IP prover um to construct a state restoration Pro so we are going to use the IP prover to construct a strategy the state restoration prover um and the upper bound which shows that the

state ration soundness is um upper bounded by T to the K uh times the original soundness is doing something very similar right so we are going to um construct aover uh an IP prover that uses the state restoration uh prover and the way we are going to do it is I don't I don't want to get too much into the detail because it's a um it's a bit of a tricky um idea that one has to uh think about here but eventually the prover makes the State Reservation prover makes a lot of queries right and the what the prover the IP prover can do is it can guess

which queries are going to be the U are going to be the one that theover the state res approver finally decides to Output right we can assume without loss of generality that we can increase the budget of queries so that there there is actually such path so like there is actually such path meaning that um we we maybe need to have like more K quer doesn't really um matter um so the probability that the the that the IP prover actually um chooses correctly the path that is going to be a uh output of the sequestration game

is going to be uh this one and the proba that the state restoration uh game um wins is uh this so like we kind of get um kind of get that the state restoration um times one over um t plus K which is K minus one is the soundness of the IP um and then we just uh this immediately implies um that bound um so I didn't I didn't uh go through that but I just want to mention that um those two

um bounds are actually tight okay um any questions about uh this the the the two bounds that I just uh um discussed okay so the most important thing to remember is that state restoration soundness is not equal to the IP soundness and moreover there is quite a big gap between the state restoration soundness and the IP soundness so when we think about um restoration soundness it's it's better to prove that our construction is just uh has this St restruction function

uh soundness as is not go go through this um um transformation okay so I see that we don't have um a lot of times uh but but just let me uh show you uh the construction of transforming uh interactive proofs into um into an an argument okay um this uses the F chir transformation and also you might um you might see why we did all the hard work of defining State restoration sence the way we did um because this Con construction actually

perfectly models um the state restoration soundness so we're not going to go to go through these proofs but actually the soundness of uh this construction is exactly the soundness of um the state restoration function of the underlying I State restoration standard of the underlying IP so how would you go about um applying the F miror transformation on on the IP so the the prover IP is going to um to be used by this argument IP so like when you have this uh fancy and uh um p and v those denote the the argument Rover and verifier

um and the the fancy Pro and the feny verifier are going to use as routines sub routines um the I prover and the IP verifier um okay so what is the IP prover going to do the IP prover is going to uh send its first message then it's going to uh look at the first random function right um if you remember in the state restoration game uh every round has its um random function it's and now we Den knowe this function by F so we're going to uh feed this function with X um the the Prov message and uh some

salt afterwards we're going to Output um that as the response from uh the verifier and we're going to continue basically so now the for the next uh um um Pro message we're going to fed the next random uh function with x the messages of the approver so bar so that the approver kind of commits to the to all of the all of the previous messages and can and cannot just uh start from like middle message for example um and of course uh the sold so far um and eventually uh we're just going to continue and we are going to Output approve which is going to be um

the approver uh Messages Plus the Sol so far and we're going to send that to the uh verifier and the verifier can um because the verifier of course has access to the function the verifier can uh recreate uh the rows because it's a public coin uh interactive proof decision bit of this um this verifier is fully determined by the instance the pro messages and the random uh randomness of the verifier which now is going to be the randomness um that was uh constructed using this random functions so this should look very uh similar to

the definition of State Restoration soundness in which basically the prover if you look at this prover right like uh this amazing prover that we have here uh this prover what what what should we expect from it right um this Prov should learn something about um um about the random function and the way it's going to learn something about random function is by uh querying quering it a bunch on what it's going to query the random function on queries that look exactly like that right that have the prover messages so far and drinking in my favorite C and eventually the the prover wants to win so it outputs some complete transcript if we

go back to the definition of state reading some articles on Z is very interesting we can actually see that since you guys are here this is perfectly modeled by by this game so like this game captures exactly what it means to for aover to cheat um in the fat uh transformed IP uh so like in the in the non-interactive argument um that is generated by this IP um any questions about that okay so uh how much time do we have you guys uh I think none because we're at the hour and I think it the DK

hack event is starting now so I think the answer is none oh okay so um I'll just say that uh this construction could be made more efficient um this is the topic of chapter uh 15 this construction has um some very desirable properties in terms of the knowledge soundness and the knowledge of it and um in general the most important thing that you should we should take from this session is that um State restoration Is the Gen is the natural thing to think about when when you want to uh transform interactive arguments interactive proofs sorry to a non-interactive argument and um and I encourage you to reflect a bit about uh

about that definition of the restoration and appreciate how related this definition is uh to this construction uh 14.1 and uh of course if you have any questions feel free to write them in uh in the on the channel I'll I'll try to answer um uh those and feel free to also email me or email us like uh about any questions and um yeah that's it I think um