ZK8: New Directions in ZK hashing - Dmitry Khovratovich - Ethereum Foundation

Transcript

foreign they told me to stay close to the microphone as close as possible the problem is I like to like walk around like Chrome the auditorium during the during the talk so something will not be recorded that's okay yeah that's possible to grab a mic yes that's a cool trick actually uh might grab it right now just just do it I'm doing it okay it's much better much better so great to see everyone uh

thank you for coming for for the last very last is it very last probably very last talk of of today and it's of course it's going to be great talk it will be about hashing so probably have heard today about hashing a little bit but this will be a completely different talk so I did kind of the stock beforehand and it was like too technical like a lot of foremost everywhere like from the from the title foremost in the title that's horrible and now they're purely like entertaining talks because it's like we are almost into the tonight right everyone is thinking about the beer and then up close Beer Garden close by so this will be an entertaining stuff

but also you'll I'll try to teach you some kind of new and funny things about ziki hashing that you may not know yet about so let's actually joint work so my biggest mistake that I forgot to put my co-authors into the list I'm sorry quarters if you hear me I know everyone so Lorenzo Christian Marcus Roman yeah and Reinhardt yeah they also all helped me and GP at the last stage also to develop this new functions so why new directions in ziki hash and build because new directions to cryptography everyone wants to have a fancy title so I will talk about some new stuff that has happened in hash function design

thanks to Fantastic new developments in zero knowledge argument systems so with the help of our close friends from zero knowledge team we are able to design much cooler functions so why is that in order to explain uh the story I have to go a little bit to the Past two centuries ago this our story starts with a poor Gardener Joseph maniga who worked in a poor French country in France at tularis Gardens near as small Palace at that part called Louver

uh Stephanie here was tasked with a tedious task he had to move orange trees back and forth back and forth because orange trees were like of great value to the country into the palace and unfortunately there the pods were orange trees are stored were quite too fragile they broke and broke and broke they had to dispose of the trees that's not about trees it's about pots so that one year decided to reinforce a pod with iron bars and he used this circle structure so he put concrete in

it and he put iron bars at certain distance and this made the construction far more durable it withstood climate changes and kind of clumsy movings from outside to inside and also some kids playing with orange trees all this stuff uh this invention was later presented at vortexpa 67 the universal acclaim people figured out that it's possible not only to use reinforced concrete to reinforce orange tree ports but also apple tree ports or various like Cherry tripods so improve like this invention was used

everywhere and of course it was later called reinforced concrete which by a chance also the name of our new hash function so what should you remember from this presentation if you have to go right now if you have to go right now so we uh I designed a new function which is of course Ziggy friendly uh and all these previous functions are terribly slow you might notice already but with lookup arguments we can build a much much better hash function which kind of surpasses everything that you have known before that's it now uh to the details yes of course the reinforce concrete um

so hash functions up until very recently they were used in tons of schemes and protocols signatures blind signatures aggregated signatures multi-signatures commitments blank commitments all this sort of things including fat Shamir and up to very recently just normal hash functions were okay like you can use charity 56 everywhere you can use it which has chapter 56 if you not to give a shot if this is usual 512 or you shot three or you shot three 512 for you shot three five twelve truncated to 256. that was all not a problem they were not even a bottleneck anywhere so people were designing like faster and faster Blake 2 black 2B blake2s black three black four

black 69 but yeah for what reason they are never a bottleneck until we started using them in zero knowledge with zero knowledge everything becomes a bottleneck in particular hash functions because uh because what for example everyone knows about zcash so now everything is okay with zcash but this is about sad dark times of zcash like six or maybe even seven years ago so how zcash works is a private cryptocurrency thing so in zikash all coins are stored in the Merkel tree and you kind of is there a laser here no I'll use my finger sorry

I don't know where it's uh let's work with me um okay so basically you know if you have a coin you know a secret and in order to spend the coin anonymously you have to prove that you know a secret and of one leaf in a tree so anonymity comes from the fact that you know a leaf in a tree and you don't show which one first second third fourth so anonymity comes from this original tree was built on chapter 56 because it's really really great hash function even though it was designed by NSA but still so far so good no one has broken it yet

and approve that I can spend my coin it took like 40 seconds to generate and of course that was inconvenient so imagine you're like you're paying for a beard now you say oh well I have to pay with my zika say the 40 seconds that's untolderable well I probably use something less Anonymous so everyone will know that I've paid for like ugly beer and well this complete break of privacy that was horrible they have improved significantly since then they have now used much better hash and everyone is now able to pay with beer for beer with Z cash uh some another story has also happened with the fractal protocol fractal protocol is fantastic stuff it's

fantastic it's fantastic 70 pages of stuff like and it's recursive it's really nice to read I I I've read it well not entirely but some the the stuff it's it's really cool it it's it's not difficult to read and the nice thing is uh they're using uh you kind of prove that you have a proof that you have a proof you know all this recursive things and in order to to prove that you have a proof you can first commit to something then you open something you commit to something then you open something and you do it in Merkel trees because they they don't want to use all this offense pairing based schemes that's all complicated um and in order to construct local trees

they decided to use some hash function which hash function shutter 56 won't work ketchup won't work so they decide to use Poseidon so what do I think about using Poseidon as a miracle tree if it's if a hash function that they're partially designed is it good no why because they said well we tried Poseidon and for prover it took 99 of time to generate the entire tree with Poseidon and then they they did kind of dirt optimizations to employ it really dark matters and they managed to cut it down to 90 so still huge amounts even with Poseidon and yeah that when I looked at it I was very sad they said why not like employing our team we at that time we

had no money no work we had to design a new hash function we could work for food foreign but yeah well unfortunately this paper uh we didn't notice the paper at the time of publication so after we found it it was already too late so uh it's of course better it's of course possible to find the hash function that that makes this girl happy so hash function sends your knowledge there are like two kind of nice usages so first of all of course inside Miracle trees but also in like in in smaller tiny things like commitments but like in in big applications in Merkle trees so in accumulators if you want to do set

membership with Merkle trees we have seen today that in after using caulk this this application is somehow kind of crossed because well calc is much better uh regarding accumulate if you prove multiple things if you're a single thing and is still quite good so Merkel 3 is accumulator and the second one is again if you do this commit reveal things in Fry so all this fractal case it boils down to to this one so used here and there and everywhere uh actually in in many places and we're gonna we wanted to design hash function that would work nicely here with the next here will work nicely everywhere else how we did that

uh yeah first we how how problems are solved first we looked into the requirements the requirements the diversity that you start with so we we like you know like how to how to choose a laptop laptop must be light and lightweight and it must have like huge battery capacity well unfortunately these things really go together so the same pretty much same thing here so you have like what we need for music have function it must be very fast close to like mainstream hash functions it must be very secure and secure it does mean that you just produce a security proof and that's it in a hash function case it's not it's not enough to have just security proof you have to

publish a hash function declare some boundaries wait till until people start breaking it they started breaking some reduced versions some modified constants and you come out and say well you guys you have broken the wrong version now try to break right version you reject submissions to some proper conference because they've broken right version or maybe you reject submission status that break the right version but you think it's not yet time to publish such result so it's it's all kind of it's it's so complicated third party cryptanalysis it's a subtle thing and yeah in addition to this you have to use this uh it must be small in circuits

so like hash function like really powerful and fast smaller Circle in order to minimize proverb time so like these two things were not enough that the third things really like a killer requirement okay let's let's try to see what we have here possibly so designs designs flourish so this all started with Mimsy in 2016 and they were like a chain of hash functions that arise from memes there were Friday there was Poseidon rescue reinforced concrete that we're talking about here some other stuff I don't know how they are pronounced uh so you see there's also a problem in hash function naming that the the names

are not kind of self-talent you have to always explain why why do you call a function this way for example the guys they decided to call the function Neptune well why do you call it Neptune because you have already Poseidon and you have many projects named Neptune they kind of foreign what happens if you use a hash function Neptune and the project name Neptune what happens no one knows there's another chain of designs uh based on the hardness of disk lock analytic curves and this started with the challenge function 91 now we have Pederson and sensimilla a very nice designs also small in circuits and provably secure before you have a quantum computer but we'll never

have a quantum computer so they're secure and yeah all this family of functions they are designed there are several problems with that first of all some of them get broken the more the better so some of Mimsy something is broken Friday was totally broken Grendel was broken a little bit yes so with this discrete blockage function the problem is it's pretty much resistance is not that good let's call it broken but yeah in this case we just called okay we pretty much resistance so so far okay but still uh some analysis is present but it's it's better to have more analysis and we kind of afraid because all these hash functions they designed on new

principles and it takes quite some time to understand these principles then it takes more time to develop new attacks based on this principles and worse enough uh you have to battle algebraic attacks and algebraic attacks is is really nightmare that you you you can't just estimate the complexity of all these attacks because they are complicated this government-based exercise Ferdinand is here is great expert on how this attacks work and he must he can confirm that estimating complexity of what stack is not is non-trivial so you you can compute the wrong number of number of rounds you need in your function so

[Music] the problem also in the design is that in order to withstand such attacks your hash function must be on one hand of high algebraic degree on the other hand it should be reducible to System of small degree equations and this makes us think that if we encode this as a circuit if we have to have something of high degree then we have to have many multiplications if we have to have many multiplications that our functions will be big in circuits and this this like uh negative feedback and we don't know how to break out of this Loop so

the problem is yes we can just make it fast and secure and you can you can see this on this um if we consider uh older proof systems like growth 16 and if we compare proven time measured in r1cs constraints with speed you can see like the like two families of functions so one of them is this algebraic hash functions you see that like kind of super slow because this is like the the speed this access is the speed on CPU when you just compute the hash function and this one is the number of constraints so in the case of Chateau and Blake you have like tens of thousands of constraints but they're super fast here we have few

constraints but they're super slow how to uh choose between super slow but small and super fast but big it's unclear so have to design something new and we were looking and looking and looking for something that is like Fast Ziggy friendly and high algebraic degree and like failed thousands of times really before we met with uh lookup arguments and here come the contributions that will describe a hash function for 256-bit Fields they'll be also designed for 64-bit fields and for smaller domains as well so lookup arguments is really really

cool trick so we have seen today already a talk about caulk we have Halo 2 lookup argument we have lookup lookup argument they allow proving that some entry which is private entry or not not necessarily private entry isn't some table not too big table and this gives us an additional uh element of a circuit so in circuit we can prove not only that we have multiplied the things we got the third one but we also can prove that something is looked up in a table and here's the result but how to use it how to use it in hash function design how to use this to look up things properly so that you have something working and secure

the problem is that lookups must be in small tables well rather small tables but in circuits you work with Big Field elements so clear problem is how to come from Big Field elements to smaller tables so well natural ways try to come decompose somehow like with the native computer arithmetic when you have like 32-bit words it's easy to decompose into into bytes 32-bit word is four bytes all the four bytes are out a little bit worse so this mapping is bijective is easy to decompose and compose back but in fields in particular in Prime Fields it's all

much more difficult so suppose you have decomposed into 16 bits then you looked it up in some table and then you get 16-bit as a result but how do you compose it back how do you compose this limbs of six 16-bit limbs so that you can get a field element remember you must have no collisions you must have no overflows of this field element so how how to ensure that you still get a fitted element after you compose them back so just the lookup argument is not sufficient but you have to do something smart here and yeah here's a simple example that's the main technical slide of the of the talk

so suppose you have a prime number 769. and 769 how to decompose into about two two parts how to decompose it well you can see that like 769 it uh if you divide it by 30 you get 25 and 19 as a remainder so what kind of hands is that you can divide by 30 and get something from 0 to 24 and you can take a remainder uh module 13 that you get from something from 0 to 29. but of course if you if you notice that this not all the things are possible right so if you if you're like in for example 768 then this will

be 24 but this if this is 24 this cannot be arbitrary because this prime number is not a product of this two so this must be something smaller so you have to be smart and the idea is that you can 24 you declare a special case so 24 you don't do anything with 24 it's it's just a standpoint and it's a fixed Point sorry you somehow permute from 0 to 23 but 24 you keep with this guys what is dangerous it's dangerous to overflow it's dangerous to go beyond this 19. 18 actually so you can your key from modifying from

0 to 19 a little bit but if you are in the higher part it must be a fixed point so some parts a fixed Point some are not fixed points so this lookup is um and the kind of exercise so if you if you like add them together the same way you divide it then there's no overflow like simple exercise why why it doesn't overflow the nice thing here is that uh this if you implement this if you think of this as a polynomial it has pretty much High degree in particular over this Big Field because you're like one of

this fixed Point there's also fixed points this this has a high degree in political when you compose them back this kind of integer operations that makes the entire thing very a high degree and this solves our problem this solves the problem that we need to get high degree to battle this algebraic attacks and with of course with bigger Fields it's pretty much the same but more complicated so The Big Field to what you do you you take a prime you divide it not to two bins but in bigger number 27 bins you do this smart substitutions and so on the thing is all together you need like 43 lookups not 27 lookups because you

also have to take care of this uh edge cases basically this edge cases they add lookups into into your but as a result the algebraic degree is a super cool degree so you don't not bother with algebraic analysis anymore so it doesn't matter if you are mistaken by like a factor of two or three here right and this operation there's decomposition and composition back is called bars the bars they are in force concrete and they reinforce our hash function there are some also standards tricks of symmetric people they can't just take and use bars you have to they

have to wrap it with some extra stuff here confusion diffusion and so this old stuff getting back to Shannon so to prevent some attacks and blah blah blah So eventually if the the full scheme has more operation than this but the cool thing here is that the structure is very much it very much resembles some older hash function design and also block Cipher design so that we just can't we just can take the old security analysis and to reuse it it's not like we take grubner basis analysis but we take some old crypto analysis from 2000 zeros from for even from 90s really

from there before internet and apply to our hash function and it works beautifully so no need to rely on government bases anymore performance performance is is really cool here so if we compare if we look into proof systems where lookups are possible then well we can't just measure any more the proof time as the number of constraints because with custom Gates and arbitrary degree and a large number of columns so the the best thing we were able to compute the so-called area degree product so for plump like systems you

you take the area is the size of a matrix of your weakness and you multiply by the maximal degree of a polynomial that encodes a gate and what happens here is that you see that like uh Blake and Chateau are still very high degree products but regarding performance or enforced concrete for BLS for Bless Field that we're originally think of it's actually very close it's it's much closer to uh shined Blake that that their previous designs and the thing is we can do even better so yeah for for prime numbers rising from Bill S curve we we can be really close but for 64-bit primes if we

if this 64-bit primes are used in a proof system we can be really really close so yeah applications the same as everywhere so snarks Miracle trees verifiable encryption authenticate encryption everything is ready so what I want to talk uh in the variant this is really work in progress so in some snarks like plonky 2 there's a very nice prime number used the 64-man so the 32 plus one and the thing is addition to multiplication in this field is very fast it's much faster just basically a bit shifts and addition so you you do it

it's much better than in this 256-bit fields and what is nice here is that you can also do decomposition nicely so the maximal number in this field is just like this the cool thing is that you can separate UH 60 into 16 bits like 64-bit number to 16 bits and your operation will be just permute bits it has very high degree just premium bits and add them up together and that's it just permute you don't have to design any smart test box like high degree level just permit bits another exercise proof that overflow doesn't occur and the thing is since you permit bits and zero this H case remains zero so you don't have overflow

uh uh yeah pretty much the same structure yes and the claim is well well of course there are problems we have like eight elements in the state we have more expensive diffusion layer and so on but speed really rules here so you see like we're just two times slower than just two times slower than Chateau it was unimaginable like several years ago to start time slower than Chateau now we can do it so we can hopefully we can design something better like in a concrete layer and in this uh bricks we call them bricks they are also some load graduate stuff maybe we can do something really better here and then it can be on par with Saturn not with Blake

yet but but we hope to to be really in part with it but I think that's what we have already is is quite good so look up arguments have health of the laws thank you guys thank you everyone who designed lookup arguments that's really cool stuff so and GK friendly hash functions are not slow anymore they are friendly to everyone they're just friendly hash functions and we use security analysis from all good old times and we promise to deliver even faster hashes for your specific Prime field thanks [Applause]