Meet the Cairo Verifier

Share this post:


StarkWare recently announced the creation of a new Cairo Verifier in collaboration with Herodotus, which will enable developers to create highly customizable L3 appchains on Starknet soon.

Learn more about the Cairo Verifier, why we need it, and how the verifier is technically implemented with Raz, Product Manager at StarkWare, and Marcello, CTO of Herodotus.

Transcript:

Raz Landau:
Hello to everyone watching us at home. I can’t see how many people are there. I see a message from Lezun, or Lizan, I don’t know how to pronounce it. But I can see [inaudible 00:00:34] and Devora. Devora is in the background monitor in the chat. And we are here to talk about the Cairo Verifier. Very exciting. But first of all, maybe Marcello, you want to introduce yourself? Nice. A hundred people watching.

Marcello Bardus:
Okay.

Raz Landau:
Did it break up? No. Yeah, Marcello, introduce yourself to the audience.

Marcello Bardus:
Yeah, yeah. Sorry, I got disconnected for some reason. I had to rejoin. So, hey everyone, I’m Marcello from Herodotus. Yeah, happy to talk about the verifier today.

Raz Landau:
Yeah, and I’m Raz, I’m from StarkWare, a product manager here. I’ve been at StarkWare for a year and a little, and yeah, actually one of the more exciting projects I’ve had at StarkWare. And this is actually the second time we’re doing something like this, Marcello and myself. Last time was just audio. This time it’s also video. Who knows what we’ll have next time. Okay, so I assume the first question is what is a Cairo Verifier? But I actually want to start with, there’s even a book that is named as such. Start with the why, why are we even here discussing this thing called Cairo Verifier? And Marcello, I’ll let you start. I have my own opinion obviously, but let’s see what you have.

Marcello Bardus:
Sure. Of course verifying proofs is a pretty essential piece of whatever we do, especially at Herodotus as we generate storage proof that allow certain contracts like access historical data and also data located elsewhere. We utilize STARK for that. And of course we need to verify them somewhere. So that’s why we need this verifier. But also any other project would definitely benefit for that because, as you probably know, L3s could be also enabled by, verify a lot of other cool applications such as, for example, clients are proving can definitely benefit from use of the verifier. So yeah, that’s why it’s useful, I guess.

Raz Landau:
Yeah, yeah, I completely agree. I want to say, first, I dare you to answer the question without mentioning L3s, but now it’s obviously coupled, although there is more than that. I think you can break down the question to sub-question. First of all, why do you need a verifier? And this is pretty obvious, right? We’re doing a zero knowledge roll-ups, proofs are useless without verifying them, or meaningless you can even say. Then you can say, why do you want a, let’s say, a Cairo Verifier? Cairo Verifier is a maybe confusing terminology which you prove are STARK proofs. So it’s a STARK verifier, but it’s a STARK that has the Cairo constraints and also the layouts, which we will discuss soon. So it’s a STARK verifier specifically for verifying Cairo STARK proofs. And why do you need this? Because, well Cairo is cool. We love Cairo and specifically it’s also Turing-complete, so you can prove everything. So that means you can verify everything.
The third question is why do you need it on chain? And this is maybe something you usually look past, but it’s worth mentioning that yeah, you have, I don’t know, a C++ verifier in the Stone repo. And there’s also a Rust one written by LambdaClass and maybe others, but these are off-chain verifiers. Why do you need an on-chain one? Well, the same reason you need on-chain everything, right? You need something that’s on a chain that you can trust and ideally decentralized. So you know it’s not just trust me bro, I verify that on my computer and it works. And the last part is why do you need it on Starknet? And this is the crucial innovation I think in this verifier. And there’s a lot of words you can throw like L3s and the client side proving and whatever you want, but I think it comes down to costs.
Verifying proofs on Starknet is cheaper than doing it on Ethereum. It will be substantially cheaper. And with this cost reduction, this opens the door to a lot of other things because, before you realize this, you can always ask why not use the existing verifier on Ethereum that’s retaining Solidity? You can do app chains on Ethereum, they would be L2 and not L3. You can try doing client-side proving, but you’ll always hit this cost problem, which also hinders scalability and cool applications like gaming in the browser, provable gaming, improving game execution in the browser, and verifiable machine learning as your knowledge machine learning. So yeah, I think maybe, Marcello, tell me if you think otherwise, but I think it’s the TLDR, the one word is just costs.

Marcello Bardus:
Yeah, definitely. For sure cost is important because, at the end, even if you use some applications that benefit somewhat from client-side proving, very often it may be the case that the verification customer one completely unjustifies the use case. And this is why we can benefit a lot from the same verifier being deployed on Starknet, where the verification is much, much cheaper thanks to the properties of Starknet. Like a good example of that, I think it’s in gaming. I feel like it’s still an unexplored area, but for example, we could open some sort of state channels between users, where they can just interact between each other like exchange signatures, whatever, and then just prove it. And at the end, the verifier on-chain will just be convinced about the state transition. Which I feel is some concepts like state channels are of course a very old concept, but coupled with all the recent innovation in this space, we can actually see some production usage of that. And I’m super excited to see what the future will bring and what new things will be unlocked with this primitive.

Raz Landau:
Yeah, totally. I think Louis here in StarkWare is excited about this as well, and probably he’ll have his own Twitter space or whatever this is called, to talk about it because we’re not just on video, right? We’re on YouTube too. So yeah, I totally agree. The cost gives you speed, which gives you proving gaming and also customability or whatever, which is basically L3s, right? We can talk about L3s because they go hand in hand with this verifier. This is a very exciting area. But the main benefits for L3s, in my opinion, is being able to customize whatever you want. Again, you can try doing it on L2, it would just become infeasible due to the costs, or at least limit you at the very earlier stage.
But as I said, I think L3s are just part of the picture because you can do a lot of other stuff that not necessarily are blockchains, so not a layer per se. For instance, verifying zero knowledge machine learning, which I think is one of the more exciting innovation in this field. And I’m really looking forward to see how this turns out. And in general, I think this is just putting a verifier on Starknet and having it be much cheaper and open many more possibilities. And there’s also one use case you demonstrated, and you talked about in Denver with ZeroSync, you can say a few words about this. It just I think makes Starknet a verification layer for everything. So right now you can say Ethereum is this layer, and with Starknet being a layer like this, I think it enables much more. This is my take. And yeah, you want to talk, say a few words about what you did with ZeroSync?

Marcello Bardus:
Yeah.

Raz Landau:
Very good example.

Marcello Bardus:
So maybe let me first cover ZeroSync and then let me add on something and comment something you said, which we really liked. So ZeroSync. So for those of you who are not familiar with ZeroSync, it’s a project developed in Cairo that essentially verifies the Bitcoin consensus, like their proof of work. So basically whoever verifies that can get convinced that, hey, this is indeed a new value block on Bitcoin. And of course this is within Cairo, so whenever you run it and finally prove it, this will output you a STARK proof. But the thing is that verifying STARK proof is quite expensive. But finally with this verifier, this is possible. So effectively you can have some smart contract on Starknet that is actually aware of what is happening on Bitcoin using this techniques, which is pretty cool. Because as of today there was no trustless way, completely trustless way to convince any smart contract anywhere on Ethereum that hey, this is the latest value block header on Bitcoin.

Raz Landau:
Yeah, Bitcoin on the Starknet, as you famously said. You wanted to add another comment I think?

Marcello Bardus:
Oh yeah. So I really like what you said about the L3s being this place where you can write your logic in a very specific manner tailored for use case. I think there is something more deep to it is that I like to think of blockchain is like this global state machine. But this global state machine, why would the validator care that I made some action? I probably don’t want the entire world to know that if we’re building a game, we just care about the participants of the game being assured that hey, everything that is happening inside is valid. And then in the end we just want to settle this information somewhere. And I feel like the separation of concerns powered by STARKs is actually great. I see a lot of innovation and super happy that we can contribute to that with the verifier.

Raz Landau:
Me too. Okay, so we covered the why I think. I hope people at home agree that we made a persuasive case. Now maybe let’s say what is the verifier? I think this will be the shorter part. Marcello and I are both not marketing guys, so I think we’re both interested in the technical stuff, which we will deep dive very soon. But first let’s just make things straight and say what is a verifier, a Cairo Verifier? So Marcello, go ahead. Or maybe let me try and correct me, because you are far more familiar in this than I am. So basically we’re talking about the Starknet contracts, just one or maybe two? Is it just-

Marcello Bardus:
As of now it’s one contract, but we’re still improving some stuff and it’s a possibility that it’ll be many contracts.

Raz Landau:
No. Yeah, okay. But now it’s just the one including-

Marcello Bardus:
[inaudible 00:14:05].

Raz Landau:
… Fact registry, right?

Marcello Bardus:
Yes.

Raz Landau:
So yeah, it’s just a contract on Starknet, a singleton that gets a proof generated by Stone, a STARK proof generated by Stone over Cairo program. And verifies it, means checks that the proof actually proves the execution of this program. If not, it rejects it. And if it is, it registers what is called a fact attesting to the validity of this execution of this proof, on a component usually called the fact registry. Then it can be queried to actually assert that this proof was verified so it’s correct, and continue with whatever logic you want. The most well-known, I think, use case is updating the state of a blockchain according to the fact registry that the transition was indeed correct. But again, you can do much more. You can for example, verify the Bitcoin chain. You can also verify zero knowledge machine learning. You can also do what you guys do at Herodotus, which maybe you can say also a few words about this. But do you agree with my quick summary?

Marcello Bardus:
Yeah, I would put my best efforts to ensure that this is indeed the shortest part of this Twitter space. So what is a verifier? Oh, that’s quite of a philosophical question. I guess first we should probably iterate what STARK is and what Cairo is really about. So let me speedrun this as much as I can. So Cairo is basically an architecture like a virtual machine as well. And this comes with a constraint system that can be satisfied and proven with STARKs. But of course, as you mentioned before, proofs are useless if we don’t have a verifier. And the verifier is basically a set of operations, some logic that needs to be executed in order to actually verify this proof, and be convinced that this proof attests to what has been proven.
So now to be more practical, we developed this verifier as a smart contract on Starknet such that, on Starknet, we have some logic that is able to get convinced that hey, someone indeed properly executed this Cairo code. And this is implemented, as you said, in this model of having a fact registry. So what is a fact registry? A fact registry is basically some abstraction on top of the idea that, if we verify just some Cairo code, it doesn’t mean anything. We want to verify something, some very specific Cairo code. And also we want to verify that this very specific Cairo program, given these inputs, return these outputs. And the fact registry is basically an abstraction that makes this process developer friendly and understandable.

Raz Landau:
Your answer was much better than mine. Thank you. Cool. Anything you want to add to this part?

Marcello Bardus:
Yeah, maybe just for some context why this is also useful for Herodotus. For those of you who don’t know, at Herodotus we allow smart contracts to access historical data, as well as data located in other places on Ethereum. And one of the tricks we used to make this possible is something that we call generating and updating the historical block hash accumulator. So basically the idea is that we convince some smart contract that indeed there is a commitment to all of the block headers that ever appeared on Ethereum. And we need to basically prove the state transition. And thanks to the fact that we now have a cheap verifier that is available on Starknet, we can do this with a higher frequency. So it implies that we have lower latency.

Raz Landau:
And if you want to learn more, please, I encourage you to do so. And you can also listen to the last time Marcello and I talked, but only hear us, not see us. Okay, I think we’re good to go and move to the actually interesting part of this talk, which is how did you manage to do it? And it was quite a ride, right? We’ve been at it for I think a little over three months now, right?

Marcello Bardus:
Yeah.
Raz Landau:

And it was definitely an interesting road, not without challenges and difficulties. And there are some that I wanted to talk about specifically. I think it highlights many interesting choices you made and challenges you overcome. So let’s start with that. And let’s start with the basic because we say the Cairo Verifier, it’s actually a confusing name. It’s a Cairo Verifier written in Cairo. So it’s a Cairo Cairo Verifier. It is both written in Cairo and proves Cairo. Cairo is the most overloaded term I think in our space. And so we explained why it needs to prove, why it should prove Cairo, and also why it should be on-chain on Starknet.
But to be on Starknet, you don’t necessarily need to be written. There are two options because there are two Cairos. There is Cairo Zero, the old Cairo, and there’s the Cairo One, which we just call Cairo now, which is the newer version. And I don’t know how many people know, but there is already a Cairo Zero Cairo Verifier, which is part of the Cairo-lang repo. So the question arises and your Cairo Verifier, maybe we haven’t mentioned, is written in Cairo One. So the question arises why? Why not just take the Cairo Zero existing verifier and use this on Starknet?

Marcello Bardus:
Okay, so first of all, thanks for this Cairo Cairo introduction. It’s super useful. So maybe for some context, the verifier written in Cairo Zero is actually very useful for recursion and was a great reference for us. So now how this verifier is built. So as Raz mentioned, it’s implemented in Cairo One, but what’s important is that this verifier is designed to function as a smart contract deployed on Starknet, whereas the Cairo Zero verifier in the Cairo-lang repo, like I mentioned, it used specifically for recursion. Yeah. So now how we have achieved that. So we of course had to operate within some constraints imposed by Starknet itself, because of course, depending on where you do the computation, you’re going to have different trade-offs. So we had to, well, adjust to these trade-offs. So why we decided to do it in Cairo One, first of all. So it’s possible to deploy Cairo Zero on Starknet. Still it’s possible, but soon I don’t think it’s going to be a possibility. Raz, you tell me. I think it’s going to change in a few weeks, right?

Raz Landau:
That’s true. Yeah.

Marcello Bardus:
It won’t be-

Raz Landau:
It won’t be possible soon. I can’t commit to the exact time. But yeah, this is the technical detail, but assuming that you will be able, if you deployed it right now, it would be okay and it would live forever, assuming you don’t want to upgrade it. But I think that this is the more technical reason and there is a more in depth answer to this question.

Marcello Bardus:
So first off, this verifier within the Cairo Zero would require a significant refactor to operate within the constraints of Starknet. And also Cairo One is pretty flexible, which means that whenever there will be some upgrades to the overall STARK protocol used specifically for this Cairo interaction, it’ll be much easier to handle that in Cairo One. And good example of that is just switching the hash function. In Cairo One that was pretty straightforward and literally every week we experiment with different setups, whereas in Cairo Zero that would be quite painful as abstractions are quite costly.

Raz Landau:
Yeah, I think I can say that it’s not a trivial question. We talked and debated whether to do it in the Cairo Zero or Cairo One, but ultimately Cairo One is just a much better language and it’s much more flexible, and it’s easy to make changes like the hash function changes you did, which we’ll discuss soon. And yeah, I think ultimately this was the right call and the right way to go. Just for people at home, use Cairo One also? No, it’s just Cairo. If not for the reason that it’s probably you won’t be able to deploy Cairo Zero contracts on Starknet in the near future.
Okay. And yeah, maybe you mentioned it so I’ll add a bit on why there is this Cairo Zero Verifier. Anyway, so it’s used in the SHA in the StarkWare’s prover, in the recursive proving mechanism. So we use the Cairo Verifier, and this verifier is written in Cairo Zero because it was written quite a while ago. And there is actually a good chance the Cairo Zero Verifier will be rewritten in Cairo One. Again because Cairo One is just a much better language. Maybe, yeah, I think I was just interested, how was the experience for you to write in Cairo One in a project of this size?

Marcello Bardus:
That’s actually a great question. So Cairo One is still an evolving language. So the nice thing is that we keep seeing new features that actually significantly improve not only the performance of the verifier but also the overall developer experience. So it’s quite nice that we can have some influence of where the language is going and also the tooling. But like I mentioned, overall the experience has been great because Cairo One is just a way more flexible language than the Cairo Zero. There are also many verifiers written in Rust and Cairo One is, in some way, mimics Rust. So that was also very, very helpful. The ability to use the same patterns so that this code is very readable to other developers. Because in our opinion what really matters about the verifier is the auditability. How many people can actually understand what’s happening. Because this verifier is something that you have to put trust in it. And if it’s not auditable, and it’s written in a language that’s very hard to reason about, that’s a bad thing.

Raz Landau:
Yeah, that’s actually a great point. Yeah, it’s not your everyday program or contract. This is a one you really need working properly. And we know that we audited our Cairo Zero Verifier and it was no easy task. It required experts in crypto and the readability of this is definitely very important. I completely agree with that. And yeah, I think exactly as you said, I think I asked you this the last time we talked too because you wrote Cairo code also for Herodotus. But I think this was far bigger magnitude and it even demonstrated even more how you can affect things in the language. Just this morning I think we got a request from you for one of the features and yeah, it’s not without challenges. You mentioned tooling. Some, as you know too well, are still lacking in Cairo One, but I think we overcome this obstacle as well.
And actually I can say this specifically I’m talking about profiling tooling, which you use to keep profiling and benchmarking the verifier, and they actually progressed while you developed. So it was both challenging, but it was nice to see the progress go hand in hand. Moving on, unless you have anything to add on this?

Marcello Bardus:
Nope. Let’s move on.

Raz Landau:
Yeah, so we talked about comparing the Cairo, your verifier, which is Cairo One to the Cairo Zero Verifier. I thought it’d be interested also to compare to the Solidity Verifier on Ethereum. Because again there is one, otherwise we won’t be able to verify for instance, Starknet’s proof and state updates. And these are completely different languages and also different chains. And I thought it’s worthwhile talking about the difference. And specifically one big difference I thought is interesting is that the Solidity Verifier on Ethereum is by no means one contract. I can’t remember the exact number. I think I counted one and it’s a couple of dozens I think. And yeah, that’s something not everyone knows. And yours is just one so maybe say how come and why you did it? Yeah.

Marcello Bardus:
Okay. So this will move me to my previous point. We really believe that the verifier is something that you have to trust that should be auditable. And when something is part of across many contracts, it’s very hard to reason about it and something we really wanted to avoid in this design. Because not only it affects the overall perception and the amount of trust people will be able to put in this code, but also the speed we can move with. Because of course when everyone on the team is able to work with this, and it’s relatively the architecture is simple, everything moves faster.
So this is why we decided to go for a monolith. But maybe to defend a little bit the Solidity Verifier, one of the reasons why it’s done this way or not another is because Solidity and EVM imposes significant constraints. Which is, for example, there is a limit on the amount of code data you can pass, amount of computation you can do in one Ethereum transaction. And of course verifying a STARK is not trivial, which means that the proof very often needs to be split into multiple parts on EVM. Whereas on Starknet we don’t have the same constraints, we have different type of constraints, which allowed us to take this decision to go for a monolith.

Raz Landau:
Yeah, thank you for pointing this out. Obviously we’re not doing stuff for no reason. We’re not splitting logic just for the heck of it. Yeah, exactly as Marcello said, Ethereum poses restrictions and limitations and that’s why we decided to split the logic to be able to meet those limitations. And exactly as you said, Starknet has little less limitations or other limitations. It’s also more flexible. And I think this is also part of the collaborations and the impact you’ve had throughout this work. We understood what limitations are actually necessary, which can be relaxed, and we’re still working on it. This is specifically one challenge we’re still working on overcoming, but it’s much, I think it’s way more flexible in doing stuff on Ethereum.
And there’s always doing stuff simple is always better. So if you can, definitely. Okay, so maybe I’ll jump to a question I wanted to, or a topic I wanted to discuss later on, but it relates to the limitations you’ve mentioned, which is the mysterious bootloader program. I think some people know this, most not completely unaware, and it’s kind of a mythological creature that very few people understand truly. And they think, in this work, you come to be very familiar with it. So I think it’s worthwhile using this platform to talk about it too. And what is this thing? Why does it exist? How it relates to the limitations on both Ethereum and Starknet? Yeah.

Marcello Bardus:
Sure. So let me take a huge step back and let’s talk about one properties of zero knowledge. So one very cool thing is that in this type of protocols, the verifier doesn’t need to see everything, which is amazing because it enables use cases such as ZK roll-ups. I don’t need to see every single transaction to be convinced that this is indeed the new state and the state is valid. However, I still need to see something, for example, the previous state route and some commitments to the transactions that have been executed. And of course the same is for verifiers, and specifically in Cairo is the same for programs in general. So the verifier of course needs to see what is being executed, because why would you verify the execution of something you don’t know what’s being executed? But this can be tricky because a program can be quite big.
An example program that is pretty significant is, for example, Starknet itself, like the Starknet OS. Imagine that every time you would verify proof that transition is the state of Starknet from one state to another, you need to load the entire bytecode responsible for this audit. That would be pretty bad because it’s just a lot of bytecode, right? And this is something needs to be visible to the verifier. So in that case, in the case of Starknet to the other one verifier. So that’s pretty tricky, but thankfully there is a way to overcome this and these are bootloaders. So now what is a bootloader? Basically it’s a program written in Cairo that has a public input, takes public input, is input visible to the verifier. Takes as a public input, the hash of the program. So we don’t have to reveal the entire program. And simply as a private input would actually take the actual bytecode, execute it and say, hey, here I’m proving to you that I executed this properly and this hash actually corresponds to the executed bytecode.

Raz Landau:
I think I just thumbed down you, but I actually meant to thumb up. I don’t know. At least I saw it on my screen. I don’t know if people, did you see the bubble?

Marcello Bardus:
Yeah, I could see that. Anyways, just to…

Raz Landau:
But yeah, I interrupted you. Go ahead.

Marcello Bardus:
Just to add one more sentence to that, with the trick of using a bootloader, we can significantly reduce the verifier complexity. Because the verifier doesn’t have to see the entire bytecode and this is what the bootloader enables.

Raz Landau:
Yeah, exactly. So the claim changes to, I ran this program, which I ran a program which hashes to this hash and got these outputs instead of, I ran a bootloader that ran this program that hashes to this hash and had these outputs. Maybe it doesn’t go well verbally, but I hope other people at home got it. And again, this is how we do it for the Ethereum, for the Solidity verifying theorem as well. And yeah, just this morning we discussed about the option of hard coding the code of the bootloader and not passing it as a call data as well, to even further reduce the size of the call data that you need to send to the verifier. Because this is the major factor that it affects the call data size. And yeah, let’s see what we decide. Actually, Marcello, just before we went live, tried to explain to me another trick you found. I don’t know if maybe we will save this for last. No, you know what, I’m interested. You want to explain this now?

Marcello Bardus:
Okay, sure. So there is a limitation on Starknet. So actually one transaction can upload up to 4,000 files in one transaction. Of course STARK proofs are quite big and especially if the executed program is big, aka it means that the verifier needs to be aware of what the program is, it’s going to be a problem. But we use bootloaders. Perfect. But the thing is that every time we verify the proof, we need to upload the bytecode of the bootloader to the verifier, which is quite redundant. However, we thought of actually finding a better trick because part of the public memory is also the output of the program. So even if we put the code of the bootloader into the smart contract, we don’t have to re-upload it, but we have a lot of inputs and a lot of outputs of this program is going to be an issue.
So we thought, okay, how do we make the proof smaller? But if we cannot make it smaller, how do we overcome this limitation of 4,000 files? Actually we came up with an idea of just taking the proof and basically converting the proof into Cairo code, however that sounds. So the idea is to take the proof, split it into, for example, three parts, deploy these three parts as just some stupid hard-coded files on Starknet. And what is important, bytecode deployed on Starknet does not get committed to layer one, so there is no state diff. Yeah, basically that way what we can do, we can just call a contract on Starknet that has part of this proof, that we call again and again. And basically we don’t even need to upload the proof in the call data because we upload the proof as bytecode. So it’s kind of a dirty trick. It’s kind of gaming the sequencer, but probably it would work.

Raz Landau:
If that was too technical for people listening at home, it’s okay if you understood it then hit Marcello up afterwards and also explain it to me. No, Marcello will talk about it. We’ll see if it actually works or if we think it’s gaming the system too much and just block it. Let’s see. But moving on, maybe that was a bit too technical. Well, okay, another limitation I wanted to talk about, we talked about the call data. This is one major factor limiting the verifier, and how you develop and design its architecture. The other is obviously how many steps does it take for verification? And one thing we probably knew before, but understood all too well during the work on this Cairo Verifier, is the importance of hash functions. So Marcello, you want to say some words about this? Describe your somewhat painful experience with hash functions in the verifier.

Marcello Bardus:
So maybe to give some context first, I like to categorize hash functions in two ways, especially in the context of working with ZK. There are ZK-friendly hash functions and CPU-friendly hash functions. So CPU-friendly hash functions are the one that we use all across the web and let’s say in the normal world, such as for example, SHA like MD5, Blake, Keccak as well. That is used a lot in Ethereum. And then we have other types of hash functions that are mostly related to ZK, such as let’s say Pedersen, Poseidon, Rescue and so on. Specifically in the verifier we can, and also in the overall track protocol, we can use a combination of both. Because let’s say CPU-friendly are also called prover-friendly, whereas the CPU-unfriendly, which are at the same time verifier-friendly, they can also be using the protocol.
And basically the reason why we have these two options is because we can play with the trade-off and find a sweet spot between the prover and the verifier when it comes to verification costs and proving costs. So now for even more context, Poseidon is actually very good for the verifier because it’s easily arithmetizable. So it just doesn’t cost a lot on Starknet. That’s a basic explanation. But on the other side it’s quite expensive for the prover. So in the past we tried with proofs that just use Blake to us, which is super friendly for the prover. But the thing is that it’s extremely expensive for the verifier. And one of the main factors that affect the verification cost is indeed the hashing function.

Raz Landau:
Yeah, extremely inexpensive is very accurate. But yeah, Poseidon is apparently, not apparently, that’s not surprising. It’s a great hash function, especially for verification, also for proving. And that actually, that was also an interesting part of this collaboration. Because first of all I should say this is a configuration of the Stone prover. I don’t know how many other provers let you play with the hash function the same way Stone does. And yeah, using this extended… Stone actually used Poseidon before, but it extended the usage of it in the protocol, in the proof and as such in the verification. And that’s something that we’ve been working on. I think it started before we started working on the verifier and it takes time. But throughout the work and this collaboration, it really pushed things to production. So it ended up being out sooner than we thought. And it was a very, I think, a nice demonstration of the impact you’ve had on us basically.
Yeah. Okay. I think one last thing I had in mind is talking about layouts. Again for the interest, and I know you talked about it in Denver too. Marcello was just in ETH Denver, where he gave a talk about the verifier as well. I wasn’t there unfortunately, but I hear it was great. And I know you also used this opportunity to, again, demystify and maybe clear things out about layouts. Because again, not many people know what this actually is and how they play out in this setting. So yeah, I thought it’s worthwhile also talking about it here and how it affected the work on the verifier.

Marcello Bardus:
Sure. So maybe let’s introduce what layouts are. So layouts are effectively a combination, a set of so-called builtins. Another word, what are builtins? So Cairo is an architecture that allows you to run some computation and express whatever you can as it’s doing complete. However, certain operations are just very expensive. For example, hash functions such as Keccak. And there is a solution to this problem and this solution is called builtins. You can think of builtins as some sort of sidecar to the main CPU, that are just responsible for a very specific operation and are optimized specifically for that operation.
So that’s basically a builtin. But the thing is that when you take the CPU and then all of its sidecars, it’s going to change the way how you arithmetize the whole thing. Which of course affects both the prover and the verifier. And now how does it affect the overall thing? Well, the less builtins you use, aka the simpler layout, the cheaper is the verification and also most importantly the proving. Yeah. And what type of builtins do we have available? For sure, Pedersen. For sure we have Poseidon. We have also already mentioned Keccak, Bitwise built-in, Rangecheck, Output Pointer, Output builtin. Not sure if this should be actually classified as builtin, but-

Raz Landau:
Yeah.

Marcello Bardus:
… It is a builtin. And then I think there is this new one like Rangecheck 96, something like that.

Raz Landau:
Correct. But this, let’s put it aside for now.

Marcello Bardus:
Okay.

Raz Landau:
It’s on hush-hush. No, just kidding. So yeah, I hope that cleared things out and yeah, maybe should mention the work so far was on a layout called the recursive layout because this is the one used for the recursion, not surprisingly. Which is what, as I mentioned, the Cairo Zero Verifier is used here. But there are other layouts and the Cairo Verifier on Starknet is expected to support all layouts. There are some that are more tricky than others. There are ones that are basically bigger than others, there are more constraints. Not surprisingly, the ones that include the Keccak builtin, which is the most complicated builtin, I think it’s bigger than all the other builtins combined. And we’re trying to solve this issue also in these last few days. We have a question from the audience, but I’m not sure I fully understand it. Marcello, maybe you do. It says, at what overhead is the proof generation of the program currently running? I see by Diego. I don’t know how to pronounce the last name. I’m not sure I understand the question though. Marcello, do you?

Marcello Bardus:
I guess it’s related to what is the overhead for the prover to prove something. So it depends for sure on the chosen layout. It also depends on the amount of steps. So maybe why on the layout as we’re talking about the layouts. So like I mentioned, the layout affects the [inaudible 00:50:33] and for those of you who ever try to get deeper into STARKs, there is something called composition polynomial. And when you do the verification, you have to evaluate a few points over this polynomial. And on the prover, well, you have to do FFTs. So the less complicated this polynomial, then the faster the proving. But also you have the number of steps, which is quite significant. And finally, we already spoke about it’s the hash function, because if you go for something that is verifier-friendly, but prover-unfriendly, the overhead is going to be significant.

Raz Landau:
Yeah, we played around with it quite a bit. So Diego, I hope that answered your question. If not, maybe ask again. I think the answer was that there is no answer. There is no one answer. It depends on multiple factors as much as… Okay, let’s see if I forgot anything. We talked about Cairo or, in its full name, Cairo One versus Cairo Zero, and this monolith architecture versus Solidity Verifier’s split architecture. We also, we skipped to talking about bootloaders and why, well, you should maybe verify only bootloader proofs. I don’t know what the people at home think. We covered the hash functions. I didn’t ask you which hash function is the best in your view. I don’t know if it’s a fair question. Do you have a favorite hash function?

Marcello Bardus:
I think it’s an unfair question because it again depends on what we’re optimizing for. But if we care about the verifier, I guess Poseidon is the best.

Raz Landau:
Yeah, yeah, it’s an unfair question. I think Poseidon was really surprisingly pleasantly surprised.

Marcello Bardus:
Also, Poseidon seems to become a standard in the industry to the point where people are even harder accelerating that specific hash function, which means that it might become friendly for the prover as well, maybe in the near future.

Raz Landau:
Okay, so we’re getting the red light I think. In standups where you have a flickering light that shows that you need to wrap things up. There’s no light here, just Devora messaging us in the internal channel. So let’s wrap it up. Are there any, I don’t know, other stuff you want to mention, that we haven’t, or just general you want to address?

Marcello Bardus:
Yeah, I think that in practical terms, this verifier doesn’t really care whether we verify Cairo Zero or Cairo One. It’s mostly a question of the tooling and what Stone is able to do. In the near future it’s going to be able to do both Cairo One and also Cairo Zero. As of today, from our experience, we saw that working with Cairo Zero is still easier. However, Cairo One can also be proven.

Raz Landau:
Yeah, that’s something we’re working on right now and it’s expected I think very soon. Maybe worth mention that Cairo Zero has its advantages, namely it can be more efficient in some scenarios. But yeah, definitely. Let’s see. Yeah, if people are, first of all, I can end with saying that I’m personally very excited about this and seeing this to its very… I forgot how to say the English, but seeing it to the end, which it is coming to its end pretty soon. It will continue to evolve and upgrade it, but I think this stretch is coming to its end. And for me it’s exciting and a bit sad actually too. But for people who are listening to this and are Cairo Verifier appealed, what should they do? Do you have any suggestions?

Marcello Bardus:
Please go check our GitHub. Also join the relevant Telegram chats and feel free to reach out. Always happy to help and especially what type of ideas you guys have to utilize this verifier.

Raz Landau:
Yeah, I completely agree. I encourage you all to do so. And with that, I think we’ll wrap things up. So I want to thank you, Marcello, for coming to this talk, and for all the work that you’ve done, you and your team, and Herodotus team on the verifier. As I said, it is far from over. It’s just this part is. And yeah, it’s already, maybe we haven’t mentioned, but there’s already a contract deployed on Testnet to be deployed on Mainnet very soon. Yeah. So thank you for that and for this, and thank you Devora for monitoring chat. I think we don’t have any more questions. So yeah, I think that’s a wrap.