SNARGs Book Study Group - Week #2 with Christian Knabenhans

Transcript

the probability that the verifier is convinced is bounded by some small error Epson SP again we'll cover knowledge soundness um informly knowledge soundness says that the malicious Pro that is able to convince a verifier somehow new corresponding witness for the instance formerly we Define is using extractor so what we'll do is um we look at a specific instance X um we look at a specific malicious Pro P tilder that is going to run the interaction we collect this interaction in a transcript alpha 1 row Alpha 2 and then we say there exists an efficient extractor uh here specifically we look

at rewinding extractors that takes the instance a transcript and has a blackbox access to the approver and is able to Output a witness and we we say that the probability that the verifier accepts but that the witness that is outputed by the extractor uh is not in the relation so it's not a valid Witness is also upper bounded by some error cap just for some some details it's not super relevant in the section but you you might want to know this in general um before the sound this only depends really on the specific instance we look at or even in general you can Define it to just depend on the size of the instance um here the knowledge error depends on the instance uh but also on

this Delta quantity here um and this is a failure probability this is just kind of quantifying how convincing aover is so for any instance that might be you know in the language or not in the language this is uh the probability that the verifier is not convinced is going to be uper bounded by um Delta so if you look at an instance that is in the language you know the verifier will always be convinced so Delta is going to be zero if you're considering specifically the the good Pro the honest prover um that is defined by the sigma protocol and you look at the relation uh instance that is not in the language then this is going to be at least one minus the soundless error and otherwise it might

be something else uh again this is not going to be super relevant for today uh it's just kind of a question of definition and it's good to know that these um this will also kind of influence the the knowledge sound specifically and then the third definition that we look at for today is uh zero knowledge um so zero knowledge is kind of defined formally slightly differently than the soundness and knowledge soundness because we talk about uh kind of zero knowledge we we talk about simulators that's the best way to formalize those so specifically um we Define a view so we take aover we take a verifier we take an instance witness and we Define the view to basically be the transcript um

so what the kind of the verifier is able to learn from the interaction everything it has access to and then we require the existence of a simulator that only takes the instance so in particular the simulator does not know anything about the wetness and we say that these two distributions so these are going to be distributions over you know um some some potential messages and potential challenges these two should be um very close in statistical distance specifically you know we quantify how close they are by this um this value zsp X and this is going to be the zero knowledge error uh but this is how we we Define Zer

knowledge so those are the definitions that we'll look at um are there any questions about the definitions or about Sigma protocols before we we dive into the the actual technical content no okay so the road map um for today so we've seen um we've seen what a sigma protocol is we're not going to give specific examples uh but these are very useful in general for example for uh proving you know knowledge of a of a pre-image of commitments or you know the things that invol signatures and we're

going to transform those into non-interactive arguments uh in the ROM and we look at you know soundless know soundless zero knowledge and see how they transform when you apply the transformation and then we'll wrap up with looking at the state restoration uh property which is kind of a a very nice theoretical tool um that will help us in doing this this translation from interactivity to non- interactivity you know we we're only going to cover uh this part until the random Oracle model um typically the way you would apply this in practice is by theistically instantiating the random Oracle with a specific hash function and so what this allows you to do is to go

from an Interactive argument to noninteractive argument in the ROM to a nonactive argument in the standard model that is juristically secure and that you can actually run in practice um and the heuristics don't really kind of change the parameters so the parameters you'll get here in the stand model are going to be essentially those that you get from the theoretical that's why we kind of focus on the theory without kind of going further on the the Practical side but I'll give some uh some tips on on uh parameters and kind of concrete um yeah things you have to keep in mind when you do practical applications uh can I ask about the definition part sure uh I just wondering if uh uh if

those uh applies to interactive and non interactive in the same way um that's a good question um mostly yes um so there are some syntactic changes of course um so what what changes specifically for example if we look at at soundness here um row here wouldn't be sampled at random right because uh and particular the prover is not able to be you know we don't have interaction so the prover will out put a single proof uh but you can replace uh for the nonactive case this entire thing by U aover being

output by sorry proof being outut by the prover that is run on the instance and then you replace the transcript by an actual proof so this is how things would change and similarly for completeness and um you would have the exact same things uh for knowledge soundness and um for Z knowledge yes thank you any other questions all right so we'll focus first as a warmup on the case of non-adaptive security so in cryptography there's um kind of always this notion of adaptivity

that you can consider um what nonod activity means is you fix a specific instance and the adversary is not able to kind of tamper with that instance this is kind of set before um the true the prw and the verify interact and then at the end you kind of are able to say something about soundness or not soundness what we consider after is adaptive security where the pro and the fa interact but maybe the prover is able to influence the instance for example it only sends the instance at the end of the interaction or you know maybe if you have public parameters it's able to first see the public parameters and then is able to choose an instance that's he want that it wants to um do an attack on non adaptivity is always um easier than

adaptivity so we'll we'll start with that then we'll see how we can uh strengthen the protocols that we have um to achieve adaptivity so we'll start with a construction right um kind of a compiler that takes a sigma protocol and outputs a non-interactive argument and a very natural protocol is the one in figure 9.1 so uh as before we had these red things right so before the prover um would send the first message and then the sigma verifier would sample a uniformly random row and send us to the SP prover what we're doing now is we're simply replacing this um we're replacing the choice of you know randomly sampling

from the verifier by the random Oracle that we assume here so instead we feed this alpha 1 message into the random Oracle F that was kind of sampled uniform at random earlier at setup kind of just lives in the sky and are able to query it that allows theover to non-interactively get a challenge that is going to be randomly distributed and then we can the argument prover here is able to you know just run the the SP prover as a blackbox and get two pro messages alpha 1 Alpha 2 and that's going to be the proof and then on the other hand on the argument verifier we'll we'll do basically all of that uh and unpack it for the SP verifier so we'll pass the proof as two

messages we'll derive the same SP Randomness by acquiring the random Oracle again and then we'll just run the SP verifier um with the instance and the the transcript so this is going to be exactly the same as before we just kind of replace random sing by the Randle it's a very natural thing to do are there any questions about the the constructions themselves [Music] all right so the first kind of um sanity check that we that we want to do against disc construction is if it's well behaved in in the sense that um if you give me a sigma protocol

that has some soundless error can I see anything about a sound ER of the non-interactive version that I just constructed and we'll start with a lower bound and this is LMA 9.2.1 the slma says that if you give me a sigma protocol for some relation um that satisfies this mild condition to which we'll come back later um there some some mild condition that you can assume the S prol satisfies then if I construct the argument as defined here above I can say that the soundness error nonadaptive soundness error of the argument is going to be at least T * the sound of the sigma protocol minus you

know T chose 2 * the square of the s t here is a specific parameter that we'll use for the adversary and this is a query bound so in the sigma protocol world the adversary is not restricted aders is all powerful it's able to you know compute as long as it wants uh it just has to interact with the verifier when we go to the nonactive setting we have to restrict the argument adversary somehow so we don't restrict the adversary on r L time or resources or space instead we just say it has a maximum amount of query it can make to the random orle and this is going to be fixed it's going to

T so what this is saying here is that you know if you give me um maybe this easier to to see um it here you know if you set T and EPS P to be such that t * p is is smaller than one right so you can think of T being you know somewhat large maybe 2 to the 80 Epsilon SP being very small maybe 2 to the minus 128 this equation above you know says that the the sness uh of the argument is going to be at least T2 times the soundness of the the sigma protocol so in some sense you know you're not kind of um gaining any soundness in fact you're you're losing soundless um and

you're losing soundless kind of linearly in the query bound of the this is just what this LMA says now this LMA hinges on the small condition that we imposed on the sigma protocol um and this this requirement says you know there exists at least one instance that is not in the language and for this kind of specific instance is very convenient for proofs for every possible first pro message so every Alpha One in the set of bits the probability over just sampling some some random challenges by the verifier the probability that there exists a second Pro message that makes the verifier accept is

exactly the soundless error so this is kind of a a simplifying assumption that we make um it's the reason why it's there is not too important um it's just kind of very commen for the proof to assume that there exists such an instance and in practice this is a condition that is Satisfied by very very ual um Sigma protocols that you might come up with in practice and I'll show you immediately how to use this so if we if we want to look at this proof um what we want to to talk about is um this probability so this is going to be um upper bounded by Epsilon Epson log of x so this is the

probability that the argument verifier accepts given that we You Know sample a random Oracle at setup and then we ask the a malicious Pro plda that has access to this um Oracle access to this random Oracle to unput us approve Excuse me yes two two questions I hope they are really small yeah go ahead about the qu about uh when we when we uh see it from a practical standpoint uh is it basically a hash

rate a number uh kind of velocity with which uh trer can Brute Force the hashes um so it's it's related to the hash it's not exactly the hash rate um so the way we typically set T in practice is if you you know this limits the amount of of queries that the adversary is able to make to the random Oracle when we instantiate the random Oracle with a specific hash function a reasonable way to set this in practice to say okay what is a reasonable bound on the number of hash function evaluation that my adversary is allowed to make um and so you can look at for example okay what is the you know the

combined power of the the Bitcoin network over the last 10 years or 20 years you know that that's kind of a reasonable estimate or you look at some specific hardware and you say okay how many hashes can you do per seconds and how many seconds um have it lapsed since this Hardware exists and how many more seconds am I expecting the the protocol to go on and that's kind of a good upper Bound for how much hashing power the adversary has and how much kind of uh random Oracle access the adversary has um typically people said this to be uh you know 2 to the 64 if you're not too conservative to two to the uh 80 to2 to the 100 um in practice so you can think

of this as being you know like roughly 100 bets large um if you're very conservative yeah thank you that's a great context and uh another one uh if it's uh easy enough could you could you give an example of uh that uh of that element uh that you were talking about uh just recently when uh presenting this uh proposition presupposition uh which we take um sorry I don't think I I got the

91 uh I mean uh either there an easy example that you could give for 91 um I don't think I can give an easy example without specifying a sigma protocols uh and that would require pulling in a whole bunch of crypto um so I don't think I can give you a very quick example on the spot without bringing in a whole lot of additional um background okay the intuition is you know there's kind of um you the the soundness error says okay the probability of convincing a a

verifier is going of always Bel loose some threshold and what this is saying is that well you know there's kind of one instance that is exactly at the threshold you know for this instance um for the specific instance you know for all possible Pro strategies for the first message you know you you cannot hope to convince a verifier with probability more than epon SP kind of exactly you know so there's one instance that kind of matches this bound maybe the in will become more clear when we do the the actual proof right this kind of feline proof here um so what we want to bound is the the soundance error of the noninteractive argument which is exactly this thing here um that's what we defined earlier so what you can do is you can you know

substitute the definition of v that we have from the the transformation that we introduced um so this is just saying okay well I know the proof is actually um a tupal of messages and I'm just going to run the SP verifier on those messages and the challenge is going to be the the random Oracle output on Alpha One and you can Define you know this event here um let's see this event here um to be uh a concatenation of some some random variables so you can define those random variables uh XI that say okay I know the prover is going

to make T at most T queries to the random orle you know call those alpha 1 I and for each of those you know you say there's a random variable x i that corresponds to the verifier you know on this specific try that the adversary is doing being convinced right so inance as the adversary the argument adversary has kind of T queries it makes to try and and figure out something out about the random morle um or about the the verifier strategy you know declare a random variable for each of those tries and then you can do a simple

inclusion Exclusion Principle by saying okay so the probability that the um the argument is convinced is the probability that at least one of those T tries convinces the SP verifier and what does this going to be so it's going to be at least um the probability that um any one of those convinces this minus the intersection so this is the the intersection to make sure that we're kind of um covering everything and so this part is just going to be T times the soundness right because it get T Tri and if we want to tighten the bound somewhat we can say okay well there's you know uh T choose to VAR um indices IJ and T that are distinct uh and for those you know

probably there's no overlap is going to be Epsilon squ so this is just to have a tight result you can also kind of just ignore the second term if you want to be a bit sloppy and just say well the lower bound is T times the the soundness of the the signal protocol so this is just kind of a um a first um sanity check to try and understand what this transformation does and how it behaves in particular it doesn't boost soundness you know but there's a lower bound that says well you know there's somehow the the argument in the sigma protocol sound as errors are closely related by a factor of T the kind of dual is I think maybe more

interesting um the Dual LMA sets an upper bound on the argument so this is kind of more interesting in practice because what you're seeing here is that the argument uh soundness is going to be at most t + 1 * the sigma protocol sound this so in particular you know if you set um this to be 2 to the 80 bits you know for example and you know that this is your Sigma protocol is going to give you I don't know minus 200 U like 200 bits of security then what you can say is you have you know 120 bits of security for the argument

itself so this is saying okay the the maximum amount of of um of security that you're going to lose concretely is going to be just a factor of T um it's going to be exactly the quy bound and if you combine this with the lower bound that we have from before you know you kind of sandwich this um argument sound as error between this upper term and between this lower term that also depends on the sigma protocol so in some sense you know the kind of attack that the pro that we constructed above is kind of optimal in some sense and there's a really tight um security relation between those two terms um I don't think I I'll go through the proof of this inefficient reduction

because it's I think slightly artificial from the tools they use um I think I want to focus bit more just on the general technique of the efficient security reduction um which is kind of something that you'll see more more more in the I think in the following sections of the the book and it's also kind of a standard tool in in cryptography um the first other any questions about the the state of the LMA okay so as a reminder we're just trying to say um you know we know that this um the probability of this um argument verifier accepting for a proof

given by Mal approver is going to be at most t+1 times the probability of the sigma protocol verifier accepting given a sigma protocol Pro uh and in particular it's not any Sigma protocol Pro it's one that we construct so if you give me an argument adversary that you know kind of breaks um soundness of the argument I'm able to return a sigma protocol adversary that is able to break um the sigma protocol sound this this is kind of a standard reduction in cryptography the way this works is you basically just run the argument prover so there's some subtleties uh for example for the random Oracle you might remember from the the the lecture last last uh last week that you know if you

want to store a random Oracle it's very big because it needs to take potentially unbounded inputs so instead of restoring this Oracle because we want to be efficient we will lazily sample an Oracle and the way this works is you here you just sample an empty table and for every um query to the Oracle you sample the random value and you keep track of it in the table so you're really kind of just building up the random orle as you go and so you don't need to store all possible entries you just need to store you know at most t plus one of them in this case and so the way this SP Pro works it just runs the the argument prover simulates a random Oracle to it until this adversary outputs a first query alpha 1 roughly

there's going to be some more details but until it that puts a first pro message then you know the sover um expects a first pro message us just output this that you send to the verifier that leaves here over the edge of the screen and the verifier is going to answer with a a challenge and then you feed this challenge into the random Oracle so instead of you know um doing the interaction with the proofer you program the random Oracle to be this challenge at the value alpha one and then you create the argument a approver again on this value and at some point the pro is going to give you another value Alpha 2 that's the high level strategy there's

you know some small details um in particular you know P here might not be well behaved so it might for example refuse to give you a first message um or it might you know do queries that you can't really pass as a message um in this case you need to be more careful so this is why we kind of sample this index um as part of all the queries and then we'll simulate it up to one query and then we'll take that message to be correct that's kind of a more technical detail on the proof that I don't think we have time to go into um you know the core um technique is that you know you have this kind of equation here that you can basically say that this is fine you know this is kind of the probability of

the approver not behaving nicely um for the reduction is going to be you know 1/ t + 1 um and then if you do the complete reduction you just kind of follow up these these arguments and you can conclude that the argument soundless is at most uh t+1 times the um Sigma protocol soundless so I know I went over the proof rather quickly I think I just wanted to give you more of the high level you know idea of how reduction Works um because we're going to be using this again um in the following section I think the the exact details of the proof um are a bit slightly too

involved for um this kind of format uh but I think with this intuition in mind you should be able to go back over the the actual proof and just follow along and see okay how do they you know specifically break down the adversary and relate these two things but the core idea is that you can build a sigma protocol prover that behaves you know very closely to um a good Sigma protocol Pro that is able to convince the verifier even for an instance on the language given that you have this argument Pro that is also good at convincing an argument verifier about instance another language so that was soundness um we can

do the similar things for knowledge soundness um so not you also pick up the factor of t+1 again very briefly um here you also have the similar kind of construction so here you know we kind of do the opposite right you we're saying okay assume that the sigma protocol is extractable assume there's an efficient extractor ESP that takes an instance a transcript and has blackbox access to approver and is able to Output a valid buness well you can simply wrap this around you know and um construct a an argument extractor that takes an instance a proof this time and the transcripts that correspond to the the argument kind of interface and here you only get an argument

Pro so in order to feed an SP P prover to the SP extractor we're just going to construct um this malicious SP prover and this is going to be exactly the construction that we've seen above so we'll just reuse um the reduction from above and we'll say well you know if I'm given a good enough um argument prover I'm able to build a good enough Sigma protocol prover and I can just feed this to extractor theor is going to give me a witness and I can just output this witness and the loss that I incur is very similar to above I also incur a loss of of T +1 now additionally there's some other losses um that are kind of hidden in this um running time so this is the expecting running time of the sigma

uh yes of the of the extractor of the argument extractor and now this is going to be the extractor of the sigma protocol but in addition we will pick up an additional Factor if you remember the extractor kind of took this failure term so now we put this additional failure term that is also dependent on and then because we need to do some random Oracle um programming uh and queries we'll also pick up this Factor R * T So R here is the output of your random Oracle um and T is the number of queries so this is just to saying well you know the run time slightly increases but still these two things are you know closely related by a fractor of T and then you know for Z knowledge

things get even easier um so Zer knowledge kind of a direct reduction so if you have a good simulator for um a sigma protocol you have a good simulator for the argument um you know so you can see this here right um the way we build the simulator is you well you first run the SP simulator to get a simulated view an instance and a simulated transcript you set the proof to just be the the corresponding values of the of the interaction and then me here is kind of this interface to program the random orle and what you're going to do in the simulator is you will plant the random morle to say that well actually F of alpha 1

should return row just so that the verification passes at the verifier and so you know you just say well you know if I I have a simulator for the sigma protocol that does all the heavy lifting you know somebody has proven that a specific Sigma protocol has a good simulator all you need to do really when you go to the random Oracle with this construction is to program the random Oracle to match the interface to make the verifier accent that's it again for the proof there kind of slightly more detail um but you know the those two those two things are very closely related so that was about um non-adaptive security which kind of a warmup next I'm going to look at

adaptive security and see how you know in turn adaptive sound list and adaptive Z knowledge uh do Break um for the the simple construction that we've looked at where you just kind of hash or you know feed the first message to the random Oracle is the broad intuition of how you know kind of going from an interactive argument to non interactive argument you know preserves soundness up to a multiplicative factor of of t okay I think those was the the the

heaviest proofs uh for today the rest is kind of just variation on the same idea so I won't go into technical details just give you the the high level intuition um but first we want to see okay what happens when we now have adaptivity um so if you remember you know if you look at a sigma protocol you know this is it um you have three messages let's look at a specific Sigma protocol that's going to completely Break um under an Adaptive adversary this particular Sigma protocol doesn't really look at the first message um it samples a random Challenge and it only accepts if the instance matches this challenge so for a given instance you will only accept if the randomness that you know randomly generated matches the

instance this not a very good s protocol are very useful it still has you know decent soundness error right so the soundness error is no whoops is 2 to the minus r um because you're sampling um row at random the probability of the instance matching this is going to be 1/ 2 to the R so what happens when we do the construction that we had above so if remember we built a argument Pro and argument verifier and instead of doing this interaction we feed this into the random Oracle and the random Oracle is going to give us the

row so what what happens now well there is a very simple attack um so here what the adversary does it just you know samples an ala one runs it through the the random orle here to get a row and then after that says you know what actually the instance I was thinking about is exactly the road that I sampled you know because I'm constrained to set the instance at the beginning I can just set the instance to be whatever out here and then the proof is going to be alpha 1 and Alpha 2 and now the argument verifier is going to take alpha 1 runn it through the random orle again get row andow and behold row matches the instance that the

you know the prover has announced and so here you know the sound Cent is one the meas Pro is always able to find an an instance X X that convinces the verifier with this proof and in particular you notice that this doesn't match the bound that we had before right so in particular what we show before is that in the in the nonactive case this should be you know t + 1 * epsp you know and here uh the prover only makes one query to the the random Oracle so you know we can even restrict the the prover to to only have you know one uh one query you would expect this to be you know something like two times um the the sound from before 2 * 2us R you know obviously this is not bigger

than one so you know what what allowed the adversary to to break uh adaptive soundness is that it has the ability to to decide on X after the interaction has run or after it's kind of computed appr proof so kind of looking ahead the way to fix this is to artificially Force the adversary to in some sense commit to the instance before it does any of the the the interaction or any of the random Oracle querying for the actual proof so particular what we'll do uh we'll see this later on is that we also require the instance to go into the random Oracle And if you've read any of the you

know there's there's roughly one or two papers a years on you know how people um mess up the aaman practice and they kind of Miss uh some parts of the transcript of the instense or the publics into the the transcript this is exactly such an attack if you don't include the instance in what goes into the random Oracle you you allow yourself to an attack an Adaptive attack so that's for the soundless part right you need to make sure that everything goes into the transcript there's also an issue with um zero knowledge um so again we'll look at a specific Sigma protocol uh that is kind of degenerate but but you know illustrates why this this breaks in practice so so in this Sigma protocol um

we again we have two messages we completely ignore these messages so you can assume that those are are zero for example the verifier will sample a row we send us over and here you know if you assume for example that the relation is easily decidable you know it's something in P the verifier will just um exhaustively check whether there is an A Witness for X you know so for you know assume we have a relation that is Trivial and the verifier you know interacts with the prover but that's kind of completely useless it will just decide um based on instance and you know this this will have some uh zero knowledge error zsp so again uh the way we build these

provs right uh we'll build an argument Pro and the um an argument verifier and we'll feed we'll feed uh A1 into the function and we'll get a challenge so what is an Adaptive attack here so what you can do as an adversary is in the first stage um so here the adversary U is the verifier right so in zero knowledge we assume improver is honest and the verifier is malicious and it it's trying to um distinguish between kind of a simulated and a uh real world so it's trying to to verify whether it's interacting with a prover that knows

something about the witness or with a simulator that doesn't know anything about the witness and just kind of has zero knowledge of the witness so in the first kind of stage of the adversary it's going to um choose you know kind of adaptively an instance and a witness um so that the instance is actually in the relation you know just so that the verifier will accept they draw and it will just store for later um the random oral eval at zero um and zero here being kind of a place fold for the Alpha One value that the the honest Pro will send and then this is kind the the setup right and then during the the distinguishing phase the adversary will

just check whether quering the random Oracle again is going to be the same value as it store before if yes then this is going to be real this is going to be the real B because the random Oracle doesn't change right when you qu a rle twice on the same on the same value it's going to give you the same answer however if the random Oracle you know now suddenly says something different for zero then the now knows that it's in a simulation because the simulator doesn't do anything about the Randle it it samples those values at random um it doesn't have any information about what F of Z should be and so here there's a very easy way for the avory to distinguish whether it's actually running with aover or whether it's actually running in a

simulation right this doesn't mean that the adversary is kind of able to learn anything meaningful from the witness uh about the witness from the prover it's just saying that there's kind of a a break in distinguishing capabilities in particular you can say that the the zero knowledge error of the non-interactive argument is going to be at least uh 1 - 2us R so it's just the the the probability of um not hitting a collision with uh the random Oracle value here so again there's going to be a fix that we'll kind of look at later on that that fat implements the the capability here hinges the fact that the kind of the

value of the random orle is kind of easy to guess in some cases for the first pro message uh for this adversary so what we can do instead is we can make this value hard to guess so we'll add the random salt to here and we'll just say well okay actually the challenge should be the random oral crate on the first message and the this random salt and because this random salt is going to be sampled at random by the prover and is also going to be sampled at random uh from by the simulator it's going to be really hard um for the the um adversary to distinguish you know or to guess what it should kind of output here uh to check whether it's running in the in the real world or in the simulated world that's

the the high LEL ntion are there any any questions before we go into the the actual fat transformation so just to recap we we started with this kind of very simple construction that just considered the first message it gives you uh you know soundness knowledge soundness zero knowledge in the non-adaptive setting which is already pretty pretty good for the fact that you're just kind of replacing a random sampling with a random

Oracle however when you want strong guarantees in practice like you know non adaptive uh guarantees this uh it does fail so for this we need to be a bit more clever about the construction uh that we do about the compiler and this is the F transformation for Sigma protocols and this is exactly the two basically the concatenation of the two fixes that we decided that we discussed so given an SP prover the way to construct an argument prover is to let the sppr up with the first message you then build this thing so this thing in particular it has the instance in it to prevent um the

Adaptive attack on U on soundness and it also has the salt T that is a tow that assembled uniform at random and then you do what we did before you input this into the random Oracle you get a challenge you feed this challenge into the SP Pro you get a second message and the proof now is Alpha 1 Alpha 2 but also the randomly sampled salt uh because the verifier needs needs this to to do its own query and then you know we we par this as two messages and assault we feed this into the random Oracle we get the new challenge and we just feed this into the SP Pro so that's the F transformation for Sigma protocol

and you know this is kind of a very nice information because it also preserves um a whole bunch of efficiency metrics that we care about so for example the proof um is almost is almost the same size as the as the SP proof so in particular um you're only sending the two messages as before and you the only addition that you're sending is the message uh tow so that's the size of the proof that the ver the pro has to send then for the prover you just have to run the SP prover and in addition you make a single random Oracle query that has size you know size of the instance size of the first message size of the salt and same for the verifier the

verifier just does the SP verifier and does one random Oracle query of this size so if you think you know concretely you know this thing is going to be I don't know maybe 64 64 bits you know a few bites um compared to whatever the SP proof is going to be and if you think in concrete terms you know the the non intive argument Pro is going to be uh your SP prover and the only cost you're going to pay in addition is a bit of hashing so that's the the fat transformation and then what we can show uh is that the things that we've had before uh kind of

carry over nicely in the Adaptive setting so the proof looks very similar um what we have here is that the the argument the Adaptive soundless error of the argument is at most t plus one times the uh s error of the uh Sigma protocol and um so I don't want to go too much into the proof because again there's a bunch of details um that are kind of not super material to the day um but this is a very similar strategy you can kind of bound the probability that the um doesn't play nice with the reduction with a very similar limit as before and again you need to lazily sample a random Oracle um for this reduction to be

efficient you can also do the same for knowledge soundless so here is the say that the knowledge soundless error of the argument you know now we have a bunch more parameters because we want to be more more precise than before is also going to be at most t + 1 time the soundless error again we have this kind of um interesting you know shift of failure probabilities that are also kind of dependent on this value T in practice you know this is something that you take care of with concrete parameters and um the runtime of the extractor for the argument is also the is also going to be the uh runtime of the SP extractor with this kind of new parameters so again you pick up a small factor here which is just from doing

this additional romal queries um and you pick up this failure error here and the proof is very similar um you we use this this small L that relates the two um and then you build the extractor in a very similar way so you first um given an argument prover you build a malicious SP prover that is good and U security relates closely to the argument prover and then you just feed this to the SPX VOR and you're able to relate the to efficiently so again I'll skip the proof the proof is very thorough I encourage you to have a look at it you know kind of after uh between now and the next U the next meet

is going to be in two weeks just to give get a bit more kind of comfortable with the the intuition but if you only take away the the high level um high level takeway I think that that's going to be uh very useful for for example concretely setting parameters and finally your knowledge um here things get a bit more interesting so before we we didn't have this Factor t/ DS now we have the Z knowledge you know kind of the argument being um uper bounded by this Sigma protocol sound this Sigma protocol zero knowledge error plus a distinguishing Advantage which is going to be the number of queries times 2 the S which is the the the sold space

so if you think of it right now we're kind of sampling a random salt and we're fitting this into random Oracle and if you apply the attack from before which is going to somehow think as being optimal the only way to distinguish between those two is to just query T things in the random Oracle you know trying te out of these two the S possible salts and maybe you get lucky and you find the one that was used by the prover and in this case you're able to distinguish whether you're in the real or the simulated world or you don't with prob to dsus T DS and in that case you know that's you're not able to distinguish those formerly you know we do this using hybrids so we have a a real distribution

which is going to be the adversary running against um The Honest prover there's a hybrid where we have this kind of short you kind of simulator that still has access to the witness and still you know kind of runs the the SP prover but instead um it programs the random orle using the salt sample at random so it doesn't take the Sal the salt from the approver it kind of generates a new one and the distinguishing Advantage between these two is going to be exactly this T over 2 to the S term and then you can show that these two when you replace the actual prover by the simulator that doesn't know the witness anymore this is exactly the zero knowledge error of the sigma protocol there's nothing about the

argument here anymore and so you can nicely decompose these two terms so that's kind of the the high level uh ideas so maybe the the the you know one line takeaway um of this section is that at least for Sigma protocols um there's a very simple construction F construction that takes an interactive argument and gives you a non interactive argument that preserves soundness and knowledge soundness and zero knowledge nicely and the price you pay is directly related to number of queries to the random orle that the investory is able to make which is something that you can you know reasonably control uh and and cost in practice

however you might have noticed that I mean the proofs are kind of um they're very specific for Sigma protocols and the for example the this assumption that we had earlier um and they're in general not not the nicest to work with and if you you know kind of looking ahead for in two weeks from now you can imagine that this is going to be even more complicated when you look at multi-round protocols where you potentially have many many different rounds and you need to argue about what's happening in each round um and how these kind of um probability work with each other so this is why the book discusses this notion of um State restoration soundus which is kind of really Central in the book and is very good formal tool to analyze those kind of protocols and I

just want to show you the the state restoration game as a high level idea um the idea is that this is a notion that is kind of uh a direct translation of what you would expect security to look like when you look at a an interactive argument that you applied F chier to so what is is saying is you have a malicious Pro for a sigma protocol um and it's kind of against the state restoration game and this Prov is able to run against a Challenger um and you know for at most times it's able to send an instance a first message and a salt to this Challenger and the Challenger is going to initially sample a a random function right so kind of a random

Oracle of its own and it's just going to answer these random orles so this is just capturing the exact same um the exact same interface as the random Oracle just as a challenger and we have the same bound then at some point the state restoration prover is outputting an instance and a full transcript right so this is very similar to the proof that we had in the non interactive case you have put two pro messages and Assault The Challenger samples the corresponding uh Challenge and outputs this so this is just kind of really modeling the power that an Adaptive prover has when it knows that it's you know kind of running in something that is going to to

be compiled with a random Oracle type construction like the P transformation and um I'll skip those definitions you can uh generalize this to um State restoration knowledge soundness and to you know kind of with rewinding and straight line flavers the core Lema is that the soundless error of is directly related to the state resoration um sound as error of the sigma protocol because you know we kind of really targeted the the definition to be about something that is going that is a sigma protocol that is going to be apply like that is going to go through vamir and that is then going to be an argument and you have the same for for

knowledge as well and so before we kind of had a direct proof now we can of decomposing these two things uh and then what you can show kind of as a second step is say Okay so this um stion soundness things is actually related to The Standard soundness of the sigma protocol using this factor of T So before we had kind of um Epsilon AR small equal t + 1 * x p and now we kind of introduce this intermediate notion that is kind of really targeted towards the goal that we have um as a as a stepping stone um yeah so I I'm don't want to talk tooo much about stration I think we're also out of time but this is going to be a recurring theme in the rest of

the book it's going to be especially important in two weeks from now for um the the multi case are there any questions um kind of maybe on the on the high level things I'm also happy to dive into more uh technical definitions or proofs if you're interested uh but I think it's more important that you get the the high level the high level intuition for how F works and what the pitfalls are when you try to compile interactive arguments into non interactive one I see somebody's typing uh so I'll

wait until the the question comes otherwise yeah feel free to um to to leave the channel maybe go over to the the Z hack uh kickoff um I'll just stay around for a few minutes if you have any specific questions no question from me but let me thank you for the for the session you're welcome yeah I hope it wasn't too rush again you know this is 30 pages of technical content that we have to go through an hour so it's going to be a

bit compressed but hopefully you have the the high level intuition for the rest of the the book as well and the idea of a reduction uh and of kind of composing extractors together yeah thank you bye thank you much