ZK HACK - SNARKs from Hash Functions - Nick Spooner

Transcript

hey nick hi welcome good thanks so nick is going to be talking about how to do snarks from hash functions so i'm very curious to hear this take it away nick all right great hi yeah thanks anna uh my name is nick i'm uh postal boston university and i'm gonna be uh moving to the university of work uh next year um and i'm gonna be talking about uh sort of a class of uh of snarks um which are built from probabilistic proofs like what i talked about and then the the cryptographic ingredient is just uh hash functions like collision-relational hash functions um so let's sort of go into this a little bit deeper uh so the first ever

construction of snarks um was from it was built on top of these these pcp objects that ale talked about um and uh actually sort of going a little bit even so even earlier back in history um there is a sorry there is a succinct uh interactive argument for np so this was sort of the original uh so it's like a snark but without the n right um this was sort of the original six-inch argument construction um and it has sort of quite a simple structure

so once you so you have approved verifier um the approver is going to invoke the prover of a pcp system right so it generates some pcp uh then it commits to the pcp using the the collision hash function in a merkle tree form so this is sort of a just a vector commitment um uh the advantage of committing to the pcb like this is that you can open as uh as we all know the militaries have have local openings so you can open individual positions in the pcp string um without having to sort of communicate the entire pcp string

um so the proofer is going to send the route to the verifier um the verifier is going to choose some randomness for the pcp um and then the approver is going to then compute uh the the sort of openings of the the positions that the verify just asked for right so you use the pcb randomness to figure out what the query should be to the pcb and then uh then you compute the positions and you send them back the the verifier is going to check the openings um and then he will check that the pcp verifier so the pcp sort of decision predicate would accept on these pcp answers and the the choice of randomness

that he picked um so the way that this proof system is working is that you know and ale as ali pointed out like a pcp like the pcp model is not the same as the like the snog model right so you can't just it's not secure to just ask the approver for pcp queries but if you have some way to force the prover to sort of commit to the pcp string before you asking the queries then this becomes secure and so uh this is the the what this uh what this interactive protocol does is it forces the prover to commit to the pcp string using cryptography um so uh so that's the sort of the structure of

the scheme and i want to just like look briefly at the the efficiency parameters um so you start with the pcp parameters and you can derive so very easily from this the efficiency parameters of the scheme um so uh so the relevant parameters for pcp is the soundness of pcp is this is the soundness in the pcp model right so for a pcp verifier the proof length is just the length of the string the alphabet is the like what is uh each symbol in the string needs to be needs to be picked from this alphabet and q is the number of queries that the verifier is allowed to make um so the soundness is pretty direct so

basically it's the probability that you that you can break the pcp right by sending out a malformed pcb string plus the probability that you can break the collision doesn't hash function um so this this is sort of a straightforward uh analysis um the uh proving time is very strongly related to the pcp proving time basically you you produce the pcp and then you just need to do this hashing right so so the extra cost is just in like hashing the pcp which is roughly linear in the size of the pcp the verification cost is the cost of verifying of the original pcp verifier uh plus the cost of checking all of these

authentication paths which for merkle tree is uh it's like basically you apply that the hash function uh q times log l times so you have like q authentication paths and each one of them is like log l so you need to um so that the total cost is like t times q times log out um and finally the communication uh is like the number of queries multiplied by uh the like the the size of a symbol um plus the size of all the authentication paths which is about uh cap and times log l where look where kappa is the security parameter so it's like the size of the output of the hash function um so notice that these uh for reasonable pcp parameters are small

overheads so the the proving time of the pcp is certainly at least l because it needs to produce this this string of like the hell um and so in in in practice sort of the this is uh the extra time for hashing is uh is not very much compared to uh just producing the pcp string um the verification time so you can think about q as being something that is sort of poly logarithmic um and l is polynomial so log l is logarithmic and so this is really like some polylog in the uh in the input size times um times uh the time to run the hash function so

really like the the main costs here are in producing and verifying the pcp um the communication if you like take a reasonable pcp is going to be uh some polynomial fixed polynomial security parameter basically so it's like poly kappa and logo um okay so so this is a succinct argument like we have built a succinct argument um you know obviously we needed to assume a pcp but once you have that then actually building this succinct interactive argument is very easy um so then how do we uh how do we then obtain a non-interactive argument well it was already sort of pointed out in the chat that there is a general sort of method

for going from public coin interactive protocols to non-interactive protocols which is called fiat chemists it's the fiat chemical transformation and what you do is you just take the protocol on the previous slide and you apply the feature in the transformation so you as before you generate the proof that the pcp proof now this little box here where we're uh modeling it as a random article so this is a uniformly random function um and uh rather than sending the route to the verifier because this would involve some interaction what you do is that you use the route or you pass the route into the random article to

derive the randomness for the pcp um then the this gives you the the pcb randomness you use that generate the queries and then the proof is just the route and then all of the authentication paths so like it's really the the same thing as before um it's just that rather than sending rather than receiving the randomness from the verifier we derived it from the root using the random article so that's the proof and then the verifier does exactly the same checks as before um along with this additional check that kind of the the uh the randomness was correctly derived by applying the oracle to the root um so what is the soundness in this in this case

um so we still have this uh sort of cost of breaking the collisions hash function and actually uh if your adversary is making t queries to the random article then you can bound this cost with this explicit expression it's like t squared times uh two to the minus uh kappa where cap is the security parameter um however we we do have a slightly different expression for the on the pcp side so before we had just epsilon pcp right you could you sort of got an opportunity to attack the pcb once uh here because the thing is non-interactive the prover can attack the pcp sort of as many times as he wants um so he can try different pcp strings and he can basically like try and cause uh the randomness to be a bad choice of

randomness for that pcp um and this corresponds to a factor t blow up in the in the soundless era so if you want to obtain the same soundness as in the interactive setting then you need to actually like improve the soundness of your pcp which in practice means that the pcp is going to be less efficient all right um so this was sort of a little tour of pcb based snugs let's uh take a take a step back and think about uh what the properties are that they have um so the sort of the the first bad property that you might think of is that you know all of the stuff is in the random oracle model and some like very smart cryptographers have proven that random articles don't exist so like there are constructions in the

random oracle model that are like not secure with any concrete hash function um thankfully this doesn't really bother us very much because uh no practical like reasonable construction that wasn't designed explicitly to break the random article model has been broken uh when you like plug in a sufficiently strong hash function um you need to be careful that your hash function is sort of you know looks like a random article it's very unstructured um but otherwise uh you know this seems to be like a generally secure way of designing protocols should also mention that um there are results showing that if you want to have snarks at all then you need to make some kind of funky assumption um

and uh random articles are maybe a mild mildly funky assumption um so the other thing about random articles is that they are it's a sort of robust model so let's say that i you know someone breaks like sha or something like that right like if someone finds a collision in char uh that doesn't mean that we have to throw away all snob constructions uh in the random oracle model we just need to find a new hash function that you know looks more like a random oracle than charters right so there is sort of this this uh this robustness like it's uh like these are constructions that continue to be secure with some hash function

assuming that some strong enough hash function exists um the other thing that you get is that the uh the hash functions are relatively lightweight cryptography uh you don't need to um you don't need to sort of do a lot of computation on top of the the pcp in order to um in order to like do the crypto part i like to commit to the pcp is very cheap um they're also automatically public coin because uh essentially the the choice of system parameters is just the choice of hash function um which in practice we don't even like choose we just like fix it to be some like public well-known hash function um

and uh these these snogs are actually post quantum i'll talk a bit more about that later um the main problem here is the pcps are really expensive so like as as ale said um you know they've gone down from being sort of galactic algorithms that you can't run but a technically polynomial time to uh being prohibitively expensive so like tens of megabytes for the resulting stock uh so what do we do and uh ali already gave gave us a hint in his talk we're going to try and build snarks from from iops instead um why because known iops are more efficient than known pcps um

and the idea is quite straightforward right so uh what you do is you uh so what you do is you you take this uh this killian for pcps protocol that we applied for html to and you so generalize it to a killian for iops protocol so you just uh you know you you do the the same protocol like this killian protocol but you do it for many rounds like as many rounds as you have uh oracle strings um and then you apply for your chimney to make it into an interactive protocol so you don't do you don't end up having to pay really for this interaction um so let's uh take a look so what that

actually looks like um so now we have an iop proof instead of a pcb approver uh and the iop proof is going to generate the first uh oracle message in the iop he'll then hash it pass it into the random oracle to generate the random like first verifier message the first verify randomness in the iop you feed that into the iop approver and then he spits out another uh oracle message for the iop um which you then plug into the uh to the random article and you can do this for as many rounds as you have in the iop eventually uh after this the end of this chain um and i should say that the previous hash gets plugged into the to

the oracle as well in order to uh in order to make sure that these hashes are like in a chain you can't do anything anything strange by reordering the rounds um at the end of this chain you you uh plug this the the resulting hash value into the uh query algorithm this is the verifies kind of query randomness um and then you do exactly the same thing as in uh pcp you you like look at all the queries that the verifier is going to make and you open um each of the strings at the appropriate query position so there are now multiple roots and relative to each route you have different authentication parts for

the different courses um so the verifier is then sort of analogous to the pcp verifier the difference here is that you know now you need to check this entire chain of hashes so you need to check that like the hash of the first root is uh if you hash the first root and then you hash the second root with that hash and so on and so forth then you get the correct um like uh then then you get the correct randomnesses that were derived by the approver um and you plug this into the decision algorithm along with the the answers that the prover gave you um

and uh and output and accept if the uh iop verifier accepts so really this is like uh like conceptually very similar to the protocol from pcps um and what you get out really is the same thing like it's a it's still a um an interactive sorry it's still a a snark um so you sort of you you got all of this interaction um uh you like introduce all of this interaction in order to try and make things more efficient and then you got rid of it all by by like using the random article to write the randomness by using the html okay um

so uh so you know it was proved proven in 2016 this construction works um and so you get a uh snog there's you should get secure in the random oracle model the snow costs are basically the same as before so if you like the iop parameter iop parameters are similar to pcb parameters except that you just sum over all of the rounds um and the proving time is uh is going to be uh the same as the iop proving time plus some small overhead the very same for the verification time and the argument size is still small um so there we go uh and so in in the end what

you get is that that you can sort of replace pcps with iops in the random market mode and you will still get knocks um you also uh this transformation preserves zero knowledge improve knowledge so all of these technical properties still hold you and you end up with the z case now all right um so what i didn't touch on in the last slide which i talked about before is soundness and the reason is that soundless is actually somewhat complicated in these in these multi-round protocols um so the quantity that is important here is what's called state restoration soundness which is something that's quite different to interactive status in many settings

and this is actually sort of a statement that applies also to like any fear shamir of of any protocol so not not just you know the most general case of iops but like all uh interactive protocols you have to worry about this um and state restoration soundness is is the following thing so uh so if i have an interactive protocol between approver and a verify um then in the interactive setting you know i have to run through sort of uh an interaction in order right so i i do like uh i send a message and then the verify says we're running this and there's a message verify sends me randomness and so on and like when i get to the end if the verifier rejects then i'm done right as the approval rate i

have lost um in non-interactive settings uh i can like so long as i am able to to simulate the verifier in my head then uh i can certainly try and like produce another transcript right so i can just sort of run through the protocol again and uh and like re-simulate the verifier and if i happen to find an accepting transcript right then then i'm good um but state restoration soundness is is more than that um so what you can also do is you can take say the first uh transcript that you ran and you can pick some prefix of it like this m1 r1 and then you can resample the suffix so

you can put in a different message and get a new randomness a new uniform randomness um and let's say that you know that one doesn't accept either um you can also you know go to some other transcript and pick like pick another transcript and uh and use that prefix instead so like maybe i choose the second transcript and then i get uh like a another related transcript where the the prefix is the same and the the suffix is different so i can play this kind of uh this kind of weird game where i'm trying to where i'm basically able to explore the tree of transcripts in this way um and all i have to do is the prover is to find any accepting transcript in in this like via this method

um and uh this can actually give you like quite different behavior to the standard interactive soundness so it's related to the standard soundness by basically a factor of t to the k where t is the number of random oracle queries or the number of times that you can sort of do this uh this this like resampling of the transcript and this is actually tight for some protocols so um you know that you can you can write down protocols where uh this uh where this this sort of inequality actually is actually tight and equality and this this is really bad because if k is somewhat large like even sort of logarithmic um

then t to the k is going to be really huge um and it's actually going to be a significant security loss um thankfully most widely used protocols have good state restoration sounds so things like you know fry and bulletproofs and all kinds of like your favorite log round protocol some check like all of these actually have good state restoration soundness and they don't succumb to this but it is still important to to consider this whenever you're designing protocols um one like important example that came up recently is actually the parallel repetition of a sigma protocol um is uh like like a k-round sigma protocol i guess like uh it does not have good state ratio state

restoration soundness which is sort of surprising um so it's important to think about this um but you don't have to sort of worry about it for existing protocols because because essentially all protocols that we use in practice uh have good stake restoration sounds okay um so uh what does that say about iop based snogs basically the the you know the the as before random oracles don't exist that's a shame um all of the good stuff stays the same so we haven't really lost anything uh in terms of the the sort of nice properties of pcp-based maps but we no longer have this issue that pcbs are expensive um

we can we can sort of move from pcps to iops which which are much more efficient um okay uh so i'm gonna sort of uh go through a little bit the the sort of history of iop based snogs uh which is not very long um basically the the way that this has gone is uh they we've been so pushing to improve the asymptotics of iop protocols um and this inspires ways to sort of improve the concrete parameters of iop protocols which you know is sort of a self-reinforcing cycle like it's it's like exploring the space of iops um and

as a result of this uh of this research effort you end up with improved iop based knocks um so uh there are a few uh sort of families of constructions that that exist um the original one is uh is this uh secure computational integrity thing uh succinct computation integrity sci um which uh which was based on sort of pcps i mean it's like it's it's almost a pcp it's kind of a pcp where you uh like break it up into two rounds but basically a pcp um and this gave you something which was like uh you know a few tens of megabytes uh which is maybe a little bit better

than than you can do with a plain pcp um and there was this legero uh result which is sort of uh the first kind of um like it's a it's a good concrete improvement uh it's a it's a square root sized sized argument where basically you um like arrange your your witness into a matrix and then you and then you do this kind of folding of a of interleaved read solomon codes um and this gets you down to you know a few megabytes um then more recently there's sort of a couple of different uh types of construction that get you to 100 kilobytes uh so there are these these

stocks of stockwere um which are based on the uh these iops for um reed solomon with uh linear size and logarithmic query complexity and this uh is sort of a snark for for machines um and then uh sort of following not following on from that uh abruptly at the same time there was uh the aurora protocol which is uh based on a um univariate version of the subject protocol uh this one is for four circuits or r1cs um and so this is sort of where we are as of 2018 and we haven't really gotten much further than this uh and so there's a natural question of

like can we do better can we like go to 10 kilobytes or one kilobyte or less than a kilobyte so uh um one second um okay so so this is sort of a natural question like oh you know where like where do we go from here um and there are some sort of uh like there are some sort of asymptotic uh limitations which which uh which have put barriers on how far we

can go um so uh if you like restrict to looking at uh protocols based on on sort of pcps and iops that are compiled using macally or bcs um then you can look at kind of the asymptotic parameters and the so the best practical parameters like the best things you would actually want to run on a computer um have the these asymptotics basically linear proof length um like linear alphabet size and roughly kappa times log n so kappa is the security parameter here kappa times log n queries um and if you compute the argument size you get this kappa squared

log squared n um which you know you can think of as being bounded by capper to the fourth power um uh if you are willing to sort of uh go to the realm of like good asymptotics but like kind of um impractical uh as an implementation um then you can do a little bit better so you can shave off a log in um by basically you're using a different low degree test uh and then there is a question of uh so that this these two are sort of the what we know so far and then there was an open question so can you basically go from

kappa queries to kappa over log n queries um and this is called the sliding scale conjecture uh and it's it is open it would get you down to an argument size of of like something like kappa squared um so if you got there then you would be able to hopefully get arguments of size that are less than a kilobyte um which is uh which is pretty great um the and actually this is sort of the best that you can hope for uh so you can show that if you can go below this uh sort of kappa over log n queries then you would break some like uh so very reasonable complexity

theoretical conjecture so uh this is sort of the best that we believe that you can do uh in particular the argument size needs to be basically kappa square um it turns out that actually if you move away from macaulay and you you sort of uh you know optimize things a lot then you can do a little bit better than kappa squared uh but it's it's sort of a parameterized thing a bit subtle um basically this this kappa squared is kind of the the limit um still i mean it's still sort of out of reach and it would be great if we could if we could get there using efficient constructions um but uh but there is sort of an asymptotic limit that you hit okay

uh so the last thing i'm going to talk about um is post quantum security so uh i think i i have a few minutes left so um postmodern security is you know something that's very important these days a lot of people are thinking about it you know people are building quantum computers um even president trump was interested in quantum computers um and nist has been thinking about post-quantum cryptography for a very long time there have been uh you know there's already been uh like standardization competitions and this is still still ongoing they're evaluating uh

signature schemes and things like that um so you know the postpartum security is a big deal um and uh if you don't believe nist about this uh then uh you can also take a look at this uh uh screenshot from from the show a netflix show altered carbon which is set in the year 2141 um and you can see that uh people are buying things uh in bitcoin and zcash um and if they are going to be using zcash then you would hope uh that you know we would we would have made it post quantum by that um probably in the year 20 20 141 there will be quantum computers

um so the problem that we have is that all sort of discrete logarithm based constructions are insecure against quantum adversaries and this includes of most you know things like growth 16 and and basically everything the producer will be talking about um and so uh this sort of means that they have kind of a uh an expiration date right like at some point um quantum computers will exist and they will be you know good enough to break cryptography and then all of our stocks will be um thankfully everything presented in this talk is post quantum secure um and i want to sort of elaborate on that a little bit

um so back in uh 2018 uh a very similar talk to this was given uh where there was this caveat that that sort of everything is like plausibly post quantum so we don't know of any attack right in the case of discrete log schemes like shaw's algorithm gives you an attack here we only have hash functions so we didn't know of any attacks um since then we've actually come a long way in terms of the provable security so we can prove that all of these schemes that many of these schemes are post quantum so i'll give you just a couple of results so firstly this um bcs transformation from io knox

and also the macaulay transformation both of these are secure in what's called the quantum random oracle model which is the natural quantum analog of the random oracle model in particular it models superposition access to a hash function which a quantum computer would have um the caveat here is that we only know how to show uh soundness from from a sort of stronger property of the iop called round by round soundness versus uh status results in the classical setting but thankfully again most protocols satisfy round by round soundness so everything's fine um the more recent result is that the interactive protocol is the that i presented at the beginning this killian interactive protocol uh is also post

quantum secure assuming uh the quantum hundreds of learning with errors so this is like the plain non-random oracle model uh this is really hard to show so the problem here is that uh the classical proof is by rewinding so you sort of take in that take your adversary and you like run him on many different choices of challenge this is how you prove many interactive protocols are secure and then the quantum setting rewinding doesn't work basically because of uh the no cloning theorem because the non-clonability of quantum states um and so what do you do it turns out there's a um there's like uh you know you can do a lot of work and eventually you you can

uh you can extend the rewinding the this uh rewinding technique to the quantum setting um there is still a lot of open stuff um so like you know we haven't for example shown iops for killian is secure in the quantum setting uh sorry killian for iop is here in the quantum setting uh we don't know how to prove security of killian from crhf's only qlwe uh we don't know uh so there are these like lattice bulletproof protocols that sort of uh like it's like bulletproof based on lattices and these could be post quantum but we don't know like there's a lot of stuff that is still open uh so you know even though we've come a long way there

is a lot of progress to still be made and i i'm currently working on this and i would love to talk to people if they're interested in that um so just to conclude um so hashtags hash based knocks are sort of something that's really well mapped out um we have a bunch of constructions uh you know from pcps and from iops uh and this also this is this sort of more exotic construction um we understand their security very well so we have you know good security in the random oracle model and the quantum mechanical model that's sort of very like precisely understood um and robust in the sense that you know even if my hash function is broken

tomorrow i can just pick a new one and then and then i'm i'm you know uh ready to go again um on the other hand we have some sort of we we understand the the the structure of these things so we understand actually how to go from a snog back to an iop we know how to build a snog snog from an iop and then we know how to build an iop from a snog so really we we have like a good characterization of of how these things work which actually leads us to lower bounds which are pretty close to being tight um so you know this this is great like we sort of we understand everything

um in this setting really well but it also means that kind of we're a bit stuck like we we have these lower bounds we have these barriers and like it seems like there's not really much further we can go um so in the next talk patricia is going to be talking about um so searching for treasury and uncharted waters he's going to be talking about leaving uh the sort of cozy world of hash-based snarks that we understand using more cryptography to obtain proof systems that may be where the security is a little bit less well understood but the efficiency and other properties can be a lot better so thank you very much um

thank you thank you so much nick for the talk um