SNARGs Book Study Group - Week #6 with Christie Di

Transcript

hi uh I'm Christie I it's security so last week we recall that the presents the and uh it's a succinct arguments but in reality what we want is uh snar so we also the non interaction then the prover only do send one proof and the verifier can verify so that's that's will be the talk today the M Construction and basically looking ahead from Kon to mik we just need to perform

and uh remember recall that the Kon in the in the construction it's actually uh constructed from uh PCP and for mikani we will it will be also from PCP and tree but it's from St restoration PCP and the Mer tree so a station PCP captures the fimir transformation so because in F transformation you uh the pro uh can

simulate the verif response so you can actually simulate multiple rounds of and the verify interaction and it will output one of those by best try in order to capture the the sttion PCP is saying that even if the PCP approver can run the verifier for uh for example it will still it will [Music] still it it will not make the very first except X is not in the

language so this basically capture the Vere security so let's look at the definition of ster sttion PCP uh so we use for Star PCP we use a game to capture the idea for idea that the PCP PR can attack PCP multiple times so the game will will have the resolution Pro as will takes in the sttion pr and it will simulate the verifier Randomness using uh uh random Oracle uh it also has the a s size so this so is

basically so for the so for the uh F transformation so basically in the PCP interaction the PCP prover can output X and the PCP Oracle Pi for the same instance X and the PCB proof Pi it can Al it can run multiple it can run verifier for multiple times we basically want to derive this verif riness even for the same instance and Pi so the S size is say is basically saying that we uh basically

allowing us to derive different referen even for the same same instance and the ptcp proof but s defines the how many how many SS you can try for a same instance and the proof so the game looks like so the game will will takes will takes in the output of St resoration R for in this Loop so it will repeat repeat uh step one until the sttion approver uh decides to

stop so in each iteration the sttion approver outputs U instance and the PCP proof and uh starts off with choice so the the gain will ass simulate the verifier challenge by by hash all the hash the output of the Pro and it will gives this simulated verify challenge to the PTP approver and in the end after exit the loop the station approver decides to give a final output so this will be the final the the thing it decides to really

send to the verifier so from now on it cannot try verifier for another time and the roow and the row will be the final verify Challenge and we say PCP approver is T move if it execute step one for two times so now we have the definition we wonder how it relates to the original PCP soundness so recall that for adaptive soundness adaptive PCP sence the PCP Pro can choose a instance and Oracle of by

its own and we will sample the Vare Challenge from the randomly uniformly randomly from all string of size R and we will check if the side length of the instance is smaller than and if it's not in the language the probability that for still except so the difference here is the gain for sttion approver allows the sttion approver to try T times for more budget T and it and and the RO will be output

by the game because game is honest instead of sample here so intuitively because the stere restoration gain allows the pr to try different R verify Randomness for T times it will be T it will be like on the factor of T less secure than the PCP uh PCP sess so the here we have a plus one because in the end the last in the end uh after T iteration the the station uh have one more output in the end so it's

in total has t+ one twice and we will prove this by security by constructing the PCP prover given sertion prover the PCP prover will simulate the gain for the St stor Pro but remember uh in on the high level the game allows the St solution Pro to try T times but PCP prover only can only try once it will output an XP and it's over the RO will be some verifi challenge that uh PCP approver doesn't that

cannot get feedback from so for out of t+ one trials By The Station PR it will just choose random random one exp one random one try of those t plus one try T and the output output the J J's run of station Pro so we denote I to be set of indices such that x Pi is equal to the output equal to

the so remember that the the approver can TR T times and I is the set of indices that the ice the I outputs by the stage output by the stage storage improver is the same as the final output is the same as the final output by the game so as long as the J that PCP prover sample as well as the J that the PCP PR sample is inside this I it means that this output x Pi is the same as the

final output x Pi of the game so indeed whenever J is in this set of indices the x Pi output by the game and the PCP prover will be the same and the row row on the in the first probability is randomly sample string from of lens R and this row is the output of R&D a random function so it's also a random string so that means the the first probability should be at least the probability the the probability that the

St restoration gain wins because the predicate only depends on X high and low and all of them have the same distribution if J is in this set of indices and uh notice that this events that J is in I is completely independent of all the other events because J is a random is really a random integer so it a Rand the probability a random integer in a set of siid t + one is at least one/ t + one by the by the probability of independent events we can

separate this probability into the probability of J in I and the probability of rest of the predicat so that's how we get to this step and we can you can just uh switch uh this properity in to another side of the inequality and we will get to the final get to the bound to the PCP keys on this so is there any question okay I think we are good and for the knowledge sence it's

very similar so the knowledge sence is just has one so in instead of X in R we now have xw nothing in R where W is uh W is the output of extractor so if we set the resoration extractor to be the same as the PCP extractor then then the proof will be almost the same the W is the same because W is the same as long as X and Pi are the same because they're the same algorithm and the these parts are the

exactly the same as the sum is proof so whenever J is in I these two these two will output the same X and high and if we just pull the pull the probability J in I out we will get this t+ one in front of uh in front of the PCP sness Arrow so now we have a building block we can go to the real M transformation recall that the mikadi

transformation is really first apply the Kian transformation and then apply the FIA transformation so the FIA so the Kean transformation remember recall that in the Kean transformation we have the prover and verifier inter they can interact with each other so they both have a have a random Oracle for the for the mot tree commitment so the in the Kyan protocol it first the prover first simulate the

PCP approver and then it commits it commited to to the to the PCP Oracle pip to get the roots so you send the commitment to the verifier and the verifier will send a random challenge G given this random challenge the approver can derive the query set and the opening and the opening answer correspond and the answer that's High restricted to the square set as as well as some opening proof for the for

the Q and A uh for whether a is a valid opening for mot trade root uh and then finally verifier will output accept or reject so in meic construction we also because it's a non interactive for construction we want we want to we want the Prov to just send one pi and the verifier will output accept or reject the fs Oracle we have one extra Oracle FS Oracle in for the F Shir transformation and F sh

transformation will allow the Prov to simulate the verifi challenge row so the first two steps are the same it will non interactively construct the piie from the PCP prover and the Mer tree commitment but it doesn't send to the verifier instead it will derive the PCP Channel PCP rendance itself and it also because it derived the P Rance itself it can simulate this the third response itself as well so it it can derive the query set from the simulated

Randomness and also derive the opening a Mer tree opening and the answer restrict the answer correspond to the sare set so it sends single Pi which which is which basically contains the transcript of all the qn trans uh it's by pH hash itself and then it will check it will run as in K and construction to check if verifier PCP verif accept and if the opening is correct in high level really

it just it just the PCP uh the argument improver in M Construction is just simulating one it's just the the proof is sense is basically the transcript of one Kon construction and it can internally perform multiple Kean perform multiple Kean verification and only send the best one of its choice so in terms of efficiency measurement because it's non interactive we don't have the communication complexity instead we only have the

argument size which is the size of the single proof the pro sent to the verifier and the size is basically the same as the size of the transcript of construction in the Kean construction uh the Prov complexity and the verifi complexity is are uh almost the same as the Kon so they are both dominated by the PCP prover complexity and the Vare complexity in this diagram we can see more clearly that the r fmt fmt random Oracle can help the pro to derive the

commitment and the fs random Oracle is for the f transformation that it can derive Randomness for each each root theary outputs commits to and it just need to Output one of the row it it tries so far and for the verifier it will first use the FIA Shia to derive the same readiness and then use the fmt r Oracle to do the merco tree checks so now let's prove the

soundness so last week we already know that the nonadaptive sunus and uh from nonadaptive sonus to Adaptive sunus is very easy the proof mostly the same so here we will only prove the Adaptive we will directly prove the Adaptive sness of helan protocol so suppose that we have a mikali mikali construction with with let's see so here the M Construction so we have it it's upper

it's it's upper bounded by the key one times PCP sence error and the multi extractability error of vertical commitment so recall that the for the for keyan construction the argument sonus is upper bounded by Epsilon PCP plus single like the one extraction error for single extraction error for the Merle commitment instead of multi extraction error so there are two difference to the keyan case we have an actra t+ one factor and we have the multi extraction arrrow instead of

single extraction Arrow so the t+1 arrow so recall recall that I mentioned that mik is uh basically St restoration PCP plus veral commitment and we already know that the restoration PCP sunus is upper bounded by t+1 PCP sunus really we we first have the mikadi sness to be uh f plus uh merco tree arrow and then we by this reduction we have the t+ one in the final bound when we reduce to PCP sness

the multi extractor error is in to it's because we can perform we can perform multiple so the argument prover can try multiple times instead of only try once so the argument prover is able to query FS Oracle with different roots and it can quy multiple times so for each such route we can extract PCP Pi so that's why we we actually try to extract multiple

pies for the move for and Each pie will be used for a for the first move and the TS in the State resoration game so looking ahead head that's how the proof will work so we will construct PCP proof from each query root to the fs random Oracle and and the each PCP proof will be submitt to the St restoration game so each

root so because we extract for multiple times instead of one time this will give us multi extractability arror instead of a single extract extraction Arrow so the we can first prove we can first prove that argument is reduced to Restoration soundness and the M jaction error of Mer merco tree commitment we will show that this these two distribution were the first one

correspond to the correspond to the argument and the second one we will it will correspond to the stere soltion game and we will show that the difference between these two distribution are bounded by the multi extractability error of merco tre so the so the first distribution we run the argument Pro honestly and we get the S get a single Pi so we will run a single extraction to get

the PCP Oracle PI from this the root that's in the argument proof and so the five toles we care about are all the query answer pairs in the fmt to the fmt oracles the instance X and the Oracle proof that's extracted from the final output rout and the bits that indicates whether the argument verify accept uh the second distribution is the uh St restoration

game distribution it will takes in the argument prover and simulate with the stere restoration prover G so it will output instance pi and Pro riness itself and Al we care about the same tle but the but the beats here because there is no argument verifier we will the bit is instead the PCP verifier bit verification bit and uh some merco tree Mer tree opening check bit so this bit is to check whether whether some Marco

tree opening is valid or not the PCP stere soltion appr is is constructed as follows so it takes in argument prover so the argument pro has access to random Oracle FMP and the fs so the stere restoration prover needs to simulate fmt and Fs Oracle so it it will simulate the fmt Oracle honestly without doing any change but for each FS Oracle it will extract

so there are two cases either the query to FS is something contains a root or it's some garbage query so if it's something that contains the root then we want to extract uh PCP proof PI from the root and then we can submit submit the PCP pi as a move to the stair restoration gain and we can the game output the r the game output will be the the renous will return to the argument

prover in the case where the Cur is a garbage that doesn't contain any root so it won't be useful for the argument Pro anyways we we will just simulate with some random function with samples itself and just return the return row as the hash of such random function so in the end the argument prover will output a pi and the PCP the resoration pro will run the extractor the last time to uh to Output the last to

Output the last pie it will submit to the St restoration gain and the BMT here will be the will be the bits that checks whether the argument prover outputs something that's that can be open successfully it so it basic basically the bits AR bits or the argument verifier breaks into two part PCP ver and the merco tree opening checks so in order to prove the two

distribution are are the same except some probability we need to show that the five tole the four toles the top of four elements are the same on both iter have the same distribution and we also need to prove that the queries to the argument prover are the same otherwise if the current distribution in the two distributions are different then the argument prover is able to tell that the answer is get from caring the oracles are different in the

two case two cases then the argument Pro can abort so they have to be the same per distribution so we will we will Define some bad event e so this bad event e is basically the the multi extractability arrow so notice that if the extractor for each root it extracts some [Music] Pi extract some good Pi then we we are just inside the stere restoration gain so as long as the extractor works

fine the two distribution should be the same so the bad event is saying that the extractor doesn't uh extractor fails so it's either the case that verifier accept but the the the extracted Pi is different from the opening so it's saying that the pi that's extracted in Step eight so the St restoration in the end the St solution expect some PI from argument Prov final

answer so if this Pi is different from a a is the opening a is basically so the argument Prov has some internally it can run it can run some PCP Pro and it has some PCP or a proof so this is saying that the the PCB Oracle that this argument Pro internally has is different from the the PCP proof that the stere resoration pro

extract or the other Bad Case is where with submit two different F Shir queries root J so we submit some root J in one iteration and we submit root J Prime in another iteration the bad event is saying that we submit two different two two different curves such that the curve have the same roots but the extractor but the extractor uh extract to different p in the two the two different

iterations and this is bad because this is saying uh this implies that the argument prover is able to find two two different two different openings for the same commit ments the condition on the that event doesn't happen the two we will argue that the two distribution are the same so we will argue by by saying that the toles every term in the toles are the same and we argue that the queries that argument receives in both distribution are the

same so let's first look at the ques to the fmt oracles fmt oracles because we simulate fmt Oracle honestly we State restoration prog simulates the smt Oracle honestly and it doesn't change anything they should have the same distribution in both cases for the Cur to FS Oracle there are two cases either the query to FS is of is it's composed of contains the root or is it's just

some garbage query that doesn't have a valid format if it's a garbage query then it's easy we just quy the G random Oracle G that stere resoration Pro samples itself so we in in the in this distribution one let's let's call this D1 and maybe the arc and this one is the sertion so in Dr in Dr if x is invalid is in the B for format so basically it it cannot be passed as instance root and to

then in Dr AR distribution Dr it will the the West will receive F dollar and in the second distribution the DSR it will receive GX so because both fs and G are random Oracle these two have the same distribution so let's look at uh the other case where X is of good format it's something that contains the root in this case the Dr will

carry this tople of three elements and in these the restoration it will submit submit a move of of x to Sigma where Sigma is the root in to and Pi is is the extraction output from the from the root and the trace in the m m Mt Oracle we can see that so the move

is actually it's simulated by the game Sr as a as an output of R&D random Oracle so if it submit a move what it really get is actually uh a result of R&D Rend Oracle but with pi and sigma instead of roots and Tow uh so essentially we are comparing these two distribution the first one is the output of x pi and sigma and the second one is the output

of FS with input audio I thinks might died can you hear me now yep thanks okay sorry yes I think I was yeah let me re re go over this part again so we are essentially compare the output of R&D random Oracle where with input x pi and sigma and the fs Oracle output with input X root and to so because Sigma is

contains root and to what is really different is this input Pi so both are random function so as long as we can show they have the same distribution then we we should be able to argue that the querit toe FS are the same in both cases indeed by the because we condition not e it means that it means that the first case so the first case and the second case won't happen so now we have event e

or now the better event is the F event e or event two so the negation of this B event e is the negation of event one and the negation of event two so the negation of event two is saying that for every for the same root we can always extract the same Pi basically that implies for the roots we have a one to one correspondence to the pi so each root correspond to a unique Pi that means it it we we always

we when we query the same X root tow we will always get the same query and and because R&D and Fs are both Rand the Oracle the if the input distribution are the same the out output distribution should be both random uniformly random and identically distributed so now we know the Oracle queries are the same so that means that means the argument prover cannot tell any difference in the The Dr distribution

and DSR distribution so it means that the pi it outputs here and the High outputs in this step should be the same otherwise it means the argument prover is able to tell whether it's a query the query answered by the real random Oracle or by the simulated random Oracle from stere restoration Pro B so basically everything in the pi everything output by the argument Pro should have the same distribution in particular that includes instance X

and and pi and because X and because little Pi are the same if we run extract if we have the same Little P we will have the we we do the extraction on this root will give us the same pi as we as in the extraction of this root so if this little p the same the root will be the same then the extraction will give our give us the same big

Pi so this part X and big Pi should have the same distribution for the romness row the renous row will can be similar can be argued in the same way the first one is the hash of X root and the second one is a move to the St restoration game so it's actually is the R&D of x pi and Sigma which is the root and to by a similar argument as in the C to

FS we can we know that the row here and the roow here have the same distribution finally we for the bit B the first for the Dr distribution the bit B is the verif uh bit B is the verif argument verifier output and for the D restoration the bit is the PCP verification bits and the Mt merco tree opening check

bit so we know the by the con instruction of mikar the argument verifier is checking first the argum the PCP verifier and then checking the and then perform the Merle tree check in order to show the distribution of B is the same we will show we will show that if so we want to show that b b equals B AR is equal to B stere solution then we need to show in both

Direction so in the first direction we can assume the BR is equal to one and then we want to show B station is also one BR R is equal to one it means that there's a PCP Pro accept and the loal tree check is one so because the event e doesn't hold so in particular the first condition doesn't hold then we have then we will we know that the pi Q must be equal to a otherwise this equal

to zero but we assume it's not equal to zero so we have uh Pi Q equals to A by condition on not e so if we have Pi Q equals to A that means that means the the the the the bits the very uh the PCP verifier in St restoration distribution is the same is also one why is that because this Pi is the same as this uh this Pi restricted to Q is the same as the

answer other in in the other case we assume that the BR AR is zero and we want to show that BSR is also zero so it's zero either if the first part is zero where the verifier is reject the rejects or the second part is zero where the mer check fails so in the second case we know that we know that the we know because we are we are compos of the two conditions

if this is zero then this if the then if this is zero the BMT in the state resoration case is also zero otherwise if it's one then then it must be the case that the verifier PCP verifier is zero but but PCP verifier is zero by condition on not e that means that means the pi Q is the P Q is uh equal not uh that means Pi Q must be equal to a so that that

that will implies that the bit in St resoration distribution is also zero for the PCP verifier so that's how we prove the two distribution are the same condition not e so then then if we they they are the same condition not e then it means that the the two distribution are the same except when e happens so there the there there the same ex there

prob there probability of better event e close in this statistic statistical distance what is the probability of e we can see that these two events are very similar to multi extractability events what is the multi extractability event so the multi extractability is so just to recall here's the definition in multi ability the adversary can output multiple roots and the multi the extractor extract multiple

message extract the message multiple times from this roots and in the end adversary outputs output some query set in our case it's a Q and the answer and the opening proof the motic exra ability is is upper bounding uh upper bounding the event that for some so in our case we can view the P argument as the adversary for mul extraction so the P argument whenever it makes OS s quy it's submitting a root to

the extraction interface so the so whenever it submits a OS s the extractor will extract uh a PI from the root eventually this PR AR will output Cur set opening of the final root and the opening proof so this uh is actually the root finally output and this this event and this predicate is saying that in in our case we'll be saying that

the the last extraction the last extraction Pi when it restrict to Q is not equal to a that's output by the by the argument prover or the the or the merco tree opening merco tree check fill and this event is it's same as our case two the event two so this part is event of one this part is uh it's is implied by event one so event one record that either VR equals to one is the event

that VR equal to one and I Q not equal to a so v r not equal to one we r equal to one implies that uh Mt check equals to one and this and the pi Q not equal to a are the same in both cases so E2 in in our construction is saying that they doesn't exist I I prime such that root I the root I and the root I prime query to the OS Oracle are the same but they

extract to different Pi so event two are exactly the same as the second condition of multi extractability so that's how why the uh probability of event e happens is extract is upper bounded by the multi extractability of M tree commitment so combining all of these together we can we can uh we can conclude the proof so we first have the argument prover and then we construct the state restoration prover with access to the argument

prover as in in this like in this construction and then we have shown we already proved that these two distribution are exactly the same so the are exactly the same except probability of e which is upper bounded by the multi extractability arrow and the topos we care about are the row x i and B and the left the event the

predicate both probability o only about those things the pi row bit B so this together is the B argument and the row are the same row are the Same by the so because the distribution of those tles are the same the probability must be the same as well and because ending a extra event will only make you probability smaller so we can get rid of

the last predicate and and then we can and then this is exactly the St resoration gcp s z so indeed we have that the argument sence error of mikali is the St restoration error thus error plus the multi extractability error and by the previous claim about the redu action between the soltion PCP and PCP onus we

have a t + one factor when we we reduce to the PCP on this so This should conclude the proof