zkSummit -SNARKs love Hash Functions: Hashing (to Elliptic Curves) inside SNARKs-Rebekah Mercer O(1)

Transcript

[Music] hello my name is Rebecca I'm not gonna be presenting another snot constriction today unfortunately and instead I'm gonna talk about what hash functions look like inside of snogs and most importantly like how we can achieve hashing inside of snacks efficiently so the road map is I'm gonna show this day of the art for arithmetic circuit friendly hash functions and the snacks presented so far today have been kind of varied in the like computation model which you can efficiently prove things about inside the stock so I'm gonna be

focusing on ones that that target like all on CS so think growth 16 we want to be minimizing the amount of field multiplications and so what I'm gonna do is say like what what do we need to keep in mind when choosing hash functions like what is gonna be expensive what it's not what properties do we need what properties can we maybe do without and then which hash functions best satisfy these requirements so the first thing you might ask when you think of like hashing inside of elliptic curves I mean hashing inside of stocks is like why can't we just do what we've been doing for the last 20 years which is like use a hash function which has been made really fast so sha-2 went through a standardization process it's like really

battle-tested achieves all of the properties you'd want from a hash function but it's but just it's really slow inside of a stock and the reason why it's really slow inside of stock is because the things that make a hash function or any arithmetic on a computer really fast like a lot of bitwise operations so this works with bytes and woods so each each letter here is representing a variable which is 32 bits so like a wad on a computer and then it uses operations which act on these bits so this happens I mean practically instantly on Anya hardwa XOR Inc is really cheap rotations great and inside of a stock this is

exactly what you do not want so if you're walking in arithmetic field you don't have a 32-bit what there's not really such a thing so what you have to do instead is separate all of these into one bit per field element and then do all of the X's and ands and rotations in a bitwise fashion which which is terrible so if yeah it's just it's not what you want so this leads to proof for a shot to hash having about 27,000 constraints which is huge for a 512 bit message to be processed and one one of these proofs creates like

1.5 seconds which maybe isn't that bad by itself but if you want to do multiple of these it's gonna be terrible fast this means it's about 54 constraints per bit process so you're doing yeah almost 54 multiplications every bit you're processing this is I mean it just looks we have a lot to improve here so maybe if you think about the ways that we can improve maybe first we can relax all conditions so sure as a hash function it satisfies a lot of properties that you want from a hash function um but if you want to just just use your hash function for commitments then it's maybe a

simpler goal so commitments requiring least second preimage resistance which means that given a message it's hard to find another message that hashes to the same yet the output of the hash function is the same or collision resistance which is like you choose any two messages such that the output of the hashes is the same so what happens if we only need this goal and maybe we can we can first like construct something which is simple with that just satisfies this so the reason why we would like need just this goal is because in mukil trees which you used a lot in in cryptocurrencies that youths knocks for example we often have commitments to coins or to like transactions that a

constricted and vocal tree and each layer of this you to use a hash function but your hash function only needs to be collision on a second preimage resistant so we definitely have the motivation so and we also have a solution so thanks to like Sean Bo who you had earlier today and Dara from Z cache like they constructed this really good hash function that satisfies exactly the requirements you need in this case it's called the Peterson yeah it's like it's a Peterson hash and what you do is you split up your message into its bits or you could split it into little bit chunks and then you have generators yeah which was the GI in this case and you can just

multiply like little sections of your message by each of these generators and this is great because instead of well we had better automatic before we now have field arithmetic so now instead of like one and between two bits being one multiplication we have that one multiplication is one multiplication so we at least we've made some progress you can do when doing which is like instead of where I've written here each bit is a labeled M you can construct little chunks instead so maybe every M I would be like three bits and you can hog code some parameters and then you can use some lookups which saves you on doing the multiplication so you kind of like pre compute the multiplication so then

instead of Reaper forming it you can just say like you know it's one of these eight values if it's three bits and and this is the one that it is so this leads to about one point seven constraints of it instead which is if you recall the last one was 54 like we've already done a great job so Sean and air should definitely be praised for that yeah so it leads to around 900 ish constraints for a 512 bit message and also an important thing to stress here compared to the hash functions that I'm going to be presenting nice it's like this one has provable security from the discrete log assumption so if you want to be conservative in your assumptions that

you're using you don't want to move fast and break things then and you only need properties for the needed for commitments then this this was a great choice but what happens if you don't just need commitments like you don't just need collision resistance then you need indifferent sure ability from a random article so you need your hash function to look its output to look random and wait like common use cases which you need this full for example the additional signatures so if you replace the verifier improve our interaction instead with a hash function then you need the hash function to have like a random looking output and as well if you want to compose like stock verification

with some of the newest knocks that every unproduced like the universal set ups knocks a lot of the time these use the Fourier transform as well which is it's the same it's like if you and if you have an interactive protocol where you have a proven verifier and you can replace that verifier interaction with a hash function as well so this is a way that a lot of the newer like Universal Universal set ups knocks get rid of interactivity and so if you want to yeah if you want to compose with one of those if you want to verify that inside of a stock then you want you want your smart you want your hash function to behave randomly so what do we do here

so we can so there's been a line of work so there's Mimzy hash originally this was started because in MPC you have in some types of MPC you have a similar computational model that you get addition for free and multiplication you really have to pay for in terms of communication so MC hash was suggested and then the like this is just more work that builds on MEMC hash then the more recent line of work of which we have one of the authors in the room is this a pack called vision and rescue and the faculty talk had and Poseidon and these are these are the papers that were

written for the motivation of hashing inside of stocks so like they really take care to make sure that you're not wasting any multiplications so the paths because one of them of each of them targets a binary field and the other one targets a prime field so which so we have rescue and we have Poseidon so I'm gonna do some thought leadership here and tell you like which one I would conclusively use and so for that we need to take a look inside of them kind of so Poseidon is made and and rescue as well a made of these three-stage Leia's so this is like one round and and you repeat this many times

depending on like what you secure what security level that you're comfortable with so the a ok Leia is just add round key so you add a constant in this layer so inside of a stock that's free then the M layer is like matrix multiplication so this is also by a constant by some like constant and so this is also free inside of a stock then the S the little s in boxes that called s boxes and this is a this is like a kind of hash design taken from the hashes that would designed way before Knox even existed so the combination of these things is like

something which people maybe believe is skew so what happens inside the xbox is really what's most important and Poseidon itself has some partial layers they're cold in the middle which only use one of these X boxes instead of putting the whole state through nest box just to even more simplify the arithmetic complexity of the entire circuit and the like concrete numbers are like approximately 228 constraints in the case of MIT foreign sixes Cubs which remember the 753 but cough so you would have a really bad time in all of the situations with these but this one it's like it's very yeah you get no

point three constraints pub it processed because you also walking infield element straightaway here so you so processing one feel element is processing 753 bits already so you don't it's yeah you get a lot of efficiency straightway so what are these Xbox as themselves look like so in Poseidon you have X to the Alpha is that your expert s books and this needs to be a buy action which means you have to use alpha as the you should use alpha as the smallest prime so that your prime minus one is not divisible by that prime so you should be P minus one should we count co-prime all minus 1 in

this case should be co-prime with the prime number that you use those alpha yeah so it recommends that you use 1 alpha 1 over alpha if 3 isn't co-prime with o minus 1 but we chose alpha equals 11 instead because this is aw smallest prime let's go prime so rescue uses both X to the Alpha and X to the 1 overall for us X boxes which is exactly the same number of constraints inside the stock but if you want to be nice to you approver as well then they might want to produce this hash function outside over in the hash function outside of the

stock as well and one of alpha raising a number to the power of 1 over alpha when all of the arithmetic is modulo 700 like 2 to the 753 almost is very slow outside of outside of smaug like to do this on computer your computer is not very happy with you so yeah so if you have to speed the recommendation is that you would use Poseidon however one caveat is that I haven't really said anything about the security of these recently suggested hash functions and so I I'm gonna defer to Allan who's talking right after this about exactly that so like contrasting

the security of these that's his job so what happens instead if so so far we've been hashing to like field elements so we've been hashing to practically bit strings we don't need the output of the hash function to have any special structure like in some cases you do need the output of the hash function to have a special structure your hashing to an elliptic curve point and just to like show you what this in one line if you don't like hashing to in love with a cuff point is kind of maybe a weird phrase so you just want to sample a random lift at cuff point so you don't know the discrete log pretty much um and it's like it's also it's a random elliptic curve point so the motivation for this one of them is

verifiable random functions they rely on this super heavily password authenticated key exchange as well like I've not seen this happen in a stock but if you want verifiable that's why I chose indicated key change then this would be use case where you would need this and then like if you want to verify pls signatures inside of the stock you also need to do this and that one will be important for like my clients for any protocol that that uses VLS signatures for example so just to motivate why verifiable random functions use hashing to elliptic curve points because it's kind of interesting these instead of the normal back and forth where you prove that you have a private key that corresponds to a public key this is kind of which no signatures look like instead

you prove that with this hash with this cuff point which is the output of a hash of a message then you get to multiply your secret key by the hash of a message and if for some notion of like order if the output of that hash function multiplied by your secret key is larger than a target value this counts as like winning the lottery and some proof of steak protocols like aurorus genesis for example so like proof of luck you do the like repeated hashing and if you find one that has a bunch of zeros at the start first then you win the proof of stake equivalent of like how you win the lottery as you do a multiplication by the output of a hash of message and if

I've just said your x-coordinate is larger than some target value but if you have some ordering then you can define who wins the lottery so this proof looks just like shinola so if you're familiar with astronaut Hall would just look like all of the H prime to the M Harries you're proving that the number that you multiplied by H prime of M is your secret key so and as I said before in as well you need to replace the verified by a hash function so here Bob is replaced by a hash function and then another motivation is snacks with private input so maybe this isn't talked about very often but girl 16 you can't actually put private information right

in and not have malleability so if you um so this is just a security property that says like if you want this idea of like if you if you can only want people to be able to construct proofs if they have a valid witness oh no a valid witness then you want simulation extract ability rather than the security property that's in got 16 by itself and one of the extensions which gets you this is Bo gap is on 18 and this does it by including a message hash to elliptic curve point as well like this stops people being able to like maleate the proof so in this case as well you would want an efficient inside of smaug having

two elliptic curve so what is not friendly hashing to elliptic curves hashes look like so we saw insurance talk as well there's such a thing as an embedded curve and this is like the cub which is defined over the scalar field of the original curve so this is why the stock arithmetic takes place so this is kind of saying there is such a cub so like does hashing to elliptic curves inside of a stock makes sense as a phrase and so what this slide is saying is like yes it does if you have elliptic curve points defined with that coordinates as the as the points in the like original scalar field then you can define a curve so this just means that

arithmetic inside of the stock can can be used to describe an elliptic curve you can like efficiently ascribe live to KUB group operation yeah so it just means the rest of my slides are going to make sense so the first idea that you might try is called trying increment and this is kind of like the so Clos way to get an elliptic curve point and way that you do this is you have you just use it normal hash function you hash your message you say like if this was an X of an XY coordinate pair on elliptic curves would it make sense and if it does then you say like great so I can solve the equation I can solve the

cab equation and I can get my Y and if it doesn't then you add one to that X and then you say like is this one the solution to the cab equation if if it is then you're great if it's not then you move on so you can do this outside of smaug it's like an okay way to go about life but finding inside if it's not gets kind of difficult so finding whether or not f of X itself which is defined here as like the calculation is a quadratic residue so if that Cisco if that's going to have a square root so it is why can you exist finding out whether or not that that has a solution that takes an exponentiation which means like of order of the field size bits so in our case 753 constraints

just for that and then square rooting itself so if that is a valid solution to that problem then you need to square root in order to find your Y and this can either be done with one more exponentiation so 753 mole constraints Oh with like a whole algorithm of its own which is like significantly more than that yeah so we have the this you need to add one for approximately half and then and then on and on and on and there's very many like analytic results about how well distributed the exits are so like all you're going to have to add 50 before you find once again which is a square are you only gonna have to have one like there's very many there's not

very many results about that and so to be to be conservative so that you don't run into like bad cases all of the time you're gonna have to set that K parameter pretty high and in Knox there's no way to say like I'm done now let's cut show it from this loop and so every time you want to do this you're gonna have to do it the way that you would do it in the West case and so it leads to like very many constraints very fast and then so maybe the next thing you would is like how about we use a hash function that we just defined before those ones were really cheap right and multiply it by G and then we'll have an elliptic curve point and this doesn't work for kids if you look at VLS signatures everything is terrible if you use this

as your hash function it just you can immediately forge just from someone's public key and from whatever message that you want this signature scheme kind of doesn't exist has a signature scheme anymore because you can just yeah it's just because this this equation holds and so using only public information you can just contractions they're completely valid it's also expensive so moving on to the non expensive ones these are the hashes to elliptic curves of the yeah priests not lecture true also so you have eco style and coatings they have these like pretty simple equations first you you define like this little rational

equate like rational function and then you have this one so this is great if you're okay so this only achieves one-wayness number one so this isn't by itself a solution to a problem this is also but this bit is solved so you can extend this by just kind of using it twice you just double everything as in like double formulas you can create it okay yeah create a hash function which can be modeled as a random Oracle but this one I assume that you're your prime is to mod three and this is because it uses cube root yeah cube rooting and it needs cube rooting to be a bijection which means all minus 1 comma visible by

3 so this doesn't like in all case so then there's another suggestion this one is this one is pretty cool so here G is the carve equation so pretty much you can pick 3 X points and then construct the cab equation for each of those and because we have that this is equal to a square those like results from number theory which say things multiply together that are equal to a square at least one of them is a square so what you can do is you can construct these instead of like the came any that you had to do in try and increment you can just construct these three versions of the Cobb equation and then one of them will have a square root so the formula

again looks like this it it looks I mean it looks silly in its latex but it's pretty low complexity I romantically and then you can also make sure that this one is extended in order to satisfy the requirement of in differentiability from a random Oracle then really recent lack of dampen a and we add I think yeah it removes all of the restrictions from this one generalizes it it proposes a constriction that even walks in be n curves yeah and and so this one is all good it's like full speed ahead with

that one so but what happens if we could do better than this because we're inside of snogs so the blob even a paper just targeted like constant time hashing to elliptic curves they didn't consider that it would maybe we used inside of snarks and what can we do inside of stocks so inside of stocks instead of for example if we just wanted to compute a square root then you can imagine that instead of having to compute the square root inside of the stock in the field arithmetic with all of the multiplication gates counting as constraints you could instead if you wanted to prove something and has it a square root you could just feed in the square root and instead prove the that thing that you just gave Squad is equal to your original number so instead of

doing a long complicated square root algorithm you just do a multiplication and then you make sure that the things are equal so you just like add to your witness so this takes us from run time which is yet a cube of luck all which is how long square routine usually takes two constant so you just do one or two occasion so maybe we could use this to our advantage so each of the X's in the formula from the page before actually parameterised by another T and so like how do we get that T we use one of the hash functions that we just said so we who's inside of a snack we're gonna use rescue or Poseidon then we want to pick the first square so checking the

squareness outside of the stock is an exponentiation checking it inside of the stock uses one of this yeah it uses also an exponentiation but what happens if we have different ways to win this the fact that it's square on on square and the turns out that we do so we can use what i just said before to witness that it is a square so if it's a square it has a square root and so you can just submit the square root and then square it inside of the circuit and then you're finished but what happens if it's not square so what happens if someone lies to us and they say like this how do you observe and it's because of this the result which is like a square multiplied by a square in the prime field it's

still a square but a non square multiplied by a non square in a prime field it's a square so if you choose a non square which is like so QR it's quadratic residue which is just like a mathematicians way of saying a squad number in a prime field um if you have a pre computed non square then you can only multiply things by this which are non square in order to produce the square so we have two cases now so either you submit the square root like I said before which is called X in this case that solves your equation and then that can be checked inside or you submit the square root of the yeah well you submit the square root of the number that you're wishing to prove is square

or non square multiplied by this hard-coded non square so then this square root will only exist if the number a in this case is not a square so then we have that you increase the witness size by two elements you give the square root of either a or a multiplied by a beta and then you can a check that the square of this is either this is just a bit so the bit is showing like this is either square or non square if the bit is zero then you're in the non squat case and if the bit is one then you're in the squat case so either way that equation will have a and this is how we do it so in summary you can submit different things to us

not accent like rearrange equations of it and save a lot of constraints there's no accent hash functions gonna walk together as friends thank you [Applause]