ZK10: Hash Functions Monolith for ZK Applications: May the Speed of SHA-3 be With You - Roman Walch

Transcript

foreign [Music] Welch and he will be talking about monolith which is a new ZK friendly hash function right take it away hey uh yeah so micro seems to work so this work is a joint work with some other researchers like Lorenzo Garcia Dimitri who was speaking in this room in the uh two hours ago with Ryan at lift neck Christian rechberger Michael schofenegger is also here and me of course from my bike so um we had two talks already about the symmetric hash functions for zero knowledge so I hope by now I don't need to convince you that they are important for your knowledge use cases but uh some examples I still want to mention here so

basically whenever you have some mercury in some Synology use cases you also need the symmetric hash function when you have a Mercury you can then also build directly some use cases like Anonymous transactions to Anonymous credentials hash functions are also used in CK Roll-Ups where basically Outsource a lot of computational some side chains and on the main chain you're basically just verifying that the industry or knowledge proof that you everything you did on the sidechain was done correctly and also for recursive snacks which is also a Hot Topic in zero knowledge there we also use some symmetric hash functions and symmetric cryptographers have been pissed in the last years and have come up with new symmetric hash functions which are actually optimized for these

types of use cases so most notably notably we have the Poseidon hash function which is nowadays implemented in many many different your knowledge proof systems but there are plenty more of these functions like a rescue griefing animal and many many more so the state of the art right now is that for for performance these new hash functions are significantly faster than a traditional hedge funds like sha free inside of SEO knowledge proof system but when we consider the performance outside of the proof systems so just for hashing some data these functions are still significantly slower compared to Chateau sha free and these traditional hash functions as we have seen in some recent use cases Blaine hashing performance actually also

matters for your knowledge use cases for example in recursive proof systems and I have been had people talking about their concrete use case for recursive proof systems namely a signature aggregation in these use cases actually approved during every recursion step has to build a Mercury hashing a lot of data and then show inside of physio knowledge proof that um the has been hatched basically and here playing performance actually matters in building these mercuries and in some concrete use cases which we have found in some papers people have shown that using Poseidon or similar hash functions up to half of whole proof generation is actually due to hashing and building

these Market trees so in these use cases plane performance still matters a lot so when we consider this but the ideal hash function would actually be it would be a hash function that is super fast outside is your knowledge proof so just for hashing but also be very very efficient inside SEO knowledge proof and that is uh with these hash functions we have mentioned before unfortunately not given but luckily in the last years researchers since your knowledge have come up with different kinds of lookup arguments and this also gives um researchers in symmetric cryptography a new angle to optimize for a better symmetric hash functions but if you think about it when we have some large Prime fields for example up to 256 bits and the hash function is defined over

these large Prime Fields is actually not straightforward on how to build a lookup-based system for this uh hash functions so you cannot really build a lookup Dairy with 256 bit that's unfortunately not possible so and um so if researchers thought about that a lot and came up with some new designs which actually optimized for lookup tables so um here on the slides you can see that the first hash function using lookup tables it is basically for the same team of researchers as uh for our new hash function here and uh it's called reinforced concrete and I've put the whole function on the right side and as I said it's the first hash function actually making use of lookup Arguments for better proof and plane performance

so it's built from the three different kinds of layers so we called them concrete bricks and bars and so for the concrete layer it's basically just Matrix Vector multiplication plus round constants something that has been done in pretty much every hash function before also in the bricks layer it's a standard non-linear layer also very similar to what has been done before but the main novelty comes from this bars layer that we we have here once in the middle of the permutation here and here is where I look up magic actually happens so what we came up with in in this design is that when we have a large field element up to 256 bits we actually split it up into smaller field elements so small in the area of about 10 bits so

on these smaller field elements you can actually apply a lookup table and uh after we have applied the lookup table we can compose the results back to a large field element again and so with this trick we basically are able to use lookup theories inside of hash functions and uh get the better performance in plane and inside of the inside of proof systems and you can also see here these bars functions actually only applied once in the whole permutation and that is um since the actual switching from a large to a smaller field actually gives the hash functions a lot of securities so that is very good so as a result we were able to show that with this hash function we are significantly faster for

hashing outside is your knowledge circuit than any previous hedge functions like Poseidon rescue etc etc but we are still owners of magnitude slower than shaft 3 for example and besides that the these uh reinforced concrete design has some different problem as well so when we would say we want to to build a similar hash function for smaller Prime Fields like uh audio local Prime field which is used in some one improved systems then we cannot really apply this design strategy of reinforced concrete as is since the design that we had on the previous slide is not really flexible it's fixed for a fixed uh State size of just three field elements and that basically disqualifies

it for a smaller Prime Fields already because the hash function itself would be insecure just from the field sizes and so reinforced concrete can basically just be used for large Prime fields for example for kcg bass proof systems or fry bass proof systems which are instantiated with large Prime fields also the decomposition in reinforce reinforced concrete is uh so when getting from a larger field element to multiple smaller field elements that is also kind of slow and it is also difficult to generalize so it's not really a problem for reinforced concrete because we have seen buses only applied once in the whole hash function and we have free field elements so we do not really decompose a lot of times but when

we go to a smaller field we have to apply Powers more often and then these DDS and slow decomposition actually can become a bottleneck again and a different problem is um that when we Implement reinforced concrete for just hashing we kind of have to to rely on lookup tables uh for for getting a better blame performance and that is uh since the the function that we evaluate during the with this lookup table is actually very slow and um so um we kind of need this lookup there for fast pane performance but as we know since um since the beginning of AES when we have some lookup there is in hash functions these may be susceptible to to some

cache-based sidechanalytics so when sidechain latex come to see your knowledge this might actually be a problem in the future but right now I'm not really aware that this is exploited so far but in the future we might want to protect against side channels as well so when we started this project so basically what we wanted to achieve is a new hash function that is super fast in plain also very fast inside the physio knowledge proof system and we wanted to achieve the the performance industry knowledge proof system losing their lookup arguments similar to reinforced concrete but we didn't want to rely on lookup Arguments for the plane performance such that the hash function can actually be implemented in a

constant time implementation without much performance loss and we were focusing on uh smaller Prime Fields so here that the goldilock prime filters is used for example In Blocky 2 and also on the 31-bit prime field that is used in blonky free and the design that we came up with we adapt monolith and now I'll talk a little bit about the design itself and then I will talk about some benchmarks to show you the performance that we achieve so here you can see um one round of the monolith permutations so um we also similar to reinforced concrete have three different round functions and we kept the same name so we also have a bus function with decomposition and lookup there is we have a non-linear layer called bricks and we have a linear layer

called concrete and now let's go a little bit into the details of these three different round functions so that a nonlinear layer we call bricks so you can see here it is actually very simple so on the first state Elementary basically do nothing and starting from the second state element we just add this querying of the previous element to to the state word and we do this since this has several different advantages on one hand it is very simple requires just one addition and one multiplication where field element so it will be very fast in plane and also since we only have one multiplication so it's just a degree two polynomial that we evaluate here it will also be very efficient

inside of here so your knowledge a circuit and finally the squaring function actually gives you a very good statistical properties so this is a good for the security of the hash function itself regarding the concrete layer what we usually have here is a matrix Vector multiplication plus some round constant C but uh when you get for to a smaller Prime field you actually need to have large State sizes so the minimum State size we have with this hash function is actually eight field elements and having a generic Matrix Vector multiplication with uh for eight field element State it's usually very very slow and it come easily it can easily become the slowest

part of the hash functions so we need to use something here that is actually very fast to implement but it is also that also provides good security for the hash function and what we decided to use here is using circular MDS matrices so this was also done before this is not an innovation from us and uh basically this MDS property is a property of the Matrix that we need for the security of the hash function and the circular property so you can see it here each row in The Matrix is a rotation from the previous row um and when we have a matrix like that we can actually use ffd to compute The Matrix Vector multiplication so this will also be very fast in plain and as I said since it's an MDS Matrix it also

has very good statistical properties and together with the bricks layer from the previous slides it will give our design good properties against statistical attacks so finally where the the most important innovation from our design comes from is actually that a bus function so a similar to reinforced concrete we will follow a decompose s-box compose a design principle but the decomposition is actually completely different to what we do in reinforced concrete so instead of going from a large field element to multiple smaller field elements we actually decompose the field large field element into a bunch of eight bit limbs so and then we do not apply some arithmetic function but actually a

binary function on this uh um on this 8-bit limbs on this decomposed Limbs and the function that we apply here just uses excer Gates and Gates and rotations so this is something that is very very fast when we implement it in plane and furthermore this uh aspects that we use here is chosen in a way that we can actually compute it on the whole field element without Computing the decomposition first so this thing is X actually very very fast in plane and does not require the use of a lookup area for fast hashing performance but also very similar to in real Force concrete switching from a large field to in this case bits actually is very good for the security of the the hash

function so also a small number of bus layers actually is enough for giving good algebraic security here and for in the proof System since usually it's not good doing some binary operations improved systems but we can deal with that by using some lookup tables so now I have talked about how the design actually looks now let's talk about performance the performance that we can achieve with this design and I will specifically Focus here on the 64-bit Goldilocks Prime field that is used for example in blonky too so first um there are modes of operations that we are going to use this uh permutation in um so on the bottom here you have the General's purpose

hashing so for general purpose hashing you use the sponge mode of operation so we've heard this in the uh two talks in the the first session already but uh um when we actually have some uh use cases where like in Mercury is where you have fixed size inputs you can actually go with a compression mode which allows to be instantiated with a smaller State size and therefore it will be faster so in the benchmarks uh in the next slides we will always distinguish between a compression mode and the sponge mode so and these are the two use cases for that so about um plain hashing performance on our system and we instantiate monolith with the compression mode you can actually

see that we can get the compression of the 139 seconds in the sponge mode we get a runtime of 210 nanoseconds when we compare this to for example shot free then you can see that the compression mode is actually faster compared to sha free and when we have the sponge mode then we are slightly slower competitors are free comparing monolith to different um uh said Care Friendly hash functions like Poseidon and it's a recent uh update because I don't do that was presented at the previous CK Summit you can see as odisa also instantiated with the Goldilocks Prime field here you can see that the monolith is significantly outperforms those two hash functions here it's uh at least a factor five but

it goes easily up to factor of 10 and 15. and here we also have benchmarks against deep five and tp4 Prime these are basically the most important competitors to our um to our hash functions since they basically try to achieve the same also with lookup tables and they can also see here that monolith outperforms both of them um here on the um you see it here on the slides here regarding constant Time Performance so since we have this uh special function in our bus layer that doesn't really require lookup table for implementation you can see that going from not constant time implementation to a constant time implementation has a very negligible overhead and that comes from switching actually the field implementation to a constant Time Field

implementation that is also true for Poseidon and poseidon2 since they don't have any fancy lookup tables in there but when we compare this to for example reinforced Concrete where the lookup table itself does not have a very nice structure to to be implemented without the lookup arguments that the constant Time Performance would be significantly too slow so um regarding proof system performance I first want to talk about how we actually parameterize our arithmeters monolith for a blankish proof system and I will focus here on bars since the bricks and concrete layer basically straightforward so to remind that we have a

decomposition and a binary s-box in here so for the decomposition we basically for every field element that we want to decompose we get eight new witness variables and also from the output of the lookup there we also have eight new witness variables and we basically have ADD do we have to add these two decomposition constraints to to show that the decomposition was done correctly and then we have to connect the input and the output via lookup table and this lookup table also includes already range checks for for these limbs here but so far it's basically straightforward nothing magic here but there's also one thing that we need to consider when we decompose field elements into smaller Limbs and that is basically that we have to ensure that

these limbs together do not represent an element that is larger than our field size this would give the Rover actually an opportunity to cheat in some cases so I ended for this Goldilocks Prime field we actually can do this very cheaply uh since this Prime field has a very nice structure you can see here in this hex representation of the maximum value in this Prime field it's actually a lot of ones here in the upper Limbs and a lot of zeros here in the lower limbs that basically tells us whenever we have um zeros here the only thing whenever we have a non-zerous here we do not allow here uh all serial xff because then they have a field element with

their decomposition would represent something that is not part of the field and would allow us to cheat and in this proof system we can actually do this by adding two constraints and two new witness variables so these constraints actually enforce when these are not zero we cannot have all ones here so and we only have to do this for the input since the s-box that we have chosen in um in uh here that ensures that uh every valid input always create creates a valid output all right so this was how we arithmeticize smaller monolith and now let's talk a little bit about actually a proof system performance so here on the slides I compare monolith against D5 T4 Prime and

also Poseidon and poseidon2 and what you can see here in the First Column is that monolith requires a little bit more lookup tables compared to deep five and deep4 Prime and obviously for silent Poseidon 2 do not require lookup tables here having my lookup tables so we have seen this in the previous slides look up the areas lead to more witness variables so you can also see that monolith requires a little bit more Fitness variable compared to the competitors but the main advantage of monolith actually is that the round function has a very low degree this also affects proverb performance so our Brix function has only degree 2 whereas tip 5d4 Prime and Poseidon in this field they require a

round function of degree seven so when we estimate approval performance by the area degree product which basically witness times degree you would see that we would estimate that monolith actually leads to uh allows the most performant approver compared to the other hash functions so on the next slide so we actually implemented a custom gate of monolith inside the blanket 2 proof system more concretely we are using a pull request on this proof system which implements the lockup lookup tables and here so we wanted to verify the estimated performance that we have and so on this proof system actually comes with a Poseidon custom gate which basically

implements the whole Poseidon permutation in one row hold custom gate so we added a monolith here with the same parameters as the as the Poseidon hash function that it already exists so we actually added a custom gate for monotlif which also just uses one row in the trace and compare the performance so and what we see here is that when we prove actually the monolith permutation we get the significantly faster approver compared to Poseidon and also verification time is significantly faster nearly a factor two for both but since we are using implementing the whole permutation in just one row and we have seen on the previous slides we have significantly more witnesses and the

result leads to a larger proof but especially when we copy the the plane runtime for these parameters from the slides before where we have a hashing time for monolith in this setting with just 210 nanoseconds come compared to Poseidon with more than three thousand dollar seconds it's a factor of 15 here as a difference we will say especially if the combination of the faster proven verifier that monolith significantly outperforms Poseidon in this setting here and this plane performance obviously also carries over when we want to create a Mercury so building a Mercury with monolith is 15 times faster than building a Mercury with Poseidon here so that basically where all the benchmarks now I want to conclude my

talk so the goal here was to implement a design a new hash function that is fast in plain that is fast inside the SEO knowledge circuit and we came up with monolith that is in play nearly as fast as shafri and it also outperforms Poseidon inside of the blanket 2 proof system also we designed a monolith such that it is easy to implement in a constant time so it does not uh it's not susceptible to cash based side Channel attacks our design is built using two different nonlinear layers so in the bricks layer it's a standard nonlinear layer like used in many other hash functions and in the past layer we actually decompose for the first time into bits and that gives us a lot of advantages in plane performance

so it's as I said currently the fastest your knowledge friendly hash function for just plain hashing and uh in our paper we actually have a more generalized description so we're not only focusing on the Goldilocks Prime field but on uh the same prime rate as well and the similar primes can also be instantiated with our new hash function so here are some links so here on top we have the the paper it's an ePrint so here are all the implementations very benchmarked plane performance and the blonky 2 benchmarks that I had on the last slides are can be found here on GitHub so um thank you all for your attention it was my talk if you have questions please don't hesitate to ask thanks a lot

so I guess we have time for one or two short questions let's start here so my question is if what why do you need to extend 2 degrees 7 in order to implement in Planck is you can definitely implement it with degree three uh maybe even less yeah so in Poseidon that the the non-linear layer is the the biomap X to the power of T and uh for this proof system the smallest D you can use is seven so and when you directly use it here you have degree uh seven of course but uh you can of course uh um use a smaller degree up a round function but that comes at the cost of larger witness sizes so having a smaller degree round function actually

allows for more trade-offs following that line how is it will be to plug this into a transcript and then prove the correctness of the transcript into another proof If you mean to do your recursion or something like that have you explored that and whether it's yeah so so it's uh the the hash function itself is a permutation like Poseidon so if there is implementation already there from Poseidon you can just switch the permutation and then it should work like before yeah hi thanks for the talk uh it seems that you were mostly targeting smaller fields and so have you thought about so what would be the effect of uh applying manually on larger Fields but potentially using lasso uh yeah we have

seen lasso yes uh not sure yet what the cost metric in Lassa would be so uh we need it's one of the things I wanted to talk with the designers so I'm not sure how good monolith would there would be there maybe some of my co-workers could answer the question I don't know yet but for uh for so the main thing when we use this decomposition like we have here I have shown that we have to make sure that the decomposition is actually part of the field so depending on what field you're using this may be expensive this may be cheap and uh yeah so for a larger for larger Fields uh it's basically the same considerations and if it's possible to have something very have a cheap decomposition and also an s-box which

guarantees that the inputs leads to about output and you can easily apply that as well but for different Prime fields we may have to look at it in in more detail yes yeah I would expect that the bar function will be very cheap with lasso because you could you wouldn't have to do one checks you would be able to have decomposition plus operation in potentially one or two lookups so it could be very interesting yeah this is definitely a very interesting topic and I guess we will look into that as well yeah thank you hi uh thanks for the talk so I wanted to ask the same question but I've got another question uh it's about a fine layer so we always seen the different designs that we always have the fine

layer that's there normally to do diffusion between the element of the state if I'm not wrong but also we see that we start mixing in DS box the different element of the state so we already already do some diffusion there uh is there any way that we can get rid of the of an layers or at least because different layer is quite expensive for prong because we've got to do a lot of additions and I can see that in the different constructions if I'm not wrong the the the cost in prong comes from the linear layer most of the time so have you considered yeah so we actually considered some parts of that so there

are nonlinear layers we have a lot of mixing for example a Feister networks LMS networks Etc but uh they come with different problems and in the beginning we actually had a design where we didn't have a linear layer but in the end it actually led to some to a significantly slower design so we tried to explore that it's not that easy and in this case we had to discard it but maybe someone will come up with a better design without explicit matrix multiplication in the future but uh so far we were not that successful in that yeah okay and there is no problem to use small coefficients in the linear layer Yeah so basically we we are most relying on the MDS property

here and then the small coefficients do not really matter but in it can matter in with different matrices with different uh branch numbers but in this case uh should not matter so AES also has only small coefficients just for reference okay we can continue okay yeah all right so as chair I take the power to ask the last question so can you say a little bit maybe something about the Crypt analysis of these of the hash functions in particular like we saw that the hash functions are dependent on the field right like how transferable are results that you

like fine for one field and then can you move them easily over to others or is that still yeah so so some properties for example in the statistical attacks you usually rely on the differential characteristics of the non-linear layers as well as the branching of the linear layers and the added differential characteristics are definitely field dependent so for the like a break attacks so we are mainly looking for um so that these are mostly independent of the of the field size but it of course the matters on how many field elements you actually need to instantiate the secure hash function so in general the analysis I would say can be transferred

but you need to adapt the parameters for example as I said the the differential characteristic for the nonlinearis field dependent so you need to plug in the the the correct field size and then you should hopefully get a result that is securing the other filters as well okay thanks a lot so yeah if there are more questions uh Roman is around all day so please find him during the breaks and let's thank him again for the nice talk thank you