XMSS Signature Aggregation

Transcript

incontiously the rest. Okay. So, I going to be short. Um I will

talk about everything previously has been said and explain from like the SMSS signature scheme to the minimal VM and all of this. So I will try to speak about like open problems and what we have been doing like more on the code side of things. So we have several works fronts. Um one of them the first one the most basic is like the signature scheme implementation. So going from the that Benedict just described like to a rose code. So that is this repo. There is also a very useful repo that contains all of the primitives that we are using.

So basically the fields uh the post hidden hash function the air constraint builders and all of this. So PR3 then we have the we repo right now that is on a separate repo but soon to be upstream to to PL3 and then we have this uh VMC repo where all of the logic of the bin VM is is implemented. So I will I will try to decouple the open problems on these different report so that you can have a better overview of what needs to be done and what will be done in in the coming months. So first we have this XMSS signature repo that is quite feature complete as Ben

just said well implemented. We have a good documentation we have a good test in that but we can find some rooms for improvement. For example, improve the documentation because it will be used by all of the client teams and so we have to be very specific in the documentation and the in the API. Uh we can add more test because this is a very sensible cryptographic implementation and so adding some fuzzing and some stuff is always welcome. Refactoring some code and some small potential avenue of speed up. For example, I am think about adding some SIMD optimization for this signature scheme or adding like maybe more optimization to the Merkel tree or

this kind of things. So small speed up could be gained maybe also better paralization and simplify the logic where possible but basically this works and we are able to generate signature we already have benchmark and so this is not let us say our main focus then we have the plunky 3 implementation that is also very complete used by all of the industry of course but we can have some gains on some very marginal parts uh like CID instruction for example We made some good progress in the in the recent weeks. For example, adding cmd for Mac for posed or for specific like product stuff or multiplication very low level

stuff. Uh we need also to think about how fat shamir is handled because right now it is not exactly the same as the one that we have in wheel. So we have to have also discussion this afternoon about this. We haven't looked that much about like multle tree. I know that this is already very good in block 3 but we have also other implementation that are available. For example, I am thinking about some Facebook research repository where maybe we can find some some tricks to optimize like data exchange in the in the Mer tree operation and all of this. Maybe also more efficient matrix operation,

transposition and all of this. We don't do lot of this but in the in the lin VM repo we have some matrix operation and some transposition and for now this is a bit more a bit costly so maybe we could have some improvement on the DFT side this is something that we use widely but I think that this is already very very good so I don't think that we could gain that much but this is to be explored and then we have all the investigation on the side of multilinear because right now like PR3 is univariat and so there is no multilinear support and so we have to add like a lot of primitives such as how to evaluate multilinear polomials how to

implement sum check how to implement wheel pro 3 and of course test then we have the wheel repo so the the cing of we repo of course is the real implementation so the wrong things that is ended by Here inside we have a big building block that could be also considered as a primitive that is a sim check. We can have outsource of optimization for the sim check. A lot of papers have been published. Jolt is a very good source of inspiration for that because they are using some check everywhere. Justin Taylor published a lot of papers. So and also Angus Gri within this room publish the universe keep trick can also be used and some bag

and papers and all of this. What is very costly in real is is about the first round. Why? Because this is where we are using the big polomials because as you know like when you commit to a to a polomial inside the BCS you start with a very big polomial and then you you fold it round after round. So the last rounds are almost free but the first round are very costly and so we can think about outsource of optimization to better understand what we are doing there. Better paralization strategy, better CMD strategy. Yeah, outsource of strategy. Uh we have also like the initial constraints of the of the

wheel that are then combined inside a big evil egg multilinear polomial. This step is very costly. Right now we have done a bunch of work to do everything inside the PCS in the evaluation domain. Meaning that what we done at the start is that we we did everything in the evaluation domain and each time we had to do an FFT. We transformed that into a coefficient domain. So it was like kind of a costly operation each time. So we found a trick to implement the DFT completely in the evaluation domain uh to have to avoid having to have this kind of uh conversion at each round. So we currently maintain in the code a DFT

that is basically like a copy and paste of the blank 3 DFT but adapted to the evaluation domain and we recently Jako recently found like a nice select trick that could get us rid of this implementation. uh we are also implementing that right now and uh we are also checking about how to make uh we as fast as possible and closer to fry. So in the coming days we should run like some benchmark in order to compare apple to apple with the same configuration for fashia same configuration for burger tree to compare we and fry to see what what's going on and we have also like batch opening that is widely used by by in the Lin VM and

that should be also upstream inside the W repo and finally we have like uh this lin VM code uh that is the last repo that I mentioned we can do all sorts of improvement there because the repo is quite new um handled by Emil like from like couple of months um so we can improve speed as show on the diagrams to reach the targets that we want um so this is basically 1 signature aggregated per second and the 2 to1 recursive aggregation is 200 I noted 200 and 50 millisecond but Justin seems to mention even lower like numbers always go lower

uh we can also improve the compiler uh fix the final design because we always have open question and uh new stuff to discuss so at the end we will have to fix the design, write it properly and yeah make it as simple as possible. We want we want also as mentioned by Justin during this first talk to provide some public goods. So it is important for us that all of our primitives if possible are upstream to blankly so that we can h use them but also all of the community so that we have more a on the code more optimization and yeah it can benefit all all of you. Uh yeah and then all of the classical stuff like review the code,

add more test and yeah clean up the code base. This is basically the work that we'll focus on in in the coming months. This is all. [Applause] So, so you said there is a batch PCS were implementation. Is that right? >> Yeah, because yeah, currently um Emil is is working like to move faster on on the NVM is working on a special fork of we let us say and in this fork he implemented like the kind of a patch

opening. This need to be upstream into like the more well-maintained for It works but it will not work. Currently if you commit to polinomial and the second is much smaller than the first one it will not work but in the in the general setting currently it works but so it needs to be done more properly. Yeah and there is currently there are a bunch of open issues in the wheel repo and it is one of them. Thank you.

>> Any other questions? Thanks again to