Minimal zkVM

Transcript

Yeah, I think that we can get started. What I was thinking about this session is maybe like this is the first very dedicated session about like the minimal CKVM and LVM. What we can talk about is like the general architecture and maybe discuss about it as I know that there are many KVM experts in the room probably this would be like a full discussion. So it's just a paper written by Emil on the minimal CKVM. So yeah, I think that we will be able to go through this paper and maybe we can like step by step. Don't hesitate to ask questions, suggestion, remarks.

I don't know to what extent uh because there is this day to what extent we should come back on the VM itself or if we should focus on the proving system >> the paper like first the algorithm that we want >> so okay to begin with the go of This VM is to improve a single program that will be able at the same time to aggregate XMS signature and to handle recursive to recursion to be able to verify aggregates of aggregates.

So we need at the same time to XSS and to recursion in the same program. So this game is designed for only one program in mind. Initially the field collab for it nice positive properties. >> Yeah. I think signature verify should take but also the slot on. >> Yeah correct correct correct indeed. I think that maybe like the diagram that is just on the top could be detailed with like the bit and stuff. This one like yeah this is interesting maybe just to to understand how we aggregate like

the bits represent like the different validators and then you have aggregate scenes that's just concatenate like the the three signature that's how like you you generate the stuff. Sorry, quick question because you just mentioned the field and maybe this is a wrong session but um why not use binary fields like was there a reason to go with cloud >> is the security of field >> well but then you can use more classical >> yeah it's a fair point I think it's defin we did some experiment the beginning of the year with that I think that there is also a paper about like using binary fit

for posted that is currently written by Gitri and and all the guys which is under construction. What we have done with classical ash is that at the beginning of the year we tried like a different proof system like news and also ash caster by lab with sketch and more traditional function. The final goal of this experiment was that it was much slower like to prove what we want compared to this on CPU CPU as this is what we target. So that that's why we switch like but definitely interesting for sure.

>> No, it's good that you guys run experiments before. >> Yeah. Yeah. But maybe number have changed since then and we can even maybe revisit the proof system and stuff. we just because like the the the signature scheme that we have to verify involve many hash. So what we have to prove are hashes and uh we just try simply as a very first benchmark to prove as many hash as possible with various proof systems. So for example how many time can it take to prove kak using venus or using hash caster? How many time did it take to prove like posed using PL3? And the result of this experiment was that by far proving pose through fry techniques or weird technique was much

faster than the other. >> Um >> when was that did you do the experiments roughly? >> Uh it was January of of this year. >> So quite recent. >> Yeah. All of that evolves really really fast. So not that reason. >> Regarding the API, um you are currently uh have has input, you have the signatures, you have the bit field and you have uh the slot. But if you force that on the crypto library, it becomes very Ephrame specific. So can't we just

have the signature and the build film and the slots uh will be handled at the client level like it is right now in the country. So the thing is that the signature scheme needs a slot whereas in BLS you don't need the slot right the slot is really that's why I said verify signature verify should take as input >> right and I think it's also not that bad if like crypto libraries that are specific to I don't think that's >> u but the goal of Justin was that it's useful for But okay.

Okay. Maybe then I take that back. But I guess you still need the slot because it's part of the secret. >> Okay. >> I mean sometimes the slot is part of a secret. Sometimes the slot in general if you look at just XMss outside of Ethereum world then uh the slot will become a part of the secret key whether it is reasonable to model this way here. Yeah, I would also probably think of like since the slot is coming outside of the from the environment essentially then it makes sense to move it as a extra field.

I think also this is interesting like the first line of this mentioning why we chose like koala bear instead of baby bear due to this interesting photoorphism that makes it very very efficient for posision compared to baby bear >> talking about binary fields I had discussion about gem this morning and I learned about this new field G hash in the context of stocks it's it's 128 bit field. Um, and my understanding, correct me if I'm wrong, is that uh it's a great field for CPUs, but less good for GPUs because on CPUs you have like custom acceleration, but not not on GPUs. And in our use case, we are primarily targeting CPUs,

but there are synergies all the work that we're doing on on ZKMS, for example, where we do care about G is you as GCM. >> Yes. Okay. >> Um, yeah. So, as much as I would love to have a good alternative to the side and we haven't been able to get anything that's relevant like 1 to two million per second or whatever, I'm optimistic that like maybe there's there's some way, but I don't have alternative right now on Gash. Um, yeah, this is like the kind of standard 28 bit binary field extension that is used in adsg mode. It

is the fastest finite field on CPUs because of x86 and ARM because of um uh the carryless multiplication instruction that's like optimized for that. Um we have started to take a look at the the new signing to the work that Demetri and collaborators have um worked on and um you know uh also implemented like vision over Gash um as soon as I you know get something in the realm of what this can do.

I would say so my virtual opinion is still that cross is the most like it's the best CK hash function for a variety of reasons. But I mean on besides there's the security stuff. I mean one of my concerns is just the the native computation speed of it in comparison to other hash functions which is undeniably slower than things that are like bit optimized. But I I get the the considerations around this. >> Right. My hope thinking long term is that it's eventually we'll have CPUs with acceleration at which point we'll be in a very very good position have ketchup acceleration

point can show the idea is that you don't You want the that for the xis you need an exponent which is automorphism and for baby bear the smallest one is seven and for is three >> okay >> and simplyation we have cubes instead of seven >> no it's okay just back one.

>> Very true. >> And so if we want 128 bits of security without the conjecture like even with the conjecture up to capacity in web, we probably need an extension degree of at least five. And I believe that with the current like if we target 12 security with the current proven security we probably need extension six but implementations in degree five with project up to capacity the memory of the virtual machine is

read only as in k and it's it's a big vector of read only memory that is committed as a multilinear I didn't mention but everything here is multilinear and some check based >> maybe this is interesting to to know two things. First why we chose like read memory instead of read write memory and second I think that the the another difference with ko is that they have this notion of segment while in the current VM we have only like a single segment with a big vector with all all of the elements.

So first why read only for simplicity and the main advantage of of write is that writing a program is easier more natur but in our case because we only need to write one only one program I would say that we prefer to make it a little bit difficult if the pooling system is easier and more efficient I said and about this memory segments I think it's for the pre-ompile but like some parts of memory are dedicated to some preo compiles and um in the current implementation it's not the case like

the memory is a single segment and the pre-ompiles are handled in a different way with lookups from air tables into the memory I will come back to this uh I'm not so much into that but uh isn't one of the main arguments for uh for the non-deterministic read only memory versus read is uh readwriting helps if you if you if you do continuations because you need to fingerprint the memory state at the current point of time you want to reuse it later. Uh but

In this application, you wouldn't you wouldn't target something like it, right? >> Exactly. No continuation. >> Yeah. So, seems like matter of choice. >> Right. So, my understanding it's more of a question of the extent of um sort of user experience for the underlying VM. So you can express a lot of really powerful programs using the read only paradigm which I think is why a lot of uh people in industry have opted for that because it's substantially easier to have basically an almost immutable memory trace and that sort of makes sure that you win a lot. Now in a sense I

would say that the real question here is the developer developer experience. Um so a lot of people the way that they code and the way they write smart contracts utilize read write just because that's how we do it in the processor. Whereas I would say that the issue is are we okay with using and developing a specific VM ISA that is restricted only to read only institution if these um sort of developers are okay with sort of re sort of structuring the way that they write programs um to utilize that as as a base. And so that's more of a question of what is

your ISA and CAPM going to be used for. So I think and correct me if I'm wrong Justin but in the case of the lean you guys are fundamentally interested in um doing very specific checks with superheard audited um contracts and there is I would say um very little chance that you cannot do what you want um without read only. Um so that's the first comment and the other thing I want to say is um if we're going to go into the paradigm of read write um and talking fundamentally from like an information theoretical perspective um you have to make sure that the memory trace has to contain every single additional change and there has to be

sort of a data structure that is temporal. So as you know you have your base your base memory but then every single time you write or memory, you're going to have to augment this and and there's no way around it, right? Because you need to make sure you do that. So, I would say the open question is fundamentally based on your motivation. Um uh but it is possible to do, but you need to make sure that the way youize your memory allows for very efficiently to be able to check all these updates and and I think I think that's an interesting problem. But in the case of VM, it may just be the case that um that thing won't be interfacing with your end user devs. It would be more kind of like

people like here who who know exactly what they need to do because it it deals with sort of the guts of the protocol. And I would say in that kind of applicability in that kind of context um read only is both more efficient, simpler to audit and sort of like fundamentally pushes a lot of the burden um on us to make sure that it's ideal and and perfect and and sort of takes that trade off. So I think it's it's definitely feasible but um it's more of a UX issue in my view. I don't know. >> I fully fully agree. I mean also software uses reg for that reason but what I've heard but I'm not sure because I'm not much into it though I might

suffer >> uh is they are reconsidering it for the for the reason of continuations. >> I mean I can think I mean I know the Caribbean quite a lot and start team as well so I don't think that they are about to change the VM anytime soon but it's actually true that the Caribbean as it is done today with the original memory prevents from doing continuation and the problem is not that much due to the memory because you can snap track the memory you can make commitment of the memory anyway the problem is that uh there is a relocation step at the end of the of the process of the car meaning

that the addresses are known only when the program exit. So you cannot start proving if you have not exited the program. So this is the main blocker for the continuation currently. But you can do then you can because it's it's like in the car the memory is not 1D it's 2D. So you have segment index and segment position inside the segment which gives you the nice property of being able to do dynamic allocation at run time without like in real for example you need to give the size of the segment that you want to allocate on the he for example but in a VM you can just alloc and it pops in your segment you can write infinite infinite up to the fit size of

course number in the segment and then at the very end they are all concatenated to form from the one dimensional memory that is eventually considered really from the prover point of view. So the limitation is this step. You could do a prover that would keep the memory two dimensional but then the memory would sort of have a lot of holes to not a lot of space. Um yeah the question was again but yeah about the kind of things this is from a you point of view if we really want to push uh all the thinking uh to the to us uh we we really have two use

cases uh one is aggregating uh proof uh uh sorry aggregating signatures and generated proof and the other is aggregating proofs and generate a proof of proof. So the alternative is writing two circuits uh one for each. um >> so so I think I think the significance of the readonly memory um is not that it's a UX consideration but it actually means that the the the lean VM bite code is not a programming language or if you consider it to be a programming language it's not a complete one um because uh like so so there's no like there's no

there's no div up op code for example uh in this langage language there's there's add and all. So what you can do is check a division using a multiplication. Um and so like in order to implement division you would need some extra thing outside of the bite code that um you know that says to put uh the result of the division in the appropriate place and and that's how stuff works all over the place within this lean VM design. So I think rather than looking at this as as a VM that implements a programming language that you could just execute to perform the computation, it's it's more uh informative to look at it as um a

system for expressing constraints. >> Yeah, constraints with control. I so I I I agree with that analysis to a large degree. Um yeah, so I agree with that analysis to a large degree. Um however I would say that um you do have the designer freedom to pick the op codes that are fundamental and I think that it is possible for you to have I mean there are languages that exist lisp like languages with some caveats on the underlying data structure um which actually can exist with one or two like two like basically two real op codes and

then some memory of like lookup op codes which are complet and and you are able to sort of work with that. So my comment on this would be that it's not something that is directly impossible. It's just a question of judiciously choosing the outputs that you are actually going to enshrine in your base um and you you won't sort of like um sort of run into that wall um in general. So you will be able to resolve this concern. Now the issue is with that um whether you know for me to be able to compute a program that I care about I'm going to need 10 billion offloads or not and and that's sort of a fundamental tradeoff um which I guess you know if if we sit down and churn into like a super optimized use

case for the two specific cases that we want we might be able to resolve it but I would be a little bit less um optimistic that like a dev who wants to write in this would be able without sort of some kind like compiler or optimizer that like is sort of to them um sort of um out of the box to actually go and do that kind of work to make a really efficient program. So it's more of like a a question of making sure you pick things that give you the freedom you want. Um, and then again, like are you okay with most people not using this and instead coding on EVM and using EVM and ZKVM sort of products um to um to do

that execution and keeping this as something more of like a base layer plumbing level VM that we know for a fact is 100 billion% secure um that you know we are comfortable zking the consensus layer or zking some kind of like fundamental signature aggregations as part of the L1. So in that context I would say that uh you know like it's much more responsible uh from the perspective of security to have a system that is fundamentally auditable and secure even though we pay for it in sort of the expressivity of our language downstream. But there but there is a world in which that language

is as small and as sort of compact as as lean VM and is still turning complete >> 100%. >> That is possible. >> Yeah. Like brain has like five op codes and it's turning complete. Oh seven. >> Yeah. So >> there's also one that just has two. There's the SK combinator calculus. >> Yeah. So actually so it's it's funny you mentioned my state complicated calculus because um so uh the the way I stumbled into this was I I had to design a VM for a very specific small list like language um and no I think is that uh calculus that you mentioned it's one of those um and um and what it's a little bit clever in so actually the first three op codes of that language uh so the first one is

just the memory lookups um and then the second and the third are actually um a little bit funky. Um but those three themselves actually give you full turn completeness. They call it baby knock. So so there are solutions for sure. >> Yeah. And I might have overstepped in saying that it's not turning complete because I don't actually know that for a fact. But either way, the fact is that practically speaking, you wouldn't be able to implement the programs you want to implement in terms of computations, you know, within within this language without some external thing that is filling the memory with the right answers because that that's not what this is for. It's not for running computations. It's for checking the answers.

You can also get op codes that are macros of the fundamental op codes um in order to sort of like alleviate the concern that a lot of people would have about sort of in a sense coding in by code, right? You you can do that and and that would actually be relatively easy to implement if you have the fundamental op code secure. It's sort of like a pre-ompile kind of, but you can sort of like harden that into your I say and just have very very generic um sort of links between your more complicated off codes. Like you can for example like hardcode an if statement of code on top of the first two or three. And then that just becomes a question for us here like

what is the most clever way to do so that I can give people the fundamental things that they require in order for this to even be usable in UX. because there is a world in my view where you know you harden this um and you do all the really important stuff with it. You you sort of demonstrate security downstream over time and then you build on top of that something that resolves the UX question. Of course that's you know reaching but I definitely feel like that is possible >> but in that case instead of having a macro that creates um a by code we can also have a macro that creates a secrets directly >> by code I mean surfaces I'm I'm operating on top of the uh of the a when I say macros I mean that like the

constraints that are used by all code one and all code two um then have code that does the first two you can sort of collect figure out that leverage the other two in order for you to get that I'm not operating on the CPU I'm talking >> okay uh right now the link VM has uh a DSL that's compiled down to a by code that then compiled to a circuit so when we talk about B code we need to make sure we talk about uh the by code there rather than the circuit below Yeah. Although I mean at the end of the day um there's also a question of

whether um so I'm running the program right and I'm getting the bike code the real bike but at the end of the day if you really want to get really high efficiency on these things the real question is transcription representation of this field elements um that's really where the massive efficiency because all the B code sort of um like compile like efficiency work that's done over the last 20 30 years in building really compilers that work is basically what we need to do at the circuit level to make sure that that's as optimal as possible and I think the design space there is a little

bit different but I would just I agree with you but I would focus on on sort of how do we get that representation of the B code at the circuit level as often as possible and what kind of restrictions can we put on the way that that code is generated. So what structure can we impose on it so that we don't have to do really expensive things um in at the circuit level if that makes sense. >> Sorry to open such a huge debate. Last question and then we move on. Oh, just um a couple of comments on our experience with the Petra VM which was a VM that uses a read read only memory model. Um

you know I believe in this model like uh what we basically did was we had a a read only memory and we tried to design a high level functional language which was a strict subset of SML then actually wrote like a ton of SML and uh I liked the approach we ended up taking which is you can write code in that and um as long as it complies with a subset you can run like a normal uh interpreter. So the devx was good. Our experience overall was like the amount of effort it takes to write a compiler even for a very basic functional language which is like I assume something that would be easy because it's from like college textbooks um in practice is is quite difficult. Um I do think it's expressive enough. My general

recommendation for this application is just straight circuits to sidestep the entire thing. Maybe that's ignorant. >> Yeah, this is a very interesting point and probably this is the right moment as I see on the screen like the different op codes. Probably this is the right moment to to have this discussion. I know that Claymore and maybe a bit familiar with this new approach avoiding the compiler stuff playing with the hairs in style instead. And we just discussed that briefly with Kmon beginning of the day because I think that with with KO they have similar experience and this is the approach they have taken uh for the new KO M design uh

instead of having a compiler playing with circuit and stuff. So maybe if you want to take a word about this [Laughter] >> I'm not sure about the question but I'm fully aligned with open VM for anyone who has read the open paper and so the basic idea I think is just to not make hard decision about the code that you want to use but just make sure that you build the framework that you can add on top of the kind of chips as they say components as they say stuff anyway that you want to add which are at the end just sort of independent circuits that

are all binded together with the arguments that you make sure that you give a global consistency but you don't need to think about a stand I would say a global ISA but it's more about independent circuits that communicate with Luca and that overall needs to be all consistent with each other in terms of Can they put other on the element? >> I think this is what you just mentioned, right? Fair enough. >> I mean, I would not use errors. I mean, we're we're basically using Spartan non-uniform circuits. You basically don't need to pay for lookups. wiring is

quite cheap and you just I think it's going to be easier to do formal verification for that sort of thing too. >> Uh yeah, a single circuit for like the leads and then you have two to one aggregation and you can sort of in order to get variable sized you know larger statements you're just playing with the recurs recursion architecture. Believe me it would work the question is what is the simple approach for me it's not 100% clear because it is your approach you have one big secret and that's it so it's hard to prove that is good but when it's done it's done and

you quite confident it I think it could help if you can um explain the state of the compiler like is it finished how many lines of code is it >> uh it's not finished because It's not perfectly stable. It's like currently approximately 5,000 lines of code. But I would say we don't really care about the compiler. What we care about is the produced by code. Once the produced by code has been created, we can remove the compiler because we we would forally verify only the by code the result. >> So the compiler Yeah, I know that that's approach.

One approach would be to to have like a formal specification of what you want to prove and to formally verify that the program with this minimal ISA does what you want it to do and in which case you can the compiler is just used to help you write the code but when it's done you don't care about the complexity or the correctness of the compiler because you will only prove correctness at the back >> and There is an alternative. It would be formally verifying the constraints.

Uh and in that case we can also discard the by code. Um >> verify which constraints. >> Uh so you have uh currently you have compiler by code and then another step to convert that into constraint. Right? >> The the by code is like this by code with this those four op codes and you have a trace. Each cycle you execute one of these four codes and that will interact with memory and the circuit is used to prove validity of this execution. There is no really a compilation from this ISA to that on the secret is only used to prove the validity of this exhibition of this.

>> Um do we foresee the um circuit changing a lot or not changing too much because I understand that we're doing world verification but how much of the world stuff is going to change in the next few months is that war 2.0 what is going to happen here. One advantage of having the the I say approach is that it's easier to adapt because your program it's like a few thousands of codes and so it's probably easier to change some part of the program than to change if it's a big circuit.

>> It's not obvious to me that easier to verify the compiled code than to verify the source code and and that the compiler is preserving the semantics. It was like proving that a simple compiler preserves semantics should be pretty simple and that could be like a good way of organizing the process of proving that the bike code is correct if you're convinced that the source code is correct. I guess also how confident are we in being able to formally verify the like anything you produce um how confident

are we that the formal verification stack is going to be ready in time because if if it's not ready then we will have to rely on extensive testing rely on a lot of checks. I think the idea is really to play on for onification 100% but you will have to ask Alex how hard or easy will it be I think that right now like they are building like the building blocks such as some weird primitives some some check primitives and some basic primitives so that we can reuse all all of their component for the full stack not really but yeah we rely on that for for the future. Okay. But what's our backup plan if that's not going to be ready soon?

Because better to have stuff in between then to wait for the thing to be ready. >> Are you interesting like very well tested with fusing with all of these kind of best practices? >> It won't be ready if you mean by soon in less than two years it won't be ready. Uh but uh this will not be deployed in production. >> Yeah. The goal is to deploy this in four years. Okay, two more questions. So in addition to our elements, I will quickly come back there. So those four op codes that interact with the memory and basically you are able to have arithmetic

constraints add a new memory and you have conditional jump to have control for if else and some kind of functions and loops. And you also have this reference of code that enables you to communicate information between different parts of your memory. And in addition to those four pretty simple op codes currently there are four pre-ompiles. The two of them are used everywhere because both in XMss aggregation and encryption we need a lot of hashes. The two last last ones dot product and multilinear evaluation are used in regression. That product enables you to

perform as its name suggests that product but in the extension field which is really important because the initial op codes act at the basis field level. In region, you want to be at the extension field level. And if you have this product, you can basically perform multiplication with doing the product of size one. And you most importantly you can fold large chunks of your memory which is necessary in multiar is also like one thing.

to note is that contrary to KO there isn't such thing as an allocation ber register so when you want to call a function which is like the notion of function is not entrained in the ISA it's an abstraction that you can create on top of the for a function basically let you jump to another place in memory >> yeah just a question because you say there is no So when uh or how are you updating the frame pointer? Actually when you jump you are able to modify the frame.

It's like one function that lets you potentially update something like it's one that does everything you want to do. And the key idea is that when you want to jump to a new function, like you want to call a function, you will receive as a hint the location or of where to jump. And the the idea is that because it's read only memory, no prover can cheat because if it was read right, the prover could make you jump at a previously written location memory and

you will you cannot destroy previous memory and that's why you can remove the allocation pointer register and one thing is that when you jump to a function before jumping you need to write using the df of code your current program counter and frame pointer to be able to come back to your previous context like a detail but just to the high level idea is that you can have you can design functions using those codes. Okay, I think that's the the so the main goal of AP is to be able to have a dynamic

dynamically side frame at runtime when you don't know the the size. I mean if you want to do a number of loops that you don't know and it's just provided as an input then you need a for sure but maybe in your context you just have fixed size files and you know how many times you're going to to do that. That's why you can remove the >> you can remove the AP because you can transform the loops into recursive function. You let the compiler indeed if you you loop you know the number of iteration at compile time you can unload it. But if you don't know you can simply transform every loop into recursive function.

You convinced or not? But there is nobody if you do this now because you have no color code. But in the color of code normally you need to store the place where you need to go back. Yes. >> Well, you don't store where you go back. You can unfold it in an infinite number of time. But then at the end of the day, how do you prove that you eventually sort of finalize a program that has been done like so that you you come back to initial place >> actually before jumping you will write down at the beginning of the new frame your current PC and your current FP. So it's like a code but at the very end you write this down and you don't have any AP and so when so you write it down you jump

and then you execute your function and at the end of the function there will be an open code jump again to come back to the previous context that will update the PC with the value of PC that has been written down at the beginning of this frame. Well, this this is the call of code at the end. How it's done in just write the two values and code. It's just the col is basically writing FP return FP return PC and jump in. >> Okay.

>> How do we how do we make sure that the program terminated? >> There is it's a good point. Um when you define a program, you must give the list And you must give a special line which is like the final line. And in the proving system you will accept that at the end of the execution trace you are indeed you have indeed up on this line and this line actually it's a jump that will make you jump in place. So you can execute it. So the idea is that you can pition table with this line. You can

That is until the next number of two and you simply assert at the end of the execution table that you are indeed on this fin. Actually you assert that at the on the execution table you need to assert two values that the first PC is zero and that the last PC is the final PC that is part of your B. Okay. And one funny thing is that using this reference op code, you can do ranch checks because basically the ref lets you access some memory value based on an

address. And this will fail if the index address is bigger than the memory size. And using it you get a check that some value is smaller than the memory size. And if you check that for instance if you want to check that some value x is smaller than 10 what you do is that you check that x is smaller than the memory and that and that's 9 minus x is also smaller than the memory meaning there is no underflow in the subtraction. And using this it's a weird way to have efficient range checks using the derence of

>> and in practice what happens when you exceed the range the program >> the no valid proof can be generated. Okay program >> you you could make the program but the validity proof will not be will fail to generate or will fail to verify such a validity. >> This is where it may be helpful to think of this as a way of expressing constraints rather than a way of computing. You can do it if you switch but it's not really important maybe don't know how much time we got that um quickly the proving we can talk about the the

architecture of the proving system everything is >> maybe this is not to go to log in since there is afternoon session about this is not useful full if you want to gain time to go through the log star since since there is a full session this afternoon. >> Okay. Okay. Okay. So without talking about everything is multilinear meaning you commit like your memory is a multilinear. Your f tables are multilinear. Actually you can interpret every F column as a multiar but you will not commit to all those multilarians individually as you will do

is if it was in Ko or in the univariate case what you do is that you pack all those multilinears into one big multilinear. There are multiple ways to do it. One solution is the J PCS. you concatenate everything. And the key point here is that if your columns have some padding using the J PCS, you can avoid committing committing to the zeros. So you can you can gain up to vector of two because you do not commit to the zero.

You pack all the non-trivial parts of your columns together. You obtain a big multiarian that you commit and using an appropriate sum check in the PCS you can reduce claims on of every individual column to claims on this big multi and then you can use your your PCS rear. But actually there is a way I believe to reach almost the same performance actually but eventually even better performance for the pro side and most in the most simple way without using the of the jacks.

Basically the idea is that you will cover every non-trivial part of the columns with power of two chunks. You will you may commit for instance here you commit to a bit of zeros because your power of twos for instance if you take three or four chunks per two chunks per column you will go a little bit beyond the nonzero part of the column. So you commit a bit to zero some padding but much less padding and if you commit to it entirely until the next And then you put all these chunks into a

big single multi. Importantly you start with the big chunks. It is important for to have some alignment with for the good alignment. And you can reduce evaluations on each column. Two evaluations on each chunk. And you can reduce two evaluations on the big multina. And one advantage of this one advantage of this approach versus the jack one is that you don't have a sub check. One disadvantage is that you that there is control flow in the verifier. So if the

verifier is a circuit, you probably prefer the jack ps approach. In our case, currently we have some control flow. So that's why I believe this approach is potentially simpler than the jacks. Maybe something interesting there is to mention as multilinear things that are like new things when compared to the unariat. What are the pros and cons? What are the difficulties and the main advantage that we have by by using multilinear polomial instead of using the classical way with f of variable.

The main advantage I see is that you will reduce the proof size because you can as I explained here you can pack almost everything into a single material because if it's uni yet you need to commit to every column individually. Okay. You can have a batch mer tree but you will have some kind of mer open oping opening for each column and so if you have a thousand columns your proof size will be likely above 1. And in this case the mer opening will be on only one big and then with this new approach we also

have to deal pretty much everywhere with the subject and then we we need to find out source of customer optimization to to optimize this new tool that comes into into the room. >> Indeed. So you can improve validity of air tables using some check. It's pretty efficient. For instance, currently we can pro like on this um Mac you can prove almost 600,000 pos whereas on PL3 the approach it's a bit more than with the same actually using degree five extension of while in four in three it's four

so the probably if we take the same parameter the same conjecture we can likely go to like 800,000 and also to answer your question one advantage of the multilinear approach is that you can use which is I believe which saves a lot when it comes to the fetching the code that represent the instruction I'm not sure if this is the right way to go. I also saw that the Google team was uh was taking that idea. Um which is probably well known under the people uh

which is uh that you uh use a mixed radics FFTD. So not just powers of two, powers of three for one reason because you can approximate at the given domain column length better. >> Yeah. So you get less fighting overhead. >> Sorry. >> You you remove some fighting overhead like the instead of having >> exactly you you tailor your domains to give them the execution trace.

>> You can do such tricks with I think that we discussed that with Angus and you didn't see that much performance. >> Yeah, I can comment. I'm just just one reason reason because for me before the check PCS came up it was I was not sure if multivariate over prime fits make makes much improvement because for one reason the univer has the synergy between the committed values fd commit and constraint evaluation >> so you reuse these values so which which you can't put it in even if you commit the result on that work that FD work

those cannot be reused in the subject >> and that's why I was never sure since the jack bcs and likewise I like you say I'm not so sure anymore which is better >> just sorry so on the rad thing um I guess there's two things so one slightly unfortunate feature I mean sort of the Nice thing about coal bear is that three doesn't divide p minus one. This also means you can't you can't like like three would be a useful radius for this sort of thing. So you can only do these radius things for like things that divide pus one which there is two and 127. So it's doesn't quite work as well.

The other place that radius comes in is you have like mixed radius FFDs. So you can do like radius 2 radius 4 radius 8 and those work quite nicely when you have nice twiddles. So for like complex MFDs or I think for Goldilocks, there's some nice twiddles at eight or four. We looked into this and couldn't get a huge improvement, but this is certainly something that would be worth looking into. >> What again the prime practice of P minus one? >> Uh it's 127* 2. >> So the prime factors correspond to like what are the what are the FFT sizes you can take?

>> Yeah. So I mean the koala bear sort of I guess the reason we chose it is sort of working against statistics. We chose it explicitly because we didn't want three as a factor of pus one. So there would be a potential advantage of baby bear if you wanted to >> 127 also >> two things one to Lor's point about the univariate sort of synergy of encoding and um and constraint evaluation is sort definitely true but also when you're in the multilinear setting you don't need to do the IFFT you just do the forward FFT to encode So it does save some work that you would have needed to do otherwise.

Um and then on this if you use Spartan you only have one polomial because all the sort of breaking it apart is done by the wiring check. So that's also nice. >> It's a good point. >> I think that's it basically because there's also this log up. Okay. And I believe that the drawback of this approach is that you need to communicate the inner evaluations of every chunk. So if you have a lot of columns and a lot of chunks, you have a proof size overhead. But with a slightly more

complex approach of using rectangles with each side of the rectangles to be a power of two, you can cover your air table and reduce significantly the size of like this. But anyway, this is not implemented. This is just an answer. And there is load up star which plays a significant role in the system because it's currently only lookup that we have. But maybe it's more topic for sentiment.

>> Yeah, if you want maybe you can show like the nice plot that you have on the rhythmic with a number because I think that we have never showed the number system. So yeah, don't know what you think about it >> the the nice clothes that you have with the with the number just in the read me there where we are. Yeah, this kind of >> this is on my old laptop. Um currently Yeah, I think this one is currently I would say the the three hard parts of the the the hard work that remains to be done is to first improve performance by a factor of of

approximately four to five. Second to finish the recussion program because currently we only have program for a week don't have to end to end thing. And third all the the XML the current XMs verification algorithm is not the real one with the with all the the trickable hash and the the real encoding the real XM encoding. So there is some work that needs to be done to make it as GK friendly as possible and to implement it for real in the XMSS.

on on my side I I think this one is quite important because this the plot that you have on the screen because this represent like how many time it takes to to aggregate like 500 XSS and so if we reach first the target that is the dotted line it would be like quite a significant milestone for the overall project. Yeah, there are some non optimizations for currently the reco compile we store the two like most of the time because they don't 16 is used is used in compression mode but for shamir actually you need the 16 outputs so currently we

store the 16 outputs every time and it's a quite we pollution of the memory in practice when you you use XMss. Uh and the idea was suggested two days ago and we can currently I think we can reduce significant like we can reduce almost a third of the memory size by eliminating eight feed elements of each of almost all 16 output and then there are also some nonoptimizations and then it will be a lot of engineering job to make it fast.

Could you talk a little bit about non-determin your design and also sort of what you are comfortable with and not comfortable with when it comes when it comes to nondeterminism and like if you have any concerns about it. Currently there a lot of noneterminism when it comes to function because Because when you want to call the

function, you need the prover to hint you where. So imagine you are here. You you want the prover to give you as a FP2 which is the start of the new location will end up I calling the function and this value you need to receive it as a heat and the argument is that from the vector perspective you don't care where you end up because your the computations will perform you will be the same and you will return with the same result. But turns out the prover has the liberty to Put this check of memory wherever you want.

>> Yeah. Uh I I think that we are right >> anything to add anyone questions >> how many how many columns >> in the exeution paper >> no in the end you repeat it's a single large one there is like there are four air tables and one memory. So you commit the memory and then four tables and in the execution table you commit to five columns in the that product you

commit to like eight to nine columns and in each in the pos 16 you commit to previously like in the plunky three array you commit to like 155 or 160 columns using degree tree constraints like the the air tree. But turns out um if you look at the performance for recently we gain a bit using the grade nine constraints because in our case using we and using in particular the posed hash function it's um

the commitment costs are quite big compared compared to proving the validity of And that's why reducing so like you you gain something like um something like you remove I think 32 columns but you increase the degree but in the end it's faster and so granted that there are something like a little bit more than a thousand columns here and I don't know how many colors but functionally it was like 24 something like this. And so now it should be like 200.

>> And then what blow up do you consider >> the the rate of the code? >> Yeah. >> 12. >> Okay. >> But one thing that you could imagine imagine is that because it's a collaborative approach to merge those 10,000 or more SMS signatures. So you could if you want in the end to a small proof you could use one half of a rate one half everywhere and in the very end you use a rate like one four or something like this to get the minimal tiny proof.

>> Yeah. But maybe also for recursion >> and also that's potentially we prefer a slightly indeed slightly slow even at the beginning to get faster. Definitely. [Applause]