Episode 250: What's the Deal with Hash Functions?

Transcript

[Music] welcome to zero knowledge I'm your host Anna Rose in this podcast we will be exploring the latest in zero knowledge research and the decentralized web as well as new paradigms that promise to change the way we interact and transact online [Music] this week Kobe and I chat with Dimitri kravatavich researcher at ethereum Foundation desk Network and abdk Consulting and JP omasal CSO at Taurus we compare symmetric and asymmetric cryptography and then dive into hash functions we discuss the process of

developing and improving hash functions and explore what it means for a hash function to be ZK friendly now before we start in I want to share that one of our ZK Summit Partners Elio are currently in their third incentivized testnet phase Elio allows for programmable privacy and with this testnet developers can now build their own private and scalable applications if you want to try it out check out their repo at github.com aliohq look for snark OS now Tanya will share a little bit about this week's sponsor today's episode is sponsored by anoma anoma is a set of protocols that enable self-sovereign coordination their unique architecture facilitates the simplest forms of economic coordination such as two parties transferring an asset to

each other as well as more sophisticated ones like an asset agnostic bartering system involving multiple parties without direct Coincidence of wants or even more complex ones such as end party Collective commitments to solve multi-polar traps where any interaction can be performed with an adjustable zero knowledge privacy anoma's first fractal instance nemata is planned for later in 2022 and it focuses on enabling shielded transfers for any assets with a few second transaction latency and near zero fees visit enoma.net for more information so thanks again anoma now here is a dive into hash functions with JP and Dimitri [Music] today Kobe and I are here with JP omasal CSO at Taurus and Dimitri kovratovic

researcher at ethereum Foundation dusk Network and abdk Consulting we're going to be talking all about hash functions so welcome to the show Hello thank you for having us hi Anna great to be here and hi again Kobe thank you for joining me on this episode I know we're going to go deep into the tech so I'm very glad that you're here with the with us happy to be here okay I want to get to know both of you uh let's start with you JP you are CSO at Taurus tell us a little bit about what you've been doing what you've been working on and what led you to work on hash functions sure uh so I've been doing cryptography for maybe 15 years so way before blockchain way before zika posts were

practical and I was not much interested in ZK proofs at the time 10 years ago I was most interested in symmetry crypto and in particular hashing so I started doing a hash function work during my PhD between 2006 and 2009 where I submitted a hash function called Blake to the shastri competition so maybe you're familiar with hash function Black 2 and blacks 3 yeah these two come from the original black design uh I also design other hash functions maybe the best known is also siphash which is ironically not a harsh strictly speaking and I also work together with Dimitri who's here on hash functions

optimized for passwords what we call password base hashing and this led to the design called argon2 so fast forward to today I'm CSO so Chief security officer of a company called Taurus uh it's a Swiss fintech essentially what we do is the technology software and Hardware that banks are using to manage digital assets the cryptocurrency stable coin tokenized Securities and the like so I'm not doing purely crypto also a lot of personal security but I keep you know affording the crypto research I keep at any conferences doing research giving talks and podcasts like this one cool and actually we met for the first time when you I mean I I got to know

your work when you spoke at CK Summit seven there you were talking about like auditing ZK systems and stuff would you say part of your work is audits sure I've been doing a lot of security Consulting and in particular uh vulnerability research God audit card reviews and since maybe 2014 2015 a lot of security audits security assessment for blockchain applications so while it's contentious protocols new ciphers you name it and the last year or two I've been working on auditing zika proof systems which was like I mentioned in my talk the most interesting and the most

challenging topic so you know when you have all these crypto components working together hash functions ciphers polynomial commitments pairings and the like it's so complex but super interesting cool Dimitri tell us a little bit about your journey and what you've been working on sure well I hate to say that but my journey is pretty similar to that of JP I did my PhD at about the same time and it was devoted to pretty much the same topic with a little bit difference that I was yeah I was I did semester cryptography at that time as well but I was not that much on the design side I was on the easier side I was at the site of breaking things so so-called cryptanalysis and died with my

PhD co-authors and with my supervisor we broke a number of ciphers and hash functions and we didn't participate in the shot 3 competition but we continued working on the analysis and then we started a little bit of the design and that's how we designed first this winner of the password hashing competition that JP hosted at that time that the winner was sargon2 and it's now used in many different applications of password hashing then at pretty much about the same time at about 2013 we started looking at Bitcoin what was well like well before ethereum started to exist and we started various anonymity

properties of Bitcoin and then I did like more and more research in the area of blockchain and well this was not like much about zero knowledge I think up to the year 2018 when I was still doing uh design and Analysis of asymmetric Primitives and I was just found a paper about Starks and in this paper about Starks uh elements a song with co-authors they suggested using a hash function based on block Cipher AES and what was really nice about this hash function is that it was the design that I broke exactly 10 years ago and this paper wasn't published because it was

not so interesting so people said well who would like decide to use a hash function based on AES if we have like much better hedge funds so this result was not published in 2008 but it became useful in 2018 and since then I started to look into zero knowledge space and on the wave of this interest I joined ethereum Foundation as a researcher and yeah we do tremendous amount of cryptography research uh at the frontier of crypto at ethereum and I do a little like more practical stuff at dusk Network where I develop uh some concrete protocols that use zero knowledge on a daily basis

because it's privacy oriented blockchain and I also do Consulting in my own company BDK consultant which we founded with my wife in 2016 and working also with my friend Mikhail there so we indeed do audits of a lot of things including their knowledge protocols and and circuits so it's kind of we design things at my first work and then ordered the implementation of this thing at my kind of second and third work that's kind of pretty and you do kind of you get money twice for pretty much the same job and maybe one thing you did not mention uh maybe the Pinnacle of our careers or biggest achievement is when Dmitry and I collaborated on attacking kitsak which

is now known as cesri and there was a cryptographic competition just to break kitsuck we did not break it but we had the best attack and we won a crate of Belgian Trappist beers okay um which was very very fun by the way I want to double check something you just mentioned that in the Stark paper they were using a type of hash function that you had already broken or you had like figured out the vulnerability of so did that force them to change it yes so what actually happened is that uh they designed to start for um non-traditional field it's not like a big Prime field where still using now but they looked into smaller

binary fields and they selected as a hash function kind of tailored for this field a hash function based on the Block Cipher AES block ciphers and hash functions are somewhat similar but they also different in security properties block ciphers are somewhat smaller and in order to not to fall into the Trap of small security level you have to make sure that you this smaller State doesn't pose extra vulnerability and what this dark paper did they made it into hash function in the most straightforward way and this straightforward way was insecure because it added degrees of freedom I would say that can be

exploited by an adversary in order to mount for example a collision attack so this degrees of freedom are unavailable in the block Cipher setting because basically what they did they said okay so in the block Cipher there is a key which is secret and there is a message you encrypt and they say okay let's be both message that you have a key and and the message and that gives you kind of the freedom in the key that you didn't have in the cipher setting and because of that this resultant function becomes really vulnerable and we found this property back in 2008 when we tried to attack AES and related designs and I I was reading the paper like late nights

and I immediately pretty much the same night throw to Ellie and said well you guys you you're doing something really wrong so you should have used a different hash function and early replied well if you you think you should use we should use a different hash function couldn't you suggest it different hash function and I said yes so we we certainly can do it and I have a team we can do the job yes it was the year of 2018 so it turned out that already at the time early uh covertly collaborated with another team from from Belgium who designed a different hash function for them it's it's called it was called Friday and they presented presented it around divcon in Prague and the thing is pretty much the second day

after this design was present me and colleagues of mine from Austria and from Great Britain we found some real good vulnerability oh man in this hash function this is such an interesting way to do business development I feel like that's the job of the auditor like you you break stuff you're just like are you sure you want to work with them you sure you don't want to work with us broken right so we did found the vulnerability and published a paper about it and that's made the Stark team to switch from this Friday setting to something new they actually decided to run a competition in around 2019. I remember that yeah and our new has functioned

Poseidon was one of the entrance to this competition and the sad news like the one year one year later they told us well there was like a third party Crypt analysis from from France and the central French guys decided that your Poseidon thing is not really the best one so this second design from belgians is better so we decided to use not Poseidon but the rescue hash function so we said why so it's like thousand times slower and yeah and just two years ago we kind of devastated we invested huge amount of time into design and Poseidon optimizing here and there and then they said well we of course you did a great job but we

are selecting rescue but it turned out they they did select rescue but they're kind of unselecting it right now I think oh gossip I mean a lot of people use Poseidon today right yeah well they couldn't uh tolerate the the sloth of rescue so from the security standpoint it it was somewhat like a little bit better but not like tremendously better uh but from the playing performance ratio so Poseidon couldn't be beaten at that moment and I think this made people using it I want to take one step back into something both of you said you talked about symmetric cryptography versus and I'm guessing versus

asymmetric can you actually Define that for us what's symmetric cryptography and what falls under that so symmetric is all the crypto Primitives because we talk of Primitives you know the core building blocks our supports the protocols so a symmetric is everything that is not asymmetric an asymmetric is also called public key so as soon as we have a public key and a private key whereby you can generate the public key from the private key but not the other way you're in the realm of public key Kai asymmetric crypto and typically this involves you know mathematics security proofs and relatively slow operations so RSA

diffie-hellman elliptic curve this is all asymmetric uh whereas block Cipher Streamside first hash function brf it's symmetric and fast and I guess ZK Falls in asymmetric as well actually both uh okay components a lot of physical proofs rely on the harness of problems such as DLP so this discrete logarithm problem which is at the core of many public systems but at the same time you have a lot of hash functions and hash functions like algorithms in in CK proofs and typically you have people so like me and Dimitri we are more in the symmetric crypto world because it's a different set of technique maybe different skills different communities so there's

traditionally this separation between the public key and the Secret Key Well similar Community it doesn't mean we don't know anything about public key but we're more specialized in symmetric stuff cool it's also a bit different about how the field approaches into adopting new schemes and protocols right like you mentioned all the time the competition that you have for new hash function right for Blake to when when it was in the competition for a shot three and this competition for uh the new hash function that would be used for Starks and so on so for example why was there even competition for shot three like what's wrong with Shot 2 right well the the history of this uh is

the following so just for the background maybe not everybody knows this concept of crypto competition so it's like a destruction Derby you submit to algorithm and you try to break other people's algorithm without booking yours and it's organized by the US agentinist so the National Institute of standard technology is the agency in charge of doing U.S federal centers but what happens in practice is that what you need standardizes becomes a worldwide de facto standard so except for national standards uh and this organized this for the as block Cipher to supersede the desk Cipher in the in 1998.

and the reason why they organize a shastri competition is because Chateau was not broken but the fact that Xiao 1 was broken and Chateau was very similar to show and in terms of design in terms of operations in terms of the people who designed it it made a lot of people nervous like you know what if what if it gets broken so it's like an insurance and it was also as a byproduct we got better more original faster designs like if you like a black too well blacktube was not strictly speaking a competitor I designed it after because I was a bit pissed that Blacky lost I was like okay it I will do like two which I believe is superior to get stuck in

terms of engineering then people started to use it but yeah that's the short story that I actually didn't understand from your original story that you you are behind Blake and Blake too not just break and then and was is there a Blake three like at what point do you stop is it because of the competition like oh we're winning right now so we don't need to go further or like yeah what what defines you know the thing with harsh functions is the simplest crypto algorithms to design ever It's relatively easy to design a secure hash function and I could teach you in 10 minutes how to do it and you design a very secure hash function cool what is what is hard is to design something that is secure

but as fast as possible because the faster you go the fewer portions you make so the less security quote unquote you have so the game is to find the right trade-off between security security Assurance you know confidence and security because as some people say attacks always get better uh so between security assurance and speed for different Notions of speed it can be speed on software speed in hardware and speed as a circuit as an arithmetic circuit which is the reason why we have these different families of hash functions suppose I don't rescue which are algebraic which are you know ZK circuit oriented hash functions uh very different from just three and Blake

and the like I would actually add that this landscape of hash function usage and this performance competition it has changed significantly with the introduction of vector instructions in modern CPUs because the designs of hashes that came in late 90s and in the early zeros they were like sequential they didn't make use of pearl of or vector instructions they couldn't work on really long memory words like 128 or 256 bit and at some point it was difficult to compete if you are a sequential design but if you start designing something which can be easily paralyzed or

vectorized like JPS design Blake 2 and Blake 3 you easily beat uh this old stuff by I think Vector of 10 or or even more and you so quickly become much faster you so quickly become not a bottleneck anymore in any application that would potentially use a hash function that you could use your hash functions slower than it could be but much more secure this kind of means that instead of like making it like 10 times faster you make it only five times as fast but twice more secure and the security margin which you have in your hash function between like the best possible attacks and the actual design

is so big that people even don't start bothering trying to attack it so because of that we see quite little progress in crypto analysis of traditional hash functions that they become kind of so fast that we can introduce much bigger security margin into them and uh they are not a bottleneck yeah that's a great point and this leads me to the answer to another question uh why blacks 3 so the difference between black twin Black 3 is that Blade 2 is employing this you know parallelism CPU core level parallelism whereby you do several instructions at the same time in the same CPU core potentially we have different RS

continuing it so you have vectorized instructions uh Black 3 goes one step further it exploits multi-core computing so you have a partisan instead of in the sense of using multiple chords at the same time so the more course you have the faster you you can be and it's also acceptably fast if you have a single core I want to ask you a question about like zkps and hash functions because you talk about like ZK friendly hash functions but I'm just realizing that like I'm not entirely clear where they work together is it in the engineering using zkps or is it in the Z like in the circuits themselves where this these hash functions are actually being used I think well we can simply say they're

used in two capacitors so one usage is uh directly in circuits uh something like you design a protocol an algorithm that uses a hash function and then you build a circuit of it and you prove that the algorithm works correctly and at some place inside the protocol there is a hash function for example you prove a set membership in the miracle tree you prove that you know a leaf and a miracle tree and you you prove that there is a path from a leaf to the root in this miracle tree and this is used for for some kind of set membership for example you prove that you are in the white list

of possible traders of some crypto assets or your proof like in Z cash that you own a coin in some tree and this coin has not been spent yet so here hash function is just part of the algorithm part of a circuit recently emerged another usage and this one in recursive I would say simply recursive snarks and incrementally verifiable computation schemes which are based on recursive to apply and music is snark two parts to chunks of a computation and inevitably you have to use a hash function at every step because well what

happens is that you have to construct some challenges uh in order to compress uh the chunks into kind of a single piece of a computation that you verify succinctly you can press and in order to prove that you have compressed correctly you have to use a challenge and in order to generate the challenge you have to use a hash function and you have to have all of it inside your circuit because you do it recursively and because of that a hash function started being used as part of cursor snark proof again this can be in a form of a miracle tree but it doesn't have to be numerical tree it can be like anything that helps you to generate the challenge or to prove that

you open the commitment if your commitment is based on Miracle trees then you use a miracle 3 circuit but it does have to be based on it based on that grid overview concretely what it means for the hash functions why do we need to use different hash functions for these applications so I would say that maybe two main aspects from a technical perspective so Dimitri mentioned that you have hash functions into circuits so you have a program and you express the program as a circuit so you want a hash function that is small in the sense of having very few elements of the circuits so typically um constraints that's one thing so if you take shastri or Black 2

or cassag they're not designed to minimize the number of constraints they're designed to be fastened software so they will not be optimal for that circuit use case and the second aspect is that oftentimes we walk with uh you know mathematical structures typically finite fields and we process elements of finite Fields so if you look at the general hash function it just works with bytes so you would have to translate finite field elements into bytes and the other way which in itself is also a rock prawn and a bit costly so ideally you want hash functions that rely on field element because field element is that's the native language of many proof systems just to check that

like so are you saying that if you're using hash functions in recursion versus using hash functions within a circuit you would actually use different ones like you wouldn't use the same one for both because they don't have the same properties you may use a different one for recursion uh for example if your cursion implies to have to compute a whole Miracle tree and proof well formation of this miracle tree inner recursion so not just so your circuits that you prove in the recursion consists not of like a single path in a tree but of a tree of a full tree and this also means you have to compute this

tree while making a proof so in applications like set memberships you compute this miracle tree like in zika actually computed like incrementally but if you for example decide to compute a miracle tree for like four several million of transactions instantly that will take you quite some time and in recursion if you're supposed to compute the miracle tree over quite big number of data blobs like hundreds of thousands or something then it becomes a bottleneck by itself so not like not just the proof time but the moment where you have to compute the Merkel 3 first before you even open some elements in

this and when you face the problem of computing Miracle tree fast then your hash function must be fast enough for your approver to sustain for example this happened in this fractal recursion scheme where where they computed a full Miracle tree at every recursion step so they they used Poseidon because they later proved Miracle paths in this tree so they wanted that proof of America path is compact has let has few constraints but the fact that they had to compute this miracle tree first made a big overhead so they they spent

at the very beginning they spent 99 percent of time just Computing this tree before they even proven anything about it and this of course emphasizes that Poseidon as a as a hash function which you just compute on a CPU is quite slow so this 99 percent would never happen if they used shutter 56 for example or for Blake two or three of course yeah I think this is a good time to maybe talk a bit about the requirements from hash functions because we we talk about a few different ones right now and let's say what are the requirements in different environments but um let's see maybe the what what is their usefulness in in different places

so we talked about the zika shoes of it right when they were using for some from cell membership in with the miracle tree and if we recall like when 2016 before Poseidon existed and all that that that was most of their proof it was like 40 seconds and most of it was Computing shot to hashes and basically one of the biggest breakthroughs that they had was when they moved to sapling was switching it to a Pederson hash which is interesting because that construction is actually not really symmetric crypto anymore

so what's what's like the basic difference between them like why wouldn't you use that one everywhere right I think they faced quite a complicated trade-off so one a clear requirement that you have there is of course a security of a hash function so you you must not be able to find the Collision or Worse enough pre-image faster than for example two to the 128 operations if you declare a security level of 128 bits and this security requirement is actually quite well defined so you you don't have to think about a particular zero knowledge proof

system or a specific usage of a hash function or to figure out if you have hash function is secure or not so it actually even doesn't matter much in which Hardware you compute your hash function because okay there's a difference of like maybe even a factor of town doesn't but this clearly doesn't affect the security if we talk about 2 to the 128 operations or something like this so the security is like very well defined and one clear requirement is that the hash function must be secure so one reason why zcash selected the so-called Paterson hash is that the security of this design it stems from a number Theory problem of the security of Discord logarithm and this is in some

sense better than the security of a regular hash function which we don't reduce to any like popular assumption but the security of a popular hash function stems from how we call it public scrutiny that an ability of the entire world of cryptanalysts to break it for a long period of time but other requirements are kind of more subtle so the second requirement that that came into application was clearly succinctness in circuits so that your hash function must be short enough that it should have a few constraints we would say so but even this is not really well defined because what people really

wanted is a small prover time but the proofer time is not by itself really well defined because it's somewhat depends on the number of constraints but it also involves some other characteristics in particular when we talk about not proof systems like growth 16 but some more sophisticated like plonk then you have to take into account Gates algebraic degree of polynomials that are involved the number of columns and so on and so forth so the performance of approver is really really difficult to quantify here so when we for example from the design standpoint it's actually very difficult because on

one hand you want to design a hash function that could be used in many applications with many proof systems but on the other hand it turns out that a hash function that is good for one proof system is not that good at the other proof system so for like for the design point of view it's both goods and bad if you design the hedge funds and just for a single proof system it doesn't allow you to publish your hash function at a really top conference because people will be less interested the trade-off of optimization as soon as you optimize for something then you optimize for one use case and not for the others but yet flopping what could be mentioned it's funny if you take someone from the you know symmetry community and you ask

them give me the name of a one-way function they will think one way a function they would say get suck black what not if you take someone from the public Key Community from the academic public key they will sync one-way function well discrete logarithm uh something like Peterson hush because initially if you look at the foundations of crypto the concept of one-way function was defined very theoretically and is instantiated by things like discrete logarithm was RSC is a Trader function and I had discussions with people from that Community telling me ah you know I don't trust AES because there's no security proof yeah and likewise ah we can trust just free because look at all

this massive bits and bite shuffling doesn't look secure to me but I think if there's one message for the audience here is that you don't need to worry too much it's not that there is no proof or that it might be insecure it's just that the construction doesn't lend itself to the kind of proof we know today how to design in some sense it's nice that you have like the the biggest um let's say back Bounty other right for these hash functions in the form of cryptocurrencies right exactly the proof is in the pudding you know um yeah and there's also the topic of let's say Quantum resistance that maybe some match functions at least are plausibly should stand better against and that's a good

question because when it comes to signatures only you can always wait for the hypothetical day when we have a quantum computer and just switch back to switch to plus Quantum signatures but in the case of privacy preserving proof systems is different because you might be able to to open the previous transactions the day you have a quantum computer so it might be a more pressing use case for post Quantum so if you take things like Starks there plus Quantum mostly can you tell me like currently what hash functions are primarily used you've mentioned a few of them like the Shah 256 like in ZK systems are there some standards that people seem to

gravitate around that they do feel like they can trust them they have the right properties what would you say like today with the new systems like what is the most common hash function being used from my perspective having seen a lot of projects a lot of code bases a lot of audience that I did positan is the clear winner here uh what person is personally is not One Singular harsh like Blake to it's a family a framework to design hash functions you can tweak the number of rounds change the finite field but ultimately the same design family yeah accuracy because I don't understand the main hash function today in terms of implementation in terms of deployment cool you were just talking though about like how they're battle tested you're

sort of like you put them out there it seems like and you're waiting for someone to break them but are you doing some sort of formal check are you sending it to peers being like please break like I'm just curious like when you put it out there it seems really scary because you're like it's good until it's not why would people trust it yeah that trust is important trust you know it takes a number of signals starting with who designed it starting with how the specs look but there is no you know when we talk about symmetric crypto or hush functions the ones we're discussing today we don't have complete Security proof because the question is what is security is Collision resistance to the randomness and distinguishability second premise resistance so it's very hard to have you

know a comprehensive proof however what we do have is proofs for specific classes of attacks and in particular bounds complexity bounds on the harness of doing certain types of attacks such as certain classes of differential attacks and if you if you look at the Poseidon paper I think most of the paper is devoted to explaining arguing why the design is not vulnerable to certain types of attacks including the algebraic attacks which are maybe the most relevant for Poseidon and once you have this kind of assurance that let's say you know four rounds of your function will be safe then you add some additional computation what we call security margin in case someone finds a much better attack

but that's if your function is completely new if 10 years later there is no single attack no single incremental Improvement maybe it means that function is not too bad but the problem is that people are reluctant to reduce the number of rounds and that's where I added this paper called too much crypto or I said that you know we could save a lot of energy on this planet If instead of doing 20 rounds of Cha-Cha we we did half of it but it's almost like the the case of like flight and airplanes where it's like you have to have so many redundancies you have to have so many backups you have to have so many things in those odd cases that like someone finds a way to get through some of these

barriers yes defense in depth security controls and what scan me initially with no the blockchain world is that people design a new proof system they got it and the day after it's deployed and tons of value is based on it and it makes people from Academia you know crazy because in Academia historically we would have to wait maybe 10 years and have many papers many conferences about a cipher before using it and now it's like yeah the proof is in the pudding it's uh we deploy it and oh just hope for the best it's very Cowboy territory it feels like um I like it because you know it's the ultimate test

there might not be academic papers at your Crypt but you know that if people break it they can steal one billion dollars like like Kobe said the best Bounties in the world in a way exactly um you talked also Dimitri about like breaking some of these yourself so like in the design of these do you learn how to do them mostly from breaking the other ones yes like is that part of the process of building hash functions yeah sort of so well some people are born with the capacity of design and good things but most of others they actually learn from breaking so you're kind of supposed to break things several times before you learn how to design a good

one and indeed so after you participated in a few Krypt analysis paper you can try to design something something good and of course this uh competitions uh they play a really major role as uh only the the very best designs survive actually I would like to add to the previous comment by GP about also too much crypto indeed some cryptographers are scary of not only of modern hash functions but also of older hash function that they don't have a security proof but here we would add that this hash functions I usually should not be

considered just as black box so they when we mentioned some number of rounds this rounds means that the hash function is built as a sequence of more or less identical components and the history of design and Analysis is shows us that usually how attacks progress you you break like more and more of this number of rounds until you you reach the full hash function so this kind of plane with the number of rounds is not exactly what you have like in airplanes but it's more like selection for example a width of a wall when you design a skyscraper so it

was figured out like 150 years ago how much concrete you should put into a wall if you build like a 100 meter up skyscraper and you know that there is some kind of a security margin there uh like you you could have like 20 percent less and I'm pretty sure it will stand because there must be security margin yeah but is is it normal concrete or reinforcements yeah yeah exactly I just I'm just realizing where you're getting that name from um we will talk about that shortly the reinforced concrete which is I'm actually curious about when you talk about the this kind this kind of lineage of you know how to design hash functions

you you've designed Poseidon right like you're talking about the kind of properties and the kind of analysis that you've made and the attacks that you've shown that you're not very vulnerable JP you mentioned like that Dimitri in the paper showed that a list of attacks are basically not applicable to Poseidon or to the family of functions let's say and I'm curious because Dmitry you mentioned that even the hash function that was this a a as best one that the tarks paper worked on weren't they doing the seminalities or even in the in the short time where algebraic hash function functions were

worked on there were even some some of those that were broken we saw that in your talk in Zeke's Summit 8 right so weren't they doing the same analysis or were you coming up with new attacks or how did that work uh well in some in some cases they indeed did not do pretty much the same analysis but also and some other in some other cases like when you break things usually you break something that has not been broken before so you you seek as a capitalist you seek for a place which is like the most novel The Land the least explored and to try to find the bug there you try to find a

mistake uh like people decided to use something new so they kind of they design a new hash function there must be something new there so it depends you can use like 90 percent of old and 10 percent of the new and then as a designer you concentrate your kind of analysis of this new ten percent and this of course makes the cryptanus job much harder because like much much smaller attack field but uh what was in the start paper and with some early algebraic hash designs that they had to do something almost completely new they had very little to rely upon and because of that we had like quite a few places

where you could you could try to find a problem with and because of that it's kind of breaking them was by kind of somewhat easier so it still requires a little bit of wires like intuition where you can very should expect a problem but when you design something completely new there is of course very big room for for bugs like when people started building like real Road Bridges they they fell like every second year because it's like something completing you you never built a bridge for such a heavy thing like a train but since then people have learned and now we have we can design algebraic hash functions like improving upon Poseidon and we we can build upon its security uh so that like we can

introduce like yet another component which can be the only novel thing compared to the previous designs and then we can concentrate our own analysis on this component and then cryptanalysts will concentrate an analysis on this component because they they know it will be very hard to find some problem in the parts that have been battle tested yeah so like when you when you write Poseidon you you you say you know I covered all the attacks that I know about and that all the community knows about but that should give you this much confidence like you should still work really really hard to attack this so I think that two reasons if I'm the devil's advocate here maybe two reasons that make people

nervous for getting algebraic hashes the first one is that all cryptoysis is based on finding patterns finding structure like mathematical structure structures or behavior that we're not aware of as a designer because yoga as a designer is to break any correlation any mathematical structure any symmetry in the input or in a set of inputs so that the outputs all look random and uncorrelated for whatever type of correlation and the challenge is that if use algebraic functions you use algebraic groups use algebra use math using structures and the question is could we leverage some of these very structure to to break the hush and which brings me to the second point

that there's a class of methods called um well equation solving and specifically with the chromatar basis techniques and these are classes of methods where it's very hard to predict the complexity of the competition you're like okay I have a bunch of equations and if I want to break the heart I just have to solve these equations but you don't get directly an estimate like you need to do the 100 operations or whatnot it's mostly empirical so as as soon as there is uncertainty people can speculate and say oh what if yeah but you know what if we find some solvable equations uh and all the challenges to demonstrate that these attacks could not will not work cool the

Dimitri do you agree yes yes I I certainly agree so this uh there is indeed this problem that the best algebraic attacks well they kind of fall into two categories that are like more known attacks like interpolation without going into details it just basically a solvent of an equation with one variable and we kind of know how to solve equations with with just one variable so all this algorithm of uh solving polynomial one one variable equations are well known they're com their complexity are well known but when talking about multiple variables then the best algorithms are much less understood they are very ad hoc so the best algorithms for grubner bases

they are not described as like compact algorithms they described as a series of papers or Worse enough they exist only as pieces of code and proprietary systems like magma and because of that of course it's difficult to trust that they will not approve improve significantly so I think from the theoretical point of view all this equation solventies and be complete and you can't have like a generic solver which is super fast but in particular cases it it may be super fast and the fact that we don't understand this algebraic uh grammar basis algorithms really well and we don't we we don't have good mathematical Machinery to

estimate their complexity it makes people somewhat somewhat nervous that we rely when we select this number of rounds we rely on complexity estimates that may be off in in any direction so they can be often like actually they are worse the complexity is much higher which essentially means that your hash function can be faster or Worse the complexities is is lower and this means that your hash function is less secure well kind of evidence now and like there is consensus that the complexity of this algebraic attacks is underestimated that their real attacks are more expensive they require more memory uh not only

like computation time but they're also like memory uh Hearts this this attacks so that the actual complexity is probably higher than we expect and this gives a like extra confidence but this of course is not like the level of confidence we we had in the designs from the past like Chateau or AES and you remember the attack that broke AES in 2002 so guy came up uh with this paper like hey yes it's broken that's the end of the world you know repent because as the AES block Cipher is moderately algebraic and this guy he had this paper it was very optimistically so I could break a yes by solving the questions

but he had no evidence no proof of concept he tried to publish the paper and that a lot of people you know demonstrated that it was very optimistic uh to be polite uh but there were a line of attacks on the AES that choose what Dimitri mentioned linearization uh algebraic attacks German bases but it didn't go anywhere it's like oh we just have these equations we just have to solve the equations because everything can be you know expressed as equations so maybe it's good to start describing how algebraic functions or algebraic cache functions look like um because we we understand that they're so much more efficient for music APS but

what's what's so special about them like what what their structure looks like and what's interesting about them uh okay maybe I should uh try to explaining a little bit how Poseidon works yeah without drawing anything without involving any math so the idea is that there is an input message that you want to hash and how it works uh you interpret this message as a series of field elements if you are working in the prime field so suppose like there are two field elements you want to hash and get one field element as an output so basically you can press two into one like a Milky three let's say like a Merkel tree

exactly uh so how you do it you to prevent one specific attack you do you can construct a state note of two elements but of three elements and you said that third element to be equal to zero uh then what you do is that you apply very uh simple uh transformations to this state so you have like three field elements so what you can do with field elements you can for example add one to another you can multiply one by a constant you can exponentiate uh one to some power and of course exponentiation is expensive in both circuits and plane performance so what we do we just exponentiate to something

uh which is invertible because clearly if you exponentiate and this this information has collisions then the full hash function will have collisions so what you do for example you exponentiate to the power of five because five is usually uh co-prime with the field size minus one so what you do is that you permanently mix elements of the state you just add one element to another with some catfish since you basically if you if you like thinking about it as vectors and matrices then your state is a vector and you multiply it by a matrix of coefficients you multiply it by a matrix coefficient and then you exponentiate

you don't actually have to exponentiate all of them into some power you explain it just one of them into some power just take one element and to compute the fifth power of it so you multiply the state by matrix you take a fifth exponent of one element multiply by state Biometrics you take you exponentiate one element to the power of five so what you get eventually is after making the sufficiency mini rounds is that uh you still get a function uh and of the resultant State you take one element doesn't matter which one suppose they can take first then

uh you cannot really invert it because you cannot uh figure out what the rest of elements are and you cannot uh make them just arbitrary elements because when you invert it back you will not face a single zero element that you have put in the state and the very first iteration and the property that we want for this to be secure is that the resultant function has so-called High algebraic degree and what actually happens is that if you take one element and compute the power of five uh then you have like x to the five then you mix it with other elements and if you compute again if you

exponentiate it to the fives then you will have an equation of degree 5 times 5 25 after doing it one more time you have an equation of degree 125 and so on so you you just make it grow till the time when you can't possibly solve so because if you want to find the Collision or a premature to the hash function what you just have to do is to solve a polynomial equation and you just make it grow to the uh to the threshold where you know you can't solve a polynomial equation of this big degree and this degree is something like again to the 128 and from this since degree grows more or less by the factor of 5

every time you can easily calculate how many rounds you need Governor basis attacks they come from interpretation of this process separately like you look into individual rounds they all of you say it's like polynomial described in there all of degree five and then you make this system of equations of degree five into a single system and then you try to find the so-called globular bases well that's better not to talk what exactly government basis is some kind of a set of polynomials that kind of divide every polynomial from a system but what's important there is that as the number of rounds grows it also increases the complexity of this grubner basis

attacks because what happens is that you have to solve bigger and bigger set of equations and this makes at some point again this groupner-based attacks inapplicable so when you design the hash function then you select the number of rounds what you simply do you just increase this number of rounds till the point where above the degree is very high and the estimated Governor base attacks are also of high complexity because like two main equations and it's actually the same because uh people say yeah there's algebraic hashes and non-algebraic but if you look at Shot 2 and the like they work with bits they work with gf2 finite field elements and you can

describe Poseidon in terms of gf2 elements you can describe sha256 in terms of any finite field element because of the universality of equations you just end up with more questions so it's not that you obtain a strange presumably less secure function with one technique or the other is that the representation that we use to read the spec to God is is different and has to be succinct because the underlying equations are exponentially large this is interesting but like or I think it's starting to answer a question I've had for a little while since you've been speaking which is sort of the rounds we didn't really explore rounds that deeply like you've mentioned them a few times I have a question about them like are they

all the same like every time you're doing it are you always doing the same thing are you doing a different thing in different rounds well they they are a little bit different so and this kind of little bit differences sort of a protection against certain types of attacks so they're like there is one class of attacks that exploits the fact if all the rounds are exactly the same uh basically the exploitation is pretty much similar that you can like apply one round to the input and you apply one round to the output and then you still get like a valid transformation that's a so-called slide slide attacks what you're saying is like every round can be slightly different and you're you have

these techniques to attack it and you're adding extra rounds so that it just sort of gets out of the range of that attack technique but I do Wonder like are new techniques always being introduced as well new attack techniques that can like handle more rounds like it seems like there's sort of two races like how secure can you make this how many rounds can you add or how well can you add variety into the round so it's super hard to track versus these attacks that like you mentioned one repeatedly but like could there be another one that's like in development right now so there are some classes of attacks that well Dimitri knows very well is that the attacks that try to walk around the number of runs for example what we call meet in the middle or rebound attack

we exploit the Run structure you can have bypass so to speak certain rounds but ultimately the more rounds you have the more security so if you have like an infinite number of rounds it should be fine unless you have attacks like the slide attacks that Dimitri mentioned unless you have a structural weakness but then you have a different design paradigm which is what reinforce concrete is doing you have two main components of around and you have one very different type of front that provides another property because we don't design runs randomly there are different properties we want to achieve that's what we call vertical security and horizontal security also called confusion and diffusion because you can be very solid

in One Direction have very high degree of your equations but you want a question that not only have a high degree but equation that makes many of the input many of the components so equations that are quite dense and that combine each component together okay but you want all these combinations to have a high level of solidity uh so to speak so which translates into algebraic directory but are you also like in designing these trying to reduce the number of rounds this is the feature that I'm not really understanding and what you're describing because like what I just just heard is like well we added enough rounds so that they can't touch it but yeah is there also pressure to make less rounds like that's what you were talking about earlier right JP you

were saying that like that's why do we have all these rounds we should just get rid of some of the rounds yeah but I got quite some pushback because it was often quite emotional arguments it was you know kind of what-if arguments but then you know now with the applications we have just some applications where you don't really care about maybe a 50 speed up but at scale uh where every nanosecond counts in a I don't know big cloud systems uh it can have a tremendous impact if you're an optimized speed of your hash and now it's even Amplified further in the zika proof systems because of the order of magnitude of the overhead of the circuit process I remember that very strongly like when we were working on deploying Mimsy even like we were

choosing the number of rounds from Mimsy the general guidance is not take a security margin like add 20 more rounds you know why not right oh wow it's it's performance over it in two places both when you create a proof like when you compute hashes when you compute numerical three but also when you need to use the tree itself in the smart contract and that that becomes very costly and very expensive um so that's that's annoying and that actually brings me back to the performance discussion because you you mentioned that you know this is really nice when you design functions like Poseidon because you work

on field elements and then you do let's say low degree exponentiations and some arithmetic operations and that's very efficient in the circuit right like because circuits works really well with arithmetic operations at least the popular ones crowd 16 long they work really nicely with those um but something LED you to to design reinforced concrete right which targets a different trade-off a little bit yes so I would say that well if we first talk about this number of rounds again I would say that like in the design process this selection of number of rounds is not that difficult so how it works usually well how it's for example

it's happening right now in in our team of designers uh we are thinking so we have like some start and point like I I say okay I have starting points so let's have this round and let's iterate it for like 10 times let's have 10 rounds of of this kind and I say well we need 10 Rounds because uh the security will be sufficient against the attack we we know against the attack we have developed during the course of this design and someone else says for example GP says okay I have a different round structure so it will be like 20 percent faster and I reply well okay it will be 20 faster but what about the security so if

we if we use the same 10 rounds will it be equally secure and because well not exactly the security will be like 30 percent less so we would we would have to have not like 10 rounds but 13 Rounds so for to have the same security and we we realized that from the performance point of view even if like every round is somewhat faster uh we need more of them so that like eventually uh the new designer like the second version will be slower so say okay well this probably will not work out but maybe we can combine the best of the world's kind of questions and like the better one and then we like think and think further and eventually we select something that is

like fast enough and and secure so we've kind of gradually increase the the performance uh while still having sufficient security I want to ask something like we've mentioned reinforced concrete a few times I don't know if the listeners are familiar with the work but does reinforced concrete is that like an add-on to Poseidon or is it like a different category is it a new hash function like is it is it just like a different place well why one might say that in Poseidon so this number of rounds is quite big so we have like more than 60 rounds and this is exactly because we need this algebraic degree of a function to grow up to some needed level up to like 200

to the 128. reinforce can concrete tries to replace 90 percent of Poseidon with just one new round oh so instead of like we take like 60 60 out of 65 Poseidon rounds and replace it with one round with but which potentially has the same algebraic degree just the round itself is very different from this point of view it can be seen like an advanced uh like a very next version of Poseidon but kind of from the design point of view from the analysis this new round that we introduced it's of course the very kind of fruity Target for for channels so we we can't recommend it for usage

immediately because like of course every single cryptanus in the world when she when he sees it they immediately go into try to break this particular new addition in the design well I have a question too Dmitry I think this tricks are actually what they do in reinforce concrete is let's say completely break the Symmetry break the structure by using an operation that has nothing to do with your underlying Mass structure but the problem is that since it has nothing to do with it it's way much slower to compute well if you work with finite Fields so my question did you think of this trick in the design plus I don't and if yes why did you discard it I think we did not uh because we

couldn't find a way to describe it in constraints and like r1cs constraints that we worked at that time so at that time I was not when we designed Poseidon I wasn't familiar with other Ziggy proof systems so while I was aware of starks but still in Starks you can have like not an R1 CS constraint but on almost an arbitrary polynomial expression but it's still about like multiplications and I had no way kind of we couldn't decide couldn't devise a way to break the algebraic structure because we didn't know how to efficiently implement

it in a circuit and we were also were familiar with one such attempt that was exactly in this Friday design that we broke that the guys exploited some similarity between uh binary Fields based on on bits and binary Fields as like polynomials and we were afraid of of using this kind of tricks and that's why at the time of Poseidon we didn't go for it by the time everything has changed when we learned about uh ziki proof systems that could use lookups and this gave us kind of extra tool to start with I have a very practical question how should people choose parameters

because you know when you shut two and like all these traditional old functions you have test vectors you have very accepted and known designs that people use and contest against but with Poseidon and others you have all these constants that you have to choose then you have to derive and all that are there any standards or any efforts to gather the community around not Merchant that's a big risk oftentimes I did code reviews of this kind of you know custom as I don't know and there are notice vectors

to compare against your implementation so what what ground truth to use so what some people do is that the abstract art Poseidon as you know a framework working with arbitrary finite fields and they implement it for a known instance of Poseidon this specific Finance with this number of rounds and they check that they have the same output as the other implementation and then they just customize their new design to work with different parameters which gives them some assurance that they are doing the right thing but we've seen some even impose I done some small mistakes like you know getting the Matrix Vector product incorrectly or things like this are there like risky parameter choices like what can go wrong

well if you make too few rounds of course then it's more it's more in the usage of the hash how you use it if you hash multiple inputs how you combine them I think there there is one vector that can be like realistically dangerous so in Poseidon we use matrices to like we use a single Matrix to multiply a vector and it's possible to make this to design this metrics in securely so that there are some invariate subspaces there so when you exponentiate this Matrix it it has not a full rank at some point and kind of reference Poseidon matrices they

don't have this problem but if you generate them randomly there is kind of non-zero chance and can non-negligible chance you do it wrongly so you you have to just make a simple check for for it so there is in the reference implementation of Poseidon there is a simple script that would check your metrics that it doesn't have this vulnerability I think the paper describes it too yes yes and there is a paper that attacked this non non-reference matrices and they should they show that there can there can be problem so this is actually this attack that that we missed when when we designed a hash function so this attack

we didn't we didn't think about properly but fortunately the default mattresses we we Supply they didn't have this vulnerability okay that that that's lucky and um when you choose the the coefficients or the elements in these metrics do they also affect the performance somehow or they just completely random and they don't matter for performance I think they do affect the performance uh but it's possible to to select them uh as small constants so this is not a reference version I think in the reference version they are like big Prime field elements but it's possible to make it very safe in the reference

yeah yeah but it's possible to make them small actually we have we can select some sub-metrix of the AES uh block Cipher and they have like Ephesians three two one and so on and it will be most likely okay you just have to check it with the script so we didn't see kind of this when when this becomes a bottleneck so it may be a bottleneck in some circumstances so you can you can make metrics multiplication a little bit more uh optimized so in the in the sort of hash function world what else is happening and maybe what do you see on the horizon so I would say like uh indeed with introduction of Mimsy Poseidon uh rescue

Friday and other designs for the zq world the attention of cryptanalysts and designers has somewhat shifted to this new hash functions because they look like low-hanging fruits for many ones and people are somewhat tired of attacking the old designs that not much happening down there and what becomes interesting I think is the development of new zero knowledge proof systems because if you design a hash function tailored to a particular zero large proof system it can become really really fast for example if you take Poseidon and try to optimize it for Planck if you for example design IOP which handles just this Poseidon circuit you can make

approver like 10 times as fast compared to a regular plonk prover with a Poseidon and I think what we should expect in the near future is that the design of hash function tailored to some specific applications where some novel proof systems are used so new proof systems appear like almost every month we have Nova for example we have new lookup arguments like like caulk and and its relatives and we should expect that there will appear hash functions that will make use of operations that are admissible in this in this proof systems and that try to optimize themselves

further and further to be used only in some like very limited set of proof systems but still there will be fast enough the problem of course with it is that it will be difficult to criminalize them because we might have too many different hash functions for any new every new application when I have a new hash function it's this is of course bad because we can't afford sufficiently number sufficiently many Crypt analysts to look into this hash function and they will be much less battle tested and it sounds like there's no standardization in that case so you don't get sort of that confidence that you're looking for exactly because the proof systems evolve

so quickly we can't have a standard there because we can't have sender there we can't have a standard hash function because hash functions will try to catch up with the development of new proof systems to be like fast and tailored for them but this of course we will have this trade-off between performance and cryptanalysis that we can have much much faster hash function but the amount of crypto third party Krypt analysis we have for this hash function will be smaller what about you JP yeah you guys covered uh it covered quite a few points I had in mind as well regarding standardization as Mitra mentioned we can expect to see different hashes optimized for their use

cases because unlike you know general purpose hash functions does a field where first of all there's a lot of competition between projects uh other projects we know and where every single small incremental speed up has a meaningful effect on the user experience on the cost on the cost in terms of gas and the like so even though Poseidon is kind of the de facto standard now we can expect people to optimize it for every single use case that they have but it doesn't mean we're not going to have a kind of standard semi-standardized way of framework to build hash functions I think we're pretty Converse to maybe a handful designs and then we'll hit diminishing returns and people will stop working on

new designs um which brings me to another Point um maybe at dk8 the GK Summit in Berlin there was this great talk by omertion of it's about Hardware optimization Hardware implementation and I know that the trust of a harsh is quite important when you have to design uh Hardware Hardware design because you have to set it on a harsh at some point and you have to worry maybe at some point about interoperability because we see many people were using the same code as simple as item code we also see people who just re-implement stuff for the sake of it but maybe there will be some you know vested interest in using the same tools at some point

um and also so we briefly touched the topic of rainforce concrete I think there's a lot of potential in the the trick that Dimitri and his colleagues are using to have this component that is breaking the Symmetry and the challenge challenge here is to estimate uh what security you gain from it and how to do something that is relatively fast or not too slow to implement as a circuit or whatever constraint system you you use so I mean no offense to Poseidon but I expect that this kind of design will manage to outperform but they don't like designs uh if we know how to do it right and the great thing is that it will go faster and deep your academic environment because people will just deploy something and then that one is

wrong and someone will break it or not right yeah or not yeah I think to be completely honest I think that uh one thing that would make a difference in order to get this actually happening would be to get the tooling for deploying local based systems more practical that's just hard to do today but it's getting there so that's nice cool Dimitri you did a talk at the ZK Summit 8 and JP you did a workshop I'm going to have both of those videos up by the time this podcast airs so I'll definitely add those links in the show notes if people want to explore a little bit more of the work you're doing and I want to say a big thank you for coming on the show and sharing with us what's happening in hash function land

and also letting me ask a bunch of questions I clearly needed to ask to better understand how this works so thanks a lot thank you so much for inviting us and oh thank you Anna thanks guys thanks for talking about hedge functions it was super interesting yeah so thanks a lot and thank you for being our 250th episode guests this is kind of an exciting one I want to say a big thank you to the podcast team Tanya Henrik and Rachel and to our listeners thanks for listening