EVMMAX Implementers Call #1

Transcript

okay cool yeah so this is the first meeting for uh evm Max um do people want to sort of just quickly introduce themselves and sort of where they're uh coming from just because the meeting is quite small sure uh I can start I guess my name is chance I am from the PSC team privacy and scaling Explorations which is funded by the EF and we do a lot of ZK and NPC research among other things and so I'm interested in seeing this because most of the stuff we do is based on modular math thank you uh leis maybe leis can't speak as score

bajer hey uh yeah this is my real name is Amir um I believe I met some of you at Devcon sea um I'm with the JavaScript team I'm working on the ethereum JS execution client um I'm interested in uh implementing the evm max eips with the JavaScript client and potentially uh uh working on some of the eips and some of the open questions and work in the evm Mac space currently so okay nice um Donner we know who Donner is

but yeah yeah mostly work on E right now radic yes I'm radic from ipsilon team and I'm working on the evm max pack uh with uh also an implementation in evm one yeah so I also interested from the perspective of uh how the spec is specified and uh and uh and the potential use cases it can be used for MH uh P hello I'm P from ipsilon and also work on uh ev1 and E currently and in the

future on EV Max as well nice uh Andre I think you're also in ipsilon right yeah from excellon Team I wasn't that much involved with vmx yet but trying to follow the latest developments uh and leis I think so yeah um Lis I'm from B the best team um working or started working on evm as well and I'm looking to follow the vmx and looking to implement it on B as well okay that's nice uh and Ellas wrote in the chat that's

from kakarat zvm Team implementing evm in Cairo zvm cool uh yeah and I'm Kev I'm currently in the EF um mostly doing applied cryptography uh and yeah I'm really interested in evm Max and seeing where we can take it uh so the first thing I guess everyone has a sound understanding of what we're trying to do in evm Max if not then um I can explain or Danner or um Jared's kind of left the chat can explain does everyone sort of have a a concrete understanding of what evm Max um I'm happy to get a quick rundown

yeah so evm max um essentially adds these modular arithmetic opcodes into the evm um and it it just allows you to do modular it should allow you to modular arithmetic a lot cheaper than um implementing them in in raw solidity um the implement the specs for it I can link it's EIP 6690 um and one of the sort of goals of evm Max is so that you don't need to reimplement pre-compile for every for example field or curve that you want to uh have So currently like if you need to if you want to if you want to support cheap

let's say BLS 12381 Edition you need to have a pre-compile for it which is EIP 2537 but with evm Max you can have something that's not as cheap as a pre-compile but definitely cheaper than implemented in implementing it in raw solidity um does that Ellas was that does that answer your question and does anyone want to add to that cool um yeah so on the first thing on the list is uh what was done till now so does uh Jared you're back on the call do you want to sort of explain the progress that's um happened on your side yeah sure um Hey so uh just on my

side in the last uh couple of weeks so we um back in early 2023 I posted uh a draft proposal uh under EIP 6690 um and in the last week I've uh so about a month ago I I posted uh another draft proposal which was an updated version of 6690 based on um kind of the feedback since and also talking to vitalic about um what uh he envisioned as being useful uh so I I've since updated EIP

6690 to reflect this draft spec that we've been talking about uh so I would say yeah in addition to that um in the past I've uh I think there was a there was a a period of time uh where there was a question whether the BLS precompilers were going in or not um and so at the time and this uh idea evm Max being the main compe competing idea uh so I implemented a few of the operations um the BLS operations uh so in the past well today actually I

posted sorry I when I say I implemented a few of the BLS operations what I means that I wrote them in assembly using evm Max so today I posted uh a link to the tool I used to build that uh it's updated with EIP 6690 so I think that's kind of that's been the progress from my side yeah um maybe uh ipsilon can Chim in I know they've been doing a lot of uh prototyping work as well uh yeah so uh so we also implemented uh kind of a

version of uh uh of the of the evm max spec but on the top of the URF some so using um using uh uh immediate Arguments for the instructions uh based on this we implemented a couple of uh simple uh BN curve uh B curve pre compil scle Parts implemented in the using this instruction set and so it was I believe uh uh Point addition and point multiplication we also have some had some version of uh of easy recovery but of course easy easy recovery precompiled from from from the current spec and uh

yeah and this is implemented on uh in the in the evm one uh for now yeah and uh yeah and that's that's basically all we also had prepare some some document which uh sum up the um the outcome the feedback from this imple those implementations yeah so that's that's all we did I believe or I forgot about something so maybe someone someone remembers better okay and um so I guess that's it from mainly the client side of things

uh I guess no other client has sort of started an implementation is that right Amir and Lewis yeah not yet okay um I think probably the first steps for if you're a client looking to start is to figure out the cryptography like the library that's underneath that does all of this modular arithmetic um if you guys ping in the chat definitely happy to like help you look through which ones are suitable um and in terms of the first use case that use cases that we want to Target uh Poseidon's the one that sort of comes up

quite a lot are people happy to uh Target Poseidon first instead of some um elliptic curve we can also do bls2 for example since there is a pre-compile for it I think Poseidon is a good thing to start with one thing that I was thinking of is when I was benchmarking performance of like Montgomery versus Barrett um the numbers were not super convincing for a single Poseidon because it's not enough modular operations but the thing is we very rare we very rarely do a single Poseidon hash when we're doing something useful we'll typically do a minimum of like 32 Poseidon hashes

for that like mutating a Merkel tree or something like this this so uh perhaps like broke off uh okay one moment hang on I think maybe was you saying oh wait okay I don't know if chance can can use I'm sorry my internet cut out um cool okay what I was saying is is instead of benchmarking one beside hash I think we should Benchmark a minimum of 32 when we're considering Montgomery versus Barrett which is maybe more specific than what you're asking but

that's what I was trying to say right um so I guess Poseidon would be implemented inside of the solidity um contract and you're saying that so with evm Max we have evm max memory so once you put something into evx memory uh we do this uh Montgomery transformation and once we take it out we do a Montgomery transformation I guess are you saying that if I have input and I put it into evm max memory and I do Poseidon over that just once and I take it out it's not uh the performance of that is not great yeah exactly the cost of moving in and out of Montgomery is too

high okay that's sorry for but how how big is the output problem from the posad hash one more time how big is the output for from the from the posad hush it's Conant size it's like one field element if it's like 200 it's it's gonna be like 256 bits okay uh yeah okay that was yeah just wondering if if it if it really makes some real difference to first of all if if it's really needed to take it out from the evm max memory and and put it back that's first thing

and the second thing is if it really needed does it does it make uh any difference if it's so actually small uh yeah okay but something which has to be investigative at good point that we we have to check it just to clarify sorry were you um were you saying to the the the base field width here is 32 bits and we're just talking about like field elements not like extension field or any of that like we're just talking about single 32bit numbers as the as what we're Computing beside and over right uh it could be oh wait I know if

you're asking me um I don't think it would I mean I think for Poseidon it would be parameterized over a field right so it just depends on what field you're doing it over I would assume that we'd start with a fred2 bite field um that's what I would assume that chance was doing it over uh it is super interesting I guess and quite a bit unintuitive that one Poseidon the operations that you do inside of Poseidon is not enough uh as in the coming in and out of Montgomery somehow is still a dominating cost um so I think it'd be good to investigate that um I didn't think bidon was that fast I

thought we was doing quite a lot of um multiplications yeah it justes like a thousand multiplications this could also be a problem with my Benchmark code are those numbers based on on the JavaScript performance no this is based on a rust implementation see okay and was this also doing a Montgomery transformation on the pidan constants no that was without uh trans that was assuming the constants were already in Montgomery form okay um yeah it'd be interesting to see um this maybe if there's some code

because it's super unintuitive I'm probably missing something here um cool so I guess are people happy with focusing on just a Poseidon use case for now um just because it has a lot of um details in it that I think we need to iron out anyways like for example the constants that are used in Poseidon we ideally don't want to be putting those in and out of Montgomery every time you do a Poseidon hash so we'd have to figure out some way to deal with that and I guess from an algorithmic point of view Poseidon is a lot simpler in order to implement than let's say um some e some elliptic kind of

arithmetic um anyone against sort of using Poseidon is the first use case that we try to aim for yeah I think it's a good idea to start okay cool um so can I just ask there so I've seen like it seems from my Layman perspective here having tried to glance at the resources around beside in that there's a few different configurations in terms of how many constants are used um for what we're targeting what size of constant table are we are we looking

at oh this depends on the field that you instantiated over as well as the number of inputs to the Poseidon hash so yeah we should definitely Define this so we're all benchmarking the same thing um I'd say we could just use a 254 bit field and two input Elements which would be I think like 60 rounds split between partial and full rounds yeah so can can we have a uh or maybe we do we already do but uh I'm interested definitely in some use cases of using posad not only the implementation of the posad itself so it would be very helpful

especially the case when you when you need to calculate many poson uh hush in row ask wait are you just asking for an example use case where we would do that yeah exactly exactly it's uh I I want I want make sure that that we on the same on the same page so so so the biggest use case is maintaining like a Merkel tree that exists on chain and opening it or mutating it so every so if we have a Merkle tree of depth 32 that can store four billion elements then we have to do 32 posidon

hashes any anytime we add a leaf to it or change a leaf within it that's the use case I'm thinking of yeah and uh and this uh this posidon hash and this constant array I okay I'm I'm new here but uh in this in this topic so this this constant AR you or this Con constant Matrix you use in posidon is uh the same Matrix for all the posum calls or you change it yes it's the same for all of them okay great or I should say it's the same for all of them for like a single application but if you change the field then there will be different constants but

yeah cool yeah sure sure I'm um and one thing that Jared uh brought up inside of the GitHub issue is how do we plan to sort of iterate quickly on um these contracts so like what is the pipeline to implementing Poseidon and if we need to change something really quickly what is the pipeline uh what if someone wants to implement bls2 Edition on the side uh what sort of tool are they going to be using to quickly iterate um so current yeah um I'll just chime in and say that um from from from what I've done

my I would personally opt towards using something similar to uh so I presented this tool evm Max s 12381 um which is a essentially it's people here may have used like templating systems before um so this essentially builds uh it is a templating system that generates Huff output so um when you write contracts with this you are well I was you're you're writing Huff code but then you also have the ability to call into uh python to generate more uh to to to to generate part of the code

and uh maybe people will opt for a different route but it seemed like for quick iteration having something like this where we have an assembler with the the the basic ebm ma support and then we have the ability to just generate assembler code with a higher level language I think that to me sounds like the easiest way to iterate and and from what I've seen in the past of how people write these like low-level uh crypto contracts and I'm just thinking of zircom lib uh zircom lib as or zircom as the as my um frame of reference I've seen people

use uh basically generate the the the resulting code with a higher level language um but maybe people have maybe there maybe the there are other opinions here it just seems like that would be the easiest way to start off with um yeah so just to clarify if I wanted to create the BLS uh a bls2 381 elliptic curve implementation using this I would need to well first of all I'd be writing H Huff code um but fredd the evm max op codes that I want to insert into the Huff code I would write that in

Python so is that correct or um so what you you would be writing Huff um but to so like the the big problem to to in invoke the evx op codes you are uh it would be easier if I could show you but essentially you are a assigning symbols to ranges of the me ebx memory space and then when you invoke the op codes you are invoking them with the symbols you the text symbols names you've predefined um so yes you are invoking them in Python but it it is very much

like embedded in the hu code okay um but then if you like I said if you have if you want to do something B bit more complicated you can just write a template method that will where you implement whatever it out whatever it will emit you implement that in Python okay I see okay and the evm one currently um radic you can correct me if I'm wrong I think currently there's just a like a library that you use to just adding yeah just a just a simple Library which uh allows you to to generate the code with the with the evm max instructions uh but uh but it's not very

uh very convenient actually so it's more for like use it to to generate uh to generate evm evm evm tests basically or mainly and uh yeah so we extended it to to generate also this additional instructions but it's very low level so so definitely we need something if you want someone to to to to prepare some use cases on on the top of the AVM Max we definitely need something more convenient I I haven't looked at the Jarett Jarett tool but uh but yeah I'm curious and I I will definitely do it soon uh yeah so we had some idea with with Y with implementing

support for for for evm Max up codes in y but not sure still because we haven't started doing this yet so not sure if it's the the best way to do it so so so yeah so this is something we needs investigation okay and I guess chance was you also going to look at Jared's tool um I can also take a look to see like how convenient we think it is and wherever does only better yeah I think just looking at the python just now it looks pretty convenient but I have concerned about uh actual low control in the evm like I think the operations will be very

fast but I think having to write the logic around the operations might increase the gas cost significantly so i' lean more toward doing some like hacky thing in Ule and then like WR writing a script like sort of sto evaluates the gas cost there yeah so that's actually a really good point um because that is totally correct um with the with the EC mold implementations the like that the majority of the overhead well let's just say conservative really maybe half of it or more is in the non ebm Max op codes and the control flow and it's uh so yeah that's going to be that's going to be the hard part

about writing contracts in you know in in a lowlevel language in in assembly right yeah yeah that was also my impression when we implemented this C recovery that the most maybe not the most but a lot of a lot of gas was uh was used to just just jump in the in the loop or or just just yeah just to to to on the coun flow yeah yeah I mean like stack operations just manipulating stack I know people have been talking about um repricing non-control flow evm op codes to be lower so maybe in the future that will kind of help allate this issue but

right now it's I mean yeah depending on the use case it's problematic but you me you mean the the stack stack manipulation regarding the the implementation of VM Max without TF yeah in this case no I just mean like I just mean like um like so in the EC mole in the like double and in the in the it just it just does a loop right where you're reading bits off of a scaler and doing stuff BAS on those bits the um just the just the stack manipulation and the bitwise operations involved in doing that Loop and reading the scaler are yeah exactly overhead yeah yeah yeah

yeah yeah you just reminded me the the the code I I I had seen before yeah thanks um so maybe it makes sense to possibly explore the Ule route um just because it might be more indicative of act the actual gas costs of evm Max once you implement it um I'd still be interested to have Jared's um tool because if it's easy to use then initially we could at least have some uh gas cost numbers like if it's just really easy to use yeah um I can uh I can I can update the gas cost numbers for the BLS operation and give a

breakdown of those if people would be interested um I guess I'm I'm curious why people think U will be more efficient than handwriting this stuff I don't oh no no sorry I might have misspoke I don't think it'll be more efficient it just seemed like it would be more uh indicative of the actual gas costs uh like if someone was to implement Poseidon yeah okay yeah let's let's let's let's check these two directions yeah so so we definitely can check can check you and uh and and and just in the end of choose uh the one which is which which will be

the the most convenient for the cryptographers yeah okay cool um and I guess one other thing from the GitHub issue uh or more generally is like what is the status of the EIP at the moment um do we have the correct gas cost numbers or do we need to do more in investigations to figure out what s what um the gas pricing should be for uh these new up codes um yeah I can comment uh so I think it would be great to get feedback I I kind of took well I I updated the IP based on my own accord

based on what we have been talking about for a month and I felt like uh this feature set that I included here was kind of the rough consensus of things that we are looking at prototyping and researching around um regarding the gas model uh so one thing that will likely make a big difference in the end so this gas model is based on you Implement my implementation of the arithmetic uh using Ingo and based on the what the authors of what the gark library

provides so for example if we from my benchmarking it's about two times the overhead of uh if we were to create an implementation that would use handwritten assembly for for the arithmetic so um I don't really know where I was going with that but um I guess um how what is the methodology for pricing these up codes like for example let's just take M mod x um is it the same methodology for pricing pre-comp and like how do we

determine the cost of this is it relative to cat check or so what I did was I based the I based it on the the current pricing uh and performance of EC recover in get so I took a benchmark of the EC recover pre-compile uh measured the gas throughput from that and used that as a Target um and so the implementation of this uh like the gas prices used here uh are based on the cost of the arithmetic and then the cost of interpreter Loop overhead in gu

so to to like to generate to to measure The Interpreter Loop overhead we simply just create a piece of Evan bite code that does these operations in a loop and then we take or well I take the price of the or the cost the the the run time of the arithmetic itself ract it from that get an idea of The Interpreter L overhead um and then another I guess another like assumption here is also that the the amount of memory memory we can allocate in evm Max in a single call context is not enough to influence the runtime in

the worst case meaning that the latency of memory does not become uh Factor here to to a significant extent yeah we can we can also prepare some some benchmarks from from the ev1 side comparing also to EC recover or to any other any other hopefully will um uh hope you will uh with welld designed gas schedule yeah I have a question to jar to the gas costs uh if particle gas would be available would you set one of these gas

cost of one to sub one um values can I didn't see it on the screen but who who is asking that question P oh uh yeah yeah um I think so yeah for a lot of because there's a lot of ones in the table yeah yes uh I mean yeah something we could look at doing is is is revising the gas model so that if you're because with with 6690 you can invoke an you can invoke uh you can do multiple arithmetic operations

per op code so I think that per operation we could look at going sub one definitely because like a lot of them are really cheap I mean addition and subtraction are are very very cheap and then the multiplication at low widths is also very very fast yeah yeah so thank you so for the sake of the argument maybe it's it's worth to to quote this as particle gas cost even if that's if that even if that's not available to to be you know actually charged for one operation um yeah sure I mean that kind of conflates with the the previous particle gas cost

per yeah sure yeah we can figure out you don't need you don't need the particle gas proposal to pass to charge less than one because because of the strided operations right what you said I think that you could charge less than one and then round to the nearest you know round to be a whole number yes like in the scope of a single op code you would need the I mean the strided op codes that you have right now anyway yes for the sake of the argument less I'm saying the the cost of the invocation of a single op code should be

a full number but the the individual operations within that can be some yeah yeah okay thanks um um my understanding is that we usually price pre- compiles based off of EC recover whereas these are up codes and we're also pricing them based off of EC recover like is this okay um is this like a sound way to price B codes I'm all ears that people have alternative proposals this was the easiest way to assign a cost model but if if it's okay or not I think nobody nobody answered this question yet yeah so uh I but I think that's that's

that's the the most common way now we get to to to to to prepare discuss the the gas schedule for for pre compiles okay I see um yeah I guess we can put it in the questions to see if anyone has a better idea but yeah if there's no better idea I think we can just move forward with this right now and and um the cost of a addition I guess this goes to P's question so the cost of just a 256 bit addition is now the same as Mal is that correct as in

is uh as uh as a 256 bit M mod if I was just adding to integers together in solidity is this now the same cost as doing a Mal mod x I think so I think it's it's either it's either the same or it's like one off one less maybe yeah I guess this goes to the uh using not using uh whole numbers for the gas cost but I guess that does seem a tiny bit off uh uh so you're talking you're you're talking

about the current M mod op codes M mod admod right yeah so in the EIP um the evm max EIP we have Mal mod um oh okay you're talking about the ones in evm Max because we have them in the evm [Music] um I would have to look up the cost model again but I mean uh so you mean 256bit modulus right yeah so if I was just adding two integers together um the cost of that relative to doing a Mal mod x so Mal mod is eight gas right now and malm mod x is two G per

jarett's table in the EAP from what I see the cost of an ad mod x or submod X at for the cost model I proposed is one at 256 bit it's it's two yeah and eight for mole mode in the evm like the current one we have yeah so it's much cheaper in the evm max yeah sorry maybe I maybe my questions like misformed so without evm Max I can add two integers together um the cost of that relative to in evm Max I can do a Mal mod x the cost of that um does that make sense

yes eight cheaper okay okay makes sense um yeah so I think the gas cost numbers are still we still probably need to justify them a bit more but it doesn't really stop us from getting this Poseidon uh example down um and in terms of on the to-do list I guess the Basu and ejs folks um if you just ping inside of the evx channel we can talk about sort of the cryptography and the API for it um I did have a a GE PR which had like a big int Library so like a simpler implementation

that can probably be easily ported to bzu and ejs as a big like just a start off um I can link it inside somewhere a quick question so what cryptography needs do we have that we we would need an external library for for a client implementation for evm Max um you just need to be able to do modular multiplication modular addition really quickly um so you could use in in Java in JavaScript you could use the big in um sort of n new native type um but it's probably not going to be fast um So eventually you're probably

going to want to use some specialized modular arithmetic Library I see the um so like the implementation of AD and it's only the M mod uh the M mod algorithm that is is complicated the implementation of modular addition and subtraction is is very very simple okay um were there any questions from anyone else we've gone through all of our items on the list yeah I wanted to talk a little bit more about pre- formatting Montay values

for use in the EPM Max I think this is really important and I think it's also like relatively simple to do we just need to spec out how we select the Montgomery constants for evm Max for a given modulus right uh so the problem um just to clarify the problem is that we have constants for Poseidon and we want to be able to sort of pre-compute them into Montgomery form well it's not just that it's so for example if I have a if I have a solidity function that accepts an argument that is going to go directly into evm max Whenever I send that transac action I

could preformat that argument in the transaction call data in Montgomery form if we support this yeah but but but we don't support loading and storing and basically we don't want to the interface to make visible the montgomer form of the of the values in the contract yeah I think this is the question to be able to I mean to to sacrifice the purity of the API for pragmatic reasons right because it's going to be much faster but there are there are other Solutions also we can we can we can consider just like uh like for example

we can we can extend the with additional section in the URF which uh which have this or which has this this this values already precomputed and they will be loaded directly to the to the uh the evm max um slots or or registers without any any conversion I I um I'm really skeptical that this will actually be a problem in practice and I also feel like yeah I mean we could hypothetically we could add them to a

section where we we choose some consensus uh Montgomery parameter and then that's not I mean with we make that unobservable to code but then if for some reason if for some reason in the future we have a new multiplication algorithm or or some new Montgomery uh reduction algorithm comes out that doesn't use those constants it kind of creates an awkward situation with the existing code well it would

be so first of all I disagree I think in practice this will be a large bottleneck but I guess what kind of change would you would you expect to see to like the Montgomery algorithm that would break this I don't know I mean I'm thinking like even Beyond like if if if something unrelated if some other I I I don't know I I I'm I can't predict how things will develop and uh I mean it's safe to say that Montgomery arithmetic reduction will stay around given that it's been here

since the 80s and it's kind of ubiquitous at this point I think I'm just it's it seems weird to tie consensus to to a to a constant that is very much dependent on the hardware of the machine in question and specifically the uh the word size of the machine in question right because the the is it based on that yeah I thought the Montgomery constants were just based on the modulus and not necessarily on the hardware so it's like uh it's for for the optimize

Montgomery uh multiplication algorithms it's a 64bit value um yeah it's based on it's based on like taking a number taking a a number that is a power of two that is like so you take the size of the modulus and then you the next largest number that's a power of two that that is is one greater than the I I I I I I I won't really go into detail but I I think it is tied to the to the hardware at least the the anyways I was I was thing for me to look into I think yeah I was actually kind of

curious like oh okay like back on the subject of Poseidon though because I know you were me like I just want to hammer down on on why what the rational is behind thinking that the like Montgomery conversion is going to be a big overhead factor I mean I think you I think you mentioned that the constant table in use would be correct me if I'm wrong did you say 64 values um yes oh my God I should know this but I don't yeah it's going to be like around

there yes okay and then the output is is the output is a single field element or it's two field elements it'll be something like that it depends on the size of the field but yeah it's like such that that the the size of the field elements output is equal to about 256 bits okay and then we're doing so like pide and you do do you have a do you did you say thousands of multiplications yeah for a single posid it should be on that order right okay so like we're talking about added overhead of of 60 multiplications to compared to a

compared to an operation that's going to be doing thousands of multiplications and I would assume like additions and stuff so I mean it's definitely good to quantize if we can find if we can find a if we can find something where the overhead of Montgomery conversion is a huge factor that would be great to to bring to the Forefront so I just I'm skeptical based on what I've seen so far okay yeah so I think we can keep it as an open question um once we have Poseidon implemented we can see whether it's that the overhead is large for going inside and outside of Poseidon uh

sorry inside and outside of evm max memory um I agree with Jared that it's a bit weird that it is an issue I would assume it's it would be an issue for things like if I just do one addition or one multiplication uh then the overhead would become apparent uh but there might be just something that we're missing um so yeah it be good to I'll put done as a question that we need to answer I was mostly thinking of or or comparing this comparing like Montgomery to Barrett in this context like I'm concerned that if we have if we're if we're converting all these

things into Montgomery form then it would be faster just to use Barett at that point that's my thinking for for some things right um I guess H but this all comes back to I think that specking out how we Define the Montgomery modulus I I think we can do this in a way that doesn't provide a lot of implementation complexity to the clients but I I will look into this and and report back though okay yeah that'll be interesting I think I do see where Jared is coming from as well in that uh if we allow allow the constants to be precomputed

you sort of leak uh the fact that we're doing Montgomery multiplication um in the background um whether it's an issue um I guess I I'm not sure yeah so I guess that's something to just think about I don't know right now um so I'm just going to write down spec out theidon probably choose a particular field to start with is the use case sorry kid go ahead no

sorry uh what I so is this is what we are using posidon for is this non elliptic curve based what is the what is the use case here uh the use case is forming a data structure that is compatible with essentially ZK proofs and so what you use to make such a proof could be elliptic curve based it could be based on something else how do okay so the the choice of Base field here is irrelevant to the to what proof system system or what what uh

whether it's elliptic curve or not on the on ultimately yeah so what proof system you use that will determine what finite field you use right I guess the two use cases that I can think of is um as chant said if you're verifying merrye Puffs M for one and the other one is if you're verifying stock proofs um first stock proofs that does require a bit more because the call data is probably going to um be more than the cost of the computation and there is some auxiliary stuff that I

guess Stark is probably doing like aggregating multiple proofs together um so we can probably try to not factor in the cost of call data that much as like arum in against it because I believe STK uh where do sub stock proofs to um to L1 um so those are the two use cases I can think um yeah I think the argument is people don't verify stuff on L1 because there is no fast modular maap and starkware is just an outli an

outl an outlier where they were like like you know we're going to do it anyway essentially um but yeah I guess what I was trying to say is that even if Poseidon was cheap um I believe that people would probably still um wrap their proof in something like gr 16 or whatever because uh the call data cost of a stark is going to be the overriding it's going to be a lot a lot more than just doing something like gr 16 yeah so this sort of transitions into um building Merkel trees on chain not just verifying but like mutating

them and then storing the data on chain and that is where you do like 32s for example but actually I think you're talking about something else I think we're talking about different things now yeah so yeah that's one use case so yeah I guess I see two use cases to start verific use case and verifying Miracle paths just and probably mutating Miracle trees as well as you said yeah but I think people R proofs right now just because that's the only like economically viable option yeah I yeah I agree yeah the call data is a bit too much sorry the proof size is uh a lot so the co data cost

overrides everything else well not just that even if you have a relatively small proof like if you have like a Lattis Bas commitment it's only maybe 8 kilobytes but if you want to prove the like do ZK proof of opening on chain the modular operations would be significantly larger in cost than the call data okay I see this here yeah so I put mle path verification using Poseidon and mation as sort of our top sort of simple use case that I think we can Target

pretty easily um and Jared I guess you said that the GE implementations uh sort of there so we can use that as one of the um like as maybe the base library to just uh Benchmark this off of so what we'd be missing is a Poseidon implementation that we can pipe into the G um PR that you made yeah that's correct okay um and radic I guess for ipsilon it is it updated with the latest 6690

EIP uh no because as I said it's uh it's it's based on the URF as far as I remember the 60 690 is not yeah but we can we can make this uh EF counterpart yeah just to compare and uh so but yeah that's that's a good idea now to to get it in more in sync with this specification and uh and um and prepare the maybe POS an implementation based on this and do some benchmarks so yeah for the next call I think it's a good task to do it okay that makes sense so are you going to work on the Poseidon implementation with TR

or yeah I would love to start as soon as possible actually but now I'm finishing the E implementation in solidity MH MH okay let makes sense uh trance was you going to work on theidon just trying to figure out who's doing theidon implementation yeah and I can provide some like a field and some constants to help with this okay okay this is great um and I guess you might want to work with Jared to figure out how do we integrate this into GF so that we can actually see the full pipeline of here's the Poseidon implementation and here's how we pipe it

into gef and here's the numbers and if we want to modify it we just this is the pipeline to modify it um Jared would probably be the best person to help with that yeah feel free to ask any questions um um I would say that the templating tool I posted for the BLS contracts is probably a good reference to use for how to interact with gu um uh you might choose to build your own assembly generator that's fine um but uh if you run into any issues though feel uh feel free to ask me okay yeah I think you will do okay do

you think it makes sense to write a simple Ule generator would you be able to do anything with that or should we just stick with the Huff thing for now my I haven't looked at Ule in a long time my fear with Ule last time I looked at it was that they're like the way the way op codes are expressed in you will instead of just like so if you take Huff where you just it's basically the the bik code it's basically the op codes themselves just one by one and then you can you know add functions and macros and whatnot last time I tried to use Ule the way to express the op codes

was by this like you you you call the syntax was strange um and I I it was I didn't find it suitable for for my liking but I mean go ahead if you if you feel otherwise um okay yeah let's let's stick with the H thing I think for now sure I yeah I think it's I personally think it's simpler but yeah okay cool are there any other

questions that uh people are thinking of or things that we should discuss I have one more I want to discuss a modular inversion call um I think we talked about it a bit in the chat is there are there any thoughts around this I I think it would be useful to have as an OP code but I could also see it being implemented as sequence of instructions what do you feel is the where do you feel like the overhead from this becomes dominant or or not if

not dominant a large factor I think the control flow around implementing modu inversion is tough because if I remember correctly there some conditionals so you can't even just like unroll it to get rid of most of the control flow I also think that or I I know okay this is a separate thing I but you can batch modular inversions to make them faster I have no idea how we would expose that as an API I I just have like this suspicion that implementing it as an OP code will be significantly more performant and it's something we have to do like pretty

regularly um could we just Benchmark that uh that seems like something we can verify I mean my suspicion is that that's true as well um but it'd be good to just have numbers that support uh so in the template tool I posted there's an implementation of modular inversion for BLS uh using the the Fairmont for I don't know how you pronounce it but the modular inversion via exponentiation um so so using a chain also all this yeah using ad chain yeah okay so yeah

that's one option and the another one is as as far as I know is the the uh extended Elan algorithm but not sure which are now best uh because this this uh this AR chain is not uh uh on the general so it has to be generated for every model so yeah we could also uh look at the modular the mod XP pre-compile for this case I think that is probably it might be more expensive than ad chain but from a code in terms of how much code size it it occupies it's much

much less I yeah I know I think it's an interesting area of research um it seems like adding dedicated inverse would be really complicated the relative to what's already in the spec but I mean agree why would it be complicated um because I mean what's there already so add and sub are just both addition and subtraction basically big and addition and subtraction the setup the set mod op code is fairly simple and then the real meat of the complexity here is the Montgomery

multiplication which is also uh I mean maybe it's on par with the complexity of uh UK extended ukian I mean not really because it's the the modular reduction is all like constant time basic basically it just seems like adding inverse would be the most complicated thing yet in this proposal yeah right now it's essentially just a very thin wrapper around Montgomery and adding inversion is adding like a whole new algorithm into mix so the complexi is coming from in the back end or whatever cryptographic

Library using will now need to implement like extended ukan algor extended idium uh the extended an algorithm or is the complexity like gas costs figuring out the gas cost for inversion like um I would guess both like yeah correctness but then by identifying identifying the worst case uh worst case inputs to the inversion but maybe that's maybe identifying worst cases is not actually that hard I just haven't looked into it okay um I mean it sounds like it's something that's good to investigate maybe as a lower hanging fruit I

guess um if we have constant time algorithms then it's probably easy to figure out the worst case um in my head it's more like how what is the usage of inversion like if inversion is used everywhere then everyone's going to have to reimplement it right right um in their contracts um but if it's only used in one or two places then I think it doesn't make sense to have it as a dedicated up code um yeah uh I think that's a good point I I mean I wouldn't be opposed to adding it it

it it just doesn't yeah the the justification just isn't there right now um yeah yeah I agree um I think I agree too yeah so let's let's let's check it then then we can decide on the next also or have least have some more input next right right that makes sense okay uh so I've written down the stuff we've discussed I'll past it in chat uh so for baso and ejs I I guess the next step would just be to looking to add a

modular arithmetic lib um uh this is sort of the precursor to implementing the EIP uh for chance I guess you're going to spec out the Poseidon um and add a Poseidon implementation using a Jared's tool or uh some U um Tool uh for Jared uh I guess you'll be helping chance integrate this implementation into the g code base and some stuff that we need to investigate is whether we need to pre-compute the Poseidon constants or not or whether it's like efficient enough to just uh convert them on the Fly and then investigate whether the op

code inversion is so costly that it needs to be an OP code um I guess and also investigate whether inversions used a lot in the use cases that we care about uh is there anything I missed sir uh I guess just like to tack on to the point about inversion investigating whether it's used a lot but also used in a way that makes batch inversion not viable and also used in a way that makes bch inversion valuable um I'll write that down I don't completely

know what that means because are you saying that uh like so there's if if if we need to compute multiple modular inverses we can use Montgomery batch inversion which just boils down to converting one inverse under the hood and then some multiplications on top of that but I'm like you could imagine some kind of computation where the result of one what you're Computing the inverse of in a subsequent step depends on the inverse from a prior step where you couldn't batch I don't know if that makes sense but essentially just identifying if

there's cases where using Montgomery batch inversion doesn't uh isn't possible with the given algorithm okay okay I see because if we can use batch inversion every in a lot of places it feels like less of a justification for adding it is well it's obviously less of a justification for adding dedicated inversion but I mean yeah maybe maybe it's not anyways yeah possibly um because batch inversion does actually still do an inversion um so I guess we can investigate further uh the most important ones I guess is the pre-computing the Poseidon constants and yeah that's just to get the full

pipeline of what's Happening um is there anything else we missed I guess I just want to ask um how are we doing on time okay we still have a bit so like when I implement this for GU um it's pretty easy in gu I think I saw a comment from somebody Lew getting on and off of native code has a cost um like when I implemented the arithmetic and gu it's pretty easy to map what you're implementing to the

hardware go I think go does a decent job of that and you're not you're it's pretty easy to implement this stuff performant and I guess I would wonder if like there like uh b or Java if you have if if not having uh a close handle to the hardware would make implementing the arithmetic difficult I mean I yeah I guess people would have to find that out as they implement it I'm just curious um yeah so in Java I can speak for Java it's you need it it's it uses a gni so native interface and you need to

build a context every time you you step on to the native code so that that has a bit of a cost um but I think getting into native code is less costly than than getting out uh um then get calling some manage code out of the native code which is not going to happen in this case we only going to be getting n to native code and jump back um so yeah yeah that's that's really the gist of it okay but you the 21 introduced a new native access method that's not gni jni has gotten known overhead issues this might be the right time to investigate using the new stuff

um it hasn't been available in previous versions of Basu because it was based off of stuff like Java 17 and Java 11 but in Java 21 that's the new base that's where it's in so it might be worth investigating it now you might get better performance okay cool yeah Dano what was that called uh Java 21 uh ffi I think I can't remember the exact um this project Panama they have some formal name for it now but um it was in preview prior versions in 21 it's the new stuff but don't know correct me if I'm wrong I think it's mostly the efficiency is more around memory passing memory slots into native or having

access into me of of memory in it native code but I think you yeah not sure like the the context you you you don't need to build it as well still all the same uh yeah definitely worth investigating I guess I'd imagine that You' uh create the context object in the let's say the C code and then you just pass a pointer uh you have the Java code hold a pointer to it um so your memory is managed in sort of the C code or the r code or whatever efficient Library you're using or does that make sense I think there's facilities where

you can call um basically the library directly kind of like jna with less depths and less overhead okay I see definitely worth investigating yeah Jared does that answer your question um yeah sort of I guess we'll just see where the numbers pan out over time MH yeah also worth considering that net I'm not sure I cannot speak for them uh another since there's no one from there on the call uh I'm not sure M but net would be another it's another VM that will have this problem right uh any anyone else have any

questions okay cool yeah so yeah I guess we're going to finish early that's great um yeah if there's nothing else then yeah I'll see you guys on the Discord chat just maybe happy Christmas and and Merry Christmas and happy New Year because we seeing each other again after that is true merry Merry Christmas Merry Christmas see you guys