zkStudyClub: HyperPlonk (Binyi Chen, Benedikt Bünz)

Transcript

hello everyone welcome to this edition of ZK Study Club today we're very excited to welcome Benedict Boons who's been a guest before and also Benny chin on their joint work that they also did with Dan Bonnet and Jin FEI Jung uh of espresso systems uh and Dan is of course with Stanford University and that the title of the paper is hyperplunk and it's talking about their work uh optimizing the Planck approved system so if any with that please take it away thank you Alex so yeah today I'll be presenting hyperplunk which is an adaptation of the famous plant proof system that's adapted to the Boolean hypercube using Market linear polynomial commitments so this scheme has linear time proverb and also has very nice

support to the high degree customer Gates so also it's high paralyzable and Hardware friendly because it removes the use of ffts so before getting to the details and outstanding our results let me really quickly go through the Notions of snarks and speeding blocks so our main goal is to building a pre-processing snarks which is basically a scheme that enables the approver to convince the verifier that he knows a valuable internet to certain public circuits and goes to have small communication and the small verification cost so it consists of three algorithm in the setup phase this preprocessor will take as input circuit and output some public parameters and then approval given parameters and an online witness

to the circus will generate the proof and send it to verifier and verify after a signal proof will check it and output accept a reject it will help it to be complete meaning that all is Proverbs should always succeed and will hope to be noticed on meaning that if verify accept this proof then it must be case that proofer not exactly knows the online witness okay and also create super snarks and you also need some succinct property meaning that proof size and and the time for verification are all very very small meaning the sub linear to the Circuit size or even logarithmic to the Circuit size so that's the snarks and I want to say that many recent snarks were built using

the following framework so what they do is they start by designing a interactive protocol in the ideal world called polynomial IOP and then the compile and there are some many many examples like Planck or sonic or modeling or liberal and many more they are offering this category of poly IOP product codes and then after that they will try to compile this ideal protocol into an interactive extinct arguments by using a crimp throw primitive called the polynomial commitment schemes an example includes the famous kdg commitments and also in the product arguments based ones including bulletproof and also fry based one and also the dark which is built

from groomful on order and there are many more so this framework is like the very good property of this framework is that highly flexible and modular meaning that you can just combine any one of the polio Op with any one of the PCS and you attend a new snark for General circuits that has different kind of features and I will quickly remind you what is probably IOP is essentially it's just an interactive protocol well in each round the proverb or we'll just send some polynomials to the verifier and the verify will reply with some public random challenges and then finally the verifier can also query some some evaluations on these

polynomials and check certain relations holds between these evaluations and we'll also note that this is very general you don't need the polynomial doesn't have to be always univariate it can also extend to multivariable setting will there are much the polynomial has multiple variables each variable has different degrees so of course this kind of Ideal protocol is definitely not a snark right versus interactive and also the polynomial is so huge and so too large to be sent and it's too costly for a verified to just evaluate the polynomial himself so we need some crypto Primitives to compress this polynomial and enable some efficient evaluation checkings at least this so-called polynomial commitments so

given the polynomial with some boundary degree the proofer can commit it to some bit strings which lens is independent of the degree which is very short and required to be blinding meaning that the prover can not cannot open these commitments with different types polynomials responding degree and another feature of PCS is that it allows the approvers to convince the verifier that certain evaluation holds true which is with respect to this committed polynomials so the proverb will generate a succinct evaluation proof that is knowledge sound meaning the same property like meaning the verify verify accepts that means that prover must know the the underlying

polynomials meaning that there's some way to extract these polynomials from distributor okay so yeah that's that's the background as I think most of audience already familiar with backgrounds so now we are ready to State our main results so the key result we have is we build a new multivariate for the IOP that adapts this Planck Universe IOP into the Boolean hybrid Cube using Martin linear commitment schemes to obtain final snarks so the good feature of this scheme is that first is fully linear and highly paralyzable because we fully remove the use of ffts which has as costly linear complexity and it can be hard to paralyze when the instant size is large because it has really

complex memory access patterns so this makes it favorable for applications like CK row Apple CK evm that has like gigantics like very very large certificate size so the second thing and I think even more importantly is that it gives a really good support to the high degree custom Gates so what is custom gate custom gate is one of the Planck's like really nice features that enables developers to design their own gate types for asthmatic circuits so that they can minimize the circuit size for their own applications I take a just take example so with the help of high degree gaze you can express a living elliptical curve addition for example with only two constraints where

you use r1c as it can take many more constraints so however that's this kind of custom gate is not very like there are some limits in the sense in the case of Planck because it's in the Planck the number of group exponentiations being conducted is proportional to both number Gates and also the degree of the custom Gates so it's like the multiplicative relation in it so which limits the feasibility of using a very high degree gaze in in the in the design and in contrast our polio P like after plugins with the with the PCS like only has additive complexity with respect to the number of days and the degree gaze the

degree of the gates so it allows us to use much higher degree grades without like affecting the performance of proof system so after plugging this uh PRP with the PCS like a variance of kcg in marketing and setting we also have very good concrete proof size for the resulting synarks it's basically like six kilobytes to seven kilobytes for most of the like possible application of the case size and along the way will also build some efficient special evaluation methods and made these things to build your knowledge if you want in the marketing setting which is also non-trivial and it can be of independent uh interest I think is there any questions on the in the chat

uh oh okay no no okay thank you okay so beyond that we also uh extend is hyperplunk to also support lookup Gates which is a very important custom Gates basically we extended the famous pull up top methods to the Boolean hyper Cube and in the martini setting of 10 the first linear time look for polio op and finally we also construct some new multimedia commitment schemes that can be plugged into a hyperplunk plop to Pretend some new snarks with different nice features and one highlight is that we improve the recent Orion ptcs which has really fast prover basically the

proverb complexity is like it's only minion number of field operations plus some very fast hash operations and our contributions that we preserve is linear time improver but in proof is proof size from several megabytes to several kilobytes this is almost like 1000 factor of savings for the proof size and beyond that would also do some very simple fry based marketing commitment schemes which is I think is simpler than Virgo but like with some using some other Tech ideas and yeah so that's uh that's the general uh contribution we have made and uh the rest of talk will be organized as follows so I first explained how do we adapt the Planck to the Multiverse setting and build a much

very polynomial IOP and then I'll explain how to handle uh the high degree Gates or and and do the batching for for the kids and next are describe techniques for supporting lookup and finally I give some very Grand Source evaluations and benchmarks okay so let's get started for the hyperplunk part so before describing the hyperplunk polio P I'll quickly review the workflow of Planck so so given our arithmetic circuits the first step implant is that I compiled the circuit into your Trace which is basically a matrix and then encode this Matrix using some univariable polynomials interpolate them

basically and then I need to prove that this trace or these polynomials exactly encodes a valid circuit computation meaning that circuit will output 0 like communicate values and this is done by two checks versus the so-called gate identity check meaning that every gate value are consistent meaning the inputs and output are correct with respect to this addition or multiplication case and second I'll need to do a wiring identity check meaning that different gate values should be consistent say identical if they're connected by the same circuit Wiles so I'll dig deeper on each step in the in the following slides so let's first see how do we do the encoding so given a fan in two

arithmetic circuits for example with n gaze what we do is that we translate this circuit into Matrix with n rows and its three columns so where each row now maps to your Gates Right and each column maps to the left and and right inputs of the gate as well as the output of the gates so for example there is a gate 0 here which is the addition gate with input 5 6 and 11 so that the First Column is five uh so first row is 5 6 and 11.

so this is the way we we transform a arithmetic circuit to a matrix which is so what so called trace and then the Planck uses the universe polynomials to interpolate these Columns of the Matrix uh so that it can conveniently conduct some polynomial equation checks later so you can see here I to the First Column I use a polynomial L to interpolate this these column values into a multiplicity group in this in this universe polynomials will Omega is the roots of unity and similar signals for R which is another polynomial and O and now the key things is like there's some some caveat

of this kind of method is because that in order to interpolates this uh values and because in the like underlying product or you need sometimes you need to use the coefficient form of the polynomials so the encoding here you need to do some like Fast Forward transform here which we'll call fft or NCT and the first fft has complexity and log n and also it requires the use of some fft friendly Fields meaning that it has a really large multiplicated group inside it so this makes like something bad like not very good when the inside is super huge and oh yeah as I want to say that it's less paralyzable because it

involves very complex memory access patterns but I would say that this is not a big issue like plug is really really useful and widely used in the world because like in because fft only involves field operations it's much much more efficient than the group exponentiations however because you see that like fft is cost in linear so when n keeps growing this becomes a problem like for example when n comes to this like 2 to the to 20 it becomes significant part of the post when it comes to the 30 is even more significant it might become bottleneck and also as we said that it also hinders the hardware

optimization because it's very hard to do parallelizations so given this we address this issue by interpolating this Matrix using marketing polynomials and interpolating these values using Boolean hybrid Cube instead of a multiplicative group generated by roots of units so you can see here I interpolate 5 into 0 0 5 into 0 1 and 1 0 and 1 1 so this is a Boolean hybrid cube with Dimension two and similar things holds true for R and O and this polynomial can be interpreted as some polynomials uh with with two variables so the the advantage of using this kind of encoding is that the underlying

protocol we used or use the polynomial index evaluation form there's no need to do anything about coefficient and evaluation form transform so you basically need to do nothing when you're doing coding and here I want to emphasize that now like in this margin linear polynomial there are log n variables and for each variable the degree is one so it's basically a linear English variable and we also mentioned similar to the universe I think there are also many polynomial commitments works for multinomial polynomials including kcg base right-based bulletproof and Dory there are many more and most of them are also relatively efficient meaning that proof size and verification or o log n

with very good constants so I wanted to say that this kind of idea is not brandly new actually like Spartan and clocks they also use some similar ideas to interpolate weakness into Martin linear polynomials but difference here is that they what they work is they work for the another type of construction system called r1cs rather than the plant constraint system okay So after talking about encoding let's see how we like make sure that this Trace is correct and is like encodes value computation so the first thing is that we need to ensure that this Trace encodes uh like it's it's consistent with each case and this is done by

checking a unified equations holds true for every point in the interplates that edge so basically we need a way to unify so if we call we have addition Gates and multiplication Gates so we need a way to unify both games into a single formula and plunker address it by introducing some pre-processed polynomial for the selector polynomials that encompose different gate types so basically if there's for the ice skate if it is an addition gate we set it to be one if its multiplication gate with that you put zero and now we only need to check that for each point in this in this interface set the following formula is evaluates to zero and let's see why I think post post addition Gates and the

multiplication Gates so when there's an addition gate we set s to be one so you can see the left hand side is activated and right hand says inactivate turn off so we obtain a constraint about the addition Gates and similarly if s equals zero equals zero we obtain a multiplication location Gates like the right hand side activate the left hand side is turned off and we constrain the multiplication gate so that's the idea of Planck to unify everything in a single formula so that now the problem is reduced to basically a zero check relation where one wants to check that the formula holds true or say a formula evalues to zero for every

point in the set h and the plant view is a protocol for this zero check relation by showing that this polynomial is divided by a zero polynomial that values only set h so that if F evaluates to zero on everywhere in H or equivalently by showing that f is the product of the zero polynomial and the so-called quotient polynomial here okay so that's the ideal Planck however now we we use marginal polynomials and everything is now embedding Boolean hypercube and though there is no such easy Collision check now in the multimeter setting rather than in the universe setting so instead we still can use a standard trick to transform this digital check

actually into a very classic sound effect protocol and solve these issues essentially if f is the value is zero everywhere in this cooling hypercube then we can interpolate these coefficients and say oh yes the corresponding polynomial over this point of this variable Z is actually identically zero and then we can use the very famous throughout the limit you say okay then then that means for a random Vector d uh did the corresponding equation should be zero and this is exactly a sum check which check that the evaluation of some polynomials over the Boolean hypercube is exactly some certain values like zero and even better

using this kind of idea using this some check protocol can further improve the prover time from closing linear to linear because we're no longer use fft is or even the fft friendly fields okay so that's about gate checking and the other thing is that we also need to ensure that different gate values are consistent if they are connected by the same Wells for example here you see that 7 is the output of Gate 1 and which is also the right input of gate 2 that means that the corresponding value should be consistent right and similar how it's true for other kinds of color slots so if they are are connected by

some walls they should have the same value um so Planck's obviously issue by proving that this this witness values lro should be a a private experimentation of yourself where this fermentation particles the wiring information of the circuits and the and the plug gives a very nice nice idea to do a permutation arguments but what we get is like we could like explaining it in a more modular way essentially we build a more modular framework explaining these ideas explain the dependency of these protocols for different types of relations okay and more importantly we extend these

relations this this kind of reductions into the marketing various editing and the key difference here is that at the bottom we replace the caution check with the classic some check protocol and this is also the core reason why we can uh like get rid of ft and obtain some scheme that has linear time proverb okay so that's about the how basically higher Planck works and I also want to highlight there's a key advantage to the mark like to move into the marketing setting is that it enables much better High degree cut gauge support so we record that in this simplified

plan constraint formula like I would say called bolina Planck constant formula there's a degree three formula because like there's L times R times s and but in practice we can definitely use other types case if you want for example you can replace the multiplication case with some much higher degree Gates like like some two examples L to the 5 plus r and more generally we can definitely embed more custom gate types in this formula using different sectors and a key key benefits or key advantage of doing this is that it helps you to reduce the size of the circus or witness

for certain applications and that means you can you don't need to prefer a really large circuit you can prove a much smaller circuit which makes sense to help you to have fast approval right and there are some examples for example with the help of hydrogregates you can express the ECC addition with like much fewer constraints and same thing holds for sure for some algebraic hash functions like a rescue or something else however the power of this custom High degree gate in plunk is kind of limited because recorded involves some protocol called quotient check what quotient polynomials its degree is actually

multiplicative to both the number of gates and the degree of the customer Gates so it has degree DN and after plugging to a PCS we also need to commit to this quotient polynomial that means it also includes the number of group exponentiations of this underlying protocol and we know that the PCS part is actually the very heavy part of the snarks and this makes the like proven performance worse if we use a really high degree case and also because we have a question check which is checking like the product of two polynomials we also need to do some higher degree polynomial multiplication which implies on larger size ffts so in practice the recommended degree used is not

usually not too large like usually like less than eight if you you ghost to even higher than the advantage of using High degree gate is trade off or canceled by the by the deterioration of the proving performance per gate but in contrast the hyperplunk has the advantage that this hydrogregates only mostly affected the underlying information through radical protocols then with some check protocol and we know that some check consists many just of field operations rather than group group operations and also some check in each round there will be some Universe polynomials but it's only degree D but not degree DN so that means

like we don't have a very very large degree a polynomial to be committed so essentially I want to say that this enables the use of very very high degree custom Gates and even if you are using very high degree calcium gas the cost of the sum check over this High degree polynomial can still be comparable or even less than the cost proving cost of the polynomial commitment part and the entire cost once increased much even if we use very high degree gaze and this is justified by our benchmarks as well we showed us the the proving Clause only is only 20 more expensive when we switch from some gas with degree two or three

uh to degrees 32. okay so meanwhile I want to very quickly say that we also have some optimizations to the classic subject check protocol tailored for the hydrating polynomial statute I won't go into many details on exact improvements but I want I do want to highlight the key property of this classic sound check protocol so the Samsung plug is basically a very efficient code for you to to ask for approver to argue that the sum of evaluations of a marking the polynomial of the Boolean Hardware Cube equals certain values and the key property it has is that it reduce this like almost 2

to the new evaluations of f to a single random evaluations of f so let's verify only need to check a single evaluation of this multimedia polynomials and this is very good property then it can be super useful in some other scenario which we'll see later so I won't go too much on this let's uh let's uh let's summarize what we get so now like after having this we know that we we obtain a hyperplunk which is a market variable IOP for the for the MP relation or asthmatic computation and in the pre-processing phase what the previous test does is that it will send some Oracle called selected polynomial

and the permutation polynomial will select the polynomial encodes those data types includes like addition Gates and multiplication Gates and or even custom Gates and the permutation point will includes like hard work whilst hardcore information for the circuit Wireless okay and then in online phase the proverb will stand the weakness or like circular weakness polynomials here Arro to the verifier and I also not want to note that in the marketing setting it's very easy like after when you do the snark when you do the commitments it's very easy to combine them together and or just obtain a single commitment for all of them so basically you only need to

send one commitment in each runs and then what after that what we need to do is just to run this polyrp for the gate check as wearing for wiring checks and all those uh protocols their underlying protocol or just just the sub check over some higher degree polynomials and we also note because some check is really vegetable has really good property about it about batching so we only need to have a single sump check for both polar LP and this can save save us some like proof size and improve the efficiency of protocol okay so after that we know that finally to verify we need to evaluate this uh

big like the like very complicated polynomial at a single point but actually it turns out the corresponds to like many evaluation queries of queries to the many Martin linear polynomials so in the vanilla setting in the Berliner constraint system we already need like 14 polynomial evaluation credits for verifier and this is not very good because that means if you plug into your PCS then we need to generate many PCs if evaluation proves one per evaluation queries and PCs evaluation proof in the multinational setting is exactly one of the bottleneck of the proving time and it's very very expensive so we don't want to build so many imagine proof

we'll just cancel out our efficiency of the poly LP protocol so given this to address this issue we also designed a new poly IOP for the direct evaluation so that we can reduce the num like the multiple number of evasion credits on Martin linear polynomials into a single evaluation query on a single multi-linear polynomial and hence the resulting stock only needs to provide a single PCS evaluation proof which is much more efficient okay okay so let's look a little deeper on how this patching works so here the Proverbs goal is to convince the

verifier that K polynomial evaluations are consistent or correct where each query can involve different polynomials and also different evaluation points and we hope to build some like informations from the radical protocol then transform these K queries into a single query to this marketing polynomial and we also hope that this protocol is very very efficient namely the proverb time should be not much larger than the time complexity of doing this K polynomial evaluations and second we also need this protocol to be really efficient meaning that the communication approves size should be logarithmic and the verification time

should be also logarithmic so it doesn't add much overhead of the underlying hyperplunk protocols okay so we note that there do certain protocols that deal with this so-called battery evaluation problems but they do not meet our requirements here so first Halo influence is a very good work that's uh also do patch evaluations but the key things that he on they only work for Universal polynomials but not generally for multivariable polynomials we'll also know that Justin Taylor's book has also proposed some solution for this special evaluations for Market Nino polynomials however after generalizing this approach into the setting that's

where we have multiple points and multiple polynomials the solution only has two work time K Square mu times student mu well case number of evaluation mu is the number of variables in these polynomials Which is far from optimal because the complexity of evaluating K polynomials is only with complexity K times to the MU so given this we improve the state of the art by proposing the new Belgian protocol with prior time only K times to the new which is almost optimal because in any way needs to take this much time to evaluate the K polynomials also this is basically a kmu factor stating of the state of the art and in hyperplunk stating setting K is like

always larger than 13 and mu can be larger than like from 20 to 30s therefore it is almost like several hundreds of factors of saving to the state of the art we also note that protocol is efficient meaning that communication and verification time are all logarithmic with really nice constant so let's see how it works so recall that our goal is to prove that f i c i equals y i for every like I from 1 to K where GI is the evaluation Point f is the polynomial and the Y is the expected claimed evaluations and to illustrate the key idea I just considered the most like the simplest

case where there's only one evaluation point which actually makes the tax evasion not that making sense but I just want to use this toy case to explain the high level ideas okay so to prove that this fizi equals f y equals y i a cheat trick here is to rewrite the evaluation of fisci in interpolation form and in the multi-linear setting this is the interpolation formula is called multimedia extensions so what we do is that we list the evaluations of this uh polynomial fi on the Boolean hypercube and then actually the F's like this this evaluation exactly uniquely represents polynomial

and the FC valuation on arbitrary Point V I can be expressed as many combination of a tensor product then these tensor products related to this point d i and the coefficients are related to those evaluations on the Boolean hyperq and basically is just a sum of them which is basically essentially a sum check of the Boolean hybrid cube right and as we see before the classic stamp check protocol has really nice property that verifier only needs request this marking in the polynomial at a single random Point therefore we successfully uh transform the batching protocol into a single evaluation but of course this is not

very helpful here because already in the beginning we only have one single evaluation so the question is that what we do if there's many there are many evaluations what if K is larger than one and a key key property of of some check is that is definitely vegetable right it's like very nice property that you can you can merge many subjects into a single sum check and then in this setting you can still reduce the reduce the protocol into the single sum check which only involves one single random evaluation so the idea is now you can reduce the evaluations of F1 D1 f2z2 to have case

DK to a single random evaluation of some polynomial F star well F star is basically a linear combination of the original polynomials fi and you think think about this like the verifier he will get the commitments to fi so as long as the PCS the polynomial commitment scheme satisfies certain homomorphic property the verifier can reconstruct this uh commitment to f-star given the commitment to the FI and then after that it can check the corresponding evaluation proof for this F star R2 okay so that gives us a really good idea to to transform many many evaluations

into single evaluations okay so I also want to note that this kind of techniques can have a really cool application in somewhere else like for example the commits and approved snarks or more generally enables you to efficiently improve the the relations between the vector commitments I want to talk to a margin details I just want to say that in this setting we obtain even like even more efficient scheme which prevent complexity only two to three meal and this kind of techniques is very very useful for us to building some commit and improve snacks from Market linear polynomials and is also one of the key building blocks of our Orion plus pcis

Construction okay so after that I want to focus on another cool feature that we achieve namely extending hyperplunk to also support a support lookup against so before delving into the technical details I want to also like mention really quickly why we need lookup case I think most of the audience should be convinced that yeah lookup is useful but let me just quickly go through it so like 1 to 32 very typical application of a using lookup once the rent check sometimes given arithmetic circuit we want to show that certain values is in certain ranges for example from 0 to 16 right and this is a so-called wrench

check problem and sometimes else like we also need to apply some bid operations over this on top of the circuits for example if you want to prove the correctness of a r256 hash it involves some Excel operation for example right and the one good one bad thing is that if you only have addition Gates or multiplication Gates it's very expensive to express this kind of functionality for example if you want to do a rent check what you usually do is you decompose them to some binary values and check each binary values is exactly Boolean values like basically either 0 or 1 and this takes like L gaze where L is the number of Beats or in this range

but if suppose we have some pre-computed table that stores these valid values and you can efficiently prove that a certain Tuple or certain value is in the table then things can become much more efficiently because one lookup gate suffices for us to implement both rent checks or bit operations so I think you are convinced that lookup is used for and let's see how we can solve this problem um in the marketing year setting so given two vectors F and T well T is some pretty precise table and F is some online witness how do you prove that each element in F is inside the table t and the pro lookup is an elegant scheme

that solves this problem the idea is to interpolate this Vector onto your set age which is basically a multiplicative group generates by a roots of unity and now we can interpret this structure into two polynomials and then it transform this Loop calculation into another relation console called multiset equality relation over polynomials which is much easier to be handled using polio IOP protocol I will skip the exact transformation from lookup to multi cell equality but I do want to highlight that the resulting protocol essentially is the fact that you can very efficiently rotate the evaluation on polynomial by

several positions like what you do is just multiply this so-called set Edge by a root of unity so basically from F batch to F Omega Edge you trans like you rotate the evaluations of the this this uh on the set by one partition and it's very useful and is essentially used in the in the resulting protocol table uh product cooler cup scheme and however in our case there's some changes now first the so-called the set at interpolates that H is changed from multiplicative group into Boolean hypercube and we change

from Universe polynomial to multimedia polynomial and in this setting the existence of such a very very simple and linear function of Bluetooth root of unity is a longer trivial so we need we do need to find another types of generated function or next function that enables to to rotate this these sets okay so to address this problem our first step is to First view the Boolean hypercube as some field which is binary extension field and then we can replace this Omega which is a root Community which some other generated function for the corresponding multiplicative group inside this field and we know that

there's a really cool connection between this technique and some very old paper for building short PCP which I find is kind of amazing okay so let's see how it works so um let's consider a prematurely new which is of degree mu and with binary coefficients and it's easy to see that this uh this polynomial like polynomial with binary coefficient modular P mu is isomorphic to the binary extension field F2 to the MU and by definition of the Primitive polynomial X is exactly a generator of the underlying

multiplicative Group which is basically F to the MU minus the zero points so now this gives a very good way to do rotation okay so let's see an example of mu equals four so for every non-zero point in the Boolean hypercube we can trans like we can represent this Vector as a polynomial with a binary coefficient right well the the vector are trans like are mapped to the coefficient of this polynomial and then what we do is that we just multiply by this generator polynomial X and it will turn some new polynomial with binary coefficients and this translates back to a new point on

the boonie hybrid Cube and this gives a really good map from U to its next function next new and which looks like this so this and I I want to highlight that given that X is a generator this next function exactly enables us to Traverse the entire Boolean hybrid Cube except the zero points and when mu X4 you can see the cycle looks like this and this basically gives a way to rotate this this this set right so basically when we want to rotate the evaluation of f x what we do is just to compose this FX with this polynomial map next X so F and x x exactly Works similarly as what

we had before for f Omega h however there are some carriers of this approach this approach is that in this next polynomial map a vector map in some Dimension the function is quadratic for example you see here the b0 X will be three if you want to interpolate in this algebraic form it should be the case that you have to integrate AS b0 Plus B3 minus b0 times B3 which is quadratic and because D has multiple Dimension after we compose the degree of the resulting polynomial will actually blow up it will no longer becomes a marketing Union polynomials and that means the in underlying some type protocol it would

be much more expensive so given this issue uh we a key observation to solve these issues that we found that actually we only care about the behavior or the values of this composed polynomial on the Boolean hypercube but nothing else so what about just stimulates it using another marketing polynomials right so recall that we have this next function we call the next function we have and the key observation here is that for all the quadratic formula in in some Dimensions this quadratic formula are all correlated to one single variable piece three which is the last variable

in this vector and then gives a really good way to to mineralize this function so the idea is the why not just the enumerate the value of this last variable um from zero to one and then we can rewrite this next function and to make it linear and make mineralize these functions right so this gives a way to define a new marginal polynomials as follows okay so basically if X3 equals one will trigger the net left term if X3 equals zero will trigger the right term which all maps to the these next functions and the key like there are several two nice property about this F shift Martino polynomials first is like efficiently

computable given only the Oracle axis of f so basically only involves like in order to evaluates F shift you only need two evaluations of the Oracle F that means in the underlying protocol you don't need to send any extra oracles you don't need to send the compose polynomial oracles you even don't need to send the oracles for f shift you only need to send oracles for f and it's sufficient for you for verified to simulate queries of f shift using queries of F and second is that it's evaluation on booling hypercube is exactly consistent with this compose polynomial as next X to give like to make it more precisely let's see some example like see the see the cases like for example if Case B3 if

B3 equals one then we see that the left part is triggered and the right part is inactivated and turned off and the result exactly matches at next B right you can see here and similar things how true for B is three equals zero if B series is zero the left term is inactivated and the right hand is activated and the result is still matches to F next view so we can prove that the evaluation exactly the same as f n x x so given this instead of doing some check or like marketing a protocols on top of F and F next X what we can do is we can directly work on on polynomials F and F shift which are all

both multi-linear and then this gives a really like really efficient and a million times local polio IOP um and like which which is really really efficient and much much uh I think it's really practical okay so finally just a question on the efficiency is that so if you apply that next function that the enf rotate function more than once then does that mean you get an exponential number of yeah and the yeah that's a good question yeah if if you do like if you want to rotate by multiple position which is some of the cases in the Halo 2 right

like then then we need exactly we need exponential number of evaluations for f for example if you have here you want to rotate by four you need like two to four evaluation of f so it's still open problem how we can like uh implement the shift by by a long distance with very efficient protocol and currently because in the lookup case we only need to rotate by one position it's very very efficient you only need two evaluation of that yes yeah very good question yeah okay so finally let me briefly mention our grams thought evaluation results I want to say that current implementation is only approval concept and also meets some optimizations we also haven't fully

implemented lookup solution yet but we are planning to implement all of them very soon and post a new Benchmark in the paper but even with the current raw implementation I think hyperplunk still did quite well so the proof size is logarithmic so it's it's worse than plunk but it's still comparable and I think it's really also really practical and it's also much better than most of the multimedia based snarks it's only six gigabytes for for typical application like for Mu equals 20. also we compare our proof concept implementation with a highly optimized Planck implementation called jellyfish and it turns out

um hyperplunk already output Splunk at 2 to the 14 Gates and add 2 to 20 it is already once faster than Planck and this Gap will keeps growing because because of the difference from uh like costing their time to to linear time and also want to mention that like our skin is also more paralyzable so if we use GPU or fpga or some Hot Wheels this Gap can be even more significant also we've used some and we compel have fun with a variance of Spartan that's plugged with the KGG PCS for a fail comparison and it turns out the a writing is also very fast but the key key Point here is that the difference

here is that sparkling only works for r1cs and it involves more constraints for certain applications like TK row or Cache or zkevm so hyperplunk is still more efficient because it can like embed like represent this computation using much more succinct circuits so the the scale you need to prove is smaller so the final approver time is still better in this in these applications okay okay so I still want to say that yeah there are still plenty of space for our implementation optimization and in particular we see that the bottleneck of our hyperplunk implementation is about the commitment part the PCS part so the commitment to the PCS and the evaluation

opening of the PCS is to account for most of the time for approver So currently we are implementing uh three we do three separate pcs-evaluations which is actually not uh not a ideal way to do it because it's very expensive and there's no reason to do it if you want better efficiency the reason we do is just for Simplicity of implementation but we will try to combine them and just run a single evaluation proof which we think that we can expect significant improvements over the performance of playing over the implementation and we are implemented this very soon and hopefully we can get a like a new Benchmark which also

improves the performance of hyperplunk yeah and yeah that's basically the uh it and let me quickly summary what we have done so first we build a new um plug-based based multivariate for the lp with an inner time Trooper there's no ffts and there's much better hydrated custom gated support and we can also make the general knowledge in the multimedia setting which is actually not that trivial um compared to the universe that I think and also extend it to support lookup and it will build some new market linear polynomial commitment schemes that improve the state of the art which includes scoring plus that preserve

linear time and have really small proof size and a new fly based Martin near commitment scheme that's generically transform any Universe PCS into a multimedia PCS okay so that's the that's it and thank you so much yeah any questions uh wow Benny thank you very much for that presentation very comprehensive uh easy to follow and really interesting so thank you very much for some questions going on in the chat I chose not to interrupt you because Benedict was covering them oh thank you thank you um but uh yeah um does anybody have any questions uh for Vineyard or about this work in general venue or Benedict or I just bought this work

I guess I went today just for the questions in the chat there were some questions regarding the precise cause depending on the gates and so on and it's to be honest a little bit of a complicated form like it's a little bit complicated because uh basically for example High degree gate because like less if it's a single variable like uh raised to a higher power right that's one type of high degree gait another type of high degree gate is you have many wires or columns in the Halo 2 sort of language and you say like you multiply all of them together and and that's more expensive uh uh a little bit but you know the the

um yeah so the I I think I answered a couple questions regarding that in the chat um and I want to go through all of them but yeah it basically depends on the specifics of the Gate of what exactly the cost is I see okay can you repost that conversation um in the chat because when you join late on Zoom it doesn't show you the previous track um yeah I can I can I can find it I can also find it um any does anybody else uh have questions about this work yeah can I follow up with a question on that um

so uh yeah thanks for the explanation I think I uh understand how like the complexity of these these Gates works but so if you have multiple custom Gates uh like the way that you merge them that does that not really blow up this uh this degree or like the complexity of doing the evaluation in the sum check yeah good question so like we we assume that a number of terms in this is constant but of course you have like keep keep adding different complex Gates it definitely has some a complexity on evaluation checks so you like we assume that you won't have too too much too many type of complex case at like

connected by them right if so for example you have one thousand type of skates definitely it will affect the the complexities of the sum check yeah so our assumptions that this is constant like like less than 10 or something which won't affect much of the overall complexity of the sound check I mean I think the way the way to think about it is that you need to um like if you think of the gate as you know there's the gate formula then you had like some nice uh yet at some point you have the gate formula right um essentially like the Groover needs to

symbolically evaluate this gate formula and so that of course depends on you know how many terms there are it depends on what degrees they are right like if it's a high degree right like why why where does this log squared Factor come in well you know if it's a very high degree gate where I multiply many things then actually you know like it's it's the multiplication of polynomials that then uh I mean but yeah basically I need to symbolically uh evaluate this this formula like expanders uh once per day this is the way that I would formulate it and it's not really simple to put

that into one formula of what it is like of what it could be but we can bound to the cost of it so uh this might just be more of a curiosity but are there basically like pathological types of gates you could construct where you can't do this uh like sort of polynomial symbolic polynomial multiplication trick and you're stuck with uh sort of the naive um D Squared evaluation time or I mean so the the descriptive evaluation time is essentially it's a symbolic evaluation I just do it in like right I just do it in a valuation form

um uh right but you know I mean I think that the the D log squared D algorithm that we use actually does rely on ffts it just relies on small ffts so for example if you're in a non-fft friendly field then you maybe would wouldn't use sfts you would use something like cards through his algorithm um but no I don't know like maybe and also usually I don't know yeah also usually D is not that large right it can be large then it won't be larger as one like one thousand or one million it's only like 100 and usually like I guess using card to buy is already sufficient because like it's already the D Times Square

Root T which is uh is only a very small factor uh compared to that so yeah I think if you want to have a like using non-print long FD Friendly Feed in the practice you can definitely use carousuba and we want it back too much of the efficiency yeah thanks so I have a couple questions um so to follow up on that is this technique also applicable to like standard plan you know so so this for this how to do with custom Gates is effectively you're composing um you know two protocols right like you have you know first opening the multi-linear and then you have you know you know opening up this um like custom gate coming to polynomial

right can we just do this for a standard plug as well you mean by stand upon constraints this more standard plan proof system uh yeah the verifier doing this polynomial locally uh the prover will effectively compose two of different openings um right yes you are saying so what's the main question main questions like this this kind of hydrogly high degree custom gay technique can also be used in the universe setting it's not the occupation yeah yeah that's the question a key question the key reason is that it's not that efficient it's exactly as mentioned before that's the universe setting you

don't have sub check but what you have is quotient check and if you do this kind of techniques like finally you have to commit to a really large degree quotient polynomial which is definitely less less efficient so it limits the Practical practicality of this approach in the in the universe setting yeah that's that's the question right um this is you know exactly what when you wrote then this that is that's the important part right like in Universe time check we commit to one quotient polynomial which is of degree D times and in uh in in this sound check in the multivariate sound check I also commit

to like some sort of polynomial in every round but that one is only degree D not e times Zen and there's log n round so essentially the depend login group operations versus D times n group operations so so that's why I like like having super high degree gates in the universe prompt just doesn't make sense because whatever Factor you save you will totally lose again when you have to commit to the quotient code number yeah the summary the summary definitely can use high Aggregates in Universe setting you can give a really succinct circuits for student applications but the points the

trade-offs like it also makes the proving speed per gate also much worse in this universe setting so it like it won't make sense for you to do a really really high degree gate for Universe setting yeah yeah in particular in the universe setting so so it's particularly inefficient to if you have just one gate that has a very high degree then you're paying that cost for everything yeah so so you want um the degrees for your gates to be a roughly the same and that that's also part part of what limits it right yeah I just misunderstood I think I you know I don't think apart um so my second question is

um you know what is if you well if you want to like estimate like the recursions about this um you know because there's like for some check you have this love Factor um you know I'm just thinking about you know from a practitioner perspective will this be useful as an inner proof right because you know um you know Infinity like you know how efficient is a verifying circuit uh so do you think there are estimates on that um uh I think in terms of verifier complexity uh like verified circuit complexity is still only one PCS evaluation proof verification but of course the the multimedia PCS verification is more expensive than the

universe that team right in the universe I think just a constant number of pairings and a small MSM but in the marketing settings login of them but I think I think concretely uh it might give you some overhead uh having Con on this like I'm like exactly computer this but I don't think it would be super high it can be can be efficient but not maybe not that efficient as uh as a universe verifier but it still be efficient and I think because like because of the proving time itself is already fast it might also make sense to do some recursion in some sense in some setting yeah but but good question I haven't like very carefully calculated the

circuit complexity for verify yet yeah thanks yeah so the the cost breakdown on that slide that was just for the prover right um do you do you have a similar cost breakdown for the verifier uh I mean I think the verification needs to evaluate the gate formula once at least yeah okay yeah no I mean I think that's that's exactly it the verifier just evaluates the gate formula ones that's okay and well no and and um actually you know the other thing is that the degree of the Sam check

increases right um so in standard sound check you actually send over the entire polynomial but you know one thing that we do is you just send over like if you have a high degree gate you may as well just send over a commitment to a univariable and only up in every round of the same check so there's no additional cost to the verifier Yeah so basically the verify cost is basically two PCS check why is the PC marking in a PCS check and one batch Universe PCS check well because in the in the in the some check of high degree Gates what we do is we'll just send the univari Oracles in each round and there are some Universe Oracle queries but we can definitely use a Halo

influx to to batch all of the evaluations and then finally just one yeah one Universe PCS check yeah would it be fair to say that there's basically additional log Factor um in the bar of our cost I mean assuming that like okay we can't think about that yeah yeah um so there's a question in the chat uh aurelian I hope I'm saying your name right um if you want to ask it out loud feel free or I can it's up to you yeah yeah yeah I I can't I captured if you could go like way back to the first slide but explains the hypercube encoding and what I'm trying to understand is uh

what was the cost of adding like one more variable or one more wire and what's the advantage or the hypercube compared to like other ways to identify wires you mean in the encoding part right like I think way in the beginning yes yeah like first slide almost that is really [Music] um let me just uh I'm trying to understand how the Hydra Cube part comes in because because you can do a more compact

encoding right with like two variables that are indices into like today a 2d grid and you can also do a less compact encoding like one hot right so our where's the hypercube important I mean I think it's uh it's just the trailer right I think that that the number of rounds of the sound check decreases if you're um using uh a higher degree Cube um or I guess like yeah if you're using say like base three or whatever but it only decreases by a factor of lock to

like say it's h right then uh number of rounds of some check decreased by a factor I'm going to write it down by Factor uh log 2 of size of H right if we're encoding over here H to the right whatever um but the degree of the sum check so the degree in each round increases by a factor of age so um I don't think it's a worthwhile trade-off but what's the stage all right yeah so the number case

the number of variables basically in the multivirus log H is the number of variables right no no no no no I think it's the it's the base right like it's like zero one if we're using a Boolean hypercube I thought your question was what if we don't use zero one to encode but what if we use zero one two yeah oh I see that question I see so yeah so I think it's basically uh so we call that thing H then you can make it bigger to decrease the rounds of the subject but in fact the block to age but it increases the the complexity of the the degree of the subject by a

factor of H so yeah it usually doesn't seem like a worthwhile trade-off yeah I was actually doing something I got it thanks I was actually doing some backup of the envelope calculations about this um and it seemed to me that um that's an rt4 um so so your your base is for um might be more efficient because um that you you still have um a relatively small number of additions if you look at the generalized um some check that that works with an arbitrary base um each round is still um not particularly complex in that case

so so then it may actually be actually excellently actually I think we we try this method before okay yeah and the main reason why it's not even more efficient is because of the like high degree Gates like I remember that when we use like like in close to four like for example you it definitely decrease the number of runs um like you decrease number of runs for some check but actually if you have high degree Gates I forgot the exact computation I had but if you have like a high degree case then each round the complexity is much larger it's not like it's not from like from n to half of n to four fourth of n to something like

that it's like there's some quadratic I guess quadratic blow up and actually if you have like larger um like like uh bass like from zero to four or something actually the the complexity for how to get it is actually worse so that's why we stick with the with binary hypercube yeah but in the the in the in the in the just the linear setting the multimedia setting there's no difference I think or maybe there's some efficiency as you said like there in terms of multiplication versus addition there might be some uh trade-off and might be having higher degree might works but to me I think seems like the same but in terms of in turn the high degree Gates definitely I

think the best best approach is to using booty hypercube yeah well I think I mean at least in terms of the scale the group operations say you go to the extreme of only two rounds so you take a cube of square root n on square root n so definitely the group operations will improve right because you have no plus d Times log s so now log s is like one uh and I I wonder if there's a chance that you know you increased you you're you got a decrease deficiency because you know since you're you're thinking of the degrees as constant of the unit variate you're using like uh some something for polynomial interpolation

that's you know for very small domains but uh my my uh my guess would be that I mean the proof size would be huge but uh in terms of proverb time actually I'm my guess would be that if you use fft for the unit variates that come up then uh the extreme of like just uh two variables might uh uh might actually work well so actually I think uh for group operation is actually not a big change because you see that this n plus d log s right like constant times n plus d log s and in practice n is much much larger than d right even

you change from log as from log n from like from 20 to 2 then D log s is still very negligible part on compounded to total number I think maybe what I forgot what I what I'm suggesting there would be an additional square root n sort of uh like the universal send will be sorry yeah it will be like a degree yeah maybe square root n times uh times times d uh yeah yeah so yeah I guess right the general formula it's D times the individual degree of the witnesses which in your case is just

one time to log s so yeah so in what I said I increased that one to like square root n so yeah I forgot about that I mean this should be like it's true that there should be a family right like essentially if you formulate things correctly um then if you only have one round you should get back to your normal universe um maybe there's a trade-off like intermediate Point yeah like you save on the verified cost you know because imagine you want on one extremely univariate and you know on the

other side you have high performance right uh hypercube I think really like are there basically shootouts in between where you trade-off proverb like large approver time because you have higher degree you know universe ffts but you have like you know uh more like less variables right so therefore you have like uh um less complexity uh on the bottom of our side [Music] right so you mean with with less number of runs maybe you can get a better verify time but yeah I think what is is in that case is it sufficient to have a market linear PCS do we have need to have some multivariable PCS maybe right because the yeah I think it's more like probably

multivar with PCS so you want to pack the entire like constraint you know in a multivariate uh well like right like so like you like on one side like like a universe it's just like a lot like lying and on the other side you have hypercue but now it's like basically a hyper group of higher Dimension like what we're uh we're not a cube anymore right we're used to mention that you pack more elements Maybe let's see yeah good question I I need to check I think yeah this button is a it's a good start yeah I mean what is interesting is that even with right like the reason why one of the key reasons why Universe lung

is bad for high degree Gates is because of this quotient right that that is of degree n it could be that even with um I mean like two or two rounds I don't know if that's true well that even with like say you extend it to a few rounds right like like if you think of plonk being one round hyperplunk being the other extreme uh like login rounds or new rounds you know it could be that even with a with a few rounds uh you know the degree of the coercion polynomial also always like decreases exponentially so perhaps

you know like even a few rounds are enough to make it a non-factor um that's certainly possible yeah this was why my intuition was that um using a relatively small base but not two so say for the the degree of state if it sort of scales smoothly between univariate Planck and hyperplunk then I wouldn't expect the um the the cost of the high degree custom gates to be that much greater um so so I'm surprised if it is um but but you've done this moments so yeah I just think that in the end like I

mean we mainly cared about for real time I think the proof of return is going to be optimal for for high performance could be if like you really care about it verified time that there's some other spot that's in the middle that's better but I don't know I always feel like yeah yeah maybe at a point where you should just care about prover time and then use recursion to bring down the verified time like I don't know yeah yeah the case but you care about the verify your loss right because we're very familiar is that uh it's very fire secret and then it does approver I can always use recursion to bring the verified down

well even with recaption you still care about verify a time because um your recursion threshold is going to be yeah I don't know um uh to 12 row circuit or or maybe two to the 11 if you're particularly clever about it um and so um that's it's still a few milliseconds um so it depends depends what you consider an expansive verifier really yeah yeah I mean yeah I guess like it's like I feel like expensive verified is defined by what we happen to have at uh evm recompiled um which seems a little bit like

arbitrary like you know maybe we should just recursion work how do we verify it as a sequence so you're just uh like just to see this verifier as a circuit right like this circuits the MP Company can you can definitely model every computation you just you just like um Beyond prove this circuit verification or Beyond proven the circuit correctness it also proved that verify will accept this proof so that's the idea of recursion and finally yeah you can use two chain for example if you

you're okay with that like there's a I mean there's also much more yeah I mean you know for the specific case the kg polynomial commitment team right you can use something like IPP in a pairing product yeah please use all of the pairings into one right like there's much like the things that we can do that we already know um pretty well a content it seems like all of the techniques for optimizing recursion are independent of the difference between one can hyperplunk as far as I can see yeah one is just that in hybrid plant you have multiple pairings right like if you use it with kdg you have yeah new

pairing and we have we have techniques for combining all of those that are very very efficient yeah still I also want to say that the the snack verifier is more related to to the PCS part like you should think about hyperplunk as polio P right like you can plug it into any PCs right like one particular institution since KGG and maybe you can do others or even our new marketing commitment scheme like proposing the paper so with difference PCS you have different PCS verifier circuits yeah I mean if you're using if you're using accumulation like in bcms 20 um then the accumulation verifier does not need to do a pairing even if if

using kcg so that I think that's the pcdl scheme right right navigating to the Outer Outer verifier exactly yes yes so yeah I I I I did you say that most of your work was um in the field like field operations will be some check what was it about verifier well for verifier I think like using our like Universe Oracle like the classic stem check also has some field operations right you need to evaluate through like the wrong polynomials at some points zero one but in our set in the high degree setting what we do is to

send Universe oracles like it's basically user commitments and finally you need to the verify this course is just to check the evaluations of them and basically just a batch PCS evaluation for univariable polynomials so basically there's no there's no uh cost about some check related to uh related to the degree of 30 and the fifth like not much field operation so as I said before the basically the bottleneck of verify is just one PCS evaluation check for Martine polynomial and one flash pcsc validation for Universe Oracle yeah for Universal normal yeah that's basically the verifier

yeah that makes sense yes because the origin of the questions that when you use a trying to do a recursion on a curve like BN 254 it doesn't have a cycle right and we verifier then it has to do group group operation in a non-native field right this kind of field and it's doing elliptical operation in the base field of the inner Secrets right so the group operations are extremely expensive and the field operations well in the same field so we have the average so I think comes to the previous

collection so basically if you you want to stick with ktg then yes yes you either use you can use two chain right you can use two chain with BW curve uh versus the POS curve and then you don't need to do any non-native operations like this native group operations will be still efficient so yeah thanks so that's actually opposite whether you're a cycle or not then we the costs of um a group of field operations are reversed like depends which one you can use but yeah as I said in this setting you don't need to recycle you just use a two

chain that's enough yeah but of course we want to do like a more layer of recursion then yeah maybe we need to cycle or use some Halo Halo method like okay you you mean not to cycle just a chain yes yeah yeah yeah yeah yeah so so just to clarify um you're saying most of the operations that the um verify needs are in the same field um but I I What proportion are in the different field okay so obviously I think it's just that the verify mainly the

group operations and pairings I guess oh I see okay or mainly the kdg it does eventually polynomial commitment verification like that's really okay the verified as the newest thing one it is three things it evaluates the gate formula once at some point it's uh well it has to check all the challenges so I guess four things uh and then it has to open one multilinear PCS and batch open uh mu uh univariate PCS okay I'm I'm just trying to reach us

which um Fields these operations are in and so so say you're using a cycle like if you're using cycle like you're actually doing recursion uh or without recursion without recursion is there's no qualification with recursion so if it's two chain then uh I think oh gosh um with recursion then a single rpw curve like field operation is eos right and uh and a group operations are DPW right sorry I didn't hear what you said oh sorry so so if you do a recursion or do

two chain recursion uh like then all the group operations are related to BW curve and the field operation are the POS field uh PW field yeah I would say the non-native group operations that you need to do is evaluate the gate formula once that's the non-native operations that you need to do the best okay so say hello two yeah yeah you can you can you can uh use the accumulation whatever your favorite accumulation scheme is right we now have a bunch of them um for the PCS openings um and then you would use

yeah the non-native field operating the additional non-native field operations are the the um or or the evaluating the gate formula once darknesses so guys I uh just quickly wanted to say we're at the end of the allotted time but if there's still questions I'm happy to keep it going and uh and if anyone needs to sign off I think a couple people have already jumped off but yeah feel free and jump off if there's any more questions we can we can keep rolling if Benny and Benedict you guys have time because I want to be respectful of your time as well or we can conclude it here so I'll pause for a second see if anyone has any other

questions yeah I'm fine um I still have there are minutes yeah okay cool thank you Benny uh does anyone have any final questions for Benny and Benedict by the way thank you guys so much for answering all the questions uh uh comprehensively to this point uh I have a question um so uh the paper talks about like how to build a steak machine with some repeated transition function uh uh have you and one of the ways to do that is to use your like polynomial shifting technique so as to not like duplicate the inputs uh or the outputs of one step to the inputs of the other

uh do you know of a way to do like periodic you know the equivalent of periodic columns with this polynomial shifting technique um by that I mean like that you would pre-process some smaller polynomial constants and then be able to sort of uh have the verifier repeat it um through the entire trace of all of your uh you know however many times you want to repeat that um so if you've seen that technique so the question is whether we can do something similar to air right you can do like some constraint periods of time like apply some constant like every every 10 step or something like that yeah exactly so one thing you can do

that's using a selector right people can always do a select or have a selector say this is zero for every like 10 step and the 11th step you could pick it move it to one or something right as you said you can do some purpose editing that's one way to do that and another way is to do shift but uh as stera just asks like the shifting by a more like longer distance is is is is more complicated it's more expensive using our approach like in terms of because the normal evaluation will be like it's exponentially increased so this is still open question whether we can do really efficient shift by a large instance yeah yeah I was I was trying to figure out

whether there was any different representation that would still give you a permutation on the um uh on the cube exceeding zero um and I think so normal basis doesn't work um right because that that doesn't give you uh a full permutation it with an efficient shift um but I I don't know whether there's anything else that might work yeah so in summary it's always doable you just do have some pre-processing like have a selector or have a permutation like Oracle like we shall purposes or if you want to do online without any extra overhead as we did for lookup then you

need to think more like if you just shift by one or two definitely is this doable and it's efficient but if you want to do a like longer period then yeah then then there's also an open question in the in the multimeter setting yeah uh if you could do something like a power of two shift then then we see you can build any shift from that yeah um but I couldn't see any way so efficiently do that yep okay thanks thank you okay going once going twice any other questions for Benny and Benedict

all right going three times so awesome okay hey guys thank you all very much yeah thank you very much for joining today uh Binion Benedict thank you both for being here this is a really great session and uh we'll post this on YouTube here soon and if you want to share the slides with me you guys don't have to if you'd like to I can put them up on SlideShare and I'll put it on I'll I'll link it in the video description all right thanks guys thank you thank you