ZK8: SAFE: Faster and simpler hashing for ZKPs - JP Aumasson - Taurus

Transcript

foreign but you know they won't succeed we'll keep on hushing stuff and hushing in plenty of ways and I have yeah this topic of my dog crushing and fast hashing and the great news that we have some time I think so I mean that's the last talk of decision right so we have the conference finishes at 6 30. it's three so three hours of hashing um so hashing is everywhere not just

hushing one message but doing a lot of stuff with hushing and in zkp insecure proofs in particular so you know commitments in every single talk today you hear about commitment polynomial commitments and so on you hear about Miracle trees when you don't know what to do you use a tree the future mirror of course when you want to turn a protocol from interactive to non-interactive you hush stuff and of course when you want to generate to make things unpredictable like in future and just for simple hashing of course to the random functions so they're in the permutations to some extent the rbgs So deterministic Random bit generators exhaust extendable extensible output functions so there's so many fast

functions I don't know myself all of them and if you look at the snark at the protocols um like alio so you have hashing everywhere if you look at stocks you have even more hashing so I don't need to convince you that you know what is ethereum people are trying to do killing hashing the they want they won't succeed so I've been designing hash functions for quite a while uh so this is a joint talk a joint walk with what Dmitry was here uh uh in the main instigator of this project and more than 10 years ago in 2008 2007 so Dmitry and I were doing our PhD and working on harsh functions trying to broadcast functions and then we designed some hash functions with more or less

success and the game at the time was to make hashing faster and faster meant well you implement in software in C you're an academic you don't write very good code but you try to make it as fast as possible and you measure in terms of cycles per byte you know to make it independent of the frequency uh but in the ZK Summit context we don't only care about you know the speed of vanilla hashing so vanilla means when it's run as it's specified not in a circuit not in a in terms of constraints of or air or r1cs you name it but in the context of zkp the performance matters even more than the speed in pure

software because people who are you know spending days trying to make their harsh a bit faster hashing at you know 10 gigabytes per second instead of eight gigabytes per second and then yeah we're faster man look at the read and write speed of your drive I look at your bandwidth uh look at your network speed you don't care about being 10 gigs or 20 gigs it depends but so in the context of physique Pros an important metric is the number of constraints so be they are one CS like in Marlin or air or other types like in Planck and all the plant family but in general if you have many unconscious constraints you will have many IR constraints as well so that's what is sometimes called algebraic complexity and of course the goal is to

minimize the the cost approve the narration um and if you use a simple general purpose hash function such as Black 2 Orchestra 256 it won't be ideal let's say so that's why people came up with the concept of ZK friendly hash functions so functions that would be well suited for the use case of secure proof systems where most of the time we work with algebraic structures so hashtag finite field typically polynomials and so on but most of the time you're going to work with objects that will lie in a finite field and for example something that is straightforward

in a normal computer like the extra operation the most stupid operation of all time uh then it's quite painful to do on finite Fields because you have to think in terms of encoding in terms of converting your final field representation in terms of xor and that leads to many constraints and that's very annoying by the time when I wanted to implement Black 2 in uh in Leos the language of aleo I was stuck at the part where I had to do exhaust I was like damn it doesn't work so yeah even though I like black too not I'd like to of course I designed it it's really not what you want to use if you are going for an efficient circuit

an efficient progeneration so people came up with a bunch of designs Poseidon is the most famous one so one of the co-designers here as well and Poseidon is orders of magnitude faster and smaller than Black 2 or shot 256. design I believe in 2019 right uh whereas Blake 2 was designed in 2012 it depends how you count it and shot 256 was designed even earlier some people are making the argument that oh Poseidon and other algebraic hashes they're a bit new they're not as well studied that I want so we want to stick with shot to a black

too but um I think Poseidon is safe at least the parameters that are defined so of course another way to make hashing faster is you know just to reduce number of competitions reduce the number of rounds familiar perspective many harsh functions are also over designed but that's another question so let's go back to Poseidon uses using alienoma does ficon penumbra you name it many projects but people designed or other hash functions such as rescue such as Griffin Neptune is a variant of Poseidon mimc so sometimes to optimize maybe for the field size or to optimize for the constraint type so if you see the there's also synthemia

by the zikash people and if you just look at the the numbers here so black two shot five six not GK friendly hashes or big numbers here in terms of other product in terms of r1cs or blue cap constraints and you see there's really yeah an order of magnitude between these guys and um and uh zika friendly ones okay but they're fast natively in the vanilla mode so so Ezekiel from the hash is good it's presumably secure it's presumably efficient and it often works like this so it's a sponge a sponge function

do you know what a sponge is so it's a sponge function instead of hush function but it's a bit misleading because ultimately a sponge function gives you a harsh function it's a way to construct it so it's a very simple way instead of having to design something that takes something big and shrinks it to something smooth you just design a permutation this is something that Maps you know in a reversible way an input of some fixed size so in kit stock it's 1600 bits and input I don't it depends but it's easier to design as a cryptographer so when you look at the Block Cipher you look at the Block Cipher it's a permutation with the key you remove the

key you get a permutation so you take your block Cipher you move the key you get a hash function and with this permutation you can create a hash but you can create other stuff but the way it works is that you just Excel your input in your permit you exalt your permit your exhaust so of course you just exhort part of this statement everything otherwise it's completely broken and there's another mode that is called duplex so here you don't just send input and collect the output you can combine the two you inject you absorb some input and then you read it and then you can write right right and then maybe you want to read to get some output so the typical use case for this is a trng

whereby you get entropy from your system you introduce entropy and the read option is when you get a Cisco or whatever that needs some sort of random buys so maybe you can also think in terms of theater at this point okay I send my right my commitments and I read my Challenge and this kind of thing and you see the word bad bad bad so bad means that you have to encode your input in a certain way and part means adding some additional data for example the encoding of the size of your input um to get the security proof working and to get a secure design but in practice it's not so easy to do you know I'll tell you what's easier than I told you that I tell you it's not

easy okay what's this guy saying um so in crypto like many times it depends uh it's deceptively simple in the sense that once you have to implement it there are many questions that that come to you like well the encoding the parameters the interface how do you define the API you take five different implementations of course I don't you get six different apis six different ways to encode the input to to assign the arguments to the input and also what we call the domain separation so if you have objects of different type of variable size you need some encoding to say this is the start of my first object now I'm going to the second object and maybe there are different

types of objects and you want to avoid trivial collisions whereby if you have an object of two bytes and an object of one byte then you can also see it as one object of one byte and another breath of two bytes but if the three bytes have the same value then in these two situations you end up with the same same hash so domains a person is quite important and the budding so in the real world in the vanilla case non-dk would already care but in the ZK space every single optimization is useful because something that looks small on paper can translate in terms of hundreds of constraints uh you know so they're simple ways to simplify it some people started specifying the harsh

function in terms of field element instead of beats so there are some papers that talk in terms of algebra capacity so you know the capacity Concept in a sponge capacity is the size of that part one you don't or you don't write and don't read uh and just Define it in terms of reading and writing field elements and also if you assume that the input has a fixed size so let's you take a feature meal you know in advance the number of elements that you're going to provide you know their size because the size of your field is not going to change Well normally so there's a lot of things specific to the ZK use cases that we can leverage to simplify with the designs

okay so maybe you don't trust me or maybe this it's fad uh it's not that hard there's no bugs in harsh functions so to to prove that I'm right I did the flowing experiment a few days ago when I did my slides I picked a uniformly random Poseidon implementation on the GitHub website well not uniformly random because I picked on the first page of second page of the result and I gave myself five minutes to find a bag you know quite challenging I was like oh but the first implementation I didn't find any bug I looked for the usual stuff you know domestic version and even sometimes people can't use Matrix vector and Vector matrix product in Poseidon

but the first was fine and the second implementation which I will not cite because it's from a friend I found a bug and it was then then what I can say is that they were trying to implement multiple instances of Poseidon to spawn multiple instances and to estimate the security level depending on the parameters the parameters being capacity rate and width side of the state and the competition was wrong what's wrong in a way whereby the overestimated the security um if I remember correctly they derived it from the width not from the capacity so you could get an instance that the

program believed it was maybe 128 bit secure whereas it was not so while the upshot is that even very smart experience people can get stuff wrong if I write cryptocode I will get stuff wrong all the time so we need to minimize the risk minimize the erosion bring what the people need safe support API for field elements it's not a new hash function it's just a way to simplify standardize the boring stuff so we're an implementer you know the API the encodings all these things that you hate doing because it's not really cool it's not very interesting it's not really deep mathematically but it has to

be done and we also get rid of the padding do you know that in terms of putting the accessory the sketchak you might think they're the same no they're not the same because the padding is in shastri in just wicketsack is not the same padding as not just Wicked suck and I think that in ethereum the olden the user non-shastry gets like so the the old padding yeah okay let's see crypto is so confusing and launched like three days before nist ready [Music] so yeah so nobody no problem we get rid

of the padding it doesn't come completely for free we have a walk around we use what we call i o pattern which is essentially a description of the course you're going to make so you might say I want to absorb then byte and then I want to read two bytes and so on and so forth and it will be beneficial to everyone if it's kind of de facto stand out because it will make implementations interoperable it will give a common Baseline to you know implement this kind of heart function um and also for people who are interested in Hardware so what Omer presented this morning uh I think it will also be easier if we have a single way to do hashing so that you don't have to to

create a new a new chip for every single uh hash function use case so then again it's not anything very deep or new it's not a completely new mod it's just a Twist over the duplex mode um and it's not a new permutation so there are a lot of good works in the permission space I think Dimitri will present a new one in uh you know 45 minutes but the flip side is that you can use a neat permutation with safe so you like Poseidon use it you can use any finite field so our goal is to be as generic as possible

so the API has to be quite quite simple so that's essentially four course start where you initialize the the sponge so it looks a bit complicated IO pattern demand separator but the i o pattern is just description of the coaster going to make again so absorb squeeze absorb absorb squeeze with the size and the main separator is just fancy name to say you know personalization or another string that will make the function different so if you have the same i o pattern and different separate domain separators you will get different

initial values which means that the functions will behave completely differently for any same input you will get completely different output so absorbent squeeze it's you know write and read as I mentioned however the difference is that you can provide arbitrarily many bits to each of these calls so if the rate of your sponge so if what you can write between two permutations is I don't know just three bytes you're not limited to three bytes here because it will distribute whatever you have to read or write across as many you know small absorbs or speeds as possible uh what I want to say is that

if you look if you look here if I have to absorb if I can absorb three bytes per call I can do three three so you can call our absorb with nine and it will take care of doing the two permutations and likewise for the for the squeeze okay and finish is the conclusion so why do you need to call Finish if you can just squeeze stuff out and call it a day so finish will do maybe two things so it will erase the memory right you want to use the mem0 or equivalent to safely erase the memory to make sure that nothing is is left in you gosh or whatnot

and it will also verify that all the calls that has been that have been specified by the i o pattern have been executed so the goal is to prevent what cryptographers call misuse uh maybe you define your function in a way that you have to do another strip soft codes and write and read it and bytes and the Finish call Will validate that all the calls that had to be made have been done with the right length parameter so you can see it as a safety net in your protocol to ensure that you have used this correctly and that you computed the i o pattern correctly and there's no padding at all no no

reason to bad stuff yeah but there's a caveat so the state is stateful of course you have the permutation state so it's the the elements of your permutation it might be four six eight more field elements depending on the size depending on the security level the permutation of course the function that will permit the the elements and two counters so just small numbers between 0 and the right so they can be you know eight bit values positive 8-bit values and then we also need a hash function you're like okay what the why do you need a hash function for hash function um it's just to bootstrap the design so when we compute the initial value we

take this i o pattern so this encoding of the the usage of the hash function we encode it we're just very straightforward sterilization system and we hush it down to 128 bits to write these 128 bits in the initial value but you don't need it at runtime uh you can just pre-compute because you will know in advance what you're going to Hash what you're going to read and write so this can be part of the design you don't even need to have it as part of your code you can pre-compute the initial value uh and you won't need a hash function at all and likewise the the tag the initial value is derived from the use case

but you can also hardcode it evenly in the code and so that's what I mentioned you this you define you derive it from the i o pattern and just to give you an example by repeating what I mentioned before so if you these are three i o patterns the first one you absorb three bytes through those three elements sorry you see I'm not in field mode I'm still thinking in in terms of byte you know you absorb three lemons and then you read one and in this case you absorb two elements and you're you read one in the third case you absorb two then you absorb one again and you read one

so which ones are equivalent to each other sorry one and three right one and three because here you're going to absorb two plus one equals three and here you're going to absorb three in in one one call but for the safe mode it will be equivalent so it will aggregate these two values and it will just see this as one single absorb with three elements which means that you're going to have the same initial value which means that you're going to have the same output at the end so you have this degree of flexibility in how you organize your your goals um so you can see start us committing to your i o pattern and then the Finish as

verifying the commitment opening the commitment okay um so then you can see this this thing we did as a middleware between the applications and the sponge function and the sponge if you have an opposite on the kitsack or whatnot it can or it should only expose this very minimal you know low level API where you initialize the capacity with the initial value you pyramid of course and read and write element so you can read or you can add and there's you don't need any anything else are you a problem absorb somebody

switch on and off again can't you know okay um so let's move to concrete use cases be very straightforward so medical tree the simplest medical tree you can imagine two two leaves and one root so each Leaf is one Element so you absorb the first one you absorb the second one and then you squeeze out one element but before that you have verified you'll have defined your initial value and then you verify that it is correct um in the paper we provide some test values using the shastri 256 which functions if you want to verify it

so that's the case of a basic you know non-interactive Twitter and to interactive protocol uh you have some elements of the proof awesome typically commitments the program is to these two values then the verifier will send some challenge so in terms of safe in terms of sponge this will be an absorb this could be a squeeze this could be a read then a write then a read and and so on so um some limitations of this very nice mode that we designed maybe the first one is it doesn't support what is sometimes

called variable input viable length input if you don't know in advance the size of your message then you cannot Define the i o pattern therefore you don't have an IV so you can hush um so it's it's a use case that sometimes happened but we specify how to handle it you will most likely need some padding but you'll be better off if you know the size in advance you will have less less overhead we even describe a way to use what we call the infinite length prng if you don't know

when or if you're going to stop generating output if you have already this stateful system or you will read forever that can also be done it's a small walk around in likewise for the aead so authenticated encryption with Associated data um you have walkarounds to support input when you don't know the size in advance so yeah I just showed Market three but of course you can do prf AKA Mac encryption and authenticated encryption simple hashing everything you can do with a permutation uh also the input domains the person that depends on your protocol so let's say you you hush stuff you hush a field element that's fine then you need to

hush a string so you have to encode your string into a field element but then this becomes a field element but you're hushing a string so you have a collision between the case of harsher field element and the case of string which happens to have the same encoding so you might want or need or it depends to add some encoding to Signal the type you can add an extra byte you can add an extra element um so then it really depends on your podcast constraints and specifically what is controlled by the attacker what is potentially you know what modifiable budget occur what is determined in advance what is random

so there's no single right answer here also you need a hash function like I mentioned before but it's not a problem we have good hash functions and maybe last point that people raise is but where's the security proof um Dmitry and I are very convinced that it's secure so shame on us if it's not but more seriously I don't like writing security proofs some people do it very well the change compared to the original design is very small and it will be very easy to show that

our model with our with the i o pattern instead of the budding is exactly the same security bound as duplexed and uh but what not and I think some people might be walking on it right yeah so proof in the full version of the paper as we say um so yeah if if you'd like to learn more you have a page online hack MD page the reference code is file coins implementation in the Neptune Project which is a small twist over Poseidon so if you're a hash function designer

you can focus on creating a permutation which is by far the hardest part and just reuse this mode uh for the rest sure specifying a protocol it will help a lot the implementers to specify to write it in terms of safe course absorb squeeze instead of having different terms different notation different language also it will make the the code reviewers very happy and implementers likewise so if you have to code in software Hardware um might be convenient to to use this same wording this same API this i o pattern because it will also make your library interoperable with people who choose to use the same

protocol um so it would be happy if it becomes a de facto standard we don't have a certification program or you know do this at your own risk thank you for your attention and here for questions [Applause] yes for like MPC in the head or or yes so you can see strobe as a generalization

of of a sponge so it's a stateful object where you can write and read stuff here all God is limited to emulated some symmetric Primitives but if you are in a case where you you want to come into stuff you have this concept of Chinese response it can also work very well because it can save you from having to choose okay well I'm going to rush because I've seen many bugs where you know you had to Hash a transcript and people were forgetting to put stuff in the transcript so there are many bugs in TSS in threshold singing protocol where okay that's what we have so if you have something that is stateful

um and that is hushing is absorbing all your transcript um in the first place so you have the guarantee that you're not going to forget any value in your in your hash dude that's actually a good use case use case we could have mentioned here special science every round sorry I didn't understand yeah okay interest for this oh no for any any application so if your

chairman just happens to be one relevant use case but you know energy is not the only case where you need to read and write about it [Music] all this is [Music] implementation where I just like

this would oh yeah it will just you just have to call them aside them like in certain ways but it's not no text overhead it's the the same costs you just have to like call the proper inputs like visualize it for food it's pre-computation so it's not runtime cost just give people aware sorry [Music] I just copied to the IV

so we just you see that you pass the harsh output as field elements so if it's 128 bits and you have 128 bit field let's have one otherwise you pass it at Cross three and then you just copy paste it [Music] [Music] well typically it should be a a crypto friendly field you know where you know the discrete log problem is hard and a large Prime model field because if you

want a binary field then black is two is fine because it work with bits which are you know gf2 but yeah it's typically the use the main use cases it's at least 64-bit fields and most commonly 256 or more cool and um where is the field uh like where would you declare yeah good points because we don't depend on the field we don't encode the field but we don't need to because if you have a different field the function will behave differently the operations will be different so you will get a different input you have a different output sorry so that's why you don't need to explicitly say I'm using this field or

or this group [Music] exactly and that's the part where if you need to hush objects which are not natively filled elements you need to convert them to field elements and you have some ambiguity yeah right yeah so it can be straightforward but these straightforward problems are sometimes the one that people get wrong so you want to avoid collisions and two different items mapping to the same field element and that depends on that responsibility of hashing as a field is on the person who's using the other color or the

application because we can anticipate what people will need in office and our strengths and mages or whatnot yeah oh you can put you could put whatever you want in the initialization uh we have this domain separator which is a generic input type specified as a string of arbitrary size which is just appended to the i o pattern so if you have on a one gigs image disk to they want to hush it as well the good thing with hash functions you can as

much as you want yeah sorry if no other questions thank you guys and uh hope you like it