zkStudyClub - Goblin PLonK (Zac Williamson, Aztec Protocol)

Transcript

hello everyone uh welcome to this week's edition of ZK Study Club today we're proud to host Zach Williamson of Aztec protocol and he's going to be talking to us about his recent work on Goblin plonk so thank you very much for being here Zach over to you cheers hey everyone so yeah Goblin plunk what the hell is so um this is some work that um uh I've done like we've been doing recently about um how to do effect efficient recursive proof composition uh it's also there's been a lot of research that's come out lately about folding schemes using subjects so this is not this is someone this is adjacent to that but I think it can be combined in very interesting ways which perhaps we can discuss at the end but uh yeah so that's some uh so hang on

hang on how do I Advance life there we go so what's the problem so Goblin Park is not a general purpose like skin problem it makes a few assumptions that um may or may not hold true for certain applications in the zika trader space so the goal the idea is that you have a system a setup where you have a very resource constrained um prover that's constructing zero numbers groups where what one wants to preserve privacy and you and this proofer also wants to perform um arbitrary depth percussion but the expectation of the Assumption is that there is also in this in this network a very computationally um well-resourced proverb available uh but

um they're not trusted so they cannot um they cannot it only give them any secrets and also the actual amount of like the communications bandwidth between the two previous is quite limited um I think for example if you're say building a privacy preserving Layer Two and uh and you have a resource constraint prover submitting proofs to a mempool for example um that represents transactions to be aggregated to be sequenced then you have this you have this model where basically uh client-side you've got a very wimpy prover you want to be able to recurse then once your transaction gets picked up by a sequencer by private you have a very resource resourceful um uh you have access to a lot of compute um but you can trust it so no privacy and the The Limited damage between the

two uh for the same reasons why ethereum transactions on appear to connect with can't be too large um so I said we insensitive to the final proof size so so that that's actually kind of contradicting what I just said um by incentive I mean like you know tens of kilobytes not megabytes and the final verification costs don't matter because of this was also proven um so yeah requirement so just to summarize briefly the the ZK stock version problem so um if you're defining a snack over elliptic curves then your circus will be defined over some curve where uh the arithmetic of your Gates is going to be modular the number of points in the curve which will be a prime sub loops um

and so to to verify um a proof within a proof with one elliptic curve you need to perform arithmetic what in the field that the curve is defined over and that's going to be difference to the curve that the native modulus um that's your your circuit of meticulous performed over P does not equal Q this is the problem um and it's uh it's it's not good um uh so there are several Solutions I'm just going to run through briefly from like historically because the obvious one is yeah brute force it you use your native Prime field the arithmetic to emulates a binary arithmetic and then you use your emulated binary arithmetic to emulate the prime field or nothing we really want to do but later on these two these two abstractions um adds a lot of costs so

it's like about 200 000 constraints to verify a simple proof within a proof under this model so it works but it's very expensive it's um yeah it's like oh it's not not good not good at all um so uh the next um solution um and like this is the current one that everyone's using over elliptic curves um uh the one that's that's that that's really really very elegant is using Halo 2 curb Cycles so uh you know you have two curves A and B where um they form a cycle because basically the the fields are swapped so um the the coordinate field of one curve is the same as the native field modulus of the other curve um and vice versa so you can't create these Cycles with both of these curves pairing friendly but

that doesn't matter because of the accumulation schemes that uh heliopylene had and it means you can defer like all the expensive non-native curve operations you need to do to verify proof within the proof you can kind of defer them by by kicking them to the into a circuit to find over your cycle curve where they become native operations which is very efficient so this is kind of the the best way of doing it so far but it does have some drawbacks in practice your protocol logic is probably wants to be you want to like if you're encoding some kind of critical you want that to be over one curve so you only have to deal with one prime field modulus uh and so you're going to use a cycle cut strictly for occasion I.E you're going to embed like a snot clarify

algorithm within your cycle code and that's the only circuit you're proving of your cycle curve which kind of means that to recursive one cellular main curve you really need to verify two proofs one of your main curve one of your cycle curve it's kind of expensive it's not flashing to do and also uh at each layer you still have a relatively chunky amount of money to field arithmetic to perform um you can delegate the group operations to another particular curve but when it comes to actually verifying the proof of your cycle curve you have this intersection where you're going to have a snap clip of your cycle curve and some public inputs are that's not proof will relate to claims you want to make in your main circuit and so the claim is going to be defined over your native field modulus the public inputs will be

defined over your cycle curves native modulus there's another field matched up there that you really can't avoid and not aware of any ways of avoiding it so so so it's it's better than the brute force method a lot better but it's still got some drawbacks um curved cycles and so this then leads on to Goblin plot which is basically very much an iteration of I see it as an iteration on on Halo 2 which is the idea is can we basically avoid um doing this this expensive curve bouncing step and so some of the con like one of the concepts key concept goblinplunk uses is this idea of an instructional machine I think they're called State machines in in other places um I've I um very much pinched this idea from Geordie uh um when I was chatting with

him about ckvm so this is very much coming from him but the idea is that if you have some complex operation you want to do inside a circuit instead of Performing the the sort of like evaluating the arithmetic in your circuit you cheat basically and you you just you you write the instruction you want to perform into a lookup table along with the claimed output and then you go and then you count with your life inside your main circuit uh and so and the idea of within a structure machine is you define an instruction set of like nasty functions basically and whenever you're in your in your circuit you come across you you need to evaluate one of these nasty functions you don't you just write an instruction inside your instruction machine going you know here's the inputs to the nasty function here's the claimed

output I'm going to be wrong with my life and the idea there is that the benefit of that is that you can take that that lookup table and convert it into a transcript um multiple transcripts where you have basically a commitments um to the to um to the set of like commitments to all of the claims for Specific Instructions and then you can construct bespoke snark circuits um solely to prove the correctness of one instruction over and over and over again this is a very nice and efficient because uh you can create these you can create like a custom very wide circuit feature these instructions where you can you where you can like Max you can Define like the optimal algebraic constraints specifically for

instruction for example like field representative and generally white circuits are going to be much more efficient than narrow circuits because you're doing less wire copying and also um every degree of your polynomials like every constraint in a stock second has a has a constant cost associated with Computing the opening proof goes away I think Dara put in the chat uh he's just links I'm just I'm I'm commenting here for folks who are watching the video so there's a link uh to a GitHub issue in Halo 2 in the Halo 2 Reaper which I will put on the YouTube link but I don't know Derek do you want to mention you just want to give some context around that comment if you can't talk that's okay bottom line is he what he said is the best way we had to avoid native arithmetic or

public inputs for Halo 2 is in this issue so um yeah so anyway so folks I'll link this in the in the video I'm sorry interrupt oh yeah I'm I'm not I'm not up to date with this isn't greatest inhaler too um I'm aware that the noise is a problem I'm not familiar with the latest on how to avoid it uh so yeah cool um so so so so one of the so we have this idea of an instruction machine was fermenting in our heads around um basically if you want to do complicated operations in your stock circuit you don't you cheat you put them in the lookup table then you make it somebody else's problem um uh and then you'll do is you can construct proofs with these instruction machines to prove all of the like the credits of the transcripts and so so

what we're thinking with this is well hang on a minute we have one we have a nasty function we need to do uh in and I'm stealing Ariel's nomenclature here he was talking to me about proofs of nasty functions um uh so we have these we have this nasty functionality which is non-native elliptic curve arithmetic this particular scale of multiplications so why don't we just shop those in a lookup table and forget about them and find out try and find a way of um uh like solving this problem uh at uh at some in some abstraction here which is not like within a recursive cycle of circuits so one of the things we do here well another concept we need is this concept of transcript aggregation so the idea is

inside your stock circuit you want to do elliptical scale multiplications you don't you cheat instead you write them into a into a lookup table uh so you can use something like click up all this like one of the the stuff that Oracle has been doing or whatever like there's loads of techniques but the the basic core idea here is that what you're doing is at the end like the result of this operation is that you have um uh columns in your circuit which describe the elliptical scalar multiplication operations they need to be performed and they're cleaned outputs and that those columns are going to become basically directly translates to polynomial equipments so you have basically equivalent to the transcripts uh at each recursion layer and so the idea is you need some way of doing

transcript aggregation combined like basically combining aggregating multiple transcripts so so that at each layer of recursion we're just tracking one transcript um and so this is not a faulting scheme because in Goblin plunk this transcript the size of transcript grows as you recurse um you'll if you have imagine you have two snark circuits they're both needed to perform non-native skill multiplications um the result of doing aggregation is just you have a transcript polynomial which is just the sum of those those um the the input transcripts so this isn't too much of a problem because if one entry inside this lookup table is going to be an instruction to do like a non-native scalar multiplication so there's not going to

be many very many of those per circuit so this transcript description is not going to grow particularly quickly so the degree of the transcription polynomials is going to be relatively small compared to the degree of one of the circuit um size and yeah if you're using multilinear if you're using subjects multi-linear color commitments this is some really really nice ways of like trivially aggregating transcripts um I can get into it a bit um and so the final technique with goblinplunk is this concept of cab transposition which is very much stolen from eip4844 where the idea is uh you can prove the equivalence of commitments to the same set of data over two different duplicates and so this is

very useful because effectively what I'm trying to get to here what I'm trying to build up is that in Goblin plant what you want to end up what you end up with is you're doing you're recursing repeatedly over and over again at um uh in you know in some recursion stack and each layer of recursion you're running a Brute Force verification algorithm however whenever that algorithm comes to the point where it used to do elliptical scale multiplications it doesn't do the multiplication it shows your instruction into a transcript and then you combine those transcripts as you recurs so at the very end of your recursion stack you're going to have this chunky um polynomial commitment to your transcripts that you then need to prove the correctness of and uh

so how do you do this well the trick here is that you commit to the same transcripts over your cycle curve you prove the equivalence of the two committed polynomials I like the data within them and then you just and then you construct a proof of correctness for your elliptical scale multiplications in a circuit to find over your cycle curve where all of the operations are now native scale multiplication it's not non-native and so you know it reduces the complexity by about two orders of magnitude uh and so how do you do curve transposition right I've just glossed over this well okay you have two commitments over different kinds of different Prime fields to the same information uh well there's no magic bullet way of doing this but there is a way that's

pretty pretty fast uh so um what you do is you just use a regular polynomial equipment scheme like IPA to open the commitment of your cycle curve that's a random point and then you construct a snot proof of your main curve where the polynomial equipments form columns in your circuit and your set and the circuit is basically a a bespoke circuit tailored to do non-native Prime field operations where you as a public input you take in the random challenge you used over your cycle curve to open those polynomials and you literally kind of in your circle you iterate over the coefficients of your polynomial and you you construct the evaluation of that polynomial um in the field of your cycle curve so

you're using non-native arithmetic which is not particularly difficult to do it requires um for each polynomial each degree of your polynomial which in this case is going to be an instruction to do an elliptical scanner mole requires one non-native field multiplication one non-native field Edition and you can just combine that you can just create one one big chunky constraint that does does that um as a premise of operation so that's a lot of information big info dump but this is um to try and summarize it all um you know you you want to do your main recursion of a curve a um and so and the the operate the scalar multiplication operations of occur that you need to do when you're verifying you

you delegate that to this imagined elliptical voucher machine via this instruction machine process where you you're shoving the operations into a transcript and then at each recursion layer you're aggregating the uh the the instruction machine transcripts produced at the current layer of recursion with the with the previous aggregated transcripts and then at the very end of the recursion stack uh you you provide a proof of correctness or a transcript um to to the elliptic curvature machine now this is going to be defined over your cycle curve and then use curve transposition techniques to validate that the transcript you shoved into your Overlook to curve VM proof is equivalent to the transcripts that

was built up in your recursion stack um so this this is a funky sequencing you've got to do here to make sure that your challenges are generated in the right way so that you look you know you can't do rewinding attacks um but the this is the um the overall architecture it's not particularly simple or elegant um but I do believe it is very very efficient so um to try and dive into this in a bit more detail um so you know you're at each at each level of recursion so this red square is basically defined as is the idea is that you're this you're constructing a proof of a stock second uh and um the the blue squares is basically aggregation algorithm so you're saying okay as you as your as you're

constructing proofs the previous proofs you'll want to you wanna you wanna verify run a recursive verifier on the previous proof um technically it's more it's not a verifier it's an aggregator because it's not fully verifying the proof um uh and each layer you're shoving your expensive operations into into these transcript governments which are part of the proof um and then once you've finished with your recursion um you have this final proof and within that proof you're going to have commitments to your transcript polynomials uh and so um you take you you you run this instruction machine circuit uh which basically takes as an input the transcript polynomials um and

um uh and would and the um the kind of the the the sorry let me I'm I'm doing things I'm like at the very end of your recursion stack the next thing you do is you make this ECC VM proof so the idea is the proven knows okay they know what's in the transcript they commit to the same information over your cycle curve so obviously like you you need to make sure that um there's going to be some range checks involved here to make sure that you're not overflowing the modulus with with contexts where uh you prove the practice of much of it looked at Cub scanner moles over the cycle curve so it's all nice little natives or cheap um and then um as part of making that proof you will have to the proof will have to open those

um uh the transcript problems Committee of the cycle curve at a random point so we're going to reuse that um and we're going to then feed that information into the into the instruction machine along with the original transcript and what the instruction machine is going to do is it's going to produce instructions for a non-native field virtual machine to um where the instructions are going to be what's the instructor the the non-interfield operations that need to be performed to evaluate the coefficients of the transcript um as if they were coefficients committed over the cycle curve and then that those instructions get fed into a non-native field patch machine you get a proof outer and then boom the very end of this you have um four proofs

um to prove instead of one but the idea is that um you now uh yeah basically it's it's a way of minimizing the amount of work that this prover is doing because the idea is that you have these four posts that's the sinks you can kick them off to some third-party aggregation service to to combine and you don't particularly care about the costs of verifying these four proofs as long as it's as long as they're succinct so it's not too painful um succinctish uh anyway should I should I stop on this for questions because um yeah I know I've just gone through a lot of a lot of info here yeah thanks this is great uh does anyone have questions uh so Dara is putting in some comments

um I let me uh uh uh dare if you want we cannot hear you Dara so if you've been trying to talk then yeah there may be an issue with your mic we cannot hear you um if you want to type your question okay so Dara's gonna rejoin and come back does anyone else while there is doing that does anyone else have questions for Zach maybe not um okay yeah everyone maybe still processing the slide there's a lot of information on here um yeah but if

proof does that include the transcript from all the instruction machine calls okay so it includes the latest transcript so the idea is that um I'm gonna get into this in a in a future slide but the idea is each proof contains the basically the old transcript and the e-transcript and you can very easily if you're using multi-union stuff you can very easily derive the current transcript from the old transcript and then you transcript um and in doing so you implicitly put up are also proving the corrects of the aggregation that the old transcript plus the current transcript equals a new transcript so so the each like so this doesn't contain all of the transcripts of the previous proofs it can take well it contains two transcripts like the the transcripts at the previous layer and the transcript

of the current layer and the transcript of the current layer contains the aggregation of all of the all of the info like the the sum of all the um the thing the instructions that have been added um as as the previous beam requesting dire uh how's your mic or no we can't hear you sorry if you're talking there we can't hear you um for enough just asked a question do transcripts go on size is more steps are executed I believe you said yes yes yeah so so I'm making a very a very explicit well implicit assumption here which is that uh the every entry into transcript describes a expensive operation to perform and

therefore the transcript will grow at each recursion layer but the idea here is that the overall size of the transcript is not going to be it's going to be much much smaller than um the the the degrees of the polynomials that you're committing to for your circuit uh because um like to give an example like to do a non-native scale of multiplications between like Four and Twenty Thousand constraints and that becomes one uh one degree of your transcript polynomial so it's um yeah it does grow but as long as the instruction as long as each instruction represents something expensive um the assumption is that's not going to be a problem you hear me now yeah yes yes excellent okay um so these four proofs that you get out

at the end um but what kind of profiles I have because I how expensive are they to verify so so the Assumption okay so so making some explicit I've defined describe some explicits I was here so um the way we're planning on building this is using a half pairing friendly cycle where the red proofs would be fairly succinct and one would have seem very cheap to verify um like these virtual machine circuits the assumption is that they'll be quite wide for maximum efficiency so like 70-ish columns so you know not trivial to compute to verify but but um like you know you're talking like like 120 or something scalables possibly for each proof and then the the cycle curve

proof will be more expensive because it's the assumption is is um uh the commitment scheme will be IPA and therefore there'll be this linear time step you need to do where it'll be linear in the site and the degree of the the VM circuit but so so um the efficiency of the elliptic heavy on circuit matters of radio the the um the current kind of like architecture we have at least on paper we haven't built it yet um is can do one like a variable base native scale or multiplication in eight rows and about 70 columns so the assumption is that the degree of this politic curve um would be that large and can be can be stomached by um by whatever verifier is

going to be consuming this proof so so the red proofs here if you're using the the half um half pairing cycle thing the red proofs are kzg proofs on the ECC VM this is an IPA proof uh why that way around so it's doesn't have to be that way around the the reason we would do that way around is because uh caseyg is much cheaper for the proverb um to compute an opening proof for the night than IPA so it's just um gonna be um if one is ruthlessly focusing on optimizing The Proven efficiency um for the for the person constructing this this Goblin stuff

um you'll want your main recursive SEC your main circuits to be to be over your cheaper curve which will be the kcg Curve but yeah there's no fundamental reason you could flip the curves around I see um um or you could do one step of a Halo recursion um to move that um the pink proof to the to be a kcpg proof yeah um well you could just you I mean you could or you could you don't you don't need a high paying for any cycle I'm assuming this this abstraction would also work for if you're if you're using passenger and develop curves um because I saw your comment but you're saying it's similar to what you guys

folks are doing with Halo 2 um but like defying the other Catholics again yeah exactly um I mean I was looking at Heritage and thinking like how how can I avoid how can I avoid verifying verifying this cycle curve free for every layer I don't because it's uh because because uh because I was way too lazy for that um yeah unfortunately it's it's too complicated for me to explain if you look at that ticket then there's a diagram um which shows it's a data flow diagram showing where everything goes but to to try and explain it in a video it I don't know how I would do that sorry fair enough um yeah I can't look at the chicken because I'm sharing the screen but I will look it afterwards and and

pick your pain on it but um there's also an additional considerations because we're planning we're building this like honk Brewing System which is very much like hyperplunk where it's using some checks uh which is like it's really really nice for the very very efficient very fast number of teas but one of the downsides is that the verifiers is got a logarithmic number of hashes to do so actually verifying proofs is not like the the grunt work the verify is doing outside of the non-native arithmetic it's not completely trivial anymore and so yeah so the idea of having to do like verify like at every person like do it verifying another proof over the cycle curve plus the non-native it was like Earth's not good so we we were thinking

about yeah like so let's just not bother let's be lazy but just uh but just to put it back in the context you're assuming the verify here is like a roll-up server right that theoretically has you know some stronger abilities yeah exactly if you send all these four proofs to a small contract then then it's then that small content is going to cry and it'll cost you hundreds of dollars in guest views because of the IPA verifier so um there is that assumption cool I I so I guess you can have some kind of hybrid where periodically you um you compress um

your application proofs um but you're not doing it on every step as you you would in the original hello paper yeah exactly because this is not if brilliantly this is what this construction is not really succinct because the the transcript grows as it recurs so yeah as you said like you can you can just fix the recursion depth um to some hard limit and basically then like wrapper wrap a bot like put like fix fix a recursion to a hard limit and take that entire protocol then just put it in a box and say that this is this is now your recursion perimeter where the idea is like instead of um doing like Halo 2 recursion at each recursor cycle like you do goblin

recursion for like a hundred cycles and then you take all these four proofs and you and then you you request those using handle two uh and then you then you have a like a like a a generic accumulation scheme that that doesn't have any like linear growing term yeah it's eventually we're going to work out what the um the most sufficient way to do this is when everything's all up and up in the air at the moment yeah and another I think another useful application of this is folding schemes so so volumes have become quite popular recently and there's been lots of really cool stuff done with them with like sangria another Supernova pipe whatever and and sorry since uh we since I'm sorry just because he's here srinath uh

author of um hello hopefully you can make you know maybe you have some comments at some point about comparing contrasting or commenting on the applicability listings there but anyway I didn't mean to interrupt you I just want to call this or not is here uh and he presented I think two weeks ago supernova um yeah so I mean like the thing I'm I'm thinking about here is that um if you're using something hypernova where you need to do one I believe like if you wanted to use IVC you need one non-native secular multiplication for each default um which doesn't very much work but zero work is better so instead of actually doing that you just use goblinplunk um uh so you just edit but each time you have like each fold you

just shove that non-native operation into a lookup table and then after say 100 or six volts maybe you um or like add some fixed constant number of folds you then um do this transition step to prove the correctness of the scale of miles and then you go again uh and it's it's um it takes an already like relatively low cost uh folding and basically makes it disappear I think yeah I just noticed you got on the slide the the sides of the sizes of all of these intermediate um things in terms of group and field elements and that's interesting they're smaller than I would have expected well like take them with a grain of salt because uh not implemented

with my code yet so yeah actually it could be could be making some optimistic yeah well maybe we should move on there so in terms of costs yeah so the napkin math here as I'm thinking uh you like each non-native scale multiplication instruction becomes reduces to doing one native scalar mole and the ccvm and five non-interfield operations in the non-inter to field VM and y5 it's because uh one is like once again I'm all instruction in the VM needs five columns um you have four for your X and Y coordinates because you need to split them up into one to eight bit chunks and then you have one and um column for your Skinner multiplayer um so that's five

um uh so but if you're if you're you depends how you slice it I mean you could you could uh if instead of the VM instruction being doing non-native scan them all the information is you know like do like do 15 miles required to verify proof or whatever then that would get reduced uh but this is like the rough napkin matter plonkers constraints I reckon that um uh like the the the the goblin plant costs are probably about like eight thousand plunkish like by slunkish I'm saying I'm imagining uh like width for ultra plonk um because that's the one thing almost most familiar with them so my my claim which are not yet proven in code is that uh the costs of like doing one layer of it Encore Ultra progression

reduces to about eight test thousand is blockage constraints plus the cost of the the rest of the therefore algorithm I think I think we can be better than that my my hope is called in the cost of one area of occasion getting it down to about eight one nine two plunkish constraints that's uh that's my goal at least but um until I've actually sounds feasible yeah um and like that with this that basically makes recursion uh just a like a disposable primitive you can just throw in everything because it's so cheap which will be pretty pretty pretty pretty cool uh so

yeah I don't know how we're doing for time because I have I have a few slides for like the details for like the VM designs Etc but um I mean well just just so you know it's uh we typically go up to 90 minutes so there's still an hour left in the session so I think yeah just yeah I think we can proceed we got plenty of time I said all right so this instruction machine stuff so so technically for what I described the goblin plump you don't really need this concept of an instruction machine because you only have one instruction which is doing electrical multiplication the reason why this this instruction abstraction I think is useful is because if you're doing Goblin plunk you might as well build in a structure machine into your

protocol architecture um and use it for more than just non like elliptic curve operations for example you could have an instruction machine to do cat check rounds chart two by six rounds um big integer arithmetic etc etc uh so I figured I might as well just describe a little bit how it works um so again there are some kind of explicit details here which are not um which are like not not um uh like you could generalize this a lot so I'm saying the transcript has four columns that's because we're planning on building it adding it into a width four plonkish proving system so if you had more columns you probably want your transcript to be wider as well uh so the idea is that with the transcript is going to be the same as the width of your of the circuit that you're making a

presetter uh where um the what did I say m describes the transcript size um okay so um so so one convention we could do is how do you actually get instructions into the transcript well like the simplest thing you can do is you just have a convention where the transcripts um like the the instructions that you where you'll like the constraints when you're writing into your transcripts you make you put those at the very start of your second and then you just have a selected polynomial which copies them across and then if you need those the transcripts outputs also in your second constraints so that's just the simplest way of doing it you don't even need permutations or lookups

uh um and so this is the idea of an OP code um so again I'm like using assuming that that you have some similar to morphism to break up your skin and your your 256 bit scanner more than 228 bit chunks and that's what Lambda hair is uh so the idea is the instruction will be you have these 200 scalars um Z1 plus under Z2 times B add it into an accumulative a that will be the off code uh um and uh yeah um so here this is like a weird work example that even I'm struggling to understand um so the idea is that like like this like this as as an example of what one

could do is like the the First Column here is the op code value and then the the SEC the the second or third columns are like Define your x coordinate the fourth in the like y4 and Y2 discuss your white coordinates and Y3 and y4 just go to Z1 and Z2 and so the idea here is that um your structure would exist in transcriptavers um so I think what I was trying to exp trying to get at here is that um you can if you if you have a very complex instruction for your instruction machine that that requires more uh more entries than you have um room for in your transcript you can just split it you can just pack that instruction across multiple rows uh and so here's just a little bit of an aside for if you're using a multi-linear

preview system how do you aggregate transcripts because it's really nice and simple so if you're using a multi-linear um printing system like hyperplunk or hunk which is still not yet published but we will see um the idea is that your your subject requires multi-denial polynomials but multilinear polynomial scheme schemes are not the best um they're very painful uh um but there are some there's a very nice technique that was played in The Gemini paper where you actually commit you basically you have a transformation there but you have a particle which transforms claims about the evaluations of multi-linear polynomials to claims about evaluations of univariates polynomials and you actually commit to your polynomial so um in the universe

scheme where typically uh the the the representation is just that the coefficients of universe polynomial um are the um are they kind of the evaluate are the other um the vertices of the of your of the Boolean hyper Cube that you're that you're multilinearizing um just as an aside this is a really really nice way of doing things because hello would somebody saying something uh I heard that too it may have just been a mic misfire so uh yeah uh keep on uh keep on rolling one of the nice things about these transformation layers is it means that getting shifts is very very nice so for plonkers systems you

need uh it was very very helpful to get to have a cheap way of getting uh commitments to your shift like shifted input vectors with this vectors um so if you have the if you if you if you're representing your probably name as an inverted form you can get the shift attributed by just multiplying your polynomials by X um uh which is easy to do um but uh basically um so yeah the audience you have some universities and univaritization map which Maps univariable polynomial smaller linear polynomials where your coefficient univariable polynomials represent the value the vertices is to be put in hyper Cube why does this make it nice to aggregate transcripts because um you literally just kind of just combine them so the idea is that uh you as your let's say at some layer of

recursion you have equipment to the transcript of the previous layer why old and you have a commit to the transcript at the new layer at the um like the white wine and the idea is that the the diff you can take the difference between these two to extract the transcript um at the current layer which is kind of pretty easy to do because you literally just because one I'm assuming you've got an additive homomorphic commitment scheme here you just subtract the the old transcript from the new transcripts and that gives you the the coefficients that you want is to sit there in the wrong they're they're at the wrong monomial Powers so you're just downshift by one of x to the m where m is the is the number of entries added in the at the current transcript layer so I'm making some assumptions here I'm making

an assumption that the the number of entries added to the transcript is known as part of the verification key so it doesn't vary for a given circuit uh and then you can just use some simple consistency check so you basically say um okay you derive this transcript polynomial YX um by taking like the difference between the new nail transcripts uh I think I yeah and and they're just downshifting by x to the m and then you do some consistency checks where you just check that um uh the um this this output polynomial um all of the um for all of the degrees that higher than M uh there's no data that you have everything is zero um and similarly the

uh you do this you do this um copy check again basically where you're saying that um the first for the first M rows of your circuit uh y w i on the leg the Y commitments to a second and for the first M Rose uh the your transcript polynomial and your y upon the numbers are equivalent because you're you know you're writing you're writing instructions to do transcriptions uh so I can go into some more detail but this is kind of just a just a bit of implementation detail it's making it's making a lot of assumptions about the premium system that's being used um which which is kind of independent of goblin blockets as a scheme so uh yeah the server is only useful for like multi-linear subject systems um

so yeah uh so VMS um so um I mentioned before that we have the concept of like an electric current virtual machine and almost a field virtual machine these are very primitive VMS the only reason they're VMS is because I'm making an assumption here that when you're recursing in Goblin plonk the circuits that you're recursing over are not uniform as in they're different and by extension the verification algorithms can be different um uh which that means that by the time you've you've finished uh doing a bunch of recursions uh you don't know like like the actual arithmetic that you need to perform in your transcript is not going to be known ahead of time if it is then you don't need a VM but to give an

example of why this may not be the case um like even imagine you're just you're you're rehearsing you're verifying the multiple hyperplunk proofs or honk proofs because the um the verifier uh algorithms uh um uh The Verve has to do with scalar multiplications that's a logarithmic in the circuit size so if the second size of each circuit your application stack is different then yeah again any two different operations similarly if you have you may have different advertisations at different layers um you know with different polynomial identities but maybe which means you may have more wire commitments more advice wires Etc and so the Assumption I'm making here is that once you once you have at the end of your academic when you have this

transcripts the like the verify the verify doesn't know precisely what operations need to be performed so that's why you have a VM uh so so that you can you can um you can kind of build up the build up the instructions uh over time and they can be actually just part of the witness statement uh but these views are very primitive this isn't like they like they have an accumulator that you can add stuff into um and you can like well here's an example instruction set for eccbm so the idea is like you can set the accumulator to to be the result of multiplication you can add a multiplication into the accumulator you can do an assertion that accumulates equals some value uh um uh so so basically like super super primitive operations so so that so they're barely virtual machines

certainly you don't have memory or registers or anything like that um virtual machine this is an example that can be expanded but the idea here is that um the the idea is to evaluate some somewhat General arithmetic statement that can be um used to represent like a large set of non-interfield operations um so this this may not actually I think we're probably actually going to change this by the time we've implemented it but the idea is that you can do things like add and or Supply um in inside the internet field machine or you could do like basic linear operations um uh and submitting the uh the modulus the idea is that the the actual modulus of

this um the operation you're performing and the VM is not fixed uh so because if that's the case then you get some other nice stuff for free it means that uh you can get big into your arithmetic for free which is kind of useful um uh for other use cases it means you could do just really put it together over over arbitrary 256-bit module so you can do you know sector versus K1 as well as stuff over your cycle curve and your main curve so it's um yeah so that is you wanna you basically want one row in your field virtual machine to just do some some somewhat General arithmetic statement that that covers a large a large um amount of uh

operations uh so so um so I've done a bit of brainstorming about how to do this ucpm not yet built it because been kind of busy with other stuff um but I'll see him is planning on actually doing doing a spike on this soon machine is you can just do the if you want like what other algorithm you're going to implement because you could just do the the normal double then add um or doing ECC multiplication but that's kind of slow it's kind of boring and with Lookout tables you can do much better so you can use basically my idea is my thoughts I take the best algorithm that exists in the real world and just put it in a circuit um using lookup

tables where you use this this kind of like four bit sliding window knowledge and format 30 bits if you take your input Scala that your Skinner multiplayer and you split it split it up into four bit slices but each slice isn't isn't zero to six to Fifteen it's actually minus 15 to 15. um uh where where the values are ordered so minus 50 minus 30 minus 11 Etc that's really that's that's efficient because it means you get there's little bits of information but um uh because um inversion negations are basically free for elliptic curves um you already literally needs three bits of data in your lookup tables which is nice um so the idea is with this four four array sliding window method uh so the thought the thoughts are that to make

such a VM circuit you'll have three distinct blocks in your circuit like like sets of columns your first sets of columns will be all transcript validation but basically you're iterating through the transcript robot robot row and you're doing all the consistency checks equivalent like all of the the basic logic everything except the scale multiplication so um uh but you're just making sure that like the like you know if there's a current outputting is added to the cumulated correctly that the operation like depends and your your writing stuff to the lookup tables depending on the um what the operation is saying the the second block of columns in your circuit is for um scalar decompositions and point table computations So that obviously taking each input scaling multiplayer and

you're decomposing each of those four bits non-adjusted form version verifying that the decomposition is correct and then you're writing that those decomposed values into a lookup table so you're saying for a given point index and a given round of the scalar multiplication algorithm you shopping uh the the value of your your Sunday window Scala into a liquid table uh then the the next and so also in this block of columns you're doing the the Point table computation so um if if your sliding window represents the points p 3 p5px11 p up to 15p then you need to compute these and put them in a lookup table so we've got the that's what that's what the the um the the point combination block does it basically it um the transcripts from your the transcript will basically write

a value into the into the uh into the section of your circuit right to point in uh and then you'll double the point to TP and then you'll compute 3p 5p7p et cetera and you put them on the lookup table that's associated that maps to the various um sliding window forms uh so those are the those are the first few blocks of classical validation and then scalar like like decomposition Point table computation the third block of columns is the uh actual scale multiplication but basically my thoughts are you have um you have enough columns to perform four-point editions and what you're doing is you're basically iterating over your points pulling out those sliding window values from the lookup from from your lookup

tables you've computed then using those to pull out values from your pre-computed pointer table again using a lookup protocol and then you're adding them into accumulator and then um you're also doing some some tracking to make sure that um once you've like for a given round once you get through your point through 40 of your points you then need to double the accumulator to four times um and then and then the new increase around counter and you go again so this is a lot of logic to to perform and and it's somewhat tricky to concode it within polynomial arithmetic but it can be done I'm fairly competent of that at least and um um so I was going to ask the the most uh efficient algorithms um if if you allow variable time algorithms um for multi-scale multiplication

answers outside the circuit I think it's like typinger and um boss Costa um that involves putting points into buckets yeah I I had I I'd always assumed that those were going to be far too complicated to do in a circuit um is actually possible to occur in a second I mean it's a bit mental um what I'm describing I think it's sometimes referred to as the Strauss algorithm which it's not asymptotically optimal but for if you're doing a relatively small multi-skin multiplication so like less than two five six points I believe it's better it gives you better performance in

pippenger because the constants are better um right okay but yeah um it's uh so um uh so yeah yeah but it's just kind of I guess the devil's in the detail um this is all just paper designs I'm making some claims here I'm making a claim that is possible to implement Strauss uh in polynomial algebra I'm making a claim that's possible tables but uh yet to be proven um but uh I mean we we know it's possible because um the the um our spiritualization is complete uh it's just can you do it without making mistakes um

not the first time around but you know my my plan is basically implement the algorithm put on GitHub rag on Twitter that is perfect and it has no flaws and then I'll get a bunch of reply guys to Define all the flows I'm Gonna Fly Girls and reply girls my apologies reply non-binary people I want I want I want all the angry reply people um absolutely so and by the way oh yeah this is unfortunate columns at 70 columns um at least um uh but uh um but you know 70 columns eight rows what really matters is the Euro area of your circuit and that area is very tiny to do a variable based scale them all so you know um beats the multiple tens of thousands

you require for non-native field non-native scale multiplications um yeah so that's the that's the rough idea for the camera's machine the 90 field virtual machine I think is less um less unknown because um I think that the EVMS EK VM folks have done done one or two already um but uh the way I was thinking about doing it is uh the idea is you have two sets of columns the first set basically evaluates all of the non-native algebra like the algebra for anonymous field operation uh like as I asked to find by that word formula in the other earlier slide then you have a second set of columns um that do the range checks so the idea is the the the the columns that do the

algebra um each for each non-interfield element that they're that they've got uh they shove it in a lookup table to say oh you do arrange check on this and then you do them in a separate section in your circuit the reason why you would want to do that is because um that way you can get rid of duplicates so that uh the the when you're when you're doing your range checks your only range checking unique values uh and not duplicate values um which will reduce the complexity of the circuit do you see amount of work you're doing um so absolutely click up or another lookup table protocol to where duplicates so uh I'm assuming like these column numbers assume that you can do like degree 17 polynomial Expressions uh in your main plot polynomial which if you're using

um if you're using autoplank or like a blanket star system that doesn't use that doesn't use uh subjects is insane because because you need um crazy ffts but I'm I'm hoping that the plan is the Hope is that some if you're using subject verticals because you don't do ffts it actually might be tolerable to have high degree Expressions um but if that's not possible then you just it just means you need a few more columns so it's not not the end of the one um uh and then you have the transposition circuit so this is the bit that's kind of complicated so the idea is um the for the elliptical virtual machine the way you want to structure your transcript inputs is going to be in a way that's optimal for the VM which means you'll want it all in one row but the way you're writing the

instruction into your into your main transcript is going to be optimal for the width of your main circuit which may which means that you're probably if you're so here for example if the main circuit is four columns and the the group came out of the curve the M requires six columns then you need to do some funky Transformations because uh what's going to happen is part of this transposition transposition sub protocol is that um as part of the grumpkin eccbm proof these transcripts polynomials are going to be opened at a random point and then you're going to and then what needs to happen is you need to take the the information in your main transcript that's over your main curve that maps to

these columns and basically interpret it as if as if they were as if they were part of the grumpkin transcript columns um when you're evaluating your polynomials so by that I mean like in this example for example um uh the the values here x low index high before um need to be com like they combined for one column in your in your Easter CBM same with the Y Lo and Y High values and then Z1 and Z2 they're very independent columns and the op code is is an independable column but here it's been duplicated because this well it doesn't need to be duplicated but there's a redundant um redundant value here that's not needed uh and so the idea is that the the transcripts this transposition circuit

um is going to iterate over your main transcripts and construct the this um uh and and create construction instructions for the non-native field virtual machine that are consistent with what needs to happen to um to [Music] um compute like it's basically like open the transcript information as if they were coefficients of the group can use the CPM polynomials so here for example we're saying let's do multiply so at row I let's do a multiply and add like I have the nine field Bachelor here so you multiply an ad um where over um like Zeta and X more the the grumpkin time so that's

basically saying that's that's evaluating um one degree of the um of the exponential here um in in the uccm and so the idea is that if you're doing if m is the number of Easy Ups plus one then from rows I to m you will want uh like whereas I to M will exclusively be um multiply and add over the x coordinates um of the um of the information in the in the easy transcript so basically what's going to happen is as you're iterating over the main transcript you're just taking the x i and XL values and you're shoving them into the first like into rows byte like zero to m and then similarly you're then taking um actually maybe and then for the next

M resin your circuit you can put your your evaluation multiplying ads on Zeta and Y for so that that gives you the the Y column and then you do the same for Z1 you do the same for Z2 you do the same for the for the opcode row uh and so there's there's a there's a weird kind of like um it's a very it's a bit of a weird transformation that's happening here because you're not you don't want to open the main transcript polynomials you don't evaluate the main transcript polynomials over the cycle curve modulus you want to evaluate the polynomials that you would produce that would get produced by the eccbm and the values of the cyclical modulus so there's some there's a weird funky trans

transformation that has to happen here but um it's it's very doable um so like the end state of the 90 field transcripts after processing the main transcript will be that uh each virtual machine operation becomes as I said like five of these non-interfields VM operations where you interleave them so so the idea is that the monitor field VM um at the accumulator only works on one polynomial at a time and if this polynomial degree M then it means that you're going to have five M rows where like the first M like where where each block of M rows is going to be working on one polynomial so either the polynomial for the x coordinates upon the name of the y coordinate the polynomials for like Z1 the polynomials for C2 multiple polynomials for the for

the op code uh m and yeah the reason why why it's um essentially is actually M plus one rows um for each block is because at the very at the um at the final uh you also need to shove in an asset equal up code um uh every emeros to check that the the resulted resulting computation is is is is uh lines up with what it needs to be um so this is this is um possibly a slight overcomplication that's to do with the fact that the curvm transcript format is not the same as the format as your main transcript format um this problem will go away if you could you not just make them the same

yeah uh but um uh you could uh I can't quite remember why I was so gung-ho not making the same when I wrote this up I think I think the idea here was that um actually yeah I know I don't know um perhaps it's just need to see complex you just make your main circuits with five this kind of goes away so yeah um yeah but anyway if everyone wants a different then there's a step you can do um to to transform them properly uh so yeah details about the transposition circuit

I don't have some worth going over this because I imagine this this is like a month old and it's already Obsolete and I haven't even wrote in a line of code about it so um but the idea is yeah there's going to be a little bit of a little bit of um algebra if you want to do these Transformations there's a bit of a bit of a cost but it's pretty trivial compared to the costs of actually proving the eccbm proving Anonymous if you'll be in so it's kind of a not that relevant um oh this was originally this was an internal talk to my team so this is an internal domain but hey I'll share it with you guys as well um so yeah this is basically how we're planning on tackling it um implement the VMS first and then add this concept of an

instruction machine into our into the into our like circuit Builder code um and then um kind of a use this use use these VMS that we've built that we will built to um uh to like in our recursion code instead of actually forcing the office of operations the recursive verify circuit will just um instead just use this this transposition comparison to build it up and it's like like an instructor machine transcript um so yeah I mean it's it's fairly complicated but you know I think it's eminently doable and uh yeah like at a very high level um just the idea of deferring non-native

elliptical operations that are required to recurse uh and then transforming them into a problem over the Recycled curve like reduces the complexity by about an order of magnitude or more compared to brute forcing um and and I think has uh better constants than um doing it doing it at the age of recursive layer like can I do so yeah that's that's the golden plunk um lazy recursive for your composition uh thanks for uh thanks thanks for following along and yeah it's very very happy to answer questions any questions folks huh thank you awesome yeah thanks thanks a lot Zach um man that was a a lot of information in a short time uh thank you for uh

organizing it uh as well as you did and if you like I mentioned if you want to share this deck with me I'll put it in the YouTube video I link a couple of I just for everyone's just to say out loud here for there's some comments and uh one of them is reference uh Dara reference the Gemini paper which I think was about elastic snarks uh and Mikhail one of the co-authors presented that actually at ZK Study Club so I'll link that in the YouTube as well um and yeah and then Dara also linked a CK Study Club on uh MSM algorithms which I'm assuming we discuss as pipinger I'm not sure if we discussed uh what was it uh with the other one uh yeah thank you

I think I'm not sure which of those were mentioned yeah but great opening up to questions does anyone have any questions for uh Zach or comments uh on related work I mean again potentially maybe I know we've talked about hyperplunk a few times in here and hyper nova um so maybe maybe it's it would be interesting to hear your thoughts on the relevance of this construction to your work not to call it not to call on you but if you feel like it would be interesting so um but yeah in general if anyone has questions feel free in um go ahead and ask stunned silence follows Zach's

presentation yep hopefully some of this might be a bit clearer if if uh if we can print instantiate it in code um yeah yeah I guess the you have a bunch of I think costs in there but I think yeah concrete benchmarks definitely I think I mentioned this earlier on the side chat that it would be interesting really interesting to see this concretely instantiated and benchmarking that um yeah and of course after implementing something it's it's easier to explain it in general even if people are not reading the code yeah yeah so uh yeah keep keep uh you know um in hopefully in a month or so we'll have a POC maybe two months

um depending on our time what other stuff gets in the way um but yeah internally we're pretty we're pretty bullish on this for like taking the taking the the pain out of um like taking drawing the stick out of the costs for recursion uh so uh yeah combined with uh like folding scheme stuff um uh I think it it makes occasional IVC like just utterly utterly trivial even over arbitrary circuits yeah I think I mean that's obviously a theme across a lot of development in the space um and uh yeah it's it's been interesting to see I mean this is something that for zprize we're looking at exploring this year how to create yeah some categories around around applying different types of

recursion recursive techniques to you know for for computations that otherwise would be impractical so so for the Z price thing uh would that be sort of Define a higher level problem and you can use any recursion method to do it or would it be targeted towards specific methods yeah I mean it's always it's a bit of a trick so like ideal is what you just said Dara I think the trick the trade-off in running these competitions is always the more open you make it the harder it is to judge basically uh you know yeah you could really if you want to open all the way up you can say hey invent your own new proof system if you want to but then of course I have to make sure that's correct we have to make sure it's you

know it has to be audited right so you know then it's okay maybe you fix it to like a handful of proof systems or recursion schemes you know and so you kind of you there's a so there's this tension between like the degrees of freedom you give the competitors and the ability easy ease of judging but the goal this time is to move it up from you know last time was really all about the msm's low level and now this time it's more about like hey what's the problem we care about use any one of this number of schemes to kind of solve this so we talked specifically yesterday at the steering committee meeting we met we talked a lot about Nova and and just generally like Hey how do we work Nova in and giving people more flexibility so hey you're not just stuck with Nova but

any recursion scheme could work and just I think that would be good back to the point about concrete benchmarks and there's so many great new schemes coming out for different you know that I think have a wide range of applications it would be good to just concretely see for this application or this application like what are you know what are we what are we talking about in real world numbers and so anyway we have uh we're going to be defining the prizes over the next week and we'll release some more info about that but yeah definitely planning on sharing that in the ZK Study Club telegram groups it would be awesome to get feedback from you all specifically on your thoughts but um in general that's the tension so can I make a very very tongue-in-cheek suggestion for a price category absolutely the uh what about a roll your own crypto price

so a price for building a proving system that does not yet exist in code uh that's interesting I we had not considered that what we did have one of one that one thing that we did consider having is having like a bug Bounty of like hey all these new crypto systems that people are inventing that you know it's not they haven't been out in the wild yet you know in some in some cases already being used and so it'd be interesting to see like hey if anyone can find a vulnerability like that maybe that's like worth having but we hadn't we hadn't thought of the inverse of like roll your own crypto um yeah it's not not great for legitimacy and safety but uh it could be fun now yeah most most plausible sounding fake paper I I liked your um uh uh April Fool's Day

um thing about that yeah thank you thank you although um at least someone appreciated that I mean I think we should have a prize category for who can come up with the most clever new name for a prefix to block because we have a lot of different Planck or plonk variant names and so I think you know that that could be deserving of its own and valuable to any researcher who's writing a new paper about Blanc so um you know uh maybe the iacr would sponsor that one um cool I'm down with that that sounds like fun uh awesome do we have any more questions for Zach or any just discussion topics that people are interested in or want to comment on generally

okay cool well um I think I'll cut the video here in a second but thank you very much uh Zach for being here thank you Dara for always being a uh a strong contributor to the conversation and thank you everyone for attending and uh we'll see you guys next time oh I guess maybe a quick plug we have an upcoming we're doing uh we're presenting some upcoming work or some work that uh Ariel uh has has co-authored so we'll be doing that one I believe in two weeks uh anyway I'll publish the schedule on the telegram group but we have some other really cool sessions coming up hope to see you guys at those as well all right thank you very much Zach cheers thanks everyone take care