ZK9: Poseidon2: A Faster Version of the Poseidon Hash Function – Markus Schofnegger (Horizen Labs)

Transcript

foreign [Music] so Marcus is going to be telling us about Poseidon 2 a faster version of the Poseidon hash function we actually learned about Poseidon 2 also at CK hack because some folks implemented it so yeah take it away so yeah let's start so first this is Joint work together with Dimitri and Lorenzo from ethereum and ponos and yeah welcome this talk will be about Poseidon 2 which is a faster version of the Poseidon hash function so let me first give you a very short motivation so Poseidon the hash function some of you may know it has been well

used in practice recently in the last couple of years and why is that well it has proven its efficiency in in many many use cases sorry um so it's also implemented in many CK protocols and well uh the good thing or the nice thing about Poseidon is that it can be represented by very low number of constraints in well most proof systems not all of them but most and it also has quite good plane performance of course not like Shot 2 but it's good for what it is however when designing Poseidon when we designed it like four or five years ago already I think there were some things we completely ignored so we just focused on rank one CS colors or rank one constraint systems but we just

completely ignored for example the the plane performance or other proof systems and in the last couple of years we asked ourselves well how can we make it faster can we even make it faster while still being very close to original design and maybe even just as secure as the original design and we're going to talk about that in this talk but first let me give you a very short recap how the sound actually works so it's essentially a cryptographic permutation you can see the design on the right side here and in the beginning we have this we call them full rounds because we apply the S boxes or the non-linear functions to the whole state then we have some partial rounds and then we again have these full rounds and these monomial functions for the S boxes and the thing the important thing

is that every Matrix so every M this is a matrix multiplication is actually an MDS Matrix and all these things for the implementation then gets used in a classical sponge mode to for example build a general purpose hash function or even encryption if you want all right so these are the observations we made and these are the the most important ones these MDS majors are actually quite expensive so they're very good in terms of statistical security this is related to things like the branch number and so on uh but actually it's for our purposes of course some something like too good so it gives very very good security but higher than can actually be achieved so our question was can we find a cheaper Matrix which is more efficient to implement and more

efficient to compute but which still provides the same security level um yeah the second observations then we can also use all of that in a compression mode which has done has been done also recently for example in in Jive like half a year ago all right so first in a nutshell what are the changes well you see these uh highlighted in blue we essentially we essentially exchanged the matrices with uh with two different ones so first we have the me Matrix which is used in the full rounds and then the Mi one which is used in the partial rounds and we also add an initial linear layer at the very beginning I will come to that also in a minute so why do we do that well in some settings it can improve the performance by effect of up to four depends of

course on which state size you have which prime sizes you have and so on and it's also much more efficient in the very classical block where I still have like a limited number of columns all right so how is this done well let me uh let me give an introduction to the first into these two matrices so me essentially we took some inspiration from light with cryptography from Hardware actually we'll try to minimize the number of extra Gates and this is uh quite similar to what we are what we want to achieve because if we don't have many additions uh then likely we have fast stars in plane so this me Matrix is exactly that one here so it's a succulent Matrix built by two times uh this M4 Matrix and then just repeated in four Matrix and this

now uh may seem very very random but it's actually taken from this dl18 paper and actually what this does is so what this enabled us to do is we can compute the multiplication but that matrix by using just 12 12 operations in total and that includes both additions and also multiplications so we repeat that for a number of steps for the whole state and then we do the circle and Matrix and in total we only need five T operations again and this also includes additions and so both editions and multiplications so we have some number of operations which is linear in the state size which is of course better than the naive approach where you have a quadratic number of operations in total all right so that's the Matrix for the

for the full rounds or for the external rounds let's call them like that um and then we have the Matrix the new one for the internal rounds so we take uh we took inspiration from a recent permutation which is called map Dune uh this map implementation uses this Matrix quite differently and also has like a different structures for the non-linear layers but we essentially found that it can be used also in Poseidon this this Matrix and the nice thing for the partial rounds is that as a designer as a crypto analysis with a crypt analyst we don't need to focus on statistical security anymore because this is done by something which is called White Trace strategy and it's only done in the external rounds so what we can focus on is actually algebraic security so we we

are trying to find the Matrix which provides dense polynomials in the output and which prevents Subspace trades which essentially allow you to skip an arbitrary number of rounds and we found that this Matrix is uh so if you use the right values in the middle it actually allows you to do so and it's quite efficient because as you can see you just need to like compute the summit and just add the sum to each intermediate value and then you have the new state so this is even more efficient than the than the Matrix before [Music] all right so we also did some additional changes to Poseidon uh so first uh since uh there was this optimized implementation we were just at the partial or the round constants to the first threat in the partial rounds we

now do this directly so the optimized version is not needed anymore the more efficient implementation version and we also add a linear layer to the very beginning of the permutation and the reason for that is that there have been some attacks in the past which essentially allow you to skip I think up to two non-linear layers without increasing the cost a lot of the attack so we do this like as a precautious measure but let me emphasize that the original Poseidon which does not do that um is is not in danger so it's still safe to use the original Poseidon the changes is very minimal in that regard and finally also we we propose a new compression mode so this is very very old so to say instead of using the

sponge function you can just do two to one compression or four to one compression and so on uh more directly by using such a compression mode and if you're building a Mercury for example this can help a lot and uh finally a very nice uh message for all the developers and implementers so this efficient transformation of the partial rounds is not needed anymore actually it makes the whole thing a bit slower if you do that and uh the good thing is that all the like the hundreds of constants you need to store all the matrices for your passwords so that's all not needed anymore with the new version of Poseidon okay so in a nutshell what are the changes well we add this linearly at the beginning the me1 and then we exchange

all the matrices for the for the full rounds and also for the partial rounds so two different matrices in total and we do the around constants more efficiently in the partial rounds however some things stay the same and that's the nice thing actually so you can use the same round number both for Poseidon and for Poseidon 2 which means essentially that you can use the round number script of poseidon1 you get some output for the round numbers and you can use them also for Poseidon two so they're the same and they are also non-linear layers and the s-boxes and these gcd conditions this is all the same as the original Poseidon okay so something about performance we have two tests here one with a 255 bit um Prime and one with a 64-bit Prime and

we see already for 255 bits that Poseidon is Poseidon 2 is consistently faster and also for the 64-bit Prime we see for example that we're always below this uh five uh microseconds here um and let me also emphasize here depends a lot on which prime field to use so for example if you have a prime field where multiplications can be done very very quickly because you have an optimized version of the reduction and then of course the performance difference is a bit uh is a is not the same so essentially this focal is very generic and also if you move to a smaller Prime which makes you essentially increase the state size and then the performance difference is even larger compared to the original Poseidon so even for 32-bit primes for example it

may be very beneficial to switch to the new version so we can have up to four times Improvement here and the code is also available here you see the link below all right so um before actually concluding the talk it also besides the conclusion let me give you also some Outlook so well first first the conclusion right so Poseidon 2 is significantly faster than uh Poseidon the biggest change is actually in the linear layers and we're also working or we have finished working also in a gate for plancky 2 which essentially switches from Poseidon 1 to poseidon2 and uh what we found or what we've been uh seeing in the past and this is now the Outlook thing is uh that there are many modifications also to the original

Poseidon which focus on playing performance so for example there's this modification using the circle and MDS matrices which doesn't change the the specification of Poseidon but makes it a lot faster I think times two improvements something like that for a 16-bird size so it's pretty pretty nice and what we can learn maybe from that is that plane performance is always important so not only circuit friendliness but also pain performance but with all these modifications we are still not getting close to the traditional hash functions so not two shot three the let alone shot two which is even faster so the questions of course can we close this Gap can we find some hash function which is both uh circuit friendly but also like very very

fast and currently we're working on a successor to reinforced concrete which also works with smaller primes so this is called RC 64 but we're also aiming for 32 31-bit primes and we're trying to close this Gap and yeah well I want to close this presentation also with the question maybe can we even read shot three like plane performance and maybe in the future future maybe even shot two let's see thank you very much [Applause] so I think we do have time for questions okay we have one over here thank you for the presentation it was

really nice yeah hey uh our team was doing uh an Implement actually it's the implementations of course I don't do in zkx so we went digging into the paper and uh I think we have different questions my question would be the around the 4x4 The Matrix which you use also for for example eight by eight you are using a circular extension of that did you look into other sizes whether the so the paper that you've used have have these kind of figured outs but I haven't seen any generalized results behind those um so if I answered the question correctly it was about this M4 Matrix yeah the M4 which is which is kind of you use it also it multiplies but but you you don't use have other size and even for eight you are using this in a circular fashion yeah you are not using

a generalized results of that to eight okay uh if you look for Alternatives there yeah um yeah so that's a good question yeah we did look for Alternatives the reason is that um and this is also closely related to lightweight cryptography that the the larger the state size get so the the dimension of the Matrix the harder it gets to actually find an efficient one um however um for example if you are thinking about this um this circulate MDS matrices for Poseidon which you can use for the original Poseidon and improves everything um you can actually also use the third current MDX Matrix for this M4 Matrix so a very famous one is the simply AES Matrix which is Sacramento NDS so maybe instead of doing that here you can also

do like three or four or times two ffts and then maybe maybe you're able to even accelerate this version yeah but that's that's an excellent question yeah thanks thank you are there any other questions I think we would have time maybe for one more see well I guess if not then thank you so much for this talk