"Succinct Arguments over Towers of Binary Fields" by Ben Diamond

Transcript

patience okay so hello everyone and welcome to a new session of the PSC learn and share series uh today we have Ben diamond with us and he's going to present uh his latest work on snarks over binary Fields I will let you further introduce the paper uh thank you very much for attending and please the floor is yours Ben okay well thank you again for having me uh very glad to be here uh glad to present about Bas Nars over binary Fields this is a joint effort by ulana and will be presented by myself Ben Diamond um so um before I I get into the

substance of um the presentation I'll just say a few introductory words about the landscape that we are stepping into um just to set the stage and also maybe give some background so you can point to maybe two rough um categories that um snarks fall into the first we can point to elliptic curve based protocols okay so these tend to be succinct with constant size proofs constant verification cost um slower for the prover of course they tend to have uh trusted setups and um depend on either elliptic curve uh discret log type assumptions or knowledge exponent type

assumptions uh as for aggregation they support certain kinds of folding often around cycles of Curves uh and using you know homomorphic commitments the primes the the fields that um are used in the arithmetization tend to be large on the order of 256 bits they are the um scalar fields of elliptic curves and the bottleneck of course is computation now there's a separate um rough category that we can call starish protocols that have become very uh prominent in the in the past couple years so these

um tend to have bigger proofs and are more costly to verify not least because of the size but also in terms of computation uh for the pr they are much faster uh they have a nice recursion story where you can use the same field to ariti the uh verifier that you did to arithmetization uh they support more flexible choice of fields so smaller Fields let's say 32 or 64 bits um for the arithmetization and then often use extensions during the cryptographic portions and uh the bottleneck actually winds up being

bandwidth we we can say um adol vatana having implemented many things that uh what ends up happening is that the sheer cost to move data from a host to a device let's say an fpga uh turns out to be actually more significant than the actual computational cost this is essentially because the computation is now so fast that um uh data movement now becomes a bottleneck okay so just holistically what can we say about the landscape today uh we live in a world where proof recursion is practical uh it it's routinely used in deployed systems and um uh related to this the Poseidon hash

has become a de facto standard that's used in many systems this is because in the prime field setting Poseidon is more arithmetization friendly than um other uh than sort of classical hash functions um and um we we we also live in a world where lookups are becoming on the margin more uh more viable more um sort of efficient relative to the other components and are being used more and more so this will also prove relevant to us uh because lookups um make possible certain things in binary Fields let's say like uh

unsigned integer multiplication which previously um were were more of an obstacle than they are now okay so here's an example of a of a deployed system uh today um due to polygon you can see that it involves recursion and batching and various things so just a couple more remarks about um performance of deployed systems so this is a a benchmark of polygon Z evm we can see that merization uh represents the dominant cost um by some margin uh this essentially entails Poseidon hashing a giant Matrix columnwise uh we note that Poseidon is is pretty slow on CPU maybe fivefold

slower than ketak or maybe maybe a bit more um there is a further phenomenon called embedding overhead which takes various forms but one of them is a um setting where you have a circuit whose whose wires in principle could take large values like 64 bits but which um actually in practice during honest proofs end up only having say zero or one valued wires so for example in starky catch circuit there are a bunch of columns something like 2500 of those the vast majority even you know during on his proofs actually only end up having either zero or one valued

wires so all of these things motivate us uh whether we can um uh design a snark system over the smallest possible field namely F2 the field with just two elements um so a brief historical discussion um what happened to Binary field Stark so the original Stark paper this is due to beneson bentov hores and rabv 18 uh was over binary Fields um since then the topic has sort of disappeared um we can point to a few things that do and don't work this is a very rough overview and there's more remarks in our paper uh

but um I can say that there is an NT analog for binary Fields so-called additive NT this is due to Lin chungan 14 um this definitely works it's efficient it's a very it's a great uh great technique uh fry does work in binary Fields actually the original fry was written in the setting of binary Fields um other things are are much harder to make work right so for example uh there's the issue of relating rows of the trace in deep Ali style Starks uh in the prime field setting there is a there's a way to sort of iterate through the trace domain algebraically by multiplying by a

multiplicative generator in the binary field setting it's not easy to see how you replace that um there is um an idea along these lines in hyper plunk uh we will say more about this later it turns out to be not um quite enough on its own um read Solomon codes including in the binary setting need to have large alphabets at least as large as the block length is so this turns out to be another source of so-called embedding overhead um where even if your if your message has uh binary uh components the code word might not so this gives you a

blow up in the size of your code word uh maybe you can use breakdown with a binary code uh this turns out to have further issues and and actually we we get around this using a so-called packing uh scheme in our in our commitment scheme so uh we will have time to get to all of these uh but um that that concludes for now the sort of historic and background discussions so at at this point I'll Now sort of pivot forward and and um sketch what's what's coming ahead in this talk okay so um I'm going to give an overview of tower Fields how they work why we use them what the

benefits are uh I will describe our polinomial commitment scheme it's a multi-linear polinomial commitment scheme that uses read Solomon codes in the binary setting with no embedding overhead using this so-called packing or Block Level en coding technique uh I'll describe certain um so-called virtual polinomial constructions that let you pack and shift and do other things to committed columns and um I'll describe various gadgets that let you do arithmetic operations like addition and multiplication okay so this is crucial because the difficulty of doing these was often viewed as the main obstacle to or or an obstacle towards uh using

binary Fields so we we can actually achieve these uh finally we'll get to um the arithmetization of ketak which is a critical um uh sort of component in ethereum based applications and finally some performance benchmarks okay so binary Fields what are they how do they work um essentially an element of a binary field looks like a string of bits of some length let's say d which you can think of is 128 okay and um every such string corresponds uniquely to an element of the relevant binary field okay so this is not the case for Prime Fields uh in that setting you have this kind of wraparound um

phenomenon you have so-called non-canonical representations of elements don't have that here okay addition is a simple exor binary exor of two elements okay so what about multiplication and and here we need to differentiate between the classical way that binary Fields get defined uh which involves univariate quotients and how we do it in Towers so the classical way essentially what you do is you take a univariate polinomial ring with coefficients in F2 uh and you quotient that by something irreducible of degree D so let's say 128 okay so the elements of this ring are essentially degree 127

pols these bits then are the coefficients of the relevant pols and um to multiply two of these things we need to multiply binary pols modulo this irreducible polom sorry um okay so H how does it work in the tower case it's it's quite different so I'm going to sort of get to this in stages uh gradually um essentially we start in the same way we take some bit width

which now actually has to be a power of two so again let's just say 128 okay and um again each such string of bits is one of our elements of F2 to the 128 uh but now and again addition is exor what about m multiplication so the story here is a bit a bit complicated so um let's go through it in steps what I can say is that we now have a recursive situation where I can split this string of bits in half into two 64bit chunks and um I I I'm going to claim that these are uh elements of F2 to the 64 so the next smaller field down and that the original thing is indeed sort of made up

of of these two Hales in in a sort of not just a formal uh bit level way but actually an algebraic way okay and and this goes on recursively and we're going to use this to to do multiplication and do many other things okay so if I have two elements red and blue and I want to multiply them how does it go well very roughly what I'm going to do is I'm going to split both into 64-bit halves and then let's say I have a way of multiplying um smaller things okay so you know we still don't know how multiplication works but at least this is a smaller problem so we can we can think recursively okay so if I multiply the two lwh halfs of of blue

and red um you know the the low half of blue and the the higher half of red and so on and so forth there are four cross terms and if I can handle those recursively the claim is that um after doing just some further linear amount of of additions or or or extra work I can then get the answer okay and so a couple remarks first of all we'll see soon that this number four of sub multiplications can be improved to three using uh techniques related to katuba multiplication uh but you know further in order to understand what these additional operations are which is really the the substance of it we need

to describe um a bit more rigorously what these what these things are so just to sketch this as thoroughly but quickly as I can essentially we want to build up a sequence of fields inductively okay so we start with F2 uh what we're going to do first is take a univariate quotient the same thing we usually do but now of just degree two not 128 let's say and this gives us F4 okay so this quotient ring is a field it's a perfectly good field so ignoring its internal structure we can iterate this process we can write down a further univariate quotient ring whose Co coefficients uh come from T1 and quotient that by

another polinomial which I've written down here and um I can keep doing this so you see what the pattern is at each level I quotient by this F Iota minus one that essentially um takes sorry this should be I A minus one uh takes the new Ander it squared multiply by the last one and then add one okay and um the claim is that these are irreducible so they're of degree 2 and irreducible at each stage uh so that ensures that these actually are fields of the right structure um as as desired uh now stepping further into the future it was noted so so this

was proven by vemon um 1987 uh was proven by fan and Par that you can actually uh multiply and uh do inversion very efficiently in this particular Tower okay so this um the complexity turns out to be n to the log base 2 of three so this is the katuba uh complexity and the idea is essentially something like how how regular katuba works but a sort of recursive uh version of it [Music] um so I that that's all I'll say at this point and and um we can come back so just a quick um a couple remarks about why we

use towers and not the classical approach so every prior approach to Binary fields in snarks has used standard Univar quotients why not use them um in in our setting well for a couple reasons first of all we want to support um programs or circuits in which other data widths appear for example elements of gf2 to the8 the 8bit binary field this shows up in um AES and and grol and various hash functions like that um but moreover there are other reasons involving the internals of our commitment scheme so for example um the read Solomon code we use will have an

alphabet on the order of F2 to the 16 so we want to be able to work efficiently with these intermediate Fields right so um now it's true that regardless of how I Define F2 to the 128 these subfield F2 to the 16 will arise in the Big Field uh the question is does it arise in a sort of computationally tractable way uh if I Define it in as a univariate quotient it's just not obvious where F2 to the 16 even lives inside of this big field right so in other words even if I give you an element if you want to even decide whether it lives in the subfield

F2 16 or not um it's not completely obvious now there's some computation you can run that would decide this but you can't just read it off of the bits um whereas in our case the elements of the subfield F2 to the 16 are easily identifiable as the uh Big Field elements whose you know first 16 bits are non zero but the rest are zero this can be determine just from one uh linear read over the the bits essentially uh there are some further subtle problems around packing so if I want if if I have 16 bits and I want to assemble those into an element of F2 to the 16 um how can I how can I do it well

in the classical case I can do this but the complexity might be something like a matrix Mt of size 16 by 128 whereas for us I can just write down the 16 bits in the first 16 positions um a really um kind of non obvious but really critical point is if I have a small and a large field element uh an f216 and and one of these can I multiply them faster than um a general multiplication so in the classical case the only thing I can do is embed the small thing into The Big Field which has its own cost by the way and then just multiplying The Big Field right so you're not exploiting the fact that um that one of the operands

actually has sort of less information uh and then sort of reversing the the the packing operation so these all end up being really crucial uh in the classical univariate quotient approach they all are costly and for us they're all free okay so this is pretty important and we'll keep showing up throughout the rest of of this talk okay so error correcting codes play a crucial role in in our work and there there's a ton to say but the very very basic thing I can say is that we we target read Solomon codes these um have good distance relative to their rate their their um MDS um Now The crucial thing about readed

Solomon codes is that their alphabet has to be large at least as large as the block length of the code so there there is just simply is not a binary read Solomon code for example um the alphabet's going to be something like F2 16 uh this makes it necessary for us to do things like packing in our polinomial commitment scheme um they are efficiently encodable in the binary setting so I've already mentioned this result okay so let's um charge ahead into the sort of inner core um component of our snark which is our multilinear polinomial commitment scheme and again um yeah so I I'll essentially skip

through this you know why can't you just do something simple where you just use breakdown over F2 and essentially there there's an embedding overhead problem where if I take a message whose components are just bits and use breakdown then um a priori the the code word uh could have entries in in in a huge field so there could be a 128 fold blowup um even even if we use RS um at least the alphabet here is small but the blowup could still be up to 16 fold so again we want that to be onefold no embedding overhead there's a sort of technical security problem around uh can we guarantee that the extractor actually extracts a polinomial over F2 and not

something larger right so the prover should not be able to get away with uh pretending to commit to something over F2 but committing actually to a polinomial over a bigger field okay so now uh I'm going to get into the sort of key packing technique of our polinomial commitment scheme this is a kind of technically involved strategy that lets us use a plain read Solomon code um but nonetheless not have embedding overhead and this is described completely in the paper so I'm just going to give it a rough survey and you we can always come back to this but roughly um here's a story that we start

with the prover has some Matrix these are the coefficients in multilinear lrange basis of some polinomial over FS2 uh M by m let's say um so instead of uh using breakdown directly which would stipulate that we encode the rows under some error correcting code we're going to do a packing thing okay so we're going to proceed in each row we're going to proceed write words and actually bundle chunks of 16 bits into F2 to the 16 elements okay so now I have a new Matrix of the same height M but 1/16th the width and the entries now are elements of F2 to the 16 instead of

bits okay so the question is can I now pretend that essentially this is the polinomial I started with and apply breakdown now so this would involve uh Reed Solomon encoding these rows uh Merkel hasing them and and so on um the answer is is not quite um it it turns out to be um more difficult than this because of the compatibility of the various fields and this is a kind of um technical segment that I'm I'm going to Breeze Breeze through this uh but roughly uh there's a naive way of encoding this that turns out to be wrong right so this is the sort of value T

Prime that the prover sends to the verifier and the problem that we encounter is that it's essentially of the wrong shape it's it's too long its length is M whereas our code uh had message length M over 16 instead right so the tempting thing to do where you view F2 to the 128 as as a as a vector space over F2 the 16 uh sort of involves segmenting these elements vertically in chunks of eight and then viewing each slice as a read Solomon message of length M now this turns out to be not uh what you want so uh there there's a kind of data layout subtlety that you need to um sort of come to terms with uh that we

describe in the paper where essentially what you what you want to do is proceed um horizontally you chunk this message T Prime into chunks of 16 and um how many chunks are there of course M over 16 uh and then it's a of bitwise slices that need to be our read Solomon messages so it's actually this thing that you want to read Solomon in code and this is exactly the shape you you want um it's it's a vector of F2 to the 16 elements of length M over 16 uh exactly as we expected and you do this 128 times uh so this ends up being um the right thing to

do um this is kind of the key uh key idea of the packing scheme and this is described in the paper uh so um going on um I'll now start describing uh what happens next so we now assume that we have the ability to commit to multilinear polinomial over F2 and um and then evaluate them so what do we do with that uh that's what I will describe now so in the paper we describe a number of ways of uh of working with these things um that we we call virtual pols and um yeah so let's let's get into it

the first is what we call the packing construction so the idea here is that uh from the view of the verifier let's say this is essentially what's committed to is some long column of bits and um what we describe how to do is that um what what you want to what you you might want to work with in practice is a variant of this column where instead of uh having bit entries you actually have 64-fold fewer entries but those elements are elements of F2 to the 64 and when we say a virtual polinomial what we want is to be able to work with this thing on the right as if it had been explicitly

committed to even even when only the thing on the left has actually been explicitly committed to and um we give a oh so in in the paper we give a way to do this that essentially uses sum check right so um what we find is that uh if we want to evaluate this polinomial as if it existed uh at some at some point we can write down an expression that uh involves a sum of of this polinomial uh entries in in over a certain Cube um which is sort of exactly the U setup that you need to run some check and um and uh so you can evaluate the

virtual thing using a sum check over the physical thing uh and the sum check is is very efficient for the verifier it would be just something like six rounds uh in in the case of of a of a 64 fold packing we have a further construction called the shift construction uh which also ends up being very important in applications so um again so we start with a raw emitted column we now want to uh work with a further column which now has the same shape so same length and has F2 elements but has been shifted uh circularly let's say by some amount of position so maybe three or actually this number can be totally arbitrary um and so so this is is an important

problem this was sort of posed by by hyper plun and we we do give a way of doing this for arbitrary offset uh the complexity uh I'll I'll I'll say a few things in a second we we actually have a further variant which is a sort of uh chunk wise shift where I can break this thing into chunks of 64 and shift each one individually by say one position or five or just anything uh and that shift can be either circular or it can be a simple shift with zero filling up or down uh we have ways of doing this the the complexity again is is actually independent of the number of positions you shift by it only depends on the size

of this block which in this case is 64 or in this example was uh you know 2 to the L uh uh the complexity for the verifier will be something like log of the block length so six or or l or something like that which is which is quite good um so why is the shift construction useful so this is a a hint at what's to come it will be useful in in our gadgets for addition for example and multiplication and also in Kack why well it lets us write down constraints that involve uh columns and shifts of columns but without committing to those shifts right so for example in the case of

ketak one thing you want to do is uh sort of check that the next round State uh the main cat state is equal to the output of of the last round under some um some operations what we can do is sort of uh zero check some a shift of the current state with with the output of the last state uh without separately committing to the shifted current state so um this is is very handy for for Kack and we'll see other examples um I already mentioned this um how do we do it uh just a very rough look into what what happens internally

we are able to write down a b variate polinomial um called the shift indicator polinomial uh such that when the arguments X and Y are in the cube uh this thing acts like an indicator for for the kind of offset property essentially it it returns uh value one if and only if the uh the binary strings X and Y differ by an arithmetic addition of o o o being the offset modulo the the bitwidth um of these binary strings uh the key fact that we need to describe in the circuit that sorry paper is that the circuit of this is um only o of B sized so this is is is an interesting fact

that we go in depth into uh so this adapts an idea of SE theor and wobby uh where in that case the offset was just one okay so um speeding ahead um I I will now say a few things about um our gadgets so um let me just pause here and and and make a remark about uh about lookups right so I think a year or two ago if if you had asked somebody um you know what goes wrong if you try to do a binary field snark a lot I think many of the responses would have been something like the the complexity of

your arithmetization will blow up because you now cannot add or multiply natively in your field and we claim that actually that issue is no longer a problem now first of all even in the prime field case you have problems with range checks and most Pro protocols actually you know don't just add 32-bit things they break into into say 8 bit Limbs and then natively add those but you you still need to combine them and and range check them and things like that um but the other factor is the um the availability of lookups which which we use in our multiplication uh specifically we we

describe a variant of uh of of the lasso lookup in our paper uh that works for binary Fields okay so how can we do arithmetic addition so what does that mean so again we have a committed columns X and Y which which contain bits and a further committed column Z let's say and the thing we want to check is whether if you proceed through these columns and you segment them into chunks of say 64 bits it should hold for each chunk that um the bits of Z are the unsigned arithmetic addition of the the bits of X and Y and that should hold chunk wise okay so what we end up doing is committing to a single first further

auxiliary column carry out okay and um what you'll notice here is that carry in is a is a onstep shift down of carry out okay and this is kind of the key fact that um we know how carry in should relate to carry out it should be precisely a shift with with zero filling okay so the carry in should be zero at the first bit of each chunk um and we don't need to explicitly commit to carry in because we have a virtual polinomial force it um and then we we now need to write down some very simple constraints okay so Z should be the bitwise addition so over F2 um so modulo 2 of of x y and carry in

um and then carry out should be correct right so carry out should be one if and only if at least two of The Columns x y and carry in are are true um and and this also you can write down as a simple constraint now interestingly you know carry out is is on the left hand side and actually involves carry in even though carry in is is is sort of virtually depends on carry out so this is is totally legal so just two constraints and a shift okay so how does um multiplication work so this is sort of technically involved in in very interesting story that I'll I'll describe in in a bit of depth okay so we start with X and Y

which are column really columns but I've I've I've rotated them and and actually these are going to extend horizontally but I'm zooming into one uh chunk of let's say 32 bits here okay and we want to multiply them now this is going to bring everything together essentially this is going to bring together shifting uh packing and and um also addition in in in a pretty interest and lookups okay so what we do we're going to split both X and Y into limbs so you can think think of these as being 32 bits and the limbs as being uh eight bits each let's say okay and the very rough idea is that we want to run through the schoolbook uh classical method where each limb by limb product

we handle using a lookup and the rest we handle using additions and things like that okay so let's proceed uh in the very first step we're going to um have have this kind of setup so I'm going to I'm going to do nothing to X I'm going to shift it by zero and I'm going to um what we call saturate so this is a saturation operator it's a it's a third uh virtual polinomial on Y at the zeroth position so this is y zeros everywhere four times and then and then X and um If I multiply these two I get a double width cross term and then another double width cross term and so on and so forth uh now the first key idea is that

essentially using one um look up I can guarantee that uh these cross terms are correct okay that um this green thing is actually the unsigned 8bit product of x0 and y0 and then this one for X1 and y0 and so on um now there's a key kind of efficiency idea here which is that how many how many green uh pols do I need to commit to is the answer four well you can do better right so actually you know some some tricky animation here so by sliding these things up the key idea is that um if I look at the even cross terms and the odd ones the evens

have no overlaps and the odds have no overlaps so instead of committing to um four things or however many limbs I had I can commit to just two it's a constant number of green uh green uh polinomial per stage of the schoolbook algorithm instead of L so this is very good for efficiency now um let's keep going some um sorry these got shifted a bit so uh keep going here um now I shift X by one so it's zero here at the first position and then x0 X1 and X2 I saturate Y at

one so now it's y On's everywhere and again I do the three cross terms use another lookup to make sure these are correct and again this can be moved up um keep going through this now I shift X by two so I have zeros here and here and I saturate Y at two again we're we're we're doing the elementary school method sort of Step by Step here okay so now I have I have cross term for x0 Y2 and X1 Y2 uh another look up and then finally in the third position and um a final lookup so now putting together all the green things we had this from the first stage this from the second and this and

this and um the claim is that by applying the addition Gadget to these we can finally get the actual um the actual product okay so what is the complexity of what we just did uh if L is the number of Limbs per word um we had to do L lookups one per stage we had to do something like three times L commitments so essentially committing to the green things and and there there's one further that it's kind of technical um L zero checks essentially you're checking whether these um the the the bitwise sort of lifts of these are are are in agreement with the thing you looked up um and then some

additions okay so the key point is that the number of invocations of subprotocols was order on the order of L the number of Limbs per word and not something like L squar okay um so final I guess thing is that um how does catak work so I I don't have too much detail here but I can say that we have an arithmetization of ketak that's very efficient it essentially commits to um you know 60 raw Columns of bits um each catak state is is is sort of split vertically so we have 64 um rows per katex state um if you put this all

together we can do one of this sort of core catak F permutation in in around 1500 rows um if you sort of allow a full Trace size of 2 to the 28 then um you can commit to you can you can fully prove uh 164,000 catch a okay so we have some benchmarks um so I guess just dumping the benchmarks here you can essentially see that we are able to prove in single threaded and software we're able to prove um you know commit to a 2 to the 28 size Trace uh very quickly so this is something like

um you know on the order of you know a couple orders of magnitude faster than than prior works for F2 elements right so the key is that our our work is indeed exploiting the um small coefficient size whereas these essentially are not and then we we also have the benchmarks here for F2 to the8 okay so I guess that uh concludes the sort of um official content um I I have a bunch of sort of auxiliary content if if we want to go into further detail into anything um you know I guess we're we're running a bit early um should I open it up to questions now or or how do you all want to

proceed so I mean time is not a concern for us so you can extend as much as you want it's more about what you want to do in regards of questions we usually leave time at the end of the session for questions again up to you if you want to dive into something else that you think is worth uh showcasing uh or you directly want to jump into into Q&A is is up to you let's do Q&A and and let that drive the sure sure sure sure cool so yeah let's go ahead and open it up so anyone that wants to speak can just unmute himself for herself and and ask uh taking profit of the fact that

I'm already speaking I I will ask a question um so my question was well I have two of them but I will for now just ask one uh which is relate to this lookup s section that we were looking at now um are the lookups fixed or dynamic because if they are fixed and you are doing operations with two to the 16 uh based elements you have a table of size 2 to the 32 to cover all of the possible operations that those have because you have them permuted so yeah so okay so if if I'm understanding you the comment is about the size of the lookup table right so indeed it's that so our limb size would

be eight let's say right so with Lim size of eight your table size would be 2 to the 16 yeah with with size eight definitely I thought you were using size 16 here hence why it looked so big basically so yes so yes indeed it's true that if our limb size were 16 our table size would be 2 to the 32 which is probably too big so I I'm in agreement that in practice you would want a limb size of eight um I think it's possible that that uh a 2 to 32 sized commitment of 32 bit elements would be practical in some cases the key thing being that our commitments are smaller because we're committing smaller sized field elements

and we're not paying the embedding overhead so for example like we show the proof sizes uh in the paper for polinomial over F2 up to size 2 to 36 um but that's because they're single bit elements so uh but as Ben said we're we're sort of predicating the multiplication on the idea of 8 bit limbs right now have you done any further Explorations on on that like benchmarks or even even estimations on whether would it be worth it or which are the cases on which you foresee that it's worth it to to towards the direction you mean to the direction of

increasing the limb size exactly yeah to having having a table of two to 32 which is probably the theoretical maximum that we can aim for nowadays yeah um I don't have anything concrete to say about that it would depend on applications so I imagine if you're doing snarks to prove elliptic curve operations and doing Big Field arithmetic where like you're you know multiplication is a heavy operator then you might want to do that um it sort of depends on on the application as Ben noted like our catch circuit and all of the hash functions that we're targeting make no use of lookups right now um so yeah I don't have anything more

fair enough that makes sense do you have Benchmark of kitu not yet we're we're working on that we have a thorough description of the arithmetization in the paper which is more complete than uh than what's in the slide but we are working on a full snark to prove the catch a circuit and we'll hope to have you know results on that and in a month or two right so we can tell you exactly how many columns what shape the columns and then what you know zero checks and things you need to do but we just haven't implemented it yet yeah I can also say that we we did run some benchmarks on looking at our sum check

efficiency uh and like basically did bench marks of like if we were to do these sum Che operations for you know this degree of pols that we need and for the number of multiplications uh and came up with an estimate that we could do 5,000 catak FS per second per core um and that would be basically our Target right now taking into account the the cost to do the polinomial commitments to F2 elements and the cost um to do the sum checks for a 2 to 28 size Trace in what Hardware is that because that that that is almost fast than running it natively without proving

anything in the in your machine um that was on the uh well that's that was single threaded um I guess we should double check that but that's the estimate we came up with um that was on AWS GF or uh like a c7i you know probably metal or 32x large instance which has a an Intel CPU um we're using the Intel CPUs because they have particular instruction sets that make the binary field arithmetic efficient W that's awesome I I I will read some

questions that I see in the chat uh W is asking what is the space SL memory efficiency versus things like fry yeah um it it depends on the application so the what our our major claim here is that for many circuits of interest you actually are committing to elements that are much smaller than than the field required so first it depends on the application but like for things like these hasher circuits where you're doing a lot of bitwise operations the memory requirements are we could like sort of get a theoretical up to 32x Improvement because uh we're only

committing you know the bits themselves and basically where you pay for this is in the sum check protocol but the memory requirements uh it actually doesn't blow up the memory requirements because uh there's basically some uh techniques for doing some checks over small fields that we're able to Le leverage so that actually makes it um you know more of a compute bounded uh computation and sorry you asked about memory requirements versus bet what was the compared to fry right memory requirement fry oh oh sorry uh we and then are you asking about fry over binary fields or fry it's quite noisy where I am right

now but I'm curious in general you mentioned very early on the conversation that there Hardware limitations that try to move from Custom Hardware it would cause issues for you so I'm thinking in terms of f efficiency doesn't makeing much easier you to have hard sorry that was hard to hear yeah the mic doesn't sound really good why maybe you can write it uh [Music] down yeah I think I think essentially the answer yeah it I guess by fry I'll interpret you to mean something like you know deep

Ali right which uses fry as a sub routine um I think I think it essentially comes down to what you're comparing to are you comparing to um fry where your circuit has arbitrary um 32-bit values or you know fry deep Al where your circuit has one bit values in the latter case we're essentially going to do better by something like a factor of 32 which which we think is the more practically Rel comparison right um another thing to note that maybe wasn't explicit is there's a um even in the binary field

setting one of the really nice things about breakdown is that we can shape our matrices so that for practical sizes we can have block lengths of at most 2 to the 16 which lets us use the 16bit field versus if you're doing fry it would make more sense to you're probably committing uh or you're you're probably encoding with a block length that's greater than 2 to the 16 because um it depends how much you're batching but that would sort of make sense and and so in order to just do the read Solomon encoding itself you would need to use multiplications over the 32-bit field which are um you know scale something like uh I mean I

have the the exact number somewhere but more than double the cost of yeah more than double the cost uh how much of a speed up do we achieve using Intel gfn uh it's significant um that said we've put pretty much all of our CPU optimization efforts into the implementation with the GF instructions so it's an interesting question we have uh We've developed like algorithms for kind of um essentially doing vectorized field mols which recursively call more vectorized field mols so if you you know we

actually maybe Ben do you want to go do you have anything deeper on like how to do multiplication or uh slide wise exactly but I scroll back to the the field mold slide I mean it doesn't need to be a SL it's SL format for the recording or anything you can just show whatever you want guys whatever is easier for you to to show it I I guess uh what what I'm trying to say is that if you do this recursive decomposition sort of as uh as scalers like you you know Ben showed a version where you have to do four

recursive multiplications and then there's actually another version where you only do three recursive multiplications and one recursive like multiplication by a special constant uh if you sort of do that naively non vectorized um it's more expensive but we also developed an algorithm that essentially can do vectorized multiplication of field Elements which um will recursively reduce to a vectorized multiplication of this the subfield elements and this is all based on the idea that like you have a string of bits let's say it's a 32 bits and you can sort of cast that into either an F2 to the 32 element or a two wide Vector of F2 to the 16 elements or

a four Vector of F2 the8 elements or so on um maybe shot at this question about the code word has to work over maybe Nicholas if if you can explain the question no it was just like in your explanation you were saying the code world is f 26 and is there any reason for this or just like viable or just prob sake of explanation so okay I'm not

sure I understand but it one fact is that the alphabet of Reed Solomon in our case has to be at least F2 to the 16 or larger so the elements of your code word um maybe the comment was if you start with a message whose entries are bits and read Solomon and code that then the entries of the code word will be elements of F2 to the 16 is that the remark right yeah so the reason that is essentially comes down to how read Solomon works right so uh the re the alphabet is going to be F2 to the 16 it's like mathematically essentially what you're doing is multiplying this message by a matrix whose entries are in

F2 to the 16 and after you do that the the vector that comes out will have larger entries so this is essentially a fact about the alphabet size of of readed Solomon codes maybe just to to say it slightly different and to explain why we use the term embedding overhead like if you wanted to uh use fry uh for example uh what you would do with with you know bit entries so your elements of your encoded of the polinomial you're trying to commit are bits zero or one you would embed them as elements of F2 the 16 and that would effectively be a padding with with 15 more bits and then you would multiply by a generator Matrix which has elements from F2 to the 16 so

that's where we get the term embedding overhead and the you know purpose of uh our polinomial equipment scheme is to be more clever than that yeah I have one more question uh related to the packing construction uh specifically on how are you performing the Su check uh four elements on the two to the 64 range on the on the two two to the 64 field when indeed you are not in that like this kind of I know you're not yes yes yeah you're referring to this setting how do you perform the

check here yeah exactly okay so maybe now actually I can pull up the other slides very quickly am I am I still sharing do you all see this yeah yeah we can see okay so

essentially essentially this is the the relevant content right but just to say it in words um the the the polom here actually never really exists it's actually virtual right so rather it's this polinomial that exists and the thing that you Su check is um is a certain a certain sum involving this polinomial right so it's actually a polinomial whose entries uh live in F2 or or yeah not quite it's a it's it's a product of your original F2 polinomial with this um with this beta okay so this beta is uh is is a sort of special basis

of F2 to the 64 over F2 um so this this ultimately turns into the thing that you you need to sum check uh now there's a further algorithmic question which is how do you efficiently sum check something whose entries live in uh in a subfield and that's a sort of further topic but maybe I can ask you which aspect you would like to see more info on this is interesting and also at the same time the reply that you that you gave me was pretty clear I'm just wondering how was this beta derived like what process do you need to follow such that you end up with a beta that is good

for you to perform in the S over okay so so the beta I I I I skipped this material at the beginning but the beta is a is an intrinsic um sort of part of the tower field the the beta is is a special is uh a sequence of elements of f 2 the 64 which um give you a basis over F2 of F2 to the 64 so specifically these are essentially the monomials the possible multi-linear monomials um any element of F2 the 64 looks like a sum of these so these are constants essentially Global constants

that um depend only on the on the tower field and um and exist sort of forever and and the key observation that makes packing work is that um in order to write down an F2 the 64 on the level of bits I just concatenate 64 bits but that concatenation actually is algebraically Meaningful it actually corresponds to a linear combination where the coefficients are my 64 bits and the things you're combining are these betas that are um sort of vectors they're elements of The Big Field which form a basis um so it's this algebraic expression that actually captures the packed thing and and then the further

observation you make is that this this expression is itself a sum and so is amenable to the sum check uh and that's kind of so if you write down this internal thing then some checking this turns out to be enough where here beta hat is is a kind of a a weird trick it's actually taking these betas which are just an array of elements but viewing them as the evaluations of some multi-linear and then taking its multi-linear extension so we're we're viewing beta now in kind of multiple ways on the one hand it's a basis of this field over F2 but it's also the evaluations of a multi-linear which we call beta hat and um you know beta hat is sort of efficient to evaluate and and

this lets this lets the sum check work and just just two more comments on that um beta actually had has like a very simple descript like I can tell you that all the beta elements are Hamming weight one and the you know depending on the indexing the one is at a very particular place and that's just an artifact of like the particular tower construction we use uh and then the other thing to to just observe here is that the sum check that we're doing is actually a very small sum check it's it's over like 64 elements it's not like like you're adding another big Su check instance or something thing which we would be ex more wary of so the complexity of the sum check depends only on the Block size that you're packing not on the column

size so in this case it would be something like six rounds not you know L rounds or something like that right that makes sense that makes sense yeah a quick question still on this slide maybe uh do s or the polinomial that you're some cheing over this is of degree 2 right so the t is degree one one and beta is a degree one okay thanks so well well degree okay so degree 2 in what in in capital x this is uh yeah yeah it is yes yes yes absolutely

thanks any other questions anyone has okay so I think we can wrap it up here uh is there any last thing that you guys J want to mention um I I should have a useful links slide maybe I can just jump to that if I still have it uh sorry give me just a second um yeah I guess just to say like we have uh we're working on a software Implement an open source software implementation of this called Bas uh you know developing that like uh you know things are getting

pushed in real time we're working towards full snarks for various uh hashers of Interest including Kack gral and Shaw 2 um and certainly when we get those done uh we'll be publishing the benchmarks on that and I think that'll answer a lot of people's question about concrete uh performance um there's more details in the paper and we'd love if uh you guys have any feedback that you can share with us on this presentation um you know uh we'd love to hear it because we we want to do our best to educate the the community about about our work so yeah and I I'll say that um you know

thanks again to to to the audience and if I welcome any uh questions or comments by email so anybody either here now or or watching in the future uh feel free to email me uh with questions oh and last plug we're uh we're actively hiring cryptography Engineers to help us build this um we think it's going to be the best snark in the industry so it's an exciting time to join us and if anyone's uh Keen to do that uh you can reach out to me directly VI email I'm jimo jimo W vatana doio or if you have referrals cool thank you everyone I add the the emails in the in the description of the video so that you can you can basically

reach them uh guys thank you very much for for doing this presentation and spending time with us it has been amazing and and really insightful so yeah once again uh show our appreciation for you coming here today and have a nice day everyone enjoy enjoy the rest of the day cheers thank you all