Ethproofs Call #8b: Poseidon alternatives

Transcript

Hello everyone and welcome to Eve proof call uh 8B. Uh this is technically our 10th call and it's going to be on pedon alternatives. Let me quickly share my slides. Okay. So um today's call um is going to be 2 and 1/2 hours. It's the first time I schedule it as two and a half hours.

Usually we overrun. Last time we spent a whole two and a half hours on on poseon and I think it's a very important topic. So um good to to spend time on it. If you're new to the call, we also have a corresponding uh community telegram group. That's t.m meep proofs community. And there's also a QR code for you to to join easily. So uh today again we're going to be focusing on alternatives to poseon. Um and in the rest of the year we have four more calls uh tentatively scheduled. The next one being on on formal verification and lots of very exciting things are

happening with formal verification. for example, EVM ASM, which we're going to to hear about soon. Um, and this is uh scheduled to happen on on June 26. So, what I'll be doing is uh sending a poll in the Telegram uh group. Uh, if you'd like a calendar invite, just respond to the poll. So, um, today's uh, Eroof call is going to be split into three parts. We're going to have a few quick updates that we should go through pretty quickly, but there's a few like really exciting stuff here um going on. For example, uh we have Franchesco and and Nicholas who are new faces. Um we also have um some short

talks on hash function security in general um with some again some exciting uh announcements. for example, the the Afina consortium. Um, and then we're going to go into the meat of uh of of today's call with a whole slew of of different hash functions. So, often here we have um some of the designers of these hash functions uh who'll be able to in some sense pitch their hash function uh talk about the performance, talk about the security and how they may be uh relevant for for for the blockchain space.

Okay. So without further ado, I would like to invite uh Farah to give us some uh updates on ETH proofs. >> Share my screen. >> Okay, ETH proofs. Um yeah, the real time proving cohort is live and it's been running every week, every Sunday night since our last call. Um so this is a snapshot of this week's cohort. Um, some weeks we've had up to three provers make the cohort. I think the biggest issue right now is just teams going on and offline to upgrade which is kind of a good sign. So they're maybe not hitting the um livveness score which is 95% but uh typically we're hitting over 95% for

sub 10second proofs or teams that do become eligible. Um we have completed the first security sprint milestone. So, six of eight ZKVMs on ETH proofs have integrated into SoundCloud, which is great. Um, we are actively working on milestone 2, which targets um improved security at 100 bit provable and smaller proof sizes at 600 kilobytes. So, ZKVMs are upgrading which is really uh good to see. So, OpenVM 2.0 has come out by Axiom, Pico 2.0 0 by Brevis and Airbenders 100bit version is on staging and will go live into production next week on ETH proofs and then we have new ZKBMs that have

onboarded since the last call too which is great because they've already integrated into SoundClout so congrats to ZKDTVM by AntChain Open Labs and Venus by CIC. Um, our onprem proving initiative is underway. So, teams are currently getting set up with their hardware. Uh, we have a new page of metrics that's ready when those teams start to prove everyone in 10 blocks. >> So, just a reminder that the teams participating in that are Brevis, Matter Lab, Succinct, and ZISK. And then finally our ETH proofs validator to monitor the health of the ZK tester um implementation which is pulling proofs from ETH proofs to validate mainet is

out of the queue. Uh you can track it here with the validator number. Uh so we can now start to monitor the health that of the changes that we make which here you can see it kind of went offline when we're updating verifiers in the client. So uh yeah you can track that and uh we'll have more updates on that in the next call. Amazing. Any questions for Farah on e proofs. Okay, it's amazing just to see the the continual progress uh on this. Thank you so much Far Vah for the update. Um next up we have Yuichi on EVMASM.

>> Yes. uh EVMS is about the guest that runs on this GKVMs and this project is uh looks like this. So uh we do have a risk 5 specification in lean. Um we have most of the interesting parts of the VM specified in the and there are like multip there can be multiple specifications and then uh so we have uh the things the specifications on top and bottom so like the this is just fitting in the middle and it's a simple assembly programming no compiler is involved plus some program logic for assemblies. So and

then everything is done by AI models and agents. The code is audited by the generated by AI and proof also. And then this workflow um has been very uh agent friendly. Um so a single loop of like codeex can uh generate like 200 P request per day and something like that. So, and they can like make mistakes, but they can also repair their own mistakes quite autonomously.

So, this has been working pretty well. Um, I I g some numbers. So, so far 55 EVM instructions have been proven to match a specification. That's not checked. But uh you know it's if it's 256 bit additions then I mean there can be just one spec. Um there are like trickier specifications like signed divisions. What happens if like yeah divide by negative one is has some interesting behavior. Um the codebase is roughly 150 lines and uh it takes 4 minutes to build. So it's still okay. Somebody has been

cloning this repo a lot like 3,000 three no 300,000 clones so I don't know who is doing it but yeah please talk to me like if you are doing this if you have that much that many computers maybe you can contribute as well um the progress okay has been like maybe by instruction counts like 8% and then like there's some overhead as well so maybe it will take 10 times 30 times more commits That's what that's broad codes estimate today. My my own estimate was like it's we are currently at 5% or something. So um it's very aligned opinions. So that's the code base. Um it's something

interesting. So please have a look. That's it. >> Y we have a question. What are you using to manage the loop? Uh so the loop um so currently I have so both codeex and clone code have fairly recent features for looping things around like uh it's called go/go or slash loop. So I'm currently using these. I sometimes use helms agent when I have access to API keys. Um at the moment this is not being used by today but uh I I was also using this as well.

Uh the loops and gold commands work pretty well. >> Are you targeting risk 564 or 32? >> It's 64. I'm just following I'm just asking I was asking this question earlier and I'm just yeah following what people say. >> Very nice. And is it correct that uh you're now working on this full-time? >> Uh the agents are working full-time. I mean I I'm sometimes like you know just looking on the phone and I was in Rome like two days ago and I mean I'm in Portugal right now so the situation hasn't changed much and yeah Mediterranean experiences. Um so yeah if I get like more tokens then I can

sometime probably get busier on the phone or like even on laptops. But at the moment, uh the bottleneck seems to be like amount of tokens that I can put in. >> Mhm. I mean, for context, I believe we gave Yuri 10k of tokens and he burned through 5k over a few days. Um but yeah, we'll we'll work to get you more tokens. Um and um it's also great to hear the progress. When when we were in KN, you estimated 1% uh of total progress. Now it's bumped to 5% 8%. Um and uh this is extremely relevant to the canonical guest uh effort. Um and uh I gave a talk about this in KHN and hopefully the recording should be up uh in in a few

days. >> Thank you so much uh Yi. >> Next up we have uh Felix uh who will talk about ZKD DTVM new ZKVM. If not, uh we'll uh move on to Franchesco uh who'll talk about Linda. >> Cool. Can you see my screen? >> Yep. Okay. Um so we have been working on um leanda which is essentially uh postquantum proofs of read solomon codes using leanvm. So the idea here is we essentially want to um construct some

proofs which are viable candidates for replacement of KZG in the DA um protocol in Ethereum. So uh I'm just going to walk through a few of the constructions. Um so the first construction is essentially using um RLC. So the general idea is that um each of these uh rows can be considered a code word a code word or a blob which has been um read solomon coded and and extended. Um and uh we essentially merkelize each uh blob and then combine the roots of the the merkel roots of each blob um to derive a challenge. uh and we use this challenge

um in the RLC to uh construct a final um a single row. Uh and then we do a lowderee test on this um row using fry folding. Uh so that gets us to around um 364 kilobytes per second in terms of uh message prover throughput. Um the next construction is using the barentric um formula or or formulation essentially. So the idea once again is to um the the difference here is that we input uh these blobs um by the way they're they're input into the VM via non-determinism. Um but we do them in uh even and odd ordering. Um once again

merkelize them uh derive a challenge and then use this challenge to um construct the barentric coefficients and then for each row we do a check to ensure that they're low degree using this um barentric formula. So that gets us to around um 950 kilobytes. Uh this should be noted it should be noted that this is on an M2 max. Um for an M4 Max we can expect around uh a 2x in throughput. So um reports of of 2 megabytes per second on an M4 Max uh using this construction have been reported. Um and then this is one that I've been working on more

recently um which is essentially uh using an out of domain evaluation. So the general idea is that we take um blobs as nondeterministic input uh to the VM. So once again these are the re Solomon codes. Um we hash exclusive the systematic component of each blob. Um and then we then use the uh we combine we we hash the hashes of we we hash the blob hashes to derive a random um evaluation point. Um we use this evaluation point to um basically produce an outofdomain row. Um and what's nice

about this is the fact that uh it binds the columns. Um so you don't have to do any hashing over the columns. You have um essentially this this random evaluation point. Um and uh then finally you just run the the lowderee test on um on on this out of domain row. Um and yeah you also merkealize it. So this is the object that would be used for um column sampling in the uh in the DA protocol. Yeah, that's all from me. Um by the way I I will share these link uh these slides um in the chat and there's links um to the the the circuit implementations if people want to uh

explore an experiment and if you have ideas please do reach out um because this is still an active area of research. >> Very very cool. Thank you so much Franchesco. Um so for those who don't know Franchesco he's also known as Taleptin. He used to be um uh I guess uh a grantee at the FM Foundation and now is is is full-time and it's great to have him work on Linda. Um and from my perspective these numbers are kind of promising enough u that uh I think it's quite likely that Ethereum would go with with LINDDA. Um great. Next up we have uh Nicholas who will talk about Sphinx plus aggregation with LINVM.

Thank you Justin. Um I'm currently see hi I'm Nicholas I'm a master student in procure London I'm doing my my mast's thesis on spring plus aggregation with using hashbased snarks and around November October time I I looked initially looked at Cairo playing around with um you know implementations performance you know looking at different hash functions looking at different parameter sets playing around with grinding and target thumb sums in plus all that sort of fun stuff uh Um, and I got some early results, but around February, a few months ago, I ran into leanVM. This is how good the sort of Poseidon hashing throughput is. Saw that

XS is already implemented and and decided to to have a go with Syn Plus. Um, and I do have sort of not quite complete, but mostly the way there. Um, like an implementation. You can see here's results I ran yesterday. I'm able to aggregate about 2,000 signatures very very comfortably half a half a megabyte proof and about throughput 40 signatures per second. This is on a university computer. Uh Emil who's the the main contributor behind LENVM was managed to show about 140 signatures per second throughput with the same same circuit.

Um yeah and actually what's very interesting is that leanVM the overhead the main cost is actually the bit decomposition within sphinx and making sure that you you traverse the remote trees correctly rather than the actual pose hash calls themselves. Um and yeah on the way you know uh domains like full proper domain separate separation that's defined um looking at as well the new NIST smaller parameter set that's been released recently um and and also possibly looking at recursion for for smaller sizes. Yeah, thank you. >> Amazing. Um and uh for context, Nicholas I believe is a a master student uh at Imperial College um doing his uh his

thesis on on signature aggregation. Um I guess I have one quick question. Um why did you move uh from Cairo and I guess what was your experience there? >> Um so Cairo my it was just too slow. I was able to show like aggregation over like naive concatenation. I was able to like save on about 33% in terms of like the proof size was 33% uh 66% that of like if you just concatenated each sing um but it it took quite a while um and was very expensive in terms of memory and my my guess from that is because of like the Cairo programming language is it's a lot

higher level than what lean VM provides um so there's sort of a blow up in constraints because there's a lot of range checks which are being done which you don't control and and yeah, so that's that's why. >> Okay, got it. Thank you so much, Nicholas. Okay. Um, next up we have um >> Sorry, sorry, Justin. This this is Felix from Anton Open Lab. Sorry for to be later. >> No worries, Felix. Go ahead, please. >> Okay. Can I uh Do you see my screen?

>> Yes. >> Okay. >> Uh so sorry everyone. Sorry to be late. Uh uh I'm f from and open labs. Today I will show our results on real time proving on JKDTVM. The TD VM is on A3 ETH proofs now using 16 90 1590 GPUs based on the result of 3,000 continuous BRS from Monday and Tuesday. The average proving time is 3.41 seconds. 99% of the proving time is under 4.28 seconds. 90% of the proving

time is under 4.27 seconds. Uh all proving time is under 8. 6 seconds since we use 16 GPUs. We have 16 provers. Each prover has five task crews covering CPU and GPU tasks. All tasks are fully pipeline to maximize GPU utilization and throughput. DK DTVM is a GPU native DKVM which has 100 bit proving under UDR assumption and using refi instruction set. The proving system is based on Sunra Pop and Cola Bfield build. The core innovation of JKDt VMs is for the block executor. We

use JAT which is our block executor based on EVM1 that uses pipendra algorithm and the batched mo tree updates to reduce the running cycles for the emulator and trace generation. We use an aggressive static binary translator to temp five ro five op code straight into machine code and a GPU native trace generator to be g traces in parallel. For the proving system, we use only skip in a tail to fully use the GPU course plus an F practical to speed up lockup performance in GPU.

For GPU isolation, we design a multi-GPU hierarchical code pipeline that works by blocks and sh across GPUs to maximize resources use. For the no map, we will release a new version let the proof sites under 600 kilobytes this month and we will open source the proving system and block executor in August and release a new version with 128 bits provy and three 100 kilobytes proof size before September. Thank you.

>> Amazing. Uh thank you Felix. Um 99% of blocks proven under 5 seconds is really really amazing. That's a fantastic performance. I believe one of your innovations is the pangolin PCS which is a new polomial commitment scheme. Um can you tell us a little bit more about this PCS? U we we are tell the detail of about this PCS about a few days later in our blogs and our tweet on Twitter. You can you may you may can read this uh blogs >> Excellent. Really looking forward to this and also look into the open sourcing in August. Um check if there's

any questions. Nope. I think we're good. Thank you so much. uh Felix. >> Okay, next up we have a whole section on uh hash security. And here there's like multiple uh initiatives uh going on. Uh I guess I'd like to just kick it things off um with a couple of updates. The first one um is that um we have this idea called multi-hashing XMSS which is where the validators instead of having a single XMSS tree with a single hash function perodon they would for example um create three XMSS trees. One uh with some sort of fallback hash function which could be Blake 3 and then maybe uh another one with with a more

experimental hash function such as a monolith. We haven't really decided on the hash functions but the concept basically is that if padon were to break uh we would have defense and depth uh with another hash function and the downside here is that we might have to switch to GPU proving for the signature aggregation as opposed to CPU proving so we lose a bit of decentralization it's not ideal but it's much better than than nothing. uh and we're also looking into uh binary field-based uh proof systems uh to to see if the performance could be good enough even on on on CPU uh although unfortunately um it seems that only the Intel CPUs provide the uh the instructions that we would need uh for

for binary field high performance. Uh the other initiative that I wanted to to briefly mention is the the SHA 4 uh uh idea. So, I gave a talk at NIST uh just a few weeks ago. Um I couldn't find the talk online, but I'm sure I'll find it and I'll I'll share the link. Uh but the basic idea is to try and pill NIST to do a a new hash function competition um for snark friendly uh hash functions. And I'm kind of very pleased to report uh that the idea wasn't like completely dismissed out out of the bat. Um there seem to be some amount of of interest from the NIST folks and uh we're expecting to have a call uh with the

broader uh NIST cryptography team. Um just to set expectations, it's going to take a very long time even to start this competition. So we're looking at 2029 or later just to start the competition and then that competition would probably last several years, maybe half a decade. But uh still I think this is uh uh kind of the the ultimate endgame if you will uh potentially for for for snark friendly uh hash functions. Now um next up there's a very uh exciting initiative called the Athena consortium which might be a stepping stone uh towards the sha for competition and I'd like to invite Frana to tell us more about about that.

Hello, I hope you can see my screen otherwise yell, wave your hands, etc. Um, so the Hi, I'm Frana. I work at Maiden. Uh so as we have noticed in conversations with folks in the cryptography field uh recently there's a wide agreement that with the new research on skipping class on Poseidon 2 um folks want to migrate away from Poseidon 2. Um but what we noticed is that there isn't a lot of agreement on what they want to migrate towards. uh might be posed one, might be something in the rescue class of functions, might be something else entirely. Um and because Prooseidon 2 is kind of one of

the fastest practical hash functions that we have, any migration is going to look like a downgrade, which kind of incentivizes cryptographers to try tweaks to hash functions that might um help manage the the the downgrading performance. I know that we just mentioned that we need a SHA 4 because Poseidon 2 itself might not be performant enough. But now imagine a downgrade from Poseidon 2 and that's going to that's going to be even worse. However, one of the risks of this uh is that those conversations are occurring uh with folks that for all their qualities and I insist like all the industrialers that I've that I've talked to are un clearly very good at their

job. they they haven't dedicated six or seven years of their careers specifically to uh symmetrical cryptography and algebra oriented hash functions. Um so who knows they might do something safe but they might as well also do something slightly unsafe and those conversations are also siloed. So one of the risk uh is that uh we might end up with a field working in ZK in the next uh the next year uh that might make seven eight different choices in in the matter of replacing Poseidon 2 with something. So everybody agrees we want to replace Poseidon 2. Um not everybody agrees what we want to replace it with and um there we want to avoid security

security um breaks and we want to avoid fragmentation. Um what to do about this? Well, we have figured out that a long time ago, Stockware had um asked academic cryptographers to give concrete industrial guidance on which functions um to uh use in this industrial context to do say a ZKVM or or a ZKL2. uh and in uh that was all the way back in 2019 and that was kind of successful in terms of giving us more ideas around the security bounds and advancing the research on those hash functions. So we've asked the industry if they wanted to uh help uh

with this community problem. Um we have I've it's been an honor as far as I'm concerned to witness the uh level of contributions uh that we've seen across the industry for cryptography as a public good. So we've managed to garner a little bit of a budget. Um and then we have um the uh a consortium of uh academic specialists world-class folks that are working specifically uh on algebra oriented hash functions that are going to give us guidance on the question of both where are the actual risks represented by the recent attacks on Poseidon but as well um what is the best

knowledge that we have for replacements of Poseidon. too. Um, this is uh from us in the industry something that we're asking without being dogmatic about which hash function to look at. Uh, there isn't also um a requirement for funding members of the committee to follow the exact recommendation. Really, what we we want is a menu, a short list telling us here are the dishes on the menu. If you want to replace Poseidon 2, you have options A, B and C. Um here is what we know as of their soundness without any tribal knowledge going beyond uh what is uh published right now. Um and then maybe we will um during

those six months uh that so the initiative has already started we will contribute to benchmarks uh to help with all this. Uh with that I wanted to give a hand of applause to the initial funding members of this committee uh that are really contributing to cryptography as a public good and that includes EF. Um if you are not on this slide and you think that cryptography as a public good is fantastic and you have a little bit of money um uh burning a hole through your pocket, know that we're raising for a fixed budget. If we uh haven't talked to you uh it's probably that we haven't had the time.

Uh we're kind of running this on a on a shoestring of OBS team. Um so uh feel free to contact me uh and I will be more than happy to point you out at how you can contribute and how you can have your logo on the next iteration of this slide. We would very much welcome the contributions. With that being said, thank you very much and a big kudos to everybody who contributed here. Thank thank you Frana and thank you so much for the initiative. I think it's it's a great one and congrats getting so many funders uh in in in the initial round uh you mentioned benchmarking. If I recall correctly from our conversations you were thinking of potentially using Plony 3 as kind of a shelling point for uh kind of apples to

apples benchmarks. Is that correct? >> Yeah. So this is the main reason why you haven't seen logos of um Aztec or I alo in there is mostly because uh we have focused this on folks that are initially uh using small fields uh because first that simplifies the work of the committee that gives them a more clear target and the other advantage which is really incidental is that this is some a place that has plunky 3 as a lingua franka um everybody knows what benchmarks in circuit or circuit.

Insecret being the difficult part um on PL3 look like and so that is going to give us a very clear target to be able to compare our administrations of those uh different hash functions whatever the committee happen however the committee happens to choose them. >> Perfect. Um I guess this is a great segue to Leo who will give us a little bit more technical information about the Afina consortium. Yeah. Hello everyone. Can you can you hear me?

>> Yes, we can hear you. >> Okay. And uh do you see my screen or anything like that? >> Uh we can't see your screen. We can see your video. Okay. Now we can see your screen. That's good. So, okay. I'm assuming you can see my >> So, I will remain at a very high level for now. uh because the work hasn't gotten started yet but as uh as was said uh I was tasked with uh gathering this consortium of cryptographers so thank you for entrusting me with this uh the way I see it I'm trying to to answer uh the that question which is on on my screen someone is asking for which hash

function to use for their zk system which operates on blocks of fp to the n for specific values of p and specific values of n and that person is asking what should I do and is it okay to use posedon for these specific sets of parameters it's an excellent question because there has been uh progress on the crypto analysis of functions like posedon so on these algebraic hash functions arithmetization oriented hash functions however you want to call them uh first algebraic attacks have wrecked havoc in this in this whole area so algebraic attacks are attacks that rely rely ultimately on solving a system of polomial equations and you

have techniques like the free lunch or the resultants that have proved much much much more powerful than what was anticipated by the designers of these functions including myself. Uh recently and more specifically for poson there is this skipping class paper where uh essentially um some cryptographers have found a very clever way of writing the equations that would occur in these um polomial system solving based attacks and to write them in such a way that they are easier to solve. So such that the solving algorithm is more efficient which is a problem because then it means that the function is even less secure and this attack this technique to skip rounds was much more powerful than what was known uh to be possible. So they

managed to skip three rounds while the best state-of-the-art before was one or two. So that was a significant uh breakthrough. And another issue which is not so much uh a hint of insecurity it's a a hint of poor understanding the the focus of academic cryptographers like myself so far so far sorry has been on the case where P is huge so your prime is more than 200 bits. uh and then as a consequence your number of elements your number of coordinates in the blocks on which you operate is smaller than four which is not what we are interested it interested in here. Uh the prime is much smaller and the number of elements is

much higher and that changes a lot of things in terms of crypto analysis. So all the results that were relevant in that context the the big p small n might not be relevant in the smaller p bigger n uh regime of parameters. So we will uh work in two steps. First we want to improve the understanding and we will write a detailed state-of-the-art on the analysis of these hash functions with a focus on relevant parameters and then we will write guidelines. So we will as as Frana said we will select a small number of hash functions that we consider to be safe and we will write clear descriptions of them like a a light standardization effort type of thing. So

these are the cryptographers that have been kind enough to agree to to join us in uh in this effort. Uh I'm not going to to read their all their names. Uh as you will see they come from all over the place. That's on purpose. they have specific expertise that are also all over the place which is also on purpose. Um so I'm sure we will manage to make some uh some important progress in this area. I have decided to call this project Athena to stick with the Greek goddess um trend for these hash functions and you can expect to hear from us uh soon. We will keep you updated on our progress. With that I thank you and I'm happy to take

questions. Thank you so much. Uh, Leo, I'm not sure we can see the SL. Oh, there we go. Um, perfect. This is the last slide. Um, yeah, and it was great meeting you um in in Rome and I think you gave an excellent presentation um at the uh the hash function event. It's a shame that it was not recorded. Uh, but you know, hopefully you'll you'll give the same presentation somewhere else where it is recorded. Um and uh yeah, just for context, um Leo is kind of widely regarded as like one of the best in in the field of hash function crypto analysis. So it's a a

great honor to have him lead this initiative. Thank you so much for for accepting to do this. >> My pleasure. >> Okay. Uh next up, we have Jeppe um who will talk about some bounties uh that he may have claimed or will be claiming in the future. Uh Jose. >> Yeah. Hello. Hello everyone. Uh so this will be a really quick update. Uh just want to share as Justin was said saying that I just want to share with you. Um so that a few days ago we claimed the secret shoe bounty for Pum one plus linear player over Koala Bear uh with the six full rounds and the eight uh partial rounds.

And uh we are currently targeting also the next one uh with two partial rounds more. Um so we didn't publicly share the technique yet. That's because we observed um something we didn't really expect and we would like first investigate the reasons if there are deeper reasons uh that could explain this. But what I could share instead is that um our techniques doesn't use resultants uh to solve the secret problem and uh overall the attack for for the claim verified bounty the first one um sorry the 68 one uh costed only $300 in uh GPU computing and um so if you want to know more of course we're

working on a report uh that we will share soon and uh we will there we will describe the diesel. So, what we did, that's all and thank you. >> Amazing. So, $300 spent. What was the bounty? Was it 10k or 15k? >> 10k. Yeah, >> 10k. Okay, very nice. Um, and is it correct that you're trying to get the kind of the the next bounty and you've been hiring um renting hundreds of GPUs? >> Yeah, that's correct.

Okay, that's correct. >> Well, good luck with that. >> Yeah, actually um okay, I will tell also these little details. The the the next uh the next bounty somehow seems will cost around three four times uh the first one which is a bit less than nine times because the degree increases by nine times. Um there are different reasons for that or probably also optimizations that implemented but uh yeah it's >> it's in the range of a few thousand.

Yeah. >> Excellent. Uh and it is also great to meet you uh in Rome. >> Of course. >> Um next up and let's let me check the Uh yeah we do have questions for the parental regime on this slide. White states over small fields. That's maybe a question for Leo like n= 8 and 12 with 64-bit fields or n= 16 or 24 with 32-bit fields is a concern that pose is fundamentally old and safe or that the existing pose security analysis does not give enough confidence for these parameters. I think it's the latter.

>> Yes. Um so on a deep level we don't understand uh the behavior of algebraic attacks as well when we are trying to fix more values. Uh so basically when you run these attacks you are target these algebraic attacks you're targeting the co some coordinates of the output of the permutation and if you are trying to attack one for instance if your prime is huge or if you are trying to attack eight of them because your prime is small um it's not the same. So it's more of the latter that we don't understand as well. At the same time, these round skipping tricks also tend to get more powerful when the number of elements

increases. So that is also something we understand less, but that's something that's a bit more worrying. That that would be the the the summary of it. Great. Actually, we do have another question. Which attack class is the limiting one here? Interpolation grant invarant subspace or something else? So um invariant subspace and skipping class are not really their own attack. It's a way to enhance uh an attack where you're going to write a system of polinomial equations. So when you write your system of equations uh the the solving step has a given complexity. But with round skipping tricks what you do

is you write a simpler system that you can then solve using different techniques. And this system is simpler than what would have happened if you did not skip the rounds. And essentially the complexity of the solving step becomes the same as the complexity you would have had if you are attacking fewer round. Hence the name. It's as if the the rounds you have skipped didn't count. That's why we call them that. The way in practice so far we have been able to f to find round skipping tricks was by reasoning about yeah invariance of space type of structures. So classical symmetric crypto um techniques in the case of uh posedon um the best attacks. So so what you do

is that you're going to write your system of equation that you need to solve somehow and you have some freedom as to how. So you can use resultants. Maybe you can use the simp the basic pipeline of F5 FGLM. I wouldn't believe that it's something we need to worry about, but who knows? Um and you will write your system using these uh these round skips. Yeah. Uh but it's it's not two attacks, it's two aspects of the same attack. >> Got it. Thank you, Leo. Um, next up we have Manuel who will talk about Super Hash.

>> Hi everybody. >> Can you see? >> Hi Manuel. Uh, not yet. >> Um, see, can you see my screen now? >> Uh, still not yet. >> Uh, I think I'll have to get out and and come back. >> No worries. Okay, let's move on to Danny in the meantime. Uh Danny, uh the floor is yours to talk about uh algebraic oriented uh security. >> Yeah. Hi. Uh let me try to share my screen also.

So give me a sec. Um oh um I will have to rejoin maybe um because of Yeah, I have to rejoin. Sorry. Because of the Mac OS security. I've got to rejoin. Adam. >> Okay, no worries. Um, I guess we can just get cracking then with um the the meat of today's presentations uh which is uh the alternative to Poseidon. So, let's start with SHU as a potential candidate alternative uh with owner.

>> Hi, Justin. Thank you. Uh let me try to share my screen and for context Honor um received a grant from the FM foundation and uh he's now focusing on making lean VM friendly to Bitcoin which means uh using J 256 my screen now. >> Yes, we can see it. >> Okay, cool. So uh um in short we added SH 256 uh per compared to LMV for uh Sphinx verification. Sphinx plus verification. Uh so this sphinx plus is a PQ safe and one

of the candidates for future use. And uh let me show you some verification requirements. It's uh means if um uh spin verification means we need to verify uh sphinx signature on uh limb. So the in the left side we have this parameter states and the right side uh the number of hashes we have to do in the circuit. Uh so it's a uh roughly estimate circuit but I just round it up to uh uh to be yeah.

So uh this one is seems uh uh nice but uh I think this have uh less uh set of signatures that uh signer can use. also uh signature signing time a bit uh uh I think I there's a there's that trade-off. So let me uh give some introduction about limbium. It has very uh minimal instruction set four of them. So it has uh two pre-o compiles post one extension P operations and it's a multi it use multilar proof system uh and GK for memory in the back end v PCS

and it also also has a Python DSL. So you can see that uh VM in that uh library. Yeah. So we uh if you want to add uh SH 2 to this VM we want to add as as uh pre-o compile uh also uh we want to change PCS uh it was before working with pos on hash function now uh it's uh we have also want to make it short to 56 I uh mark it with uh this pre-ompile it because uh insert circuit uh SH expensive but uh on the other hand uh

with SH 56 um PCS becomes a bit faster. Uh now we have some benchmarks. First of all we have this SH 256 air uh SPR employ from Tomman. It's a 700 cells in a single row or one uh compression. Uh I made some benchmarks that uses try back end with baby beer prime. Uh for those input size we as you can see it's uh five to 10x uh slower

than the poson one. I mean I uh want to share this as a baseline. Um and um also we have another uh SH 56 air implemented with lookups with S TVO uh back end. It uses circle stack circle stack and M31 uh prime. It's uh previous one doesn't involve a lookup but was uh 7,000 uh cells but this one has 4,000 cells uh

and it's a uh this difference is uh about lookups right and uh I think this tweet is related with this uh implementation and they uh argue that they see 8 kHz on M2. Uh I also tried to uh uh uh regenerate this result but I guess I failed uh I mean not failed I couldn't see that numbers on my uh M1 machine but uh we also ported this uh SHA 256 air logups lookups to the

uh to the stvo uh library. this rookie number library. So uh so I also compared uh two uh with lookup and without lookup on st. So uh studio yeah sorry lookups uh starts to pay off when input size getting high input size means I mean a number of hash uh a number of SH 256 compressed calls right it's uh uh I think it starts to getting payoff when uh it's uh around 2 to the 15.

Yeah. Yeah. So also uh I would like to uh share how look lookups look like in SH 256. Uh we have bunch of tables uh 24 of them uh and you can see the uh sizes of number of tables of these uh functions. These functions uh are in this SH 56 algorithm. Uh they include some rotations, shift, exor and ads. Uh and we have such number of cells for this. I mean this cells mean if you use uh log up u this 7 million is the number

of multiplicities we have to uh count and also uh uh since there's no uh it's a studio I guess it's not multilinear so uh it's interestingly these tables are um has um multilinear closed form it means we don't have to send I improver don't have to send uh openings of these tables right um I mean if for a random point verifier you can just calculate the uh openings of tables if yes all all of the tables has u mult

actually have uh >> yeah uh lastly uh we uh let me share with you our poson pre-ompile in limbium uh no sorry not pos6 pre-o compile in the left side we see this uh I also put this poson timings to compare with the uh shot of 56 six uh this actually in the second column uh is SH 56 uh pre- compile uses poson back mean it's a V but it's in poson uh but in the third column it's a chart

56 with chart 56 V uh uh so you can see the difference that uh there have there's some improvement when we switch to the out of six B and also we added uh we ported this uh rookie number uh air with lookups to the limb VM I guess maybe it's a not a very good implementation for now it still didn't catches the one with the uh without lookups I mean these two are without lookups uh and this is the one look up.

So, uh I guess thank you. >> Perfect. Thank you so much, uh owner. Um I mean the the goal here is to try and um have lean VM be fast enough on the CPU to prove all uh Bitcoin uh signatures if they were all replaced with Sphinx Plus. uh with the new proposal from NIST uh with you know two to the 24 messages that can be signed that's 300 signature 300 hashes per signature. Bitcoin does 10 signatures per second so that's 3,000 hashes per second and that's something that we should be able to to um to do relatively easily. And the stretch goal would be to have the the more expensive uh Sphinx

plus signatures which I thought were 2,000 hashes uh per signature but in your slides were were 4,000. Um we have a couple of questions in the chat but in the interest of time owner can I ask you to answer them uh in the chat directly uh and we'll move uh to Manuel um to talk about superh perfect. We can see your screen now, Manuel.

>> Can you see the slides now? >> Hey, hi everybody. Uh, my name is Mano from Lambda class. I'm going to talk about um this idea that we had a formula known as super hash in which we use uh techniques from equality saturation to design crypto cryptographic uh hash function. So let me see if I can uh get it moving. Uh the main idea here is that uh hash function can be uh thought of as a term that is a like a composition of atomic operations um sboxes linear layers uh hit operations and uh in that sense uh

terms are what uh egraphs actually uh optimize. Uh our vocabulary so far uh is a very small one. Sboxes, um, build operations and so on. And, uh, the good thing about this is that, uh, egraphs and quality saturation work, um, by rewriting designs. Uh, in this sense, a a hash function is a design that we can identify with an environment vector. This is uh, somewhat of a fingerprint for um, the hash design.

uh this fingerprint will talk about how resistant the design is uh how it behaves in hardware and so on. Uh the idea being that uh if we think of a hash function as a term we can actually rewrite it. Um typical uh equality saturation deals with equality. That means if you have um a design you can apply rewrite rules to find uh equivalent designs. This means that uh you're going to find a a different design which has the same security and performance properties. But the thing is that maybe we can uh improve a little bit and teach the graph

to saturate a different kind of relation which is not necessarily equality. So if we teach the graph to saturate directed relations, we can actually find improvements of the original design. uh directed saturation will work with a criterion uh that is going to be stated in terms of the invariance that we are interested in. Maybe we want to have a design that's better behaved in terms of uh how resistant to linear attacks or differential attacks it is. We can also think of improving a design in terms of its performance uh and so on. the list of uh invariants that we are going to

use is really up to now a convention. So this is really um sensible for us at this point. The thing is that when we want to uh in we're going to be interested in having good ways of improvement. This is uh we're going to have a different sorts of rewriting rules uh mainly uh handmade uh improvement rules made by cryptographers. Um for instance if you uh add more rounds or if you change parameters of sponge block uh these are going to be handcurated uh rewrite rules

that's that they are going to be um improving the original design but also we can have a different egraph that it's not going to model the design of the hash function but it's going to model uh a design of an attack or a specific In this sense, if we uh tie if we tie these two teams, these two egraphs, we're going to have this um kind of loop in which one uh e-f will design and the other will attack.

Uh for now, we have like the foundations for this uh all the equality saturation uh theorems we have in line already. We're going to work on uh the soundness of the directed improvements. Uh we're also interested in having a larger um vocabulary for this having more uh atomic blocks to express more uh hashes and we also have to work on uh closing the co-evolution loop. Uh that's uh going to be very interesting for us. Um at this point we're optimistic. we have um uh good reason to to think that this will yield uh very nice results and

hopefully will become a a good tool for cryptographers to to use. So this is it for now. This is uh kind of a short talk but uh if you're interested just contact us and uh we'll gladly uh answer some questions. Thank you. >> Thank you Manuel. U next up we have Danny uh who will talk about AO security. Can you hear me?

>> Okay, perfect. So, hi everyone. Sorry for the issue right before. Uh, so I'm going to do a very quick intro about um what's called AO-Scurity. The name has to be changed, but it's an open wiki about arithmetization oriented primitives. Um, so let me Oh, I cannot change the Um, sorry I am trying to switch to the next slide. Um, okay.

>> Yeah. >> So, sorry. So um this it's a wiki that I started as a personal research initiative uh during a break uh to go deeper into the the maths and the whole literature about arithmetization oriented primitives. So uh we've seen many hash functions recently in the past few years. So it's you know posidon rescue griffin all the other um and many others primitive. So if the industry continue to rely on um these primitives uh we would need to keep track of all the research uh work and also uh see uh which uh actually blockchain or products in general uh use them. And on my side

uh during this break I wanted to go back to the maths uh that are actually useful uh in this um in these primitives. Um and I realized that uh all the security analyszis the algorithms uh uh and mathematics in general are all scattered through you know pgases github issues informal node group discussions videos like here also uh but there is no single place to look it up. So I wanted to start creating a centralized and also a live reference uh for the crypto analysis uh of all the primitives using linfo and also sage code. I went through the lin for fever recently.

Um so um most uh of the content of the wiki the link is at the end uh is at the moment AI generated to go through the whole uh literature uh and I also implemented some of the attacks from different papers uh that are uh um that are available at the moment on existing primitives uh and everything is going to is going to be available uh on the uh GitHub repo. everything is open open source. Uh but so on the on the on the wiki the idea is to list all the different primitives the design the security claims uh list of all the published attacks uh but also for anyone

who is interested in the cryptonis itself having like a kind of a course of all the all the cryptonis and the tools used for these primitives. Um and to go further I wanted to uh initially uh the directions of the project is uh mostly uh uh implement in lean or other uh term prover the lay mass the terms to verify actually uh if uh if the the pen and paper proofs are correct uh and also track the open questions because when you look at some papers there are some open questions also and having also an open-source repository where in the same spirit it as uh they exist for some uh elliptic

curve uh cryptography primitives to have a list of all the attacks and also exploring independently some new directions that I've been talking with a few people but also has I've heard from some people uh from some people so um everything is open source at the moment uh I mean it's always going to be open source uh you can go on the uh repo uh happy to move to any uh um any public good uh website or repo. Um so that's it for me. Uh it's going to be updated in the next few weeks or months. So it's it's going to I've I've got to go through the whole papers. Uh um that's

it for me. >> Amazing. Thank you so much. Um and I believe Leo last time uh you showed me some sort of a wiki as well that maybe one of your ex- studentents uh was was working on. >> Yes. Uh yeah Daniel we should talk because there is my my own well my own with other people were working on such a thing and I was recently as in half an hour ago notified of another uh such effort. Uh so we should we should get together I think because I think we both we all look at slightly different sides of this but I agree with you that centralization would be the best. Uh so yeah drop me an email we probably should talk and then we can all contribute to to this type of effort because I think

this type of effort is really welcome. Uh as you pointed out it's kind of a mess right now. >> Totally agree with you Leo. >> Cool. Um, happy to connect you guys on Telegram if you're not already. Um, next up we have uh we're going to be talking about Blake 3. Um, so we have the Airbender team that's using it in production. Alex Glassov will present and we also have Al Kindi from Maiden that has looked into using Blake 3 as well. So we're going to go through the hash functions uh sorted by age. So we started by with SH 2 and now now Blake 3. Uh, Alex, the floor's yours.

Uh, give me a second to to share. So in Ethereum, Blake 3 uh is probably a a good candidate for every part of uh of the L1 with one exception which is the the XMSS hashing uh where we just have too many hash functions and we're doing the aggregation on on CPU. Um but yeah, so for example for the risk 5

ZKVM plague 3 could uh could potentially uh work without any issues. >> Okay, can you see everything? Can you >> Yeah, we can see your screen finally. >> I hope to claw back a little bit of time uh so we can read it uh in parallel. uh it's also not Blake 3 but we actually used Blake 2. uh I will explain a little bit about the nuances uh and I will only talk about it in um basically conjunction with the air bender as a as a risk five prover um because we don't want to to just prove Blake we want to use it for

something meaningful okay so the motivation for Blake is simple it's fast I mean arguably one of the fastest hashes uh for a CPU at least um there are some nice internal properties. So um native NDNS but it's not that important. Uh no need to ex to maintain ex message expansion like for SHA. So and it has internal structure which is basically a loop. So instead of arithmetizing the full um Blake hash invocation by full round function we can uh arithmetize internal permutation round. Um and other nice properties it doesn't require padding. So the node hashing is 2 to1 exactly one round and it's not inflated

like each 56 with a huge internal states which of course require would require um extra circuit variables. Um some journals of bender to have some context why such property important. So we have a very very small set of circuits less than 15. Um for recursion we don't hand design anything we just prove a recursion as a program. So and in such program uh we want to basically invoke the Blake. Um so that's why it's not just proving Blake but it's a proving of the Blake together with some control flow attached to it. And from technical capabilities in air bender you

can basically invoke a pre-ompile uh at some moment in time in the over the global virtual machine state. Um so in the current version of air bender currently used in isproofs version two um so we only support a pre-ompile which is a single blake to s permutation with additional uh options which basically speed up the node compression. Um the circuit is the heaviest across all of ours in a sense of the width uh basically number of elements in a row per typical invocation. Uh but when we go closer and closer to the um basically

recursion route. So we just run recursion program over the one layer of proofs and then we get some new proofs. we run recursion top of them and we want it to converge to as little number of circuits as possible. Uh so if we continue to use a blake pre-ompile circuit individual circuit type we have to prove it and it's adds to the uh proof sizes. So we plan to get uh in Blake in air bender v3 next version a more lightweight even more internal primitive for Blake um which is u internal quarter round function how it's usually called in the paper which is uh nicer to verify so we need to pay less in recussion to verify it so we can

start to use it closed recussion tip also one important thing to note is um by default in settings we use seven round blake uh in line with the parameterization from from Blake 3 and the famous too much crypto paper. Uh but it's not that really not that important. It's more like a historical reason because uh most of the linear hashes which we have in the next version will be I mean all of them will be less than 1 kilobyte. So there is no difference between black two and black three in this mode and there will be only one circuit where we will require uh a little less than two kilobyte of linear hashes uh for Merkel tree leaves uh and it's the only place where we will actually pay for three

tree structure compared to plague 2 uh linear hashing mode. So two concrete numbers uh when we did the experiments so right now our commitment time our commitment scheme is fier um I mean the the most of the work is just a low degree extension uh the creation of Merkel tree in this case when we use Blake it's 70% of time spent in entities or commit during the commitment and 30% of the time spent on hashing and when we experimented with the Poseidon 2 it 20 to 80. So it basically flips the complexity of the commitment scheme and it's dominated by the hashing in case of small fields. Um commitment itself in

the current version is 70% of the prover time. So this is unarguably a good trade-off. Uh don't have data for uh v3 yet but eventually we'll get it. Um an important note we only need to pay to prove Blake only when we invoke the recursion. So there is no Blake in in the host program at least in those we're interested in at the moment. Uh so uh prover play pays the cost to prove the Blake circuit only when the recussion is uh actually done. It's and it's actually less work than the base program itself.

Um, and if you factor out all the prover cost per Ethereum block in uh, our typical workload, then the provers 30% of the total proving time uh, to prove Blake related stuff. So with all the numbers above, it's just unarguably good tradeoff for our case. Uh, uh, sorry I was still out of time, but I tried to be quick. >> Very cool. Thank you so much. Uh yeah and the fact that you're only spending 30% on of the time on recursion is really good. I'm curious what is your two to1 recursion?

>> It's not on recursion. It's 30% on proving the blake across basically the total prover work across initial guess program plus all the recursion which will happen. >> So okay >> it's it's not that small. Yes, it's not that small because the base layer base layer is basically the guest program. It's the largest one in terms of number of risk five cycles being proven, but it's still good tradeoff. >> Cool. Um Al, do you have anything to add on Blake?

>> Yeah, not really. But uh so basically the question of like two or three uh boils down to the uh number of rounds. There's also that the um the idea that Alex mentioned about using the permutation uh when you have like the 10 rounds although I think he didn't explain more about it. Um so these are basically the the this things that are we are still investigating. Um for for Miden in general the the key is not uh performance but basically reducing the chances that we will need a u a hard fork or an upgrade in the future. Um performance like initial experiments

show that for our use cases it's not like a huge penalty. Uh maybe for recursion that might be as Alex also uh showed in his presentation but there are ways to go around it. Uh um yeah and security is basically either the the defense for the seven rounds or one can also go with the 10 rounds. I think the delta between the two um shouldn't be that huge. Um just one thing that I would like to add is that if anybody's working on um on the same thing for Goldilocks, please reach out um so that we can pull effort together. I think ZISK are looking into that as well. Um

but if anybody else u is interested, please uh reach out. Yeah, thank you. >> Okay, cool. Um next up, we have a hash function that I didn't know about. Um I think it was invented by Algorand. It's called sum hash 512. And we have uh Leo to talk about it. Do you have a Leo? Leo fan. >> Hello. Hi. Hey, can you hear me? Yes. >> Okay. Okay. Let me share my slice. Uh yeah. So uh yeah. So I'm here to talk about like some hash which is like adapted from hash and this work was done like several years ago when I was still

at a and we so when was at a like we do the uh quantum um quantum transfer I think at that time and we we choose uh several several things that are key to to this transition and uh some hash is one of them. Uh yeah so like uh the work has already been put into practice like for several years. So if you search like go some hash argument the github will pop up and you can see all the details here. So it's basically like a subset some hard function at its core is parameter has like three parameters qn and m and the q is homogeneous the a is

a dimension and m is a impleance and each function here is indexed by like this public well known matrix a with like m by m and it takes a binary string of like len m and then outputs are elements of integers modulo q and little Quick heads up. We can see your script but not the slide itself. >> Okay, sure. Sorry about that. Yeah, ask my >> Let me see how can Yeah, ask my cloud to to generate a script.

Okay. So, how about that? >> Uh yeah. So, the output Yeah. Yeah. Yeah. That's Yeah. And so it's basically a matrix vector of multiplication there and the conjecture security properties like we have like uh several things here. So we have like collision resistant target collision resistant which also like imply image uh uh pre pre-image thing and then the oneness and then the last one is on invertability. So like if you put uh this thing like into some um uh like the compression factor

uh is like set uh appropriately then you can have like this like collision resistant which is equal to relaxed un invertability. Uh so which means like if you break like one of them like you break all of them and there's like one thing you need to note that this like f sub a is like linear and it's not um it's like not render and of course it's not a render article and please do not use that instantial one. Okay. So that's that's um uh that's a construction. And then the crypto uh crypto analysis is like uh we use a uh an idea of like called like

mering tree. is basically uh like a uh generalization of the idea invented by Wagner I think. And then uh this idea was like um proposed by I'm not sure if I pronounced his name right. It's uh Shortenoff. Yeah. So like as you can see like we have um uh quantum. So like the the estimation here is like the time plus time plus memory and we do it in favor of the adversary where like the the adversary is like uh doesn't cost anything to do sorting or like the glover search

doesn't also cost anything there. So for here this like argument is like some hash 512 where like the output length is like 512. Uh the it's stiffly exceeds this like 128 bits of quantum security here. uh if you see the uh numbers in the table and then the instantiation is to say like how we can instantiate this algorithm some hash the first of all as you can see like the uh the matrix A was like uh generated by shake and using the states argument um yeah so like which means like we didn't build any back door in there you can you can generate a by

yourself and the outputs uh Here is like uh n Q which is like 512 bits and um yeah and here like we only um like the original designs only handle a fixed length input but you can very welcome to use like Merkel down guard training method to handle like arbitrary length with some stress name padding and also there are like two modes the sorting mode or unsorted mode. If you use sorting mode then you have like pseudo randomness there. Uh if unsorted mode then it's like the plain uh some hash.

Yeah. So that's it and yeah you can search the uh GitHub for the for the spec and for the crypto analysis. There we have uh both classical and quantum analysis for for this max function. >> Very nice. Thank you Leo. Um since this is um I guess a variant of it, it might make sense for Beanie to present um his presentation on on it hash functions now and then we can take questions for the the two of you simultaneously.

>> Yeah. Thanks Justin. Can can everyone see the screen? >> Okay. Yeah. So yeah, it's kind of the predecessor of some hash and uh uh to be honest, I'm not a expert in symmetric hash function. So please correct me if I say anything wrong. And this is actually a bit high level and the motives to encourage community to explore about the snark friendliness of our had a hash function. Uh so I think this is most most of people already know this so I'll be quick on these slides. So at hash function was invented by ATI 30 years ago. Uh and the idea is really simple just a matrix vector multiplication. So

given a input for simplicity let's say this binary string you just multiply a random matrix with it and get a smaller output. And initially this is not very efficient. Uh actually the the rank of this matrix n is actually pretty large for security. uh but later we can we will see a much more efficient variant and the security office can be reduced to SIS and and then reduced to some worst case last problem and has endured like 30 years of crude analysis and people believe uh for now is still secure against quantum computer.

So as I mentioned this is not very efficient. So in 2008 the shvky machine per per and roen introduced a variant of it called swift hash function by leveraging the polinomial ring. So now instead of multiplying over zq uh and use a big matrix you just do a inner product between a vector rq vector and another random rq vector. Essentially this is can be understand as a uh matrix multiplication vector multiplication with zq as well by uh equivaling considering this random vector as a negyclic matrix but thanks to the structure and the fast multiplication over polomal rings in fact uh every

input bits in amortization only needs to do about log n multiplication over cq. So it's much faster than before. For example, if n00 now this is only 10. And additionally the input norm can be slightly larger rather than binary can be an like rather than can be a norm that has been bounded by some parameter and the security office can also be reduced to a variant of SIS and people still believe that uh this is quantum security and for now we don't have any better uh attacks correspond is actually a pretty complex formula in

terms of the parameter uh n uh the rank matrix and the modulars and norm of the inputs and and I would refer to this uh software github software called last estimator for uh for the concrete number whenever you want to get a security uh level estimate and this is based on all the best known attacks uh in these 30 years and there are many more uh resources in that GitHub. So I really strongly encourage uh everyone interested to look at it. On the other hand, I also found that actually there is already a proof of concept uh of attach function over code locks in uh two two years ago by Jen Fay and it's only a proof concept. It's a

very prelimary uh result and the runtime and snark circuit size is about two times larger than Poseidon. uh but I think this this uh is only a preliminary result and there are many spaces for further improvements. So I encourage uh engineer and researcher to look more uh to it. So finally I want to highlight some uh nice properties about it hash function and explain why it seems to be a good fit for snark friendliness. So first it has very flexible choice for modulus. Uh we only need this modulus to be slightly larger than input norm. So there are many choice for for choosing it like such as a 32-bit prime and another good to know fact is that this uh moduous Q

doesn't have to be a prime uh it can be anything for example power two even though I don't know how in how useful this will be in the snark setting but I think it's a good to know fact and want to highlight more about another property about atah hash function is in is somewhat naromorphism so if you have some nom scalar C1 C2 and some nom vector V1 V2 then a line combination of these two hashes is exactly the hash of the line combination of underlying vector and this turns out to be very useful if you want to have more efficient uh snark proving given this ni homorphism for example suppose you want to prove correctness of um multiple hash computation for some long

vectors and naively you will just prove them separately if this is a standard hash function but now if you have any homomorphism you can do much better. And the idea is to uh generate some randomness given this output uh hash hash output using some standard hash function that can you can understand as a random oracle and then you can encode this randomness as some um nom scalers with uh in R in this ring and then finally you don't have to prove this separately you just need to prove the hash once and prove that this linear combination of hi equals the hash of line combination of underlying witness vectors. So approximately the snark

circuit size can be now be k times smaller than before which is a great saving and in partic uh even better if h this hash output are the public inputs rather than inside the circuit the generation of randomness doesn't have to be proved in the circuit it can be but down outside circuits so you don't have to even have to prove this uh stand hash function but of course if you have to I don't think this is a big deal because this is only proving a much smaller uh input rather than a big input v_sub_1 to vk but I also want to mention there's some limitations uh so I don't recommend to uh like only using hash function so the hash output size is pretty large uh

usually it's larger than 1 kilobytes which is much larger than 32 bytes so I would suggest that if you want to have start friendly hash function but still small output you should compose a hash function with another hash function that has smaller output size. Uh so that to get the 1 kilobyte digest first and then compress again using another hash function and some other care is that you have to make sure the inputs are no norm but this is not very hard to just do some standard input decomposition. Okay, so I think that's basically it. uh the the key thing I want to convey is that uh ITAI or the swift hash function are pretty simple and it's plausible

postconure and has endured for almost 30 years of C analysis uh and uh it supports many different modulus and it has a really nice property about homomorphism which makes it a great fit if you want to prove ash computation for many and long input vectors but I also want to cons like warn that this is not a perfect panacea. Uh usually has larger output size and some nom input requirements. So I would suggest if you want to use this maybe combined with another hash function with a smaller output size. Uh that's it. Thank you so much.

>> Thank you Beanie. Uh we have a question already. Um are there any resources you can link regarding the linear homorphism property? uh resource you mean the you mean the uh some >> I guess the original paper um >> original paper I I think this is kind of forklaw people because it's matrix mical vector modification so they have a linearity so it's a nearomorphic uh yeah >> kev asks since sub set some hash can be used heristically as a random oracle I guess it's a replacement for peterson hashing in the postquantum setting rather than a replacement for something

like SHA or Blake. So for things like Merkel tree constructions for example. Okay. >> Uh yeah is basically only collision resistant. You cannot use it at the random or uh but Merkel tree can use collision resistant hash function as well. >> Correct. I guess one question I have is um are you implementing um a lettersbased scheme such as lettuce fold and do you have performance numbers that you can share for? >> Yeah, unfortunately not for now. Uh >> yeah, but uh hopefully in the future.

>> And do you know other teams that are implementing lettuce based? >> Yes. Uh I know Nethermind they have open source uh implementation uh and there are several team they are not open sourcing yet I but I think Nethermine is the one that have an open source implementation and also I think the team from uh from EPFL I think Alexandra students they have some library right Jacomao do you know maybe Jacomao knows about this I think there's another library that works uh implement a lot of less cryptography. I forgot the name.

>> And is the never mind one zinc plus or something different? >> Uh it is a different library but it implements many similar things uh if I understand correctly. >> I I can try to find the link uh like later and put it on the chat. >> Thank you. And Ramco is saying that A6 andZ withdraw has a Latis commitment >> implement right. >> I I believe they've implemented Hashi. Oh, there you go. That's the link. Yeah, perfect. Um, cool. Thank you so much, Beign and Tom and Leo. Uh, next up we have Tommer uh who will talk about uh

Rescue Prime Optimized, also known as RPO. Uh Tom, you're muted. >> Thanks. And now you can hear me, right? >> Yeah. And we can see your screen. >> Perfect. So yeah, um Rescue Prime optimized, which is kind of an instantiation of um Rescue Prime. I think they're not that different. It's um rescue prime with a chosen um one specific matrix. I'll talk about why like it it came to be. Um it's a work that we did in 2022 with Al, Willie,

Alan and Bobin. But and the original work on rescue prime was also with Simon and before that on rescue with Ellie and Abdel in addition to all these people. um in the interest of revity background motivation some design decisions state size and security and a little bit of benchmarks. So I need to start from the marvelous design strategy that is a generic way to create algebraic hash functions. And the trick in all those algebraic hash functions is to alternate between highderee and lowderee power maps. And the trick to keep it efficient is that nondeterministic hinting allows

to evaluate the highderee power map um by folding it back at well by having it as the compos inverse of the lowderee power map and then you can write both s boxes at once as one low degree polomial. So here in the picture we can see that's one round of rescue a 2019 paper and the main problem here is that the high degree power map precedes the lowderee power map and what we saw is that this it when you fold it back it spears over to the previous round. So in 2020 I

think with rescue prime we swapped these two uh layers. So now the lowderee power map comes first and the high degree power map comes later. And then in 2022, Bobin came and asked that said that he needs a specific instance of this family to be used in Maiden to work on Goldilocks with 128 bit security and to be CPU efficient for client side proving on edge devices. Now to instantiate on Goldilocks and with 128 bit security is easy. That's exactly what the design template is meant to do. To do the client side proving on edge devices requires some

optimizations. So these optimizations are only the we the least efficient part in all these functions is the one over alpha power map which is now in this figure is presented in the second part and but we can't play with that as that kind of it doesn't break the security but we don't know what would be the security or we didn't know we know better now but we didn't know what would be the security if we start removing hybrid power maps so we focused on finding an efficient NDS matrix.

Um eventually we got this is a work by um that was done by um polygon zero by Amish and he found a circulent low heming weight matrix MDS matrix to use. We put in some effort to verify that it's indeed an MDS. And when we convinced ourself ourselves that it is, we used it as well. And we also made a small reorder of the operations within the round. So that it would be MDS constant injection and the power map and then again MDS constants and the power map in which is uh only semantics because MDS and constants are linear

operations. So they can um we can swap them and it doesn't affect security. In in the RPO paper sorry in the RPO paper we have two versions uh one with 128 bit security with a 12 element state and one with 160 bit security with 16 element state. Both of them with seven rounds and to the best of my knowledge there's no known attacks today. So maybe it's time to consider um to reduce number of rounds to six or maybe five.

and then because I don't know anything about implementation, Al was kind enough to help me benchmark this. We see that for Goldilocks RPO um runs oh in 2.63 microsconds procidon one is 92. So about double maybe maybe even three times slower. But then for smaller fields they're about the same. And this is expected because we know that the entire family of rescue functions becomes more efficient with a larger state size and with a smaller field whereas Sidon requires more rounds um which makes the

circuit larger. That's all for me. I'll take questions. >> Okay, great. Um, very uh nice surprise to see that you're matching the performance of Poseidon one uh with Baby Ben Ko Bear. Um I guess one question uh is if we do reduce the number of rounds does that kind of creates fragmentation or confusion?

>> well I'm I'm really a big fan. I joined Leo's project and I think that's the right way to go. We should avoid this fragmentation. Yes, it could create that. But hopefully the Atheina project will um standard I know sort of standardize certain versions of these functions and then we will all just converge to those. You could still make different decisions in your use case, but that won't make sense for you. Especially if someone does recommend on five rounds, I'm pretty sure that people will start converging to the more efficient version.

>> Very nice. And I believe um no one's using RP right now in production. So I guess if we do the standardization beforehand then uh there'll be less of a chance of of fragmentation. >> Yeah. Yes. >> If I may on the topic sorry >> go ahead. >> Yeah. Just on the topic of fragmentation um I agree that fragmentation is annoying but I think we can only really talk of fragmentation when the field is already kind of solidified. So like yeah pedon one has been around for a while and has been used by a lot of people. So making a poson 1.5 that would be perhaps unwelcome fragmentation but it's not the case of all primitives and I don't know to what extent like

there is an interesting philosophical question here if we should allow uh round numbers to be changed over time but yeah that's a question for another time I guess. Kev is asking how much of the performance degradation is coming from the inverse SB box >> um the performance degradation of what like this is just the performance in compared to what so sure that's the bottleneck if that's the if the question is what is the bottleneck then the inverse Sbox is definitely the bottleneck ah compared to Poseidon one um so I can't answer this directly I can say that in RPO the bottleneck is the

inverse SB box and in Prooseidon one the bottleneck is the MDS multiplication. >> Got it. In a sense super comparable, right? Because one has way fewer rounds than the other. >> Is that right? >> Yeah, exactly. Yeah, sure. But I get you still compare them on performance, I guess. >> Right. Okay. Um, well, if there's no more questions, uh, I'll let's thank Tom and move to Leo who will talk about anemmoy.

>> Yeah. Can you see my slides? >> Um, I think yes. >> Very big lag. Last time there was a lag over 10 seconds. >> Ah u well I will see then I will just try to drop the pauses. Anyway um so yeah animo um so in this talk I'm going to talk about two things and also a mode of operation we suggested alongside animo called jive and I think both um algorithms can hopefully contribute to the discussion about round skips. So first uh anoy itself so I'm enrolling the slide. Um we published it at crypto.

It's a joint work with with a big team. Danny who talked before was a member of this team. Um and what we wanted to do with anoy beyond just pushing the state-of-the-art of the conc slides. Ah um is he the only one or >> there's a delay of 40 seconds. Unfortunately, >> 40. Uh not sure what I can do. >> If you send them to me, I might be able to to share the slides instead. But I guess in the if you send them to me on Telegram, we can figure something out.

>> uh that's not uh going to be practical, I'm afraid. Um um quickly share. So now what can you can see that my screen okay so is it okay now or >> it's just taking a very long time to to load I think there's a there's a massive delay why don't we move to Alan >> and maybe you could restart your computer >> cool >> uh Alan the floor's yours uh to talk about tip five >> oh

>> now it's better my screen how do I share my screen okay then Then let's go. Uh, floor is back to uh, Leo. >> Actually, I'm I'm I'm not sure. >> Sure. >> Okay, Leo, let's let's try real quick. >> Do I go or? >> Yeah, sorry. U, it sounded It looked like the problem was fixed. Um, >> okay. Let's try again. Sorry about that. Uh, >> sorry about the flip-flop.

>> Yeah, it's the joys of remote presentations. Um, okay. So, my screen. >> Yes, that's better. Yes. Yes. >> Okay. And now it's moving. >> Now it's moving. Perfect. >> Okay. Perfect. Sorry about that. I'm not sure what happened, but who knows? If it's old, it's solved. Um, Animo. So our goal with Adimoy was to first uh well mostly it was to push a state-of-the-art on the design. Uh we did this in uh with two big contributions. One was a new SBOX which was an actual SBOX not just a monomial and the second was to try to have a structure that is as close to what we usually do in in F2. So it's built like

some primitives that are defined over F2. So you have like your internal state can be seen as a rectangle a two dimensional rectangle with two rows. We have a diffusion layer which is applied on each row in parallel. So it operates over half of the state. Each matrix operates over half of the state. Then we have a small linear layer over the columns and then the SBOX that's over the columns. So it's really a classical SPN structure where the SBOX actually provides very strong mixing uh over its input space.

um the width of the state so the the length of the rows you can choose it rather freely and it has again this classical span structure we have you have a kind of slice sbox uh and layer so the fly style our sbox uh it's what's on the left part of the picture and you have an inverse mon the a monomial which is the inverse of a low degree monomial so you have e which is x to the^ alpha for a small alpha And within the fly style, you have its inverse. The Q functions are quadratic.

And the key insight behind anoy is that you can use the open fly style as the sbox of a cipher. It has a high degree and it's a bjection. But during verification, you can look at the closed flight style because there are ces equivalent and I will not go over what that means. But it's a low degree function. It's not a permutation, but we don't care. But crucial has a low degree, which is nice. Then for the verification uh animal has some known issues. Um so this is a picture I made for this workshop I gave a talk to last uh last Sunday. You have variance of animoy.

Each row corresponds to a variant and then what you have in the other columns is the complexity of some attacks. So it comes from the paper on resultant based attacks which as far as I know is the is the best um at least as far as anyway is concerned which was put on the print not that long ago. Um but what's interesting is that some versions are completely broken. So for instance this version here when the exponent is equal to three and you have just one column in your state it's really insecure. The best attack is in 2 to the 80 instead of 2 to the 128. However, as you increase the the state size and when you use a smaller prime, it's what you do then uh the number of um the the security level

increases. So, how did we choose the number of rounds when L is larger? So, when the the length of the rows becomes larger, it's based on considerations related to regular crypto analysis. In particular, we did not want to have fewer than eight rounds. Uh because an SPN with fewer than eight rounds seemed a bit iffy to us. Uh but when L is smaller, well, for all of the values of L, but it became more important when L is smaller, we were using pointless estimates of the degree of regularity that are now completely outdated. But it was st at the time. We didn't uh we're not the only ones who made this mistake, but it was a mistake.

uh at this stage the versions of animal with a small L shouldn't be used they are not safe but when L is larger they are not really affected if you look at the version when L is equal to uh 10 uh you can have security levels that are in the you know two to the 200 for the 128 bit secure version so the advantages of anoy so when air is small it doesn't have many to be completely honest because first it's broken and second the native speed is going to be a disaster because of the the huge expo exponents over large fields.

But uh one of the key advantages of Animo is that you don't have round skips uh thanks to its real SPN structure. So the fact that you really have a nestbox which completely mixes a small part of the state, you don't really have round skips. And for larger block sizes, it scales much much better in terms of complexity because the MDS layer is only defined on half of the state. So if you have a state with 24 elements, you only need an MDS layer on 12 elements which is going to help quite quite a bit for performances. I had a look at the what we had put in the paper. So it's uh slower than posed on. So you again have something like a factor two. We were faster than risk prime for this specific set of parameters uh because we have

half as many uh inverse sboxes basically. So that would be the the reason I think uh for the constraints these are some benchmarks that we made in the original paper for the case of plunk but I don't think they're really relevant for us because it's here because it was for the case of large prime small number of elements so I would just keep however something else I wanted to talk about was the mode of operation if you want to build a compression function so we introduced jive in the case of anoy and the reason why I think it's important is an observation on these round skips. So what do you need if you want to do some round skips? You want to have that diffusion is too slow. Uh that's prevented by having an actually

MDS uh linear layer and you want as an adversary to have a lot of freedom in terms of how you can choose your input. Uh and this can be solved at the mode level. So for instance what we suggested was if you want to build a 2:1 permutation to use this mode which we called jive jive 2 in this case but it can be for any level of compression and the key idea is that you make uh linear combinations of several inputs and several outputs of the permutation to obtain one output of the compression function. So if you have this more complex linear combination in practice you're going to be safer than

just with a truncation or a feed forward because you will block these round skips. I think from a provable security standpoint it doesn't change anything but in practice because of round skips it can make a difference. Uh so to conclude if you have a small P and thus a large L actually anymore isn't such a bad alternative to posed but I really think we need to talk about uh the modes of operations when we build uh compression functions and that's going to be it for me. Thank you. >> Thank you Leo. Um, one question I have is, um, is ANMOY going to be considered as part of the Aphina consortium?

>> Uh, very good question. Uh, I would like us to have at least a quick look. I will probably uh, first have a look at uh, I mean ask our industrial partners for some benchmarks to see if it's actually competitive and then we will see. But my my initial if you had asked me the question two days ago I would have said I don't think so but since I prepared this talk I realized that actually maybe we will see. >> Okay very nice. Um so Tom is uh uh you know now one of the maintainers of plunky 3 and uh he can help with the with the benchmarks and uh yeah he's hoping to have many different hash functions implemented.

Great. Um, next up we have Alan who will talk about tip five which I believe is used in production uh today. >> Can you see my slides? >> And now still good. Um, yeah. This was a a a paper written in 2023 uh before we launched Neptune cache. We launched Neptune cache in 2025, February of 2025. So we've this function, this hash function is uh live in production since more than a year.

Um, and before we had tip five, we were using Rescue Prime optimized in a Stark VM and we noticed that 80% of the time was spent hashing and that was expensive. And so we decided to um to switch to a different hash function. And we all know that Blake 3 is the fastest, but you obviously don't want to use Blake 3 inside of a recursive Stark engine because Blake 3 doesn't arithmetize nearly as well as some of the alternatives. And so we thought um let's let's design one that arithmetizes well but doesn't pay too much of a penalty in terms of CPU performance.

Um, and we were inspired by reinforced concrete. Um, which beforehand I had tried to attack using algebraic methods and I got exactly nowhere because the look split and lookup construction um, seems to thwart algebraic attacks. Now, reinforced concrete didn't seem like the best choice for our Stark engine at the time because it was tailored to large fields and it doesn't have uniform rounds either. And so, TIP 5 um takes that construction to a in a different architecture. So, we have uniform rounds

and we make use of a um split and lookup um tool. Um, we use the oxoy field 2 to the 64 minus 2 32 + 1. Some people call this the Goldilocks prime. That's obviously wrong. The Goldilocks prime denotes a different number. Uh, we have uniform rounds that makes the air the description of the air simpler and concretely lower degree. And one more thing is um in contrast to the the arithmetization oriented hash functions that were available at the time uh we knew that we needed uh a wide state and um well we knew that we needed a wide

state and and that means that we can get away with fewer rounds. Um, specifically in um, Neptune cache, we target a security level of 160. And so our digests are five elements of this oxoy field. And so we want to be able to do 2:1 hashing using one invocation of the permutation. Uh, so yes, it is a sponge construction in overwrite mode. This confuses people sometimes. We don't add the input in between every permutation, but we overwrite the the rate part.

Um it's a substitution permut permutation network. So there's an MDS matrix, there's an injection of uniformly random constants. Um and there are there's a a layer of S boxes. But the feature that sets apart um tip five is that these S boxes come in two classes. There is a power map X goes to X to the 7. Those are the T S boxes. And then there are split and lookup Xboxes. Um which is essentially looking up into a table. And that table is defined in terms of this function X goes to X to the 1 to the^ 3 minus one. And this function is defined over a different

field. So it's embedding a foreign field arithmetic. You define this function over every bite of your field element and then you end up with a new field element. Um so besides the uh split and lookup SBOX we have the power map and then the the power map uh defends chiefly against statistical attacks linear and differential cryp analysis whereas the SBOX attacks defends chiefly against algebraic attacks. So it's a hybrid construction.

Um I'm aware of two papers that analyze um tip five and they both um present attacks that are more efficient than what was present in the original than than what was analyzed in the original paper. Uh I think the current state-of-the-art is that you can attack four out of five rounds with a small caveat like uh you need to reduce the the capacity by one element and and then you can attack it. Uh but it's also worth noting that academically an attack is any algorithm that breaks the hash

function faster than brute force and we are still targeting 160 bits of security. So academically speaking an attack that works in 159 bits constitutes an attack constitutes a full break of the cipher. But you could perfectly use that um if that were the optimal attack, you could perfectly use that in production. Um back at the time we uh had a back of the envelope um uh benchmark against Poseidon. I don't think this was using the um um circulent MDS matrix and so I expect uh

the cost of Poseidon on the CPU would be a lot less but still tip five is is uh pretty darn fast. Uh it's not quite up there with Blake but on on par with Katchack but of course that's the CPU cost. What we really care about the the the whole uh the main metric driving this um research was how do we get the recursive proving as quick as possible and by switching from RPO to tip 5 we ended up with a 2.68 six eight um performance improvement and uh yeah as I said at the start

Neptune cache is live since February 2025 so this is another um argument in in favor of tip five there there's a a de facto huge bounty in terms of fame and perhaps even money if you can exploit it if you can exploit a vulnerability in tip That's it. Floor is open for questions. >> Amazing. Any questions for Alan? I guess one question is how much value is secured uh by tip five?

>> Uh I think the uh price now is 30 cents and there are around 80 eight hang on 8 million coins in circulation. So that's what roughly 3 million US dollars. Okay, got it. Um, and the four out of five round skip, that sounds, you know, like a lot to to >> It's not a skip. It's a It's an attack.

>> Okay, got it. But it's not something that in practice you're worried about. >> Uh let me put it this way. If I had been aware of the attack at the time that we were uh designing tip 5, we would have opted for six rounds instead. uh the the original analysis in the paper concluded that you can attack three rounds but four is difficult and then those two papers basically proved us wrong.

>> Got it. Tomas is asking is it defined to other fields? No, it is tailored to this field because uh this field has a particular structure that makes this particular uh split and lookup construction work. When you look up every bite of your field element, you have another field element and generic fields don't satisfy that property. >> Right. Okay. Um cool. I mean, Kev asks uh a bit of a philosophical question. If we choose a new algebraic hash function, do we reset the crypto analysis lendiness counter?

>> I don't know how to answer that question. >> Yeah, I'm not completely sure how to interpret it either. Um in any case, thank you so much, Alan. Um this was uh very interesting and and look forward to the report um from the Athena consortium as well. Uh next up we have Marcus. Um you mentioned um reinforced concrete and I believe uh there's a a couple other hash functions skyscraper and none that uh are in the same family.

>> Marcus, of course yours. >> Yeah, thanks. Hope you can hear me and also see the slides. >> Yes. Um yeah great. So yeah this will be about monit uh mainly as a potential alternative. So um it it can be like after tip five but the motivation is pretty similar. So essentially we observe that highderee functions like they used in rescue for example this uh the inverse function and so on uh they are quite uh expensive and quite slow. So especially if the field is like not not very very small. Um but we also observed and I mean that low degree functions even in poson I mean it's of course better to do like to the power of seven or something but still you have to do like full field multiplications and so on. So it's like still not very very

fast. So the idea behind like monolith was how can we minimize the CPU operations uh in particular for the for the nonlinear operations and we came to a similar conclusion as tip five here. We wanted to use this new then new technique of lookup tables in CK and then essentially also exploit those lookup tables um and in particular exploit the fact that many of those can be implemented with vector arithmetic on CPU uh which again of course makes it much better. All right. So what are the main properties then of monolith? So it has pretty good native performance uh and in particular the lookup tables. So you don't actually have to use like lookups on the CPU. you can do the memory lookups uh without any so you can do do those functions without memory lookups

to resist some side chain attacks if they're of a concern to you. Um it also has an efficient proof system representation but it's less efficient than for example poson particularly because we use uh the lookup argument and we'll see some numbers also on that later. Uh when we designed monolith uh we focused particularly on very small primes. Uh so like then we focused on frybased proof systems and like especially like 64-bit and 32-bit primes or 31 bit primes and there are some like constraints uh which primes you can use and which primes you cannot use or at least which primes are less efficient than others. Uh but like for the for the Goldilocks or Baby Bear or M31 primes it's fine and it also works for some other classes of primes. And if you're

interested in large primes, uh there's two new primitives like there's reinforced concrete, there's also skyscraper and I'd say skyscraper is uh is better than reinforced concrete in almost every aspect. So should should use uh that. But essentially it's very similar to monolith. Some some things are different of course and it works only for larger primes. So it's it will not be the focus of this uh of this presentation. So yeah, how does monolith look like? It has a very uh very simple run function consisting of three layers essentially. We call them bars, bricks and uh concrete. And then it essentially does this like six times. So it's six round functions. Um let me focus on the bars layer here. So it's uh like most interesting point of monolith or most

interesting component. So the idea of that is that any input gets essentially so any field input gets essentially split into smaller limbs. for example 8 bit limbs or 16 bit limbs uh via this very simple sum here and after the splitting we apply some sbox on this limbs it has to be some it has to be chosen specifically for like some properties where it's not so important and the sbox looks like a chartre lookup essentially and the advantage is that you can via vectoratic you can do many of those sboxes in parallel so you don't have to do it like specifically for each uh limp uh independently And this provides strong algebraic security for a similar reason like uh Alan mentioned before that essentially you're operating

over a different field here. So you're mixing two fields and then that gives you pretty high degree in the fields here. Yeah. So that's it. Uh the the bricks layer is very simple compared to the bars layer. It's just some f like construction where we have those uh squaring operations. Um also maybe the the intuition behind that the squaring is better than the cubic sbox. So the to the^ five or seven sbox in poseidon in terms of constraints but also uh compute and uh doing this but it's not a permutation in the prime field. So you have to use something like a fel construction or something to get uh the entire layer to be a permutation. So that's why we mix it with the f like construction

and particular it also has very good properties even better than the cubic and b seven but not like it's in the same ballpark it's low degree so it has good statistical properties and yeah it has to be mixed with some matrix with some linear linear layer and here we use a very simple MDS matrix this is essentially exactly the same like it's done in the external rounds of pose one uh it's just some matrix some NDS matrix and yeah you can use different ones you can circle ulent ones and all the all the newer stuff that came out recently. So about the performance uh it's um much better than Boseidon one or Boseidon 2.

It's uh yeah similar to tip five it also comes very close to uh to ketchup and in the proving however we see that yeah it's still better than posylon 2 but we see we have a problem for well not a problem but it's like worse in the proof size particularly because we need uh more witnesses due to the due to the lookup argument here. So we we essentially split each field element in each round into those limbs and those limbs have to be stored somehow in the lookup in the in the trace table and this of course uh needs some some additional um size uh yeah uh security. So that's also very interesting why we here right. Uh yeah

so two components bricks and concrete provide the statistical security and this bars component is like field mixing provides the algebraic security and yeah to the best of my knowledge there have been like two very nice papers that came out recently that analyze these this this type of constructions. also reinforced concrete I think was analyzed or in particular skyscraper was analyzed but also deep five and also monolith and um currently the so monolith still withstands these results and in particular the security margin remaining is still more than 30%. Um now if we think about something like round skipping um it means like this this permutation has six rounds if you can skip like one or two rounds is

devastating compared to Bidon. Uh but I don't think that's so easy here because first we have a full MDS matrix and secondly particular for the results in those papers. It seems very hard to bridge another round or even another two rounds uh which would be needed for a full attack. And that's it from my side. Thank you so much. Um the performance is is very impressive. Um my mental model here is that you're you're matching the the plain text performance of of SHA 3 and you're even faster than than Pedon 2 in in circuit.

So um yeah, pretty pretty amazing. Any questions from the audience? I I guess um one one question I have is are some of the attack strategies that have been applied to tip 5 potentially reusable in your context or are they not at all? Um I guess so some of those actually similar. The problem uh was so in particular for monolith it's not a problem it's a it's a I mean everyone knew about this is that the that the highderee sbox potentially allows for

nice differentials um you can avoid them pretty easily in boson and stuff like that where you have round lowderee functions but it's not so easy for monolith and these recent two papers show very nicely that you can uh exploit this low differential even though it's like protected by the by the squaring functions you can exploit this property and get through them. Uh yeah by doing something like uh which is called a rebound attack where essentially attack from from many directions. Yeah. Uh so yeah reusable yeah for similar kinds of constructions. Uh for sure. Yeah.

Okay. Perfect. Uh thank you so much Marcus. Next up we have uh Stfano who will talk about Arion. >> Thank you. I will try to share my All right. Can you see it? Yes. All right. I will try to be as fast as I can. Um, yes. So, I will presenting Arion. It's an arithmeticization oriented hash function instantiated from the generalized triangular dynamical system and it has been developed together with Arab, Matias Steiner and recently also Luca Campa joined and all right I just want to quickly do a

recap of the context. So most of the KP frameworks for verifiable computation operate over large nowadays can be quite um there is a a large range into what we mean by large it can be anything from 32 bits to 256 bits but let's say a large finite field FQ and algorithms can be represented as a direct cyclic graph which is a circuit and if the an arithmetic circuit or a boolean circuit right and in general the same algorithm depending on the field into which we represent is that the circuit can have a largely different sizes and um in general we want it to have a small size over the native field

of the zeon knowledge framework. All right. So how do we uh construct then a cipher for example or a permutation or a hash function because usually the design strategies are quite similar and the basic uh principle is like a product cipher right so we have a round permutation and then we compound it uh together with a key scheduleuler we get a a compounded permutation and this is the the overall construction so then the design basically boils down to how do we design the round function okay typically the round function or The round permutation in turn is designed often as um a structure which which has a nonlinear layer followed by an aine layer. Sometimes the two layers can be

interchanged. First you have the fine layer then you have the uh uh nonlinear layer but it does not really matter. So two two famous examples are the substitution permutation network or the two branch or the file network uh for the nonlinear part. And so it turns out that in 2010 uh Ostafa and Sperlinsky introduced um a kind of system of polomials which is called the triangular dynamical system. And this triangular dynamical system is in some way a generalization of uh several strategies that are used by typical by typical designs of designs of ciphers and permutation. And one nice

property about this triangular dynamical systems is that it can exhibit degree growth anti iteration with proper choices of the uh G and H functions uh which implies low discrepancy and in fact they used it already back in 2010 to build abs random number generator. So um in a work which is very uh related to Arion which is the generalized triangular dynamical system by Arnard Bro and Matias Steiner uh this triangular dynamical system was extended into a generalized triangular dynamical system. The the main difference is that uh in addition to the G and H functions uh we have these permutation polomials that are applied to the to to to the variables and there are some constraints

which require that GI has no roots which make the system invertible and in fact since GI has no roots and PI is a permutation polomial uh we can easily invert the the triangular system the generalist triangular system by applying this formula. Um yes. So just to see how this framework generalizes existing constructions. So we can see that we can obtain a full or a partial SPN just by cancelelling out the G and H terms or we can obtain a generalized fist still by cancelelling out the P and G terms.

and uh even more recent constructions. For example, this generalized horse scheme that was proposed together with griffin and the brick scheme that was proposed together uh with reinforced concrete. Uh these uh kind of structures for the internal permutation can also be generalized by this triangular generalized triang GTDS. Um yeah. So what is Arion? Arion is an arithmetic generated hash function defined over prime prime fields a prime field fq uh where the nonlinear layer so it's a product cipher and there is a a matrix multiplication with an a constant addition so a fine transformation and inside there is the nonlinear layer and

then linear layer is an instance of the GTDS and how did we select this instance well we selected it in this it in this way so we have like that the permutation polomial is a monomial allow the grip power map in specifically except for the last branch because for the last branch which was a high degree power map and then the G and H functions are both quadratics and in particular the G quadratic is irreducible so since it's quadratic it has no zeros and um which allows for invertibility and uh one key difference is that between like existing constructions which exploit these highderee uh power maps is that uh we choose D2 to have low

aming weight not necessary to be the in to be the same as D1 because the thing is that in plain performance let's say in plain execution the evaluation of the inverse map is expensive regardless of how you choose the the the original value so one overd is expensive to evaluate and so this allows like a trade-off between the uh arithmetization complexity and the plain performance and Um yes so the other parameters are chosen such that everything is invertible and uh about the security of the So for statistical crypto analysis uh for this kind of constructions

especially over large fields is not really that much of a threat. uh well you have lookup based uh construction that is a bit of a different story but uh uh for this kind of purely algebraic constructions let's say differential crypto analysis and linear crypto analysis are not too much of a threat and so we have very good bounds in terms of security I forgot parenthesis in the linear correlation but yeah should be in parenthesis uh algebraic cryp analysis however is the most uh important threat in general for these arithmetic designs and in particular for Arion uh okay so interpolation attacks we need a baseline number of rounds to prevent those especially in the case one tries to do a meet in the middle attack. Uh and for the SOC constraint input

constraint output problem which is especially relevant for spongebased hash functions. Uh the complexity of which generally depends on the quotient dimension. Uh we have a bound which uh we computed and from which we derived the number of rounds. Uh but then there was an attack that the freelance attack which showed that you can skip one round and this attack is what actually dominates the cost when choosing the the number of rounds. Um so we have a number of uh these are like the round numbers.

uh our design originally was for the BLS 12 MBN 254 uh elliptic curses scalar fields and uh so we compare performance with other permutations and just a note for the following the tables that will follow is that uh we adjusted some of the round numbers of the other constructions to match the attacks that were also applied to Arion. So let's say the cryp analysis level was the same. It's not necessarily the most upto-date but it's on the same level. Uh so for plane performance uh these were the results that we obtained and over the BN254 scalar field and uh interestingly while Aron is like the other highderee uh constructions quite slower than Poseidon or Poseidon 2 it was still uh significantly faster than other inverse

uh power map based constructions like anoya griffin or rescue prime at least in this setting and for punk matization. Additionally uh our area was for medium and large sized uh instances was the best uh required the lowest number of plunk constraints. A plon gates except for like 2 to1 there was the second best griffin was a bit better and uh for R1catization we are not quite as good but we're still very competitive. We're still in the same range as the other constructions. So uh ENMO is the best in R1CS. Griffin is also competitive and Posidon is a bit worse. So we're basically in the same ballpark as

Posidon. And for air arithmetization, here is where like construction like rescue prime shine. But Arion even here is still very good. It's the second best for medium and large sizes uh permutations. Uh comp these are compression rates. So basically large size permutations. so in conclusion is a hash function based on the generalized strangical system was security uh derives from the generic crypton analysis that as done on on this construction but it has been refined. It offers it offers plain performance which is better than other highderee designs and the lowerization cost across different techniques. So this can actually be a good thing if you want to integrate systems which use differentization techniques. They use

the same ash function. So maybe it's very expensive in one for example I think about lookup based techniques right if you have a framework which has lookup support in another one which does not have it then the cost will explode so we have loweration cost on across different techniques and the further consideration just I want to point out that um there have been this compression modes like trunk trunk and j which achieve better efficiency than sponge but these are not randomly differentiable and crypton analysis can be different and so we recently proposed a mode which is called pax that unifies and generalizes both the sponge and compression modes and is appearing soon.

U thanks for your attention. If you have any questions I will be glad to answer. Thank you so much uh Stefano. Uh we're way over time so uh we're going to move on but uh any questions feel free to uh ask in the chat. Uh we have two final presentations um including one which is unpublished uh called Benex. That will be the very last presentation. Uh congrats to the 50 or so people who made it so far um two and a half hours in. So Sundas uh the floor's yours and then we'll have Fabin.

>> Thank you. I'm sharing my slides. Uh can you see now? >> Uh it's loading but it should load. Yes, we can see it. Yes. >> Okay. So, today I will talk about the XES. I did this work with Omar Ahmed Al Muhammad and Leo. It is available on errint and just this week we received the Septan news from journal design codes and cryptography.

Me briefly outline the structure of this presentation. First I will start with the motivation where I explain the idea behind this work. Then I will give the design overview. After that I will discuss the state size and security. Finally we'll present some benchmarks. The motivation for Xash is to combine the marvelous strategy with a new type of SBOX. These Xboxes are based on exponentiation over an extension field which allows us to apply the nonlinear layer to a vector of field elements rather than processing each element individually.

We explore two versions of XESH and implement them over both Goldilocks and M31. Uh from this construction we propose four concrete hash functions. Two are optimized for uh zero knowledge starks named X12 Goldilocks and X-8 Goldilocks. And the other two are optimized for circle Starks named X24 M31 and X-16 These two versions can easily be adopted to call.

Here you can see the first variant of XSH. Let it let me explain how it works. First we have uh I can show pointer. Yeah. First we have an fstep. It starts with the round constant injection followed by an MDS multiplication and then a nonlinear layer where where we apply a power map power map X al X alpha to each state element. Next we have the B step which is start by the MDS multiplication and then the uh wrong constant injection and then again we have a nonlinear layer but this time we use the compositional inverse power map.

After that we have a P3 step which start with the which is basically on the exponent extension field and here we first did the round constant injection and then the nonlinear power map is the cubic extension field which maps the state element again back to the base field. So f and at the end of all these three steps we have a last step where we did an MDS multiplication and then the we added the round constants.

So based on this design we construct two instances x12 goldilocks and x 24 m31. And here the alpha the choice of alpha depends on the field. So for the Goldilocks it's seven and for the M31 it's five. On this slide you can see the optimized version of excess design. So the key idea here is to use the partial layers of the compositional inverse SBOX means instead of applying the nonlinear layer to the entire state we apply it a subset of elements which improves efficiency. So based on this design we construct two optimized variants named

X-8 Goldilocks and X 16 M31. So here I will summarize the design part first regarding the ST size. Goldilock base construction uses 12 state elements uh with rate 8 and capacity 4 while the M31 base construction use 24 state elements with rate 16 and capacity 8. So in X-8 Goldilocks the compositional inverse power map is applied to eight out of the 12 state elements and in X- 16 M31 it is applied like the compositional inverse power map applied to 16 out of 24 state elements.

Um in terms of security goldilock space construction provide 128 bit security and the M31 construction provides 124 bit security. Finally all our um all four proposed head function consist of six rounds. Since I have no idea about the implementation however Alkini from the miden team help us with the benchmarking in clony using clony 3 on Apple silicon we see that xash is about time slower for goldilocks but when adapted to smaller fields they offer better performance. Here you can see the comparison in case of

Goldilocks for R1 CS long and air representation and the most efficient hash function in each representation is highlighted in bold font. And in this slide uh all of you can see the performance comparison in three representation in the case of M31 field and same the highlighted uh efficient one hash function one is highlighted in bold form. Thank you.

>> Thank you so much. Uh great Um, any questions for Sundas? I guess one question I have is, as I understand, you're currently working full-time on hash functions as part of your PhD. Are you looking to design even more hash functions or are you kind of happy with Xash? Uh yes, I'm currently look uh working on the uh design part of the function.

Actually, I am currently working on one new I'm currently working on designing a new hash function. Uh hopefully soon you will get that you will see that design and also I'm focusing on the crypto analysis of Poseidon. So I'm working on that too. >> Okay, very exciting. Looking forward to the new hash function. >> Yeah, thank you. Final talk of the day uh from Fabian. Um he will talk about Benex uh a very new and unpublished hash function.

>> All right. Thank you. Um I hope you can hear me and see my slides. >> Okay. Perfect. So yeah um thanks for having me and presenting and presenting Benex which is um a joint work with a lot of people you've you've heard already today like L or Marcus Ofano and also others like Thomas Luca and Amnab and yeah uh so let's get right into it. Why do we need a new hash function? I mean this question is a bit hard to answer I would assume but our starting point at least was um that one of our partners worked actually on um on specific hardware for cryptography and there there was a realization that we

have usually these huge areas reserved for the number theoretic transform in there and then we have a huge area also reserved for hash functions in there and then maybe the the main idea was to use kind of the structure of the entity or a kind of larger entity blocks to then build kind of a hash function out of it. However, along the the line of of working on this project, we actually realized that the performance gains that we saw were interesting in their own merit also for for kind of um application outside of of purely hardware. All right, so um let's dive in to um the core building block which is the ban network that we use to build up our hash function which is essentially

uh kind of like a butterfly construction we may have seen in in anoy or in other designs. we essentially have two branches um two input values that basically are used to produce two output values and all of them um are fed into four different uh functions and this is kind of the core building block. Um however of course when designing a hash function um by designing a permutation first we want each building block to be invertible. So of course we had to first uh find a way to make these individual functions together produce an invertible uh full building block and uh quite generally um we state uh the following way of course I haven't updated the

numbers here um to be zero indexed as as uh to the right in the image but essentially if both functions on the left branch are the same and then the difference between the two functions on on the other branch of um a permutation uh then the whole resulting network is a permutation over the two uh values. Essentially this is a generic method for all primes but to be a bit more precise we of course looked a bit um at the concrete uh primes that most of us are interested here and then also thanks to Ramco for saving this slide and and arguing why this is still called Goldilocks. Um yes indeed we looked into koala bear messen golilocks and baby

bear but this construction and the approach that I presented before and this of course much more detailed in the paper works for any prime really to uh create a permutation. So what does this mean? We have a lot of uh complex permutations in there polomials that need to be evaluated. However, if we look more closely at it, we see that we have kind of these common degrees and we know that f_sub_0 f_sub_1 belong to the same branch and f_sub_2 and f_sub_3 belong to the same branch. So for example, this value x to the 5 means the right branch always only needs exactly this exponentiation.

Um and uh this intermediate steps here will also be interesting because when you produce the value x to the^ of 7 very often you will anywaysh produce these intermediate uh powers. So you can evaluate this polomial with actually very little overhead when it comes to to arithmetization also. All right. So now we've talked about the nonlinear building block really and uh of course this is not enough. We need to of course also mix the entire state because we're not working over state size of two. So in a simplified form our construction could look like this. Of course it has up to um eight 12 16 24 element states but this kind of um propagates as you

would expect. So what's happening is that we have a pair-wise application of these um of these ban networks and then we need to think about the concrete uh matrix or concrete linear layer rather that we want to have there and we've gone through a couple of different uh possibilities where we looked at just having cyclic rotation as is used in a generic beness construction. Um we've also looked at of course non MDS matrices as they are seen in Poseidon but of course this uh whole call here is also about uh the weaknesses that these non MDS matrices introduce and of course uh we know that MDS matrices um alone are costly. Of course,

the idea is I think somewhat akin to what we see also in in anamoy that we essentially have an SBOX that is applied on two elements of the state which allows us also to split the MDS matrices on these parts of the state. So how we frame this is um to look at the output vector of such a computation as a vector of extension field elements or quadratic extension field elements where we essentially can shrink the the state vector to half the size where each element now is a polomial of degree one essentially and then we can apply the same MDS matrix to this uh vector in the extension field um to get an output

again in the extension field which can then be reinterpreted again into the regular state size where if you only look at the implementation of things. It's important to note that this reinterpretation and interpretation in the first place don't actually cost anything. This is more of a mathematical conceptual representation really. So what we have implementation wise again is really the individual matrix um application onto the even and the odd elements in our state vector and >> oh is that yeah okay um and um this means that our dimensions of the matrix are halfed um so in total total this shrinks the matrix to a fourth the size

which makes essentially finding good MDS matrices a lot easier and that's also something that we've heard in in a couple of talks before that um a lot of the cost in the plane performance comes from evaluating these MDS matrices and then finding for example low Hemingway MDS matrices or circulent MDS matrices that can be evaluated with the forier transformation. These tricks are all of course much easier if our MDS matrix is smaller. All right. While still of course retaining the nice MDS properties having the high branch number. All right. So um now to some instances of course uh the instance kind of the final product of a long cryp analysis is

now in the caveat that this is and um yeah this is a great team we're having but of course this is only internal crypto analysis as of now. So we're really looking forward to having outside eyes looking onto it. However, of course, to the best of our knowledge, we tried to integrate especially all the new findings on all of these constructions to really have a comfortable security margin and arrived at the following round numbers that you can see at the very right of this table here for the different primes. Uh the slight differences in round numbers are mostly due to also having a higher degree in in some of the primes. All right. So now getting to the evaluation of the hash function. Um we've evaluated

everything in ploni3 and used for that exactly the parameters as the different hash functions are implemented in there. So um yeah when some hash functions are not implemented in some settings. This was due to not uh to them not being present at the time of of coding this. Um, of course there yeah um I'm also happy to include more in the table in the future. So what we're really seeing here is that Benex in the plane performance positions itself as I would say on par with Poseidon in in some settings. I think in Koala Bear we're really close. In baby bear, Poseidon 2 has has a bit of a um head start so to

say, but in the Meran and Goldilocks field um we are actually faster than Poseidon 2 where only Monolith um is faster. Um however, of course, Monolith applies the split and lookup strategy and this may just not be available in all proof systems and settings. So this is definitely something where where Benex can also be interesting an interesting choice. Um and uh comparing to Poseidon one if we want to move from POS away from Poseidon 2 al together then we see that across all prime fields um yeah we actually have uh the superior performance and um yeah one important thing to note also um it's not provided in plunky free but also the assumption

would be that our MDS matrix actually um increases in benefit for the larger state sizes. So for the sponge construction where we use a state size of 24, we actually expect the advantage against monolith of this linear layer to be somewhat larger and to be either on par or even better for some of these primes if implemented. All right, so now let's uh look at the proof system comparison. We've also evaluated this in um in plonky 3 where uh for the sake of fair comparison we really just implemented what was already there with exactly the parameters provided and then also implemented our construction with the same set of parameters and I think we have kind of a a nuanced view on

this. I think Koala bear is also chosen in a way because of of the nice performance for Poseidon and I think this is due to Poseidon having the degree three power map there and we see we can only get around half the throughput for our proofs uh with a slightly larger proofs and um however for baby bear and golilocks we see that actually our proof of throughput is much much higher um which is of or of course I think I think it's a bit in essence the the situation is the following in baby band golilocks you have a degree seven power map in Poseidon which is the same degree as our

SBOX and when doing the constraints efficiently you can essentially use exactly one constraint uh per branch in the Sbox which is exactly the same number of constraints that you would have in a full layer of POS Poseidon. So already with eight full rounds in Prooseidon 2, this would equate almost the entire constraints already that we have for our S boxes. And then there's the partial layers on top of that. So I think that uh kind of explains the the significant difference that we're seeing here. All right, I think that was a a quick way throughout the paper skipping a lot of details of course. I hope I could still convince you that this is

some interesting project that we're having here. Fundamentally we have a design that's built towards hardware sharing where we can really reuse these data paths of this hierics entity um achieving higher area efficiency then >> thank you so much Fabian we're a little bit over time here uh but um looking forward to the publication that's going to be on e-rint right >> uh it's going to be on e-rint next week and and then submitted as well >> okay amazing thank you so much for Fabian for for doing this final present presentation and uh thanks to everyone here who has endured 2 hours and 45 minutes.

Bye and see you next time.