ZK9: Sangria is relaxed PLONK a Nova-like folding scheme for PLONK – Nicolas Mohnblatt (Geometry)

Transcript

So, yeah, I'd love to invite Nico to the stage. He's going to share with us that Sangria is relaxed Plonk. A Nova-like folding scheme for Plonk. Yay! Thank you. So, I hope 5:00 p.m. is an appropriate time to have some Sangria. It's not the kind that you might want, but hopefully you like it. Uh I'll start with a bit of a Nova view. Don't worry if you don't understand all the terms that are in here. This is kind of bird's-eye view. We're going to define them.

So, no Sangria is a folding scheme, and folding schemes were introduced in Nova. And they're like a cryptographic primitive, and they're the key to getting cheap recursion in Nova. Nova shows how to do folding schemes for R1CS specifically. What a folding scheme does is it compresses two instances of one problem into just one instance. So, let's say I solve two Sudokus. Rather than showing you the two solved grids, I combine them into one and show you that one solved grid.

So, Sangria does that, but for Plonk circuits. And actually for Plonk-ish circuits. We'll see that some of the extensions of Plonk are supported as well. The cost of doing that are similar to the cost you'd have in Nova. Uh the verifier's work, you'll see that there's two parties. There's a verifier. The verifier is constant with however many rows you have in your circuit. However, the constants are slightly worse than Nova. And we'll see why in a second. And you can think of this as a price that you have to pay for the added flexibility of Plonk circuits. Quick overview of what we're going to talk about. I'll give you some motivation. Like, why do we care about recursion? What can we do with these things? What are the best-known results?

Bit of background to get everyone to the same level. What are Plonk circuits? What is a folding scheme? And then we'll jump into Sangria. How do we actually fold these circuits? And then I'll describe sort of the tradeoffs. Like, what are the costs? How do they scale? And kind of what is the design space that we have to play with? So, going right into it, what's our goal? We want to do what we call incrementally verifiable computation. It's kind of like the formal way of saying we want to do recursion. We have this one function F that we apply many, many times.

So, you have a state S0 that goes into F. We have some like private inputs, omega zero, and that outputs a new state S1. That state S1 is then fed again into F with a new private input, and we keep going up until we've reached like N iterations. What we want to do is to have a succinct proof that some prover knows all the private values W0 to omega N minus 1, such that the final state is correct. So, the verifier should only have to see the first state, the final state, doesn't really care what happens in between.

What can we build with this? Where Why is this useful? So, it turns out if F is one cycle of a microprocessor, say, you know, RISC-V, ARM, whatever you want, this iterated approach to F is actually like running the processor. We could also do rollups with this. Um if S is the state of a blockchain, and the omegas are incoming transactions, and your function F is the transition function from one state to the next, we now have a rollup. We have a succinct proof of many, many blocks.

So, hopefully you're convinced that IVC is useful. Let's see how we do this. Um this is very similar to the diagram we just saw, but we have now this new row of proofs being carried along. Um and the question is, what happens inside this black box prover? So, we're going to have to do the function F because obviously we're our state is coming in, coming out. To update it, we need F. And we're going to have to do some extra work on the proof cuz we have a proof coming in, a proof coming out. That extra work we're going to call the overhead.

And as you can see, this overhead we pay for it at every step in our computation. So, the question is how small can we get this? And that will be kind of the defining feature in our system, like how performant this is. So, let's take a look at what's been out there already. Um, to provide this a little reminder of what we're doing. So, we have these nice things called SNARKs, which you probably know about if you're sat here. Uh, succinct non-interactive argument of knowledge. So, have tiny proofs, very short verifiers. That sounds like a good candidate, right? Look. So, we plug those in.

At every step, we take in a proof, verify the proof, and output a new proof that we did all that correctly. And this is sort of sort of the approach followed in Plonky2. It's how StarkWare do their recursion. It's what Fractal does. It's quite nice, but it's very expensive. I think Fractal has about a million R1CS constraints. Can we do better? The answer is yes. The people working on Halo came up with this idea of accumulation. So, they realized that a verifier could be split into like an easy part and a hard part. And what we do at each step now is we read the whole proof, but we only run the easy part of the verifier.

The hard part gets accumulated and deferred till the very end of all our steps, and we only do it once. So, yeah, that's what you see in Halo and Halo 2 and in this paper called uh I think proof-carrying data. I forgot the rest of the name. This is quite good. This is substantially better than what we had before, and I think Halo, the original version, works with Sonic. So, not exactly R1CS constraints, but it's about like 100,000 constraints. So, a lot better. Can we do any better? Uh yes.

This is what was then called split accumulation. So, rather than reading the whole proof as we did before, we're just going to read parts of it. So, we read just part of the proof. We do just part of the verifier, and we defer reading the whole proof and doing the whole verifier until the very end. And that's a paper called proof-carrying data without succinct arguments. So, you give up on the succinctness requirement. Can we do better? Yeah. Um This is what Nova does. They actually defer the proving until the very end.

So, at each step, you're going to take an unproven instance. You will create a new instance from actually running F. Fold that, so compress it with the running one, and you're going to have a new running instance, which you can keep moving forward. This is a lot cheaper, and it comes down to, I think, in Nova, about 20,000 constraints. Can we do better than deferring the proving? It's going to sound very hard. Um Personal opinion, I don't think so. But maybe we can get some efficiency from using a different constraint system. Maybe you can express our circuit in a more efficient way.

And this is sort of what we're trying to do here with Sangria. Instead of using R1CS, can we use Plonk? Cool. So, a bit of recap. I'm sorry for the Plonk connoisseurs. You're going to have to sit through this slide. You've probably seen this so many times. Uh there's many ways of describing this. I'm sorry if this this is not the way you usually think about it. So, what you can do is see a Plonk trace like a Sudoku. It's a grid, fixed size. Uh you will fill the cells with numbers and I have numbers in quotation marks cuz finite fields.

Um and there's a set of rules you have to follow. Some of these numbers are pre-filled because that's kind of like the problem you're trying to solve, right? So, the ones on the left that I've grayed out, we call selectors and those are fixed. The ones on the right, they're the controlled by the verifier. Whoever wants you to execute a circuit is going to say, "All right, I want you to start with 5 and 10 and run everything." Now, the rules. The first rule you have to follow is copy constraints and I've signaled this with colors. So, two squares that have the same color have to have the same values.

The second rule is a gate equation. So, at each row, this equation has to be satisfied and you see that our columns have little labels there. Finally, just tiny bit more definitions. The stuff on the left, we call selectors, the copy constraints, and the gate equation, those are our rules. The selectors and the rules define a circuit. Once you fix those, you have fixed your circuit. All the stuff on the right is what the prover and verifier get to play with. The verifier plays with the top part, the instance, the witness, uh the prover works with the witness part.

Cool. Now, folding schemes. Like, let's have a proper definition. And here I'm stealing a slide from Dan Boneh. Uh you have the link down there for his lecture which I highly recommend, the whole course actually. Um so, what is a folding scheme? As we said earlier, it compresses two instances into one. So, you fix the circuit. Important, we fix the circuit. And then we have two parties, a prover and a verifier. The prover works with two instance witness pairs.

So, it has two assignments to that grid we saw earlier. The verifier only has the top parts, two of them. Prover sends a message, verifier sends some randomness, and now the prover is going to output a new assignment to this grid, and the verifier outputs a new top part. Good. Two very important properties of the scheme. Firstly, we need completeness. So, if the first two assignments were valid, the resulting assignment has to be valid as well.

Super important, the second property, knowledge soundness. If you present to me, I'm the verifier. You present to me a valid assignment for my instance X, I know with high probability that you knew valid assignments for the two incoming instances X1 and X2. I'll say that again. If you present me with a witness for the resulting, the folded instance, I know that you know witnesses for the incoming ones. Great.

Another fun thing to notice is that this is not an argument. We're not proving anything. Prover says, "Hey." Verifier says, "Hey." And they move on. This is kind of why it's cheaper, conceptually. So, how do we do this for Plonk? So, we have on the left are two traces incoming. Everything that has one dash is from the first trace. Everything with two dashes is from the second trace. And we use what I call the cryptographer's best friend, a random linear combination. So, I have this random value R. Multiply one of our traces by R, add them together, and bam, we have a new trace.

Importantly, this thing is of the same size as the first two. So, hopefully you can have some intuition from this picture that copy constraints are preserved. If my blue squares on the left are equal, and my blue squares in the middle are also equal, then the ones on the right will be equal. Unfortunately, we can't say the same of the gate equation. Cuz our gate equation was not linear. We have this QM * AB. And that's going to, you know, put us into some trouble.

Luckily enough, Nova sort of solved this for us already. So, these are like the insights from the Nova paper. You are allowed to relax your gate equation. We'll change it ever so slightly so that we can still express anything we wanted to express, but that thing will be more folding friendly. The other thing is, for the verifier to hold the prover accountable, it can work with commitments. Commitments are also very short, so it means verifier will do very little work.

On the other hand, the prover will still work with the full trace. Right. How do we do this for Plonk? So, relaxed Plonk, and this is where the name Sangria comes from. Yeah. Thank you. Um So, the witness is still our Plonk witness as we know it, these three columns, but we now have a new column, which we call the error vector. We'll see in a second how we use it. The instance is still our Plonk instance, but we also have some scalar U. We'll see in a second how we use it.

And we have some commitments. And here this notation of like having WA in the box means I have a commitment to WA. So, I have commitments to all of the columns in my witness, and a commitment to the error. And this is our relaxed gate equation. So, you can see in blue sort of the new stuff. Everything in black is sort of our old gate. We have these U that pop up once in a while, and this E that we've added. Why do we do this? If you count sort of the number of variables in each of these terms, you'll that we're now degree two everywhere. So, Q M A1 B1 A I B I, sorry, is of degree two.

Q C had no degree, so we gave it U squared. Bam, degree two. All this stuff here that was first degree one, give it U, it's now degree two as well. So, we now have a homogeneous function. We've also added this error term, kind of a trash can. We'll throw stuff in there that we don't like. So folding. We are still going to do our the random linear combination, close our hearts. The scalars we also take random linear combinations of. And then the error we can be smart about. So, we'll keep this flexible for now, and let's see how we can be smart with it.

Now, you're going to have to trust me on this next sort of little equation. If we apply the relaxed gates equation to our final trace, and we distribute it out, we'll find that we have gates over our first trace, plus R times something big and ugly, plus R squared times uh the gates of our other incoming trace. Remember completeness? If our traces were correct, um gate goes to zero. So, gate of trace prime will go to zero. R squared gates of trace second goes to zero as well. We still have this ugly thing. How do we get rid of it?

Trash can. We bring in E. We say, all right, E is actually the two incoming E's multiplied by the right powers of R so that it can fit into gate on the left and gate on the right. And we just take out R times the ugly thing. That's it. So, how do we do How do we keep everyone, you know, honest, essentially? We'll get the prover to first compute T and commit to it. So T how what What does it look like? It depends on our gates equation, but it's always the same thing. So, that's defined in the protocol.

You commit to T, send it over to the verifier. Verifier does what a verifier does, sends some randomness. And then both the the prover and the verifier will do linear combinations. Prover does it with the actual trace, and we have our error term that we're adding very smartly. Verifier works only with commitments. And the nice thing about this is because you the prover had to commit to T before seeing the randomness, it can't try to be smart about how it forms T.

The other nice thing is the verifier has everything it needs to compute commitments to the folded witness. Right? So, the verifier never sees the the new witnesses, but it can still compute commitments to them. This is because the commitment scheme we're using is additively homomorphic. And this is sort of a a very strong requirement of these folding schemes. I'm ignoring a lot of details. Our commitments right now are not hiding. Um the verifier does some work on the public inputs as well, but that's quite cheap so it's abstracted away from this slide.

This is actually what it looks like on paper. It's pretty ugly. You can see T. Now, that's T. That's why I've not been showing it. We don't like it. Uh you can see also that our prover will be working with random values cuz we are using like hiding commitments. Ignore this. Go check out our little PDF if you're interested in the whole thing. The important question now, cuz we sort of lost track of where we were, performance. The verifier's work, which is the part we're doing in our overhead, is just adding these commitments.

In real terms, we'll be using elliptic curves, and we'll be adding elliptic curve points. We can count these out. We have five additions. Another nice thing, when we're actually doing IBC, the incoming instance is not yet relaxed. So, it won't have an error term. So, in practice, we only need four point additions. And that's it. Your overhead is four point additions. Um I'll point out though that Nova has just two point additions. A lot cleaner, because they don't need to work with three commitments for the witness. They just have one.

But now, we've gained flexibility, right? We're working in Plonk land. We can add more columns. We can change our gate equation. How does that affect our folding? So, we can deal with wider circuits. So, these are circuits where you can think of each gate as having more than two wires coming in and more than one one wire coming out. And the way you do this is just having the prover commit to an extra column of witness. Which means, if you remember before, here we'll now have like WD, let's say. So, our verifier is going to have to do one extra point addition for every extra column that we have.

Can we deal with custom gates, higher degree gates? Yes. But it's going to change how we deal with our error term. So, when you distribute the dice, you know how we had like the very nice gates plus R times something ugly plus R squared times gate, this actually gets moved away. We're going to have gates plus a lot of ugly stuff with different powers of R plus a big power of R times our gates. The nice thing is we can apply the same trick as we did before and just keep track of these ugly terms, multiply them by the right power of our random challenge, and take them out.

Again, this means that the prover will need to send commitments to each of these T values that are multiplied by different powers of R. We have one more commitment. We're going to have to do one more addition. So, that's the cost of custom gates. Uh one extra point addition per degree. That sounds pretty good. Um if we come back here, our overhead is just adding a bunch of points. The question is, is it worth it? Right? Like we're we're paying extra point additions for every column. We're paying extra point additions for every degree. What can we do with those things?

Um the answer is I don't know. And uh there's a nice design space here to explore where, let's say, if I add one column, but somehow my point additions become each 50% cheaper, maybe I won something. If I add one column and my point additions stay just as expensive, go back to Nova. Um Nova circuits, let's say that's our target, has 20,000 constraints. The most expensive thing in there is point addition, sadly. So, we're going to have to be very smart with how we design our circuits.

Uh hopefully, there are people in here who'll be interested in designing these kind of circuits. I'll finish by just mentioning some upcoming work and giving you a few comments. Um so, Sangria, as we saw, is a folding scheme for Plonk-ish circuits. And because we now have a folding scheme, we can piggyback off of all of Nova's results, which say we can do IVC from folding schemes. We can also piggyback off Supernova, if any of you are familiar with that paper, which is saying, "Hey, we can actually do IVC with different functions every time."

We're currently working on an implementation of this for standard Plonk specifically, just to show that it works, um and have a running example. Uh we're working on folding lookup-enabled traces. So, um we haven't spoken of lookup arguments. Hopefully, if you signed up and you did the application, you did a bit of searching what is a lookup argument. Um so yeah, we're looking to fold UltraPlonk. We have something that pretty much works. I don't want to make too many promises. ZK Summit 10? I don't know. And yeah, hopefully some circuit wizardry to come soon to have uh cheaper overhead and super cheap IBC.

Thank you very much. Cool. Does anybody have any questions? Okay. Uh Wait, wait, wait. We need a mic. Here, I I can get you. Let's try that. Sorry, uh I have three questions. I'll ask all of them. Um why is it not hiding and why t I didn't see the t computation. How is it not uh depending on the witness?

And then when you go to the higher degree, you have to go more back to the folding or just depend on the last fold? Thank you. So it is actually hiding. Uh just for the purpose of this slide, I was simplifying things away and you know, not talking about hiding commitments. In the actual protocol, it is hiding and the prover has to keep track of the values that it used to hide the commitments. The second part of your question was about higher degrees. The second like what what t is not depending on Oh yeah.

the witness. Yeah. Um Let me see. Why is it not? Yeah, you're very strict. Yeah. Uh because we've made our equation to be homogeneous and each of our variables is going to contribute one power of R. We are going to be able to have something multiplied by R. Um Does that Does that answer your question or Yeah, and just this slide on the on the on the higher degree if you the last one when when you when you use the higher degree gates.

Yeah. When we use the higher degree gates So what what is TD minus one? Oh, okay, each degree has a specific Exactly. We have now for each power of R we'll have a new sort of ugly T value. It is fully defined, but it really depends on what you have in your gate. So every time you define a new gate, you're going to have to compute this out and hard code it into your protocol. I saw one more hand somewhere around here. Oh, two more hands. Uh I think was you first, but All right.

Um I know Nova only through Lurk line. Have you thought of like making this a back end to Lurk? So I the implementation I'm actually working with Francois who's here and working at Lurk Labs. Yeah. And Uh if we use Supernova, what's your opinion? What's my opinion? Um This is on record. No. Um there's still a lot to be seen. I think it's a great idea. And I I would want to see benchmarks essentially.

The good thing is whatever you think about it, you can just use this, plug it into Supernova, and you have I guess super Sangria. I don't know. Naming. Yeah. Cool. I think that is it. Thank you so much for your attention.