Rust x Ethereum Day 2023 at The Foundry SF

Francois Garillot presents on "Nova ZK Proof Verification in EVM"

I'm going to present work that's done mostly by Artem Choroshyuk and Mathieu Penchak, who's somewhere in the room.

OK, so NOVA is the reference implementation for 1 of the zero-knowledge proof protocols that have exploded in the last year and a half to 2 years.

And the general high-level idea is that they help you make proofs of stuff that

Examples include such things such as a ZKVM or executing an instruction set.

We've had a talk that exemplified 1 of those patterns today.

That is, we have papers showing a new optimal protocol for this every 3 months.

And that's going to come back as a problem.

And all the references, the reference implementations are in Rust.

And we would like to have a verification on the EVM for 1 of those folding schemes.

It is actually not that simple, because The EVM cost pattern is 1 that has a big uncanny valley

You have certain ZK rollups that are on the right here that have, for time, adopted the approach of biting the bullet of 11 million gas paid on each verification.

And then they've improved on it, ask them.

And then you have the small ZK verification, which are the GRAS 16 plume class of protocols.

Can we do something that is in the middle?

Can we do something that is in the middle, not only because we would like to, and it's an interesting research question, but also because the traditional solution to go from the extreme right of this line to the extreme left is to stock your verifier.

That is, instead of verifying a proof, you're verifying a proof that your verifier ran and said that the proof was valid.

You put the verifier inside your verifier, there should be a meme about Zibit on this slide actually, but what if your verifier changes?

I said cryptographic protocols change every 3 months.

That's not going to, If we have to rewrite this project every 3 months, this is not going to work.

So we are trying to dog food our own silly ideas.

That is, the Nova protocol, as it stands, finishes with a stock that

is not really amenable to Ethereum cost verification, we're changing that stock.

So we are ourselves not only receiving the work from the community of cryptographers that is improving folding schemes, but we're revising the cryptography ourselves to make it more Ethereum compatible.

are things such as the NOVA reference Implementation requires insanely huge public parameters.

It's also implemented on a different curve cycle than what we have pre-confined for on the EVM so the crypto is wrong, then there's a polynomial commitment scheme that has its

own problems and the combined contracts are gigantic.

the idea is we know we are going to change the cryptography to make it more EVM compatible and then solve those problems.

But this talk is not about how we solve those problems, but please do ask me after.

This talk is about how do you develop a solidity program that is chasing equality and compatibility with the rest cryptographic protocol while that rest cryptographic protocol is

And So some of those ideas are that why we are interested in this is that when

course, this improves upon some of the existing cryptographic protocols that have been used for the knowledge proof, such as Halo.

And we're aiming to change the cryptography to make it way more compatible with where Ethereum is.

You have to pass a lot of data to your verifier.

1 of the things that we do with Foundry is generating that data on the fly from the constants that we extract from our Rust reference implementations.

that allows us to create solidity contracts, implement, adding that data to the state, but

in morsels, in pieces, that allows us to really dock what the deployment of our eventual contract would look like.

For that code generation, even though our initial project is in Rust, we're using Python because this is what has given us so far the best development speed for the generation of that contract.

So you get the Python on the left and Solidity on the right.

Sadly, I have to report it's kind of the same thing for the part that I did mention a bit earlier in this talk, such as the crypto.

You remember we were on the wrong curve cycle.

So now our solidity verification has to implement operations that are for 1 side on which we're testing, not using pre-compiles, but re-implementing curve arithmetic, and on the other side, which has pre-compiles, we're reusing them directly.

But code generation in Python saved us more than the classing and solidity that would not have exemplified the cost that we would get in the final product on the EVM.

We even have some extreme data contract that access a lot of data on each iteration.

The idea, though, is that the final product looks a little bit like this.

We start from a Rust program that generates that has its own parameters and serializes them to JSON.

And we use JSON as a data interface between the Rust and the Python.

And all of the validity of our solidity deployment basically relies on that serialization pipeline, on which we really hope there aren't any bugs.

And it's a little bit sad in the sense that a lot of this is not

Where our sources in Rust, Foundry and is developed in Rust, we would really like to have nicer pipelines for accessing that data without going through Rust, JSON, Python, Solidity, 4 languages.

Most of the development for what we're doing does not happen on the setup of the protocol.

It happens at very specific moments where essentially what we're doing is static generation for a Foundry development environment.

If you are interested in extending foundry in that direction, please come to call to me after.

So general high-level summary, cross-testing the validity of a solidity verifier with a Rust initial prover program is hard.

We rely heavily on code generation, both for things like generosity, generation of cryptoperimitives and parameter data, including some of it at testing time.

And it would sure be nice to have the hooks to allow this at testing time.

Finally, what we've eventually converged to is instead of having this live generation, equipping an Anvil node with custom data contracts for the purpose of that testing.

are interested in how they could help more, please contact me after.


Speaker 0: Hi, my name is François Guerriot. I'm going to present work that's done mostly by Artem Choroshyuk and Mathieu Penchak, who's somewhere in the room.

Speaker 1: OK, so NOVA is the reference implementation for 1 of the zero-knowledge proof protocols that have exploded in the last year and a half to 2 years. And that are mostly called

Speaker 2: folding or accumulation schemes. And the general high-level idea is that they help you make proofs of stuff that

Speaker 1: you repeat over and over again. Examples include such things such as a ZKVM or executing an instruction set. We've had a talk that exemplified 1 of those patterns today. I guess which 1 it was. But the crypto is evolving very fast.

That is, we have papers showing a new optimal protocol for this every 3 months. And that's going to come back as a problem. And all the references, the reference implementations are in Rust. And we would like to have a verification on the EVM for 1 of those folding schemes.

Speaker 2: Sounds simple, right? It is actually not that simple, because The EVM cost pattern is 1 that has a big uncanny valley

Speaker 1: in the middle. You have certain ZK rollups that are on the right here that have, for time, adopted the approach of biting the bullet of 11 million gas paid on each verification. And then they've improved on it, ask them. And then you have the small ZK verification, which are the GRAS 16 plume class of protocols.

Speaker 2: Can we do something that is in the middle?

Speaker 0: Can we do something that is in the middle?

Speaker 2: Can we do something that is in the middle, not only because we would like to, and it's an interesting research question, but also because the traditional solution to go from the extreme right of this line to the extreme left is to stock your verifier. That is, instead of verifying a proof, you're verifying a proof that your verifier ran and said that the proof was valid. That's cool, right? Nice idea. You put the verifier inside your verifier, there should be a meme about Zibit on this slide actually, but what if your verifier changes?

I said cryptographic protocols change every 3 months. That's not going to, If we have to rewrite this project every 3 months, this is not going to work. We're a tiny startup. We don't have enough people to do that. So we are trying to dog food our own silly ideas.

That is, the Nova protocol, as it stands, finishes with a stock that

Speaker 1: is not really amenable to Ethereum cost verification, we're changing that stock. We're changing the cryptography. So we are ourselves not only receiving the work from the community of cryptographers that is improving folding schemes, but we're revising the cryptography ourselves to make it more Ethereum compatible. Initial obstacles that we've encountered

Speaker 2: are things such as the NOVA reference Implementation requires insanely huge public parameters. It's also implemented on a different curve cycle than what we have pre-confined for on the EVM so the crypto is wrong, then there's a polynomial commitment scheme that has its

Speaker 1: own problems and the combined contracts are gigantic. And so

Speaker 2: the idea is we know we are going to change the cryptography to make it more EVM compatible and then solve those problems. But this talk is not about how we solve those problems, but please do ask me after. This talk is about how do you develop a solidity program that is chasing equality and compatibility with the rest cryptographic protocol while that rest cryptographic protocol is

Speaker 1: a moving target. And So some of those ideas are that why we are interested in this is that when

Speaker 2: it comes to recursion, of

Speaker 1: course, this improves upon some of the existing cryptographic protocols that have been used for the knowledge proof, such as Halo. And we're aiming to change the cryptography to make it way more compatible with where Ethereum is.

Speaker 2: So I mentioned huge public parameters.

Speaker 1: You have to pass a lot of data to your verifier. 1 of the things that we do with Foundry is generating that data on the fly from the constants that we extract from our Rust reference implementations. But that data itself is too big. So now we create code generation

Speaker 2: that allows us to create solidity contracts, implement, adding that data to the state, but

Speaker 1: in morsels, in pieces, that allows us to really dock what the deployment of our eventual contract would look like.

Speaker 2: For that code generation, even though our initial project is in Rust, we're using Python because this is what has given us so far the best development speed for the generation of that contract. So you get the Python on the left and Solidity on the right. Sadly, I have to report it's kind of the same thing for the part that I did mention a bit earlier in this talk, such as the crypto. You remember we were on the wrong curve cycle. So now our solidity verification has to implement operations that are for 1 side on which we're testing, not using pre-compiles, but re-implementing curve arithmetic, and on the other side, which has pre-compiles, we're reusing them directly.

Speaker 1: A little bit of a problem. But code generation in Python saved us more than the classing and solidity that would not have exemplified the cost that we would get in the final product on the EVM. We even have some extreme data contract that access a lot of data on each iteration. The idea, though, is that the final product looks a little bit like this. We start from a Rust program that generates that has its own parameters and serializes them to JSON.

And we use JSON as a data interface between the Rust and the Python. And all of the validity of our solidity deployment basically relies on that serialization pipeline, on which we really hope there aren't any bugs.

Speaker 2: And it's a little bit sad in the sense that a lot of this is not

Speaker 1: necessary. Where our sources in Rust, Foundry and is developed in Rust, we would really like to have nicer pipelines for accessing that data without going through Rust, JSON, Python, Solidity, 4 languages. Most of the development for what we're doing does not happen on the setup of the protocol. It does not happen on the data itself. It happens at very specific moments where essentially what we're doing is static generation for a Foundry development environment.

Speaker 2: If you are interested in extending foundry in that direction, please come to call to me after. So general high-level summary, cross-testing the validity of a solidity verifier with a Rust initial prover program is hard. We rely heavily on code generation, both for things like generosity, generation of cryptoperimitives and parameter data, including some of it at testing time.

Speaker 1: And it would sure be nice to have the hooks to allow this at testing time. Finally, what we've eventually converged to is instead of having this live generation, equipping an Anvil node with custom data contracts for the purpose of that testing. Envil and Foundry have helped a lot. If you

Speaker 2: are interested in how they could help more, please contact me after.

See all Paradigm transcripts on Youtube

Rust x Ethereum Day - Nova ZK Proof Verification in EVM