ZK13: Arithmetization-Friendly Primes and Efficient Constraint Evaluation: STARKs on Custom Hardware

Transcript

[Music] Um so yeah this talk will be about arithmetization friendly primes and the new perspective on how to see primes uh from a hardware perspective actually and this will be one part the second part will be about efficient constraint evaluation and we'll try to merge those two parts in a nice way um yeah let's let's start immediately so yeah as I as I said two parts I first talk about the trend towards smaller primes in the CK industry. This is very that very easy to see nowadays. Um and then about this new perspective of how we actually could choose a prime if we have in mind custom hardware, custom custom

chips. And yeah, the second part, so this may all seem very very hard to actually compile to custom hardware, but actually turns out that if we have the right tools, the right software, it's not so hard to do and we'll talk about that later in the second part. So let's start. Uh, of course this slides is a with a lot of caveats and many people here may not agree with the years down but yeah let's just say that uh many years ago we mostly had those large primes in CK and we still have them for some of the use cases especially for ECC and stuff where we actually need those large primes. Um but in the last years we've seen that uh we actually go to smaller primes. So they had we we had the goldilocks prime which

is 64 bits large. Then we have these nice 31-bit primes. Uh, Baby Bear and and M31 and Koala Bear and so on. Koala Bear maybe uh not not as much used as the other two still but yeah and very recently we even go to uh one bit fields and extensions of that uh in in binos. So we see this trend towards smaller and smaller fields in CK at least where it's possible. For some proof systems of course it's not really possible to do that. So why is this the case? Why are we seeing smaller primes? Well, it's uh quite simple, but the reasons are a bit different on software and hardware. So, on software, we try to use as few limbs as possible for the primes. And we only

have those like for example 32 64-bit uh registers or word sizes. And if we have of course a large prime, we need many limbs. We need many instructions. And in some cases, it scales really badly with the number of limbs. So, it's not so good. So, we try to use smaller primes. and we then have a more efficient AVX representation. We can maybe do some things in parallel. Uh things like embedding overhead is also very nice if you use smaller primes at least for real real real use cases. That's on software on hardware is a bit different because we can do prime field multiplications natively up to some extent and with some caveats of course and the same is true for tower field multiplications in binos. Uh so there are things we can do

differently than than software. Uh, of course we have this trade-off also on hardware. Do we like prefer to have uh smaller area or do we have uh like prefer to have better latency? So there's this trade-off. Do we use katsu or do we just put in a larger multiplier? Um, but in general there are fewer in uh restrictions on hardware. So we can actually decide uh which which primes to use and which prime to build the hardware for. So how how do we choose a prime? This is yeah it's it's not not so new right uh let's just assume we arithmetize something for example a risk risk 5 so there are some properties we we need the prime to have for example we need it to support some fast entity this

could be a very normal FFT or entity or something like circle circle entity uh so in general we we try to have it higher to odacity or these other properties if we talk about for example circle entities uh we also want to have it a fast arithmetic operations and fast model reduction ction. Sometimes this refers to the number of uh of coefficients in the power of two representation of the prime. It's not always the case, but sometimes and as a bonus property so to say, we can also uh think about the power map being very low uh for a certain the degree of the power map being very low because for recursive verifiers or recursive provers uh we can then be more efficiently if we consider algebraic hashes like like rescue for

example. And then as a bonus question we can think about the embedding overhead or the arithmetization friendliness of a prime and this is something uh the first part of the talk will actually focus on. So yeah what what does this mean actually? So very simple example of course we want to have few limbs like like I said before and we want to have an embedding over it which is not too large. So as a very simple uh example, let's focus on in32 simulation which we do many times in in CKVMs and we can decide for example well we can choose 8 bit limbs, we can choose 16- bit limbs, we can even choose 32-bit limbs if we want to but we'd run into many other problems then um but let's just focus on

these two cases here. Uh and let's uh of course we need more elements if we choose a smaller limb size. Uh so how does the circuit look like? Let's just focus on uh int32 simulations. So let's let's say we use 8 bit limbs. Uh we we add two int32 uh numbers or we simulate the addition with the prime fields. And of course it means that we need for example in this case we need uh 16 elements in the trace or yeah the commitment in total if we use 8 bit limbs and we use fewer elements eight in total. If we can use 16- bit limbs, uh yeah, the carry limbs they get added or the carry bits in multiplication in multiplication it's a bit different but yeah the the the the

increase of the number of elements we need is more or less uh very similar the same. So what's the solution here? Well, it's it seems kind of obvious. Let's just try larger limbs then. Um yeah, let's consider a very like some 31 bit prime. Both of them are all three of them are reasonably fast. Let's use one of them. Um yeah, for the addition we have no problem. We run well we have at most 17 bit products we can or results intermediate results. We can still store this very final 31 bit prime field. Um the problem is the multiplication because if we simulate the entire stuff with 16 bit limbs then we run into the problem that some of the cross productducts may actually be uh 32 bits

large. So probability of that is actually uh not so low. And yeah, there's an example here on the on the bottom of the slide. And actually then we have a problem because the 31 bit field is not really sufficient for the cross product and we cannot really use this which in some way forces us to use the 8 bit limbs which is yeah which needs more elements in the trace. But the solution to that is also very simple. We just move to larger primes, right? Um actually not because larger primes are not really efficient on CPUs. Why not efficient? Well, we would need to use a 32-bit prime, even a 33-bit prime actually. And which means that native multiplications are probably outside the word boundaries on some architectures even outside the double

vert boundaries. Actually, also lazy reduction gets harder. We cannot really do nice addition chains or like small addition chains even without intermediate reductions. And all in all, it's not so good. Um, but luckily that's not what this topic is about because we actually consider custom hardware, right? So what if we just ignore the boundaries we have on the CPU and talk about custom hardware and we immediately see that the situation is very different here because if we consider a custom hardware chip where we built the hardware for the prime then if we have some prime size in bits here uh which is slightly larger of a power of two is not really a problem uh because we can build a custom circuit for the reduction uh for the addition for the multiplication

and so on. Um now of course if you if you're careful you may notice that this may actually be a problem maybe not for the compute but for the memory because it would mean that you would need 33-bit memory lanes and so on. Uh but actually there are also solutions to that. This has been done in the past where you actually slice up the memory. So, for example, you do it in parallel, use a 32-bit lane, and then in another 32-bit lane, you can store 32 bits of the 33 bit uh well, the missing bit of the other 32 uh elements. And uh just as a as an information, not an expert here at all, but apparently some FPGAs can already use 33-bit primes because they include some par bit for each bite they store. So, they actually support already

these slightly larger lanes. So yeah, what does this mean? That on hardware um again with some caveats uh there is in general a similar cost for the arithmetic for similarly sized primes. This depends a bit on the structure of the prime and so on but with some covers this is true. Um that's an implementation side. What about on the proof side? Well uh fewer limbs means fewer entities makes the commitment faster in general. uh means the trace is more lightweight and we also have a easier arithmetization which may be easier for audits for example and yeah this brings me to this term of arithmetization friendly primes so that's a concrete proposal I found it pretty quickly with a sage

script I think after 10 minutes or something just setting the properties uh below so that's a 33-bit prime um why is it called panda bear because I don't know every prime is called something with a bear and I think panda bear is not yet taken so why not Um it has a sufficiently high to audacity. I think it's uh 24 something if I'm not mistaken which is lower than some others but still uh it also fulfills this nice um condition the GCD condition. So you can use rescue for example uh with degree three power map and it even has a low heming weight for fast reduction if you if you want to do something like that.

Um actually there are better primes than this one. I I found them a couple of days ago. But so this is just an example of of of a reasonably efficient and and doable 33-bit prime. All right. So what's the what's the advantage in in practice, right? So what happens if you actually do that? Um well, so what's the setup? Uh the setup is we have two to 18 rows. We have in each row uh 16 integer in 32 multiplications. So we try to simulate those. And it's very important to note here that these are benchmarks the CPU benchmarks uh from PLY 3. So just as a comparison if we use 16- bit limbs uh we need 144 columns and we need approximately double the number of

columns if we move to half the size limbs. And we see that if we use baby bear where we can only use 8 bit limbs reasonably uh we are a bit slower than when we use panda bear. But you may think now well that's like what's the difference? It's uh like not even two seconds for the commit and less than 1 second for the proof. So where's where's the advantage, right? We changed everything for nothing essentially. Well, uh the problem is this one here. You see? So first uh this is not a really CPU friendly prime. It's really bad. Uh you need to move to U 128 for the product. Actually, we cannot use U64. And we also know that the model operator, the built-in operator is notoriously slow. So we would need some

nicer thing for that, some nicer reduction and we're currently also working on that um to do that. So maybe the fair comparison is to take this new prime and to use it with 8 bit limbs. We of course we can always go to a lower limb size. And here we see that the increased number of columns pretty precisely matches to the increased uh commitment cost and also has a a big impact on the increased proving time. And of course this is not uh like especially in the proving time this is not always the same for the for all the circuits very much depends on the circuits but for the commitment uh you can you can estimate it pretty easily. So uh yeah so uh we have done all these changes. Now let's let's

assume we have some trace table where we decided to change the prime to change the entire constraint system and uh and all of that we want to do on hardware right which is pretty intuitively pretty hard because we need to change a lot of things and we already have this chip so how do we do this and it turns out it's actually not so hard to do if you have the right tools and the right software to do that and yeah Phil we talk about that now uh thanks Marcus um yeah my name is uh Phil Hodes I'm I'm a cryptography engineer at Fabric. And so I work on the the software side. Uh um basically what we've got at Fabric uh is a a uh VPU is what we call it. Fabric's VPU that provides a whole bunch of uh custom

instructions that help us do general flexible performant cryptography. Uh and our job in the software space is to kind of bridge that gap between um you know an entire start prover or ZKVM and these individual instructions. And so there's there's some work to be done there. Um, and what I kind of want to go over is sort of a case study on how we've tackled the sort of constraint evaluation in a start table. As Marcus mentioned, there's all sorts of changes that somebody might uh decide to make. And that's the the tenuous connection between the two halves of our talk that Marcus comes in and says, "Hey, we could rearrange all these constraints." Uh, and uh, what would we do about that on the uh, on the software side? So, I've highlighted some different components of

uh, you know, maybe a Stark proof system. Uh these are the ones that I'm you know they're they're they're not in every single proof system but they're in a lot of them. Uh these things in green are a bit more fixed as as sort of components. Merkel trees ent they they don't change quite as much. Uh when when somebody comes in with changes to these they're they're not so fundamental. They're not that that dynamic. And our approach to those has actually been to write essentially assembly level uh modules that that perform these computations. and uh just they're blazing fast and they take all the advantage of the hardware that we we can. Uh but these things in orange like the startup tables essentially they're very dynamic components. Um I've been working a lot with SP1 uh and the SP1

ZKVM like enables power users to write their own to change them all the time probably find little efficiencies like Marcus is talking about and rearrange the Stark table entirely. Um, and so we need uh a better approach than just handwriting all of these things. Uh, because there's like 40 of those in uh in SP1 already. Um, so yeah, that's what I want to uh talk about a bit here. Um, and I decided that I'd use Marcus' situation of these this new uh 16- bit limb size with a new prime and the his implementation of the multiplication as a good example uh to drive this. Um, so this is Marcus' implementation on the right hand side.

Uh, using Plonkey 3's air builder. Um, so just going over some of the characteristics here, some of the details. Uh, we've got a row that's being taken from a a Stark table. Uh, we're loading a whole bunch of data from that low. These these A lows and a highs. We are computing a bunch of arithmetic on those, which essentially computes the the multiplication with the carries and and the limbs. And we're constraining them using like that's the plunky three stuff that builder.asserts assert zero. It's like this constraint needs to be needs to be uh uh satisfied. Um so this I I love plunky error builder. I think it's super flexible.

It's awesome. What this implementation lets you do uh is it lets you instantiate that builder with something that uh works as the stark prover. So when you instantiate it that way, what it does is it takes your start table which has got your trace of your multiplication table or or whatever other uh uh start table and it loads in all those values from the trace table for each row and then it does this this arithmetic calculation and it combines them when it's you say zero combines them with challenges that then compute the quotient polomial which is like the next step on in the proof. Um so that's great. Uh the other thing that it lets you do though which was critical for for my component because you know there's

again 40 of these different implementations of various things of various complexity and I don't want to go in and reimplement any of this if I'm running this uh as on our hardware. Um so what it allows you to do as well is instantiate that builder with something called a symbolic air builder. Um, and so when you do that, then instead of uh an evaluation that says like here's the actual computation, you get a uh a symbolic expression which instead of having inputs that are actual integers that we're doing arithmetic with, it has symbolic variables which sort of reference a place in a trace table. So just going over what this actually is talking about here, we've got uh one

variable at the top which is an entry from a main trace table at index zero. We've got a second variable which is an entry from the same trace table at index 2. We've got a third variable that's at index 4. And we're multiplying the first two and subtracting the second one or the third one. Um, and that corresponds exactly to here when op is zero. Uh, at index zero we've got a low, at index two we've got b low and at index four we've got clo. And our first constraint there is a low time b low minus clo. So it actually takes this and automatically builds this you know recursively defined uh uh symbolic expression and this this is super critical for making something

that's handles this in a dynamic way. Um so the first step for me when I was tackling this was convert this into a portable uh definition. Um and that's what this definition looks like. I'm not going to go over too much the detail here because uh it mostly represents the same thing from above uh from the previous slide, but it is um just a bit more flexible. Um full credit to this format to uh Bobin who I believe is at Miden now uh because he kind of gave us 99% of this and and that's essentially what we're using. But basically there's some metadata that says what field that you're using and there's some uh details of like variables that you can input into this and uh the characteristics of

the traces that you're going to use. Um but what it specifies is essentially is that same representation is like how do I calculate the constraints for this stark table. Um and it does so using this list of nodes. Um, and then there's a list of expressions that reference the nodes uh that says like this is the node that I'm interested in the output for. The nodes have like constant type or uh trace type which is an input from a trace table or uh operation types like multiplication on the bottom over there. And again, you know, we've got a trace input at column offset zero and a trace input at column offset two. And we're multiplying those two things together.

Same as before. That's a low time bo. So we convert into this. It's a JSON file. It's nice and portable. And uh instead of looking too closely at this and trying to make sure everybody's on board with that, I have a nice visual representation of it, which you can't read the details of, but you don't need to um because it's pretty big. And the reason it's so big is because there is actually uh in his implementation, there's uh uh eight multiplication operations per row of the trace table, and the same three uh constraints are applied to each of those eight. And so you end up with 24 little blocks here of the same uh three constraints eight times. And the reason that there's not 24 outputs is because this actually um

includes the next step of folding in the challenge values. So the colors on here, the green inputs uh the green uh boxes are trace inputs. They're inputs from a trace table. The yellow boxes, which you can hardly see, are um there are challenge values, powers of a of a challenge alpha that get folded into the constraint evaluations. And then the blue boxes are the actual uh operations like multiplication and addition. Um and then the output right there at the top is the single value. So if I've gone too fast, the the summary here is that this is a specification of his start table and the constraints that need to be evaluated on it to get the quotient polomial and it's a big pile of

arithmetic on a bunch of input values that needs to be evaluated on every row of the stark table say some 2 to the 20 rows. Um and so that's that's really nice. It's a specification of a program that tells you exactly what to do and it's like broken down into essentially inputs and multiplication and addition. Uh and that's the kind of portable definition that we need to make it easy to uh build a compiler and that is um basically what we did. I'll mention that uh I as I was working on this there's like I keep seeing related things popping up. I think I read a blog post from Inganyama a couple months ago that basically described this similar process is like plunky 3's air builder lets you get these symbolic representations and

then you can use that as a front end for whatever kind of backend proving system you want. And this is great for us in order to uh go from an implementation in Rust to something that we can pile onto our VPU. This is exactly what we need. Um yeah, so what does that look like? I said we built a compiler. Uh we we did. Uh there's a lot of details that go into that and I'm not the one who wrote the compiler, but what a compiler looks like for this kind of special problem. Uh when our target is our custom hardware, our VPU, uh that depends on the architecture of the VPU. So that's what I'm going to describe just at the the

highest possible level. This is an actual diagram of some type of uh our chip. And one of the main characteristics of it is that there are 40 individual VPU tiles. And each one of these tiles is is basically identical. Um, and they are capable of doing uh a lot of arithmetic. And it has access to those uh performant cryptography instructions. You know, some of which for example, the most simple example is that there are like 24 wide vector modular arithmetic instructions. So those can just absolutely rip through simple modular arithmetic. Um, and so that's essentially what the compiler uh needs to do like that that entire pile of arithmetic that I was describing. Uh,

every single row of this the stark table is fully independent in its uh computations essentially. So this compiler says well I I know what the arithmetic that needs to be done is. I need to compile this into a program and I need to split it up in 40 batches to send one batch to each tile and I need to have each tile uh go through 24 at a time, load these into vectors and just rip through that whole calculation. Um and of course when somebody comes along and says uh well how about you just use a different number of limbs and completely change the constraints. Well, I can then just send things through the same pipeline that I've just described and I don't even need to know what the constraints look like because we can just generate this portable definition um and compile it to a performant VP mod

module. Yeah. Um, one other thing to mention is that we so we've done this specifically from Planky 3's air builder, but really the easiest part of that whole process is converting planky 3's symbolic representation to a generic one that we use as an input. Um, so as long as there is a symbolic representation of a constraint system for a start table in any system, we can use our same pipeline to do uh the exact same thing. Okay, so overview of the whole talk with disjoint two disjointed parts is uh is basically that we want to encourage people to not just think about what hardware they can use for their cryptography but also how you can design your cryptography with specific hardware

uh in mind at the uh at the sort of protocol design stage and more specifically that that we might have uh chosen between different primes uh based on you know arithmetization friendliness or hardware friendliness and sacrificed one or the other, but that we might not actually have to depending on what hardware you consider. Uh, and also that custom hardware uh provides can provide very straightforward and flexible uh acceleration of Starks in different provers um as long as you have the right tools and that that's what we're doing in the software space at Fabric is we're trying to build those right tools that apply to many different provers. Thanks everybody.

Great talk. Um, was this investigation primarily driven by INT32 like multiplication and did you guys like profile other instructions as well? uh yeah it was primarily driven by in32 stuff and primarily what the CKVM is or some CKVM is doing we didn't profile other stuff so it's uh very true that for some circuits which do not really exploit IN32 as much it's uses to do yeah so my my basically question is you have entity as an example which does butterfly does multiplications but none of this kind of translates one-on-one when it comes to hashers like poson hash or I don't know whatever hash you want to do you're not really having as many multiplications

you are doing sores and different things. So like how does what's your feeling how this whole thing works in favor of hashing? I I think if you if you do plain hashing for like if you use rescue person you don't have any because you don't do int you do like you're already native in the prime field you don't need these tricks right um if you use the hashing for the commitment and that this can be like shock doesn't have to be poss or after the entity after the inverse entity actually forward entity for uh you are slightly faster but that's I think dominated anyway by the number of rows. So it's yeah not a huge

difference there. Yeah. Um I was curious about kind of the same question like basically what proportion of maybe more realistic examples actually includes like how how much arithmetic. Um and uh I think I looked in SP1 of the larger examples they have built in just ran it and I was like which which start tables are actually filling up which ones are larger and uh arithmetic and and multiplication in general were a larger portion than I expected. I don't remember exactly. It's a very informal sort of look but uh that convinced me enough to be like okay I think this is this would provide some significant benefit.

[Applause]