New hash functions for Ethereum, SNARKs, and STARKs by Dmitry Khovratovich (Devcon4)

hello everyone that's great to see so many people on our purely mathematical and cryptographically talk so I try to rule out as many foreign laws as possible but so many of them are left here so this talk is of course intentionally scientific to show up that we are doing something serious but there will be also like important numbers will be on the very last slides that like this slide before last so like number of constraints and this sort of stuff will be in the very end so if you are just coming just for that you can wait so this is a joint work of the companies I'm involved with every Manta BDK consulting and also our colleagues from universities of Britain grads are now Florence a Christian Sebastian and Marcus so this kind of work that was conducted a bit independently and then later merged and still it's kind of work in progress we even haven't invented the proper name for the hash function so that's okay so you'll probably remember what the head function is what property should have the good hash function should process arbitrary large input well up to some extent but pretty like that you get by it should handle it should be collision resistant meaning that it should be difficult to find X&Y difference so that the hashes of them are identical well as long as hash function converts arbitrary large inputs to fixed sized outputs collisions are unavoidable but there must be difficult to find per image resistant means that given Y it must be difficult to find X so that H of X is y well hash functions theorem everything is hedge funds everywhere of course mainly Shah 303 or ketchup the hash function designed by Belgian de Belgian team in lead by Yann diamond in about ten years ago so sherry is built is used to build a patricia tree to construct the wrists out of the public key and so on and so forth so if it's not like the best like terms often not the fastest hash function in the world but it still can handle up to like 500 baits per megabytes per second well to understand why we need a different hash function I'll go a bit to the introduction how hash functions are used in snarks so this is some sort of a petition a bit of the previous stark talk well in Bitcoin we sign because usually I still have to start with Bitcoin unfortunately because there has the zeroes proofs apply usually to a transaction output you take so based systems so we sign the transaction with some output and hash function of production is glued it's in the block and after some point we spent the out but by signing the transaction and the output with the private key that was in the hash and the crucial point here is that the hash of the transaction is referred in clear-text when you want introduces their knowledge payment system this is concealed the hash is concealed to break up the link between the original transaction to send and the direction to spend so when the transaction is sent it's not only included in a block but also added to especially crafted Merkel treaty and when you want to spend it you prove that there is you know a transaction age which is in the miracle treaty that it has special structure and you know the private key that is that corresponds to the public key that is is in this transaction and here the transaction age is referred to in zero knowledge and the most computational expensive part in all protocols is to prove that the hash is part of the miracle tree so all the others parts of the proof are rather fast they all even with previous the original Z cache they can be managed within one second but when you have like 29 or 32 layers in the miracle tree this becomes difficult to to prove because their performance of zero-knowledge proving protocols they scale linearly or even super linearly with the number of invocations of a hash function and it turns out turned out very quickly that traditional hash function like regular hash function are not quite suited for snarks starks or bulletproof because their circuits they are optimized for Intel or AMD processors for modern architecture but they are not optimized for for the environment where Starks or snarks operate in this environments are big fields so the fields are either prime fields meaning that all now all kind of our state is a vector of integers models and prime number this prime number is 256 bit or 384-bit depends how afraid you are of recent discoveries and complexity estimates this for snarks and bulletproof and for Starks they are most helpful filled most better operators and stent is a binary field but not that big so it's like to the 32 to the 64 that's like the easiest to construct reed-solomon proofs so we can say we can simplify and say that in snarks a trusted party just kind of applies a secret input to the circuit and we can say that like all intermediate states are hashed true but still and all of them are published as a proven key and then bulletproof Starks this secret input does not need it so the proven key is just the circuit itself and for each proof there to Kunda to present to prove the creative proof you have to kind of match your execution your computation with the proven key so with a circuit or with the circuit on secretin so you have to like combine the two traces and that's why the bigger the circuit is that longer it takes to construct the proof and it depends on the circuit size it also depends on like if it's a break trace like can snarks like a starch then and depends on the width of the size of the state operates with on the degree if you permit arbitrary degree so different parameters are invoked and the foremost might not be very simple but there there's still some metric to to optimize and we know this metrics approximately for snarks we know such metrics for bullet proof so no such metrics for starks so the question is the question that should have been put when snarks and tark's were designed so kind of we cryptographic community bit missed this question this requirement that we there is a need in hash functions that operate in big prime fields or big binary fields that are best in certain metrics like circuit size or degree size products like in Starks and that there of course secure because the first two are easy to construct it's difficult to create a secure one and fortunately our cryptographic encryption oolitic experience allows us to create really fast hash functions because we know certain constructions that are reasonably that certainly fast and that we have analyzed them with crypto noses for years for decades and we know like the methods that could work the methods that usually do not work and we can quickly make a hash function that is secure and that satisfies this requirements so one the first approach was mi mc3 years ago and there the ideas from my MC was pretty simple so in the core of the mind see there is a permutation so originally it appears as a cipher but if you want hash function decide the key can be a random number it's okay here so the idea is very simple so you have you add some constant then you and you operate in a big field by default some prime field and then you raise your result of the power of three in this field so you Square and then multiply again then you add the constant then use then you put to the power raised to the power of three then at constant to the power of three and so on and each time they'd agree so if you express actually it's easy to show that typical Cryptologic attacks are differential linear kernels don't work here because of algebraic structure because the state is very wide but algebraic attacks work and the thing is we have to make our the degree of the polynomial that corresponds to this to the output of the function you have to make that the polynomial is of high degree to prevent various sorts of attacks and the degree increases like degree multiplies by three each time and the maximum possible degree is actually two to the n when n is their width or the state and we have to execute like a bit less than n steps to achieve maximum degree well actually actually a bit more but this is like the order so that you understand like if you if you if your permutation is I know 250 bits wide then you need kind of at least 100 sounds and steps to achieve maximum degree okay so there were also Patterson hash proposals but we can directly go to our contributions because the others are not exact so they're in different paradigm constructed and kind of not so interesting for us so our contributions consist of two parts so the first part as more generic so it's about it's about miracle trees and it turns out that we can do we can handle miracle tree substantially better than before recall well this is like three layer miracle trees vertical tree that handles eight messages well suppose for simplicity that the hash function it takes like two we consider a compression function that compresses with the ratio two to one and every message is of the size of the hash function output and then in this case you need any layers to hash to the end messages okay and the thing is the very nice thing is you can do better because you can when you have form when you have two layers you can process more than four messages you can take fifth one and then jet carefully we XOR in several hash function outputs in three and well you have two and using that you can for every like two layers you can process not four messages about five messages and that's give you well not so big but something like 20% in 15-20 percent increase in performance should give and this works for every hash function and collisions are pretty much resistance if it decreases but collision resistance remains at the same point so generalize birth defect also doesn't seem to work and this construction works for any hash function even more efficiently if we have a hash function that takes that can consume our bit very large input well with regular hash functions we already have that like we can we can feed very big input to sha-3 but it will be yes a sort of sequential on vacation and here suppose that our hash function is tailored to where large input size so the output size is small but what the input size is big and we use this large with to achieve cryptographic security thing is we can then decrease the number of layers of course so if for example you process the ratio is four to one that you need to twice fewer layers and what do we need how can we do that so what's the most optimal way of Parisian and it turns out that if we want to process some very wide input with a hash function then a very secure and construction is the framework it's a cold spawns mode of operation and it's based on permutations very wide permutation means permutation I mean that it's transformation is the invertible transformation that applies to very wide block here the blur the permutation is of with like 768 bits or more thousand bits to thousand bits four thousand bits we know how such permutations can be constructed and the idea of how they operate is very simple so message is sort not on to the entire state but all the state but some so-called capacity bits capacities twice the security level here if you security level is 128-bit that capacity should be 206 and the rest risks orcs or sort then they call permutation Authority called permutation story called permutation ten messages consumed and then you output this with the same rate as you consume in messages and of course permutation should be like ideal permutation the sense that issued this to some extent and essential from a random permutation well it's a constant function but you should understand what this means okay so the question is how to construct the permutation so that it will be starts narcho start friendly okay and the goal is to come up with with the design that will be both stark and snark friendly to some extent because the difference we know that in snarks we optimize we work in the prime field in stark we optimize on we work in binary fields but part on that our permutation can be built very similarly the first attempt what if we modify my MC and replace the power of 3 with an inversion and this is of course a very tempting step and it's not it's not actually trivial so when the MC wasn't was invented the author's tried this approach and it doesn't work let's work why because it's actually very interesting exercise that you can demonstrate that if that no matter how many rounds you have if you do in just the constant addition between the inversions that the resultant function would be a rational function of the input of degree 1 the thing is you can interpret your state as a fraction of like a little too linear one linear over another X plus B over six plus D and of course when you invert then the nominator and denominator that just swaps and when you add the constant the nominator changes but the degree doesn't change and unfortunately the state will be raised in a function of degree one and collisions are easy because they're like simple linear equations or even quadratics but they can be solved easily so and there isn't design Jarvis they decided to put some additional linear transformations after the inversion but it's yet not unclear for me if this is secure enough but I haven't managed to break it yet the solution that is still obvious to me because I would like to work with wide permutation because I would like to leverage the permutation with to get a more efficient circuit for a tree not for one hash function for a tree because that's the bottleneck and that is that why wouldn't we use multiple as boxes and use a very wide permutation then our function will be very similar to what we already have for example in a es or other designs and well let's call it for example inversion hash and if this inversion hash the parades as follows so it's you see like there are rounds and in this rounds we alternate nonlinear transformations which are denoted by s so each s is an inversion in some field it's not actually important for the design which filled it is because many attacks they apply similarly so of course you substitute as a parameter the field size and in some cases the binary for binder filled some attacks work just a bit differently but not tremendously different so generally if your function is this construction is secure for binary felt it will be like almost secure with the prime field unless your primes or benefit is very small but the construction is like this so HS is an inversion in the field and each a is a fine is enough fine transformation in this field that's basically a linear combination of inputs invertible one its and the another very nice idea is that for the middle of this construction we do not need full as box layer because the degree so the algebraic functions their algebraic attacks will work with they they can be kind of mitigated they can be controlled even when with one s box in the middle or two but with one is fine and the parameters of this design are of course the width of an S box and I say that this S box can be prime Filton version for snarks or this can be binary field inversion for starks and each by you can take whatever binary field to one so if you realize that if you think now that two to two binary field is good for stark you can use it if later you realize that for like root zone on performance you need 128-bit you can choose a bit different function they will work fine and then Ellis's analysis remains well at the most extent so of course we conducted like mainly my colleagues conducted a number of different sorts of attacks on this design because we already know this design from like 20 years old just this s boxes were smaller and apparently algebraic attacks become the most effective here but when you are six ourselves for example to 128-bit security you don't need many rounds here so we are talking about like six to eight rounds four outer rounds with fullest boxes fourth box layers and I'd know 5 10 15 middle rounds so the total number of S boxes is not terribly big but it's interesting to optimize it it's interesting to try to expand our permutation to see how big it should be to give us the best circuits for trees and for Starks I think what we have so in our inversion hash here in the left column there's width and we can calculate the formula Bertie much the same formula that alabanza son is used has used for approximating stark approver performance and the resultant performance predictable performance is on the rightmost column and its logarithm of time formula so this should be read that if you use sha-256 for a tree of two to 32 elements then and you need 100 because resistance then I your that proven time should be about to the 32:3 of something if you use Patterson hash then it should be like to the 22 so you see like almost thousand times faster but of course unfortunately in the real in the real world per for the performance increase from chapter 56 is not that big because astrophysicist circuit is very sparse but still if we use our inversion hash we can if we use like default width of 1000 bits we can still be like four times faster should be four times faster than Patterson hash if we if we use and interesting we if we increase the width then we can do better and for 1500 bits and to two hundred two thousand bits we can get best results so 1536 is the best we can get it's like 60% faster than the smaller one so our current proposal is to use this with how many like not very big number of rounds like eight outer rounds and not that big number of rounds and the tree will be twice as smaller for snarks we can estimate the number of constraints which is also interesting so suppose that we use 255 bit as boxes if you want to use snarks on elliptic curves with 255 bit primes if you want 3384 bit primes then you should kind of substitute them and it will be somewhat similar and we can calculate the number of constraints and we can compare with paterson hash which is like 40,000 constraints for the entire trees and if I counted correctly and for this sort of hash for the entire tree if we use if we use 6 s boxes in parallel and for 127 bit collision resistance then we should have only 666 constraints well maybe indeed for a fair comparison we should use bigger prime but I think the order of fact order will be the same so I think this is quite promising and well of course we advocate some additions to a VM or whatever will be used to support natively support the operations in the field basically for verifiers because verifiers in stars and bulletproof they need some parts of the circuit and some some field operations should be supported and optional I don't know if the inter entire permutation should be as a precompiled contract maybe it's not necessary but we will see those depending on whether some checks against the entire permutation are performed to the performance in the contract and if so then indeed a per compile contract would help so this is just the beginning just begin that's kind of the hash function that we cryptographers can design within a short time period but I think there can be designed better or better ones can be found so we can try start friendly fields we can work better with algebraic attacks for example the corner burger burger business attacks are sort of an offender explored and because and as far as they claim to be the best and in the settings should be very interesting to apply exist in Grosvenor best labor a libraries to attacks and see if the indeed kind of perform as we expect and it would be also cool have some to fix some metrics and have some kind of competition that like everyone can suggest hash function that optimize the number of constraints somewhere and withstands security attacks up to know 2 to the 128th maybe designs a miracle tree oriented hashing they already exist to based hashing but maybe there can be something more optimal and also for example maybe 128-bit security is not need that much maybe if the hash function if the proof should be like secure for only short period of time then maybe a lower security level would be nice for example 64-bit security level I'd know maybe 56 bit security level that's like this than we have we can have much again more compact designs and maybe with faster proofs and since first certifications thank you very much [Applause] we have time for maybe one question so I'm sure you've heard about the new designs coming out for the Starks with Jarvis and Friday although they're confined to the binary field how would you describe the relationship between your work in that hmm how what how would you describe the relationship between your work and that how do you see them I've just seen them two days ago and basically their idea is in the am IMC with only one register to insert a fine layer and that's not yet clear for me if this and it withstands algebraic tax because I have some doubt but I haven't found an actual attack so maybe maybe it's indeed secure but I would be very careful I think that third-party reviews I needed another round of applause please [Applause] you