Episode 274 - SNARKs: A Trilogy with Ariel Gabizon

Transcript

[Music] welcome to zero knowledge I'm your host Anna Rose in this podcast we will be exploring the latest in zero knowledge research and the decentralized web as well as new paradigms that promise to change the way we interact and transact online this week I chat with Ariel gabizon Ariel walks me through his snark Trilogy concept starting with Jens grott's work in 2010 and moving through all of the different chapters of the history of snarks he highlights what he sees as the key moments and breakthroughs of the

last 10 years and while the exact boundaries of the three chapters are kind of defined as we went it was a really interesting way to think about the history of snarks I also welcome you to share the way you would break down the snark Trilogy especially if it's different from the way that we did it we wrap up on his new work around lookup tables and then chat about two emerging research streams that have folding schemes and some check protocols now before kickoff I do want to direct you to the ZK jobs board there you'll find jobs from Top teams working in ZK so if you're looking for your next job opportunity be sure to check it out and if you're a team looking to find great talent be sure to add your job to the jobs board as well I've added the link in the show notes now Tanya will share a

little bit about this week's sponsor [Music] anoma's first fractal instance namata is launching soon namata is a proof of stake L1 for interchain acid agnostic privacy namata natively interoperates with fast finality chains via IBC and with ethereum via a trustless two-way bridge for privacy namata deploys an upgraded version of the multi-asset shielded pool circuit otherwise known as masp which allows all assets fungible and non-fungible to share a common shielded set this removes the size limits of the anonymity set and provides the best privacy guarantees possible for every user in the multi-chain the masp circuit's latest update enables shielded set rewards directly in the shielded set

a novel feature that funds privacy as a public good follow namata on Twitter at namata to learn more and join their community on Discord discord.gg forward slash nomada so thanks again anoma and now here's our episode [Music] today I'm here with Ariel gabizon welcome back to the show Ariel thank you yeah so nice being here three three times being this exclusive exclusive Club of the three timers the three timers yeah actually I was just thinking before we started the last time we got to record in person was in Split Croatia and here we are just down the coastline in Montenegro it's kind of funny we only

seem to record in the Balkans in person I don't know what's up we've seen each other at conferences and stuff whenever there's a pandemic ending meet again in the Balkans there we go in another episode but yeah so it's great to actually get a chance to do this in person once again and I know we had spoken a few weeks ago at the ZK Summit just afterwards you were telling me that you were working on this like new generation of pairing-based protocols and it would be a really good time to have you back on and so that's what we're going to talk about today yeah absolutely so so I have this sort of cheesy Star Wars uh metaphor okay or analogy or I don't know the difference between metaphors and analogies okay uh of the last decade or

so of pairing-based snarks so this is the history all the way to the new work that you're doing the history of pairing-based narcs all the way to the new work that I'm I'm working on now does it have a name the new one or is this still like Untitled well it I'm going to title it but let me uh okay let me title let me we don't want to give it away okay okay I have uh just wait a few minutes yeah so so here's my yeah so here's how I've I've been describing it lately the the pairing based uh snarks Trilogy so the first chapter that began in 2010 A New Hope uh just for Snorks not for like life or humankind or anything uh was

started by uh Jens grot in 2010 uh in this paper where he was saying uh look we have these wonderful things called pairings and back then uh snarks were exclusively constructed by these relatively complicated things called pcps these very powerful complicated things that you know site you know tangent that's what led to starkware and uh and he was saying look we have these really cool things called pairings and if we use them we can get snarks with constant proof length that we like very much uh we can not use the random Oracle model something practitioners don't care

about but theoreticians like liked very much and like an anecdote that yes tells that this this paper was rejected uh three or four times from conferences but this is not Groth 16 papers this is not I'll okay this is the growth 10. this is the grot 10. okay I don't think I know this one so yens he uh he's both the the the starter and the the finisher of this first chapter so interesting so basically this chapter uh started with with grot10 the reason uh by the way this paper I think was not accepted first it uses this powerful cryptographic assumption the

Deep power knowledge of exponent that then people were like uncomfortable with but now we're just using all the time we're using even something stronger the algebraic group model which is actually a strengthening of the deep power knowledge of exponent were they were they scared of it because they didn't know if it was Secure or was it just like novel uh uh I mean right that's a matter of I think both right okay uh it was both novel and like pretty much all crypto assumptions we we don't know if it's secure until it gets broken and well here here is a very good argument against these types of assumptions and also against the algebraic group model this assumption is what's called a non-falsifiable assumption so uh

discrete log assumption uh you can you can demonstrate it's false you can like give an algorithm that computes discrete logs uh these knowledge assumptions there there's no like easy way to demonstrate even that they're false they're standard cryptographic assumptions are about show saying you know this thing is hard uh you can't do it uh knowledge assumptions are more like saying uh you can do this but the only way you can you can do it is like in this way so it's it's kind of harder to to refute them okay yeah anyway uh but also from the practitioner's side

aside grat10 had quadratic proof length which made it not too practical but then the pivotal moment in this first chapter was the ggpr work that I introduced qaps that were then sort of recasted as r1cs's uh and this was this was really the pivotal moment uh because it was saying yeah using just pairings no not this heavy machinery of the pcps uh and also no random oracles that theoreticians don't don't like we can get almost practical snarks and the ggpr approach was refined first in the Pinocchio paper uh finally leading to the paper we all know and love grout 16 so Yen scrot also

started this chapter and ended it by giving the the sort of the most optimized version of what you can do in the ggpr approach uh yeah so this was this was very nice this is still uh book one right yeah I'm mixing up the mythologies here okay the chapter one Harry Potter yeah yeah if once we get to Seven like uh like chapters like in 2040 I'll have a Harry Potter like uh yeah I I would normally so I actually my my story of all times is Buffy so it'd actually be season one but anyway we'll stick with yours

chapter one this chapter yeah okay so this is the end of at the end of chapter one is grot 16. 16. tell me like let's let's summarize that like this became like the standard every team that was going to be building with snarks would sort of tap into this would you say like most libraries started to be built around this tooling um well uh yes and no uh I I mean one reason maybe why I know was that the the the time you know from grad 16 to when chapter two began was was not too large but yes grad 16 yeah I guess it became a standard definitely yeah uh but yeah with with the caveat that you know so

right there was this very annoying thing that you had to do a trusted setup per circuit oh yeah so this is the big thing that makes protocols from this first chapter not totally convenient to use in in practice so so you have to like really right it's like you know you you wanna you're thinking of seeing a movie if it's easy you know just go see it even if it's not great but you really have to you really have to want to use Snorks you're you're only going to use broad 16 if you're really sure you want to do it it's not like I don't have you know other plans uh because the doing the trusted subper circuit is a huge uh right it's a huge logistical nightmare

which and this in a way also maybe explains like going to a project you used to be part of uh zcash when when an upgrade like the one snark The Trusted setup would happen and then that was the snark that you were going to be using until another trusted setup would happen so that you could play a new one right it was such a Monumental feat to get one of these things launched that you can only do that I don't know once a year twice a year you couldn't do it like all the time yeah yeah if if you want to encourage like a committed monogamous relationships with snarks the The Trusted setup for circuit has its maybe yeah maybe it has like it's not like ah you know I feel like you know changing

this constraint today I don't feel like this circuit fits me anymore like yeah no you're committed it really commits you you really you're really committed a few months to advance to the last like little equation you're really like yeah this till death do us part or uh and yes but definitely people were looking for you know something more convenient and you know this leads us to the second chapter the polynomial commitment scheme Strikes Back so what this chapter sort of said is well pairings are great uh but if instead of trying to do everything with the pairing we just limit our use of pairings to this one

component a polynomial commitment scheme then suddenly we have a lot more flexibility we can suddenly get a trusted setup that is universal so one trusted setup for all circuits of a certain size bound this was the largest thing and a second thing that it has become very large very you know big is that this exactly gives us the ability to do custom Gates whereas in the the first chapter we were confined to uh restricted to r1cs very inherently uh the second chapter allows us to do custom Gates can't you

do custom gates in r1cs or is it just not a smart combination well you know I can give you any gate or a gate is basically usually an equation so so you could always break that equation to a sequence of r1cs equations uh right but sort of your your unit of cost is how many r1cs equations uh are is it going to take you to represent this equation so if you were to do something like I mean a custom gate in r1cs is kind of possible but would be clunky and slow and you'd have to do many layers I guess like you're you only have the ads and the times although I think you do also have only the what is

it add multiplication and addition in the polynomial commitment ones but you have more does like when you talk about custom Gates basically I'm just wondering if it like what does it open up well it's it's really it's really it's all about the const it's all about constants here uh so the sort of the r1cs equation is always a sum times a sum equals a third sum Okay so you know for one thing if I wanna I have now something of degree three like x times y times Z equals w I definitely cannot represent that in one r1cs equation uh I see right because I only have degree two

in um in r1cs so I'm gonna have to break it down to to two equations but you moved so instead though you moved away from the r1cs model towards planckish arithmetization is this what takes over kind of from it uh yeah I hope I'm not front running the story a little oops uh no I'm so plonkish arithmetization is yeah is basically uh part a big part of this of this second uh the second chapter uh I think people use the term plonkish arithmetization for a combination of custom Gates and

and what's called lookups yeah and did the original plonk because I think chapter two does it Center around Planck in a way well I would say actually the the I mean Planck is a big part of chapter two uh and it has become you know maybe like gross 16 became the standard for chapter one plonk became the standard for chapter two but I I would say the like ggpr was the pivotal moment of chapter one I would say the Sonic paper ah was the pivotal moment of of chapter two uh I mean at least for me uh personally you know when I saw the Sonic paper it opened my eyes it it was

like okay we have suddenly a lot more uh flexibility here yeah um yeah it was an idea of the single trusted setup and then you wait for like until you're ready to do another one to make any sort of changes that was corrected a little bit by Sonics right all of a sudden you could adjust you could update this Universal circuits you could do something without having to run a full trusted setup each time yeah yeah so the snarks of this of this general of the second generation of the second chapter they have a setup that is the setup is universal and updatable so it's one trusted setup per all circuits of a certain size bound like a top bound like

top bound would you often like do you still have to do a trusted setup but do you do it as large as you could yeah you choose a large size and then after you've done that that you can make snarks for any circuit up to that size got it right as a side note there is this work that maybe is sort of between these chapters this gkmm work it was the first work with a universal and updateable snark but it didn't fall into this uh template of a polynomial commitment scheme and a polynomial IOP like the snarks of the second chapter and it this is really a tangent this is like the bonus um on the DVD right

bonus yeah you have to buy the extended edition this was like chapter 1.5 okay so this it did give you a universal setup uh it had some efficiency like problems but there it was really a setup for circuit size rather than size bound I see yeah but but that's really uh you know a side note yeah and also the second property of of these uh setups that we have now is that they're also updatable meaning that say okay you don't trust anyone that's participated so far at any point someone can just add add their Randomness sort of to the setup so the trusted setup although even in practice though weren't the trust is set up still

with the universal ones kind of gated like there was an end point you would start the trusted setup and you would end The Trusted setup before it launches right like when you talk about adding Randomness after like you could but do most of these circuits actually allow that um well I think in most production projects it's true that there's been an end point it's it's more maybe hypothetical that I mean it's not like uh that yeah the projects that are in production now um yeah they they allow you to do two friends they once in two months they like go we're adding this person yeah uh to the yeah there is one exception there's a really nice project Perpetual powers of Tau

that I think that's from the EF I think I think it's I think it's from the EF wages if I'm saying his name right he was I think the main although as I understand that that's just like an ongoing trusted setup to always kind of spit out these what is it srs's like these so that you can if you're launching a project and want the trusted setup phenomenon you can just use that right isn't it sort of like it's meant as sort of almost like a public good for snark projects so that they don't have to run their own setups that's what I've always understood that is it's like ongoing forever so you can just kind of click in but I guess it probably is limited too like it's whatever like upper bound it's set for itself and

if your snark is higher then you'd still have to run your own yeah exactly yeah I mean they said a relatively High bound like it's uh I think it's two to the 27 uh which I I don't know if there's any circuits in practice that maybe the filecoin circuit is a little larger than there wasn't the plumo one oh I worked on that one all right you know so you know as far as I know that was like a massive one right right I don't I don't know the size of that maybe it exceeds the yeah but I'm not sure if Kobe was here he could he could report yeah um but okay so but so going from Sonics what's the next step in the movie in chapter two or chapter two yeah not

chapter three yeah because like is there anything between Sonics and Planck is there anything in between wasn't like Marlin kind of between um I think Planck and Marlin came out at a very similar time okay so yeah so so Sonic was the I would say the pivotal moment of this chapter uh yeah but but Sonic was a relatively comp especially if you wanted a succinct verifier like a fast verifier uh Sonic was relatively complicated and yeah and basically um a half a year later I think or eight months later then you know there was efforts to simplify it and I think the main two papers that came out of us at

similar time were plonking Marlin got it thank you plan came out a month before our knee print maybe but similar time okay they were both presented I think at CK Summit for I think that was when that was the summer the snark Timber and the snark Timber 2019. yeah yeah yeah I think Planck Marlin Halo uh dark because Halo one already I think Halo 1 was a little later wasn't it I thought that was like just after uh it was a little I mean actually I mean I think plonk was first put on ePrint in August but oh but is you know snark Timber we like to say Well it all happened in snark Timber okay and then CK Summit was I think in September or October of that year so it

was like right after that was a good ZK Summit this is a small one but a great one like kind of Legend is that a co-working space What quality not quantity 100 people 20 people in a basement 100 people but yeah it was pretty small all right but okay so but I'm now I'm really curious like where does chapter two end because since like so you mentioned Sonic plunk Marlin come out around the same time but Planck is very much at least like a second beat in that movie like the world changed a little bit when plunk came out I think well the um I mean where the analogy is not perfect is that the the chapters overlap and most most people are are

still watching chapter two okay and I'm I'm saying to them hey there's this really cool chapter three but they're not um it's it's mostly just being just a few people okay so chapter two maybe was broken into two parts because it was too long production said we need to cut it in two let's say the part right chapter two part one ends with the creation of Planck what happens after that what happens after that um because you have the look The lookups you mentioned the lookup stuff plunkish arithmetization has the custom Gates but also this lookup table yes and you're saying like plunk one the Planck paper was the introduction was the real kind of find more just the custom Gates was

that the big innovation um I would say like this the uh Planck the biggest simplification there was uh the permutation argument and also the arithmetization and Planck based on selector polynomials which by the way was not was not new we were going to at some point get this whole right this whole subject of attribution so the the arithmetization in Planck is simpler than it is uh in Sonic it's not totally original though a lot of people attributed to Planck it's this selector-based arithmetization that it already appears in this paper of gkr paper called proof for Muggles one of

the first subject papers uh I mean practical subject papers the subject is from like 1990. yeah but the paper that so sort of what happened was Planck went back to this actually older arithmetization based on selector polynomials so custom Gates were not there explicitly it was a little hinted like uh in in slightly hinted how oh if you play around with these selectors you can get like a Boolean gate you can get um where selector polynomial where like custom Gates really like were like explicitly like uh showed was in in the turbo clunk paper ah it's sort of it's a it was like a proposed officially a

proposal to to ZK proofs so but they're but you can think of it as a turboplank paper okay okay uh yeah so that's where really the custom Gates and their generality were uh yeah were introduced and then you did the lookup stuff though the pluck up right and half a year later uh we came uh we came with ploke up yes well I want to continue with your analogy where do you want to go with this with the story well actually I mean I was going to go to chapter three but uh but but you saying that you know maybe this is chapter two so long that that it has a 2.2 so I would say wait is the second one two two points 2.0 and 2.1 no no it's 2.1 well it's okay well

it's because it's like part one so it's chapter two part one ends with plonk yes and then chapter two part two so it starts with all of the things that add to Planck so I would say uh I mean these are not I don't know why I'm sort of like using this I like this analogy I'm going with it let's spend 20 minutes talking if it we should start counting from zero or one should be two points no we're gonna do part one part two keep it like so of course there's a lot of overlapping because in a sense chapter 2.2 is I'm going to Define it now uh actually starts with Halo that was already in snark Timber but I would say chapter 2.2

is the whole subject of aggregation okay the whole thing of like the classical uh snark scenario is you have one circuit you're doing one proof for and you want to optimize that you want to make the prover fast the verifier fast the proof small but usually it looks like the real scenario is you have a lot of proofs of the same circuit ah all the same but many of them all the same but many of them so right so this can happen in a roll-up where you have a thousand ten thousand client proofs

and now you yes now you want to prove that all these client proofs are correct um maybe this sort of happens in like a recursively verified blockchain like Mina where you're at every block you're doing the same proof where the the thing you're proving is a statement like uh I proved the previous thing I approved the previous thing the uh and the previous blocks are that I checked that all the previous blocks their proof was correct I checked the proof of the current block and here's like uh a new proof here's a new proof yeah so it's the that that's actually when you say aggregation I I immediately thought like how does that relate to

recursion is recursion a form of aggregation or when you say aggregation do you mean somewhere else there's aggregation happening well I mean I by the word aggregation um I mean I don't know if it's the maybe you could you could also look at a more general term like amortization uh but when I say aggregation I just think okay of this scenario that that what we don't have one proof for one circuit we have ten thousand proofs of one circuit what's the best way to do that given that that that's our task yeah and it could be through recursion one after

another or batching and then recursive proof or these like newer ways of aggregating right right and also part of the part of the scenario here is we have usually as we have asymmetric um resources right we have for example in a roll-up we have um weak client machines and and one stronger machine that doesn't mind making more computation doing more computation right so so then you know this scenario is a little different and you know the the considerations are are a little different yeah and I would say recursion is the the most straightforward uh thing you can do in in this scenario so yeah so recursion is saying okay do

your uh your proof and also like prove inside your proof that like uh the the previous proofs were or were totally correct but then uh especially in this context where you have maybe one stronger machine and many weaker machines people started thinking and I mean this this happened before in simple scenarios but the maybe the paper that brought this most to like the to highlight this was was the Halo paper is like uh saying well I mean our end goal is to verify say these 10 000 proofs but maybe it's an Overkill of doing ten thousand steps where in Step I

I fully verify the I minus one proof or the one to I minus one proofs maybe we can yeah we can delay you know like if we look at the total work needed to verify these tenth out because like straightforward like straight uh vanilla recursion to verify 10 000 proofs and and put that in one proof you're doing a full verification inside a circuit ten thousand times okay so yeah so uh what I think Halo highlighted was saying okay if our end goal is to verify these 10 000 proofs maybe there's a way to do that where the total work is smaller did

they just like hash them together like could you just somehow combine them and not have to do each one well so yeah so exactly so so that's kind of what people are trying to do maybe hashing's the wrong word here but like they come they combine them basically right right um and here yeah so that's that's the basic idea can we just sort of combine somehow the proofs And Delay the actual proving to an end stage where also hopefully a more powerful machine is is doing whatever is needed in these end stage in this end stage and here I mean the term that I

think and I don't know if it was in the original Halo paper but I know like at least what's been emerging is it's this is the folding right so or folding just another form of accumulation so I myself I'm I'm not a hundred percent sure on the distinctions between the different terms when when people Define them formally but the terms that have been used for for this kind of um I guess I need to choose a word to use this kind of aggregation or amortization people have used terms like accumulation split accumulation aggregation and folding I'm not sure myself of the subtle subtleties of of

how people Define these formally I I think of them as similar I think I will be doing an episode really soon probably just on that because I'm curious too so yeah just a teaser for a future one we'll figure it out yeah well here I mean yeah this this is uh I mean this is a a rabbit hole or rabbit hole is going to be not the word but this is a a long topic including Nova so I don't know if yeah I would get into it now no I want to talk about that later if we go to chapter three yeah so I want to talk about that later because I I mean one of the things I tweeted this like I was watching Justin kind of like Nova pill you and then I heard you got subject pilled and we got but I think we

should talk about that after because I want to continue on this story that leads us to basically this new generation that you've been working on right so uh uh chapter three the return of the pairing wait had the pairing disappeared in chapter two well it hasn't it wasn't totally disappeared but it was exiled to uh to the land of only doing uh where you only do polynomial commitments and you're not allowed to be involved in anything else okay okay because people are afraid that if they let the pairing get involved in something else they'll lose the universal setup there so it was exiled to polynomial commitment uh got it land maybe okay so this is the return

of the parenting pairing wow uh so chapter three that as I see it started with a work that was very like uh it was significant for for me to to see it um it really shifted like what I've been doing in the last Almost year uh this were called caulk yes and I I'll say a few words about that but in general I would say this chapter is about finding a middle ground in in terms of okay we don't have to do everything with a pairing because then for example we're we might lose the universality of the setup which which we really that would be a total deal breaker but I mean maybe let's find a middle ground maybe there's

things besides the polynomial commitment scheme where the pairing gives us gives us leverage that we don't get from a generic polynomial commitment scheme and caulk was uh the first paper that yeah that really highlighted this so we did actually we did an episode with Mary and I know I'm going to try to I'll dig that up and add it in the show notes because I know that that was recorded after the cloak paper I'm pretty sure we talked about it in there too but yeah what was it in so like and I always think of Culkin the lookup table lookup argument context is that correct yes that's totally correct so uh yeah so here uh

yeah we should talk a few minutes about lookups so so lookups uh yeah as part of chapter two uh were have been very significant to Snorks right look up say well instead of explicitly in the circuit Computing or checking uh with a lot of equations some some relation between the two witnesses let's just pre-compute a table of legal input output values say of some function and then just devise a protocol that can check let's say two witness values a b appear appear as a pair is a tuple in in this table Yeah so this has been a hugely impactful uh I guess what this did and actually we

also we have a whiteboard sessions with Mary as well that I'm going to also put in the show notes where we talk about this but it just it may it seems to have made like if you already have a lookup table you know you're looking for these tuples you don't have to compute them right is it instead of doing computation you're saving time you're saving a lot of prover time okay yes yes yeah and I would recommend Mary gave a really good talk uh at this barilon uh winter school about uh lookups yeah to that really good talk yeah so look lookups are great uh but the lookup protocols we had uh they had you you paid a price the the price was uh essentially that you had to put the

table in the circuit meaning if the the table had size uh t your circuit would grow by by T uh so I found that so like I still can't get my head around how you put a lookup table into it like but I've seen you write out these like formulas that have L as the lookup tables for shoved into them but yeah I don't actually know what that's doing well yeah I mean to give a little more detail you you do pre-compute the lookup table and and you could say maybe what you put in the circuit is some randomized combination of the lookup table and the

witness uh with Randomness that was chosen by the verifier okay so that sort of helps the verifier make sure that the proofer is not cheating this this sort of just proves that you're like using the correct lookup table in a way right like that that you're yeah this proves that the witness values that you claim are in the table are really in the table you might not have all of them in is that what you're saying like you sort of pick a few of them the main way the prover would cheat is he would say this pair of witness values a B is in the table whereas it's not yeah that that that would be the main way like say it's a table for range proofs uh where a you know you're checking that a is in some range zero to

two to the 16 and a is actually 2 to the 100. yeah okay so yeah so you want the prover not to be able to cheat by writing something that's not in the table but when you talk about how it gets what pre-compiled and then put in are you putting in all of the values of the lookup table yes yes okay exactly yeah in the current so in the SEC in the first generation lookup protocols which there's a con it's part of it's part of the second shot yeah so this is chapter two part two uh look up is part one so okay so this first generation of the look of protocols we've just moved us into because I think it wasn't but we're gonna move click up then into chapter

two in chapter two part one but all of this sort of like new work into the lookup tables would go into the second part of chapter two and caulk would definitely be in part two of the chapter two call call because no caulk is the start of chapter three oh wow okay okay okay so that pivotal so so right so so as I was as I was saying that right that the

thing is you can only if you use a table of a certain size then your circuit is going to grow by that size um in these these algorithms like pluck up uh so if you want a circuit of size 2 to the 14 and you want to keep your circuit of that size you're only going to use tables of like size a little less than that ah and if you can only use smaller lookup tips I guess you can't put that much in so you're not saving as much like the you want to put more tables you can use the more approver computation you're using got it interesting trade off there yeah so but this led to the very interesting question can I design a lookup protocol where the prover computation does not

depend on the table size okay and and this this is what caulk did wow and almost I mean they had a little dependence on table size that this paper called plus uh removed completely but basically this is this is what caulk did it totally uh almost totally removed the dependence of proverb computation on table size which opens up uh the the possibility of using much larger tables which then would save more proofer time save a lot more prover time okay yeah exactly yeah yeah and is this where your work starts then is this where you're kind of

branching off exactly so so I saw uh the the caulk paper come out like 10 months ago maybe and uh yeah that totally caught my attention and so caulk uh it it so it made this this big conceptual leap but it was not totally practical it was a little of a heavy uh protocol in terms of the exact like costs and this led to this uh kind of fast sequence of papers improving colics so uh I'll just say the names it's not too important it was called plus lookup blue oh yeah

and uh and the last one currently in the series is a paper called CQ I wrote with Liam Eagan and Dario Fiore and I'm I'm very excited about the CQ protocol because I think I think this is a truly practical protocol that allows you to use large tables let's go into it so this is we're in chapter three this is today yes we're in chapter three okay so CQ CQ like the letters the letters CQ okay so just to position it though is CQ a proving system CQ is uh just a lookup protocol but it can be easily integrated into a proving system like Planck right

so it follows the work of Coke I'm just trying to think like like what is it that you're actually doing then in CQ that allows for this like larger table inclusion the lookup tables well I mean the inherent reason why suddenly you can use much larger tables you could say it already starts in in caulk so the inherent reason why white pairings are involved here oh is that right we have different um polynomial commitments uh we have we have fry and we have I mean right the three big ones fry case bulletproof say and kzg so fry is the you could say the least

homomorphic like if I have fry commitment to F fry commitment to polynomial G and I want to get the commitment to f plus G there's no convenient way to do it because they're not similar is that why when you say homomorphic do you mean like so homomorphic I mean that as opposed to fry uh if I look at bulletproof through kzg so if I have a commitment to f commitment to G now I want to get the commitment to f plus G it's easier I just some I just sum them I just take is that the definition so it's funny I've talked about fully homomorphic encryption I've never actually defined homomorphic is it is it that you can like is it the morphism is similar like

to change it is similar is that what it's kind of I'm trying to actually get to the definition here but so yeah uh homomorphic okay so also there's this sort of in terminology that that is like a little fuzzy so I I guess you could for what I just said that from the commitment f plus G some people would call that additively homomorphic okay yeah but but they they'll just say homomorphic for short and and I think what happens is from the context like you you can infer do they mean just additively homomorphic or they mean more like the yeah sort of the word I guess homomorphic it means that you can do operations in two different orders and it doesn't change

the result okay so right one way to do you can first sum the polynomials f and g you have that operation of sine the polynomials and then take the commitment and you're going to get the commitment of f plus G okay and we say like the bulletproofs and caseyg are additively homomorphic or you know people for short will just say homomorphic because uh it means that if we do these operations in a in the different order we'll get the same result but if we first take the commitment of f take so we first take the commitment and now we sum it would be the same so we get the same result yeah so that's why we say that bulletproofs in case each year additively homorphic because the commitment operation it you could say

people will use the word commutes you can with the addition like you can do it before the Edition or after the Edition and you'll get the same result does does the caulk papers and all of the subsequent work rely on that that it has additive hormones so yeah so the additive the this property of uh additive homomorphicity homomorphism I said homomorphism I don't know right the property of having of being like additively homomorphic or yeah okay uh yeah the commitment is called yeah would be called in home a homomorphism yeah but it does need that like so definitely so okay the additive the additivity sometimes

people just call this the additivity of the commitment right yeah uh when they don't feel like I mean that's like a base requirement but uh but it's used in in Nova it's used uh um yeah the additive homomorphism homomorphicity uh the additivity is like crucial all over the place but but the point is to get caulk we're going to use we're going to use something so the additive property being additively homomorphic that also bulletproofs has okay uh what kzg has is it has this because of the pairing it has sort of this

partial multiplicative homomorphism ah what that let's without fancy terms because maybe I'm not getting the fancy terms right either uh it allows you to what you just said about adding you can do with multiplying so partially partially okay so what it allows you to be concrete what it allows you to do say now I give you commitments to four polynomials F1 F2 G1 G2 kzg commitments and now I ask you is the product of the F's equal to the products of the G's is like F1 times F2 equal to G1 times G2 so with kzg you can do that check directly

from the commitments but why is it partially then is it because it has to be f with f and g with G but not f with G it's partially because I can check if F1 times F2 is equal to G1 times G2 but I cannot actually compute the commitment to F1 times F2 so I have a way to check if they're equal but I can't actually compute the the commitment to F1 times F2 okay so but even with that how does that relate to the lookup tables like why how does that really why is that good um so okay so here we come we come to

call so why so this so why why is that good so this turns out to be extremely powerful okay and to give a little detail on it a big component of of trying to work with big lookup tables if you look at protocols like caulk and CQ is that or a big part of snarks is you're a lot of times in situations where you want to prove that one polynomial divides another polynomial okay that's all over the place now the standard way you do this is you compute the quotient What's called the quotient polynomial meaning simply the

second polynomial divided by the first so we just compute it compute this polynomial then you compute its commitment and then you open all these three at a random point and check that the first times the quotient equals the second the thing is in in caulk when we're trying to use a big table this created a situation where this quotient had huge degree so to actually compute it would be sort of like having to put the big table in the circuit in terms of the prover cost but it turned out in COG that sometimes we have quotients where Computing the polynomial is expensive but actually Computing its commitment can be if you've done if you did the

right pre-processing Computing its commitment can be much cheaper than Computing the polynomial itself okay so now we're in the situation where we can cheaply compute just the commitment of this quotient and then the question is okay does this help us and yeah it does because exactly because of what we said that we can compare products directly from the commitments in cases but you don't have to compute them you don't actually have to compute you don't have to prove that they're the same yeah or something yeah yeah I don't know if you're doing this thing like you had talked about the F1 times F2 times G1 times G2 that would just be the same You just prove that they're

same but not know what they are yeah I prove that they're the same without the thing here here to to be totally precise the thing I don't know I sort of I don't know what F2 is okay I I note I don't have F2 in my hand I only have the commitment of F2 in my hand because it's much cheaper to just compute the commitment of F2 then F to itself okay and uh do you have to make then assumptions of correctness like does this like in that probabilistic like is it correct or not are you just sort of does it lower the probability that the lookup table is being used correctly uh in any way it doesn't lower it but what is here in you know used very heavily

and this is is and this is true uh you know for all the snarks based on kzg to actually conclude that the checks we're doing imply that these products of polynomials are equal we're heavily using this this strong cryptographic assumption the algebraic group model uh so we heavily rely on that but no but it doesn't like give given that we rely on that anyway anytime we're using kzg it doesn't reduce the probability that uh compared to say to pluckup that the the load up is correct I have sort of a side question here I wanted to ask for a while which is when you listed the three polynomial commitment schemes I think fry bulletproof caseyg does fry ever use lookup tables or is it just you'd never

you can't yeah so uh so definitely so so polygon Hermes for example and others probably two yeah they use fry with with lookup tables the reason they can do this is look up arguments like pluck up they can work with a generic polynomial commitment okay because they don't rely on this additional additive hormomorphism yes they don't rely on it pluckup doesn't lookup just needs a polynomial commitment got it so they're doing some part of this lookup table work they can use part of it but at some point like call they wouldn't be able to go that far with Fry at this point exactly so okay yeah so so the the the additive actually places where the additive homorphism is

used you can even even places where it is used you can um you can sometimes get around it with losing a little efficiency uh but yeah um yeah is is yeah so so this this was also an interesting uh fork in the road in a caulk in the sense that like we we had these few years in chapter two where you know you could pick and replace your polynomial commitment scheme as you wanted and here was the first protocol where kzg only allowed uh okay and bulletproof's also not allowed also not allowed because only yeah only when you have kcg is based on pairing and it's only the only one that has this

multiplicative property interesting of course an interesting you know research question has come up with with new PCS that have this multiplicative ability so we sort of mentioned the accumulations and this like aggregation does the lookup table impact that because it feels like a different part it is it's totally yeah exactly it's it's I at least I view it as as pretty is pretty orthogonal like modular almost like you're pretty modular like like you you have you'll have your lookup component and you'll have your aggregation accumulation folding component usually they're pretty like independent of each other do you think then so in this story are we like

chapter three so far the chapter three that has been described is the lookup table component but in chapter three do you think there are other like is there an accumulation side that's still being told like that story of which accumulation scheme or folding scheme or whatever uh wins is that unfolding because we're in chapter three right oh or is chapter I mean we're in uh both chapter 2.2 because people are you know with the excitement around Nova people are working very hard on improving aggregation and they're only using the additive homomorphism so it's fine well um so we're both in chapter 2.2 in chapter three okay that's exciting

though but that's what I'm wondering then like is there a fold over on the folding side into chapter three eventually well that I mean that's something honestly I I haven't looked into can is there a kzg specific like folding that that is more efficient than you can only get I haven't actually researched that that's a good question and does nova or the some check based stuff do they work with kzg already are they just using that or yeah so they could use it they could so so yeah the Nova style stuff it only it needs an additive it crucially needs an additive homomorphism okay not the multiplicative property cool yeah well I love this story that you just

shared and I do actually welcome people to parse a little bit because like I think there's a very clear narrative despite a few of our like side bonus episode Explorations or yeah special features Explorations I'm so dating Myself by referring to DVD bonus and stuff but I hope people haven't yeah haven't got too lost with all the overlapping uh 2.2 and three and uh I don't know I think it's cool but I now I mean so this you know we are now like chapter three is on like maybe we can go back into the CQ work and is the CQ work finished and is and where is it going and what's it for right now

uh the CQ work is basically finished of course it's always like uh nice to keep trying to optimize save a little proof size or verify work here and there but I think it's very practical the form it's in so my attention a lot of my attention has shifted to trying to get it used and I think where it might have a lot of impact is better Snorks for nasty functions so we'll talk a lot about front snark friendly functions I I like the the nasty functions uh not not because I don't like friendly things but I I think that's where maybe CQ will will sort of shine most

um what's an example of this so a ketchup is a really good example right so ketchuk is definitely not a snark friendly function it does a lot of crazy bid operations and it's uh you know it's heavily it's heavily used right the ethereum mainnet it stores data in trees based on ketchups okay right here we get we get into the types right there's now people are calling um there's type one ZK VM and type 3 ZK I don't know what type 2 ZK VM is but there's a 2.52 but it's a 2.52 now there's a 2.5 as well [Laughter] no yeah there's definitely some some ad

additions on that one okay but you're saying so it's in in that context so like in the roll-up context it might actually be interesting uh well the ZK evm uh context for example when when you want to do what's called a type 1 zku VM so you want to like fully simulate uh fully validate what's going on in mainnet because the the state in ethereum is stored in in trees with capture caches you you have to do end up doing a lot of Catcher caches in in your circuit uh also what what Axiom is trying to to do now that allow you to sort of access historic ethereum data in your smart contracts um that ends up like proving this

historical data is correct like a lot of their cost is is ketchups and these are all nasty functions well the ketchup yeah catrick is the nasty function why would cqs be useful for a nasty function then is it is it because you use lookup tail table is more efficient it's not yeah it's not it's just um because usually when you have nasty functions in the sense of a lot of bitwise operations rather than like field operations uh that's where lookups make the biggest difference and the bigger the bigger table you have the more efficiency you gain you can get and and CQ simply allows you to use use bigger tables cool

has this been implemented is that sort of like your current like when you're you're saying like you're looking to find uses is it like T you're kind of like hey teams do you want to try using this and implementing it or are you going to implement it so uh I mean hopefully I'll write a few lines of code at least okay but uh yeah I am trying to collaborate with uh better coders than uh than me so what was really nice is an Andrea uh from the geometry team yeah he implemented CQ pretty much the night the paper came out wow that must be so exciting to see yeah yeah uh so he implemented over its over our quirks and

uh I mean I'm interested I think also he and other people uh from geometry and maybe other teams are are trying to get CQ into Halo 2 I mean right here is a side note right there's this whole interesting subject of what like sort of snark Library like plonkish Library will end up sort of dominating uh like a polygon Hermes and jordy's uh pil language looks looks really nice uh but so I'm wondering how things will converge but right now it seems like the mass of developers is around uh Halo 2.

yeah yeah actually yeah the way that sort of Mind share circles around some of these ideas so fascinating it's like I think it has there's certain groups that will Champion certain proving systems and then you'll get tooling being developed really quickly and it's sort of fascinating to see like which ones are picked up and which ones are picked up less yeah and I mean looking back to that snark Timber at that time you were also seeing that because there's all these proven systems coming out all at once and I think we can now look back and say like plunk kind of like dominated that but it's hard to when you look now like here in Montenegro and we're like Justin and all

these folks are here Nova's the The Talk of the Town yeah which is sort of a continuation on Halo but not Halos exactly right uh yeah I mean I would say it's it's in this General theme of aggregation accumulation but but I wouldn't say it's directly connected to to Halo but yeah but right now Halo 2. but I like to say a word now that I I mean just before we we get into that the yeah there was what was interesting I remember being at ZK Summit seven and there was this maybe convergence and Planck as a proving system but I I really remember then feeling like there were 15 different Planck implementations and there were zero convergence on that and there were potentially a lot of like

duplicate efforts yeah and yeah and you know a Year's past maybe more or less and it seems like on the library side there is maybe some convergence on the Halo 2 though I'm yeah I'm interested to see how what will happen with that yeah I want to talk before we sign off on some other works just floating around so we've mentioned Nova and I know you had some when I first brought it up or when Justin first brought it up to you you were like oh this already exists I know this from before so I wanted to talk a little bit about sort of your thoughts on Nova and then some of the competing models or I don't know if they're completely competing but these other

sort of streams of research happening so let's start on the Nova side has your mind been changed are you Nova pilled um I'm seminova build I'm uh I'm not sure what I am because I was Nova pilled a few days ago very successfully but then uh Zach from Aztec some check killed me and now I don't know if I'm just back to normal or uh uh one pill makes you hire one pill brings you down so I don't know if like yeah exactly yeah okay so but so so this is something interesting like Nova the paper came out almost a year ago I think

um and for me at least it's really just popping up more recently in what people are talking about in our channels and stuff like that but you mentioned when Justin was at least trying to Nova fill you that there was another paper an earlier paper that you thought this was like kind of directly taken from talk a bit about that maybe right so let me um yeah say a few words about what what I think are the basic ideas here right so we say we want to aggregate or fold claims instead of hat and then only like do one proof at the end yeah let me get just a little technical so to be concrete say like say the claim we want to prove is a times B is equal

to C right so the simple sort of the simple aggregation that is in the sense already happening in a lot of code bases uh is say and now say I have a lot of these claims so I want to prove A1 B1 equals C1 A2 B2 equals C2 and so forth the simple aggregation is say actually the all the B's are the same so it's a1b equals C1 A2 b equals C2 and so forth and actually this is sort of a situation that that sometimes is comes up in that case there's something very simple I can do

I can take what's called a random linear combination of all the A's I can take a random linear combination of all the C's and then I can just check is the random linear combination of the A's times the b equal to the same random linear combination of the C's so this is a common idea it happens in the Halo 2 aggregation and the code already and um yeah okay but now the question is all right what if the B's are different it's like A1 B1 equals C1 A2 B2 equals C2 and the B's are different so the naive thing you could try is all right let's try the same thing let's

check is the random linear combination of the a times the random linear combination of the b equal to the random linear combination of the C and this doesn't totally work because when this random linear combination the a times the random linear combination of the B is except the terms we want like A1 times B1 and A2 times B2 it's going to have a lot of these cross terms it's going to have A1 times B2 oh okay so sort of the idea that was there was floating around in in papers for for a a decade um though yeah I'll say that I've been a champion of this one one paper a boodle

truly High describe Petit zero knowledge arguments in discrete log setting that this is the paper where this idea started but then I saw that they actually they say oh it's similar to some some bare grot paper oh even earlier that comes up again permutation comes from so so actually the attribution I've been a you know arguing with people about attribution but I see actually the attribution is a little complicated um maybe yeah but any but the basic idea also in no event here is yeah we're going to have a lot of these cross terms but the thing is the the cross term is going to be like something fixed times this Randomness we chose for the random linear combination

and in fact if we just let the prover the fixed thing just commit to it in advance and we choose the randomness later even even though we're letting him commit to something totally arbitrary this is what's called the error term uh or sometimes it's called the slack term in these papers I think it's called the error term in the Nova paper even though we let the prover like if you have an equation that the verifier is trying to check and now we're letting the prover add a totally arbitrary error term to balance out this equation so so this seems like definitely the prover can cheat but it turns out that since we're having him commit to this error term and only later multiplying it by the randomness we chose for the for these combinations

the prover can't cheat is it because you because you're multiplying it by Randomness it means the prover can never engineer it to be corrupted like because there's less like extra step they like it wouldn't be able to figure it out beforehand yeah because the randomness multiplies the error term and the error term was chosen without knowing the randomness the prover can engineer a fake proof oh that's a cool technique but is that new to Nova or has that always been there in all of this work so this was used uh in this boodle it all paper which attributes something similar to the bear grotch paper and the bulletproofs gave a

paper gave a much more simple form of this than the boodle at all paper and yeah but but the foremanova is is a little different so yeah okay okay yeah as mentioned I want to do a full episode on Nova but just quickly kind of like what is the the trick to Nova what's it adding on those Works maybe or what's it doing different uh Nova is adapting this technique to r1cs ah and the other oh because the other ones were bulletproof more like or nothing I guess the previous work had not had a specific setting or like yeah so Nova is adapting this uh this to our our own to r1cs but then is

interesting is Halo r1cs because remember we talked in chapter two that like we were kind of leaving a bit of the r1cs model behind weren't we to get the plonkish arithmetization well right so so that's why since people are using plonkish arithmetization that's why a sort of after Nova uh people have adapted this technique I see to to plunk a sharpenatization this is what's happening in in sangria or supernova I think tries to as well maybe I'm not totally sure okay we'll leave that one but yeah interesting yeah Noah for sure and sangria it is yeah yeah relaxed plunk that's what the word that's where the name comes from

um we had Nico on just recently yeah okay so that's interesting so it's the implementation of this concept for r1cs and now because it's been done I guess there's this like oh can we also implement the same kinds of techniques yeah so Nova has really brought into the you know General awareness this this idea that you can you can aggregate sort of arbitrary non-linear equations like right in in for example this A1 times B1 we're also A and B are they're different every time you can start to do it because of this error Edition just because it's just showing that the

proofer can act maliciously yes interesting yes wow what about okay what about the some check pill all right so so this is a really cool uh technique but right we have to I think it's still to be figured out how much it exactly gives you versus other techniques so so there's a little this this feeling that oh we don't have to prove anything we just fold we do we just fold and we just prove in the end but uh I mean when you really get in down to the details you have to okay what is the cost of this folding and compared to the cost of the proving right that's that's what you're saving

so yeah so indeed and that's what I've been thinking a lot these last few days because everybody here is talking about uh Nova so really a few days ago where I was I was Nova pilled I had so there's this this error term you have to compute and I had this idea in my head that there's some fft involved in Computing this error term and then we were yeah we were talking with just edit Justin was like no there's no 15 volts and I was like of course how else are you gonna and then I I realized it was more efficient than I thought okay and uh yeah and and I was Nova pilled to to a um to a degree um yeah but like when I I sort of did a rough computation with myself I I sort

of came to the feeling that for say standard Planck like it would give you the cost of folding would be like 20 of the cost of the full proving I see says the folding starts to it's like on the proving part is that actually on the proving part does it basically does the folding add to the computation somehow right so what exactly so say we we have like uh we want to prove a thousand long proofs and we want to just fold them and just do one proof in the end and we want to use uh sangria or so what do you have to do for each instance so you need to the main thing is at least when your circuit is big and then other costs become negligible

your main cost is exactly Computing well first of all you have you do have to commit to what's called your witness polynomials that you do in a regular plonk proof and you also do when you're just folding a plonk statement in both cases you need to commit to the witness polynomials uh and then what is the additional thing you need to do when you're folding you need to compute and commit to the error terms and that also requires something that's taking some time or that yeah that requires that requires some some work okay so you're doing that work and what is what are you what are you saving so the main thing that you're saving at least the main thing that

you're saving that you can't save with with simpler aggregation techniques is Computing and committing to the quotient polynomial so because you don't need to compute the quotient polynomial and indeed uh like I found out a few days ago you have no ffts so you saved all the ffts which can be sometimes like 50 of the roughly sifting prison so you've saved fifty percent cool and also you've saved this part of comp of committing to the quotient polynomial and sort of my estimate was with you're gonna you're gonna go down to 20 25 of the work you did for foolproofing so that's a good

it's going to be a 4x5x factor it's pretty nice uh what happened uh yesterday when I was uh some check pilled six in the long run on here but okay uh was that I understood from Zach that actually maybe if you simply right because there there's another big way to avoid ffts and that that this was really very much highlighted in the hyperplunk paper instead is to use the subject protocol the subject protocol avoids all ffts like like the folding does um so it saves you that 50 it saves you that that 50 and then you don't have to do the folding and then the and and you

do not have to commit to commit to these error terms okay is it error terms the most heavy more so than the folding or is it can the same thing so when the circuit is large there's other factors having to do with a folding when the circuit is large enough so the the Computing the error term is I think the most significant cost and there's here this other topic of the degree of your constraint the degree of your Gates so for example you know Nova worked for rncs the the degree of the constraint is only two but people sometimes like using High degree Gates degree Gates of say degree 5 degree six

degree that's one thing that's highlighted in the hyperplunk paper that it's it's very compatible with high degree Gates and the thing is when you generalize uh Nova say to sangria or to to high degree Gates um if you use degree d a constraints of degree D you're going to have to commit to D minus one error terms and that's sort of like the same time to than in a regular plan proof takes you to commit to the quotient polynomial so it's like you've saved the fft work yeah that 50 percent but you haven't maybe especially if you're gonna you will want to use hydrogates you haven't saved the commitment time because committing to these error terms is as expensive as

coming into quotient and here we come to the an important point is in the subject approach you both save the ffts and there's not really something like that to commit is there any way to do both at the same time are they too different so that's something that should be explored and I think people are exploring it I think it's called hypernova where they're trying to um and yeah we still need to see where where these things were land and this also relates to the question will people want to use high degree Gates is it useful or not or is it not that big a deal used to only the gates of degree two or three interesting so there is there is a world after talking

about this yesterday uh with Zach I think there there is a world where some check will sort of make Nova sangria type aggregation less less of a big thing but or maybe they're used in combo this is this is the writing of chapter three I guess well this is this I would say is chapter this whole aggregation stuff I I would put it in chapter 2.2 because it it doesn't rely on on this mole kcg only multiplicative thing yeah yet yet all right Arielle thank you so much for coming on the show and sharing with us this journey through

the chapters to today and also your thoughts on some of this new stuff it's definitely you know very exciting and I I want to as mentioned do a Nova Deep dive maybe do a some check Deep dive again I mean we so I know uh as far as I understand Justin thaler's like championing this as well I don't know if we covered it that much in the episode I did with him this year but it might be fun to explore it again yeah I guess some check you've every time you think it's gone out of fashion it's already it's from the 90s but he's coming back it rears its head yeah nice thanks Arielle thanks Anna thanks for coming on again

so I want to say thank you to the podcast team Tanya Henrik and Rachel and to our listeners thanks for listening foreign