leanConsensus Call #2: Post-quantum cryptography

Transcript

hello and welcome to beam call number two this is going to be an extremely uh busy call uh we are 2 minutes past the hour we have 60 people on the call and more people trickling in so uh what I'm going to do is share my slides and uh we'll get started so today's call is about sharing some research up uh updates uh especially related to post Quant and cryptography initially I wanted to give an overview of updates across all the different work streams for the beam chain project but it was just way too much content so instead I'm just focusing on on the postquantum cryptography before we get started just a few points on Logistics first of all

we have the airm protocol calendar this is a public calendar that anyone can subscribe to um and it has all sorts of of uh calls on there the or devs and you know F or call epbs you name it uh and now we also have the beam uh calls uh that's advertised there and uh here's the QR code if you'd like to subscribe we also have um you know if you're new to eum R&D we have a Discord dedicated to eum R&D here's the uh the QR code it's it's uh Open Access um and what we're going to be doing is advertising the calls in the consensus Dev uh Channel and maybe in the future if there's more and more discussion uh

around the beam chain uh then uh we uh we we might add a beam chain Dev uh Channel as well and then one uh apology here is that at this uh moment we have another uh affirm protocol called the epbs uh breakout uh room um and so uh going forward I'm going to be mindful to not uh conflict with this call and this call happens once every two weeks so I'll try and schedule the the calls on on alternating weeks so that we we don't Clash now um what I've tried to to show in this slide basically is uh projecting the schedule for 2025 at least as a strawman uh we've had beam call number

one which is the social updates and the way that I'm envisioning things but this is you know subject to change of course is that in the first part of the year we have a bunch of research updates on various uh subm modules uh of the the beam chain project various work streams postquantum phography p-to-p networking finality ATT test the propos of Separation things like that and then towards the second half of uh the year in 2025 uh we can start moving towards uh specifications um some of these uh subsp specifications uh are already in progress so for example um you know 3sf uh is is already in the process of being uh specked out

and then towards the end of the year you know hopefully we can put all of the pieces of the puzzle together and have some sort of a holis uh beam spec uh for for for the whole beam project now I'd like to uh do two things in this talk first um kind of continue a little bit from beam call number one with a few more social updates and then get into the the mey technical stuff uh with with part two uh and just as a preview uh today we have a lot of speakers um uh eight speakers and the first two will uh give us social updates and then uh we have six uh technical uh speakers so on the social

updates the first thing that I'd like to to highlight is uh the importance of the existing mainl uh consensus layer client so beam call number one basically started with eight the eight new teams giving an intros and then the six uh other teams the existing uh main net client teams uh giving giving upd um and basically there was in my tweet there was this one screenshot of only the the the new teams uh everyone knows who the who the existing teams but I I really want to make sure that we're all on board in in in in common understanding that the basically the existing teams are are essential they're very much critical because of um of all

of the knowhow that they have all of the libraries that they maintaining all of the adoption and reputation that they have have among theim community and all of the diversity that they at so really there there's no way around it if we want the beam chain project to be uh successful the the existing uh Beacon um teams consensus layer teams are are absolutely uh critical um but at the same time one of the things that that I'm very mindful of is that uh the existing uh teams are are extremely busy with uh updates uh to to to to the beacon chain FM needs to progress uh we can't just stop everything and and all work on on the

beam chain especially while it's just a a proposal so really the one of the the goals for 2025 is to be this this buffer period of roughly one year for the existing teams to kind of get ready be prepared you know adjust things maybe you know hire one more person to to work on the beam chain or whatever it is uh reorganize things internally um and uh and basically give give these teams time and not create a sense of fomo where everyone needs to be uh working on on on on on the beam project now uh since uh call number one we have a uh a new consensus layer team

so that's the kakarat team um that has uh come forward and interestingly they they bringing uh bringing a new language to Ciro language uh to the mix and so I'd like to invite elas to to give a a quick one minute update uh on uh on why they're interested on the beam chain and and a few words on the vision oh thanks Justin um hey guys so my name is alas I'm one of the co-founders of kakat and um maybe I could share my screen for one sec on the single slide yeah absolutely um prepared okay thanks um it says disable share but I I can just say the content essentially so

we're 10 Engineers based mostly in France uh we've been working since end of 2022 on um provable I would say provable evm or provable blockchain infrastructure so when we started in um 2022 2023 we built the execution layer of e in Cairo which is then like a ZK and our goal for this year is to prove e one in in real time at least the execution layer and the natural Next Step okay okay I'm than just in um the natural next step is to go into the consensus layer um essentially

because snarky fangi THM has been our goal since day one and we realize that um we need the whole the whole thing and one one aspect I think is is very interesting for us is this idea of ZK stf I I know I don't want to spoil it so I let just talk about it later but Cairo is essentially a ZK DSL or a language that targets the Koo ZK VM which is uh a nice a nice addition to the risk 5 zkm landscape in that in that it brings a completely different uh I would say isolated um isolated code so that you you get the redundancy that you would want in terms of security you don't put all your eggs in the same basket um so

our team has EXP is in VM Carol python Rost Starks um we worked with Lambda class and nethermind in the last two years on like systems programming in the star EOS system and now most of our focus is on approving the E protocol thanks amazing uh thank you so much elas so let me continue on with my slides so yeah as elas hinted maybe there's an opportunity to basically have two different types of of consensus layer teams um and some of them could may be specialized in the the state transition function or the you know ZK

uh State transition function so traditionally we have one client that has a shell that contains all sorts of different subm modules the the networking the fork Choy State Management you know anti- slashing signature aggregation and you know one small part of it you know maybe 10% of the code basee is the state transition function um but maybe you know because the state Trans State transition function is kind of handled differently in some sense in the in the beam chain There's an opportunity to take that module out and and and create these U ZK stfs that could be used as libraries a little bit like blast you know is a library in the context um of uh of of BLS signatures uh and this ZK CF you

know has various unique properties first of all it's consensus critical so it needs to be exactly compliant with with the spec uh and it needs to be SN friendly and so that means that you know maybe um one could use a language that that that is maybe more more amendable to formal verification um or there could be annotations to the code I don't know that makes it more easily formally verified and maybe a different language uh for example Cairo a DSL a domain specific specific language uh could be used uh to to write the stf so that we have uh we have excellent performance um and uh you know Cairo is is is basically designed for performance

and so maybe there's an opportunity uh for for the Kakarot zkf to be you know several times faster than the Alternatives that that would use a a risk 5 zkm for example but I guess ultimately the we'll see what the performance numbers are and so one kind of strawman example just to illustrate uh we could have Kakarot provide the zks stf and an existing team for example prism basically consume that zks stf as a library so that's one way in which kind of the existing teams that are specialized in in shells if you will uh can collaborate with some of the new teams uh that that specialize uh in in notification okay final slide uh

regarding the the social updates um I'd like to invite Lis LA to to give us an update on on the renaming progress yeah hi folks um just a very quick update uh so far we've come up uh with about 75 uh unique proposals uh for Rebrand so thank you very much to many of you who've uh submitted those proposals over the past couple of weeks um some funny ones some more serious ones some very consider considerable ones um yeah so our plan or idea currently is for the for the upcoming um time to leave more or leave a bit more time for for even more proposals so please hit me

up um uh and don't hesitate to reach out in the meantime we'll be starting to sort of start curating come up ideally with a uh with some form of of due diligence accordingly I guess and and come up with um uh with a short list which we intend to Circle back to client teams first to give them a vote and ultimately we're thinking about also giving the broader Community uh to to Chairman and Nevers say here yeah so trr uh open for more proposals uh it's looking good we're making progress and I'm optimistic we find naming wise find a a beautiful new home uh for project fairly

soon amazing thank you LL wow I didn't realize we had 75 suggestions that's that's pretty cool so uh let's move on to the meat of uh of today's call uh research updates on on post postquantum cryptography and uh one thing I'd like to to highlight which actually is a is a social update is that uh we now have two new members of the applied uh research group um both of which are are SN uh experts um and both of which are are helping out with with the beam chain project so we have uh tomar and and and Han and um below here you have the the the telegram handles which have been shared

shared with permission if you'd like to um if you'd like to contact them now the the highlevel direction uh that uh that is being suggested for the postquantum uh signatures is to use uh hash based cryptography uh throughout uh and actually the the design was suggested by by vitalic in 20 2018 I I went back to the to the uh you know telegram archives and here's two two little Snippets that I found one are Lamport signatures optimal for staric aggregation and two Lamport aggregation may actually be not may actually not be

that hard um so basically vitalic was asking you know that was before BLS was even you know suggested um can we uh can we use uh signatures and and and stocks to to aggregate um and I find this this part like you know quite quite funny in the sense that you know actually it is quite hard uh and you know this idea was was suggested seven years ago and only now finally has the technology matured enough that we can you know seriously consider um having this this direction of hash based signatures such as Lamport being uh sned uh uh and and and aggregated uh using this this

technology now the the the the strowman proposal uh you know starts with a hash function that is a a foundation uh and you know right now what's being suggested is Pon 2 and then it's hashes and hashes and hashes through Merle trees so we have uh this notion of winternet which is a variant of Lamport signatures which you can think of just being you know a fancy merel tree um and then from these onetime signature atures so these are signatures where the private key can only be used once there's a very easy transformation called xmss uh which is another Merkel tree actually the uh the M here stands for for Merkel um and you can go from

onetime signatures to to many time signatures and then the suggestion is to use even more Merkel trees specifically to use snars to to aggregate postquantum SNS um and the the basis of postquantum SN is something called you know an IOP of proximity or an IPP um you you may have heard of fry um and basically we have this this this new design called were uh which is just you know an upgraded version of fry which is which is more performant that is being suggested to be used and then finally we need a way to do a recursive aggregation so if you have um an an aggregate signature here and another one here you

want to take a a meta agregation if you will and for that uh we would need some sort of of a simple virtual machine to do the the recursion part uh and here this is a name that you know I just just coined this morning uh ssk so in the same way that we have ssz SIMPLE serialize we might have simple snakify uh which is like a minimal virtual machine uh that would be used for recursion and recursion of SNS is kind of a little bit more complicated than uh than the the verification of of postquantum signatures like like xmss um and so it could be D it could uh

this this this simple ZK VM could be used for both the recursion and for and for the the signatures now um in this slide here what I've started doing is um basically sketching a a a mind map of of the the whole Beam Beam chain project and so Lis La told me hey isn't there like a formatting issue with this slide um so what I've done is that I I want to try and fit on the whole slide uh all of the uh beam chain are r& the uh progress uh almost like a tapestry and kind of here we're just starting with the the postquantum cryptography so what I've done is that I've started with the

smallest font possible which is font size one and um and hopefully we'll be able to fit everything on this one slide as we progress uh uh through through the year so let me walk you through this kind of mini mini mind map and then we'll open it up to to presentations from from uh other researchers so the the way that it's structured is that there's this strawman proposal right this is what we're currently thinking as being the most likely candidate for something like like a like a beam chain upgrade and we have these various modules uh and you have you have links to to to the research so we have posidon 2 which is a variant of

posidon uh we have winternet based xmss where paper was suggested recently and we have uh were that I that I mentioned which is basically uh an improvement over fry which is very well known uh and then we have Tomar who's uh working on the the minimal recursion ckvm and so I guess as uh you know as researchers we're doing two things on the one hand sorry about this uh will let this last if you could mute that' be great thank

you um so basically the couple things that we we'd like to do one is try and drisk and accelerate this this strawman proposal um to to try and you know find any problems as quickly as possible and if there are no problems just trying to accelerate the development uh as far as we can and secondly we're considering alternatives to these various modules so on the acceleration uh side of things uh we have a crypt analysis uh uh Endeavor that we've already that I've already mentioned on on on beam call number one uh that is led by that by metri um we have some further

optimizations that are being uh researched uh by by Benedict and Mitri and and others above and beyond the optimizations that have been mentioned in in this uh ePrint paper here um we have um a a project which is um which hasn't yet started but basically the idea is that a a lot of the the postquantum SNS use um well can use if they want these information theoretic uh conjectures so basically mathematical uh conjectures which haven't been proved but I believe to be true and if you assume these conjectures

then you get smaller proof sizes for example you know roughly two twice twice smaller proof sizes and so one of the things that we're hoping to do is basically have bounties uh to try and incentivize people uh to to prove these fs and what we could do is is specify the the statement of these fums uh using uh a formal uh language like like lean for uh we have the formal verification uh effort uh which I've already mentioned on beam call one which uh Alex is is is is is is leading and we also have a benchmarking effort uh that that that that han han is is is is leading and then on the alternative side

of things basically for every single module we're considering different things so for example for the hash function well padon is not the only candidate right there's various other things that are being looked at um similar similarly for the the signature so uh one of the the Pres presenters today is going to talk about L lce based uh signatures which is you one of the the main alternative if you want to build postquantum cryptography Rel relative to uh to to to to Hash functions hash functions are are very nice in a sense because they're they're super simple they're they're minimal uh they're they're they're easy to reason about you can write you know um a lot of

nice uh security uh analyses and and and theems and also just aesthetically uh speaking it would be really really cool if we could build all of ethereum cryptography using just one uh single hash function and then on the the the ZK VM side of things the the SS ssk um basically we've only just started so Tomar only just joined a but he's moving extremely fast and there's various things that are that are being you know considered uh considered there and thas uh will be uh we'll be speaking shortly so without uh much further Ado I'd like to uh open up the floor to the the various researchers uh starting with

Mitri to give an update on cryptanalysis thank you Justin um do you see it yes okay great so um about miden Crypton this initiative that's well fortunately um since posidon seems to be that important Cornerstone for the beam chain we kind of expected it its usage within ethereum and we started uh this initiative back last year so the initiative contains uh in

exploring in more details posidon instances over uh Prime bit Fields mainly 31 64 and 56 bit Fields because those are among the best kind of mostly used in applications and most researched um by third party analysts I have to say that uh well traditionally in cryptography the security of hash functions uh draws from public scrutiny and this initiatives uh aims at inviting as much public scrutiny into posidon as possible within the next well roughly two years so the initiative is run by group of three Within efr by Antonio Jorge and me we have also third party

Advisory board that uh may confront us on all decisions taken and kind of uh makes a third party evaluation of all our important money spend decisions so um the initiative contains of three five main points it's bounties for breaking reduced TR verions that are supposed to uh evaluate the security uh search grants uh workshops where crypto analysts gather and try to break something awards for really good papers and so- called gner based exploratory so the total budget for 25 is about 600k and we go along this budget sorry to um interrupt there's

little Tri rectangles on our end of gray my guess is that it's the zoom that has uh basically uh is showing stuff okay in front i' I've moved the the window out do you still see yeah that's better yeah perfect thank you okay uh sorry about it um okay so we have five items let's go with those uh quickly so bounties uh there are 66k already earned but nothing really groundbreaking so we have designed several instances to be intentionally weak to attract more people and we have already four or five different teams that compete for these bounties so I think we're progressing

quite nicely about it so research grants we have declared 10 different targets uh sort of gaps in theory and they already have three good recipients chosen they are starting working actually next week so for workshops we already have one Workshop uh in January and we'll have two more one is collocated with the encryption conference in Rome another one with eurocrypt in Madrid so we'll have quite a dense program where people will deliver talks about Poseidon and its very security properties um including for example you may see it like in in FSC will have a talk at 11:45 devoted explicitly to the security requirs to Poseidon in context of hash

Bas signatures so people will know um and that this is a avable target so uh for fourth item the research Awards we're still waiting for good candidates but papers get published so already in 2025 there are several nice papers that analyze Poseidon well they do good thing but they don't break anything um and finally the gr ra exploratory it's a series of experiments to be run on special Hardware we plan to buy this Hardware it's well pretty expensive but we think it's worth it so it will be supervised by top gra neur basis expert Ludovic Perez we have almost agreed with him to to work on this topic for us and I think if he covers that that would be

kind of our uh really great achievement and well so far so good and I think Poseidon Still Remains secure but of course we're exploring tent as well amazing thank you Dimitri by the way if anyone wants to ask a question just raise your hand in zoom and you'll have an opportunity to ask your question um I mean from a from a specking perspective the um the hash function is is really nice right because all of the work is done ahead of the specking and then the spec is it's just uh you know one line of code um if you're just importing a library or you know a few lines of code if you're if you're you reimplementing

um posidon 2 and you know my kind of left curve take on on Pon is that you know when you look historically at uh shat two in the context of Bitcoin and uh cat check in the context of ethereum both of these hash functions were 8 years old when they were chosen by by Satoshi and and vitalic respectively uh and so you know uh pedon is is 5 years old now so by the time the beam chain is is is relevant let's say in three years into the future the hash function will be 8 years old and it will be uh relatively relatively mature and on top of all of the acceleration that we're doing with these bounties there's an implicit Bounty uh through all of the

l2s the ZK rollups that are using padon we're talking about billions of dollars and hopefully soon tens of billions of dollar that are that is basically being secured by by this hash function so I'm you know overall very optimistic that in a in a few years time it will be uh considered to be a very safe hash function I'm not seeing any hands up so I'll just move on to the next uh speaker just for uh time reasons uh Benedict you're you're welcome to take the stage to talk about xmss okay can you see my screen and yes okay yeah so I will just give a few updates on postquantum signatures and uh

in particular how we want to replace BLS signatures uh with something post Quantum secure Justin has already mentioned we will focus on hash based constructions so let me first tell you what we have already done so uh there's a paper that we have written and uh published on ePrint it's called hash based multi signatures for postquantum ethereum and and uh yeah there's also the relevant code out there it's on GitHub it's a prototype implementation of this so what do we do in this paper we give a family let's say of proposals of candidate constructions that we could use as a signature scheme and then we give a rigorous mathematical security

analysis relating the security of this thing to the security properties of the underlying hash function so that is a security proof assuming properties of the of the underlying hash function um and then we also did some preliminary benchmarks using this prototype implementation so just to give you one uh quick look into it just uh one impression of how this thing performs so here we have a table taken from the paper uh the different rows represent different instantiations of our framework so as I said this is a family of proposals we have different instantiations of it now let's maybe look at one particular one that is I think the most promising one uh it's

this road and I want to point out three things so the first is the signature size is below 3 kilobytes then the second is if we look at signing and verification times this is extremely fast so this is below one microc um we pay some sort of price when Bel one M uh yeah yeah sorry uh 1 millisecond yeah below 1 millisecond we pay the price when we look at Key generation key generation is in this family of schemes quite expensive uh so here it took like 11 minutes to generate a key that has a lifetime of two to the 20 slots but actually uh last week there was an pull request on that repo and now

it's much faster so just simple parallelization improved that already um so that was the second thing and the third thing that I want to highlight here is the number of hashes that the verifier does this is important when it comes to how efficient will aggregation be uh and this is uh as we see here below 200 posidon permutation calls uh to verify a signature uh so this is the most promising candidate that we currently have uh and what Justin already mentioned before we are working actively on uh improving this uh like getting more optimizations uh but this is work in progress and it's not it's it's not clear that uh the complexity that we

that we add by that is is really worth no sorry the the Improvement that we get is worth the complexity that we had uh yeah so this is our current candidate proposal and now let me talk a bit about next steps what what needs to be done um so the first is what what demry has already uh talked about is the security of posidon so as I said we give this rigorous security proof but in cryptography security proof is never unconditional you will always prove Security based on some assumption the assumption that we make here has uh the form say posidon is 170 bit secure in this multitarget Collision resistance

notion and so this is something people should study crypto analysis should study uh because if this does not hold then the whole scheme or the analysis is essentially useless and the second uh direction is to study the efficiency is this proposal really efficient enough uh so first of all we need to of course figure out the constraints so for example I mentioned this this table was for a lifetime of two to 20 slots so we need to figure out what is a realistic life time that we will really uh accept uh in practice and this will change parameters again so this has a minimal but some kind of impact on all all the overall efficiency of the scheme um um

then of course we need to decide how we aggregate these signatures using a PQ snar so uh in the paper we just focus on the individual signatures uh picking which PQ snar uh you use is is uh still open and once we have several candidates for this pus we need to study the efficiency of the aggregation uh so as I have already said this first direction is something where the posidon initiative is very helpful what dimetry has already discussed and uh the second direction is something where Han and tar and the whole Arc team is essentially looking into it um to study how do we aggregate these things

what is the snar that we use and how efficient would that be and then finally there's one thing I also want to mention uh is that since we have put this paper online there are a bunch of researchers actually uh contacting us like researchers from outside the ethereum Foundation even from outside the ethereum community contacting us and saying okay we have another idea how to how to do this uh another proposal and so we are in contact with them to figure out um whether their proposals are really uh worth looking at and whether they could beat uh our proposals uh in principle and so I think this is uh a thing that I want to say finally this is

just a proposal other ideas are always welcome and uh still I think it's a good proposal so yeah that's it from my side Benedict thank you so much any questions just raise your hand um or you can unmute and just ask the question I will I will have one just you it's pry quick how with a with a slot of 4 seconds how to the 20 how long it will correspond thank you Antonio uh 2 to 20 4 seconds that's like 50 days so if we want to go to something that is more realistic like and just to be clear that means after 50 days your key would

be expired and you need to register a new key um for example by deregistering as a validator and joining as a new validator uh if we want something that is more realistic we could go to something like 2 to the 24 2 to the 26 um that's going to be something like 2 years uh yeah so just with a bit of uh blow up in the lifetime we we really get uh to something that is more realistic and uh as I said this has an impact on parameters but only a very small impact on parameters so don't expect this to change the signature size too much um it

will change the the key generation time and that's that's the main reason why in this table we only looked or in the paper we only looked at these lifetimes because if you want to have larger lifetimes you need external memory implementations of key generation and all that stuff there's a bunch of engineering challenges Associated to that but they are all solvable Terren thank you yeah I will also be very quick I just want to mention that there is this also tradeoff of U right so today as a E2 validator I generate my key it just one pair it's very simple I I can transfer between different U validator instances and then I have to be careful of not getting

slash but some in this setup I have to do a little bit more work I I have to generate Keys ahead of time and then say say maybe like a bigger size of validator because today validator client supposed to be very lightweight so I'm not saying this is a blocker but it's just something to think about uh yeah but strictly speaking this is still just a single key just the secret key is very large that's like formally this is this is just a very large secret key and a very small public key yeah and what you can do as well is have a a tiny kind of Master secret key from which you rederive like the lar exactly the there is some trade-off you could you could even have a very small

secret key what Justin says the problem is you need to expand this in time because in the your 4 seconds you don't want to spend a lot of time on expanding your secret key first so you need to there are sort of engineering challenges but I think they are all solvable and from a ux standpoint um what I have in mind is that the lifetime would be closer to you know 10 years or 100 years and as you said Benedict it wouldn't dramatically increase the key size sorry the signature size maybe would get closer to three 3 kilobytes yes call why don't we go the opposite direction and have the uh number of keys be rather small and then just have your

uh validator your VC or whatever be waky and constantly in the background so you have to replace your key every week or so yeah that's an alternative option yes that would that would probably correspond to the two to the 18 then but as you see the signature size does not really is not really impacted so it's it's not clear what we would gain from that except that the size of the secret key the expanded secret key would would shrink but the signature size is not really affected that much yeah sure CU it's in the tree um but it does help like the the ux of spinning things up and having to store keys or red whatever yes yeah

yeah okay thank you so much Mantic uh and one thing I want to highlight is that winternet xmss even though the name is very scary it's actually a super simple construction and um you know Benedict and Mitri have this additional kind of trick of using grinding to make it even simpler where the the the check sum that you traditionally have in in winternet is no longer no longer there so it's really a a super trivial thing to to implement next up uh we have uh tomma uh who will be talking about uh minimal zvm as well as uh benchmarks and

performance yeah can you see my slide yes perfect so yeah hello I'm I'm Toma and I will talk today about like postquantum signature aggregation I will try to present as much possible result we have just highlight the important points both from the results hand obtained and also what I have observed so first let us start with some benchmarking that we have uh over like um Ash Ash in s and different possible implementation that with benchmarks at the end of the slide you have a link

that I I wish share afterwards where you can find all all of the details so among of the tested implementation plony 3 shows the most promising results on high performance CPU it achieves like around two millions poed permutation per second on koala bear compared to um 30k BL Blade 3 and 4K kak so this is still like very promising results uh but while the numbers for Blake 3 and ketak may seem lower uh this implementation are currently purely arithmetic and this

means that we have no lookup uh optimization that have been applied yet and this suggest maybe a little bit more work on this St um is also a strong Contender which perform very close to plony th uh so this make it also like a solid choice binus on its side perform a little bit worse than plun 3 and2 it's based as a remainder on binary Fields um when running on traditional CPU an important note is that posten current construction is not probably secure under binary Fields so the result

obtained with binus are with grel Ash and kak uh Ash Caster is also uh a promising option we will we will look at it a little bit more in depth in a in a second but this is the most performant option we have currently for kak with around uh six uh 60k hash per second and we have room for for improvement already 10% better right now and expander also provided recently uh strong result it seems without the polinomial commitment scheme but right now it seems they supported Oran so we need to check it again for all of the

detail you can check afterwards all of the precise result with table in the Benchmark we had like a smaller Grant work on ashter exploration this is a project initially uh s by Lev from what that was also part of our team and this is a like a bull check protocol uh for efficient bullan formula uh over quadratic stuff um and so in this in this in this framework um bu buan constraint are represented using polinomial coordinates instead of traditional bitwise operation we have

two key mathematical technique to make it possible Forin Theory and for methods that make this method really really fast and performance I can share also a link to like a stepbystep explanation on how it works very precisely the results we have currently by combining bull Che that is the main stuff that is new with ashc Caster exploration stuff with classical Su small field Su check achiev quite efficient result for proving system for kak uh but unfortunately right now this they still too slow in term of

throughput when compared to what we have with posiden result with both two and and prony 3 so we also did some preliminary work on ash Bas signature aggregation using some different techniques so our first attempt is to check some performance botton neck so we first uh did some initial tests using existing ZK VM such as sp1 or open VM but unfortunately our Test shows that the performance looks not that good even with pre compile due to slowdown introduced by by the zvm so we have currently a second attent that

is uh currently developed in in a repo based on the open vmover which supports luup additionally to the first attempt and currently can aggregate 2.5k signature per second but the proof is still quite large 3 megab so the optimization we are trying to do right now is um to increase proof speed with a simple prover to reduce the overhead and use a GK log up uh plus optimize air traces that we have right now this is just a draft a draft version of the air traces that we have and there

are lot room for improvement and we also targeting an hial proof size and for that we have different techniques that we want to check in this talk um for example Justin already mentioned the we initiative as well as tier that can both reduce the the number of queries and uh the proof verification size so I will also share this slide where you can find um the two uh link where you have like rigor description of the approach we have taken for that with the description of the circuit and of the gadgets that are used and finally uh we are looking into

some specialized VM uh minimal VM for Signature aggregation in this slides I have like just put the important points that we found that are important because we explored a lot of different possibilities using the current VM of the of the market so first let us Define our ideal VM for our use case this should meet three main criteria it should be ultra Ultra simple and secure reducing the complexity to minimize possible attack vectors it should be also highight performance because to ensure efficient proof aggregation uh generation verification

and also should have like a flexible arithmetization framework to allow different proving system to work seamlessly and avoid some overhead if we want to change a small parameter in our signature that is currently under exploration some important exploration points that we found using other VM of the market first like the binus M3 arithmetization that we found really good it's you can check the details but it can it had like a be directional data stream without temporal constraint and so it modifies a bit the current arithmetization of all of the other VM we have also like the of course the sp1 recushion system that is

directly included inside the their main VM and that provides also very good uh very good stuff we want to inspire also the KR proof recursion uh K is provable by Design because K is designed to be a provable language and so we have also this possibilities where we can Implement directly our signature scheme inside in kro and prove that uh we know that St currently provided some proving records and some re very recent GPU acceleration using iicle and so this is also important point that we want to explore and finally we have jolt and

open VM joh jol is really attractive due to its Simplicity meeting the first criteria that I mention on the top uh less than 25k line of code so easily auditable and easily to maintain we have also open VM that we are currently looking at which is like a modular ZK framework which is really extensible with a lot of seamless possible extension currently supporting for example poon 2 and it's also built on uh plun 3 which is a well accepted uh framework of the of the community for for the crypto layer and to finish with my talk also important point that we

want to explore in the future some G sty prover polyedra recently like shows like some proving rord fast test ZK PR with two a little bit more than two millions POS HH per so this is something that we want to check and we want to explore we also are currently in discussion with a creator of where to how we can best Implement that reduce our proof size and use fully this uh this novelty and finally we also want to explore much more of a binary field this is a very recent technique but shows a lot of promising results we want to study like

the CPU performance for recursion and also some ash exploration because as we know that posidon is currently not secure under binary field we want to explore more Ash function and check what we can do with that yeah so this is the end of my talk okay thank you so much uh Toma um I guess I do want to make a couple notes the first one is that if all of this sounds super super scary with have lots of words that you know you don't understand it's okay because all of that complexity will be encapsulated in a library like basically the equivalent of of of blst so as a as a Dev this is not something that that you you have to worry about um another thing I'll mention is that um

right now we're just trying to get an initial proof of concept to to to drisk basically this direction to know that the performance is good enough uh but we're not married necessarily to one specific solution because what will happen over the next few years is that the SN industry like independent of of a layer one is going to dramatically mature and commoditize uh and we can will be able to reap the benefits of that uh for free any questions for Tom oh go ahead I think you're muted sorry I was mut um so one question uh so with the rlabs team uh we are kind

of like experimenting by picking a ckvm right either we have a sp1 and r zero and then what we try to do is we kind of like mimic how the beon shake is working so we have the process functions in there right and then signature signature aggregation happens within those Leg State transition functions um you mentioned about like specialized VM for Signature agregation um but I suppose signature aggregation is part of the bigger say State transition um I wonder how would that specialized VM fit in with the rest of say State transition functions because I I assume like for a

ckvm you can't really have another ckvm in there or if it's recursive proving I suppose that it has to be the same kind of proving scheme or same same great question happy to take that one so um basically it's a bit confusing but there's there's two different types of ZK VMS that are involved the the first one as you said is where you're trying to snakify the whole of the uh the beam chain and here the snar ification is done off chain it's not part of consensus and you can use whatever ZK VM you want whether that's you sp1 res zero or Cairo or or jolt or anything it's basically a decision that the staking operator makes as to which uh ZK VM they

they they trust and want to use um on the other hand the Other Extreme is the minimal zkm that's only used for Signature aggregation and here for reasons related to slashing it actually has to be enshrined so the L1 has to understand uh the notion of a of an aggregate signature and for that it has to know precisely which zvm uh proofs are are valid and not valid and so here instead of letting the operator just choose the zvm like we I guess as designers of of the beam chain would pick a very specific one and one of the key design requirements m is that it be

super super simple so that we know that it's secure and we can do formal verification on this this one thing and instead of being a general purpose zvm that can prove uh you know arbitrary statements you know written in rust or whatever other high level language it does one thing and one thing only which is to aggregate the the signatures so it's much much much simpler um and um what you have to do in the state trans function is not aggregate the signatures but is to verify the aggregation of signatures so you're only on the verifier side of things not on the proving side of things um and yeah what what you would do I guess as a as a client de that's looking

to snakify the whole state transition function uh is that you know you'd have the the the verifier which is some sort of of library that you'd Import in the same way that you'd import blast and then you just compile that to r five or whatever other you know ZK VM Isa uh you're targeting and then you're done um so you don't have to worry as a developer about this this specialized zvm and I I think from from what I have seen also on our side there is a point about that currently with the very first po that we are doing we are working with the circuit so we transform the problem

that we want of Ash signature into a circuit but with this approach kind of a problem is that if we change even a small thing into our signature schema then we need to redesign the worldall circuit it can be insecure need new aits and stuff and so I think that the very minimal Z KVM will simplify that uh because it will allow like to to change slightly without having to deal with all of the arithmetization problem because it is encapsulated into the VM and but also we are checking like the overhead of the doing that because of course it will have like performance impact so we are checking if it is more performance than a circuit approach or like less

performant and how much less or more performant it is this is our current research topic great question thank you so much I have just share also in the in the chats like two links where you can check the the details of what we are doing right now with the circuit perfect and what we'll do as well is share all of the links to the slide uh for example in the E andd Discord okay uh we're going to be running over by 101 15 minutes uh next up we have uh Josh uh Beal um who is uh I believe from Yale and a student of of

benfish hi everyone um so I wanted to share a quick overview of our proposal for aggregating falcon signatures for the beam chain um so in this area I've seen like two main categories of proposals um the first direction is using Code based snarks um with hash base signatures um which as we just saw with plun E3 um these can be aggregated in real time um and then the second direction is using last Bas snark such as Labrador um in conjunction with last Bas signatures such as Falcon and these are concretely even smaller than xmss signatures however the main problem is that the verifier complexity of Labrador is linear in the witness size and the existing implementations would need um

more engineering effort and Security review so in our work uh our hope is to get the best of both worlds um where we can leverage the small size of Falcon signatures um and also the efficiency and practicality of code-based snarks um yeah hopefully that gives a bird's eye overview of our approach and yeah thanks to everyone who's already given feedback on this video wow that was very quick Josh thank you thank you thank you for this update um so you taking I guess the alternative direction to look into ltis Bas kns um and you're one of these teams outside of thef has reached out uh and I believe you you've also applied for a grant so

uh if you're another research team looking at this um you know do do do reach out and we we might be able to to work together um and as you said like one of the really exting things here is that you know 600 bytes is let's say about five times smaller than the the 3 kilobytes that we get with xmss so potentially if all the other performance parameters stay the same uh then we could basically support five times more at this attestations or or something like that five times more validators so the more we can squeeze on performance the more validators active validators if firms able to support Josh okay uh great next up we have Alex

who will be talking about uh formal verification efforts yeah thanks and hello once I'll share my screen uh quickly and uh we should have I'll get a sense for everyone to oh wait there um so Justin said a bit earlier uh let me just move the zoom seeing unless it does a bun of triangles like it did on the imry slides H so Justin said uh I basically lead the zkm form verification project um we're trying to basically form verify risk 5 kvms and that includes a cryptography track um the main thing that we're building on the

cryptography track right now are ex execute mble and formally verified specifications for proof systems uh this is in a repository called ZK lib which you can find on GitHub and I'll post the link in the telegram chat and the is R&D Discord right after speaking um so we have this nice framework in lean 4 to try and specify proof systems uh I won't go into too many details in just in the interest of time uh but the idea there is just be able to specify OB CD iops like fry stow and were for example now as Justin said these have conjectures Associated to them and so we'd like to be able to prove them so that we can actually prove you know completeness and soundness um for an General kind of security once

these are implemented into a pro system the way that we're doing this is going to be based on producing lean blueprints uh now lean blueprints are basically a way to organize uh big proving projects in lean that mathematicians have been uh using for for big projects so for example you know they're trying to prove from last in lean over the next few years and there's a lean blueprint for this the appeal of a lean blueprint is that you can write up a bunch of documentation Alex sorry to interrupt you we have another technical problem for you it looks like uh your screen sharing is kind of glitching um oh I don't know if something you can fix otherwise uh if you can share the link

to your slides yes so I'm just going through tabs because they'll be interactive uh let me try and restart sharing and see if that fixes it I'll try and share maybe the window rather than the screen um okay let me know if it breaks again and then if not I'll link to the tabs um okay so as saying so we have this ZK lib repositor on GitHub here and there's this idea of is it broken again no sorry I was just muting someone uh who fors um so we have these lean blueprints you can generate uh the appeal of

generating lean blueprints is that you can write down all of these serum statements without proofs all of the definitions all of the intermediary lemas and you can generate a dependency graph for basically the let's say final statement that you want to proove this is a lean blueprint uh for the prime number serum in lean uh once you have this you can see you have a big dependency graph of SE that needs to be proven in lean and from this you can take on any node and you have a link to the latch definition uh and proof of the serum as well as a link to the lean definition of the serum uh so you can see for example for the prim serum you might want to prove the uh smooth CH uh close theem you can get the latch proof uh here by just clicking on the note you

can also get the lean statement of the serum uh we have a lean blueprint for ZK lib which is under construction it's still very early days so the dependency graph you can see just kind of isn't really well formed yet um and so there'll be grants starting very soon uh for stir fry and were or fry stir and were rather um and so in a few months we'll have dependency graphs to to prove everything that we need to prove around these and obviously we can add the conjectures to these dependency graphs uh with any dependencies that we know of and obviously some dependencies that we we might not know of because the proofs don't exist yet um once that's done the nice thing is that because you have all the definitions and serum stated in lean

uh you can open a lean file that would have all of these and the appeal of having everything pre-stated means that obviously you can check that the statements you have are actually correct but also um you can put in a sorry here in lean this is basically your placeholder uh you can see it comes up as a warning uh that's explicit but it means that like for the example this ter which I wrote down uh you can put a story there and then you can use it in a later serum so this means that if we want to go slightly fast and we don't want to spend time proving you know prerequisites and coding the that have been you know known for the past you know 5060 years or so and that we're confident and secure we can just focus on proving you know the kind of high

level serums uh that we're interested in to relay to security and leave uh a bunch of sories there for people to fill in later on or in parallel uh for you know coding sued that we haven't yet formalized uh although we are obviously going to make some progress on that as well so this is the nice thing obviously if you remove the sorry uh the proof uh will obviously break and then this you can see breaks the subsequence serem you can fill in an actual proof this fixes everything and this is fine so you can imagine what it would look like for conjecture the conjecture would be assum that is stated that has a sorry instead of the proof and you can assign a bounty to proving that conjecture and what the only thing that someone needs to do to prove that conjecture is to submit a

poor request uh that fills in the serum without any errors from lean type Checker um this makes it very easy to check you can see see if I submitted a wrong proof uh by changing a l here uh the proof will break and so the nice thing here is that lean will do the job for you of checking that the proof is correct uh this is quite appealing because obviously if someone does submit you know a very complicated hard to pass proof about you know the the fry conjecture uh you don't want ideally to have to spend a ton of time reviewing the the proof itself to be able to pay out the Bounty uh this can take a while and obviously there's a chance of someone making a mistake during the review process uh by having things in lean people can submit a PO

request in lean uh and you know to type check if lean will do the job for you uh you have to check a few things such as no one has introduced an axium that makes you know the serum evident or something like this um but this is something you can potentially also handle through CI on on GitHub if you like um so so this is the main appeal of uh of doing things with lean do the other appeal is obviously that there are now a lot of active mathematicians using lean uh including you know ter to and very famous maans that are running these kind of big projects in lean um for the information theoretic conjectures that we have you know some of these might just appeal to mathematicians to have expertise related to these things and so it's also a way to actually get more

people on board and interested in proving the kind of things that we'd like to get proven um and in particular by mass missions that have you potentially no interest or might not even have heard of ethereum at this point um you don't need to trust anyone who submits for request because lean type checks they the prove for you um and this makes life obviously much simpler uh and makes it possible to have untrusted parties um contributing to your project um so this is basically it um obviously if anyone has any questions about lean or something like this you can reach out to me on telegram I don't think we should take too much time uh in this call for this um and like I said we'll have blueprints for uh fry star and were uh developed over the the next

couple months uh which will include both coding Ser prerequisites uh as well as obviously the the statements they interested in to prove security um and so we can start offering bounties and and filling up the whole tree of dependencies as well as stating the conjectures and putting bounties onto these um in in the next few months and then hopefully we'll see some progress and and people can organize an effort to to try and proove these uh and and spread out the effort to kind of people outside the Fairly niched community that we're in okay uh amazing thank you so much Alex um and um just just zooming out um you know back for the beacon chain you know we pioneered a few things for example

the notion of an executable spec and the notion of having client diversity with you know five six uh different different clients and now we're taking it to the next level with formal verification and only now are we reaching this inflection point where the formal verification tools are mature enough for for this to be to be doable and it's it's just so so exciting um and for the for the uh the the the postquantum signatures in particular it's it's kind of you know very um you know practical as well because it might mean that we we could lean heavily on one implementation basically some sort of equivalent of blst um and and know that it's it's very

safe so we don't if the more we go down the formal verification route the less we need to lean on on client diversity for the cryptography at least um and the fact that we're now doing formication on the mathematical theorems themselves um is uh is also super exciting any any questions raise your hand uh for for Alex otherwise we'll move on to our last speaker another Alex uh from obal who will be talking about um MPC for the Post Quantum signatures Alex the the floor is yours hi everyone um sorry my camera is not working well I just tried to sh my screen but I got

deconned from the call so I'm I'm hesitating trying again or just giving you well okay I will try to I will try to do [Music] so okay hopefully you can see my screen yep here we go um yeah hi everyone so I'm Alexon researcher at dlabs obal and uh today we wanted to uh give you an update of some research activity we started recently and so it's about the impact of um of the postquantum replacement of blss uh and the impact it will have on distributed

validators so just a quick recap so to dates distributed validators uh over ethereum take advantage of the fact that BLS uh natively supports threshhold signatures so um if you have like a private key that is share among multiple participants using a secret sharing scheme uh it's quite straightforward to have a to build a threshold scheme out of it uh each party can sign non interactively and uh yeah you just have an aggregator that Rec combine all the signature shares that's quite that is quite efficient and um yeah the thing is that if we replace uh if we use a hash based signature

scheme that the above uh does not hold anymore so we need to to find a rock around uh to this um so how can we could we build threshold hash B signatures um an option will be to uh also leverage snarks uh so because we plan to use snark for uh s agre why not use also a snark um so that an aggregator could generate a proof ATT stating that it verified um a distinct number of signatures over the same message and that uh the number of signers meet the threshold and yeah so that could do the job but the thing is

it uh will probably complicate the signature aggregation then because we will have uh a difference between like threshold signatures and non- threshold ones um so I'm not uh I'm no snark expert uh so we investigated another approach to this problem which is okay why wouldn't we uh compute this hash Bas over NPC and this uh problem has already been looked uh at by previous work um but the the thing is that most instantiation uh were with traditional hash functions such as Sha

two or sha three which were not design uh with MPC in mind so in this Cas in this case with posidon it might uh solve uh like the efficiency problem that we have with traditional hash function and we just wanted to point out that um if uh if we we were about to go with such design it will be quite desirable to have like a prime field that is MPC friendly uh so uh for instance using the koala koala be prime for 31 bit Prime fields and in that case uh posiden 2 um peration still requires about like 30 multiplication uh

with such Prime so which is fine but the thing is that uh we have many per ation uh to compute during a hash B signature um so hopefully we will not need to compute all uh hash calls over NPC because some of them are not sensitive for instance when Computing uh the miracle authentication path but here uh I just summarized in this table um so with some parameters that uh are were listed by benit in his previous presentation uh here the number of plation calls uh refer to the the ones

that would uh be required to be computed over MPC so typically it will be like the hash chain calculation with the secret Keys um so of course the number of plementation depends on the xmss uh parameters but uh yeah I was happy to to hear Benedict says that um having uh uh two bit chunks is uh uh at this stage a promising uh Direction because it's not the one that consumes the more permutations uh but to get concrete numbers

we run a simple Benchmark using the MP speeds framework uh so here we give some results uh for different NPC protocol with different uh security levels uh security models um the results here are obtained so to compute uh a hash chain only so it will be really the the the calls that will require calculation over MPC and it assumes that um like the secret key Shares are already available so we don't uh derive them from a Sol random function so as you can see the

the timings uh for sure depends on the MPC protocol and the the security guarantees behind it uh but yeah at least so for this um uh the scheme with two bit chunks and the TSW encoding scheme uh we have something uh like around uh one second to to generate a signature uh that can probably be optimized using I don't know uh uh other implementation or stuff um but yeah just to highlight that uh in practice even though Poseidon is is MPC friendly we might face some challenge to uh calculate it over MPC so

yeah uh taking it into account to define the xmss instance will be uh quite uh appreciable and yeah for the the future work of our research uh is mainly to identify the like the right security model to pick the most efficient NPC protocol and actually uh given the fact that uh distributed validators also rely on a consensus algorithm to agree on what message to to sign and so on uh malicious 2third on L majority might make sense here and it might lead to better uh better results that we showed just uh just before and yeah we also want to to study time memory tread offs

and also so yes so here we just gave results for uh signature generation uh but ideally to date with BLS we can also either split a validator key uh using Shamy secret sharing but we can also have a distributed key generation algorithm so that the key is not uh in full at any time uh is never in full at any time but in this case if we want to have like a dkg hash Bas signat scheme uh well uh we need to to do some tests and some more benchmarks but seems quite challenging but yep that is something we we need to look at so that's it from my

side thanks for your attention thank you Alex uh we have a question from Dimitri uh yeah thank you yeah just to comment that since actually uh all these individual signatures are one time uh probably if we want just that a threshold mechanism we don't really need to compute the entire chain in the MPC fashion it should be sufficient just to kind of the share the secret uh for the beginning of the chain uh using probably just plain shamere and then uh well the majority gathers and then uh they figure out the chain beginning and just compute it in a plain way uh wouldn't it

work um so okay what you mean is that they recombine the secret yeah at the beginning of the chain but then it will be needed for each different trunks right dietry I think that doesn't work so uh you that's the same as as doing a BLS signature in in in the following way you first reconstruct the secret key then everyone has a secret key and then everyone locally signs right yeah but in BLS the secret key is multitime but here the chain beginning is one time yes but he yes but now consider a malicious party like a single malicious part is

already sufficient if you do that you reconstruct the secret key then then this validator which is a group of of people signs and then the single malicious party has the secret key it can just sign again and then you get slashed right so you if you you never want that a malicious party has the fault Secret key even if it's a onetime thing right you one time should be secure what you construct is zero times secure right right yeah I still think there is better way than to maybe yeah maybe you can you can I don't know give give uh every one

one start of one chain or something I don't know but that would probably also be insecure thank you Alex for your presentation indeed um you know in addition to the signature sizes being significantly larger in a postquantum world um you know roughly 30 times larger than BLS another you know downside is the fact that it's not it's not not as near nearly as MPC friendly I guess one mitigation to this is the fact that um we're hoping to dramatically reduce uh the the amount of e you need to be a Staker from 30 to e to to closer

to to one e uh and so in that regime there's a little bit less of a need to have MPC but then the counter argument to that would be okay what if the price of e grows dramatically to a million dollars while now you have the same problem even with one e few people will have a million dollars and so you have you need to have MPC for that uh but hopefully you know by by the time that happens you know MPC protocols and whatnot will will have dramatically uh improved any other questions for Alex uh Mark is asking will shortest slot time be an issue here as well less time to run this NPC protocol uh I guess the answer is

yes um yeah definitely okay well that's the end of the presentations if anyone has any uh closing questions uh feel free to to ask otherwise um I'll see you all on call number three uh which again will be advertised in various places including on the the protocol uh e protocol calendar as well well as the Discord group thank you so much everyone this has been a long call uh but lots of information shared have a great day

bye thanks thank you