zkStudyClub - Succinct Arguments over Towers of Binary Fields (Ben Diamond & Jim Posen, Ulvetanna)

Transcript

Hello everybody and welcome back to another edition of ZK Study Club. Today we're very excited to have the Ulvetanna team presenting Binius, SNARKs over binary fields, and we have Ben Diamond who's going to be leading the presentation. We have Jim Posen also here as well who's going to be helping answer questions. Uh Ben, Jim, thank you for being here and uh Ben, go ahead and take it away. Cool. Well, thanks for having me. Glad to be here. And uh glad to present about Binius, SNARKs over binary fields. As you said, this is a joint effort by Ulvetanna. Um and will be presented by myself, Ben Diamond, and with collaboration from Jim Posen.

So, um just to sort of start to get into things, um I I I can say a few words about the landscape of SNARKs uh that we are stepping into. Uh just a few rough remarks. Essentially, you can you can write down a rough categorization of modern SNARKs into two categories. The uh first uh depends on elliptic curves. So, these tend to have extremely small proofs, say constant size, and very cheap verifications, say constant time. And um for the prover, of course, they're slower. They tend to have trusted setups and depend on um either discrete log type or so-called

knowledge of exponent assumptions. Uh as for aggregation, they do allow certain kinds of folding, often depending on cycles of curves. Um the primes over which arithmetization happens are large. They're the scalar fields of elliptic curves on the order of 256 bits. And um the bottleneck is computation. Um I can point to a second category that's been become much more prominent in the past couple years that we could call starkish protocols. So, these depend on uh only on hash functions and typically error correcting codes. They tend to be sort of

unconditionally secure in the random oracle model. Um subject in certain cases to um coding theoretic conjectures, but um not all. Many cases um no conjectures. Uh the proofs are larger on the order of 100 kilobytes. Obviously slower to verify. Um much faster for the prover. Uh there's a recursion story that is sort of simpler in that the field you use to arithmetize the recursion can be the um the same field that you used to uh generate the the inner proof.

Um supports more flexible types of fields like small fields on the order of um 64 or 32 bits. Um and um And what we found at Ulvetanna implementing many things is that um actually bandwidth turns out to be more of a bottleneck than computation is. So, specifically the problem of physically moving the data, say the witness or some kind of trace from a host into a device like an FPGA, uh becomes actually more costly and time-consuming than the actual computation. This is just because they're much more computationally cheap.

So, the bottleneck turns out to be something else. Um so, what can we say holistically about the landscape? Um For example, we live in a world where recursion is practical and is used routinely in deployed systems today where uh the Poseidon hash, so as a sort of byproduct of this, Poseidon, which is a sort of prime field algebraic hash, has become standard. This is because uh it it's sort of more uh arithmetization friendly than classical hash functions are in the prime field setting. So, we'll come back to this.

Um and also look up arguments are now, especially with uh the advent of Lasso, and we'll say more about this, too, are becoming more practical uh relative to the other components. And um this also is important for us because it allows us to um efficiently deal with things like unsigned integer multiplication, which has been or or would have been in the past cited as a reason not to use binary fields, but that reason is no longer applicable. So, um we'll get to all this in in due time. Here's a diagram of of a of a live deployed uh SNARK system today. This is due to Polygon. You can see that there's all sorts of, you know,

batching, recursion, sort of multiple levels of recursion, things like that. Okay, so just a few more remarks about current SNARKs. So, um here's a breakdown of of the Polygon ZK EVM prover. You can see that Merklization is essentially the dominant cost, although not by uh too much. Um This essentially entails hashing a giant matrix column-wise using Poseidon. Um we uh can point out that Poseidon is significantly slower, actually this 5x, I think, is more like 9x or more slower than Keccak is on a CPU. Um There is a further phenomenon called embedding overhead, which has many sort

of guises, but one that I can point to now is this idea where you have a circuit whose wires, in principle, could take values up to, say, 64 bits large, but where in actual practical use by an honest prover, they um take only zero or one value, right? So, for example, Starkware's Keccak circuit has um a a bunch of columns, around 2,500. Of those, the vast majority end up only actually being either zero or one during honest proofs.

So, this is obviously a source of waste. Okay so with all this in view, can we do SNARKs over the smallest possible field, namely F2? And again, the the two rough reasons why we want to do this you know, very uh roughly are first of all to to lessen the amount of data we have to send. So, if the information content is only bits, uh we don't want to be sending um 64 bits sort of of of of of logical data uh of physical data per sort of in bit of information.

Um and also um can we can we reduce computation? Um So, just a very brief um historical uh remark, uh so binary field SNARKs have been brought up before. The the original STARK paper by um Ben-Sasson, Bentov, Horesh, and Riabzev uh was actually written over binary fields um as was FRI and a and a few other things. So, very roughly, um there are some things that work sort of out of the box already in binary fields. For example, there is an NTT uh replacement or analog in the binary

setting. Uh this is so-called the the additive NTT. So, this is due to Lin-Chung Huang 14. Uh FRI, of course, does work for binary fields perfectly well. In fact, the original uh FRI paper wrote uh wrote the protocol in the binary field setting. Um So, certain things don't work um sort of naively, right? The most obvious one is this idea that um in deep Ali style protocols you have a sort of multiplicative trace domain and you have this way for the verifier to algebraically sort of iterate through this domain essentially multiply by a multiplicative generator of this um

of this domain. It is not clear what the analog of this should be in the binary field setting. So here if your domain is say an additive subgroup of your binary field there is not any obvious algebraic operation um whose action on this domain sort of iterates you through it. There there's something sort of that kind of looks like this in hyper plank um which we'll come back to. This turns out to be not quite enough but we will have more to say.

So second major thing and and we'll come back to this too is that Reed-Solomon codes need to have a large alphabet. So the alphabet needs to be as big as the block length is. Um this prevents you from writing down say a binary Reed-Solomon code whose alphabet is just F2, right? It just doesn't exist. So what you end up finding in practice is that in order to use Reed-Solomon at all you need to do some kind of embedding where even if your message has coefficients that are just zero or one um you need to sort of tacitly embed those into say F2 to the 16 before Reed-Solomon even makes sense. And of course your codeword will not have bit uh components anymore. They'll be F2 to

the 16 elements. So that's like a 16-fold blowup in your size. Um maybe we can use breakdown with a true binary code with alphabet actually F2. Uh this turns out to have its own problems. So in short it's not quite so simple a picture of of whether we can make this work. We do make this work by essentially answering these questions. So, we we'll get into how we do that. Okay, so so that essentially concludes the introduction and technical sort of historical remarks.

Looking uh forward um this begins the actual sort of content. Um I can tell you uh what's what's coming ahead is essentially so I'll describe how tower fields work. These are type of binary field. Um how they work, why we use them. I'll describe our polynomial commitment scheme. How we get away with uh using Reed-Solomon codes and not having embedding overhead. So, this is a sort of key inner component. Um moving um outwards in in layers of abstraction, I'll describe what we call certain virtual polynomial constructions.

Uh shifting, packing, things like that. Um Putting all these ideas together, I'll describe how we do unsigned addition and multiplication even in the binary field setting. And then finally Kyber. And and also some benchmarks. Okay, so let's get um get right into it. So, what are binary fields? Just a rough overview. So, essentially an element of a binary field looks like this. It looks like a string of bits. Uh D bits, let's say, where D is the um sort of degree of the field extension.

So, we can think of it as something like 128. Um An important fact is that every such string of D bits is a unique or distinct field element. Uh so, this is not true for prime fields. You you this wrap-around phenomenon where, you know, bit strings representing integers greater than or equal to your modulus are sort of non-canonical or non-unique um and actually you are identical in your field to something else. Um addition is XOR. Okay, so very simple.

How does multiplication work? Well, well, we need to say um sort of what these bits mean in the classical case, uh essentially we we have a univariate quotient ring, okay? So, we start with the polynomials over F2 um and quotient this by the ideal generated by something irreducible of degree 128 or D. Uh so, the actual elements of our ring are essentially degree 127 or lower polynomials and these bits are the coefficients of the polynomials.

And uh to multiply two, we essentially do that multiplication in this ring. So, we need to multiply them as binary polynomials and uh then then reduce modulo this polynomial. Okay, so that's how it's typically done and we're actually going to do something completely different. So, um let's say what we do and then later I'll say why we do it. So, we're again going to take a bit width which now has to be a power of two, okay? So, again let's just think 128.

And um as before, this is my F2 to the 128 element, this string of bits. Um but now I actually have a kind of recursive um so, field addition is is again XOR as for multiplication um we have a recursive way of sort of splitting these into two F2 to the 64 elements, okay? And the claim is that this is not just a superficial thing I did to the bits and sort of break them in in two parts. This is actually sort of the makeup of my original field element. My original F2 to the 128 is actually made of two um F2 to the 64s, which come from the the next field down.

Uh I'll I'll say what that really means in a bit, okay? But this sort of keeps going, you know, F2 to the 32 and so on and so forth until we get to the level of bits. And essentially it's this recursive makeup that will be used in our multiplication. Uh just to give you a rough picture of what the actual algorithm looks like. So if I want to multiply blue and red, I have my breakdown, so I I I split them both in half. And the claim is that if I can come up with a way of multiplying the smaller field down, so F2 to the 64.

If I can do that, then I can sort of multiply these low halves, so blue's low half and and red's low half, uh and also blue's lower half and red's upper half, and sort of so on and so forth. There are four cross terms. If I can do these, which I can use recursion because they're smaller problem. If I can do that, then um I can combine the results using some linear amount of further work and uh get the answer. Okay so I'm going to argue first of all that we we can actually reduce this number of four to three using a Karatsuba-type technique. Um but um you know, we we need to say what these

additional operations are in order for this to sort of have any content. Okay, so essentially let's just say this a bit more rigorously what we do, okay? So we want to build up our field iteratively sort of inductively. So if we start with F2, first step is we're going to do a univariate quotient like we usually do by something of degree two, okay, not of degree D in one shot, we just go with a degree two extension. Uh this gives us F4, and this ring is is a now is is a perfectly good field in its own right, so we can iterate this process. Now we have a univariate polynomials in X1, whose coefficients come from T1, and we again quotient this

by something, you know, essentially this polynomial here, which I'll say more about in a bit. And um this process is something I can repeat uh until I get to T iota, let's say, um which which looks like this, okay? So the pattern is essentially each indeterminate X iota minus one, um I take that squared times the previous indeterminate times X iota minus one, and then plus one. And the claim, this is due to Wiedemann, 1987, is that um these FIs, the ones that I just wrote down, are irreducible forever. Okay, so we don't um So so essentially neither of the none of

these is going to split over the last field. So these actually are fields, as desired, um of the right structure and so on. Now um it's great that these are irreducible. It sort of means that they are fields. But actually we can say more. Um This particular choice of irreducibles actually has a nice computational um sort of setup too, in that um we can do arithmetic in these rings actually more efficiently than we can for generic Fs. Uh this was noted by Fenn and Parr in '97. So they give a way

to do um multiplication in in in these rings of complexity n to a base two of three, so this is sort of the Karatsuba exponent. Um and even inversion. So, this is actually a very crazy fact. Inversion is actually barely more expensive than multiplication is in these towers. Okay, so why use towers? Well, essentially the entire talk will sort of keep coming back to reasons why our use of towers is um is good. Uh but I can just say a few things right now. So, the in the classical um

definition. So, first of all, we want to be able to write programs or circuits where intermediate sized fields get used. So, 32-bit values or 8-bit values, for example, in the case of uh Kostal, um as it's called, and um also Reed-Solomon, the alphabet will be sort of medium size, something like F2 to the 16. Uh and we want to be able to efficiently deal with um with this field or or any intermediate field. And it's essentially the efficiency of these intermediate fields that makes towers really really good.

Um I can say just very roughly a few things about what efficient means in this context, okay? So, there's an idea of packing. An F2 to the 16 has essentially 16 bits of information. Okay, so if I have 16 bits and I want to cook up an F2 to the 16 from them, how do I do that? Um well, information theoretically, even regardless of how I define this field, F2 to the 16 will arise as a subfield. The question is sort of where does it sit in the big field? And is it efficiently identifiable? So, it in the univariate case, an element of the subfield just looks like any old degree 127 polynomial. And

the fact that it happens to be in the subfield um is is not something I can just read off by looking at the bits. There's some computation I can run, um essentially I should iterate the Frobenius automorphism on it and see sort of how large the orbit is. That will tell me the subfield, but that's a computation that um you you need to run. It's not something you can just read from a linear pass over the bits. Whereas in our case, the subfield elements are exactly the the elements whose first 16 bits are nonzero, but the rest are zero. So this is something you can just see.

Um another really important point is if I have a small field element, a subfield element, and a big field element, can I multiply them faster than a generic multiplication in the big field? So in the univariate case, I essentially have to first embed this thing, which itself has some cost, and then just multiplying the big field. So I'm not exploiting the fact that one of the operands came from the small field. In our case, the cost of of of this mult is something like eightfold the cost of an F2 16 by 2 16 mult. So it grows linearly in the size of the bigger field over the smaller field.

And then sort of can I reverse or undo this packing operation? Okay so in the tower case, these are all essentially free or or optimal. In the univariate case, they all have costs. Okay, so our work um sort of moving in a slightly different direction, our work also relies heavily on error correcting codes. I won't say too much now, but um what I can say that's sort of immediately relevant is that we want to use Reed-Solomon codes.

They They are um uh MDS. They sort of have the best possible um distance given their rate. Um and they're they're efficiently encodable even in the binary field case, as we've seen. This again um I I've mentioned this result. Uh the the key sort of obstacle though is that the alphabet needs to be large. So, um we're going to discuss a way of getting around this. Okay so putting some of these ideas together, um we can sort of suggest a straw man um um

PCS. So, so, you know, maybe the first question you would ask is is can we just um treat our F2 elements as if they were F2 to the 128 elements and use breakdown. So, obviously, um a priori for for a general code with alphabet to the F2 to the 128, um even if our message has components that are bits, our codeword won't in general. So, you're looking at a 128-fold blowup in the size of the codeword. Um even if we do RS, okay, so I've already mentioned this sort of in passing. Even in the RS case, we're still looking at a 16-fold blowup.

Um we're we're exploiting the fact that the alphabet uh is at least F2 to the 16 and not larger, but we we actually want to do even better. So, we want you know, a a one-fold blowup and not 16, meaning no embedding over it. There is a technical sort of security question that affects not just our project, but any actually any SNARK that uses extension fields where you actually want to guarantee explicitly that the extractor will extract a polynomial whose coefficients are in the claimed field. Right? So, it should not be possible for a malicious prover to commit to something that's not actually

over F2, but sort of pretend that they did and and convince the verifier. Okay, so charging ahead. So, getting into how we actually do this. We're going to start with something that looks like breakdown. Okay, so this is a matrix containing the coefficients of some multilinear polynomial over F2. Let's say it's m by m.

Um now, if we were to apply breakdown now, we would need a strictly binary code uh with alphabet zero or one or or or containing that uh and then apply that code to these rows sort of row-wise. Um what we're going to do instead is a packing type operation. So, we're going to go right to left through each row and chunk the elements of each row into 16-bit chunks, let's say. This gives us a new matrix of the same height m, but 16-fold less uh width and whose elements are now uh elements of F2 to the 16 and not F2.

Okay, so can we just apply breakdown now? Can we pretend that um we we were sort of given this polynomial and not that one and just apply breakdown. So, the answer is not really uh because you know, I'll I'll sort of skip through the details, but breakdown involves not just a commitment phase, but an evaluation phase, obviously. And if you sort of forget about the original shape of this matrix, then your evaluation is just not going to be meaningful. It will be essentially an evaluation of a totally different polynomial. So, there's actually an interplay of these fields that ends up being fairly complicated.

Very long story short, you need to sort of um do this this row combination operation on the unpacked matrix. So, so first you need to pack it to encode it, but you should sort of forget about that packing for the purposes of the combination. And the final remaining part is that there's this value T that sort of has this shape. It's now going to be of width M and elements in F2 to the 128 that the verifier needs to encode. And it's just not obvious what it means to RS encode this.

Recall that our Reed-Solomon code we did use had an alphabet sorry, message length M over 16 and not M. So, we sort of the the obvious thing that you might want to do sort of essentially looks like this where you view your F2 to the 128s as sort of chunks of eight F2 to the 16s, and then look horizontally and RS encode these. So, this sort of turns out to be not what you want. Um skipping ahead, there's essentially a data layout subtlety that you actually want to do.

You want to sort of view this horizontally in chunks of 16 and to get, you know, M over 16 total chunks. And then the RS messages you want actually look like um look like this essentially. So, looking horizontally, this gives us a vector of F2 to the 16s of length M over 16. So, this is sort of the right shape. Uh it sort of type checks the way you want um to apply RS, which is what we do and you do that 128 times. Okay, so this actually turns out to be what the um verifier does. Now, this is kind of on the one hand is a data layout fact. Um it's also kind of

an algebraic fact that we um we sort of go into in the paper. Now, you actually wind up needing a new proximity gap result. Uh so, breakdown relies on a sort of proximity gap for linear codes. You need a a sort of variant of that in in this sort of new layout, which we which we do give in the paper. So, I I think that's enough for now on the PCS. Um at this point, I am going to uh take this for granted, okay, and start progressing to the further layers. So, so now we should

assume that we essentially have the ability to commit to a multilinear polynomial, which for our purposes looks like a giant column of bits, let's say, and um then evaluate the polynomial that those bits represent at some arbitrary place. Um given that ability, what do we do next? So, um in in the paper, we describe various virtual polynomial constructions, which are essentially ways of manipulating and reshaping committed columns in in useful various ways. Okay, so the first is called the packing construction. Um So, here here is our picture. Again, we

have a a committed column of let's say two to the L uh bits. And what packing gives us is a way so it's a virtual polynomial meaning you don't ever need to commit to this right-hand thing explicitly, but essentially using the packing operator, we can um assuming the left-hand thing is committed to, we can act you know, and proceed as if we also had the right thing committed to even though we don't. That's what we mean by virtual. So, this thing on the right has 64-fold fewer elements 2 to the L minus 6, but each of the elements are F2 64 elements in this sort of packed way.

Um How do we do it? Um I'll I'll I'll just say in words that essentially you can write down a a sum expression involving these coefficients where um where the sum is sort of taken over these six-dimensional cube and um where the final sum is is exactly this thing. And now to evaluate that thing at some arbitrary point, you can actually use the sumcheck, right? So, this sort of exactly plugs into what sumcheck lets you do, right? So, after doing a sumcheck reduction, then the problem of evaluating this somewhere reduces to the problem evaluating this original thing

at some other place plus some sort of small amount of extra work that the verifier can do. There is a further virtual polynomial that we use a lot called the shift construction. So, again, uh start with the same picture. This is something that's explicitly committed to. Uh now the virtual thing we get out uh looks like the original thing but with a circular rotation say let's say downwards by three positions or something, right? So, this number three uh can be anything.

The shift can actually be circular or it can actually be a simple shift with zero filling up or down. So, all of these we support. We actually support a further sort of block-wise shift operation where in this case we again segment this into blocks say of 64 elements and then each block gets shifted by some amount. Let's say one or something else. And again the shift can be circular or with zero filling up or down. How do we do it? Um Let's see.

Yeah, so first of all, why is this useful? So, as we'll see very soon when we get to Keccak, um it's often useful to be able to operate over shifted versions of the things we have committed without having to actually commit to those shifted versions. So, for example in Keccak, what you want to do is sort of compare the next round of the main state with the output of some transformations on the current round of state. Um it's very nice if you can do that without explicitly having to commit to a shifted state vector. And um that's sort of exactly what we see.

Yep that's Okay, so the complexity is um it is is quite good. It's actually independent of the offset. It only depends on the size of the block. So, it's actually logarithmic in the size of the block. So, in in this original example, that would be L. And in in the block-wise version, it would be six essentially for the verifier. And this essentially answers a a that that hyperplonk posts.

How do we do it? Just very roughly, and I I can always come back to this if there are questions. We are able to write down uh what we call shift indicator polynomials. So, these are bivariate polynomials that take values sort of sort of X and Y in in the cube or or or rather just in sort of field to the B. So, they're they're sort of B variate each. Uh but the key property is that when they happen to reside in the cube, um then this thing becomes an indicator that essentially returns one if and only if the binary strings X and Y differ by an arithmetic sort of unsigned addition of O, where O here is the offset.

Um and the key point is that this polynomial This is a perfectly good polynomial for arbitrary X and Y, but for X and Y in the cube, it has this property. And there is a circuit that decides or computes this polynomial whose size is O of B. Okay? So, this is a pretty interesting and and non-trivial fact. This extends a an idea due to Setty, Gaylor, and Wabbie, where the offset in that case was just one, but for us it can be arbitrary.

Okay. So, now stepping yet a further level sort of outwards in terms of the um what we're building, uh I'm going to spend some time now talking about what we call gadgets. So, these are sort of um assembled sequences of packing, shifting, and various constraints that let you do important tasks. Uh so, in particular um unsigned integer arithmetic, so addition and multiplication.

Um we find this to be pretty important because um the ability to do these was often cited as a reason not to use binary fields, right? The idea is that if you use prime fields, then you can do these things natively in your field. Now, that actually turns out not to really be true because you have issues with range checks and wrap around and things like that, right? So, even protocols that do use a prime field, let's say 32 bits, um to add uh 32-bit integers, you end up needing to break them into limbs, and you can add the limbs natively, but then you need to combine them and do range checks and things like that, right? So, even there it's not really for free.

Uh but for us, we we need to sort of build these from scratch because um we we just plain don't have these in the binary field setting. But, we we do actually turn out to be able to do these. So, let's see how. Um addition turns out to be very simple over F2, right? So, the the setup is that we have committed columns X, Y, and Z, say. And the thing we want to prove is that if you go through these columns vertically and chunk each one into 64-bit chunks, then it should hold that um chunk-wise Z is sort of the unsigned um

arithmetic addition of X and Y is sort of modulo 2 to the 64. And that should hold for each chunk. Okay, so how do we prove this? It turns out that um by committing to just one further auxiliary column, C out, okay, so this is the carry out of of the addition of X and Y, um turns out that ends up being enough. So, we we then get C in, carry in, by shifting C out downwards by one with zero filling, right? So, note that the first or zeroth position in each block should be zero by definition of what carry in means.

Um and then we just have a few constraints, right? So, we need to um declare. So, this is not really a constraint because CN is virtual, not committed, right? But, we want CN to be the shift downwards by one position of C out where the block size is 64, right? And um once we have this, we just write down some very simple constraints. So, Z should be the addition over F2 of X and Y and CN, right? Where um you you reduce modulo two, of course.

And then um we we now need to constrain that C out is correct, which essentially entails requiring that um of the three columns X, Y, and carry in, if two or more of those are one, then C out should also be one. And this turns out to be just a simple expression over F2. Okay. So, we're able to add with just one auxiliary column, um one shift, and sort of two arithmetic constraints. Okay. So, multiplication turns out to be a a a sort of combination of every idea that we've gone through thus far. Uh so,

how do you do it? The very rough idea is that uh we use lookups for um limb-by-limb products, and then uh we just need to combine those using the schoolbook method, right? Um the key point here is that for our lookups, we we have an adaptation of Lasso for the binary field setting. So, this totally works. You need to do a few things differently, but um it it can be done. So, again, here's our picture. We want to multiply X by Y.

What we do, so let's imagine that these are 32-bits. And this picture actually tiles sort of horizontally to the right. So, we're zooming in now on one 32-bit chunk of of our columns X and Y, which we now write as rows. Okay, so let's segment X and Y into limbs. So, let's imagine that these are eight bits each. And um the idea is that we're we're going to go row by row through the schoolbook method. So, in the first row, what do we do? Well, we need to multiply Y0 by each of these things. So, let's just not do anything to to X. We'll shift it by zero. It's a no-op. Um we're going to what we call saturate Y at the zeroth

position. So, this is a third virtual polynomial, the saturation operator, which essentially um repeats blockwise. Um It it sort of fills Y blockwise with with one of its um positions. In this case, the zeroth. And um these are exactly the things we now want to take um products of. So, we we have in green the sort of double-width product of X0 and Y0, these two limbs. And um similarly for X1 and Y0, we have another double-width product. And um we can write these four things down like this. And the first thing we do is basically use one execution of a lookup to sort of guarantee that these green things

actually are the um the the desired uh double-width um cross terms. The arguments to the lookup are you know, shift zero and and sat zero of Y. And um and now there's a kind of tricky point where um how many sort of how many green things need to be committed to. The answer actually turns out to be not four but but two as this cool animation shows. The idea is that the the even and odd substrings of these green values don't overlap. So, I can actually commit to all the even ones in one column of bits and all the odd ones in a further column

of bits. Okay, so that was the zeroth row of schoolbook. Here's the first. So, now we actually do shift X by one. So, this is all zeros here and we saturate Y at one. And again, this is exactly the set of cross terms we want in the first row of schoolbook. Right? So, again, we do the same drill. Commit to these green things, use one further lookup. And again, actually I only need to commit to two, not three.

Moving on to the second row, we shift X by two and and saturate Y at two. And again, cross terms, a lookup. And finally for the third. Okay. Now, putting it all together, by definition of how schoolbook works, if we recall all of these green things that we had, this is from the zeroth and from the first and from the second and the third, by adding these, that sort of gives us what we want, which is in green.

Okay. So, what is the complexity? Well, if we write L for the number of limbs per word, um we we only had to do L lookups, some something like three times L committed columns, L zero checks, and two times L additions. So, the key point is that the number of invocations of sub protocols is only linear in L. Essentially using this even odd trick. If we didn't have that, it would be something like L squared.

Um a point about the size of the lookup table, right? So in our case there are 2 to the 16 possible pairs of two 8-bit limbs. So the size of our table is 2 to the 16. So obviously there's a trade-off here where um if you have um fewer limbs, then these numbers become smaller. But also the size of your lookup table becomes, you know, bigger very rapidly, right? So if if the limbs were 16 bits, then your table would be of size 2 to the 32.

Okay, so the final thing I'll talk about is Keccak. And um again our arithmetization for Keccak essentially puts together everything that I've um touched on thus far, right? So we end up needing shifting and packing and um also the ability to commit to bits is is very crucial, right? So um the way we essentially do this is that um we only have 60 columns. The the Keccak state is essentially something like 25 64-bit values. So we actually unpack those vertically. So we have 64 rows per Keccak state. Um Since Keccak is 24 rounds, if you

multiply this out, you see that we can do one Keccak F per around 1,500 rows and you know, 60 columns as mentioned before. Um if we allow a a total trace size of 2 to 28, you you what you find is that you can fit 164,000 Keccaks. Um the final thing I'll say is is just some brief performance benchmarks. So, what what I currently have here is is the um cost of committing.

Um our paper also includes other things like cost of proven verify and also things like sumcheck. But um yeah, so it involves um Merkle hashing with cost of additive NTT and of course binary field arithmetic. And here's essentially the table. Uh this column is commitment cost for a polynomial 28 variables over F2 and you can see that we are you know, faster by by by a lot than than these other works. Now, the key point is that our work is actually exploiting the fact that the coefficients are small, whereas these works

uh essentially don't. Um even when committing F2 to the 8th, let's say, we are still um doing doing doing quite good. Um okay, so so that I guess is is a is a good place to pause. That that's sort of the official presentation and and maybe we can uh start with uh questions. Uh there's a couple questions from the the chat that maybe you want to start with.

Yeah, go for it, Jim. Feel free and run through them. Yeah, cool. Uh thanks. So, the the first one uh maker asked with respect to why binary field STARKs didn't work and and relating adjacent trace rows, he asked isn't there a primitive element for the binary tower too? Do you want to answer that phone? Uh okay, yes. Okay, that that's a good and actually subtle question. So, there is, but um the orbits of that thing the orbit of that thing does not interplay nicely with the additive subgroups, right? So, yeah, this is actually a a non non-obvious point. Um your trace domain

in a binary field it needs to be an additive subgroup of the field, right? Or or really more precisely an F2 vector subspace. Okay? Um if I pick a primitive element and start taking its powers, um I'm going to cover sort of everything which is non-zero. Okay? So, that's too much and also it misses zero. But even if I pick some sub orbit of that thing, um it's going to be completely chaotic. First of all, its order will not be a power of two. It will be a divisor of 2 to the K minus 1, right? It'll actually be odd. Um and the elements that I trace through in that orbit are going to interact

completely arbitrarily with my additive domain with my F2 subspace. Uh so, it just doesn't give you what you want. Um and nor can I use that orbit as my domain either because that will not if I do that, then I throw away the efficient RS encoding. Does that answer the question? I I can I can re re Yeah. Maybe to add one more like way that I think about it and like it an interesting point is like so if you're working in F2 to the 16, you have a multiplicative subgroup that can like, you know, uh span or not span, but like I guess uh cover everything except zero.

But if your trace domain is of size uh you know, 2 to the 18 or something that doesn't align with a tower field, then how are you going to find a subgroup of the multiplicative group of F2 to the 32 that, you know, uh has size exactly 2 to the 17. That's, you know, not clear. Um there was another question. I think my question was next uh about um the implementation of tower field. So, I I guess this is general to tower fields and not um specific to Venius, but um it you can have you can do it using

quadratic extensions um and so abstract or say F4 F to the 4 for example at each step of the tower. Um what are the tradeoffs between those? I I can give you that a shot. Um I I mean, essentially the the the most obvious thing I can see is that um it just gives you a less granularity in the sizes of available um intermediate fields, right? Which in particular which intermediate fields can be represented um as as a sort of

with a multilinear basis, right? So, your your basis will not be multilinear anymore for certain intermediate fields. Um Also, I mean, it it's every uh even sized field basically if it was F4. So, that's that's probably sufficient, I think, unless you want to to use individual bits. So, I think there's So, there there's a couple of reasons. It's a great question, but so the first is we use the specific like vitamin tower which gives a sequence of quadratic extensions. And so, first you would have to like go and find how you're going to pick your your quartic extensions and hopefully have something that has the same structure

and then the other thing is like because of the specific properties of this tower field, you asked another question related to this. Yeah, yeah, I was I was going to ask that what what exactly you're depending on about the Vietnam towers? Is it that the irreducible polynomials are are very regular? They're the same at um Is this a modulo the indices at each step or Yeah, Ben, do you want to like try to explain why we get this efficient multiplication for the Vietnam tower? Okay, okay. The The question is where does the efficiency benefit come from?

Yeah. Okay let's just say a few quick things I can try to run back. I'm going to take basically what are you relying on from that um that way of constructing the tower? Yes. Yeah, so Sorry, just just give it a second. Uh here we are. Okay, so the very very quick way to say this is that um what what do you have to do when you multiply? Well, if I want to multiply two elements of this field ring, uh right? Then they both look like degree one polynomials whose uh entries are are in the smaller field down, right? So first I need to multiply two linear

polynomials, get something quadratic, and then I need to reduce that quadratic thing, okay? Uh modulo modulo this. And everything ends up being exactly the same up until the point when you reduce, okay? So In other words, the benefit of this only kicks in in a very very specific point, which is um when I reduce, so I have an arbitrary quadratic polynomial and I want to reduce it modulo this particular quadratic polynomial. What does that entail? Well, whatever the leading coefficient of my given thing is, I need to multiply this by that leading coefficient and then subtract it, right?

So, you know, call it alpha or something. I have alpha x iota minus one squared plus something else. So, I need to multiply this whole thing by alpha and then knock that out, right? And the key fact here is that the coefficient x iota minus two, um so, the key problem ends up being multiplying this particular thing by alpha. And um what's true in in Widmann's tower, but not in other towers, is that that multiplication by this particular element is more efficient than multiplying by an arbitrary element, right? So, there's a way of multiplying by this particular thing that is is much

cheaper than right? So, it for general f for for general f, this thing instead of being x iota minus two would be something arbitrary, right? And it's just simply cheaper to multiply by this. Why? Well, because it's a very simple monomial. It's kind of just like a shift and it sort of just checks out. Does that answer enough or I I can Yeah. Um I the the rest I can look up. Yeah, thank you. It is worth noting that we actually originally found another form of this sort of deterministically iterated uh tower basis that um was like an Ardent trier tower that gives you

you know, better than quadratic uh multiplication time, but it was, you know, the asymptotics were somewhere between the Fan par tower and and quadratic. Um and we, you know, basically stumbled upon this one uh instead and and decided to switch. Yeah. So, so it's it's it's basically just that you need efficient multiplication. It's It's not an interaction between um this representation and the rest of the Yes, exactly. It's completely big to the to the every higher part of the scheme which polynomial you use is just for efficiency.

Okay, cool. Thanks. But one one more thing to say on on the arithmetization, I can basically make arguments as to why you would like to have uh the subfields of like 8-bit, 16-bit, 32-bit, and 64-bit. Like they all have, you know, the 8-bit field's nice if you're doing AES arithmetization. The 16-bit field is nice for Reed-Solomon encoding in our breakdown scheme. Like there's it it's we were actually able to make use of all those intermediate fields. Yeah, I thought I think I'd been underestimating the benefit of that. Um Yeah, good point. You do need all of 8, 16, 32, and 64 to to express lots of interesting algorithms.

Uh you asked a bunch of questions, so do you want to Do you have any others that you wanted to follow up on that and ask now? Uh I'm just looking at the the history. Um Yeah, I was just noticed noting that um lots of functions and ciphers rely heavily on shifts. Um A question about carries was answered. Um Another code to Reed-Solomon. I actually don't remember what Was it cluster or Concatenated codes perhaps.

I can't remember now. Um I I didn't catch it either when I saw the question. Um so just matter. Yeah, Victor asked a good question about how we were able to do a version of the shift polynomials that instead of doing a circular shift like sort of is an arithmetic or logical shift. That like basically zero fills. Do you want to say anything about that, Ben? Yeah, so actually it turns out that the the the non-circular shifts are simpler actually.

Um what ends up happening internally when you look at how we define our shift um what ends up happening is we actually define a sort of downward shift and an upward shift. And actually the shift the circular shift ends up being the literal sum of those two things. Um so um the problem is not actually setting the bits zero. They just kind of are zero by what by how downward and upward shift work, right?

And so to really answer that question, you you kind of need to go into um how how the downward and upward shifts work, right? And and of course the the circular shift ends up being a sum of those. But I can just say in in essentially one sentence or so, um the way downward shift works is by writing down a shift indicator where it only returns one if it sort of Y is below X by, you know, O steps, right? But not a not above it by, you know, 32 minus O or something, right? And then and then the upward shift is like the opposite of that, right? So it's actually the sum of those that ends up being the circular shift.

Um can I say more on that or or does is that satisfying? That sounds good to me. Thank you. Okay, yeah, happy to follow up further if if you have any questions on on shifting. Um Marcus asked, do we see potential for new ZK-friendly hash functions which operate natively over binary extension fields. Um I certainly do. So, I mean one I think promising benefit of this is that we will be able to efficiently arithmetize classical hash functions, but if you're doing you know I think there's still a benefit to having even more arithmetization optimized hash functions. So, to leave a

little bit of alpha where we are investigating using the vision construction over the 32-bit tower field and seeing if there's optimizations we can find to that. And however, I know that you are also Well, you are an expert in semester cryptography and I'm far from that. So, if you would like to chat with us about about arithmetization optimized hash functions over over tower fields, that's something that we are quite interested in. Yeah.

Um yeah, I mean some ciphers already and hash functions already use um binary fields. I mean AES um and uh Yeah. They So because multiplication in a binary field is less efficient on a conventional processor than it is here. Um Yeah, I I think there's still some scope for um for improvement there.

Cuz the trade-offs are not exactly the same between between this and conventional processors. Yeah, we're we're working on our So, we are actively working on our open source rust software implementation of the Binius system and some of the you know, working towards implementing arithmetizations of various hashers. So, you know, Keccak, SHA-2, and Groestl, which I cannot pronounce as well as Ben, but which uses the AES S-box and seems to be, you know, fairly fairly arithmetization optimized for the setting.

Um Have you looked Have you looked at any of the Blake family? Not as closely, but like I'd love to have, you know, hash verification gadgets for everything. And I know that Blake is very, just you know, CPU friendly and optimized. It looks It looks like it would be very very fast on this because you can do additions modulo 2 to the 32 efficiently. You can do shifts, and you can do XOR, and that's really all you need for the inner function of Blake and ChaCha families. So, yeah, I'm not even sure how you could

um improve on that with Yeah, you probably could improve on it by using natively using binary multiplication multiplication. Yep. Um Binny, do you want to ask your question aloud? Otherwise, I can repeat it here. Binny says it seems the main reason we can't use FRI is because we can't have a large multiplicative subgroup, but what if we use the base fold IOPP that can support non-FFT-friendly fields?

Um I can say that So, the original FRI paper uh actually kind of the headline result is about FRI for binary fields over additive subspaces, and that is not lost on us. We have some more investigating to do to see how much we can adapt that to our setting and find optimizations. We are optimistic but not ready to share results right now. Um Verena, I don't know if I'm pronouncing that right. Um also Binnie, if you want to chat with us about that, um we can certainly get in touch. Um

uh You uh Verena asks, do you want to ask your question aloud? Um I don't mind if you hear me. Yeah. Yes. Okay. Yeah, so you were mentioning in the introduction that you also considered binary codes. I was just wondering what issues you faced there or what your considerations were or if you also considered any other error correcting codes besides Reed-Solomon? Yeah so I I can take a shot at this, Jim.

Please yeah. Um yeah, so this is a good question and um we definitely have a fair amount to say. Uh essentially it it is simply not that easy to construct binary codes with very small alphabets and after looking around, it's it seems that the sort of most natural construction is what's called concatenated codes. Um these are essentially a way of um sort of bootstrapping a a Reed-Sol well, to to very over simplified, they're a way of bootstrapping a Reed-Solomon code to a code over over a tiny alphabet by sort of um concatenating in front of a

very very small binary code, right? So, the idea is that if I have, let's say, a a 32 16 code over F2, right? So, maps 16 bits to 32 bits. Um if I have that, then I can um sort of concatenate that with an with with a Reed-Solomon code with alphabet F2 to the 16, and out comes an actual binary code. Um, whose distance is actually quite good. So, So, one thing that you can do, which which we totally describe in the paper, is actually use a sort of simpler breakdown, like a like a plain breakdown without packing,

where your code is a concatenated code. Um, or any binary code. And this actually works perfectly well, and it it might even be more efficient, at least in terms of proof size, than what we do, namely with packing. And we actually give some benchmarks for for precisely this construction. Now, what's the downside? Well, you know, everything I said sounds pretty good. Um, the essential downside is that the concatenated code construction just it is not an asymptotic construction. It requires that you supply this tiny code.

This sort of small code over F2 is is completely ad hoc, and you need to sort of supply that for each size of the Reed-Solomon code you get. So, in particular, it just simply doesn't even make sense to say how does the concatenated code approach perform asymptotically, let's say, right? Because um we just don't have a way of coming up with asymptotically good codes over F2. The only thing you can do is sort of plug in the best binary code you can find at each step.

So, there's a kind of theoretical challenge there. Also, much more down-to-earth reason is that it's just plain simpler, efficiency or implementation-wise, for let's say the verifier, when the verifier does not have to um perform the encoding function of this arbitrary ad hoc inner binary code. Uh so, there are implementation considerations, um asymptotic, um sort of theoretical reasons, and various things like that. Um there might be some better code some better binary code than a concatenated code. I don't know of any, uh but it's definitely something you can do that we just um opted not to do for various

reasons. Does that answer or um Yes, thanks very much for explaining those points. Yeah, I want to add a couple things. I think that that's spot-on. Um another choice that someone might you might wonder about is the Spielman linear time encodable code that is described in breakdown and uh and some other works. Um You uh like breakdown gives this construction of like a randomized um expander code, and we actually, you know, looked into this a lot early on, and sort of the memory access patterns of doing these random memory accesses

just didn't lend itself to a nice implementation, and we have like a lot of experience optimizing NTTs in software and hardware, and the memory access pattern is like well-studied, and and so we like Reed-Solomon codes. We just like Reed-Solomon codes. The other thing is um that I'm not sure Ben mentioned is there's an improved proximity gap result for Reed-Call Reed-Solomon codes specifically that's better than the best-known best-proven proximity gap for uh general linear codes. So, that, you know, gives you a little bit of a boost as well. Um And then, yeah, Ben mentioned the the point about implementation efficiency,

but that's like very important to us as you know, having a large engineering team that like the overhead of doing this inner code uh um encoding would is just kind of a pain. Um should we should we turn to Benedict who has very patiently sat with his hand raised. Uh Benedict, did you want to uh articulate a question? Yeah, thank you. Um I guess I feel like there's I have some basic misunderstanding here. Why couldn't I just use So for the multiplication exactly the slide of

um why can't I just use uh just fast polynomial multiplication? Um and then reduce my No, I meant actually the slide that you were already on. Sorry sorry sorry. Um Yeah, why can't I just use fast the polynomial multiplication and then reduce uh mod uh I guess uh FI or whatever. What's what am I missing like In in this ring you mean? In T in T iota?

FTI. The the So the two polynomials you're multiplying are of degree one, right? So the the basis like the you know, we're we're used to thinking about binary fields as having like as being univariate polynomials. Uh our basis for the tower fields are a multilinear polynomial basis. Right? So um and then you can still do you can still do point-wise multiplication. That is absolutely true, but it's very unclear how you then do the reduction and like what you're then reducing. I'm not saying it's like impossible or or I don't know, but like it's very unclear

what doing that reduction would then look like. Okay, I guess you're saying okay. Uh this is the most I guess there's at least in theory uh there's algorithms still though that are should be faster than what I guess this is like n to the 1.5. Um like I mean there's just like fancy multiplication algorithms over just generic I believe you can super generic, right? Yes, yes, yes. I I I think if you use very fancy things, you can beat this asymptotically.

Um we have not really gone down that path. Um so so yeah, let me just try to clarify as much as I can. Essentially, elements of this ring are polynomials of degree one or less in in t t iota minus one. Now, as Jim said, if I take this ring and unroll all definitions, this turns into a multivariate polynomial ring where the elements look like multivariate polynomials in x iota minus one dot dot dot x zero, where the degree what where the degree of every indeterminate is is one or or zero. So they're multilinear.

Um now, that's fundamentally the object you want to multiply. When when I when I talk about Karatsuba, what I mean is I sort of group them um I pretend that they were linear where essentially I I I group everything that is is is of lower than x iota minus one into into the coefficients and and act as if those were linear polynomials. But yeah, it's true that um there are sort of fast techniques even for towers. Um I I think that you should be able to get to n n log n um instead of what we have here. I think there's a work by uh

De Feo, uh Schost, and um one other. I can't remember that where I I I'm pretty sure they they claim an n log n asymptotic complexity for the tower setting. Um, so Mhm. we just simply have Okay, and and as a practical algorithm like not just using like Schönhage-Strassen generic multiplication. Uh it's a So, I I can't tell you specifically how they do it, but yeah, I believe that they are claiming that it's sort of more down to earth than um what what Schönhage-Strassen do. But, um actually I I think the substance of it ends up being a conversion or or some

kind of field isomorphism between this and something univariate, where in the univariate setting you can then fall back to whatever classical fast thing you want, and um they claim that there's an n log n time conversion between the multilinear representation and and the in some kind of monomial representation. Um, this is I I wish I could say more uh about how they do that, but yeah, I I believe it's more down to earth. For our purposes, we just simply didn't find a huge need because actually concretely we get quite good efficiency um with with just a simple tower uh with Karatsuba. I think we're Sorry?

Interesting, that was my next question, like whether this matters in practice. Yeah, I I think we're I think we are um maybe a couple fold slower than a a pure monomial basis multiplication with Karatsuba. Does that sound right, Jim? Uh it depends on on the platform. So, one thing we haven't mentioned yet is that Ocelotana does is uh does FPGA implementations of various cryptographic primitives. So, we look at the efficiency of these things from perspective of both CPU implementation and kind of native digital logic. I believe I would need to check with our hardware engineer that for the 128-bit tower field, which is sort of our largest uh field that we're using in our

implementation, that the univariate sort of uh basis that the GHash AES-GCM mode uh uses is only like 10% more efficient than our 128-bit tower basis in in digital logic. Um it's It is, however, considerably faster on the CPU because there's a you know, just a faster reduction. So, our CPU implementation of the tower fields um will I think be doing more to publish like the kind of SIMD algorithm we use for this, but relies on Intel's Galois field native instructions, which do

8-bit um or they do, you know, there's instructions to multiply 8-bit binary fields in univariate basis, and we sort of build up the recursive uh multiplication on top of that primitive instruction. Uh I was I was going to ask what um where do you start the recursion from? Um so, yeah, I guess it makes sense to start it from 2 ^ 8. Yeah, we're also looking at um you know, on on machines that don't have that instruction, we're investigating what we can do. We're working on a uh CUDA implementation right now. Um actually, the person working on that's on this call, but um so, we'll have more to say on efficiency on different uh different platforms that don't have the

GFNI instructions soon, hopefully. Yeah, I mean, I guess you can implement those using lookup tables. Um anyway, even if you don't have instructions. We've have an algorithm that sort of you can do kind of fancy bit twiddling stuff to transpose things in a in a cool way. Um, and I think that's the best we've come up with so far. But, you know, what we really care about is the efficiency of this stuff in in native digital logic cuz, you know, we think that ultimately, well, in the short term we will have have FPGA implementations for the computational bottlenecks of this per system. And uh and in the long term, um

you know, custom silicon. Um Benny probably has had his hand up for a while. Yeah, Benny, you want to go next and then Dara. Thank you. Sorry, I was having some background noise, so I didn't replay. Uh and yeah, it's good talk. And really sorry that I've missed the first half of the talk because of some other issues. So, uh so may I may have some misunderstanding. The main question I have is about the packing techniques. So, I've heard that you are anyway using the Reed-Solomon code for the PCS. So, uh my main question is what's the motivation of using breakdown in the first place?

Uh it seems that more natural uh to consider FRI if you are using uh Reed-Solomon code for PCS. So, is there any like uh subtleties at the beginning of when you decide that you will use breakdown rather than FRI for for constructing a PCS that combined with this packing technique? Yes. Um maybe Ben, can I take a stab at answering this first? You can go into some details. So, uh when we started working on this, um the So, FRI is a as you well know, FRI is an IOP of proximity. Uh it's not a polynomial commitment scheme. There's like a pretty well-known at this point transformation for using FRI to construct a univariate polynomial

commitment scheme. And then there's a um Hyper Your paper gave a nice uh way to do a multivariate polynomial commitment scheme using the fry well using a generic sorry a multi-linear polynomial commitment scheme using a univariate polynomial commitment scheme. Now the univariate polynomial commitment scheme that uses fry uses the technique of quotienting which means that you actually interpret the uh sort of the values of your Reed-Solomon codeword as um kind of useful information and that's basically incompatible with our packing

technique cuz we're in in the way that we're packing bits into you know Reed-Solomon codeword symbols it sort of corrupts the meaning of them in a way that is not compatible with the quotienting like deep fry methodology. Um and so that's why we looked at breakdown because breakdown and the tensor code approach strongly decouples like what is what part of the the PCS is using the coding theory and like how you're doing the evaluation.

I see that's really interesting. So basically it's the quotienting become a bottleneck. So what if like for example there are some other compilation from IOPP to PCS for example like in base for there's a sum check base compilation. So it is sum check will be compatible with that? Uh we think that's a very cool construction and we would love to chat about it offline. That's good. Yeah, thank you. Yeah, that's really helpful. Thank you so much. Uh Ben did you have anything that you wanted to add here? No, yeah. I think that covers it, right?

Essentially you're then forced to choose between either don't pack but you then you have embedding overhead, right? Where you're embedding your bits into F2 to 16s or do pack, but then you've corrupted the meaning of your of your code word, something like that, right? I see. I see. Thank you. Yeah, I think I think part of my question has been answered by that, but um so yeah, it might be worth looking at um hybrids of some of the existing um polynomial commitment schemes that that satisfy the constraint that you need for packing, but that that pick and choose ideas from them.

Yeah, to say one one more thing, um we think that this is you know at least worth investigating. Uh however, it is another thing that makes us like breakdown is that you are uh rearranging your matrix. So, let's say you need to commit a matrix uh polynomial of size like 2 to the 28 or 2 to the 30 or something. With FRI, you would need to do a Reed-Solomon encoding with uh a block length of something around that size of 2 to the 30. And so, you would need to use the the 32-bit tower field because your field needs to be larger than the uh the block length of the code. With breakdown, it shapes the matrix uh it shapes the polynomial

multilinear polynomial into a matrix, and so your Reed-Solomon codewords can be smaller. So, to commit a 2 to the 30 size polynomial, you might likely be able to do Reed-Solomon encodings with a block length of 2 to the 16 or or less, which means that you can use the 16-bit tower field and get, you know, a pretty significant efficiency advantage from doing that. So, that's um you know, for workloads where you can afford to have larger proofs and uh and faster proving, uh there's still a good reason to to do that in my opinion.

Yeah, so the reshaping has this sort of side benefit where you have a square root reduction in the message length that you want to encode, and then that in turn lets you use smaller alphabets. Um Tyra? Am I pronouncing that right? Tyra, was that your question or did you do you have another question? Uh, I I I think my question had already been answered. Great. Uh, and then I think next is Victor. Yeah. Have you all done any experiments so far or at least have intuitions on what like self-recursion might look like and if you I guess first of all, if you can self-recurse efficiently, and then if you do, if you'll actually get any

kind of size reduction in the in the in the proof after doing more than one layer of that. Does that make sense? Yes, the question makes sense. Okay. I I'm happy to take a stab. Like, we don't have anything concrete to say about this except that we're like optimistic that, you know, we're kind of starting with we're building the software implementation of the arithmetization. We give a concrete and fully described arithmetization of Keccak in appendix A of the paper, which as Ben said, we think has like very low overhead over the the Keccak, you know, like the amount of data that you need to commit for this is,

uh, you know, pretty low compared to the Keccak state itself. Um, so figuring out what our arithmetization cost for hashers is prerequisite to us figuring out the arithmetization cost for self-recursion, and this is where our stuff like, you know, possibly investigating, um, arithmetization or optimized hash functions over tower fields is interesting. Mhm. So per occasion, how many hashes basically would you have to do uh for How does it depend on the circuit size?

Uh asymptotically square root. Okay. That's pretty good. Yeah, so I think I mean uh I I don't remember the numbers off hand hand, but like Ben in the paper we gave some some kind of like proof sizes and basically we were getting compression of what something like 500 megabytes to to 10 megabytes or uh Let me see if I can pull this up in in the paper. from 512 to between 7 and 11 depending on some details. And then um we can also compress 8 gigabits to around 60 megabits.

Yeah. Um but yeah, I mean definitely still interested in doing research on like what other tradeoffs we could be able to strike in terms of uh proof size, proving time, and uh hopefully have more to say on that soon. Yeah, I'm definitely part of that. Uh awesome. I have one last question. Um and then we can close. So I think we're at time. Uh you mentioned in the talk, um you know, I think it we talked concretely a lot about proof of performance, but you mentioned when discussing STARKs, you know, some of the reasons why in practice your constraint

is just the network overhead. Can you say anything about uh the verifier cost and proof sizes in the scheme relative to maybe I guess existing deployed schemes. And the reason I'm asking this is because in in a lot of applications, like proving is obviously the biggest overall cost, but for depending on the application, particularly the public blockchain setting, for like roll-ups e.g. like the verifier cost is pretty meaningful uh economically speaking. Absolutely. Uh Ben, you want to take this cuz you you have the slide up?

Uh yeah, sure. So, um I I can say that after one level of recursion, so we were we were just discussing this, um that we we do achieve a a you know, many order of magnitude compression rate in the size. So, we as we just said, we can compress 512 megabits to say around 8 megabits in in one level. We can also compress 8 gigabits to around 50 to 60 megabits in in one level. So, um I I think that in practice, you would not use say just one level of recursion, you would use either multiple or maybe compose with something else.

Um but I I think we believe that we have achieved some sort of escape velocity where we we have enough compression to to make recursion work and to to yield possibly after composition with something else, um something which is is feasible in practice. Um Jim, maybe you can add to that. Yeah, uh one clarification. Did you mean megabytes and gigabytes or was that intentional to say megabits and gigabits? Uh I guess what I really meant was G I little I B, so gibibytes.

Yeah yeah. Yeah, yeah, those are bytes. Um and then I I think maybe the the missing thing to to make explicit here is we like basically believe in Ben, could you like forward to the next slide with the the the ZKVM chart? Yeah, this the one one back. Like this on the right. So, this is basically a diagram that Polygon published of like their overall proof system, and we basically believe in this architecture, which is like the bulk of your proving you are doing in a proof system that has a fast prover and a, you know, relatively expensive verifier. And then you have several layers of recursion that ultimately ends in a super, you know, small proof fast

verifier elliptic curve snark, but over a very compressed, um, you know, recursive statement. And then there's several, you know, who knows how many you actually need, but like layers of recursion in between where you're kind of progressively compressing more aggressively. So, we do think that for many applications like this sort of hybrid scheme where you're going to do a bunch of binary proofs, and then you're going to like do a recursive elliptic curve snark proof at the end to say, put it on chain or, you know, whatever, um, it is likely, you know, it it seems to be a winning paradigm to us right now.

Yeah, um, so so if you use an elliptic curve proof, then you lose the post-quantum um security. Um, I guess if you use Plonky2, then that's probably the the smallest and most efficient to verify post-quantum proof at the moment, I think. Um, could be wrong. Yeah. We'd like to certainly be able to get like the native binary field proofs under 100 kilobytes, and then and then it's sort of up to you if you're like, I'm not sure.

Yeah. no, no, it's it's well, super helpful, right? Cuz I mean, you can just think of like the the Ethereum throughput, right? Like, you know, if a proof is existing on chain, you can think of okay, like how big is a block and then how big are proofs, right? You so this is like for a at least for our layer one public blockchain setting, right? If you're thinking about other settings, this doesn't apply maybe, but like for a blockchain, obviously proof like block sizes and time per block is really, you know, cuz the network bandwidth you need to have like every node sending every proof to every other node and verify, it ends up becoming in my experience at least with Aleo dominant at some point. So, that's uh that's at least on the network level.

Obviously not on the prover level, but the whole network isn't bearing the prover cost, right? That's only like one person that can take as long as it wants, but um super helpful and this is a great talk. Thank you very much for putting this presentation together. Thank you everyone for attending and um with that I would just love to say, yeah, just a big thanks and hopefully we'll get to see everybody uh next time. Jim and Ben, any final words before we conclude? Uh thank you so much for having us. Uh Ben, to you? Yeah, just just saying appreciate you having us on and thanks for the opportunity.

And we're hiring engineers uh who know cryptography.