SNARGs Book Study Group - Week #7 with Yuxi Zheng

Transcript

okay hello everyone so today is the last session of our snark study group and we'll be talking about again constructing arguments but from another objects called IOP interactive Oracle proofs the whole book this whole book you can think of it as constructing arguments from different types of objects and as you have seen pre in previous weeks from my labmates we have many of these transformation and in the beginning of the study group you probably seen how to start from an IP and interactive proofs

and the FIA Shamir transform from IP takes an IP and it converts it into a non-interactive argument and if we start from some other objects say the PCP and along with merco commitment we have the Kean transform which takes PCP a prob checkable proof and meral commitment and you get an interactive argument and building on top of K kilan we f o seen the mikali transformation

which takes PCP and Amer tree commitment and the mikali transform would turn that into a non-interactive argument so these are transformations that starts from pcps we didn't really talk about this because the soundness proof in the book of mikali is a direct proof but actually you could think of mikali as as being first as a modular version of mikali as first doing Kean and then perform fat Shamir on the interactive argument which takes interactive argument and make it into a non interactive one then this is

a bit subtle here because the FIA transform as I said just here is like taking an IP and turning it into a non- interactive argument but the result of qan is an interactive argument but it turns out that in this case f Shamir on IP uh when it's acting on an interactive argument the soundness can still be bounded so like it can it can also work when in this case taking an interactive argument and transform it into non-interactive argument uh we will see this later in the proof of today's talk and yeah it's a little bit of suby here so today we

will be looking at two new Transformations two new constructions known as the ibcs and BCS construction so instead of starting from pcps we'll be starting from interactive Oracle proofs this gener relizing pcps into multiple Realms we will have Randomness and interaction in the interactive Oracle proofs and from IOP along with the merco commitment you can use you can we can we will look at the interactive BCS so ibcs construction which will give you an interactive argument the ibcs

construction is an IOP analog of the Kean construction and then building on top of that we'll look at the BCS construction which takes IOP and M commitment and turn it into an argument so that is the IOP analog of the mallic construction and again you can think of BCS as first doing ibcs and then doing FIA Shamir on the interactive argument oh sorry this should be non interactive oh and also if you have any questions feel free to interrupt anytime

yeah so here's like basically an outline the way I'm going to approach this is I will first try to give some high level definitions and like definitions then for the proof part I'll just try to go through it like on a high level so you can maybe read it read the details on your own much easily much more easily so today we'll be focusing on these two constructions the so it'll we'll first start with some definition of IOP and

then we'll talk about as well as the state restoration soundness of IOP it's very similar to State restoration soundness of Ip and then we'll talk about ibcs construction and then the third section is on BCS construction I will mainly focus on the first three to start what is an interactive Oracle proof iops we've seen from IP it's very similar we also have aover and a verifier the prover takes as inputs the instance and a witness and the verifier

takes as input just the instance recall that in IP you would have the approver is sending message Alpha One the verifier is sending message Row one and then the approver send another message and then verifier send another Randomness Dot and then in the end you have K rounds and the verifier would read all of these messages Alpha 1 Alpha 2 Alpha K in its entirety and in the end it outputs uh decision bit B of whether accepting or rejecting quick question your last PK arrow is in a different direction than all the other P arrows oh and so sorry

yes you're right you're right it should is also sent by the verifier to the approver yeah so it's basically an IP of K rounds and now for active Oracle proof the only difference is that now instead of for the prover sending these messages we'll have the prover sending PCP proofs or the or proofs that the verifier can then query at certain locations this is in a sense very similar to PCP if you just look at one round of an IOP but here the approver is sends some proof Pi 1 and the the IOP verifier will

query the pi one at certain locations and send some Randomness Row one then the prover I prover sends another proof and the verifier query at some other location depending on its Randomness and sends another Randomness and you continue for K rounds and then in the end the verifier it outputs a decision bit its decision bit is dependent on the instance X on its Randomness role and also it has Oracle access to all of the proofs sent by the Prov so it's also dependent on the query bits so the query aners

that is saw from all of the IOP proof strings and it outputs either accept or reject based on these things um here is we also similar to the notion of public key IP we also have the definition of public key iops what public key means is that all of these row eyes they are uniform randomly chosen they are just random

streams that are drawn from that that are drawn of some predetermined length and other than these row eyes the verifiers do not have any additional Randomness itself so the randomness of the verifier so this row here is exactly the r eyes that are sent to the prover across the cave across the cave Realms then you can write the the verifier accepting the verified decision bit as a function of just X and the RO ice and is able to query all of the IOP

proof strings depending on uh the location is depending on its Randomness and uh without loss of generality when it is public key iops we can also think of the IOP model as having two phases an interaction phase and a query phase uh so instead of thinking the approver sends some proof the verifier query and then send Randomness and then it send the prover sends another proof the verifier query in it and then send Randomness you can just separate out the interaction and the quering part so say now uh the approvers just sent uh the

proves the verifier just sent Row one since and then the approver sent Pi 2 the verif sent row two Dot and theover sent Pi 3 and the verifier sent row K this is oh Pi K and this is the interaction phas and after this point the verifier have access to all of the IOP proof strings and its Randomness then it can just query all the pie that it already possess yes so that's a note on public Co IOP which is what all of the constructions that will not only work with publicy IOP iops so the ibcs and

BCS protocol are built using public key IOP very similar to all of the proof systems that you've seen before we still have we can still Define completeness and soundness in a similar way so then an IOP for relation R has perfect completeness if for every instance and witness pair in the relation and the interaction between the prover and verifier should always accept this bracket notation is basically an is a random variable that equals the output put of the verifier

after interacting with the approver the probability is taken over randomness of the approver is in the verifier yeah it's just an notation to denote interaction it's similar to it's basically the same as how we did it in the IP case and we say that the IOP has S as error Epsilon IOP if for every instance not in a language and malicious IOP prover the probability that this interaction and end up in accepting is less than equal to the this is less than equal to the soundness error so this is defined for every instance X you can additionally Define

this will be used in the non improving adaptive soundness so adaptive soundness bound is using this notion is Epsilon IOP n so it's saying the it's the maximum soundness error of any instance of size less than equal to n and not in the language the distinction there was like soundness over all instance strings versus over those of a certain length this one so this one is yeah so this one is the soundness that we will

use when we talk about non adaptive soundness because it's specific to an instance if you if we look at uh we'll see later and I'll also mention it when talking about the Adaptive and nonadaptive soundness but in the non-adaptive soundness since the prover is picking the instance then we need to say the prover can pick instance any in of length less than equal to n so you just bound the soundness by the one which is the maximum sness error for any instance less than quot to n that was a little okay so if if the bre is picking the instance

[Music] then yeah I I think I just got a little lost here that that's okay you can go on so the the sound is uh so it's the malicious Prov who would be picking the instance that's right confusion was like I thought adaptive soundness is when the malicious actor is allowed to make the choice or is it the other way around like I'm surprised you're calling this non-adaptive this seems to me like it would be adaptive because the malicious actor is adaptive yeah that's a great question I might have had a mouth slip I so yeah exactly as you said adaptive means is

the malicious Prov is able to choose the instance so it can choose any that's called adaptive soundness and non-adaptive soundness is proven for every instance X you can bounce the soundness of argument is less than equal to the soundness of maybe IOP plus merco tree extraction error so you you say that for any instance X not in the language are does that answer your question yeah and I just want to make sure that the conclusion was correct like this case is

adaptive right so this notion here that talks about the maximum over all instance of lens less than equal to n is for adaptive okay so another interesting thing to note here is that we can we think about IOP as a more generalized version of Ip and like more General notion than IP then instead of just having the approver sending proves Pi when pi eyes here we can also have

the Prov sent along with Pip some like non-oracle message which is Alpha 1 Alpha 2 and Alpha k then these alpha eyes are read in its entirety by the I IOP verifier whereas the pi eyes they are only read at the maybe constants many query locations um then in this model the it's more generalized General ver definition of IOP the

verifier it well the its decision bits becomes this so it'll be dependent on the instance and also all of the alpha eyes that are non-oracle messages and all of the query Randomness sorry all of the verifier Randomness and depending on its Randomness it'll query the pi eyes at certain locations and then based on this they output some decision bit so all of the construction that we'll see later today like ibcs and BCS they will also work for this type of

IOP you would need to modify the proof a little bit but if you do that there is there even overhead will be there will not even be overhead if we look at this more general definition yeah so here it's basically the book talks about these things in a little bit more detail you can look at it on your own so like public coin IOP and similar to all of the proof system definition before you can you have lots of different parameters that can also you can also look at it offline and here it talks about the non-oracle messages and like very similar you can also Define soundness Notions other

soundness Notions like knowledge soundness both for the straight line and the rewinding version yeah and also zero knowledge but yeah I think I would we'll move on to oh this definition will be useful so let's see the we talk about this verification on local view this is also like very pretty much the same as in the PC in PCP there's also a similar definition so basically what happens here is that even though the verifier is sending entire proof is

sending long proofs Pi eyes it the whole proof pii is irrelevant to the verifier decision bits other than the number of bits in pii the the little amount of bit the very few number of bits in pi eyes that are actually queried by the verifier so we can replace hi the there was so previously here it what we had Pi I in K but we can replace that notion with replace that part with Qi the queries qis query set qis and the query

answer AIS uh and this decision function what it does is it it deres the verifier query location the query sets based on the verifier Randomness and if any of the queries fall outside of the side Qi then the verifier immediately rejects if it doesn't then you answer the queries with AI yeah we will see how this is relevant in the proofs later yeah so this is analog to how in

PCP we also had the definition of this kind of decision that function and yeah so in the next section it talks about IOP State restoration we have seen this book there was PCP State restoration and there was IP State restoration and IOP State restoration is very much is very similar to the IP case in the only difference here is that now all of the IP Pro messages Alpha I are now replaced by the IOP proof strings tii and the IP acceptance

condition is replaced by the IOP acceptance condition so nothing surprising here but yeah let's just look at the state restoration game again just to recall um so in the IOP State restoration game you also you run the IOP State restoration prover the intuition behind State restoration games are the fact that the state restoration Pro they are much more powerful than the standard IOP Pro in the sense that they can query the Oracles in I round multiple times before they output some guess of an accepting transcript they

can make multiple queries and first the state resoltion G runs the state restoration prover and until the state restoration prover to exit the loop and here for a t- move State restoration approver this this happens T times so it can it makes query of the form of this form so it's querying with some IOP strings and some salt strings and notice that the St restoration IOP Prov since we're talking about a k round protocol it can query

any of the random Oracle any of the case random oracles it doesn't have to go or at first querry the randomness in the first round and the second round it can querry any of the C and it can querry one some more and some less it doesn't matter we don't care and then after the IOP State restoration improver decides to exit the loop the it outputs its final guess of an accepting transcript and then we set the verify Randomness to the Rand I of the I round rent set is set to rent I of the hash of those things then we

output the pi and the IOP proof string the salt and the verifier Randomness so even though this is not written in the book you can call you can do it as an exercise to just s check that S Restoration IP soundness you it should also probably be ounded by the state restoration of sorry the IOP soundness with p+ K choose t plus K choose K times the IOP soundness the reason is very much

similar for why we had a similar upper Bound for State restoration IP soundness it's because here the state resoration approver when it outputs its final guess of accepting transcript it could output something from the T queries that I made before but it could also just guess something that was never queried this is equivalent to K queries basically a cross is t plus K queries as long as K of them forms an accepting transcript then it's succeeding oh I'm just speaking very high level and intuitive that's an intuitive reason but you can look at in

the IOP session it's the proof is should be very much similar the IOP prover it get it the state restoration IOP prover wins this state restoration game by it because with much more Advantage than the standard IOP Pro because it's able to guess more times and the choices that it has is exactly t plus K chose K yeah and the rest of this part is about how you can sooner Define knowledge sness for also State restoration and yeah

now we are ready to look at the ibcs transformation which takes an IOP and merco commitment and transforms it into an interactive argument I will not go through the verbal version of this you can read it offline but I think looking at this picture is really helpful so as I mentioned this is like the IOP analog of Kean so let's see side by side let's recall what Kian protocol was doing so Kean protocol it takes PCP

merco commitment and gives you an interactive argument the way that it does that is the PCP prover it first outputs some proof string and instead of sending the entire proof string to the argument verifier the argument approver will first Commit This proof string through some Merle commitment scheme and it only sends the short commitment the merco tree rout the argument verif then samples PCP Randomness and send it back to the PCP to to the argument prover it then checks whether the PCP verifier would

accept by querying certain querying the proof based on at query sets based on this verify Randomness and it then sends back oh sorry oh sorry I miss I'm I oh sorry that was not the arguments Pro based on this verify Randomness it induces a query set Q PCP answers a and merco tree proof for that opening and it sends over these things to the argument verifier and the verifier

checks that the merco tree Pro merco merco tree indeed accept the merot Tre check passes and that the PCP verifier would accept if you zoom in on the ICS transformation it it is just like the first part here it is exactly the same as the Kean construction and the only difference here is that the we're starting from an IOP key which has K rounds so after Pi 1 we have Pi 2 the IOP prover will produce Pi 2 and then we just repeat the same

thing again we we just commit to Pi 2 and send over the root and the argument verifier send back its IOP Randomness and we repeat for K rounds in the end the IOP verifier qu the the the argument improver will send over the IOP queries and Oracle answers for each of these KRS and also the merco tree proof for all of the KRS and then the argument verifier checks that all the merco tree check passes and that the IOP verifier accepts the only thing that's worth that's a bit different is so we need to note that the merco tree scheme here it's using it could be using merod

tree commitments scheme of using different parameters because in the IOP the different Pi eyes they may be of different length so say Pi I is of length Li I then we should be using a different merco tree commitment scheme so it should be we can is different configuration of the merco tree commitment scheme so merro tree I is merro tree commitment scheme on message of length Li and then we can B non-adaptive soundness

of this ibcs construction it says that the soundness of the argument is upper bounded by the IOP soundness and the merco tree multi extraction error this merot triot extraction error is slightly different from the ones that we've seen before so recall that in mikali the merco tree extraction error is this one here it's basically saying whether the adversary can find some it can output some commitment and

and opening and proofs that passes the merco tree check but it cannot be extracted correctly so it's the multi extraction error across multiple extraction here the as I mentioned before because we are using different configurations across different Realms we have another multi extraction error where we allow the MTI to be different configurations and the merco tree multi- extraction error that we were using before Amali is a special case of this merot tree extraction error

that we are using now yeah and intuitively it makes sense that the argument soundness is founded by the IOP soundness and merot tree extraction error it's because it's very similar to all of the transmission we've seen before Kia and mikali more specifically the proof it's Bas is construct so it says it's Pro Ed proving is proved by proving this Lemma so it says for every tquery argument Pro plda there exists an IOP prover such that the argument

soundness is bounded by IOP soundness plus merco tree extraction error and the IOP prover is defined here it essentially runs the argument prover and extract the IOP proof and use those IOP proof to interact with the IOP verifier in the proof we start with the argument soundness and this is just by definition of argument soundness the argument prover is run in every round it outputs root I it receives Randomness row I and in the

end it outputs some merco tree o proof of the queries and answers and then the argument verifier checks if the IOP verifier accepts and all the merco tree check passes then this probability by total probability we conditioned um this is upper is actually equal to when this probability is conditioned on all extraction succeeds and conditioned on at least one extraction fails you can bounce the first prob so when all of the extractions succeeds oops

interesting so when all of the extractions succeeds you can replace these qia AIS with actually just Pi eyes as we have seen before because the extraction exactly tells you at location Qi of Pi I the query answer is AI so you can just uh let the verifier use those IOP proof strings instead and we can also throw away this condition and the is still going to be an upper bound and that will give you the IOP soundness and then this term here it's exactly if you look at it long

enough it's will be turns out to be the merco tree multi extraction error when across different when you can have different configurations the adeptness soundness is proved almost the exact same way whereas now we're using the IOP soundness uh with this instance and which I uh also we've seen uh before so it's the max maximum IOP soundance across all instances of L less than equal to n so I've highlighted all of the difference in the Adaptive soundness proof it's so here the prover the argument prover can pick the any

instance that's of length less than equal to n and not in the language of this relation but the proof still it it still mainly follows similarly except here you need to discuss the first round and then the later round separately so for I because the output of the argument prover will look slightly of different form so when I equals 1 the argument Pro outputs the instance X and the Merle commitment whereas so it outputs X and the Merle commitment and in later rounds it just outputs Merle

commitment but yes you can try to follow this proof and appreciate how to the change it follows from non-adaptive soundness to Adaptive soundness yeah and now let's finally come to the main topic of today which is the BCS transformation the BCS transformation b stands for vasen kza and Spooner it came out in 2016 and as I mentioned before it's the analog IOP analog of the mikali transformation so you're taking a public coing IOP and a merco tree commitment

and through the BCS transformation you get an argument and let's see so here's the I have the meali construction on the left and this is the BCS Construction just to recall how the mikali construction work so before inia we were sending the merco tree commitment route to the argument verifier and then receive back the PCP

Randomness but here to turn it non-interactive we are using another Randon Oracle FS to so it produces its own PCP Randomness using the instance the root and some random salt to it is important to Hash the root here because in the interactive argument it's sending the Merle commitment and then the verifier sends the PCP Randomness R Asing the route is saying it's forcing the argument prover to first pick the commitment to First commit to something and and then pick

the randomness it cannot first look at the randomness before it has committed that's why this is important to include as an input to FS is set a answer mer true proof opening proof and the salt it then deres its own PCP Randomness using FS uh it drives the PCP Rand by itself itself and then it checks that the merco tree check passes and that the PCP verifier accepts if you also zoom in closer here

it is the exact same in the BC transformation if you just look at one round so if I just zooming here that looks the exact same as a mikali transformation and but then exactly that's the exact why this is an IOP analog is that now we need to do this for K rounds so after getting the first Randomness Row one for round one we are going to include Row one in the next hash and hash use F2 query F2 with Row one won

the second Merle commitment so like we commit the second IOP proof string to root2 and then query uh F2 with the verify random nips from the first round the second merco commitment and a new salt Brandon salt and this gives us row two and can we continues this process so actually this is basically using the faster variant of FIA Shamir protocol on ibcs so what I mean is here in the faster variant of f Shir

we're also hashing the row ice in as part of the query to F2 in the normal fimir what we're doing is instead we'll be quering F2 with alpha 1 Alpha 2 and T one t two then you query Alpha 3 with alpha 1 Alpha 2 like you query the Brandon Oracle in the ice round with all of the previous approv messages and Sals but then the query size the input size grows as the round continues but in the faster variant what we're going to do is

we take out alpha 1 and Row one and replace that with Row one t one and we take out alpha 1 and T one and replace that with the hash of them so Row one and there was a procedure of how you can so basically you're constructing a hash chain this way in the faster variant and you can recover the original query in like the standard via Shamir through this kind of hash chain the caveat here is that through using this faster variant of FIA Shamir you get an additional error term here in the

soundness Bound for the argument so if we were to use the standard V transform then though this you can also avoid the soundness error but since we are using the faster variant it also give rise to a small loss in the soundness upper bounds yes that's so in the BCS construction we continue the argument approver continues doing this kind of hash chain and committing each of its IOP proof strings for all of the cave rounds and

in the end what it what is sending to the argument verifier contains all of the merot tree commitments the query sets the query answers merot tree opening proof and Thea for each of the K rounds given this argument proof the argument verifier can derive the IOP Randomness itself using this kind of hash chain exactly like how the argument Pro honest arguments Pro der derived the verify Randomness then in it decision bit does two check it checks that the merco tree proof all the merco tree check passes

All Passes and that the IOP verifier accepts so we can found the soundness of the argument as a result of the BCS transformation by the state res restoration I IOP State restoration soundness the merco tree multi extraction soundness with M differ configuration plus a small error turn that arises from the faster variant of FIA transformation and if the parameters satisfy some bounds you can the multi extraction

error can be absorbed in into this small error term and you are you end up with the State Reservation error plus some term of order of this small error there are two approaches presented in this book on how you can prove theorem 2 2.2.1 the first one is the direct approach it is also the approach that how we improved mikali soundness you directly Define the state restoration IOP Pro and upper bound the argument soundness by playing the St by

having the state restoration Pro play the state restoration game and winning the state restoration game by uh so it means that the St solution game should output some toppos so that would make the I P verifier accepts and this is it's going to be upper bounded by the by the state restoration IOP error and plus the Marco tree multi- extraction error and the small the construction is very similar to how we constructed the state restoration Pro the PCP State restoration prover in the

mikali construction the difference is that here instead of the argument prover can query all any of the FIS whereas inali it has to be just it can only be quering FS so here it can querry the ren Oracle for any of the K rounds and if it's quarrying the first front then the query should look something like this otherwise it will contain it will look something like this so you would discuss both cases and have the state resoration IOP Pro performed the merco tree extraction and then query the

IOP State resoration game using the IOP uh proof string instead yeah so the the queries that it receives is of the form bunch of the form of bunch of commits marry commitments since is running the argument prover but it will extract from those commitments and using the merco tree Trace to extract it will extract out the IOP proof string and query the IOP St resoration gain with those proof strings instead

and the final proof is by proving this is Pro the theorem is proved by proving this claim is saying that these two distribution are uh their statistical distance is bounded by the merco tree multi extraction error and the F Shir faster variant loss another proof approach is to use a more modular approach so as I mentioned before the BCS transformation can be seen as first doing for first you doing the ibcs transformation on I and the merco tree

commitment you get an interactive argument and then you perform VI Shamir and the faster variant to get a non-interactive argument in this modular approach we can first prove a LMA here it's upper bouns the state restoration IOP soundness oh sorry State restoration IP soundness of the interactive argument that were the result of the ibcs and it bound the state restoration IP soundness by the IOP sound IOP State resoration

soundness and the merco tree multi extraction eror it's then after that you can so basically the conclusion of that claim is that the state restoration IP soundness responded by ction IOP s this and the merco tree uh multi extraction and then you can and then we perform fi Shir so we bounc the argument soundness by the state restoration IP soundness plus the error term of the faster variant of f

Shamir the little the subtlety here is that since fimir is actually defined for IP but here in the interactive argument constructed from ibcs the Prov is it also uses a random Oracle fmt so it's also quering it's also making merco tree queries but the way that it still works nicely is that since we are when we are proving F Shamir soundness the F Shamir protocol itself it does not use any commitment scheme so it's only making blackbox use of this argument prover and even though

this argument prover is making additional queries to fmt if we just let the state restoration prover to State restoration IP prover to forward is the argument Prov ques to fmt and just still responds to his fmt queries as it would have received then it doesn't change the res the the behavior of the argument so here the we use this notation to refer to an augment to refer to augmenting the state the usual IP State restoration prover of

f Shamir and it's augmented to forward queries from the argument Pro to fmt and return the corresponding answer and you can still prove the restoration sound the FIA Shamir sounds this similarly so it'll still give rise to this small error term and yeah so here's a summary what this shows is that the argument soundness is bounded by state resoration IP soundness and a small error term so that's the transform that's this part of the transformation and then so that's the first half and then

we can further bound the stay restoration IP soundness by state resoltion IOP soundness plus the merco tree multi extraction error and that's basically the first part of the transformation yeah and that would conclude uh soundless upper Bound for a BCS yeah are there any questions okay thank you all for coming uh I hope you enjoy this study

group and yeah the this area of research is very rich and yeah I it is definitely very technical yeah it takes a lot of going back and forth to see the connections but I hope you enjoyed and yeah thank you yeah thank you so much