zkStudyClub: PLONKUP & Reinforced Concrete [Luke Pearson, Joshua Fitzgerald, Dmitry Khovratovich]

Transcript

hello everyone and welcome to the uh the latest edition of zk study club today we're excited to welcome dimitri kovratovic of the ethereum foundation and dusk uh luke pearson formerly at dusk and now at poly chain capital and joshua fitzgerald of inoma uh they're going to be presenting their work on reinforced concrete and plunk up uh again so we're really excited to have you guys and over you all okay cool hello everyone glad to see that many people so our talk will consist of two parts uh so the first one will be more about the new reinforced concrete hash function and why it's why it was fun to design it and probably should be closely used and

the other part will be about uh pluckup uh integration into plonk and the result in pond cup which will be delivered by luke and joshua so i'll be the first and the guys will be uh after me uh so basically uh we are two from a bit different teams but this is uh sort of a collaborative work and also the reinforced concrete itself i forgot to mention that the first slide but it's also a collaboration from a number of people mainly from technical university grads in austria but also one person from uh radbaut university in netherlands

uh so the paper is on the print just in case but yeah let's go into these slides so basically um the the the the this will be the entire slide set and the first part will be about reinforced complete the second about plum cup plunk up is just kind of uh uh i port money upwards for blank and blue cup and basically let's look into the first part then so this table that you see on the first slide is intentionally imprecise but what's uh

what it should kind of provoke is the great disparity between the existing hash functions and in this table we have three important columns so one column is the first one the first one is the name of a hash function and the second one is about the time that is needed to prove a statement about this hash function in the k which is more or less approximated by the number of gates in the proof system you are using the third column is about is the time that you need to compute this function on a regular cpu in the native mode when you just have to compute a hash

and the fourth column is uh the amount of cryptanalysis that has been invested into this uh hash function uh and basically the more the better so what the disparity is it's that uh in the ziki mode the fastest are poseidon and rescue uh but in terms of number of gates so they're the fastest but they are also the least explorers from cryptality point of view the more traditional hash functions like uh blake ii are uh have enjoyed a good amount of kryptonelles since the design 20 years ago but

they are much slower in zk even though they are terribly fast in regular computation so just a few cycles per bite and the fourth entry in the stable so-called patterson hash which is just basically a sum of elliptic curve points with conditions from the pre-image bit string it's rather fast in zk and is reduced to uh well well tested assumption kind of intractable problem of discrete log so i've given it the greatest marking crypto analysis but in terms of every eating on x86 it's also

kind of slow so the natural goal in the design of such hash function is to do something which is ideally fast uh both in zk and on regular cpu and could have enjoyed already good amount of crypto analysis by inheriting some design principles which have been well tested in the past and one possible application for example of such a function is its usage in zero knowledge schemes where you do have to compute big miracle trees over the course of your

prover such as for example recursive schemes where during the recursion you have to build the full tree over your weakness and then when you basically uh the the next step of recursion is to prove a statement over about this miracle tree this is usually fast but building a tree is not fast and if you want that the proven the weakness is fast then a tree should be built upon a zika friendly hash function and then if a ziki hash function is slow on cpu then it becomes a bottleneck so we want something that is fast friendly and long-term test that which seemed to be kind of a

not easily achievable goal but i think we have approached it to some extent so and when we clearly understood what we wanted to achieve we turned into possible uh two possible ways to construct a hash function basically there have been two ways so one option is to use some compression function which is uh non-reversible by design and is built either on some core non-invertible function like chatu or some well-tested uh assumption like pedersen hash which is built on uh the com the complexity of discrete log so it just

adds electric curve points inside and the second option is a so-called sponge framework which is built on an invertible transformation or also called permutation so it doesn't permute settlement but it's just a biject and examples of such a hash function are ketchup or sha 3 poseidon rescue and actually a lot of other designs which are also shot refineries for example so we have chosen the second one because it seems that in terms of performance we kind of exhausted the the first uh option and uh if we wanted uh to have uh if we wanted to if we wanted

as we wanted a sponge we need uh some kind of a mapping for for it to be a sponge we need a mapping from uh basically uh tuples of field elements into tuples of field elements so in order to have a compression out of it we will just uh truncate in the simplest case we'll we'll just truncate uh one output element so and uh constrain one input element so technically to make it to make an non-invertible function out of it is technically simple so as long as you have an invertible transformation which doesn't exhibit any uh

non-trivial behavior or invariance it can serve as a good hash function and actually indeed what you just need to come to create a hash function is this sort of transformation big f if you have good big f you'll have a good hash function and it's it's fairly invertible you just have to find a way to construct uh such a function uh which is fast and has few constraints or few gates in application stuff like this so a typical approach in hash function design is to make this f as a composition of smaller f's and the small f is usually called around

and up to very recently like for example poseidon and rescue and some other designs that each round has just a compact algebraic description which in terms of zika proof systems is usually a low degree polynomial over over the state so basically lower triple for example in our case the simplest case the triple can be more filled elements and we need many rounds because um we what we want eventually is that the degree of the entire transformation f uh is deficiently high but also that if we

uh compose a system of equations uh based on this around function descriptions and then such systems should not have uh what is called grammar basis of low degree and because of that we need more rounds and this this number of rounds uh this uh kind of uh this this big number of rounds made all the functions rather slow because if you if you have uh height if you had high degree here then it would be slow in z k if you have low degree here then you need many rounds to accumulate a degree over the entire function and because of that uh this kind of

multiple rounds makes you compute a number of multiplications over the finite field which uh for the majority of fields used in practice can be sufficiently slow so we want somehow to break uh the circle that makes us to create a function with many rounds and what we did we decided to choose a very very different round function which hasn't been used before and for this uh it's it's not a spoiler that we used the power of uh pluckup well the ability to have gates based on lookup tables so for round function

there can be many different functions that we have seen in hash or block cipher designs and we can also evaluate them from the perspective of approver meaning how expensive it could be for approver to go over the constraints for such round function we can look at the evaluator who computes it on x86 and we can look at the cryptanalysts so multiplication and addition is very fast approval or value or well rather fast but from crypto point of view is this quality is low we need many such functions if you have uh a field roots like a big exponent in the field then it's good for approver but slow for revelation that's the risk you hash

function case from character point of view it's better than just multiplication addition but not efficiently better because you still have to accumulate high degree if you use paterson then this means that for ron person you choose the elliptic curve point addition and this makes the prover also a bit more expensive because relative curve addition is not for free you have to use several multiplications uh to do the uh the curve of the point edition and from a later point of view it's also uh kind of uh slower because you do this additions over all the field from crypto point of view it's all perfect if we look into block ciphers then we'd have

uh s box in the es block cipher it's that here's boxes is a mapping uh bytes to byte in the case of aes in the prover uh for the prover this is expensive it was expensive till the flu cup but for the the later point of view it's quite fast so having a lookup table on a small table of 256 elements is definitely fast it fits into the cache everything is fine except for some timing attacks so for cortanelle's point of view it's almost perfect except for this time another uh stuff like uh arithmetic that you used in shattu or orsha 3 like bit width and stuff

it's really bad for pruber but good for evaluator because it's just bit operations of bronchitis but it also will explore so you see that no no run function has pluses in all columns but we want something we want something that has plus no columns and that's the new round function that we call bar actually the bar is the essence of the reinforced concrete after we we had designed bar the rest was purely technical and this is actually the main and most important point uh of the design so if you understand how bar and why bar you you got like 90 percent of uh reinforced concrete so let's look what the bar is

uh uh well sure to mark why we didn't consider pederson or its recent design kind of evolution since emilia well first of all please excuse me if i make a bit of mistakes here because i've not studied since you know like in 100 detail and the constraints that uh the guys at zcash uh plan to use it but the thing is uh if you look into the hash function that is just addition of lithic curve points then the problem is that the result is homomorphic and the field multiplications that you are doing here is still slow even if uh this uh

these are not just separate bit but the strings and also decompositions or into bit strings is rather expensive and actually what we're doing in the design of bar uh that's we do this decomposition actually faster than before but we also compose we also combine this decomposition into some other transformations it can be interesting actually so maybe in the future we can have some combination of these two approaches and have something even uh better from the security point of view i won't exclude so yeah uh in the design of bar we need a high algebraic degree to prevent algebraic attacks

we needed to be friendly and we needed to have high performance on the 686 how to achieve it if we have the power of clonk and look up tables i don't have to look into how exactly uh look up works and how it's used together with thongs that's the uh the the title of uh talk by luke and joshua i just need the fact that there are tables that i can uh check that uh there are kind of uh wires that i can check that they are present in some tables that's the only thing i need so why we have stuff which uh why we have to put so much effort and if we were not in the field the solution would be much

better because uh in the standard approach from x86 if we uh just we work on like 10 bit strings and we can simply do just split it into whatever we call them bytes chunks words buckets and then you apply [Music] some high degree function just bucket wise and then you combine it back and apply some i don't know bit diffusion like permutation of the bits or something and it gives you high degree because this guy is high degree and it gives you resistance to majority of attacks because usually high degree function is secure against many attacks

and the crucial feature here why this is possible x86 because the domain we work is separable into sub-domains it can be represented as a product of sub-domains which can be uh and elements from the sub-domains can be modified arbitrarily when you combine them back it's always uh [Music] a valid string again so if if f is a bijection then when you combine it back it's again a bit string uh which is a valid uh but it's a yeah it's an ended string so this this end is this and it's different

sorry uh so but as we're in the field the station is much worse and i'll start i'll give here an example so after the example there will be a much more technical part which i'm going to skip for the talk but it can be easily looked up later because the slides will be shared so suppose that we work modulo some prime and this prime is for example 769 and then hexadecimal is just 301 we can't really just uh split it into uh three uh four bit words and transform them arbitrarily because if we

split it like this then we just can't uh apply arbitrary f here because the result may overflow so suppose you take like p minus one as an entry you want to modify it will be three zero zero but then this means that the last zero you can't transform to anything because if you have three zero zero and if these guys remain three and zero and if you transform if you transform the last digit into anything it will overflow so it and you you if you want this transformation to be independent then basically for the vast majority of cases you must have it must be a fixed

point so f must be a fixed point for for this case if you do such a division and this clearly won't work for us in terms of security so what we want is to find a way how to split a field element into something that is not bits or or bit uh strings and this actually this the most known trivial thing what we do so uh is to look as we we took a bit different decomposition here look that 716 is smaller than 775 which is a product of two uh numbers they don't have to be prime they just have to be some numbers uh so

that when i i can kind of embed fp into the product of integer domains and uh then i can represent any number in fp as an element from this domain by simply taking it for example modulo 25 and this will be the last element uh uh the the second element of the pair and then if i subtract it and divide by 25 it will give me this the first element of the player so the p minus one will be uh 30 and 19 uh

in this representation what it uh gives me uh it actually gives me uh quite some power because uh i can now uh if i separate kind of if i split the filled elements into two integers one smaller than 31 the second smaller than 25 then i can transport them almost independently and and transform it in a way then the result has higher degree degree uh so suppose that s is a transformation that has fixed points

for x being 20 or bigger uh so from actually from 20 to 30 but everything that is below 19 from 0 to 18 it can be arbitrary can be very high degree can give degree like 18 or 19. so and then i can make the following transformation so if i represent my x as 25 times x1 plus x2 so that x1 is smaller than 31 and x2 is smaller than 25 and if i require uh that my actually the only thing that i

require for it to not overflow is that if x1 is maximum possible 30 then x2 must be smaller than 20. and if this rules are satisfied then i can transform x1 to y1 and x2 to y2 and as a result uh i have another element from the domain uh from this actually the product of two domains and when i combine them back i have a bijection this is uh actually the main non-trivial statement that we have here also uh as a theorem for bigger decomposition

in the paper but it's fat most important to understand why it works because uh what i want to exploit is that this rules i can encode as lookups and actually just a few lookups and these lookups actually i will combine with these lookups uh later on but the most important thing is that uh this makes a bijection so whenever x1 x2 y2 y1 y2 satisfy these rules then there will be no overflow there can be no collisions there can be no two witnesses corresponding to the same field elements

x and y is there any questions at this point okay no uh then uh basically what it remains is remains to generalize this approach into something that looks very like uh a bit scary but the idea here is that instead of separating a prime into two elements we separate them into n elements so this can be seen as an expansion with variable base so if you have like a decimal base then this b is 10

in all the it's just powers of 10 if it's binary it's powers of two but in our case uh the the base all the bases are different and we have such decomposition basically so each element x we represent as a tuple of n elements so that they determined uh uniquely and under certain rules they are assembled back into field elements with no overflow and this s1 and so on sn are chosen so that for p minus 1 there is this values x1 x2 xn minus 1 and xena have certain property

so there is some sophisticated algorithm that search for this decomposition so not all not every uh set of numbers is good enough so yes and yeah this is a kind of a technical part i want to go over rather briefly so the thing is in here i didn't say what s is but in in the case of uh many uh field elements in the case of uh

decomposition into the product of many domains this s is of uh high degree and this is chosen uh in certain way so that f has the resultant so-called s box as well has a high degree um skip over that some text intentionally because it would be better i think to look at this offline so i would like on only to uh emphasize uh one thing so first of all that the result in contraction is a bijection for which you have a long theorem and in terms of performance it can be computed with n modular reductions over

small numbers so every modular reduction is over some number which is smaller than 700 in our case we have 27 reductions it can be computed with n table lookups and and every integer addition and this is to compute the function so 27 reductions modulus small numbers 27 lookups and one combination back of these elements in the single number that's for x86 why it's fast enough because we can make this and actually small rather even smaller and in terms of constraints if we use table lookups for uh for uh

from from lookup then basically uh what is possible here is that uh we can ensure uh this uh uh transformation without overflows that i mentioned for the small prime use case i can ensure this information with rather small number of lookups and constraints so actually i have uh two additions like this these guys add together to fill the element and these guys add together the field element but apart from that i need only a few

uh lookups so i need a lookup for this but the non-overflow constraints they don't give me a big overhead so actually what i have here so if i have uh 27 buckets then i have 27 constraints which have inside uh this non-linear transformation i had mentioned but also i can handle overflows and if we should care about overflows or we shouldn't care about or some sort of a carry flag then i managed to put all everything into a single lookup constraint with some additional table lookups to ensure that

this curry bits are actually zero one two something like this and so that i can have 1.67 table lookups so what it means in terms of concrete numbers it means that in order to hash two elements from the big primes uh from uh the field the natural field like bls field or bn to 54 filled i need just 126 table lookups to hash two elements and the table the big table that i use is 1500 entries plus some additions and multiplications but not terribly many of them so i think in total if you count in like plonk gates

there will be 100 more gates to handle some additions here because also in reinforced concrete there are some extra layers that ensure the resistance to traditional attacks but the main the main kind of improvement kind of innovation that we use here is indeed this decomposition and set of constraints that we come up so that all together we need a kind of close to minimal number of lookups in order to have together the decomposition the composition

and a non-linear transformation dimitri i have a quick question actually too i think just to clarify on the for the c constraint at the zero one two i i think i i'm assuming that means you know that the three possibilities are to handle no carry on underflow or an overflow is that right yes yes so uh if uh basically when you have your decomposition of a field into many buckets then you will look from them from highest to uh to lowest and then you compare each bucket to the highest possible value so while it's still highest possible you

have to check that kind of next one doesn't overflow but if at some point you are below the the highest possible then the rest can be arbitrary and this this station you kind of carry so it's it's like affinity automaton when you check over the uh carries from highest uh bit to lowest b got it and then can you go uh maybe i missed it but can you uh talk about like the z so what's what is z uh defined as in this sliding you mentioned yes well this is this is a bit technical so uh the z's are because i want the same transformation as for all the

buckets but the the buckets are of different size and what i need with z is that basically it allows me to uh use the same the same s but for different brackets so i kind of can have the prefix uh the first 600 of elements first 300 of s the outputs of s common to all the buckets so they don't multiply so they kind of every bucket has 600 elements but the entire the final table is not 700 times

27 because for on the bucket they kind of share uh this value and in order for them not to mix not mess up i use this uh z yeah um i i'm kind of sorry that this is a bit different thing i might have to to draw and open the paper in order to show exactly what what z is for no that's it's helpful though um thanks okay uh so there are some extra layers for security against some traditional analytic attacks like differential and linear cut

analysis uh which we call concrete and bricks in order to the entire structure represent what we call reinforced concrete so reinforced concrete is basically a material where you have steel bars you know inside your concrete in order to provide the necessary durability so this extra layers they are rather inexpensive uh in all situations but they are needed nurses security they add a bit like 60 percent of the of the gate uh of the gates

but yeah sort of necessary and what we what we what we have is uh this sort of a table so please excuse me for well the functions that i didn't participate in the design they may have a bit of uh miscalculations here but i wanted to compare like really apples tables so i tried to calculate this number using the same gates with the same area t like addition is like three heritage addition and those table lookups are like lookups of doubles of size 4 something like this and

well rough estimation of uh the number of constraints for reinforced concrete has to be like on par with uh poseidon rescue and pedersen hashers and similar so they are all still in the ballpark of a few hundreds but in terms of performance they are much better so we're really happy that they are much better and depending on the field that is inside we can be either like 10 times slower than sha or only three times slower than sha and i think this three times slower than shy is something that has been achieved by any zika friendly hash function before you

may wonder what is this field that is so friendly to our design and this is of course the field when our model reductions are fast uh yeah this was uh and uh yeah i think forgotten sort of the slide so basically uh it's the case when uh the fee in the field well all the buckets almost all the buckets are powers of two that's actually not possible for uh bn or bls curves but for certain primes like close to mercen primes it's possible to have this decomposition into uh basically buckets of uh almost all of them are

powers of two and because of that model reductions are very fast and we are only a few times slower than uh sha or blake and that's why we can now stop being bottleneck applications that are miracle trees so yeah this is uh all i wanted to talk about the design for the like half an hour but i can of course i think elaborate if there are some uh more specific questions i definitely think it's worth asking them now because dimitri leaves

possibly before the end any questions for dimitri before we transition over to uh plonk up luke and i think josh are gonna lead that part uh dimitri i thought this is this is great really interesting work obviously a great result um definitely looking forward to checking out the paper and you know seeing some of the other you know some of the other elements at play here but overall um really cool result thank you okay uh let me then stop sharing and uh let luka and joshua continue thank you

guys for your attention cheers thanks a lot for that dimitri uh is the screen visible i'm not do they intend to sound one uh yeah yeah it looks good i think yep so we can see the screen and the slides if that's what you want okay good to go yeah we're good to go okay um i definitely think it's worth giving a a small high overview i think most people watching this and people who choose to watch the recorder version will know quite a lot about blanc and a lot of the snarks and the constructors because we won't be going through this is how punk

works and this is how works uh assume a little bit of you know understanding the whole snark process and then the particularities about plonk with its permutation process and whatever um this work commenced uh between i guess what might have actually then been heliacs and which is now a noma and dusk um and we wanted to integrate uh lookups into into the proving system but more of like as a custom gate with a selector polynomial added on and a bit dissimilar to other ways of dealing with them as maybe having this potentially different proof systems or having them as sub-circuits and we wanted to kind of marry the two

together because it was a little bit too in the paper and one great example online the first i looked at kev's got us block over implementation that it could go well into the planck argument um sort of several months into that work uh dmitry began to create this well no sorry we'd be good to implement but dmitry started roughly the same time implementing uh and designing this pocket-based hashing function uh reinforced concrete but as you'll have seen from like the layers of bars and the things that he described there is not just up gates inside bar there's also concrete but there's also bricks and there's also like decomposition functions so that you need like modular gadgets so basically for us we wanted

one circuit that could assess all of the different types of gates in one and ultimately you know in the end for use cases if that hashing is in some kind of contract some kind of secret key knowledge with ecc gates and stuff we wanted to kind of uh merge it all together and in doing that josh and i came across some interesting caveats of merging plonk and up in in sort of the processes and the resulting uh protocol that we've implemented we've gone for it was called blanco he has another plonk ish base derivative ultra turbo everything using this kind of principles that we'll go through in a second so

um the first thing i think yeah more specific to what i said it's a method for unifying long-term book improving systems so it takes the advantages of flunk and some of these universal updatable snacks in general being succinct and fast and quite small proofs but we also leverage lockups initially for things like bitwise operations i think we just wanted to shave down the expense of a logic gate using xors and things um and because this supports arithmetic gates and local gates in the same circuits and others but specifically those if you enhance it from vanilla pump uh it helped to basically be the backbone for building a reinforced concrete hash on it

so if you look at the papers and you you kind of follow the the logic of plonk the big the big p in the acronym the permutation being the permutation equation product equation polynomial interpolation then polynomial satisfiability before doing the verifier the kind of structure in the final protocol section of the paper is followed not just similarly in the the block of paper in that they both have the quotient they both have a linearizer they're both doing some kind of checks to hold that at points copy constraints hold and putting them together showed some some some interesting areas so splunk is protocols as i said now and i think the last if i'm not mistaken

uh said case study club by ariel was f flank which is the super fast uh verification to load the ethereum uh gas then payload to ultra plum which is i think a up leverage for awesome custom gates and turbo bomb the characterization of what sort of brings these together isn't the the system of turning a circuit into a set of binomial equations or some kind of qav because that could be generalized for lots of different types of snarks it's the the kind of acronyms on their own which i really like almost concatenates perfectly that we have um these these

permutations and these these coffee constraints we have a gate equation which is dissimilar to r1cs so we've kind of been known applies arithmeticization through plong and you can you can add on and manipulate and just check satisfiability of all of these gates at the circuit they're evaluated over some lagrange basis so they have in common some subgroup of groups of unity and you say well they share this for some interpolating set of points and they have a grand product argument i'll let joshua explain the uh the next couple of slides on how some of the copy constraints work and he'll go through his beautifully designed aesthetic example

uh yeah i um all of these uh plunkish protocols i kind of view in the same way i view them as a switchboard uh and so i do this little switchboard here um what you have in each row is a uh is a gate uh or a constraint so i've got three types here i've got addition multiplication and lookups and the each row needs to satisfy uh that gate for its row but then you'll need some way of connecting these together uh so that the

output of one row can be used as an input for another um and so i i kind of imagine plugging wires or cables into these into these jacks uh like it's uh like it's a switchboard um so uh yeah can you go forward one yeah uh so uh here i've got c1 connected to a2 uh and uh b4 is connected to a5 with these uh these kind of cables and uh these cables are just constraints equations between variables but they're kind of special

and they're treated a little bit differently than the other constraints forming the rows these are called copy constraints and we can use these to build a uh permutation uh and we can check the permutation with a large product uh in the plot paper is called the grand product argument and uh plookup uh has its own product uh that that checks something kind of similar um so uh seeing these uh permutations it's kind of natural to imagine we could combine them somehow or treat them in a similar way so just some terminology

on the next slide wires these are columns of the provers private inputs and the vectors of length n so on the previous slides i had a b c and d each of those are wires a gate is a relationship that a row of the previous private inputs must satisfy um plonk up supports arithmetics and lookup gates and we can also put custom gates in there as well and these are sometimes called constraints as well uh selectors are are vectors that turn gates on and off so if you have a one index k the lookup selector that uh that turns

the lookup requirement on for row k um and we have a selector for each kind of gate that we want uh if you have addition multiplication lookups or anything else each type of gate has its own selector and we can turn those on and off whenever we want sometimes selectors can give you an auxiliary value like you could use one maybe to choose a specific table possibly or contribute a scalar into into a gate and we have copy constraints which i've already talked about a little bit they are equations that ensure that certain values variables take on the same value

and we use them to build a permutation which swaps variables with another and the swap is supposed to preserve um the value of the product and if that does then you can you can assume that they're equal and a circuit description is uh the selectors and the circuit length and the permutation and putting the copy constraints all right so uh oh yeah go ahead luke uh the the core part of what what lookup brings so if you can imagine plunk has its uh permutation equation and uh clockup has its

lookup equation which kind of does the same checks where you're looking to basically collapse a 3n product term into a term and an end product term should i say this they they do this to provide i think what what i what i call as um non-native uh finite field operations so because these uh proving systems the the snarks are constructed over of a finite fields as dimitri explained before some things are very unfriendly so a lot of the operations done in sha-3 uh are unfriendly inside of circuits when you need to create these gates convert into circuits

is very slow because of things like bit-wise operations and they don't work too well over particular finite fields and often you have to uh constrain them down to a different modulus that they weren't originally like in the context of a big integer emulation so up helps with this by basically you can imagine it out of circuit creating these these tables somewhere from like zero to two to the n in length and these tables have pre-processed values perhaps of an exclusive or between gates or in dimitri's case some modular prime outputs for some some input when you decompose a scalar and you can pass these to the proving system

and rather than do what blanc does very nicely which is take this standard uh gate equation and extend it such that you can i don't know take for example a normally difficult operation in r1cs and let ecc and find tricks that you can do with this data page and rather than doing that and extend it you can just perform one operation to scan an element of this pre-processed table and sort of simply place the output wire as the output you get from this table and then just include that table for a different part of the proof later so for our example we have um if we use four so we show this with things like compression challenges we have look up

tables are equal to kind of the the number of the wires so during the creation and i won't do too much implementation specific of the circuit when you're when you're building perhaps even prior to pre-processing the circuit um you are just passing the the satisfy the the the wires one two three and four kind of left right out bottom four to the circuit description and then later on when creating the proof is just said josh said sorry these uh parts where the selectors turned onto that particular gate are kind of kind of taken out and treated as a data structure for what we're going to refer to as a query table um so with the the gate equation i was

talking about is is this particular principle so if you have some gate and arithmetic turned on you might know it's a multiplication gate for the qms turned on in the l and the r are off and then the o's on and depending on constants and fourth wires and public inputs it changes again but the kind of augmented side you can see to this that i think's in there the subtext of a lot of like the turbo blank flunk program syntax and a lot of the descriptions on brattenberg library and a lot of descriptions on the the splunk library and art font is that you can kind of extend this on and on and then it does some fanciful combination with it that provides this custom gate

functionality and for us and we'll introduce the selector in a second it's like a lock-up gate so you'll be scanning this set of tables for a certain index i you're finding this lookup and you're taking it out and then you're treating that as part of the query structure if any questions just just put them in the chat but something to read them um so what we do this here and this is where we start to get into the the difficulties in the original protocol you define a compression challenge and this compression challenge is just something um randomly generated from the transcript perhaps some some

hashing to get some random scalar and you apply it to all of the columns of t and what you end up doing with with these four columns of t for they may be the exclusive or between two numbers plus an addition or something or whatever operation you've gone for is you apply this compression challenge and you bring them all the way down to a set of field elements so the t is the set of field elements and now as sort of you can imagine as a single column and the f has the exact same compression challenge done to it for all of those where the valid lockups have been taken and pushed to that side so the same compression challenge and f only taking lookups from t should mean that basically any value which could have existed in

t exists can exist once or more inside of f and then that's what we got into dealing with what can be seen now is two basically longer columns of of uh lookups and queries and i'll let josh take this uh yeah so here we have uh planck's grand product argument uh and if you uh you may have seen this before and if you kind of know how it works um you i probably will uh hope to understand the plookup argument and our improved version uh you have this uh this accumulator and we we accumulate this big product by

uh recursion we set the first element to one and then uh each element after that we multiply by this uh this big product and um that product contains the uh the provers wire values um and uh the index of that uh that value uh is is what is um i there uh and some random scalars beta and gamma to kind of help separate these these values from from mixing with one another or allowing the prover to choose you know

adversarial values and basically if if every element in the in the numerator is also found later in the denominator um then when you are finished accumulating all of these up uh the final element should be one and that should occur at the the nth element of this vector but if we're starting from zero and you go up to n and this is really a length n vector zn doesn't really exist in this vector and because we're using these um

cyclical [Music] subgroups it turns out that the the kind of nth element of this vector after we interpolate into a polynomial it just wraps around to the beginning and is equal to the the first element so this uh product argument works as long as z zero is one and the accumulation is checked between every pair of elements and even when you get to the very end uh you try to accumulate kind of past the end of the vector but it just loops around to the beginning and uh will equal one again it's a really nice

system it's got this kind of circularity that allows you to check both ends of the of this accumulation vector at the same time because it loops around and connects to the beginning so uh then plookup has a kind of similar argument uh yeah this is essentially what i just said there with this lagrange basis slide so then plookup has a kind of similar argument um what you do is you have the public table t and the provers list of queries f in the original argument the query list is a little shorter than the table by one element the prover concatenates t and f together

and sorts them to create this vector s which is of length two n minus one um then s is split into two halves each of length n uh so you have the lower uh n values on the upper end values and if you think about the fact that s is length two n minus one that means the the lower and upper halves have to overlap by one element in the middle and then we can kind of do this accumulation again can you go back one loop we can do this accumulation thing again

um if you look at the denominator we have h1 and h2 um basically that will run through all of the elements of s and what we have in the numerator is uh elements of f and elements of t the table uh if um if each element of s is found either in the table or the queries then this whole product will cancel out again similar to before and equal one the only problem is that this uh

this vector is actually shorter um than the the previous argument this only goes up to um it only has n minus one elements of its own so it ends one element early so uh you have the initial element which is one and the last element which is also one um but you can't accumulate past the last element and loop around to the beginning uh because this vector's shorter if you try to do that you'll end up with a garbage check at the end um so unfortunately because of the because it's one element shorter uh you

don't get the nice circularity that the previous argument had uh and it also means you have to do some extra checks that you didn't have to do with the uh original uh planck grand product so here are the the checks that you need to do this first check uses a lagrange basis polynomial that's l 0 of x which basically means we are just looking at the first element of that vector so this is saying the first element is one

uh the next check says the last element is one the big complicated check which uh is running off the page um checks the accumulation between elements uh it's got this extra factor the x minus omega inverse that prevents this check from occurring at the very end because we can't loop around in this version so you have to include that extra thing and then there's this overlap check which checks that the last element of h1 is the same as the first element of h2 um so you have these four checks uh

and uh this uh we we originally implemented this this way but we ran into some issues with it um it's possible to do it this way it's just it's a little tricky and it's not super efficient additionally there's a compression check and this is using f the query list and comparing that against the uh the values and the wires but since f is shorter than the wires you have to make sure that this check does not occur at the last element that's why we again

have this x minus omega inverse there so juggling this this extra vector that is a little shorter than the rest it just we just kept running into issues with that i think the oh yeah guys i'm just going to say i think the majority of this was covered by what you're saying um because they don't rap at the beginning in the end and i think it's uh important to highlight why they the sort of splitting happens so in our version we split the differences based on whether their indexes is odd or even whereas when josh is talking about the

concatenation and that also comes to our like our sorting process in a few slides you you take these f and these t and you sort of put put them together but you have to sort a new element a new vector sorry s which is something with respect to t such that it's in a particular order because not dissimilar to well almost the same as the previous blank arguments or where you're when you're checking this this grand product you kind of have one that you can imagine in order versus something that that shifted or permuted in this case rotation by by one or whatever you apply to the the things going into the numerator of the argument

and sort concatenating these together uh just means that all repeat elements are in order so you'll have all of all of elements of t going up from zero to two to the n for whatever you produced and then it's a single list because of the compression and then with f you sort of just insert where necessary and then you split in half down the middle and then as josh said you're just checking out those two middle elements are the same but it doesn't work when the vector of f that you're going for is in fact shorter than a lot of the others so we found a different way to do this um it's just that we could still have it and mitigate a few of the checks

so you can take this one push yeah yeah better so uh we came up with an improved argument uh this was luke's idea um and it solved all the problems we were having uh with the difficulties with the these vectors of different lengths from the original argument and what we do is we allow the query list to be also of length n so all the vectors are now length n um all the same length we concatenate them again into s which is now of length 2n and this s also must be sorted um

then we split s into two halves h1 and h2 each of length n just as before except now we split uh so that the the odd indexed elements of s go into h1 the even ones go into h2 so we kind of alternate back and forth between h1 and h2 and uh we we accumulate a product uh in a vector p by recursion this looks almost the same as the previous argument but if you look at the denominator uh we've changed the way that the h1 and h2 [Music] elements are are referenced there and the left factor we go from

h1 at i to h2 at i which h2 follows h1 so those are uh adjacent elements in s and in the the second factor there on the right uh we go from h2 to the next element of h1 which are also adjacent so we're going from h1 to h2 and then to the next one of h1 and so on and so on so those will still run through all of the the elements of s and should still cancel out with either a query value or table value and now we have a vector that is the same length as all the

others and uh the initial element here is one uh you go through the entire vector accumulating these products up until you reach the end and then the kind of next element after the end should also be 1 if these all cancel out but because of this circular [Music] cyclical group that we're using to interpolate our polynomials though the kind of element after the last one just loops around to the beginning and becomes the first one so you can check both the first and last element uh just with one single check so this can puts things more in line

with the original planck grand product argument uh it still has that circularity and um and is really nice so as you can see here we get rid of a bunch of checks now all we need to do is check that the first element is one and check the accumulation the accumulation is also a simpler argument because we don't need to prevent the accumulation check from happening at the end because this fully loops around so the accumulation between every pair of elements should hold we don't have to ignore any pieces

so also the compression check is a little simpler as well because now f uh the queries um is the same length as all the other wires so we again we don't need to prevent certain elements from being checked you can check them all yeah we've specifically removed if you remember from the previous slide that oh my good time and to kind of a high level because it must be getting well it's getting towards the end but also an hour and 12 minutes in so people just be watching um we said that we have this wraparound one but in the actual proving system itself by doing this we were able to send less evaluations of um like the shifted basis

of h2 i think we went from five to three evaluations sent for the h1 and h2 polynomials which were the split of the the s1 and s2 remember this this works so long as t has three or more distinct elements and that of course is a small caveat but i think the the likelihood of you ever generating a table with less than three for use is very small and you can always you know simply extend that reason so maybe that'll be more of an implementation we've mitigated this overlap check checking the middle elements and what josh was referring to before with the kind of

loop back around the the end going over the unity being one with pulling it's kind of to me it's like that they had the head and tail of a coin or uh if a snake represented some kind of modular number line that's our i sort of imagine it the enabling for this uh alternative is something now a little bit different so this is the the last and the most uh most most different parts of the polynomial checks and it's actually the part of concatenation that we come to so what we found when we first made uh benchmarks on and parts of this proving system is it was it was quite good it

only distinctly stood above font due to the extra commitments and so the extra evaluations but it didn't remain constant its time complexity was not the same i couldn't get we couldn't get the on log n but the verification was constant and it was because one of the operations inside was being done in a different time complexity to the rest and this was the the sorting algorithm so if you remember back to t is compressed and f is compressed where f was the valid queries well but the fruitful check of the valid f was the queries and t was a pre-processed table and we're compressing caffeinated

together upon field elements when the compression challenge that's applied these are these go down to a single column of field elements so you can't sort them based on the underlying values because there's no modular you've got unless you do a module reduction you can't see the actual value inside so you're basically taking elements of f um looking at what the field number is and then taking elements of t sorry taking elements of f and scanning t uh searching the the vector which is a nightmare and then whenever you find it you're sort of inserting it so

that you can have that length of repeated elements so uh where you have s which is just like all the elements together are all the exact same number it's it's not randomized and that was difficult because so many algorithms we were found there were n squaring complexity so i think around the 2 to the 17 the proving time was really shooting up um some of the we found a few caveats so we could have done it i think correct me if i'm wrong josh o n outside of log n plus n outside of n squared or something so yeah something like that someone we're discussing doing it different hash maps um and then we tried to work around this problem and the thing that we came on

that came about is is on the screen so it was to add to what we're now calling the the mega permutation on on top of the block up more terms at the end where we provide a a sorted version of the table t with an extra challenge which will sound this and we're looking for uh taking the t and before we treat it with respect to to how it uh to what it looks like after it's out it's cleared elements and inserting f to create this s we're actually reordering t and we're calling it t prime assorted version and we are inserting with respect to that

such that we get a set of field elements that you can organize all of the numbers uh together and we're able to go down to algorithms which take us to o and log n uh this problem uh is dealt with a differently across proven system as i understand it uh aztec have kind of a different type of circuit and how they do it there's like a shaler 2 just takes the whole elements the whole vector sorry and does a permutation on them and uh it does the the look of arguments is part of the sub-circuit inside of this this great halo 2 structure so there are different ways to do it but we found for us that this is the the easiest and most logical way to continue to augment onto augment sorry

onto the bluncle but a question that we believe in remains is is can the proverbs thought s according to t not t prime using an o n log n algorithm and thus we get that consistent time complexity across the whole proving system without needing to add this t prime because what that makes us do is it makes us have extra evaluations to this director that the verifier must have on the transcript or in the proof whatever um i believe that's everything for today uh hopefully leaving on a nice question and if you guys have any questions then shoot them over and i want to say thanks a lot to marta hector jose luis and professor kevin mo

for helping along with this work and co-authoring some of the literature with us and it's really fun work with dos sonoma ethereum well not really actually with dimitri but just gonna and polychain uh and and feel free to check out the implementations and hopefully we get some of this submitted to a conference soon awesome hey thanks guys um fantastic presentation um really appreciate all the uh the time that you guys took to come and present um i think there might be some questions popping up in chat nope okay so no questions on the chat does anyone in the audience have questions particularly i think there's

some folks here who are working on some of the other versions of plonk that were previously mentioned um it might be kind of interesting to hear their perspective on this construction or questions that they have so i guess i'll open it up if anyone anyone in the audience wants to ask a question so with that bait not taken um maybe i'll just ask you guys can you oh wait there's a there is a question so i'll let you guys uh go ahead and take that if you want to read it aloud and then an answer that would be great what is the degree of the mega argument if i'm not wrong it's three n plus two

is that correct i believe you're right um yep there there are other uh checks that have um higher degree even than that uh so it didn't uh didn't increase the the overall degree at all yeah this was the probably the largest problem running in uh for us and always looking for for improvements advice and suggestions on combining linearization was easier to do and keep folding it down but the we tried to actually put all of the the the planck term so that the standard long um with the the four wires and the pluck up plus the the specifically

sorted table uh with the different overlap checks all into one and the degree of the quote the the polynomial blew up so we couldn't do that so i think uh how we do it is we have to distinctly introduce one more polynomial which we sort of called the polynomial which now becomes the mega permutation but yes i do have an idea about where future improvements will be found um i believe sorry luke make sure you can you read the question so and for the purpose sorry yeah yeah everyone will

get to benefit from it i admit if i forgot to read the first question that uh the answer was the question was what is the degree of the mega argument the one with t prime added the next question is do you have any clues about where future improvements could be found i think i think dealing with different lengths of lookup tables could be widely advantageous and i i also say alluding to i think some people or i may know some people who are who are working on it maybe to get an n over two um where you can have like the lookup argument not necessarily need to be padded to the length of the table and things like that

and then i think another question which i'll just read here is uh what size ffts are you guys using i think that might be a derivative or a follow-on question of the original question the chaos which was what is the degree of the mega argument and then i think you answered luke and i think he meant this to be a follow-on okay yeah i think uh i'm not exactly sure what you mean but uh we do uh we do ffts um uh with uh i guess radix four uh we've got um uh the the fft for the the big uh quotient polynomial is um uh degree you know like 4m four times a degree

that's what you're asking the question is are there any places in particular where this system would be more suited or perhaps a type of computation that it would make proofs much much quicker to make well yeah integrating um this kind of as as a as a look with this edge again this lookup is a custom gate you're just leveraging a wider array of operations perhaps ones that could be done previously so to give like a an industry or i guess and a blockchain company a tangible example

previously using uh poseidon hash on the the libraries we're using before and poseidon 252 was was 953 gates but uh when i implemented it with errol using plonk up as the the the underlying proving system it came down to sort of 360 dates um it's being improved based on i just saw dimitri i think has like 265 there needs to be some work done with the representation of modular numbers for that decomposition s box but if you if you take that and you replace some of these circuit hashes with reinforced concrete instead of poseidon then yeah we're able to already drop them to the next power of two and so you know half and the proving

time so i think yeah i think that's very useful um the the use of integrating lookups is fantastic and i'm sure ultimately endless having having cpu instructions for for like uh the c instructions for cpus having whatever xor since emilia hash function reinforced concrete but also if you looked up polygon hermes evm infrastructure they're using loads of these circuits there's loads of these look up sorry it's inputs to circuits for ethereum op codes look up so i guess anything that you could take from outside the circuit that is traditionally expensive and brought in and evaluate cheaply

could be something like that i think we're at the stage now where it's just a lot of like plug and play which is almost exciting maybe a question to dimitry how much crypto analysis would reinforce concrete need before you can suggest to use in production i did not hear but i would guess that he would say easy straight away i think the rule of thumb is probably about 25 years isn't it for crypto systems or even longer in some cases yeah obviously rule of thumb that's hard to follow uh zero knowledge of the practical applied zero knowledge application space given that all those constructions are

new um awesome i had a quick question for you guys can you zoom back up to the slide where you you kind of list the plonkish constructions by the way i love the uh switchboard metaphor and diagram i think that's that's really cool and very helpful um yeah i guess maybe pop up one more um the one that lists basically all the recent work yeah great yeah so i was just curious how you guys kind of think about you know i think plonk is is becoming a pretty vibrant um archetype or an architecture that a lot of people have used as a basis from

which to build kind of their own kind of derivatives of which of which you guys are one because how do you think about where plank up sits in the family of these of these protocols and you know are there potential applications or use cases that maybe your construction is is particularly well suited for i know you just mentioned one but i guess i'm asking the question be like for example comparing planck up to halo 2 or something like that so i guess in the in this family of constructions where do you guys think plonk up sits we can both answer um i think i think uh almost unarguably in some cases less complex than halo two but i also think

that um well we're working on a library right now uh a few a few companies for kind of a a wider use space of art flunk which is designed to leverage archworks ability to to plug and play uh you know something between a kcg 10 curtain scheme or an ipa or ultimately fry and then but that comes more from the the code side so i think in that it's i think halo 2 by design having these sort of different sub-circuits is something we didn't go for we didn't get involved in having lookups uh and and say standard plunk arithmetic composing two together as sub-circuits for one final proof and we decided to just see if we could add it in sort of traditional way that we were

knowing for as a custom gate and then be able to just have sort of big one circuit and look for quite raw um increases in efficiency i think of these in front it's somewhere around the the turbo plant culture blonde in that i guess ultra flank is uh well it is long uh plus turbo funk's custom gates plus lock-up gates making it ultra i understand that correctly and they will also have a bit of a different construction for integrating these lock-ups perhaps it will separate it i know they use like a lot of range gates i don't know if they're necessary for the the big injury emulation though that's necessary for um that's sorry if lookups are necessary

for them but i think more towards tower blank and ultra blonde i think the the thing that categorized these and if you would list the companies like yeah meaner z master labs is people are taking the aspect of being able to just make permutations and make proofs about them uh you know some some if you imagine like a circuit is a big matrix just just some small sections of this data and check that it holds across all points with these brand product arguments um and this does the same but leverages sort of extra terms on that so that we can have lookups cool i don't know if you have anything to add to that josh uh no no i think i think luke captured

it there cool and then expanding on that and maybe zooming out one level up like how do you guys view plonk vis-a-vis other universal and maybe you can say generally plonk or your your construction specifically plunk up how do you how do you compare it to um kind of other universal uh proof systems that are out there i know you mentioned fractal i think their fractal was mentioned at some point during this talk uh there's obviously marlon um so i guess what what do you guys um how do you think about that one thing i will let you go as well second josh one of the things that i like the most about plonk is uh how many variations of it as a result of how many people are doing it um as to you know for something like

specialized range through saw for low verification time or specific proving it might not necessarily be the best i think it's now getting to to you know to tailored discussions or people could argue in really a lot of cases is the best but because so much work goes into it from so many different companies it seems logical to to heed towards it to see if it can be augmented and to use it you know if if one in in this space where i think you know human resources could be arguably relatively constrained if one's being like planck is being used to power ultimate scaling to ethereum uh through throughout the mater labs and through through halo 2 for scaling zeg cash i like i think it will

personally and feel free to quote me on this in 10 years i think it will supersede just because of the amount of work going in on it from so many different teams it must have the greatest focus and the largest number of people of all of the universal uh and unupdatable snarks it's so uh it's so flexible and customizable i mean there's a reason there's uh you know 18 different kinds of plonk or whatever and um that's also why i put your plunk here at the end of this slide it's um be uh surprisingly easy to customize for your own uh purposes if you have a narrow use case uh you might be able to to come up with a

really customized version of plonk that could fit that case better than any of the more general versions interesting cool awesome well thank you guys very much um i know we're a minute over i guess final alibis anybody have questions for uh for josh and luke i think dimitri might have might have stepped out but uh any any final questions for josh and luke before we close today all right well thank you guys very much again for uh for coming and presenting it was great to have you thank you for having us thank you thanks everyone for listening