zkStudy Club: Subquadratic SNARGs in the Random Oracle Model [Eylon Yogev, TAU/BIU]

Transcript

hello everyone welcome to this week's edition of the zk study club today we're excited to welcome elon yogev from barlow university and um he's going to be presenting work that he co-authored with alessandra chiesa from uc berkeley on sub-quadratic succinct non-interactive arguments and the random oracle model so with that uh over to you elon thanks a lot for being here okay hi everyone thank you thank you so much for inviting me here um okay this is i did a joint work with alessandro i'm gonna talk about snogs in general i'm going to talk about a new construction of snarks in the

random oracle model um so what i'm going to do with this stock so i want to present exactly what our result is okay and i have to be slightly precise in this i'm gonna show you the new construction i assume will not really get to how you prove the the security but if we have time we'll get to that uh but i want to start with just like really one minute about this uh slight landscape of the of what is the proof system okay and to make sure like we are all sitting on common ground and we know what we're talking about and i think this is also very informative

okay so the really classical you know proof system this is what's called an np proof system we have some what we call a language l okay this could be like r1 cs or or just any the language of satisfiable formulas and so on okay i'm not going to be like focused on exactly the encoding of the instance and and constraints and and stuff like that so we just have some languages and we have some instance in the verifier is wondering you know is is x is this instance you know in the language okay is this formula satisfiable is this list of constraints you know can be can they be simultaneously satisfied okay by some

assignment two variables and the np proof system can be viewed as follows we have some approval and this is like this powerful poover he has what's called a witness he has like assignments to all the variables that make everything satisfiable and he's sending this witness to the verifier and we usually have these two requirements we have what we call completeness means that if x is indeed in the language then there exists some w there is this some witness w okay the w that it says such that when you run this verify algorithm okay denoted here by v with the instance x and the witness w is gonna output one okay output one meaning yeah uh i agree okay i concur that this

is in the language and soundness says that if x is not in the language then no matter what approval says okay for all w uh the verifier is just gonna reject so it's gonna say zero okay so this is like a a a perfectly sound proof system for the language l with one round of interaction okay maybe just before we move on let me say please if you have any question whatsoever just feel free to unmute yourself and ask um okay uh while this was one round uh we have what's called an interactive proof system okay or really like a whole class

of different types of proof systems well in general we still have a language in an instance x and now the approval and verify they can communicate in many rounds and many of the proof systems you might have held on heard of actually are exactly the same setting only depends on these following parameters so we have the communication complexity okay how many bits are sent during this interaction we have the number of rounds we have the number of bits that the verify reads okay we'll see this in a second um we have the class of cheating proverbs i'll also talk about this and we have

some strata okay if they like share some initial setups initial randomness and so on okay let me give you a few examples that we're actually gonna use in this talk uh so ipip is just the class of all interactive proofs okay the class of all languages that can be decided by interactive proof you can have many rounds and the verifier reads the entire communication and this class we know like it's very powerful it captures um the entire p space okay so things like way beyond envy okay these are like extremely hard languages and they all have like interactive books um

if you have what's called a pcp this is again this is a proof system in the same setting okay just different parameters this is a one round so there's no interaction okay the pool will send just one message to the verifier just like an np system that we saw the only difference is that the verifier is local okay what i mean by local verifier so if the poover sent this very long proof the verifier only reads a few symbols from the proof okay so he randomly you know he tosses some coins randomly decides on a few bits or symbols to read okay maybe field elements and then decide if to accept or reject

and we have like the the big pcp theorem saying that you know in this model with like logan random bits okay like not extremely important the parameters and all of one queries so it can really be even reduced to three queries um this class captures np okay so it has the same power as an np-proof system okay you can actually generalize this and you can take the interactive proof system and you can take the properties of pcp and you can combine them together and you get something that i assume at least most of you have called an iop

okay this is an interactive oracle proof this is a proof system where we allow many rounds of interaction so uh not like a pcp here we allow many rounds of interaction but the proverb is sending like some message the verifier only reads a few bits from this message okay then the verifier can send some message back to the approval the approval responds with a new message and again the verifier only reads a few bits of this message okay so we have many rounds but a local verifier okay local in the sense that he reads only a few bits of of each communication amount and uh something that i'm calling here i think

for the first time as the iop theorem okay um some remarkable property of this of this iop that we can actually achieve iops with linear communication okay and this is like in sharp contrast to pcps where currently we do not know how to get pcps with linear communication so if i go back here the pcp this thing was actually pretty pretty big okay linear like in the number of variables okay for the sat formula okay linear in the instance let's see um okay after all this we have something that we

call a snug okay actually could have started one step before with a interactive succinct argument okay but let's go all the way to personal so this is going to be a succinct non-interactive argument so this really tries to capture the best of all worlds okay um the pool there is gonna be non-interactive it's one round okay the pool just sends a proof okay now instead of sending a long proof and the verifier reading a few bits from the the entire proof is just choked okay so this is the entire proof so the verifier is going to read all of this all of the proof but he's actually you could think of him as local because the proof anyway like is very short okay

um and this thing is actually impossible in general okay uh but it is possible if you bring in the magic of crypto and you allow computational soundness which i'm gonna uh talk about now okay once you allow you relax the sound is too computational suddenly this magical object constant is possible and we can construct it and i could say like uh all the fun starts here and this is quite a um a strong primitive okay we currently don't really know how to

build it from uh what we call a falsifiable assumptions or very like simple theoretical assumptions uh but we have many construction from uh from um slightly more heavy assumptions and we'll see we'll see one today okay so the focus of this talk is going to be about snarls in the random vocal mode so here we have approval uh we have a verifier approval sends one message this is the smell okay and this is in the random oracle model so what do i mean by a render multiple model both the provider and verify uh i assume they have some shared

results called the random oracle i'm denoting it by this letter okay it's some function that can take an arbitrary string and outputs lambda bits okay lambda is going to be like our security parameter okay or a function of the security parameter um so they both have a auto access to this function okay in reality later um like you can heuristically implement this function by some like crazy cryptographic hash function like sha-256 or something like that but to analyze things and to prove security uh what we're doing we're proving it in the random local model so i'm assuming that every input here is just mapped to some random a longer bit

string and putter and verify have only oracle access to this function say they can send the query x and they get back the response y okay and we're going to measure the number of queries that they do to this orchid okay so beyond that if they didn't query x they have no information about what the value y is regardless of what any other queries they did okay so this is like a truly random function that sits in the sky and everybody has access to it the pool the cheating pool were under verified um so what we require from this pool system is that the soundness is computational okay so what is computational soundness

um i'm gonna define it i'm gonna explain and i have some slight mathematical notation here this is i'm going to say that the system has t epsilon security okay and this is t and epsilon are going to follow us for the rest of the talk so what is the absolute security tf7 security means that any t query unbounded adversary so my cheating proven feet he has undoubted computational power okay but he's only limited to do t queries to the random overkill this is the only limitation that i'm putting on the on the approval so if we so here i'm saying that if we really sample

uh this random overkill from the functions of all the you know all functions that output lambda so this is like a truly random function and i'm right i'm running the the cheating program with oracle access to this random okay he gives me some output pi the probability that the verifier is going to accept this proof okay is at most epsilon so if if my instance is not in the of course we have the the same completeness okay like if x is in the language then the velvet is gonna accept with probability one okay i'm talking about soundness if if x is not in the language if this is a false statement the probability that any cheat improvement that does it mostly queries it's going to convince you it's going to

form is at most epsilon okay any questions somebody wrote something okay because this is a snog in the random world yes alex you wanted to ask uh no i was just going to say ilan if there are questions that pop up in the chat i will uh i can read them aloud so you don't have to keep watching there's none so far um thanks okay okay okay so why do we study snogs in the random local model okay uh the first and maybe the most important reason is that it's an elegant

model so like we like elegant things and we like to study them okay and it's elegant partially because it's an information theoretic model okay so it doesn't really go and assume that the p is different than np or some some group is how to compute this kit logo any computational assumption or specific subject okay the information theoretic model assuming that cheating pooler has this oracle access to this completely random function okay um it's not just a model we actually have very nice constructions okay uh the most popular ones are the famous mikali construction and recently

the bcs construction we'll talk about them um okay so it's a model that's it's nice and it supports good constructions what can you do with this model well heuristically we as we said you can actually just take any crazy hash function like shuttle 56 or some other hash function and you just implement the random number with this function and then you get a concrete scheme okay so this really gives you like just a scheme that you can implement and um it uses very lightweight crypto okay like these hash functions are usually quite easy to compute and this is like opposed to let's say other assumptions or over lattices or

stuff where things get slightly held to uh to compute uh it's possibly post quantum secure and actually there are proofs of these constructions to be post quantum secure in the random oracle model so if you if you assume you're like a chat of 56 is also post quantum secure then you get a construction that's also plausibly post quantum secure so that's a big bonus uh you don't have a lot of setup okay so the only like a quote-unquote setup you have in the system is just agreeing on this random function okay and this is actually deployed today in in biosystems uh i guess you even know more about this than me

um okay so what constructions do we have of sounds in the animal local model um so we have two main constructions the micalli and the vcs they both work in the same paradigm okay so this is like the high level overview of how the construction works it takes uh information theoretic proof okay that we talked about in the beginning so mikali takes the pcp and bcs takes an iop i'm gonna be focused like on the simple pcp like single round case here okay but like everything i say actually can be applied to iops um so mikali actually took a pcp

then he took a cryptographic commitment okay that supports local opening this is like what you know as a american hash okay a merkle tree and this you can easily build in the random local model and then you take these two together and you compile them to a single argument okay this is like the the high level of the view of the of the construction and we're going to slightly more detail i just want to remind again what the pcp is if somebody forgot um so a pcp is a single message okay i have a pcp approval he sends a single message the verified just this message might be long so it's not succinct okay

it might be like a huge a message it's a it's a proof for some statement okay some x is in the language or maybe some algorithm on input x you know outputs y after running for t steps so it's like some huge computation and this proof is is going to be usually like much larger than this computation okay but what is extinct in this proof system is that the pcp verifier he only needs to read a few locations okay from the proof to be convinced okay so how does mikali's not work so what is the honest move we're gonna do the honest prover is gonna compute a pcp okay for the statement okay so we have

this some statement or large computation he's gonna compute the pcp it's gonna write this so this yellow orange i don't know boxes here i like all the symbols of the pcp he's gonna commit to this pcp okay so he uses the random overkill and uses a miracle hash to start hashing the the symbols together until he gets like the root of the tree okay so this root of the tree is actually just a commitment a binding computationally binding commitment to the pcp after the proverb is now committed to a specific tcp he's gonna apply the random overkill on this route okay so this is a random worker he's

gonna hash the route and this hash is gonna give him the pcp queries of the verifier okay so instead of having the verifier um until having the verifier toss coins by himself and decides which bits uh to to read we cannot allow this because the approval is not going to actually send the entire pcp the approval is going to simulate the verifier by himself so he simulates the randomness of the verifier this is what's called a feature new paradigm he simulates the randomness of the verifier by applying the the random oracle on the root of the from the pcp he gets randomness this randomness defines uh the locations in the pcp that the verifier wants to read

okay and then what did he send what is that what does the proof contain it contains the root this root the root of the pcp contains all the pcp answers to these queries so this is a query say oh i need to i want to know this location this location this location like let's say three locations okay so it's going to contain the value of the pcp in these locations and then it's going to contain all the authentication paths okay this is the healthy authentication passes from the merkle tree so if you want to authenticate that indeed the value here let's say i had a value here of seven you know the value seven indeed is the fourth root the fourth leaf

lift that set in the commitment for this route then you need to send all the nodes along this and all the bottles okay so i'll need to send this one and this one and this a and this one and this one and this one and this one and this one okay but it's only like more or less a login nodes to authenticate a single a single element so this is what the approval does he writes the ptp completes the american tree derives pcp randomness for the verifier and sends the root authentication path for all the queries what does the verifier do well he reads the pcp answers and he sees that indeed these are

answers that make the pcp verifier accept uh and once he's done with that he verifies that these answers are indeed the right answers these are what are hidden inside the commitment so it verifies all the authentication tests okay okay moving on one question is you know what is the size of this proof okay um i hope you like you have a feeling i have an understanding of how it works and it's not going to go over this again

a bit but like one question what is the size of pi okay so it contains the vote we have to like see is this a large proof is this small how small it is okay it does seem succinct okay because we're not sending like the entire pcp which is huge uh we're sending like only locations in the practice but let's try to compute how loud it is and before i go into like the details of actually you know computing this let me give you like a one slide of uh too long didn't listen maybe it should be here actually um so mikali's construction has something that i call a quadratic argument size and

we'll see quadratic in what okay but quadratic argument size and we give a new construction it's going to be based on mikali that has a sub a slightly sub quadratic argument size and this is really the the first improvement to like the size of michaelis construction in 25 years so even the vcs construction like um eventually has the same at least asymptotically speaking has the same argument size okay what they do is replace the pcp with an iop and get like extremely efficient and practical parameters but but theoretically speaking they have the

same arguments okay so a slight warning a little bit of math ahead maybe this is a warning maybe just this is just like a indicator that the interesting part is they're kicking in um okay so what is the size of mikali so suppose mikali in the in the metallic construction we use the pcp and the pcp length okay the number of leaves is l so we have ellipse we have an alphabet sigma okay so you can think of a binary alphabet like the bits of the pcp being zero one but it could be like over some other finite field

uh and we have the number of queries of the pcp okay this is q once you have these parameters and you can write the size it's kilo log sigma because we need to write the the q answers to the pcp every answer is log sigma okay so writing the bits of the of the field element and we have queries and then you have to authenticate uh each query so if you want to authenticate each query so we have queries so it's q and then we have a lambda here so lambda is the length of the random overkill okay so every node is lambda and we have more or less login okay a login nodes okay because we have

to send along the depth of the three okay so l is the number of leaves and we have a logan okay so this is the size of mikali and now we have to go back to our definition of t epsilon security okay and okay you know i have this but you know what is the length of the random oracle how many queries does the pcp have okay so i'm telling you i want please go and build me a snog that has t epsilon security okay and like you give me some specific parameters for t and epsilon okay like this is i don't know 2 to the 100 and epsilon is 2 to the minus 100 and we'll talk about

like settings of these parameters okay but for now they're just available so i want the excellent security i want to claim that the random oracle okay has to be actually of size roughly log t over epsilon okay so this log theologian is going to play a part here and we're going to talk about this for a second just take it with me for a second the number of queries actually also has to be login epsilon okay and if you believe me for this claim okay then what you get is that the argument size is quadratic okay so what you get here this is very small you can just ignore it and i'm gonna even ignore the

log l okay just i'm gonna give it for free like in this stock i'm gonna try to like remove these things i have i'm thinking only on these two parameters q and and and lambda both of them need to be log t over epsilon so we have log t over epsilon squared okay so this is why mikhail's construction is a quadratic and this other hiding all the small things that i don't wanna like put in here okay so now i need to at least convince you slightly okay before i get to like our results uh while this is true okay um

so let me just uh i want to like convey like a few attacks that are possible by a cheating pouville so we can see why can't we set the the output to lambda to be like very small okay why not send set this to be like three okay maybe the under marker can output three bits okay so um so why is construction secure okay it's secure because the cheating pool will like the security goes by saying that gt improver can do nothing but computer pcp okay but if x is not in the language like if the claim is false then any pcp is not a valid pcp

after he computes some invalid pcp he commits to it to get the pcp randomness okay but then this verifier is gonna reject okay so you can try to build the commitments and get and get queries but then the verifier is going to reject and this is why like he has no chance uh so one thing we need is that this miracle has to be a commitment okay so one thing that the cheating pool can try to do is find a collision it's going to be a collision attack so if he's like computing this three okay this could be like part of the three he could take some node here and he has like two values v zero v one that has to you and you can try to find

another uh pair of values v zero prime and v one prime that hash to the same as symbol u okay if he managed uh to to do that then he has a collision and this means he can like if this is a leaf he can actually open this to either v0 or or v0 prime so he has two possibilities to open and this actually gives him the leverage so let's see i see there's a okay hey alex you want to just check if um people can unmute themselves okay so somebody's asking what is d

uh yeah i can but you can probably see it in the comments i'll let you okay mine looks like he maybe you maybe answered uh ariel's question it's always good to read out the question though because this is going to be a video afterwards yeah so um so t is not the t is the number of queries that we are allowing the cheating proverb to do okay and l is the size of the pcp yeah yeah so it's not a cube that we just have a log n though okay so t and there are two different things yeah i hope that time says sorry to interrupt uh for the benefit of

the viewers of the youtube channel uh the question was what was t circuit size isn't doesn't l equal pcp length also at least t in which case the lower bound is actually t cubed one over epsilon squared instead of t over epsilon squared so and then yeah so uh yeah a good question so you know l is the pcp's length so l is like going to be much much shorter so let's say our statement is of size you know 2 to the 20 okay just for like an example but t is going to be the security that we want so it is like 2 to the 100 to the 200 something like much larger than that okay and but you're right that i'm

missing like a logan here and i'm saying like i'm trying to like focus on the important parameters uh okay so we said that um okay so we said that if the attacker finds a collision then you know this commitment wasn't a commitment and then it can open in various ways and he can actually cheat the pcp and he could fool us and another attack is uh what i call an inversion attack okay so here's just one attack that the cheating mover can do okay you can start by just querying the root without building any tree behind it

okay so there's got an invisible tree here it just queries the root and says oh this is the pcp queries for this root okay once he knows in advance the pcp queries it's easy to find a pcp that fools a verifier that's gonna use these specific queries okay so the order is usually uh is reversed right i first commit to a pcp and after i committed the pcp the verifier is gonna is gonna choose the locations to read if i know in advance the location is time to read that it's very easy to come up with a pcp that fools this verifier um

okay so after he he sees the pcp quiz he can say okay this is the pcp that's gonna win okay so this pcp is fine he computes he starts the computer military he stops here at the like the last step okay what's the problem this last step might not hatch to this route okay it's going to hash to a different loop and then this different food is going to define different queries so he's got like going to cross his fingers really really hard and just hope that it's going to hit this same route okay this happens with small probability i agree but this is a valid attack okay and we have to take this into account and i'm calling this uh

inversion attack okay because like he he inverts the value of the root okay like he has this value y and it comes up with the x after this is y um okay so with this in mind uh we can actually set low bounds for uh for lambda so again my claim was to get the epsilon security you have to step longer to be logitely over epsilon so let's just see this um so this is just the inversion root that i that i said you can guess the root in advance and derive a fooling pcp okay the probability of success is the probability that in this last step i hit this this is a really small probability

it's two to the lambda okay to the minus lambda but i can try this three times okay or roughly two times okay because it didn't cost me a lot of queries to try this okay it cost me like roughly l queries okay so i can repeat this 90 times but overall that's forget about this small parameters here so if i repeat this t times my success probability is actually t times two to the minus lambda okay so i have this real event of success i thought two times and now we said the epsilon security we said that if you have thick queries your successful ability should be at most epsilon

and this is the successful ability so this must be at most epsilon and if you rearrange this you just get that lambda's log t over epsilon okay so this is like one low bound saying okay lambda cannot be like too small it has to be at least log t over epsilon okay so uh maybe i'll go back we had this okay and now the second statement what about the pcp maybe the pcp has three queries and then this is just three times longer okay and i don't have a quadratic thing okay so now i'm going to claim that to

get the epsilon security er the number of queries of a pcp must be logged over epsilon and this is slightly trickier to prove okay and i'm not gonna um show you the entire proof but let's see what we want from the pcp okay and in particular this is actually like a conditional result like if p equals np then actually we have pcps with zero queries right because the verifier can compute anything by himself okay so you have to like assume some computational assumption here um so i claim that we want the pcp soundness

okay so the error of the pcp should be actually much smaller than this epsilon it has to be an error epsilon pcp which is epsilon over t okay and why is this this is because the cheating pool can just try to fool the pcp t times you can just commit to a random pcp okay just take a random pcp random string commit to it get the queries of the verifier see if by any chance the verifier accepts okay if he accepts fine like he has a footing proof if not he just starts again with like a new random string and and and does the same so again he can try this two times and

every time he does he has like an epsilon pcp probability of winning and so if you want the probability to be epsilon you have to set epsilon pcp to be epsilon over t okay and uh for pcps and in a recent work with ali actually we also saw that that the same hold for iops assuming what's called the eth the exponential time hypothesis this is like some strong version of p versus np okay this says like np is not only like different than p like you p versus np says like you cannot solve np in polynomial time the eth says that you actually need exponential time like

strictly exponential time to solve the to solve np so under this uh today like wildly i i would say believable assumption um then the number of queries is always log one over the epsilon pcp okay and if we plug this in we get again log t over epsilon okay um so we had the mikali construction which had this luck development square you could show like uh quite easy to show low bound of logity of an epsilon this is like the best we can hope for okay

and uh and this is the state that it fails and now i can say what our result is okay with all these notation um there exists a slog in the random variable model that achieves log t over epsilon times log t okay so instead of log the inversion square log table sometimes look d so it's slightly uh subquadratic um i'll say one thing about the general approach we'll see the construction a bit i'm not sure how much time i have but yeah you still got uh technically we've got 45 minutes left of the session so um yeah it depends on the time you want to

leave for questions at the end yeah okay i think that would be like too much people will get too tired um okay so i'll just like intrigue you at this point for one thing about our proof what we do we use it like a similar paradigm but slightly different instead of starting with like a pcp on iop we we start with like some strong variant of a pcp okay so like it has some strong sound assumption we combine it with a weak cryptographic commitment so this is something that's actually not going to be a commitment okay it's going to allow the cheating poover to open to like different possibilities just not all

possibilities it's gonna still limited limit in some way and together we're gonna get this top quadratic stone and just putting this back on the scale that we saw before uh so you know i still would say that it's what it's like much closer to this than to the lower bound okay like between our walk and the low bound there's like a huge gap here and i just mentioned like uh um a very very recent uh walk that's not like published yet um in a joint walk with a iftar height now from tel aviv and is the master student uh daniel uh we showed that this is actually the correct answer this

is tight okay so we show a low bound that matches this expression exactly but our low bound works for our family of constructions so it's not like a completely general low bound it captures some family of constructions this family captures all the constructions we know today okay but it it's still plausible that is some construction that beats this just maybe we have to like think outside the box okay it's not the the same way the same you know tools and methods that we're used to um okay so

uh the way i i showed the result is like very theoretical hiding many things under this old leader notation i want to say that i'm mainly hiding it for this simplicity of the talk we actually worked very hard to get like very uh tight and concrete parameters in in our analysis and what i have here is a table comparing like the standard mikali snug okay without improvement you can do the same for uh bcs if you know like the bcs construction just you do the same round by round okay so like i'm comparing like a single round here uh and what you can see in in

in red is mikali and in blue is our so this is like the actual size of the snog um and you can see the the improvements here you can go here to like my favorite part of the table where we have like the best improvement so like here you get like a factor of two improvement uh but so this is like when t is is slightly small and and and log one over epsilon is quite big but like even in these parts of the table you get the improvement um so i want to talk like like half a minute so what should i you know what is t in

epsilon okay what should i i uh plug in there uh so this is actually a big discussion and and and could be like a big debate i'm not gonna like go over all different pros and cons and what is like the right definition of okay what does it mean when i say that my system has 128 bits of security okay this is like a a sentence that it's not exactly well defined and if you define it then maybe why is that the right definition um i'm just going to say it actually can depend on on different settings so like one common approach is like yeah just set t to be one over epsilon so for example t is 2 to the minus 2 to the 128 and epsilon is 2 to the minus

128. okay so this is a one setting a very natural setting so this is this you know the diagonal of this matrix okay so we get like some reasonable improvements there there's two other settings that you know i call here the online and offline setting i'm not sure like if it's the right terminology but the online setting says hey you know what happens if i have a snug and it's online so like i go to you know my bank and i say how much money do i have and they give me an answer and give me a proof that this is actually the the amount i have in my account okay like a snug proof

and you know i i wait for one second for the response if they don't give me the response after one second then you know i just i i know what they say okay and if i want i can just re-query like with a new randomness or something like that so in this online setting if like i'm limiting the approval to walk within like one second then the cheating pool also has only one second to walk now it could be the case that there's like billions of people doing this around the world so i still need the probability of a cheating pool to succeed to be like very small let's say 2 to the minus 100 okay so like i know it never happens uh but i can actually set up the

t okay to be something small maybe 2 to the 40 okay if i assume like the cheat improver doesn't cannot do more than two to the 40 operations in in less than a second okay so this would actually correspond to this area of the of the table okay and of course we have like the offline settings saying you know what epsilon is something like 2 to the minus 10 okay but i don't care like i'm setting t to be huge 2 to the 128. so even if you run in offline mode like you have a lot of time okay you cannot give me some some false proof okay

any questions about this or suggestions for other settings okay so in the rest of the talk really just in the last few minutes i'm gonna try to describe the new construction we're not gonna see the poop i'm just gonna like say what the tricks are to uh to get this better security okay so our starting point is mikali's construction okay so think in your mind the same construction you have a pcp you hash the route and then you give the the openings of the of the locations that the verify wants to see we are actually going to set the random oracle to be log t

not log t over epsilon okay uh this is great because it makes the proof smaller okay right um the problem is as i said i gave you like explicit attacks telling you that you cannot do this okay so now we're actually gonna need to handle these attacks okay and this is what we do so we make four changes to mikali um we're chucking chopping the three we're doing domain separation permitting the proof and using robust pcps i'm gonna quickly say something about each one of them and i just want to say that all of these changes do not increase the

argument size okay so we reduce the argument sides by reducing this and these changes do not increase argument size we're going to see why each one of them adds slightly security okay but combined they actually give us the security that they want that we want and this they allow us to reduce the the output of the random overkill okay and get a reduced snog um and our analysis even works with salts okay i'm not gonna go into depth here but like if you wanna eventually show that the proof is also zero knowledge okay and this is a theoretical study group so i i guess this is the desired property and

then you need to allow like the over putting salts in the leaves and in our analysis it's fine with that also okay so like we don't lose the zero knowledge properties this is just slightly harder things to pull that i'm not gonna go into here okay so what do i mean by chopped three so we have the pcp we compute the root we apply this to get pcp randomness okay the query is for the pcp this is the mechanical structure what we're gonna do we're going to stop the milky tree at some layer okay we're going to chop this tree okay at some layer that i'm calling i star okay and we'll see what this layer is and now instead of a wood i don't have

the root of the three animal okay i stopped at some at some layer okay i completed one two three layers and i stopped possibly there's like more than two nodes here there could be many nodes here okay so i'm calling this the cap okay like the cap of the thing um now what does the pool will do he takes this cap he takes this cap he takes all the nodes in a cap he concatenates them to one like big string and he uses this as if it was the root he's gonna apply the random vocal to this huge string and get a pcp randomness and and then open the locations okay so he's gonna do the same just he doesn't apply

the random or equal to the root it applies it to the cap to the entire set of nodes in the cap okay i concatenate it together okay so if i start equals zero this is just me okay you go to the root and you do the root i i did nothing okay if i star equals log l log l meaning it's just this layer here it's just sending the entire pcp okay so this is very secure like this is very much secure just a huge a huge proof okay so as i start gets larger you actually get more and more security the security is higher but the argument size is is larger okay and this is not the

trade-off like in our favor okay we actually we get if you put instead of i star i star plus one you get slightly better security and like a huge uh increasement in argument size except for one special layer okay there's actually one special error and this is layer log q where we get much better security and we get the same argument size okay and um so i want to explain why so what is log q q is the number of queries to the pcp right and in in level low q so if this is like a low q okay in a binary tree this level

has q nodes and if any way the the honest pubert needs to open few locations for the pcp okay and for every location he sends all the nodes in the path okay then he's actually probably sending all this layer anyway okay because he's sending queries they're usually going to be quite randomly around this so maybe not all but let's say uh you know at least half okay so he's gonna send like almost the entire layer anyway so we're just saying send the entire layer and that's it okay it's it doesn't really increase the argument size okay it increases the root because the cap is like much larger in

the root but these things are anyway inside the authentication path okay and why do we get better security so if you remember the inversion attack we had before where the prover where this inversion attack actually proved that uh lambda has to be log t over just guessed the route in advance and then got the pcp and and and so on here they cannot guess the route in advance like what can he do he can try to guess the entire cap in advance but this is huge like this is like extremely small probability which you really can ignore okay

what he can do is he can try to guess like one node of this cap in advance if he guesses one node it gives him control over this part of the pcb not over the entire pcp so it gives it like some leverage okay but what we do and that's why we use a stronger pcp we can show that you know if he guesses one node he gets slightly leveraged over the pcp and we can handle this okay he cannot he cannot fool us okay the verifier is still gonna catch it okay maybe with slightly different probabilities okay but what he cannot do is like uh attack one node and once he succeeds

controls the entire visible okay this it cannot do he now needs to attack many many nodes to control the entire pct okay um so now change number two this is domain separation this is actually a very very easy thing to do and i actually advise everybody to do this so we're gonna theoretically speaking we're gonna use a different random overkill for each location in the tree okay and i just want to say that this is actually very easy to to achieve you just add a prefix okay to all locations okay so this is a random oracle so if i add like a prefix of alone you give then

i can like have my own random oracle where for every query x i just have elon yoga and then x okay so we're gonna do the same for every location i j and the three so if i'm hashing now layer i and no j in the three i just use this prefix i j okay why is this helpful this you don't have to write this in the proof and the very fact is the same so it's really like it has negligible effect on the system but it prevents you reusing inversions of collisions okay so if i go back if by chance the puber managed to attack let's say this node okay or find a collision or inversion if he wants to

now attack this node he has to start from scratch okay there's nothing that you can tell me about this part that tells you something about this part okay because they have different prefixes okay so it's like a new collision or a new inversion okay so this is now the new construction we're going to stop here at some layer i start and a we're gonna add the prefixes okay so we have all the prefixes so this is like node one one this is not one two one three this is two one and so on so all these prefixes go into the name of the uh of the node um the third thing is permuting the

proof um so this is a slightly more like a theoretical tool that we need i think in practice in many constructions you actually don't need this but um it could be the case that like the pcp is very wheeled okay because i want to have a construction that won't store any pcb okay like not a nice pct so it could be that the like entire interesting part of the pcp is like only here okay and here nothing happens actually and so i don't want like all the queries to be in one subtree of a node okay i want uh poover to have to attack this node and this node and this one and this in order to succeed okay so i want the queries to be spread out so either you

assume your pcp has like random queries which is like usually close to being the case okay anyway oh what you do is just you permit the proof okay so we assume we have like some random permutation over l i'm just going to assume it for simplicity here you can actually implement this with a random oracle and um what you're going to do instead of writing the pcp you're going to write the permuted version of the pcp so you're just switching the locations okay so location i of the pcp goes to some random location permutation of art and this permutation is shared between the the verifier and the proof okay and this really just has the effect that all the queries are random okay

because it's before in the pcp i actually was doing query like one two three now i'm doing queries pi of one prime two pi and three and these go to random location okay so this really goes back for why we do domain separations okay because the queries are going to be in different places and now he has to work harder and how therefore each place of this pcp that he wants to attack uh and the final change is we're gonna use some stronger notion of a pcp that's a robust pcp so this is actually a permitted robust pcp because we're permuting the proof yeah is there any question did they get the thing somebody asking

about the the timing um uh welcome you so i guess just quick admin note uh yeah 9 a.m pacific 6 p.m central european is typically when we run these but uh this is recorded thankfully so you can catch it later uh go ahead and continue okay um so we're gonna use some notion of a pcp like uh a robust pcp so just what is the intuition of robust pcp i'm not gonna like later go into the exact definition that we use um so uh a pcp

is a proof system where the prover sends a proof right he commits to the proof that's it he writes it on the table then the verifier chooses you know three locations and he looks at the pcp and he decides to accept the reject okay in a robust pcp we're gonna allow the approval the cheating pooper to change a few locations of the pcp after he sees the queries of the verifier okay so we cannot allow him to change all the locations that's just like a two strong creature to exist okay um but uh it's a robust recipe in the sense that he sends a pcp

the very first sends you know what i wanna see you know symbols in the locations 5 10 and 20. and then the cheating poover looks at this you can like let's say choose one location and change what is written in the pcp and then give these locations back to the benefit okay this is our bus bcp okay it's robust because the the local view of the verifier is not only not only going to be a rejecting view it's actually going to be far from rejecting okay the distance between uh the local view and accepting view is gonna be is gonna be large um

and we're gonna measure this distance a with blocks okay because actually when you think of the merkle tree every node uh so the nodes so these nodes of the of the cap they define some blocks because i can attack this one and then i can completely control all these nodes all of these nodes okay so this is going to be like the length of the block uh and then the distance we're gonna define the distance in terms of the blockwise distance okay so just a simple like uh example here think of these two strings okay what is the distance between them okay so all of these are the same all of these are the same

they only differ in this block so this is the same this is different okay and this is different but even though they differ in two locations the distance is one okay because they only differ in one block so only one block is is different um okay i'm gonna this is gonna take me too much time i'm gonna skip the the precise definition okay um so the final construction is a we're going to have a cap here we're going to chop the tree we're going to use domain separation we're going to permute the pcp and it's not going to be

just any standard physic it's going to be a robust tcp okay so these are the four changes for the construction and with these four changes we can really show that even though the random oracle was very small the cheating poover can actually find collisions and he can actually perform in belgians okay he's not committed to any single location here but the probability that he you know attacks some node meaning he finds the collisions over inversions um it's not ex extremely small but it's somewhat small but if he does it he it

gives the the teaching proverbial just a slight uh advantage okay because let's say he finds a collision here then yes these two locations he can open in two different ways okay so it's not committed to these locations but because the pcp is robust okay that's gonna be fine that's gonna be fine if he wants to change more locations he has to find another collision not only here but here and here and here okay and the probability of him finding let's say k collisions is like going exponentially down with k okay so we can really like balance out the probability that he gains power with

the amount of power that this gives him um so i'm not gonna go in the the actual proof i'm just gonna say it goes in two steps we show that if you have this magical permuted robust pcp okay and instead of the standard commitment you take this commitment with the top three domain separation and permutation what you get is the subquery smart and the second step is actually constructing these robust pcps and what we show is that these pcps are actually not so how to construct actually any pcp that you amplify by by doing parallel repetition

it has this robust property that we want okay so it's small showing like a property strong property that pcps have and not like it's not like constructing a new pcp from scratch um okay so i'm going to skip all this math here um yeah and i'm just going to conclude so uh we gave a small construction that achieves an argument size of log t over epsilon times locally the trivelo bound is low t over epsilon i mentioned that we have a new low bound for some familiar functions that

actually shows that this is tight but really the main major like open problem and let me be optimistic here and like wishing uh that there actually are snugs in the random oracle model that achieves size a log t over epsilon okay this would be like an amazing result both theoretical and and practical um okay that's it thanks awesome thanks elon um dude does anyone have any questions uh from the group if not i have a couple i guess i'll start um my i have a few

questions the first question is um when you use the term like weak commitment scheme like in in practical terms how am i to think about that is that like using 160 bit hash function versus a 256 bit like what's the what's the how do how do you how do i kind of consider that in the context of practical applications yeah excellent so um so this depends on exactly what like your t in epsilon okay should be but in general like if you want 128 bits of security you're going to set the the output of the hash to be actually at least 256 of actually

even even more than that okay if you want like the probability of finding collision so if you set it to 256 you get that the probability of finding collision if you allow me to run in time uh 2 to the 128 it's actually half okay and if you want the probability that i find the collision to be like a smaller like 2 to the minus 128 you actually have to set the the hash to be even even larger than that okay and uh and yeah what exactly what we're saying here is you can set you can set the you can set lambda to be smaller okay let's say you set it to be 256 okay but i can prove to you or even less

than 256. so the attacker has a probability of finding a collision it's not that he that he's gonna find it with probability one okay he has a probability of finding a collision uh but what i'm showing is that in our construction finding a collision is not that harmful okay so the the the scheme is gonna handle like collisions i don't want the attacker to find like a million collisions okay if he finds like a million collisions then he he he broke us but finding a million different collisions that's hard and that's why we use the domain separation okay so you cannot reuse collisions you cannot find

one and just reuse it a million times it has to like world walk form from scratch each time got it uh thanks second question for me is uh you mentioned kind of these four changes you made um are each of those to achieve this result are each of those four are they are they hard requirements or are you know i guess what's the relative contribution of each of those uh four changes to achieving this result yeah so like for the full analysis to hold you it's like the exact match of all four of them like each one pushes that velcro to a different corner and like you have to

have uh you know all four corners yeah exactly from a theoretical standpoint i get that i guess is in pri i'm curious actually maybe you know you don't have an opinion but in practical terms like you mentioned the permit you know permuting the pcp so certain pcps have certain properties but you know potentially could there be large families of the constructions that could be maybe made to work with three of the four um assumptions okay i don't know yeah so these are the four changes um so first let me say that practically speaking um so you know one two and three are changes that are extremely easy to

implement like they don't really cost anything especially one and two okay um so like one says actually just stop before okay so it's actually like even more efficient okay domain separation is just adding the ing okay so these are like extremely easy things i practically speaking i would say one and two of like the main components that you need okay uh this really prevents chopping the trip prevents like the the weakest spot of nikali which is the root okay so it really makes that part stronger and the domain separation like you you have to have it okay otherwise like one collision and that's it like

the attacker wins okay so these two simple things are mandatory permitting the proof i would say that you know it depends on what you're using if you're using like standout iops and the file protocol then the queries are like quite random okay so maybe this is not entirely uh necessary though uh and robust recipes then i would say it it might just be like uh um like the same iop the same protocol this is not exactly a change it would just be like maybe proving something slightly stronger about the pcp that you're already using okay and you can try to use our analysis

to like so i i would assume that i like fry already has like a lot of these properties cool um oh ariel wants to jump in and ask a question uh arielle do you want to say it or do you want me to read it you tell me i don't know where you are is there an attack showing one and two a only cannot get you down on the logs quality of the epsilon oh yeah [Music] so yeah there is so for for each one like any change you make i can show an attack

okay these are sometimes you you make changes only for the proof to walk okay uh and that's actually usually the case like at least with a theoretical paper right like okay i'm doing a construction because i know how to prove it okay it doesn't mean that what you're doing in construction is is necessary uh but here actually like these these changes come from like attacks that we identified so if you don't add the domain separation um okay so maybe this like okay so if i have like a binary pcb okay um and i don't have domain separation then

actually the attacker can find one collision okay between zero and one he can use it in all the leaves of the pcp and then he's like committed to nothing because he can open every location to either zero one okay if you have a pcp over a large alphabet okay which admittedly that is usually the case and he finds a collision then you know maybe he can open to two symbols and not one that maybe doesn't give him a lot of power and that's actually a great like uh way to go okay if you can prove that your pcp is is is strong okay has this stronger soundless notion that you know even though the attacker

can open to two locations and not one to two symbols in every location it doesn't give him like any advantage okay so that's possible but for a binary pcp like this you have to have it um okay and the chopped three is like it's just attack the inversion attack that i showed like if you don't chop the tree and you just let me have the root and you said this to be thought i'll just try to guess the old any other questions i think ariel that answered your question if it didn't just chime in the chat um

the last question that i had was you obviously used pcp throughout this slide deck i'm assuming you know for the person who watches this later or reads the paper they can just swap out pcp for iop if that's their preferred construction the bcs construction are they is there any is there anything to note if you choose to use an iop as opposed to pcp yeah that's a good question we actually like didn't do it in the paper okay it's it's quite hard to analyze as is but if you take like this construction you can see that like we did it on the tree so if you have an iop and then you have many rounds of these you have many trees and so we just do the same for every round and you would get the same

advantage okay like if this on me kali improved like 20 and now you use an iop so okay you have the advantage of iop and now this is by giving you 20 percent on on every round of the iop cool okay yeah awesome uh any other any other questions from folks uh folks in the audience some question here i'm actually wondering if we replace a the community being used for mercury for

polynomial commitment and then use batching what do you think of this support okay uh so yeah so if you replace the the miracle tree okay the way we do commitment with any other commitment scheme okay it could be a polynomial commitment scheme or vector commitment scheme or anything else um you might get actually a better construction okay so you might be able to open many locations of uh of the pcp without paying like a huge price okay so here we're paying a like lambda bits for every location of the pcp and we have like more or less lambda locations okay so

like playing lambda squared it's log t over epsilon squared okay so we're playing a lot and you can replace it with a different commitment uh but these different commitments like polynomial commitments they require different assumptions okay they require computational assumptions uh so under computational assumptions like uh other constructions like ghostly 16 and and for billionaire maps and another they can actually achieve something that's close to the lower bound okay so we can get this okay specifically like if you replace the commitment scheme with something smarter but it's not in the random local model okay so it has some different assumption

maybe a setup maybe not maybe post quantum maybe not okay and the depends on efficiency it's not like a pure construction in the random local model yeah so this construction is it gives you information theoretic security in the random world is that right yeah so in the random local model this is just secure period like no matter what future brings us okay like even if peak was empty and crypto dies this construction is secure in the random oracle model okay if you actually want to implement this then you like a plug-in chat to 56 but then you have like one single assumption that there is a cryptographic hash function and you can of course like you

know replace traffic to 256 with some other function or in 100 years from today some other functions that will come up okay that's the only thing you have to do we're not relying like on a specific you know algebraic assumption and on groups or something like that cool um well elon this was a great a great talk really really enjoyed the presentation and thank you very much for uh for taking the time to speak with us thank you guys thank you for having me