leanConsensus Call #7: leanMultisig specs

Transcript

Introduction to leanMultisig (Justin)

Hello and welcome to lean consensus call number one. Uh no sorry number seven. Uh this is the first time that uh the the calls are no longer branded uh after the the beam calls. Um it's been quite a while actually since we've had a call. It's been uh over three months. Uh we haven't taken the summer off. I think we've been all working extremely hard. uh and uh today's call is uh to a large extent the the the product of of all this all this hard work. So let me get started and share my slides.

Okay. So uh the topic of today's call is the postquantum signature uh specifications and uh since the the last call we've uh introduced uh lean ethereum uh through the firm foundation blog and lean ethereum basically has three constituent parts. It has lean consensus which is uh the rebrand of the beam chain. We have lean execution uh which is all about snarkifying the L1 EVM uh as well as potentially introducing a new ISA risk 5 under the EVM and there's a whole set of calls called the eve proof calls uh that are dedicated to lean execution and then

there's uh lean data which is the next generation of of data availability in particular making sure that it is postquantum secure This effort is still very very decent. Um we just have the name. We don't have anyone actively working on it and we don't have any calls for it right now. Uh if you're new uh to these calls, uh there's here's a few useful links. So we have the protocol calendar. We have the the discord uh where anyone can ask questions as as well as the the YouTube where we have a bunch of recordings. Um, and uh there's actually a lot more content on YouTube now uh because we

have this new series of calls called the postquantum interrupt calls uh where the goal is to try and spin up some uh postquantum uh deathnets and I believe we've already had eight of the of those calls uh once per week that are uh on uh on YouTube and we also have a brand new uh URL replacing a beam road app now that that redirects to leanroad.org and thank you so much to Unaw from the the the REM team for uh maintaining this this this great website.

So here's an overview of the the 2025 uh schedule. So we already had uh the very first call where we introduced lots of uh teams that came forward interested in in working on on lean consensus. Um we've had five different calls where we gave updates on various important topics uh related to doing consensus and then we had beam day uh in can at at ECC uh which was a great success and it's also available uh on on on YouTube. Uh there's maybe you know six or seven hours of of content there if you'd like to to dig in. And one of the the great

outcomes of Beam Day was that we kind of came to rough rough consensus that a good next step would be to have um a postquantum DevNet as a as a as an good next step and that led to the the postquantum interrupt calls. Um so quite a a bit of time has happened a couple months has happened between uh beam day and and uh and today and um today is basically the first of a series of calls which will be um much more specific about what exactly we are building and uh starting to to look into the the Python specifications as well.

Now, um, initially what I was hoping to do is to have a a beam week or lean consensus week uh in November at at Defconnect. Uh, but I won't be able to travel to to Dev Connect. So, instead uh I'm organizing a couple of events uh in in Cambridge. Um so one is a postquantum signatures uh workshop that will happen uh 4th to 6 and there's also going to be a consensus layer architecture retreat uh for for Ethereum foundation uh re researchers and um I'm hoping to to be able to make a ton of progress there uh on in the postquantum workshop hopefully

make a lot of progress on the on the devet and then basically ally what I'm hoping to do after the the Cambridge workshops is to uh you know make a ton of progress on the various subspecs uh so for for the peer-to-peer networking for rainbow staking the finality gadget and then eventually hopefully towards the end of this year uh we will have the full lean consensus specs at least some sort of uh of first draft potentially and uh one thing that I I'd I'd like to highlight here is that um you know there's a lot of excitement on on some some new ideas related to finality uh

and those will be discussed during the the consensus layer architecture retreat. Uh the FM foundation actually made a couple of hires uh very very recently uh and they're bringing in uh very interesting new perspectives that could lead to some modifications over um 3SF which was the the latest and greatest uh that was uh that was known just a few months ago. Okay. So uh today's call is all about um lean lean multisyc which is the the postquantum uh signature um and you can think of it as having two constituent parts. You have the so-called leaf

signatures which are the signatures that the attesters um produce when when they sign. Um, and then you have a a step called aggregation, just very similar to to to BLS, that will take all of these signatures and compress them into a very short um multi- signature. So in the leaf signature, we have four layers of the stack, if you will. So there's the field that we start with called koala bear. And then once you have a field, you can define a a hash function which is friendly to this field, which is snark friendly. uh and here we're suggesting to use pad on two and then we have uh what's called a one-time signature scheme which is an optimized

variant of of winter. Um and then we have uh lean sig uh which is an optimized version of of xmss. So that's the the leaf signature part and then the snark aggregation itself is made of constituent parts. We have the polomial commitment scheme and here we've been putting a lot of effort into were uh we have a snark which is uh an optimized variant of of super spott and then we have stuff which is essentially completely custom. Um so we have an ISA with eight instructions four up codes and four pre-ompiles. We'll learn much more about that uh shortly from Emil.

And we'll also have um basically a program that will do the aggregation including the recursive aggregation uh of signatures which again is is also completely custom. And my hope is that um you know the complexity of all of this is actually very very much manageable and specifically we can have the full uh verifier uh for these uh lean uh multisigs in in under a thousand lines of Python. And um you know part of the reason why I'm so optimistic is that we can get there is because for example lean snark um which I guess includes the PCS and includes all of this stuff uh or

at least the this and this uh was uh was you know 400 and and well less than 500 lines of code. So uh yeah I'm hopeful this is is very manageable complexity. Um here's a little bit of a cheat sheet on the performance very quickly. Uh the pub key is about 50 bytes. The signature is about three uh kilobytes. Uh signing times on a single core. Uh and verification times are you know less than a millisecond hundreds of microsconds.

The number of hashes required to verify a signature that's a leaf signature is about 150. And um the key generation process for every year of lifetime is about half an hour. So if you want you know to have a validator that lasts 10 years for example uh that will take about uh 5 hours. Uh these are potentially nonoptimized and and might improve and this is on a I believe a 10 core MacBook. And then on the aggregation side of things, uh what we're working towards is to aggregate uh a thousand signatures per second. Um we're not there quite yet, but we have all sorts of ideas that

we believe could get us uh could get us there. Um and the these are aggregation speeds on a on a CPU. Um so for example, on a single MacBook uh CPU. Um and yet for for GPU numbers roughly speaking you can multiply this by 10. So it would be 10,000 um signatures per second on on a single uh you know gaming gaming GPU. And then the aggregate size for 128 bits of security is about uh 128 uh kilobytes which is a a nice coincidence in the numbers.

Okay. So these are the speakers uh for for for today. We're going to have Will talk about some of the um coordination around the interrupt calls as well as the the Cambridge workshops. Uh Felipe will talk about the the specking template that he put in place uh with lots of good practices from um from other efforts. For example, the the EELS project. Uh Tomas will talk about um lean sig which he's already uh speced out uh and we also have Emil who will talk about uh the lean VM that he's uh he's actively uh working on.

So yeah, uh Will, the the floor is yours uh if you're ready. >> Excellent. Thanks. Okay. Is that coming through? >> Yes. >> All right. Great. So, we Yeah. Uh it's the first I guess PQ interop the like Justin mentioned the it's the first in a series of iterative uh feature focused subnets. So, we're kind of working to like incrementally build up a new link instances client.

PQ Interop - Coordination Overview (Will)

you know, it's sort of one layer at a time and really starting this whole effort with uh the postquantum signature aggregation which you'll learn a lot more about the details today. So really kind of like setting the stage by h how are we balancing out all of these key variables like the design of the uh PQ signature schemas efficient networking faster slots 4 second slots uh three slot finality and then also kind of bootstrapping some of the uh I guess uh infrastructure that goes that's involved in a multiclient DevNet uh you know process and so really trying to learn what we can from the ETH pandops, from

the steel team, protocol security, uh leaning in on metrics and things of that nature. So, uh really all of this is you sort of like trying to balance out all of these design variables such as validator count. Uh Justin was talking about the the the amount of time that it takes to generate the keys based off of uh lifetime. So looking at the file size, the keygen time, the lifetime and trying to balance out all those variables and then do this uh obviously in a multiclient uh environment. And so all the participants in this, you know, were kind of uh the first half of this year like the the

beam chain uh talks like gave us an opportunity to all uh sort of begin to formulate these relationships and uh really the the the client teams that are emerging out of it as key participants and contributors are Ree and Ze and Quadrivium. Um and then with this particular effort, we've got a lot of uh cryptography researchers from the EF and beyond uh consensus researchers, networking researchers, and then people working on specifications, networking, things of that nature. And all trying to like advance this whole uh effort with a spirit of simplicity and optimality, which are core tenants of uh lean

Ethereum. So Justin already directed you to we also have uh a postquantum uh it started off as a telegram group. Now we have the bridgebot. So we've added the channel to uh the ETH R&D. You're more than welcome to join both. Uh we've got the calls as just mentioned every Wednesday at 2 PM UTC. Happy to see anyone there. Uh we try to post the calls uh to YouTube immediately after. And then um we kind of have this like uh sort of shadow fork of ACD emerging. We we created a GitHub or so we can work without like causing distractions to you like more timely

Fusaka related uh shipping efforts and things of that nature. So we've got a a lean Ethereum GitHub or uh within there there's a couple of different repos. We've got a PM repo where we're starting to issue PM spec sheet or sorry DevNet spec sheets and meeting minutes. We also have a project board in there so you can kind of see the efforts that are in flight and then all of the specs and subspecs that you'll learn about later on today. And as Justin mentioned, you know, we've been really the last two months we've gone through eight of these calls every month or every week. Um starting very high level uh Mazim and the the REM team kind of started off with their pitches

on what they wanted out of this DevNet uh process. You know what our stretch goals were to get to say by November and then trying to converge on some highlevel criteria for the DevNet. bringing in outside experts from ETH Pandops, Steel, uh Katia from Loadar has been helping out a lot with this uh idea of really trying to be metrics forward having uh you know client and you know agnostic metrics that we're able to measure um starting to build up all of the infrastructure that we need a fork of Dora um genesis generator things of that nature and then working on some uh getting all the specs written has been

really uh instrumental in that along with both of the or all the client teams and yeah we just finished uh DevNet zero specification last week which is great we haven't launched DevNet zero quite yet but as Justin mentioned we've got this Cambridge event coming up so really kind of working to get the first uh DevNet zero up and running before then finalize DevNet one spec before then and then use that IRL event to uh really take things to the next level. Uh so yeah, there's already a lot of uh key objectives that we're targeting get to get out of that uh that workshop and then there's some special topics uh so

looking into some additional research uh around cryptography and then also trying to finalize the criteria and structure around the proximity prize, the million-doll uh effort that Justin announced recently. And I guess fear not, all of this will be uh recorded just like Beam Day was. So we'll make the effort to record what we can and and get it transcribed and up on YouTube and and notes shared. >> Amazing. Thank you. Thank you, Will. Any questions?

Uh so Dra is asking given we're assuming a >> Go ahead. >> Oh yes. Um I said so you're assuming that you have access to a quantum uh postquantum recessive proof system. So um another approach rather than using XMSS um would be to just prove knowledge of the private key. Have you considered the um performance trade-offs of that um flexibility trade-offs because obviously if you have a signature of knowledge then you can prove any anything else that you want to do at the same time. Um if you need more than one signature you can do private aggregation.

>> Right? So this is actually that was our starting point. Um so there's a a project called Ziggy from Stockware where they do exactly this. Um and there's I guess two trade-offs. The first one is that the signatures the leaf signatures are bigger. Um so tens of kilobytes instead of 3 kilobytes. Uh, and more likely than not, bandwidth is actually our bottleneck. Um, the other big trade-off is actually the three trade-off. The other big trade-off is that the signing time grows quite a bit. So, you know, we're talking about hundreds of microsconds on a single call, but if you're doing a a proof of knowledge like Ziggy, it will take

significantly longer. And one of the things that we want to do is be friendly to very weak devices. And by very weak, we have like very strong requirements. So the the device that we have in mind as kind of the minimum barrier to entry is a Raspberry Pi Pico, which is a a $7 piece of hardware. And so that's kind of fast enough to be able to generate those those signatures uh in in a single core. Um and then another advantage of going down XMSS has to do with security. So generally the security analysis of of of you know proofs of knowledge are in the random oracle model whereas here we have

security in the in the standard model and um you know what we want is to have maximum security of the of the leaf signatures because that's something that wouldn't change hopefully ever. I see. Okay. >> Whereas the aggregation which is in the random model potentially could uh could change. >> Thank you. >> Absolutely great questions. Okay. Uh next up we have Felipe who will talk about the lean specification template that uh he created.

>> All right. Let me try to share my screen. And can you see that? Okay. >> Great. So, I'll try to just lay down some of the the Python foundation for the specs and then others here will talk about um what we've what we've done there so far. Um let's see. There we go. So the repository structure um for leanspec is is basically this. So we have uh the specifications tree um with some type definitions that can be distributed you know more generally across the subspecs

leanSpec - Python Overview (Felipe)

as well. And uh in the subspecs directory um well we have the subspecifications um and the tests uh have a this nice mirrored tree where you can reference sort of uh the specification tests um with the specification uh in a similar um hierarchy in a similar pattern. uh we have the documentation and uh we have a pi project tunnel where uh it's it's basically a single source of uh configuration for the entire uh python side of the project.

Um a little high level highle overview of the of the setup that we have. Um we kept some pretty modern uh python version support. So, it's 312 and and above and uh 314 is scheduled for October. So, we'll have to see if if there's anything there. But since we uh are just getting started, I don't I don't see any issues there. Um it's nice to have the more modern version so we can we can keep some like um syntax more modern syntax support there. Um the the tooling that that we went with uh was a little inspired by some of the

other specifications that like the execution specs uh from part of the skill team as well as the uh testing side the execution spec tests. So we use uh some of these tools UV rough uh talks uh a couple of these are um all the ones on the screen there. A few of these are are pretty standard for projects, but I'll talk a little bit about why we used some of the the other tools in the next slides. Um like I mentioned, you know, project tunnels where you could find u most of the configuration. The one of the exceptions is the talks any where you can um just configure commands for talks which is pretty standard for Python projects as well if you're familiar. Um and a little bit about the typing. Uh currently we have

some very simple types defined with with Pyantic which is really nice and and I'll get a little into the Pyantic site as well but uh Tama has been doing a really good job of defining some simple types there that are um that live within the the repository. Um but we have this goal uh of aligning types sort of across the specification repositories uh at least some of the base types um and then the more specific types can can just live inside the the lean spec. um why we went with UV. Uh this is built with Rust. So it's much faster than some of the traditional tooling for Python projects. If you're familiar with uh pip

or virtual environment creation, um this does it much faster. Uh it's an all all-in-one replacement for pip and and virtual environment managers. Um so it's it's quite nice. It leads to some simple powerful commands so you can just come in and and start working on it like uh just UVsync all extras will build you a virtual environment. It'll install all your dependencies and you're ready to go uh with this package. Rough is much the same way also built with Rust same team. Uh the Astral team is doing uh some really nice work with with Python tooling uh to make it faster. Uh, so because it's the same team, there's some seamless integration

there. So these tools were borrowed from the steel repos and it's really nice to use. This is an all-in-one replacement for um if you're used to uh Python projects. It bundles flake 8 for linting, eyesort for importing, black for code formatting. So it's really nice as well. It's much faster. Uh you can also configure everything in the pi project tol or if that ever grows too big uh rough has this nice way of of specifying its own uh configuration file.

Um a little bit of the development tool chain. Pyantic has been uh really nice for validating uh some of our data models. Um this proves also really nice on the JSON deserialization and serialization support. uh I will go into that a little bit and how that's helped in the other specification repositories and and kind of why we chose to use it here. Uh piest is the standard for testing. There's uh there's a lot of um support that the and flexibility that the framework gives us robustness. It's been around for a while there. That's a no-brainer. Uh and some of these are are standard talks. uh my pi uh make docs for documentation and

spell checker just to keep some short PRs low. Um pi dantic. Um so this is kind of like the main focus for for um allowing data models to uh just have validation built into it. Uh we don't really use the serialization just yet, but um basically invalid data can't exist. Um and so you just get to focus on the code and the readability there. Um Identic is an entire library that that does the validation, right? They have their own tests for this and and they work really well. Um a good example of this is like is creating this trick base model which Tom has created and this basically can

make all your types immutable. It can forbid extra fields. So uh pyantic also provides us some really nice configurations that we can just set for for base types. Um, and the the JSON serialization really kind of comes into play when we start thinking about maybe filling uh test vectors for clients from the specs from the Python code and and generating u JSON objects from those or filling our uh Python models from um uh test vectors in cryptography libraries or or any from anywhere else uh for testing within our our repository as well.

So this is just some really nice setup and a really a really good direction to head for for Python uh types. Um and my uh suggestion here is that uh so borrowing um again inspiration from from what's been done right I think in in my in opinion in the execution specs and the testing side uh pi dantic with piest can provide us in the future eventually uh some of this really nice um framework uh this nice flow for for uh possibly testing.

So, Piest in itself uh is is just the standard. Um it provides reusable fixtures and setups, across tests, parameterization, built-in support for temp directories, mocking, exception testing, all all of these nice bells and whistles. But at the same time, thinking ahead about clients consuming uh test vectors. Uh what we've seen on this in the steel side in the in the tests repo is there's an extensive uh area to to reach into with custom plugins and and and piests extensive hooks that they have and uh basically what what East has done the

the testing side is and we can imagine something similar you know some sort of uh you know maybe even future testing scenario comes about but defining custom plugins that can now with the Pyantic models and JSON uh support we can define test cases that will fill JSON test vectors and run they run these expectations against the specifications. So they they fill using the specifications and then receiving that validated output, you can execute those against clients. And so this has been a really nice flow for them. I think I think it's a pattern that's worth exploring here eventually. Um and yeah, these these can

be used to consume generated fixtures for simulator interactions on Hive. Uh you can execute them on live networks. Um so this is really a lot of flexibility and robustness that uh piest and py dante can provide and uh yeah and maybe flexibility for potential scenarios uh exploring custom plugins and that's sort of all I have on the on the project setup uh side of things. I'll stop sharing.

>> Amazing. Uh, thank you so much, Felipe. Um, any questions, especially from from the devs or the speckers? I mean, for my part, I'm really pleased that all of the best practices have been uh or at least most of them have been condensed in this template. And uh I think this is going to make a big difference relative to the beacon chain where I think we made a lot of mistakes. Um and uh hopefully that will allow us to to move significantly faster.

>> Thanks again uh Filipe. Um next up we have uh Tomas who will talk about uh the specking effort for lean sick. >> Yes, let me share my screen. Can you see my screen? >> Okay. So, perfect. So, hello everyone.

leanMultisig Spec (Thomas)

Uh, my name is Tom and today I'm excited to present the LIN multis specification. This is um a general proposal for securing Ethereum future in a postquantum world. So over the next about 40 40 minutes we are going to walk through that vision that drive this work and the specific cryptographic elements we we we applied uh some high performance component we have designed and it's we can see that as a a complete reimagination of the consensus layer where SE simplicity and security are really important and the best practice

to So before we dive in uh the technical details of the specification, it's important to understand the eye level vision uh that motivate this works. So this is heavily based and inspired by the Justin Drake post on Linum which sets a very important mission for the next decade. So the vision can be splitted into two key mode. First, we have a defense mode that we can also call a fort mode. The goal here is absolute resilience. Um, what does this mean? This means that Ethereum needs to be a bedrock for the future of finance and the internet of value. This means

that it must survive anything like national state and most importantly for our talk of today um the threat of quantum computers. And second, we have the offense mode or beat mode. This is about extreme performance and massive scalability. So we are talking here about a future where thousand of transaction per second on the L1 and millions on the L2. The goal here is to make the onchain experience really seamless for all the new billions of user. But the challenge here is how do we achieve this beast mode performance without ever compromising the fourth security mode.

This is a question that we are trying to answer here through all of the design choices we made and through all of the specification. So first let us talk about kind of the lin period that that guided us through all of our choice and all of the specification design. So we try we try to translate this big vision into practical working code. We follow for this three core principles that define the lean spirit. First, maximum simplicity. Every component is designed to be as minimal and clean as possible. Complexity is kind of the enemy of security,

especially in cryptography. And by keeping the design very simple, we reduce the attack surface and make formal verification of the system correctness much more achievable. Second, we have nextgen cryptography. We are we are trying to move away from legacy crypto and uh building a unifi ashbased foundation. This approach is powerful because it simultaneously addresses two of the biggest trends in our space. First the rise of snarks and second the looming quantum threat.

In third we have a security. Our we try to bring to Ethereum there a conservative security model. We try to rely on the simplest most well understood cryptographic assumption proven in the standard model where possible. We avoid complex or exotic assumption wherever this is possible. And these three principles guide every decision we make in the spec. So now let us focus on the first major challenge that this directly solves signature aggregation in a postquantum world.

The problem is a quantum thread. Ethereum current consensus relies on BLS signature. They are super cool and fantastic for aggregation but their security is based on elliptic curve and we know that elliptic curve are vulnerable to attacks from future quantum computer. So this is kind of we can call that a ticking clock for Ethereum long-term security. We don't know when this will happen but we know that this will happen at some point and so we need to be prepared. So the alternative is a hashbased signature or even latisbased. A lot of option have been studied but we retain specifically

the XMSS signature scheme that we that was designed by the ETM cryptography team especially by Benedict and and Dimmitry from our team. And the security of this XMSS signature scheme relies only on the property of a secure ash function. And this is very important because this is a simple and secure assumption making it resistant to quantum attacks. For now, it's our best candidate for replacement. But of course, this comes with some issues and scalability challenge. Unlike BLS, individual XMSS signatures are large and computationally expensive to verify. We can't just have every

validators post their own XMSS signature on chain. It would be far too slow and costly. This means that aggregation is essential and we need a way to compress thousand of signature into a single small proof. And to endle the scale of ition, this system must support recursion. That means the ability to combine existing proof into a new one. This is the core problem we set out to solve. So to build this postquantum system, our specification is built on three core cryptographic ingredients that are listed into this slide.

Each one is carefully chosen to work perfectly uh in harmony with the others. First we have a prime field koala bear. This is we can say the mathematical universe where all of our operation take place. It's a 31 bit field specifically engineered for performance. As we will see it is optimized for both fast for transform and our chosen ash function which is procedon 2. Secondly we have the ash function procedon 2. We can't use we can't really use a standard ash function like chat 3 or blake. We need a ZK friendly ash function designed for algebraic circuit and I will I will

explain afterward why this is very important. Posedance 2 is a state-of-the-art designed to minimize the number of constraints needed in a stark which directly translate into faster proofs. And finally we have like the big pieces the signature scheme XMSS signature scheme. This is ashbased stateful signature scheme that provides the postquantum security for individual validator attestations. So then the rest of our talk will be a deep dive into each of these ingredients starting from the ground up with prime field.

So let's start at the absolute foundation. All the all of our cryptography is built on top of the structure that we call a prime field. For anyone that is not familiar, a prime field is a finite set of numbers that use clock mass or we can also call that modular arithmetic. As you can see in the diagram on this slide, when you go past the large number that is a prime, you just wrap around. This creates a closed predictable mathematical universe.

This property is absolutely essential for building cryptographic system especially for the snarks that we use to aggregate signatures but not just any prime field could work. We use a specifically engineer 31 bit field called koala bear. This was this was chosen for three key properties that make it perfect for our global proving stack. First and most critically for our snacks, it is it has a high toadicity of 24.

This is a mathematical property that means that the number p minus one p being the prime is has a very large factor of two. This structure is essential for running fast free transform which are in some sort the algorithmic engine inside modern snacks. You can find FFTs everywhere in modern stacks. So in summary, high toadicity means futroof in some sort. Second, the cube map is an automorphism. This may sound a bit abstract but it's a perfect end shake with our ash function posed two.

This is what you have to remember. And inside posed 2 uses a pix to x uh to the^ 3 operation for the non nonlinear security layer what we call sbox and we will see later what sbox is and because this is an automorphism in our field. This operation is incredibly efficient and algebraically clean which again leads to faster and simpler proof. So always more performance. And finally, um, Kalabar is a small field. It's a 31 prime field as opposed to larger field like 64 or even larger field for efficient computation on modern

hardware where we can apply very nice trick to make very efficient arith arithmetic between fields and its size allows also for fewer rounds in the postad permutation further boosting performance for this ash. Every property of this field was chosen for a reason as you can see. Then let us start. >> So now we have a question from Darra um asking is two high toity important for small fields versus large fields.

>> Yeah. Yeah. They are. Yeah. The twoity is is important. This is always a compromise between the size of the field, the two addicity and all of the property. But in for the small field, we had for the 31 bit field, we had the choose between baby bear and koala bear and uh baby bear as lessicity. So this is very nice for that. >> Okay. Um so let let us dive into into the spec right now and for the FP class. So let's look at how we translate this

mathematical field into a practical and safe Python implementation. For this we use the pedentic library that was presented just before by by Felipe uh to create our FP class. First, it's robust and safe. By inheriting from the base model, we can have an automatic validation. And the class ensures that any FP must hold a value within the correct mathematical range that is between zero and P being the prime. This prevent a world class of bugs from ever happening.

Second, our field elements are immutable thanks to the frozen true element right there that you can see here. Configuration means that once you create a field elements, its value can never be changed. This is a crucial feature for writing predictable and secure cryptographic code. So you cannot change the field by mistake. This is let us say additional security. This is a kind of an important feature to write test and everything safely.

Finally like the field validators there. This is a decorator that is quite important because it acts as a gatekeeper meaning that no matter what integrates what integer you pass to create an FP element it is automatically reduce modulo P before it's even created. you can't accidentally create an invalid element. In short, the implementation is designed to be as simple and safe as possible for the developer and link the complex cryptographic rules behind the scene.

In our Python spec, we make this advanced mats um feel natural and safe for developers. As you can see there, we have a summary of arithmetic operation and the FP class which represent a field elements overload all of the standard Python arithmetic operators. So you can add, subtract, multiply and divide this cryptographic object just like you will do with regular numbers. You have overloading for all of the operation right there on the right.

the implementation. So handle all of the complex modular arithmetic for you including division for example which is done by multiplying by the modular inverse. This is kind of encapsulate complexity for those who are quite familiar with more performance implementation like plunky 3. This should sound a bit short for modular arithmetic operation but here performance is not the objective. We just want a very simple spec without any performance consideration. So of course if you want performance you can add any source of trick and different algorithm to make this operation fast and using even SIMD instruction or anything but this is not the goal there

and we include also another practical optimization when we generated up front a list of two addict generators in some sort. These are special fields elements that are required to run the FFTs instead of calculating them on the fly which can be quite slow. This spec provide a direct lookup table. So as you can see there inside this function this function is 01 complexity because this is just a array lookup. Now for our second ingredient this is the ash function. As I mentioned, we use Postadon 2 because Posaden 2 is ZK friendly. Its main goal is to be cheap inside the ZK circuit. Traditional ashes

like SH3 or Blake are very fast on a CPU, much faster than poson, but create millions of constraints in a snark. Posedon 2 create very few which means faster proving time and smaller cheaper proof. It's an evolution of the original posed with optimis with optimized linear layers that make it much faster. As you can see there on the right in the using the scheme especially this one. It follows the addest philosophy which you can see in this ones.

It mix it is a mix of expensive full round that you can see there on the top and there on the bottom where every part of the state is mixed here you have the S box right there and you can see that for both of these full round all of the part of the state are transformed and in the middle we have um cheap partial run where only one element is transformed as you can see there only a single element is transformed and not the other ones.

So this provides the necessary security against both statistical and algebraic attack at a fraction of the computational cost when compared to poson one and as we discussed at it core like the sbox right there is using the x to the^ 3 which is a perfect match for the property of our collabor field. Now let's look at the the building blocks for proagon 2 permutation. First we have the state. This is the we can see that as the internal memory of the ash function represented as a list of coal field elements.

The size of the states or the widths determine the security and the throughput of the hash. Our spec provide optimized parameter for width of 16 and 24 which are the two widths used in production and all over the place in our XMSS signature scheme and in our proof system. Second we have the Sbox that we have seen in the previous slide uh in the non this is a nonlinear layer and the core source of the function security as we established our spec use high efficient cube map which is a perfect fit for the collab bear field and third we have the linear layer the linear

layer this provide diffusion meaning that they mix the state so that a change in a single input bits affect the anti ire output. The key innovation initi in procedon 2 compared to procedon one is that it uses two different highly optimized linear layer for maximum speed. Let us see these two linear layers. First we have the external layer used during the full round of the permutation. Its purpose is maximal diffusion. It's built from a a strong 4x4 MDS matrix and ensures that the state is mixed at the beginning and at

the end of the process. Remember that we have this full rounds at the beginning and the end of the process. It's strong but more computationally intensive. And in the middle we have the internal layer that is used during the many partial run and is designed for one thing for speed. It provides a fast and lightweight diffusion. It structure allow to be applied in linear time instead of quadric time which is a massive performance gain making procedon 2 faster than procedon one.

Now I will present you like the the permit function. The permit function in our space is is a public facing API for the user. So the user for the ash function posed to should only use the permit function and all of the internal call are hidden inside this function. This is the only function that should be used by the user. So this orchestrates the entire process following the design strategies that I just me mentioned before. I will detail how it works. So it start with an initial layer on the right. You can see here this initial layer right there with a with comment to explain you how it works.

This prevents certain algebraic attack. Then it runs a few full rounds right there using the strong external layer and applying the SBOX to the entire state. This provides the initial robust mixing as you can see on this precise line. I know this is a bit small but there the Sbox is applied for S in state meaning for all of the element of the state. Next we have the many partial round where the Sbox is only apply to the first element of the state. This is let us say the chip internal layer used for diffusion. This is where we have the

optimization. And as you can see there in this line, the Sbox is just apply to the first element of the state state zero and not to all of the element of the state as it was done for the previous one. And finally we conclude with another set of full round to ensure that the output is completed and securely mixed. And here once again like the SBOX strategy is applied to all of the element of the state. So this global strategy give us the security of a complex permutation at a fraction of the procedon one.

I wanted also to make everything flexible and safe. So the spec for proced because we have like a set of parameters to define any permutation uses pedantic model and uh the class hold all of the configuration for a given instance. for example, the width or the number of full round and partial round. Crucially, it also all um the premputed constants needed for the permutation and it includes right there a validator that automatically checks if the length of this constant list match the um the expected configuration. So this is um an

automatic check and that is very useful because it prevent any source of bug. Okay. So now we have our fast field and our fast ash function. Now we can finally talk about the main event of this talk. The XMSS signature scheme that is built on top of them. What is exactly XMSS? As we had discussed it's ashbased postquantum secure function. Its security rely only on our ash function pose 2 not on the complex match problem that quantum computer can break. It is stateful by design meaning that each signature is tied to a specific time or epoch. This

sounds like a limitation maybe, but actually if you think about it, this is perfect for proof of stake because validators have a naturally sequential job of signing block one after the other. And so this removes the risk of key reuse and allows for a much simpler and more efficient design for the signature scheme. So at it score XMss is a nice way to get many time signature from one time secret and we will see how this work precisely. If you are a vis visual person I have put like a diagram right there that I will detail. So the scheme is built from two simple ashbased

components. First we have winter one time signature. This is a very simple signature based on ash chain. As the name implies, it's only secure to use once. If you look at there, you have all of these ash chains right there. And at the bottom of them, you have all of the secrets key in red. So, and how do we sign multiple times? Now, this is where the second ingredients come in. The Merkel tree that you can see there on the top. A merkel tree is used as an aggregator. A validator generates thousand of winter needs key pairs in advance, one for each fut slot they will sign. And then they

place the public keys of this one time signature as the leaves of the mel tree right there in blue and publish the the three single roots um as a long as their long-term public key in blue at the top right there. This route is very important because you will see later that the verifier will need to know this route to be able to verify a message. So if I recap on this uh nice nice diagram at the bottom in red you have all of the secret key and you have a certain number of hash in the chains at the top of them after ashing the the

secret key a certain number of time you have the associated public key. Then you ash all of the corresponding public key together to form the leaves of the merkel tree. And then you you do your classical Merkel tree. And at the end you have a final global public key that is the root of your Merkel tree. And here you can see that to summarize if you want to sign any message you first encode it. We don't need to know what it is right now. But as a function of your encoding you will have to hash a certain number of time each chain. And in green there you end up with a signature. And to

verify this signature you will have to reash each element of the chain up to the given public key. And then uh the verifier will reconstruct the final Merkel tree to compare the roots. This is the basic of the signing. But what you have to retain is this ash chains at the bottom and the in the Merkel tree. This is what is important for our spec. So now we will explore the three main element of the public API and the first one is the key generation process using the key gen function.

So this formula is a setup. First it generates the master secrets a random PRF key and the public parameter. This PF key is the single root secret that everything else is derived from. So all of your one-time secret key will be derived from this PRF. This is the first step that you can see right there in the Python in the pseudo Python. Then for each epoch the key will be active and a one time key will be derived using the PRF. Then we build the Merkel tree over the public parts as you have as you have seen in the diagram

before of this one time key and the roots become the main component of the public key. So here I have pointed out this Merkel tree and finally you bundle everything together to form like a public key and secret key object ready for signing right there. there. I wanted just to briefly mention a new innovation that just came out through a new new paper of Benedict and Dimmitri because one of the major bottleneck in ashbased signature is the verification cost. meaning that the number of hashes the verifi the verifier has to compute to go from the the

message the the signature to the public keys. Our spec include a new novel optimization to address this called top of the IP cube encoding. The problem with traditional method is that they can produce signatures that are slow to verify due to a huge number of hash to be done by the verifier. The insight here is that instead of allowing any valid signature, we can force the signature to be chosen from a small predefined set of highly efficient regions. This al algorithm take a message h ash and detamistically maps it to a signature format that required the

fewest possible operation to verify. The result is a 20 to 50% reduction in verification cost with no loss of security and no increase in signature size. This is a huge win for onchain efficiency. If you are a visual person in on the right, I put a small diagram uh where you have all of these ash chains. And as you can see on the right, we can have a mental model of this as an hyper cube. And the more you go on the top of the hyper cube, the less the verifier has to do as a job. That means the top of the per cube meaning less

ashes to do by the verifier. And so the target is to go on the top of the IP cube. Of course there are all sorts of of trick and concerns and security stuff but you can have dismantal model. Then let us go to the sign process. So the sign function puts all the pieces together. First is need to find a valid encoding. The signer repeatedly ashes the message with a new randomness each time row until the output lands in the efficient top of the hyper cube region. This is the loop defined there. So you have a

max try and up to this max try the signer will try again and again and again to encode the message to to be in this valid region. Then we create the one-time signature based on this valid encoding. This is the job that is done right there in this big loop using what we call the code word. This is a valid encoding of the message. Then it generates the Merkel pass. That is what you can see right there. And this Merkel pass will be directly uh given to the verifier for him to be able to reconstruct the full Merkel tree and to be able to check the final route.

And finally everything is assembled together into a signature object at the very hand there containing the Merkel pass the randomness row and uh the hashes. This is a single signature object ready for verification. And finally we have the third function that is part of the public API. This is a verification function. This is let us say the most important one because this is the one that will be used in our snark system because all of the aggregators that will want to aggregate signature together to form a single proof to put on chain will use this verification to verify again and again

all of the keys. So verification is the reverse process in some sort and is fully deterministic. First the ver the verifier reuse the randomness row from the signature right to recomp compute the code word. So the code word is recomputed right there. Second it's recmp compute the one time public key by completing the all of the ash chains remember the previous diagram from the intermediate value provided in the signature.

Then they hash this reconstructed key to recomputee the Merkel leaf. And finally as the Merkel pass was provided by the serer we can reconstruute the full Merkel tree. And the final check is very simple. The signature is valid if and only if the candidate root that is obtained at the end of the hashes matches the the root in the public key. This is a final check that you can see there. When the Merkel treeverify pass is called, this is just at the end a boolean true or false that determines if the verifying function succeed or not.

Now to wrap up our deep dive into XMSS, uh let's look at how the spec organized all of these component into clean and safe data structure. Here I only wanted to point it out the main object let us say. So we have first the public key. This is a public facing identity of the serer. It's very small containing just the mer route and the public parameter. We have the secret key containing all of the private material and most importantly the master pf key from what everything else will be derived and the premputed merry. Of course, all of that must must be kept secret. This is a

secret key. We have the signature object that is the one uh the object produced by the sign function in it bundles everything a verifier needs to know to verify the signature. This is a class that you can see on the right. And finally, you have the XMSS config object um that gives you all of the constant and parameters for a griven preset. We have a pro config, but this pro config contains large constants and so the key generation will take a huge amount of time to generate the keys and everything. And so we have also a test

config where the parameters are much smaller for you to run unit test or to play with it. Finally, so we have designed a highly optimized postquantum signature scheme with a clean specification. We try to do so. But how do we know that everything is actually correct? The final part of what I called at the beginning the lean spirit is a commitment to rigorous testing and I want here briefly to touch on with two very simple slide.

So our testing philosophy is built on four four core principles to ensure every layer of the spec is solid. First this is very basic but unit test every single function and class is tested completely in isolation to ensure that it behaves completely uh as expected. Second we have a lot of round trip integrity test. This is quite easy to do to do with a lot of cryptographic component but we constantly test that inverse operation work perfectly. This applies for example to an encoding decoding things or to the entire key gen sign and verify life cycle is if you sign something you must be able.

So third we have some known answer tests for critical crypto primitives like posed 2 permutation. We test against precomputed test vectors using plonis 3 for example that is an existing audit library. So we know how to compute expected value from there. This ensures that our implementation is correct and pro protects against any future code change that may accidentally introduce bug. And f finally robustness and security. We don't I have tried to not just test only the happy pass but explicitly check that our code fail as expected under any invalid inputs or

anything. But of course all of that could be improved with time. And here on the right you can see like um a full run test for the signature precisely. So at the beginning we generate some key then we sign and verify a message and we test also to verify an invalid message and we ex we try to to check if the the verification is as expected and we do this test with a bunch of different configuration to ensure that we are not just lucky and everything works perfectly.

So this philosophy is put into practice using a clear and modular test structure built on the pi test framework as mentioned previously by Filipe. We have a modular test suite uh with a dedicated uh test file for each cryptographic component and this is also valid outside of the cryptography. We are try to have a single test file for each component. This keeps our tests organized and easily to maintain. We use parameterization for coverage to efficiently run the same logic against many different configuration without duplicating code. This is for example what you can see there on the right to

test uh the correctness of the run tree test. We run under bunch of configuration with the lifetime start starting at zero epoch and then with the lifetime starting later and we try to find different configuration that can be challenging for the code. For most of our complex and optimized algorithm like like for example the IP cube encoding, we perform validation against some reference model and other implementation against uh and other correct mathematical implementation to check between two of them and finally we combine everything with end to end scenario to simulate

real world usage and what the user will do. Um so finally to wrap up around everything the lean multistic specification kind of represents like a holistic approach to security room. So we tried to build in uh using the lean principle of simplicity and security and uh for now it solve the postquantum signature challenge but in the future we will add also other element of the stack such as like our foolproving system including the Pop, the minimal ZKVM as well as as a PCS and other any other components

that should make the link consensus uh done to the end. So thank you very much and I will know be happy to answer any of of your question. >> Thank you to uh fantastic presentation. Um, one question that we have from Divia is, uh, wouldn't it be better to do to also have property based testing since we're dealing with specifications that that have invariance? >> What do you mean exactly by by this question?

>> Oh, can I speak? >> Yes, of course. >> Yeah. Yeah, of course. >> Sure. I I meant uh since we have specifications that have certain invariance like an hyper cube that is defined in a specific way um wouldn't it be better to test that specification against a property that it should satisfy so I sent the hypothesis um a package which where you can define a particular property say a hyper cube should have a particular property and then you can sort of test it um and then you don't have to sort build a number of unit tests instead one property that will be valid for any amount of input.

We have also this we have also this unit test and we are working to improve that. But we already have this kind of unit test. For example, for the hyper cube, we have a specific uh file where we have some kind of small unit test. But as you just mentioned, we have also some tests that specifically uh test the properties of the hyper cube. So that for example the I say completely random thing but for example the sum of this array should be that or should be that and we have such test but of course all what I have described is very new and so we are working very hard to improve that. Also

I I I forgot to mention during my presentation but through the work of Emil, we recently discovered that maybe the top of the AP cube encoding system is not the most snark friendly and this encoding may may change in the future. This is only a piece of the signature scheme and we can change it quite easily. So maybe this will not be the the final encoding scheme. >> Okay, thank you. Oh, a snark optimization problem. I'll get my teeth into that.

>> Yay. We'd love to have you. >> Yeah, >> dra. Um, Filipe gave a a thumbs up to hypothesis, which is seems to be a specific repo um that diff linked to. Uh, so I guess we'll we'll have a look into that. Um, one question from Path is what's the correct way to represent a public key if its size is 50 bytes? And I guess what he's getting at here is that it's not a multiple of 60 of it's not a power of two. Um, and I guess one thing we could do for efficiency is to put a bunch of the the flags uh and the kind of other validator information and concatenate it with the

50 bytes so that you get 64 bytes for example. So when you register as a validator um one of the things that we're we're looking to do uh in the context of of rainbow staking is to have multiple roles. So you could have the atttor role, the proposer role, and the includ role. And for each there would be uh a bit that you can set to to true or false. Uh and if you want to have delegations or there would be bits and if you want to accept delegations there would also be bits. So there's all sorts of metadata that we could squeeze in the in the 50 bytes.

I guess for now we could just uh have an SSD object which is a list of of 50 bytes and it would implicitly be padded with with zeros I guess. >> Yeah, for for for now at least in the Python spec we didn't handle anything with any optimization of this sort. We just represented very simply like the public key as the root plus the random parameter let us say and so this is just a list of finite field elements and then we can just SSD this list and but we can do any source of optimization of course so if I'm understanding the um uh of the hyper cube optimization it's basically

finding a point in the um hyper cube to encode a message um that gives you a constant number of um uh evaluations rather than a variable number as in um original XMSSS, right? Um and so the the snark optimization problem is basically rooting the inputs and outputs of the hash functions um correctly given that you have a fixed number of hashes.

Is that right? >> It's mostly um mapping um a hash output into all the into a point in the particular hyperloop layer more or less uniformly. And the problem is that kind of this number of points and a particular layer is not particularly nice number. And when you snarkify this process which point you end up to you have to deal with kind of long integers not particularly long like 130 bit or something but still it requires some machinery like table lookups as well uh for example if you have tables then it's

not so hard if you don't have tables as we kind of that the plan for minimal ISA then it's I mean you you might be able to um kind of tailor it to the koala bear field. Um I have to think about it. >> Yeah. I I think that also Emil will just in the presentation just after Emil will talk about the ZKVM >> and I am sure that he will kind of of mention this challenge but yeah I I think my understanding is that for now at least in the Z minimal ZKVM we started with the basic encoding. So no hyper cube things for now but Emil will be able to answer this question.

>> Okay. Thanks. >> So removing the the checksum is an optimization that was known ahead of this paper. This paper comes up with kind of this in some sense cooler and more subtle uh optimization uh which has to do >> Yes. Yeah. >> Okay. Nice. oh actually one um point that I didn't mention when you asked your first question Dra was uh another very nice property of uh XMSS is that you um you you don't have side channel attacks that could leak the private key. So because you're dealing with one-time signatures, it doesn't really matter if if you have a constant time implementation for

example, whereas if you have uh >> so in some sense we're really embracing the uh the fact that we have stateful signatures in context of proof of stake. Um and and and and that dramatically simplifies things. >> Okay. Yep. That that's definitely an advantage. I have seen also a question in the chat about like if there is implementation in other language or this specification. So I just linked a repo made by Benedict about the signature. This is made in rust and so we basically use the primitives of plunky 3 especially like the the field the koala field used from pron. So it should be harder to read than the Python spec

because this is much more complex and optimization friendly. But yeah, we have this Rust implementation as well. Just relaying a comment from the chat. Uh Manu from lip lip P2P says that uh he really likes the um the tooling that was put in place by Filipe and it it closely mirrors what they have. So that's a a great signal. >> Yeah. >> Um >> and all all of this spec is quite new.

So please don't don't hesitate to put uh any comment in the repo, open any issues, contact me in DM or anything like I would be more than happy to have new best practice or new test or any anything that could be relevant of course I will take or even like opening a peer on the repo I will review and merge for sure >> and manu is also asking for I guess links to the literature and the resources. is and we have plenty of of writeups and content and we also have a previous call lean consensus call dedicated to the research around postquantum signatures.

>> Yeah, if you want what I can do is that to avoid that being lost there in the in the channel. I can post that in the telegram group afterwards like we have a bunch of literatures, papers, notes, repo and stuff. So I I can put everything in the telegram group. >> Is asking >> by uh role do you mean regular validator versus aggregator? Um I actually meant >> in the context of uh of of lean consensus where a single so part of the idea with with u with rainbow staking is to get rid of the notion of the validator uh and unbundle it instead we kind of start with a notion of just a

staker and then the staker can opt in to various roles as they see fit and the three main ones would be uh a tester uh proposer and includer. included in the context of of fossil inclusion list for for censorship resistance >> and I think that it is enough that kind of 10% of the global validators optin to be aggregators they will at the beginning of the talk you mentioned that validators could run on the Raspberry Pi Poder and the aggregators will just have to have like a MacBook Pro or like a modern CPU to to do the job of

aggregation and being able to run the proof on their computer, right? >> Exactly. Yes. Okay. Thank you so much, uh, Tom. Um, next up we have Emil, uh, who will be talking about the virtual machine that he's been actively working on. >> Hello everyone. Can you see my screen? Amazing. So um please don't hesitate to interrupt me at any time. I'm not always very clear. So today I'm going to talk to you about this famous minimal ZK virtual machine for Linarium.

Minimal zkVM for leanEthereum (Emile)

Just to recall what do we want? Why do we need this this virtual this VM? first to aggregate XMss and second to aggregate those already aggregated signatures which basically comes down to recursion. Here you can find a list of all the very interesting papers um my talk is based on. If you have time don't hesitate to read them. First as a building block for this minimal ZKVM we are going to need a way to prove validity of air constraints. So very quickly what is an air table? You have a

bunch of column that you fill with feed elements and you have multivariate polomials that must equal that must vanish equals to zero at each transition between two consecutive rows of your table. Traditionally air tables were proven using univariate PCS fry using questioning and often using a big field and I think it might be relevant for us to move to the multilinear paradigm. So replacing fry with the weird PCS which offer offers lighter proofs to replace the cushioning with some check based

approach zero check and to replace the big field with the pagad the the paradigm of small field big field like base field extension field and as Thomas mentioned collap field is a very promising candidate for Here I'm going to present quickly one way to prove validity of air constraints using this setting this multilinear sun check based setting and you can see this as like multilinear st as simple as that.

First we need to commit to our table. Classically what you do is that you commit to each column as a individual separate univariate polomial. Here in our settings, what we are going to do is that we are going to pack our columns and to interpret the whole thing as a multilinear polinomial and to commit to this multilinear polinomial. To be precise, we interpret it as the evaluation over the boolean hyper cube on of multilinear polomial m.

So when you have encoded your air table you can commit to it and then I'm going to describe a simple concept to each column I associate up and down columns. So two different columns the the up column is almost identical to the original column except at the end. The down column as its name suggests I shift everything by one. So instead of starting by at a Z, it starts at A1, A2 and so on. I just skipped A Z. And the key idea here is that if the verifier has access to the original column A, I

can give access to the verifier to the A up and A down column using a check. You can reduce evaluations on a up and a down to evaluations on A using a simple subject. Using this fact, we are going to prove validity of one air constraint. So as I said in the beginning, one air constraint is simply a multivariate polomial in two times the number of columns in your table. And this constraint is valid if it vanishes at each transition

of our air table. And more precisely for all the the B n equals the logarithmic the log of the number of rows in our table. You must have this polinomial equal zero where I have reused the notation up and down column. And this uh this equality to zero can be reduced with high probability meaning crypto cryptographic probability to this sum equal zero where we have sample a random challenge error.

And in the end what you will do is that you will simply run a sum check for this and you will reduce the validity of your whole air table to a sum check. You you execute it and at the end of of your sim check the verifier will need to access some evaluations of a up a down b up down etc at some random point. here.

And using what we have seen here, we can reduce the evaluations of the up and down columns up and down columns to the evaluation of on the original columns with again a check. And so we are here and at this point the prover can send the claimed values on each separate column. So for now these values are claimed but turns out the verifier can mix them with some randomness alpha and alpha prime and reduce the validity of those four

evaluations to a single claim on our multilinear polinomial n. And so in the end what we've done is that we have reduced the validity of our air table to a single evaluation on the multilinear that encodes the table and the table uh itself. And just as a parenthesis, obviously if there are more than one air constraint, you can batch them using random challenge alpha. And one uh subtle t here is that if you want to get great performances on this zero check,

you will need to probably use a trick to avoid suffering from the embedding overheads that appear in the sum check because in the first round of a check you are in the base field but starting from the second round you are in the extension field where all the operations are costly and there are a few techniques techniques to um to tackle this issue. But one way to do it for instance is to use the inate skip by Angus Green. And just to uh give you an idea of how simple this approach here is, um a few months ago uh there was this uh this Python verifier in less than 500 lines

of code. It's it's really a proof of concept. it doesn't really work and so but the the main ideas are here uh and just to show you that it's possible to implement what I have presented in really a small number of lines and a very few Python files it's pretty straightforward now we have this uh building block which is able to prove uh validity of air table and we can be begin the the uh the the hard stuff which is to design this minimal ZK virtual machine. So here I have written down the list of most of

the complicated uh operations that our ZK virtual machine must perform. Obviously first the XMSS a regression and then the regression. Uh obviously a great source of of inspiration is the KO paper. I encourage everyone to read part of it. It's really interesting. And here the thesis is probably to avoid relying on too much pre-ompiles. When I say pre-ompile, I mean custom circuits or in ter they call it built-ins and to avoid relying on too much pre-ompiles because to a few pre-ompiles equal simplicity, equal security otherwise

and I believe it's possible to um take inspiration from ko but to slightly change some part of it. For instance, I believe it's possible to remove the allocation pointer. Let me explain. In KO, there are three uh registers. FP frame pointer, PC program pointer, and AP allocation pointer. FP points to the beginning of the current ST stack in memory, the current frame of where we are in memory. PC naturally points to the current instruction being executed in the by

code. And in KO AP resister used to point to the um reg to the the frontier the limit in memory uh of the the region which is not not uh which is which has not been used yet in memory. And in the next slides, I will explain how it's possible to program complex to have a complex programs with this um without relying on this IP register. And when it comes to the memory, I believe probably as a read only memory is the

most simple and efficient approach for what we are trying to build. And in the memory there will be two parts. This public memory part here is uh set by the verifier itself. For instance, when the verifier wants to verify the correct execution of a given program, if this program has some parameters, some inputs, these parameters will be written down in this public memory and the rest is committed. And this is where the execution the rest of the execution takes place.

I believe it's possible to have a pretty decent um ISAI using only four basic incriptions that I'm going to to describe. As in KO, we obviously need to be able to addition and to add and multiply elements of our memory. So add we also want probably this reference instruction which basically let you uh access some other frame in memory because as you can see when you add everything is uh as offsets relative to the current frame pointer. So you have

to imagine that when at some point in the execution you have your frame pointer that points to the start of your current frame, you perform operations relatively to this frame pointer. But if you want to access some data in another frame, for instance, to call a function, you will need this d reference instruction. We will come back to this later. And finally a jump instruction which is a conditional jump which enables naturally to have conditions, functions, loops and so on. And note that when you jump you have the possibility or not to modify

the current frame pointer. You can keep it like it's currently or you or you can update it with a new value. This is crucial in order to have efficient functions. We will probably also need pre-ompiles for instance for the hashes because both XMSS aggregation and recursion will involve a bunch of hashes and so at least two pre-ompiles one for poson over 16 feed elements and one for poson over 24 feed elements and while implementing the regression program it turned out that we probably would need a few

additional pre-ompiles for recursion and for instance one product pre-ompile to perform um to perform like an inner product but in the extension feed because most of the recursion operation happen in the extension feed and one multilinear evaluation recompiles that let you that lets you interpret a chunk of memory as a multilinear polinomial with coefficients in the base field and to evaluate it at a point in the extension Note that this this last pre-ompile using a trick it's possible to implement it at almost no conceptual cost and no

proving time cost. Here is a quick overview of a possible architecture for this minimal virtual machine. So you have the memory below. I didn't represent the B code because I assume the verifier has access to the B code which is probably the case in our context. And apart from the memory, there are a bunch of air tables, one for execution and three for the pre-ompiles. Each air table has a lookup into the memory which is with logup star. I will come back to this later. And finally there is this run product arguments that

with fingerprinting and gker in order to ensure uh consistency between all the pre-ompiles and the execution calls. Note that in each air table some columns are not committed. They are virtual thanks to our lookup logup star. I will come back to this later. Here we are going to zoom a bit on the execution table. So I will need to explain what does logup star uh provide to us. Lookup star is an indexed lookup argument recently

developed by leukanov and contrary to previous lookups argument. You only need to commit to the index column to the table containing the data column but you don't need to commit to the column where uh you have the data corresponding to each index. So the the accessed values by the indexes you can omit this commitment you can skip this commitment and actually it will save a lot in terms of commitment cost um because for instance in ko at each cycle you need to fetch the instruction

the op code and to decompose it into a bunch of boolean flags. and offsets actually 15 flags and three offsets and you so you need to commit to 18 feed elements per cycle in KO. But one other alternative would be to interpret this as an index lookup from the program counter column into the bite code. And doing so you can completely avoid committing to these uh 18 um feed elements. You simply commit to the PC

column here and all the the flags and offsets uh that are uh that comes from the de composition of your instruction columns thanks to this logup star look up into the bite code. Same thing for the values access accessed into the memory of our virtual machine. You only commit to the indexes do not commit to the accessed values here. And in the end you get an execution table where you only commit to five field elements per cycle. PCF FP and three memory indexes.

And this is much less than KO. But the drawback of this current situation is that the air constraints have degree five which is more than in Ko for instance. This design this is currently designed like this because early experiments have shown that the commitment costs were probably the bottleneck. I know it's not always the case for some VMs. For instance, I was recently I was told recently that for SP1, it's not the case on their big GPUs, but early experiments on CPUs because everything here is on CPU showed that the bottleneck was probably commitment costs. And that's

why this air table for execution has been optimized to the extreme to commit to as um to a really low number of feed elements per cycle. But if the commitment cost turns out not to be the bottleneck, we can always decrease the degree of our air constraints by committing to auxiliary columns. Okay. So, >> Emil, we have a couple questions in the chat.

>> Uh, one is uh why do we have two variants of poseon with uh 16 and 24 field? >> A very good question. I will answer it. Typically when just I will take as example XMSS in XMss you first do lot of hashes for the chains. you will have this 64 chain hashes and for this you want poson over 16 feed elements because it's more efficient than poson over 24 but once you have done these 64 hash chains you get the winter needs one time signature public key which is the top of each hash chain and you need to verify

the ownership of this what's public key to the mer tree because you know the root of the mer tree which is the xss public key and doing so you need to hash a bunch of uh so you need to hash the what's public key and if I rephrase you need to hash a lot of data and when you need to hash lot of data you probably want to use poson over 24 elements because you will hash two times more data At each time you apply your permutation because each time you apply you need to keep eight feed elements to keep the

previous information and you have 16 feed element that you can incorporate from the slice you you want to add to hash. So you so you need two times less hashes using poson over 24 elements. Have you considered using a a tree hash rather than So what you just said was for a sponge. Is that right? >> Well, we use just to to hash really long data, but for a tree when you have a tree, it's enough if you have hash like 512 into 256. And for this, it's enough to have Poseidon 16 because in the compression mode when you just feed back the input to the output, you don't have

to use sponge. to just kind of put all the input into 51 12 bits uh then apply the permutation then you sort the input to the output and then you're done. I I understand but I was suggesting using um a tree hash for the long data as well um because then you uh no you have a permutation as um your primitive so that yeah if you had a 2:1 hash then you could use that but that's not what you have I think it still be less efficient than the sponge >> yeah it will be yeah you could consider other hashing modes The other question comment uh has to do

with complexity. Um so if we avoid pre-ompiles, do we have complexity elsewhere? For example, in in the compiler or or elsewhere? >> No, pre-ompiles are only here for performance. Actually, uh implementing poson without pre-ompile would be quite difficult. But for the two pre-ompiles like the product and multilinear evaluation it's only for performance. >> No the I think were you talking about my question? Um so the the intent of the question was the other way around. Um can you do uh without a VM at all? So just using pre-ompile and essentially using a custom circuit.

>> Ah yes you mean no VM and one big custom service. >> Yes in the style of say orchard. What's happening? >> Yes. Yes. uh it would probably be possible indeed it's it's a it's totally possible just I would think the trade-off is the conceptual simplicity because intuitively uh it's probably easier to implement this with some kind of programming language and so on than with a pure arithmetic circuit but I think it could be true but um high level programming languages can compile circuits.

>> Uh sorry, >> a high level programming language can can be compiled to circuits. Um especially if they're tailored for that use. Um but yeah, it's it's a perfectly valid approach what you do. >> I mean, one thing we we're seeing in practice is that all of the commercial ZKVMs, you know, SP1, RES Zero, etc., they've implemented a minimal ZKVM specifically to do the recursion. and just designing this circuit would be would be very very difficult or maybe relies on fancy fancy compilers uh which is something we haven't really explored.

I mean, I can't really contradict that because we um that's one of the reasons that um we haven't used um recursion in the cache yet, even though um Halo 2 is designed to support it. And um yeah, it's it's just the complexity of writing the recursion circuit. Um >> interesting. >> So, fair point. The other kind of stretch goal for all of this is potentially to have this end to end formally verified minimal ZKVM that can cater for other use cases. Um so for example there's um aggregation of signatures at the application layer. You know for example Falcon could also be

aggregated potentially. Um we have this notion called a privacy wormhole. uh which is basically having privacy at L1 similar to to Zcash. Um and here you would need to prove that you sent your funds to an unspendable address. Um and we could potentially reuse the ZKVM for that. Um and if we do a really good job, maybe other blockchains and ecosystems could also reuse the the the ZKVM. For example, Bitcoin is going to need some form of signature aggregation because today it can do three transactions a second. If the signatures are 10 times larger, it will only be able to do 0.3

transactions per second. And so I think it's plausible that they will either increase the the block size or have some form of of aggregation. And we're doing all of the heavy lifting to design something which is Bitcoiner friendly in some sense, right? maximally simple and and end to end verified. Are there other questions? Okay, I will continue.

I continue a bit. Okay. So um just to give you an intuition of how it's possible to program complex um functions with this minimalistic uh ISA first uh as you may have noticed here in the instruction jump requires a boolean condition. This is again used to save commit uh to avoid committing to an auxilary column in the air.

But we can reduce conditions that are not necessarily booleans into a boolean one using only three cycles. So here here I I described it and using it we can do conditions like we can design a high level language and the compiler which naturally with blocks and you can jump to the appropriate block depending on the the condition but more interestingly it's how do you design functions because you don't have the IP register and this is the this is the key reason on why why I think we can remove this AP register. Let's say you

are here in this yellow frame and you want to call a function my function that takes as argument Y. So what first you need um to know at you know at compile time first the memory sorry the B code address of the function. So where the function lies in the back code and two the memory footprint of the function which is how much what is the s the size of the frame I need to allocate when calling this function my function of y and the key idea is that when executing the program you will receive as a hint a

pointer to a newly allocated frame. So the prover which who is running the program and generating the proof will keep track of the AP register in order to be able to hint correctly new allocated frames where the function will be will execute. But from the very fair point of view, there is no need to keep track of this AP register because you do not really care where the this new frame will be placed because we are using a read only memory. And so there is no risk of

overwriting previously written memory with this new function code. And so what you will do is that you will use here the reference instruction to write down at the beginning of your new frame your current program counter and frame pointer your argument that you want to call the function with. And in the end of the my function call, you will be able to jump back to the yellow frame to the previous context using the this PC and FP values that have that have been inserted at the beginning of this uh

green frame. And that's the key idea. You can I believe remove the AP register and using a hint because it's a read memo. That's it. Now you can do loops. If the number of iterations is known at compile time, I would suggest for performance reason to unroll the loop. And if not, you can rely on a compiler that will transform each loop into a recursive function. And this allows for so this allows for loops with an arbitrary number of iterations.

As a conclusion, what is what has been implemented and what needs to be done? A compiler has been implemented with uh the compiler is not really stable and mature but has some complex features like inlining loop and rolling function obviously condition matches constant arguments etc etc. The ZK virtual machine that has been presented here has been implemented in a feature complete way. The code is not mature at all but at least it exists. Um using both items a we recursive program has been implemented. So a program using these

four primitive instructions and the four pre-o compiles that can prove uh when we're opening uh and it works. And finally the the verification program. But unfortunately as Mitri and Thomas said um uh currently in its current form it does not rely on the real encoding top of the AP cube. More work is necessary to include this encoding. It's not uh as trivial to because it's it's a bit complicated to make it efficient with this ISA.

What needs to be done is so to include this top top of the hyper cube encoding one two to um finish the recussion program. Currently we only have weird verification which is a big part of the recursive proof but it's not all and more importantly to improve performance just to give you a number currently in it's a nonoptimized form the VM is able to perform recursion in two point to perform sorry a we verification uh so big part of the recussion in 2.7 seconds and what we need is obviously something at least 10 time faster but as

I said the VM is in its current form not optimized at all and so there are there is lot of room for improvement that's it thank you >> thank you Emil fantastic presentation as well and super impressive that uh you came up with all of these improvements over uh the the Cairo design um actually I'd be curious to get your your sense like if you were to take Cairo as it is today and implement all of the optimizations kind of move to multilinear and and some check and were and remove the AP register and implement logup star like how much faster do you think you could

make Cairo I don't want it's too hard as a question I don't know honestly it's very hard >> that's right >> I don't know care enough but uh if There are ko people in in this uh zoom. I am I would be really interested of one figure which is uh what is the time of on a standard laptop to do one recursive proof on kro on and uh it would be really interesting to know because we we can compare for instance in its nonoptimized way recussion currently costs a few seconds and so we can compare uh with the time ko um with

the time ko need for recursion on a standard laptop. >> I was going to ask what's the bottleneck there? >> There are a lot of bottlenecks. >> Not just one bottleneck. Yeah. No, no, it's uh for instance uh this figure of 2.7 seconds has been implemented has been um benchmarked on a degree 8 extension of Kabir and currently there is a work in progress to transition into smaller extension degree five or six of Kabir and so we we will get direct improvements in term of performance simply using a smaller extension field but there is like 10 todos that really

improve performance. >> Divia asks, does a recursive function in this context use tail recursion? >> Use what? Sorry, >> tail recursion. >> I don't know what it is. Sorry. >> Oh, in the sense that like uh like the call instruction is immediately followed by the right instruction. So it's like recurs >> the call from by by the right. >> The return instruction.

>> I guess there is no explicit return >> H um yes. >> And okay sorry there is no explicit return instruction indeed but there is some kind of return using this jump. Uh when you want to call a function um before jumping to the new frame, you write at the beginning of the new frame your current program counter and frame um uh and frame um pointer and so then you jump and so at the end of this new function you are able to return by jumping back on your previous context.

>> I see. I see. Okay. But I mean so you if you compile into jump instructions then you can directly implement iteration. You don't necessarily have to go via recursive >> Yes. Yes. Yes. >> Which means that a compiler has everything it needs to to transform the recursive functions into iterative ones like a a normal optimizing compiler does for t regression.

Okay, well, we're out of questions and it's perfect timing because we're just at the hour. Congratulations to the 50 people who made it through two hours of content. Uh, and looking forward to seeing you all uh on on call number eight. Thank you so much to all the speakers and have a great weekend. Bye everyone. >> Thanks. Thanks a lot. >> Thanks. Bye.