ZK Hack V Workshop: Range Checks with Polygon Plonky3

Transcript

Hey Brian. Hello. How you doing? Doing good. Doing good. Am I audible? Yeah, I hear you well. Please in the chat let us know if there's any issue, but I think it should be it should be all good. Uh, ready to talk about Plonky3? Yeah. Yeah, let's dive into it. So, can you share maybe your your screen? I will switch the screen so that you can take over the presentation. Okay, we get audible AF in the comments, so I think it should be pretty nice. Okay, I'm going to switch the screens.

Here you go. All right. Um, So yeah, again maybe I'm just stopping you before you start. If there is if there is any questions guys, feel free to post on YouTube. We will as soon as Brian, you know, find the right time, he will maybe take the questions that are popping up. We want this to be interactive, so really don't be shy. There is no dumb question. Please go for it. And yeah, Brian on your side as well, if you need anything, you know, I'm going to be in the background, so feel free to ask if need be. So, and now yeah, it's your turn.

Leaving it up to you. And yeah, see you in a bit. All right. Thank you. Thank you. All right. I'm super excited to be here. My name is Brian. I work at Polygon as a senior dev rel engineer. And today I will be presenting a little bit about Plonky3 and also just kind of dive into a hands-on example, which is range check, which we use extensively in our modern ZK inventions. Like one of the crown of jewels is the ZK VMs, right? They can't live without range check. So, we're going to dive into, you know, how to implement that using Plonky3. Um, and then just touch a little bit of different types of ranges so that you can you can understand how to optimize

your constraints so that you can use you can generate your proof as fast as you can. All right. So, Plonky3, as you all know, it's sort of it's you know, it started way back in the day starting from Plonky, and now there was Plonky2, and then now there's Plonky3. Each three it's each one of them it's quite different from one another, but its all goal is to serve sort of that the sort of framework or or back-end that people can just kind of build on top of where we provide the prover and a verifier, and people would just need to write their constraints or circuits to to to write their ZK applications.

So, for Plonky3, what sets us apart from Plonky2 is that Plonky2 was primarily focused engineered around a few Goldilocks, and it supported recursive recursive recursive proof generation. And that made it ultra fast and fast only around the Goldilocks field. But later down the road, there started to have more fields introduced to the public such as Mersenne 31 and some of the other ones as well, and different hash schemes as well like you know, it was Poseidon2 and there's Blake etc.

So, in order to support all of these in Plonky2, it means what has to you know, Plonky2 is so well optimized around Poseidon and Goldilocks field. So, it made it really hard to kind of you know, kind of just take out one of the components and then plug the new plug the new schemes inside. So, instead of doing that, we decided, "Hey, you know what? Why don't we build this sort of a modular ZK proofs a toolkit which we call Plonky3 now where you know, developers can choose their own fields, they can choose their own hash settings, and some of the other some of the minor settings as well.

There are some PRs for even trying to implement Stark in Plonky3. Um so to to make this kind of a modular toolkit where developer, depending on their applications, they can choose their settings to make a CK applications that suits their needs. So, that's Plonky3. Basically, uh I would say like yeah, it's a toolkit for designing custom CK proof implementations, and that can be used to power you know, application optimized CK VMs, CK EVMs, etc. You know, I kind of I usually use an analogy say, you know, it's kind of similar to PyTorch, TensorFlow for AI building AI models, whereas Polygon Plonky3 is there to help

build CK proof systems. So, it's sort of that toolkit or framework. Um there's a lot of So, there is this tutorial. It's called Plonky3 Fibonacci, and this is where we kind of talk about, you know, how Plonky3 works in a glance, like a TLDR version, and then showcase how to write a simple Fibonacci constraints in Plonky3. And what today what we're going to be diving into, it's a range check example, and this is where we're going to talk about the the range check implementation and some of the key I guess idea when designing a constraint, which is you know, some something called intermediate

variables. So, we're going to all talk about that today. But just quickly go through the TLDR of Plonky3. Um I guess how does Plonky3 work, right? From developers' perspective who are using Plonky3, the main steps that you need to work on is the top two parts, where you need to define your algebraic intermediate representations, which we call the air constraints, and also be able to, you know, just fill in an execution trace where constraints can kind of which we also call them as witness, right? The the execution trace, which can feed into the constraint, and then we use that to to build the polynomial,

and you know, with that polynomial, we start you know, do the polynomial commitment schemes and generate proofs, etc. All that stuff happens in Plonky2. So, as a developer, you don't have to, you know, do too much on that. All you need to really define is the constraints and generate an execution trace, which we can throw it into our Plonky2, and Plonky2 will help you figure out the rest. Yeah, it seems very complicated. I don't understand half of the steps. But, yeah, only step one and step two. So, let's take a look at this sort of, I guess, the process of, you know, process of Plonky2 generating proof

in a diagram. So, first off, we need to define our program, which is, you know, if it's a Fibonacci, then you need to define your Fibonacci programs as in, you know, how is it going to execute, you know, what are what are the each steps, is there a for loop, all that stuff. And then define your air constraints, which is which we're going to talk about in a bit, but basically means like it's defining the constraints where it needs to satisfy certain conditions for certain computations. An execution trace basically it's sort of the computation process is recording of the program the the program's execution progress.

You're you're recording the key you're recording the key variables within that clock cycle on those clock cycles. We're going to talk about that in a bit, too. And then the rest will be just Plonky 3. So you you choose your own field, you choose your own hash, and then once you have these configuration set up, then some of these ZK systems that are more of a template, but you can also customize it to to your own needs. And last but not least will be proven and verified, which is like two lines of code.

So let's quickly take a look at what are some of the fields and hash currently Plonky 3 supports, right now. So here are some of the fields that we support includes the Goldilocks field, Baby Bear field, and Anesidora. Mersenne 31 it's I think it's our latest supported fields. With that on top, we also have other hashes that we support, which I listed here. And if you want to take a look at some of the deeper examples, here are some links, so you can take a look at it. But yeah, it this repo it's it's under Plonky 3 underscore Fibonacci. Uh Yeah, maybe maybe I'll share it later.

All right. So that's just a quick run through of Plonky 3, and and overall as a developer, you know, what is it that I need to play with? What is it that I need to really work on to to make my ZK program working using Plonky 3. So let's now dive into an actual hands-on session. All right. So this is going to be the range check implementations. And today we will primarily going through three examples. One is about the Mersenne 31 range check. We're going to We're going to check whether a number is within the Mersenne Mersenne 31 range.

And then also we're going to We're going to implement another example, which is checking whether a number is within Baby Bear field range. And we're not talk We're not going to talk about the Goldilocks uh but it's pretty much very similar to how baby bear range check is done. Um but this V1 this baby bear range check V1 example that we will be showcasing is not an optimized version. So in V2 uh which we'll be talking about at the last as a last example, this will be the optimized version of the field range check for baby for baby bear field.

Uh so and then during this process we'll talk intermediate representation of that. So let's talk about range checks. So why do we need range checks? Uh range checks are fundamental operations in zero-knowledge proof systems. So because in zero-knowledge proof, you know, we don't use greater than or less than those kind of operations to to check whether a number it sits within a specific range, we have to we have to use equal signs because that's how we built the circuits.

So in order to do that, we have to we have to use this sort of a technology called range check. And during this range check what we do is essentially if given a number, we break down the number into binaries. Uh and then using those binary bits, we compare say, hey if a number is greater is less than certain bits, we make sure that the the top parts of uh of the bits are are equal to one, then the remaining should be zero. Uh something like that. Um that's this is sort of the the the idea that we're using the decomposition.

Um so we're we're going to talk about that in a bit but but yeah, that's the overall essence. Using equal sign to compare whether a value sits within the range or not. So some of the applications include, you know, the privacy-preserving financial transactions, secure voting systems, and etc. So, for this example, let's first start with the Mersenne 31, the simplest implementation of this entire tutorial series. Um the reason why it's simple, you will see it in the bit decomposition form.

All right, so let's first dive into Mersenne 31 range check. So, Mersenne 31, if you take a look at its prime its prime prime field, it's 2 to the 31st minus 1. So, this is the the biggest number, which this is what we want to make Let's say given a number, we want to make sure a number sits within this range. So, yeah, the range check ensures that the value sits less than 2 to the 31 minus 1. And for this example, we'll we'll be using field Mersenne 31, and hash will be Keccak 256, and then PCS will be circle PCS. We'll we'll talk about this Plonky2

setting in the code in a bit, but let's first get into the execution trace and the constraints. If you recall in this part, I I mentioned all we all as a developer need what need what we need to worry about is defining the air constraints and the execution trace. So, that's what we're going to be doing. All right, so let's start with the execution trace. So, we're using zero's row, and this is the execution trace is basically 4 by 32. So, zero all the way to 31, right? So, it's 4 by 32, so four rows and 32 columns, and we're using zero's row as the row to store the number to be checked. So, let's say if there's a

number that we wanted to check, what we're doing is we're breaking that number down into binary forms. So, that number has to be U32, right? Um um and then we're throwing that U32 and we're breaking down that U32 number into binaries, and then we're throwing each bits into the zero scroll of this execution trace. So, so yeah, it is stored it is stored in bit decomposition form. Um in big Indian format. You can store it in other formats as well, but it's just this is the way that I'm using it.

and the rest of the rows we're filling it with zeros. The reason why we have three extra rows is because for our circle PCS settings, um M Plucky 3 does require more than four rows. Uh so, so yeah, basically these are just empty rows. Uh we can kind of just uh ignore for now. All right. Then, so we see how the table looks like like it it looks like this. Then we just need to fill in the data so that you know, we can actually represent that table in in a vector in a matrix. So, this is the execution trace generation function. So, the idea here is we're creating a vector that has the exact numbers of elements uh

you know, total elements of this execution table. So, this execution table trace table is 4 by 32, so it's 4 * 32 uh amounts of elements. So, that's going to be uh 1 2 1 2 8. So, now we have a one-dimensional vectors, and what we're doing is just we're filling the vectors with uh the the values. Um So, yeah. Say we're given a number, a value, and what we're doing, we're breaking down number into binaries, and yeah, this is just breaking down the number and then compare with one. If it's one, then you you you push the zero uh push the one in.

Uh you know, if if you compare the bits, if it's not one, then you push in the zero. Uh so on and so forth. You After you finish the first row, that's going to be zero 32 elements. Uh and then you fill in the remaining uh elements with zeros uh for three rows. So, that's going to be 3 * 32. Uh and then you're just pushing in zero. Uh just be mindful, you're not pushing the actual number one and number zero. What you're pushing in is actually a field value. So, all the number that lists within this execution trace is actually field values, not actual values. So, just be mindful. So, you want to push in the field values And once we have, you know, uh pushed

all the values in the one-dimensional vector, what we're doing is we have this API from Ponzu tree called rage row major matrix new, and you're throwing this one-dimensional vector, and then just specify how uh specify the width of the row, and it will convert this uh one-dimensional matrix into a two-dimensional uh execution trace matrix that is usable for um when generating proofs. All right? Hey Ren, sorry I'm I'm jumping a stage cuz we have a we have a few questions in the background. So, I was thinking maybe we could we could take them backwards cuz we we have one from Philip about the the bit decomposition.

Uh yeah, maybe you want to cover this one. Oh, but the bit decomposition is not part of the circuit industry. Yeah, it's not part of it, and we will verify that bit decomposition is done correctly in the constraint. Otherwise, like, yeah, you can throw in any numbers, right? Uh if you throw in any numbers, and you if you're not verifying whether the original value is not matching with the decompose decomposition a bit decomposition result, then yeah, there's no point in generating improves. So, we'll talk about that and the constraints. Yeah, that's that's the that's a good point.

Okay, cool. I also have a bunch of questions maybe that were more related to the first part, but maybe let's let's tackle them now. So, we have this one from from Loudy. Is Plonky 3 aimed at customization or are its implementations also faster than Plonky 2? Um I think for it really depends on your applications. say if your application focuses more on recursiveness, then Plonky 2 is definitely much faster um because we we support this um but also that comes with the sort of limitation where we have to work with the Goldilocks field um and the Poseidon hash. But now that

we have like Poseidon 2 hash, which is even faster, and with Mersenne 31 um and also with circle PCS uh basically a circle PCS. So, all of these combined together, for some applications Plonky 3 is actually faster, but it doesn't have a recursive uh scheme that came comes with Plonky 3. So, as a developer, if you want to you know, build on top of such setting, then you have you will have to write your own recursive circuits. Okay, actually it's funny cuz it relates a lot with this question from Alvaro around well, pretty much uh what you're saying. Does that Yeah, does that make sense?

Uh Doesn't mean it was based on Plonkish air transition while Plonky 3 focusing on air? Yeah, so for Plonky 2, I I I can't recall too much details um but I guess so for Plonky 2, we what we supported is we actually provided people to write circuits instead of constraints. Um so there's also a synthesization portion where you have to synthesize the the the circuits into constraints, but I I I can't recall exactly what kind of constraint that Plonky2 was using. It's but it's probably not air. Uh if it's air then it could have the migration from Plonky2 to Plonky3 would have been much easier.

Um but it's some other scheme. yeah, hopefully that kind of partially answers your question, but I will Maybe this thing you can also That's typically the type of discussion we like to have on the on the Discord, so that's something we can we can check out. Okay, I'll I'll I'll jump off again. Maybe I will jump back in case I see some interesting question in the chat, so you can you can focus on your on your presentation. And I'll be back in case we have some questions, so yeah. Leaving you back to it. Yeah, I see in the comment section someone's helping out too, so I really appreciate it. Yeah.

All right, so where were we? Yeah, so so to come back, I think it was Philip mentioned this, so this is exactly indeed an important piece of, you know, constraint that we need to write. So now that we wanted to build a constraint to to make sure that the value So there are several things that we need to to make sure. So first off, we need to make sure the most significant bit is zero. Uh why are we doing this? Because if we take a look at the execution trace on the first row, um this is the largest value that we have fit in already in this execution trace, and you can see the very first column very first column is zero because, you know, the number has to be

2 to the 31 minus one. Um so yeah, just making sure as long as a number is, you know, doesn't use this first column as one, then it should be within that range, right? So so that's why we're making sure we need to make sure the most significant bits in here is zero. And then second, we need to make sure each bit that, you know, the program has fit in into the execution trace is either zero or one because we want to make sure the number that is representing is that indeed a bit decomposition is not using some random values to to fake the system. So, so yeah, this is another constraint that we need to

we need to to make sure. And then thirdly would be, you know, we need to reconstruct the value inside the circuits to make sure the value matches the inputs. This does sacrifice the the privacy portion, but for this example, this is how we are doing it. Otherwise, I will have to do the bit decomposition inside the constraints. Not what we wanted for this example. So, reconstructing value to match the input. And the input in this case, um, yeah, what what input in this case is basically a public circuit input. You can think of it as that.

And what we're doing is we're basically, you know, by converting this binary forms of numbers into U32 again and then compare it with the public input. And then optionally, this is just for the sake of showcase how to use Plonky2. We're also going to compare make sure the sum of the remaining three rows is There isn't much point of doing this, but but yeah, we're just doing this to showcase some of the APIs. All right. So, this is the constraint.

It's pretty short for this example. So, what we're doing is we first need to define the public struct of this air constraint. Uh, yeah, it's just a Rust API. You using public struct and then you have your own name. Name can be anything. Um and this is where you define your public inputs for the constraints. Um and you fit you feed this inputs in when you're instantiating the constraint instance. Uh we'll we'll take a look at how to instantiate in a bit.

So, this is the value and this will be the the number to do the range check. Uh the reason why we're throwing in again is to compare with the reconstructed value. And in here, we also need to implement a trait called basic air. And then inside here, it has a a function called width. So, this is sort of that um you know, during this uh proof generation process, it needs to it needs to know what is the width of the execution trace and this is the API that we need to we need to provide the exact value. So, 32 is the width of our execution trace.

And here, this is the constraint part. the air where we need to implement this air uh trait and then inside here, there's an API that you need to override called eval. Um and builder basically is sort of this uh iterator uh that we will be accessing. Um so, builder what it's going to return the first row what it's returning is the execution trace uh the current execution trace itself. Uh you know, where are we on which row are we on in the execution trace.

Uh and then if you do this use this row slice API and pass in the zeroth index, it's going to give you the current row. And then if you give the number that's after zero, which is one, it's going to give you the row after the current row. Um and of course, you can also access this via uh me the subscript format uh just like how you access matrix. Uh but but yeah, this is a very clean way of accessing an entire row. So, you're accessing the current row and the next row. And uh uh So, let's go through the constraints part. Now, we're actually going to go through the constraints. So, here, in Plonky3, builder has several APIs, and

some of the most used ones are called the when first row, when transition, and when last row. We don't have when last row in this example, uh but when first row, what it does is saying, "Hey, if the current row that we're on is indeed the very first row of the entire execution trace, then we're going to run this constraint." Um say, then if you're on the second row, then this uh this execution uh this constraint is not going to be be applied. So, what we're checking in the first row, we want to check if the zeroth uh bit, the the zero column of this row, is indeed zero. Right? This is the very first constraint that we are checking.

Right? And then now we're going to check each bit is either zero or one, and then also reconstruct the the the values. we have we initialize a reconstructed value by uh giving it uh a zero expression, uh number zero in uh in the field of expression, uh and then we also um this is just for the the next step, the optional part. So, we'll talk about this uh later. Uh Yeah, so so first is we access the current bit, say, we are using a for loop to access the the bits in uh every bit in the in the entire in the row

uh by doing this. And then we need to make sure that whether this bit is indeed zero or one. Uh so, assert bool is going to give you that sort of a uh give you that sort of a result where uh if a bit is you're not zero 1, it's if it's two. If a value is two, then this is this constraint is going to fail. And as simple as And now it's just basically just, you know, adding it. We're doing a bit shift, etc. Add it to the expression and then, you know, add it to the reconstructed value. And iterate that for 32 times. And then we should have the reconstructed value. Uh and last but not least, we're going to compare the

uh the reconstructed value with the public input that we have provided in here, the value. And like I mentioned, you know, since, you know, all the values that lives within execution traces field expression, so you do also have to use this API to convert the value into a field and then compare uh compare from field to field. It's not possible to, you know, uh convert field to actual uh U32 numbers, but the other way around uh is possible.

All right. So, this is when first row. with this only, uh our program should uh should suffice already. Like, it should serve the purpose of, you know, be able to prove whether a number is sits within Mersenne 31. but just to showcase the when transition API, we'll also check additionally on either zero or um making sure they're all zeros. So, what we're doing is we're creating a new uh sum variables uh and then in here, instead of adding the current row, we're adding the next row's values.

So, let's say if currently we're our iteration say the current row is here, then um I'm going What I'm going to be doing is adding the values of the next rows. And when when I'm on this row, then I'm going to add the values of the next row, uh which is this row. And that's what I'm doing here is basically access accessing the the bits and then add them to this variable here and then and then what I'm going to be doing is I'm going to check whether if the sum of the next row is indeed equal to zero.

And uh you might notice some slight difference between the when first row and when transition. So, what is going on is when transition happens when you're on let's say let's say in this example, when transitions happens when you're currently on the zeroth row, first row, and the second row. It's not going to happen on the third row. So, when transition means is basically, hey, I'm currently on this row and when I'm transitioning from this row to the next row, which means if there is a next row, then when transition will apply. And and at the last row, if you want to to do additional constraint checks on the last row, you can use you can use when last row or in this

example, how I'm doing is I'm using the the next row, which is, you know, the next row from the current row to to check. So, yeah, so because of that this constraint is only going to be applied once when it's on the very first row. But and then after the first iteration when it comes to the second row, it's going to it's not going to run this constraint and it's only it's not going to run this constraint, it's only going to run the when transition constraint for for two additional times. It's going to So, for the first time, it's going to run two of these together in the first row and when the iteration goes to the second and third row it's only going to run the when transition constraints.

So, yeah, that's sort of the constraint part where um you know, now we have the execution trace uh uh and then we have the constraints. So so from developers' perspective, the the code that they need to write is pretty much done. Uh all that is left is to write the configurations of Plonky3. Uh we'll just quickly dive in uh but not so much because I don't think we have too much time for that. But yeah, this is sort of that template that we have provided. Uh most of the time like you don't have to change too much of the setting.

Uh but as you can see, what we're using in this uh this val means the field uh the field type that we're selecting for the Plonky3 backend. So I'm just choosing Mersenne 31 um because we're checking the Mersenne 31 range check, but they don't have to match. Uh it's just an example. This could be some other field. Uh but just in this example, I'm choosing Mersenne 31 uh for the field to for the uh for the Plonky3 backend. Um and then for the hashes, I'm using Keccak uh Keccak 256 hash.

And if you take a look at and the remaining is some of the the setups for for the FRI prover uh the FRI configs which will be thrown into the Stark prover. Uh and as you can see, we can also specify what type of PCS that you wanted to use. In this case, we're using circle PCS. So this is sort of a brief intro, uh but if you wanted to dive into deeper looks of some of the other implementations, you can go to Plonky3/plonky3 Uh and then there are two examples that we have showcased so far.

Um which is the Keccak air. There's also Poseidon 2 air. Uh and if you go into these, then you'll be able to see uh these examples are basically the configurations of different fields and different hashes along with different polynomial commitment schemes to for to run the same constraint. This is basically constrained checking whether a check of hash is done correctly. And for that same constraint that you have written, you can run it in different constraint different settings and you can test them out in like one lines of code. So it's pretty handy.

All right, yeah. And so now that we have so until this point, this is where you have all of the configurations for Plonky3 from line 70 77 all the way till here line 120. And now that you have your Plonky3 set up, all you need to do is first you instantiate your air All right, which is via this. This is our constraint that we have written. This is the value that we're throwing in and then this is the execution trace. We're also providing the value here so that it can generate the execution trace correctly.

And then last but not least, we have Fiat-Shamir scheme which is generating a sequence of challenges for both prover and verifier, the same set of sequence. And then one lines of code to generate a proof and then another lines of code to verify the proof. So this is sort of just a high-level overview of a simple Plonky3 I guess prover setup and then how to verify it and also how to write your constraints and execution trace etc. All that I have written it in this example.

All right, this is the this is the constraints and then this is the the constraints implementations that we talked about and then this is the execution trace and the rest is basically the Plonky 3 instantiation and running the proof and verify. now we'll talk about the the next step, which is the the baby bear range check. Uh before that, why don't we kind of talk about how, you know, how it performs. This is the the outputs. Uh but be mindful, this is a command for running it in a dev mode. It's not a production mode. Uh you can also specify it with different flags.

By default, it's running in in dev mode. Um and what you're doing what we're doing right now is we're providing the value 100. Uh and what it's going to do is is going to generate the proof uh for 1.37 seconds. Yeah, be mindful, this is a dev mode, so it's a little bit slower. Uh and it's going to verify in 51 5.8 milliseconds. So, all these outputs is going to be showcased when you run this with this exact command. Um the code is available here, so you can take a look at this repo and then download it.

And try it on your local server uh local computer. And now we're also going to test it with the max value of Mersenne 31, which is this value, uh the 2 to the 31st minus 1. Um and it's also going to go through. So, the proof is going to work and then the verify is also going to work. And last but not least, we're going to test it with an over range value. Uh so, this number is more than what um it's bigger than the Mersenne 31 uh field. Uh and if you try to run it, uh what is going to and it's going to fail in proof generation process.

and as you can see, it it failed at a assertion of left equal right. It's because this number actually has the most significant bits of the execution trace, the zeroth column, is set as one. So, it's going to fail at that exact constraint, the a where it's checking the the zero column is zero or one. As you can see, it's one. It should be zero, so that's why it failed. All right. So, so that's for the Mersenne 31 example. Um the general I I I I I I think for the very first example, what I'm trying to really achieve here is to get an intuition of what range check is.

And also from range check, we understand how to I guess like how how to instantiate and write your Plonky2 program, all that stuff. Uh the constraints and the execution trace, etc. Now, uh we'll dive into just a little bit more complicated example. Uh it's called a baby bear range check. It's not as simple as just checking the very first bits of the number uh because the the range of baby bear range looks slightly different, slightly more complicated. Um so, yeah. We'll dive into it.

And just so you know, uh each of the examples that I'm showcasing here, your Plonky2 setting, it's they're all different from one another. I'm I'm only doing this to to showcase different, I guess, settings that you can apply for the same constraints. Uh you can also try them out with um you can also just try to change it on your own. Uh but, yeah. So, first, let's talk about baby bear range. So, baby bear range compared to Mersenne 31, it's a little bit more complicated. It is a number that looks like this. Uh it's 2 to the 31 minus 2 to the 27th.

Uh it's also uh a 32-bit prime, but the the range it looks something like this. If we represent this in a binary form, it would look something like this, where you have the most significant bit, it's also equal to zero, but you have the very first bits to the fourth bits equal to one, and remaining should all be zero. This is the largest number that uh baby bear field can represent. So, without further uh I guess I don't have to mention too much now what we're going to be doing. Pretty straightforward just like the Mersenne 31 example, we'll be creating writing our own execution trace function and also the constraints. So, let's dive into the execution trace. We

are breaking down the number into into binaries and then we're starting starting into the one-dimensional vector and then convert it into a matrix. And just so just so you know, the PCS we're using we're not using circle PCS and this two-adic fry PCS doesn't have a requirement say you have to have more than four rows of execution trace. So, so that's why we're able to do it in one-dimensional. For constraints, let's go through the requirements. So, first it's the same thing as a Mersenne 31, we need to have the most significant bits as zero. And then we have we need to check whether if the bits from first

to the fourth are all one. Like we need to make sure all of we need to check whether if all of them are one or everything else, because that's only that's only what matters. Like and then thirdly we'll be check if the remaining oops, sorry for the typo. Check if the remaining bits are zero. So, uh this happens if the second constraint is true, right? Then the remaining has to be zero. Otherwise like if we take a look at here, if the third column here is zero, then the remaining columns from from the third column to the rest can be anything.

And also say uh the only hard requirement is if the first bits to the fourth bit they're all one, then the remaining from column five to column 31 they all have to be zero. Otherwise it's going to be more than the mercy uh the the baby bear range. And then the usual stuff, we're going to check whether each bits are zero or one, and also we're going to reconstruct the value to match the public input. All right, let's dive into the constraint. So, this is a public input, and we have the execution trace with uh now we dive into the constraints. So, we're accessing the very current row, and using this current row, we're going

to check the very first condition that we have mentioned here, the most significant bit is zero. And that's what's happening here. All right, it's trying to check whether the the zero index uh uh zero column of the current row is equal to the expression zero. And this is the inefficient way, which we're going to talk about uh the efficient way in V2. Uh so, what we're doing is we're basically multiplying um the uh the first column uh element to the fifth column elements uh to the fourth column element. Uh and yeah, just we're just trying to get a product of it, and this is the that

value. And then for the remaining, what we're doing is we're just adding all them together from the fifth column all the way to the 31st column. We're adding them together, uh and we're storing it as this variable And what we're doing is uh there's a when API. So, when API is sort of like a bullying sort of like API, when this true, when this is false. and because this is one or zero, we can use it this way. Uh what we're going to be doing is we're going to check whether if the upper bits product, this value, which is the product of first column to the fourth column, if it's equal to one, which in this case when would means when true, right? And it then is going to check assert zero. It's uh it's trying to

require the remaining bits sum equal to All right. So, so, so that's sort of this magic that we're doing. The the the the second and the third constraint were all were having all of them in this one line of code. All right. And the remaining is basically uh you know, making sure every bit is zero or one, uh making sure every bit is zero or one, and then we are re-adding the reconstructed value and then compare the reconstructed value to the original value. Same thing that we did in So, now that we have done our constraints, what we're going to be doing is of course prove and verify.

So, same thing. We're going to test it with a simple number um called value 100. Uh just so you know, uh there's a little uh there's some something that we need we are going to talk about in the later V2 version. Uh but something that um what we have we have also changed some our fry config in the code. Uh there's something called a log blow-up factor. Um this is basically a result uh because we're doing multiplications of um I guess like of the different variables in the constraints, and which makes the interpolation process way more challenging. Uh so, we need to add a and which is going to and uh the more

maybe it's better to talk about it in the later section. But yeah, uh we have to add this number from one to two because we have a degree four constraint uh in our our current constraint. Degree four is because we have four variables multiplying one another. Uh so, we call this a degree four. If it if there's three variables multiplying with one another, then it's degree three. And the the constraint degree and a log blow-up factor, they're sort of interrelations of two to the end. But yeah, just just be mindful of this.

We'll talk about it in detail in the later V2 section. Yeah. And because of this, the overall resource that is requirement and also the competition complexity is going to be a is going to rise as well. Uh so, yeah, that's why we say this is an inefficient constraint. But, nevertheless, uh let's still run it. The value that we're throwing in is 100 uh for this is for the first test. And this should be and this should come out as look something like this. It has a very uh verify 1.41 ms. The proof is 9.01 ms.

And for the panic, you know, if you're curious, you can take a look at this. But, if you run it in the production mode, then it's not going to, you know, showcase this panic message. It's mostly there for for debugging purpose. And if you want to run it in the production mode, just uh add a tag called release. And it should override that. And we're we'll test it with the max number of range. Uh And as you can see, the proof time took about 1.44 second. And the verify took about 1.19 ms. And last but not least, we're also going to check with the range the over the range part.

Um which which would look something like this. All right, I just want to make sure if there's any questions. Can a custom range be used? Yeah. Uh honestly, like these are custom range. Uh I'm just using Mersenne 31 or I'm only using like baby bear range check for uh for example purposes. Like, you can build your own custom range um check it I guess constraints if you want to. Um I hope that's your question. Or are you using custom range for Plonk 3 backend?

If that's the case, uh there's only couple of uh uh fields that we we support. Like these are the fields that we support that you can plug it into a So, those are slightly different. Okay. All right. So, last but not least, we talked about the Goldilocks uh uh Goldilocks Baby Bear V1 range check. Uh we're going to skip the Goldilocks V1 range check, but it's pretty much very similar to uh to the Baby Bear V1 range check example.

So, if you want to take a look, you can take a look at it. Take a look at the source code. This one has an even worse optimization. So, yeah. So, now we'll talk about the the V2 Baby Bear range check and how to how to actually improve your constraints, right? How to make it more efficient. So, V2 introduced an optimized version with reduced constraint degree. So, first let's start dive into the constraint degree. What is a constraint degree, right? So, the degree of constraint in zero-knowledge proof refers to the highest degree of any polynomial constraint in the system.

This is a very abstract way of saying it, but like I mentioned, it's basically any of polynomial in your constraint that you have written, you know, what is the highest degree of the of your variables that exist. If if there's multiplications Let's say I have a I have a column, and I use that column to multiply itself by four times, which will look something like, you know, X to the four X to the the the the four, which will translate to degree four.

And if I multiply multiple columns, like let's say four columns or five columns to one another. So column zero multiplying column one multiplying column two multiplying column three and four. Then that one means it's going to be degree five. So yeah, that's what degree is in at least in Plonky2's constraints. Right. So how does the degree affect the proof generation process, right? The lower degree constraints generally leads to faster proof generation and smaller proof sizes as well. So this is because the prover and the verifier will need to perform fewer operations to verify the proof.

And what's the relation between the blowup factor that I talked about versus the degree, right? So degree, let's represent the degree in D, which will lead to a blowup factor by the next power of two. So D minus one. So let's say my degree is four, then the then the the blowup factor is going to be two. If my degree is five and in order to house degree five, you know, two to the two is equal to four. It's less than five. So it has to be two to the three, which is eight. So eight is more than degree five. That's why for a blowup factor for for degree five constraints, your blowup factor has to be three.

So so on and so forth. And if there's like a degree nine, well, which will result in blowup factor of four because it's going to be two to the four, which is which is 16. 16 is more than nine. So yeah, our goal in writing constraints and to to really optimize it, the idea is to try to reduce the constraint the degree as much as possible so that we don't have to increase the blowup factors. We We try to you know, keep the blow-up factor at you know, as small as possible. I think for SP1 as you can see VM, you know, they kept their entire blow-up factor to two for their massive constraints that they

have written. So, there's a lot of optimizations they have done and that's also one of the main reason they're so fast. So, yeah, just an example like I mentioned for the same column if you multiply yourself by four times, the constraint will be degree four and result in 2x blow-up. And then if it's five columns multiplying one another, degree five, which will result in three blow-ups. Right. So, let's diagnose the problem in Baby Bear V1. Why is Baby Bear V1 constraint degree degree four? And also why has to have a blow-up factor of two?

Um it's because of this line and this this product where we're we're multiplying column one all the way to column four. So, there's four columns multiplying one another, which made the which caused the problem. So, the blow-up factor has to increase to two. And in V2, what we're doing is we're using this idea called intermediate representation, intermediate variable. it's basically relying on you know, values from external outside of the constraint, but we verify that the value provided outside is correct in the circuits and the constraints and then start using it so that we're not using columns to doing

the multiplication, instead we're using public values to doing the multiplication. So, that's what intermediate variable is. So, yeah, so let's dive into the process. So, first thing same is very similar to the original Baby Bear V1. The first step and some of the third and fourth and fifth, they're all the same. The only difference is the multiplication part that we did. So, first we need to check whether the most significant bit is zero. Uh and then we'll talk about the second in a bit. Uh but let's say if the if the if the if if from column one to column four, they're all one, then the

remaining uh the sum of the remaining columns should all be zero. So, this uh this condition still applies. And we're also checking every bit is either zero or one. And also we're reconstructing the value we're reconstructing the values to match the inputs. So, now this is the hard part, right? Or wordy part. Uh but it's not very complicated uh actually. So, what we're doing is we're going to what we're going to be doing is we're going to check every bits by bits. So, we're going to check it with check the very last bits first. So, check if the product of bits three and four uh two four is one.

Right? So, what it's doing is first we're going to provide an external constraint input called A. And which we precomputed the product of bits three and four outside of the constraint. and we're providing the precomputed result as a public input just like how we're providing the reconstructed value uh the original value via the public inputs. We're also providing the the products of bits three and four uh from public.

So, yeah, provide an external constraint input A that is a product of bits three and four. And we're what we're going to be doing we're going to reconstruct the product in the constraints. Uh so, what we're going to be doing is we're uh we're multiplying bits three and four uh column uh in the constraint. And then we're going to compare if the reconstructed value is the same as the publicly provided value A. Right? And compare the product with A, the step is to ensure A is correct. So, if this passes, which means A is indeed this A, which is the public value, is indeed the same as the product of columns three and column four.

So, let's keep that in mind. And secondly, what uh what we're going to do is we're going to check if the product uh of the bits two to four is one. So, provide an external constraint input B that is the product of bits two, three, and four. All right, if if you can recall Oh, it's way too up there. Um I'm just going to do a screenshot, so that it's probably better. Yep. All right, just going to put it up here.

So, in the first step, remember uh what we're doing is we're multiplying three and four and then compare whether public input A is equal to the product of three and four. And now in the second step here, what we're doing is we're providing an external computed product, which is the the product of two, three, and four. We we precompute that externally. And we're going to also do a reconstruction reconstruction of the value in the constraint. But this time, instead of multiplying column two, three, and four, what we're going to be doing is because we have verified the product of three and four, which is A, is correct. So, instead of multiplying two, three, and four, which is going to

make the degree into three, what we're doing is where column two to the the product A, the the the public value A, which is going to keep the constraint uh degree into one. um so we have reconstructed the value uh by, you know, multiplying two to A, and then we can verify uh whether B is correct or not. And B is the public uh computed product of two, three, and four. And we're going to do the same exact thing, uh and we do we call that a C. And C is basically a product of column one, two, three, and four.

And with one, two, three, and four uh that provided publicly, and we're going to reconstruct the value by multiplying the column one to the publicly provided value B, which is the representation of two, three, and four. Uh and if it passes, then C uh is going to be correct, right? And C uh the C correct as in like C is indeed a representation of the multiplication of column one, two, three, and four. And by doing so, we kept the degree down to two.

check whether if C is equal to one or zero, uh right? If it's one, then the remaining bits must be zero. If it's zero, then remaining bit can be anything. Right? So, this is how we override or I guess like overcome this like uh degree problem uh by, you know, relying on public inputs, uh which we call intermediate variables, and we make sure the public inputs that's provided is indeed correct, and we verify we make sure it's correct via doing it in the constraints. And once they're correct, we can use them as uh a source of truth that we can rely on, and we do the additional competitions on top

of the public inputs. All right. So, let's dive into the code. So, this is the this is the constraints. And as you can see, we have provided various public inputs, which this is to compare with the reconstructed value. And these are basically the representations you know, the most significant bits you know, there's the value A, there's the value B, there's the value C. Um and this is the width. And the only thing that we kind of need we need to change is this part here.

Compared to the V1. So, first, we also need to check the most significant significant bits is zero. So, this has to pass. Uh and then what we're doing we're we're going to check whether if value A, the public key provided value A is is indeed the product of column three and column four. Column four and column three. Uh if it passes, then we're going to check the value B. And we're going to check it with the value A together. Say, you know, this is the publicly provided value B. And then we're going to convert this value B into a field expression.

And this is what it's doing. Uh and then this is where we're going to compute with the publicly provided value A. So, A multiply column two. Uh and then you compute If it passes, then we go on and compute the C and then make sure C is also correct as well in here. And last but not least, if C is equal to one, right? Using this when API that we mentioned, if it's equal to one, then it's going to run this assert zero.

If not, it's going to it's not going to run. All right. And then reconstruct the value etc. and then check whether the reconstructed value is equal to the original value. That's the same thing that we we have done three times. Right? And slight changes, I guess, you know, I just added here, but, you know, the execution traces that we're making, execution trace is the same. It's the same as before. Um, but I guess I'm just showcasing what what we're doing in externally by providing the public inputs. I guess, um, this is the bits, uh, you know, you're you're comparing you're multiplying the fourth bits and the third bits all that, and then you're providing all of these in the public inputs for your

Yeah. And prove and verify. And what we need to be mindful of here is because we have optimized the constraints, and the biggest degree that we have in our constraint is two. So, we can reduce the log blow off degree uh, down to one instead of two from the original example. Yeah, uh, I guess like this is just, uh, some of the some of the inputs, uh, so, yeah. So, I guess like that's about it for the range check example. Um, you know, you know, range checks are essential components in zero-knowledge proof systems.

Yada yada. Just a lot of stuff. Just read it. Um, but yeah, it's very important. Uh, I totally recommend to check out this repo. Uh, and then I have leave this sort of a question mark here where, you know, if you want to challenge yourself, you know, you can try to build your own Goldilocks V2 range check. Um, which the V1 version is just like the Goldilocks V1 version is just like Baby Bear V1. Um, and it's even worse, uh, of an optimization. Like it needs an intense optimizations uh, to be done. So, if you want to take the challenge, and you want to work on it, you know, feel free to work on it, and then a PR and we'd love to add your, you know,

example implementations to this tutorial for others. Yeah, I guess that's about it for the range check example. Let's see if there's any questions. There is some renewed concern around quantum computing and existing cryptography as Plonky3 is. No, it's it's hash based, it's Stark, so not really. But yeah, I I do see where where that's coming from. I think it was Google they announced it yesterday, no? thank you.

Thank you, Brad. I'm back. There was also some discussion about kind of the the origins really of Plonky3, so I don't know Yeah, I don't know if you're uh if you know about this, but yeah, we had we had a discussion from from Anna and actually the question from from last night, heart. Did Aztec make Plonky3? So I think there are like maybe some confusion about, you know, Plonk, Plonkish, Plonky. Oh, oh. Plonkish, you know, Plonk, all that, it's So Plonk is Aztec, right? Plonkish is like Halo 2, all that. Um and then Plonky2 is

um So So Plonkish is sort of a arithmetization, that kind of a scheme. And how do I compare? So Plonk is sort of a constraint system, basically, right? We talked about AIR and Plonky3 a lot. I Yeah, the name is confusing, but Plonky3 doesn't use Plonk. It doesn't use Plonkish. Right? Plonky3 uses AIR Uh, and it uses, you know, all the stark and all that stuff. Um, whereas, uh, you know, Plonk, uh, it's if you want to compare Plonk, it's it's a constraint system. You can compare Plonk to, you know, R1CS, you can compare it to Air, you can compare it to, you know, there's another thing called CCS, which

is like So, overall, I I I think CCS is sort of like overall representation that you can convert CCS into Plonk, you can convert CCS into R1CS, you can convert CCS into Air. I I think that's what CCS is. I don't know too much about it. But yeah, these are constraints. So, that's what Plonk sits in. It's sort of in that scope. Plonkish is more so, uh, you know, uh, I don't know Plonkish that well, but, um, it's sort of arithmetization process, which is, you know, if you have if you have constraints or sorry, if you have constraints, then you're converting your constraints into, you know, with the execution, you're converting into this uh, this polynomial process. And I think

that's where it sits in. Um, so so that's Plonkish. The name sounds confusing, but they're actually a little bit different. Like they they don't serve the same similar purpose. And they're not There was actually a whole a whole discussion in the YouTube comments as you were speaking. So, I actually invite people who watched the recording of this to actually check out the the comments on YouTube. That's going to be a That's going to be probably the best way to get to the bottom of it. And then the last questions before before we we close the workshop is, uh, from Rocío. So, she's asking, "You know, I'm new to Plonky. How do I get started?" So, is actually your your report that you shared maybe the best place to start with or there is something maybe a bit Yeah. So, for for us, like um, because

Plonky 3, honestly, like, uh, we encourage a lot we encourage people to build on top of Plonky 3, but also we also ask them the question, too. It's like, "Hey, it's Plonky uh do you really need what do you want to what are you trying to build? Are you trying to build a simple ZK VM are you trying to build a simple ZK program? Then maybe using something like ZK VM will be faster than learning a whole ZK back end. But if you do know that you do need to use Plonky3, then yeah, you're at the right place. So some of these tutorials that I've talked about, the Fibonacci example and the range check that I just share you. And also if you go to the the Plonky3

repo itself, we have couple of examples. I think we recently also added this Blake3 air example. So we have three examples of hash functions, the Blake Blake3, the the Keccak air and also the Poseidon 2 air. Right? If you just if you just search hyphen air, then you'll be able to see here's one Here's two second example and this is the third example. So you can take a look at how we write constraints and then also how you can convert those constraints into different Plonky3 settings to get started. Um but next year early next year we are also I'm

currently working on it. Like we're going to have a a sort of a Plonky3 zero to hero series and these two that you saw, the Fibonacci and range check are the very first is going to be the very first two chapters. Um but and then we're going to have like the look up tables, static look up tables, the dynamic look up tables, etc. Um to implement it so that you have a sort of a full range of, you know, from beginner to all the way to you know, sufficient Plonky3 developer experience using that one tutorial repo.

So yeah, that's coming along, but yeah, I don't have a good time limit for you yet because right now we focus more on after as well. So, but yeah, that's definitely going to come along. I hear you. We're going to make it as as fast as possible. Yeah, so we shared already the links to this repo that you presented today in the workshop in the YouTube comments. We will share some more info. So, people asking also where to follow you follow you on X and all. So, we will share all this information extra information in the in the Discord. So, yeah, I can see people asking who already there. But yeah, again, if you're watching the recording afterwards, feel free to hit us up in there.

Okay, I think we have Anna. Sorry, I I just did a share screen share slides. Did not realize it was going to pop right onto the screen. Yeah, it's a share. Um we I'm still actually looking for Kobe in the backstage. So, Gaylord, I don't know if you want to go help me find him. Yeah, yeah. Brian, thank you so much for this workshop. Yeah, thanks for the opportunity, you know.

Yeah, it was wonderful. And for having me, Brian. Very nice. Um I know that there's still a few kind of questions in the chat. So, if you can just maybe head over there after and just like answer for folks if they're looking for things and stuff like that. How do I answer? May I ask? Oh, just head over to the YouTube video. On YouTube. Okay. I sent it to you right now. It's so that you can All right. All right. I'll do that. I think we covered pretty almost all the questions. But yeah, if you can see anything, feel free to jump in there. That's useful cuz typically when people will watch the recording afterwards, the the comments are actually still popping up. So, that's it's nice to have this all sorted right now.

Perfect. Yeah. Thanks so much. Sure. Thanks, Brian. Thank you. Bye-bye. Hey.