From Design to Benchmarking: BLAKE Hash AIR for the Stwo Prover

Transcript

Hey everyone, I'm very exciting to be here. My name is Tav, but you can call me Stu. And I swear I thought it's a cute nickname even before I found out it's the name of the fastest prover in the world. Wait, I hope you have heard of Stu. If not, the next slide. Yeah, I need this one is for you. So Stew is Starkware, our next generation prover. It is based on circle stark. This is a beautiful math that enable efficient stark over a maren prime field specifically with p equals 2 to 31 minus one.

This prime allows for fast arithmetic and it makes two incredibly high performing high performing. Ah okay if you're out of the zero knowledge proof system proof zero knowledge world let me give you some context. So in the zero knowledge proof system the prover job is to convince the verifier that some sort of statement is true without revealing it why it is true and the verifier needs to check it with minimal effort. So in our setting the prover is two and is it is responsible to generate

a proof. To do that it uses some sort of description of the calculation called error algebraic intermediate representation but I will explain more on it on the upcoming slides. Anyway back to me. So I'm part of the engineering group at Stagwar. Specifically, I'm on the air design team. We are responsible to find clever ways to translate any statement you want to prove into its air representation.

Don't worry if you want to use two for proving. You don't need to write this translation yourself. We've already done that for you. We implemented all the necessary errors for Cairo. Cairo is a general purpose language very similar to Rust. that yet let you code anything you want to prove. But if you join me today, I guess it mean that you just like me are a bit curious to get a sense of what's going on under the wood before using it as a black box. So let you show let me show you how you can take a complex function like the Blake ash function and turn it into a set of polomials.

Let's start from the beginning. What exactly is error? So as I said earlier, error stands for algebraic intermediate representation and it basically contains all the information the prover and the verifier need or the on the computation in order to generate or verify a proof. It contains two things. The first one is the execution trace. This is a table of field element that represent the calculation steps. And the second thing is a set of polomial constraints on the columns which must be satisfied by every row in the trace. Let's just have a concrete

example. So we'll take a look about this function the split function. It is very simple. Given a 16 bit number x we want to split it into its low eight bit and high eight bits. So let's start with writing together the trace. And now I'm going to give you a rule of thumb. Every trace start with the component inputs. So if the input is X, what will be the first tracer? Yeah, that's true. X. And now the the next traces will be the calculation. And it is very straightforward. So I think you can do this as well. What will be

the next calculation step? Very straightforward. We want the lower eight bits of X and the higher eight bit of X. Okay, this is an option. I put just something more simple. But yeah, X shifted right by eight and X shifted left by eight. Yes, but not cyclic rotation, just shifting. uh but it give you the higher bits or the lower bits. Anyway, I just want to mention that this is only the recipe in the trace. The prover write down the actual values. So if I needed to calculate the split function on the

value one, I will write in the trace not me but the two the prover one or me two zero and then one and if later I was in need to calculate the split function on the value five I would write five and then zero for the higher part and five again for the lower part. So the second dimension of the table meaning the rows are actually different instances on the same com on the same computation. Now let's move for the constraints.

So let's look about this. We are taking the call two which is the lower eight bits of x and we are summing it with call one which is the higher eight bits of x multiply by two to the power of eight as you know multiplication by some fac by two to the something really okay it's just like shifting it uh to the right by eight so we actually put those eight bits and put put it in the correct value and then we said it equals to x called zero.

You probably now be just be thinking wait what we just took x split it into two parts put it together and said it equals x. Of course this constraints old like it's trivial. So here's the key point and this is an important one. The verifier never actually sees the trace. The only thing he sees is a polomial that the prover constructs for him from the trace. So if the prover filled the trace with incorrect value, it will result in with a set of polomial that misbehave and the verifier will know to reject the proof.

I don't want to get into all the start protocol magic right now. H but if you're curious, I highly recommend you to read the paper. It explains all the all the details beautifully. Anyway, back to what we are really here for. Figuring out how the air for the Blake ash function looks like. So, I will start with a quick overview. So, the Blake ash function is a cryptographic ash function very known for being secure, fast, and surprisingly kind of simple. Let's take a look. So, we have as an input two vectors. one of a state called V, one of a message called F.

Each one of those vectors are contain 16 words where each word is 32 bits. For them, we applying the run function and it results in an update state. We take those this update state along with some fixed permutation of the message. And when I'm saying fix I mean that the indices are known add according to the round number. So for example for round two it's going to be M15 then M11 and so on and so on. Again we are applying the run function and again resulting in an updated state. We goes on and on like this for n rounds where n is determined

by the specific variant of lelake being used. And the final step is the blake hash function output. What's going on in every round? So the round function is just call the g function eight times every time on a different subset of word from the input. So for example in the first call it's going to be on v1, v5, v9. You can read it. It's not interesting. Where most of the logic happen it's the g function. G takes as an input six words and modifies in place the first four using two function that's it triple sum and bitwise rotation

today I ch today today I chose to focus on the bitwise rotation because it demonstrates some cool thing I want to show you but after this talk I hope you have all the tools to build the full blake hash function myself. Yeah. So, be patient. We'll get there. You probably noticed that most of Blake is function calls. I mean, it applies the same logic over and over again on a different h shuffled uh version of the input.

Now, imagine a word where you need to write this function without using function calls. Pretty messy, right? This is why stone air designer looks like that. And for those who don't know, stone is our previous prover and it stands for stark one where stew is stark 2. H. But thanks god those those days are over thanks to stew and it's flat air design. This is us right now. Pretty cute, right?

So flatter design in one sentence mean that every component every function is proved in a different table and those table communicate via lookups. Let's have an example. So remember g from earlier that one let's start writing its trace together. So the input is oh I just gave you the answer but what what will be the first traces the input. So we have six words as an input. We're writing down to the trace. And now the first thing we want to do is we want a triple sum of a, b, and x into a.

Now let's assume that we have a different component called triple sum that enforces that the last column is indeed the triple sum of the first three columns. I put here some question mark because I don't want to dive into the full implementation. It's not the trivial but let's just say we have this component and we know that the constraints actually enforces this claim. So what I will do I will write down a to the caller g trace and add something called a lookup constraint into this triple sum component.

Lookup constraints means that the tapel a b x a tag appear in some row in the triple sum component as an input and output. Of course this this constraint encoded into polomials but I keep the math behind it for another lecture. I just want you to get the principle. We're good. Okay. I want to show you another cool usage of the lookup and this is a lookup into a constant component. A constant component is a component with trace doesn't depend on any input. It just fixed. It is known ahead. The verifier doesn't need an

rate. It can just calculate it or look at it or whatever. So imagine we have a table where the first two columns are all the possible pairs of eight bit numbers and the third column is the bitwise sore. Now let's say I'm on in another component and I want to enforce bitwise s calculation. I will just add a lookup constraint into this table. Okay, we almost ready to implement the first error. H we have all the tools to do it. I just want to start with a quick uh definition of the function. So the bit the bitwise so rotate by eight I

just chose it. H means that given two numbers each one 32 bits we want to return the bitwise saw roted to the right by eight. And this time this is a cyclic rotation. So for example if we have those number we're going to sort bit by bit with the corresponding bit. So zero or f is f zero. So zero is zero and so on and so on. Then we will take the lower eight bits and put it in the higher eight bit position. And this is the output.

Yes, we're ready. Exciting. Okay. What will be the first thing in the trace? The input. Yeah. But now that you are a grownup, I need to tell you something I've been hiding for you. And this is the fact that you can't actually write a 32 bits words into one tracel because our field element max is in two to 31 minus one. So we will need two traces in order to represent a 32bit number. And the way we are doing it is taking the lower 16 bits and the higher 16 bits. So for two 32bit word input we will have a

i and a low for a n for b i and b low. Now let's use the gun from the first scene. Remember the split function. Given a 16 bit number, we want to split it into eight bit chunks. So, and we are doing it in order for the bit wise and for the rotation. In the end, you will see. So, we split a i into a i and a i low and we split a low into a low i and a low low and so on and so on. Then we are writing the output to the caller trace and add a lookup constraint which is now an arrow. So use your imagination

and the next thing we want to do is the bitwise sort. So we want to sort the corresponding bits. So we want to saw A I I with B I I I to get C I and so on and so on. And I just want to remind you that this is a constant table. So these rows appear somewhere in the table because the first two columns are all the possible eight bit numbers per. So again we are writing the output into the color trace and add a lookup constraint into the table.

Now the last thing we need to do is the rotation. For this for this we don't have a specific component. So we're just going to do it in line. So we'll start by writing the output which is which is also a 32 bit so also two traces and now let's think together what will be the constraint on those traces. So if we take a look on the bites of output, we have CI, C high, low, C, low, C low, low, and we want to take C low low, which is the lower eight bits, and place it into the higher eight bits position and shift it all the others by eight to the right.

And now you can see the D high contains in its higher eight bits C low low and in its lower 8 bit position C II. We know a constraint constraint for that. We know this is just as before. So D I equals C low low multiply by 2 to the^ of 8 which is shifting the 8 bit value into the higher part position and summing the low parts. And we are doing the same for the low that contains C low I as is lower eight bits and C high low as is higher eight bits.

Good job. You did it. You implemented the first error yourself and now your m your mother can finally proud of you. But don't get too excited because writing errors is fun but writing an efficient error this is where the challenge begins. And when I say efficient, I mean that the we need to minimize the number of traces for the prover and we want to minimize the number of columns for the verifier. So good luck finding a suitable balance.

And now I want to show you that we at starkware know what we are doing. Let's just let the number talk. H for those who only came for the benchmark, please wake up. This is your moment. Uh so we chose to focus our optimization efforts on the Blake chain. Blake chain means that we apply the black function over and over again for end times. This is a key component in the start protocol specifically when you're ashing numerical trees. So that's why we chose to focus on that. And as you can see for n that is greater than five than 512 is still outperform the others. And this is the range we care about.

Yeah. So, thank you so much for joining my super technical talk. I'm attaching here some useful link. If you want to further explore, if someone wants to try to build the full Blake hash function, do it. You can don't hesitate to come with any question. Thank you. I was too. So, if you have any questions, just raise your hand. I'll bring the mic to you. You um nice talk. Uh I have two questions. The first one is uh why do you care about Blake 2 in particular?

It's not as far as I know a hash function that is used a lot in blockchain. So, okay, maybe it is just uh wondering. The second question is uh why do you need to split the 16 sorry the 32-bit word into a 16 bit? Yes sure you will be missing one bit because of the modular arithmetic but your constraint will still hold. So why is it so important to do the the splitting? Okay. So for the first question, so Blake is used in uh in the protocols specifically we recently changed to use the Blake because it's known for being very fast. H so we changed I think we use Posidon earlier and now we use Blake

and it's improved the performance significantly. So this for the first question but you're right in the past we didn't have a air for it. We just knew for two and for the second question because think about that that the function definition is given a 32bit number. So if you going to get a 32-bit number and the air cannot don't know how to handle it and the constraint won't hold. We can look into the math later. you need to calculate for the given input and the input doesn't know which field element are we using or something like that. So we just need to be able to calculate for any kind of input.

So this is why I answer is worried that I didn't answer all of your questions. Ah, another questions. Thank you, ma'am. [Applause] Thank you.