Episode 232 - Cutting Edge ZK Research with Mary Maller

Transcript

[Music] welcome to xero 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 in this week's episode my guest co-host kobe gerkin and i chat with mary mahler a zk researcher at the ethereum foundation we talk about her journey into cryptography her work on trusted setups universal snarks look up tables and the

work she and kobe did on aggregateable dkgs what it's like working at the ef and more but before we kick off i want to invite you to check out the zero knowledge link tree people are often asking about ways to get deeper into zk research or just meet more folks in the zk community through these channels you can find a lot of ways to jump in for example there's a zk telegram group a zk hack learning hub over on discord a zk jobs board where we have listings from some of the best teams who are hiring and more so i've added the link to that in the show notes now if you've already started building something in zk and could potentially benefit from some early funding i also want to highlight for you the upcoming zktec git coin side round so it's running from june 6

through 23rd and it's a clr matching round happening on git coin here you can post a grant and collect donations from the community this is then matched based on your quadratic voting score in a nutshell you get more matching funds if you have lots of small donations rather than a couple big ones the initiative is led by the zk validator and xerox park as well as our awesome matching partners who are coming from the zk community we will have at least 100k in matching for this round we're still putting it together but by the time this errors it should be a little bit more finalized but be sure to get your grant in and choose the tag zk tech to be eligible as mentioned it starts on june 6th but you should

actually try to get your grant in a couple days before if you're just curious to see what kind of projects are out there do head over to bitcoin dot co grants once the clr matching round starts and look for the zktec side round there you could contribute to these projects as well now i'll invite tanya to share a little bit about this week's sponsor today's episode is sponsored by penumbra penumbra is a cross-chain shielded pool and decentralized exchange allowing users to shield assets from any ibc connected chain and privately transact stake swap and market make without revealing their personal information or trading strategies to the world penumbra labs is also building in public visit penumbra.zone to learn more use a test nets and join their discord

find out more at penumbra.zone so thanks again penumbra now here is anna and kobe's interview with mary mallor from the ethereum foundation [Music] for today's episode kobe gerkin and i will be chatting with mary mallor from the ef welcome mary hi mary i've been wanting to have you on for a really long time i think you know that i first saw you give a talk at zcon1 back in 2019 in croatia and i think i approached you after that talk being like come on my podcast but i'm so i'm so glad that many years later many years later you are here i'm so happy to have you here um and i'm very excited to dig into your story but

before we actually do that i do want to reintroduce kobe to the audience this is the first time kobe's going to be co-hosting i felt that since this was a very zk heavy very kind of potentially dense episode that i should bring on someone who can help me dig in properly kobe you were on once before right uh i've been or i think two or three times or three times pluma trusted setups yeah okay we did one full episode a few years ago and then you've been on some of the combo episodes it's true the last one we did was the zk hack episode end of last year i think it's worth it to introduce you to the audience if they don't know who

you are we actually work together on the zk validator and on zika hack but you wear many hats so maybe you can just let people know what you're working on yeah very very happy too so i think that some people know that the main thing that i'm working on these days is called geometry it's a new research unit that also funds companies so i'm heading the research there so that's something that i'm pretty excited to be doing and yeah i'm also doing cryptography at cello and of course our work in zika validator where we try to get validators running in many different

networks yeah and um zika hack which exposes advanced cryptography to implementers and in a way that they can see the bad sides of when things break which i think is a great way to learn so yeah totally if anyone isn't aware of zk hack zikax also just like it's an it's like a space to learn and jump in it's it's kind of made for the very advanced users and then the very beginner at the same time with these event series that we do we have a discord so we'll definitely add links to that in the show notes if you want to check it out let's now start in on the interview with mary i want to start where kind of before z con 1 maybe like going a little

bit further back what were you doing before that point and kind of what got you excited about this space at all i started in this space really during my phd so i don't know how many people know this because i did my phd with sarah mekeljohn and jens grutt obviously jens is a very big name in the zero knowledge space so when it became a matter of you know i get the opportunity to work with yen skirt on zero knowledge i was very excited about this i dubbed straight in i would say that i was to some degree self-taught in the sense that jens was there like i have this project on trying to make um snarks something which is non-malleable so you can't do

man-in-the-middle attacks and things like that so that was how i learnt just like taking the grad 16 paper and being there like can we make the simulation extractable what does it mean to be simulation extractable um and that was actually quite successful so it's now called gm 17 typically it's not like the most used thing out there because the grout 16 is still faster but if you do have an application where you really care about strong simulation extractability then it would be a good thing to do after that i did an internship at microsoft research and this was with michael colvice and he sort of introduced a problem to me being what we call now updatability can we

generate a snack where the trusted setup is something which is much nicer looking than the setups which we've seen at that time at that time we had the zcash set up i was well aware of the fact that this was possibly not the best way to do a setup it was um it was not play replaceable i think it's a big thing it's like all of the parties had to stay online throughout the whole process of generating the parameters and this meant that you could only scale to well they thought six parties so the question then became can we do better can we make it so that players can come and players can leave and once they leave we can use whatever they've produced

so i worked on that throughout the internship and i sort of came back and was there like yes we have this problem and he of course solved it immediately in the sense that we had a snark which could be um updatable in the sense parties can come and parties can leave and i was very excited about this and i came to zcon1 being there like by the way i have this really cool thing that i think everyone should use um at this time i think we hadn't even necessarily realized that the most powerful thing about snark was that it was universal i learned that by talking to people and universal basically means that you can use the same setup for multiple different snacks

um for those that aren't aware but like the problem you were trying to solve was the trusted setup problem right it was very much it wasn't the universal part that just sort of was it almost like you had to make it universal in order to solve the trusted setup problem but you hadn't named that part of it is that what you mean pretty much i mean i think nowadays people do these sort of two-phase setups where they have like the first round where they generate the first set of parameters and the second round where they generate the second set of parameters and we were very very set on making it just one round yeah so that you would just have the initial powers of tau phase essentially and the reason for this is that we

thought it would be really nice if you could have a kind of setting where the parameters which you're using are continuously improving you're getting more and more users it's um perpetual and eventually if you don't like the parameters you're using you can update again like this was what we had in mind and this is something where in order to get it such that it can support that you actually almost do end up with something that's universal it doesn't seem i can't see a way of having one without the other in that setting there might be something but it certainly didn't come naturally the nice idea we had of the parameters continuously updating i think is not something that people have gone for in

practice i think in practice people have been more keen to have a you do your setup you finish your setup those are the parameters you work with but the universal thing people really do care about because it means that if you do have a bug in your system you can fix it or if you want to move to a different circuit which is maybe more efficient you can do that or maybe if you're just like a smaller player and you don't know how to run a trusted setup that's not something you have to do you can use someone else's so this works that you're referring to with growth and coal vice what was the universal snark that had a series of quadratic size right that's the one that's the one which i was there like it solves the problem and the

quadratic nature of the setup made it actually quite a real problem so we sort of i went away and thought a lot more about the problem after sort of talking to people as econ right but yes if you were okay with a quadratic setup and um terabytes were for parameters then this could be an option for you right right so it was pretty groundbreaking in terms of what it got but it uh never got used in practice because of that property as far as i've seen yeah i feel like a lot of our listeners probably know what a trusted setup is but we should maybe just declare that we've done a whole episode on this but this idea of basically creating the parameters for

snark you do it like right now it's usually done in like a finite period of time so that the snark can kind of kick off you just sort of said though with the universal one you can kind of make changes so maybe can we kind of explore what universal means here what do you mean you could like change the circuit or something after the fact i guess you could do that without actually running another trusted setup right yes so what i mean is that when you're building a general purpose snack so a snack which you would be able to run for many different types of computation um you can sort of split it into two phases one of the phases is where you describe the computation that you're actually

trying to prove so this computation might consist of a merkle tree or it might consist of it consists of an encryption scheme or maybe you're trying to prove that you tallied a bunch of votes correctly or that sort of could be anything the other part is generating your parameters so what we do is we are basically able to create a disconnect in a universal system we're able to have it so that the parameters that you generate don't even know what computation you're trying to prove so you can run the two completely independently which then means that if you want to change the computation you don't have to change the parameters do you still have to run one part of the trusted setup then you still have to do

something which i sometimes call a deriving phase so you have to take the parameters which you already have and then you have to run a deterministic computation so no randomness is used in order to generate the reference string that you will eventually use but the important thing here is that it is not in any way trusted you don't need to do an npc here you don't need any other players you can just locally run the computation and work from there it's the social aspect of trusted setups that has been kind of the bane of people's existence right like the fact that you have to organize people and the reason also that we do that is because this idea of like incorporating lots of

different inputs from lots of different people the feeling is no single person could corrupt it or know it or share it or you know the reason you want many participants is to give that sense of trustlessness i guess you call it or like any individual can say that they've contributed therefore they know that it's been done correctly and this is a way to build trust within the community that this thing has been done right but it's super hard to organize kobe you and i worked on one of these for plumo and it ran for a few weeks maybe a few weeks or a month and uh and it was i mean it was actually kind of fun to do but it was also definitely a coordination job of like getting people together to do it at the

same time and it's definitely something tricky especially when you're working on large parameters so in circuits like plumo or the filecoin one it's very hard to get participants or many participants because it takes a lot of time and it takes good hardware to participate so it it becomes challenging for everyone to participate because you know if ideally i want to trust it then i could just participate but not everyone can at this point so it makes it less practical and that's why universal snarks are really important are awesome although with universal snarks you still do have to do a trusted setup it's not like it wipes out the trusted setup it just you only have to

do that one time what was it like before though like was it every time you wanted to do any sort of update you just have to go through the entire process again yep i mean i don't think it was done to be honest i think just people didn't use them yeah okay so but with this advent of the universal snark like what did that become what what did that evolve into so i'd say eventually it evolved into systems like marlin and planck which lots of people are interested in and using for lots of different reasons in sort of getting there i would say the first thing that idea that we came up with was um sonic which was the first universal snark which was like

i'm going to say efficient enough that it could be used in practice it was a valid option um some trades yep with sonic kind of like the i would say the thing that i was really struggling with for a long long time is that there is kind of an inherent quadratic nature to snacks like they almost always end up looking a little bit like a matrix computation so you have your x row and you have your y row and then you have to try and um try and say something interesting about this matrix the matrix is spas typically so you have all of these quadratic parameters doing all of these constraints but actually you're only using a linear number of them and this

was really really annoying kind of the way we got around it in sonic is we sort of said okay i only want to have a linear number of parameters in my common reference string because i don't want that to be terabytes long i'd prefer to keep it in the megabytes preferably but there is like another way in which you can embed polynomials into a system and this is using the random oracle model so you can take a polynomial you can commit to it you can hash that polynomial and then you can use the hash as like a challenge point to evaluate at so i'd say probably the key

tool we were using in sonic was to have this separation to have we're going to have a set of parameters in the reference string one parameter got from around morocco and then we can get our quadratic proving system without actually having quadratic costs appear anywhere in the system and this is the setup that well not the setup setup means something very specific here but the kind of methods that um plunk is using the kind of methods that marlin is using the kind of methods that more recent one ones that people have been introducing i think one one that came out on april the other week was called vampire is using it's like always the same you have your

set of um powers of tau and you have your challenges which you get from a random oracle i just want to go back a little bit so in zcash there were two trusted setups one was called sprout one was called sapling i'm just trying to figure out timeline wise when i saw that talk at zcon1 you were working on universal snarks but had that been actually incorporated into sapling no so i think previously i possibly had my timelines wrong i think the time when i um first met the people at zcash that might have been in fc so probably 2018. okay or could it might have been 2019 but either way it was earlier in the year

at the time i think the motivation for sapling or the key motivation was that ariel had found a problem with the first setup oh yeah so they were very keen to run the second set up as soon as they had a workable solution and a reasonable cover story in order to do so the cover story at the time being we're going to upgrade to grout 16 because it's more efficient and we're going to do this as a chance to get down our circuit size and all the rest of it this is what they were telling the community at the time i think behind closed doors they were um panicking yeah that actual that story there's a episode i i did years ago with sean beau who talked through a lot of that stuff and

actually in the recent zk hack puzzles we actually got a chance to explore what that bug was in one of the puzzles it was kind of cool we'll add links to all of this in the show notes if people want to want to check it out mario actually were part of proving the security of the sapling npc right yes so they were using slightly different parameters to jensen's original parameters in particular they had tried to make them suitable for the two-round setup and the original scheme he had wouldn't have quite worked for that and so they sort of came up to me and were there like here's our security proof um can you check it can you make sure it's correct and i remember looking at it and being there like it's going to be easier for

me to prove this from scratch than to um then to audit this particular proof so that's what i did i went straight into the generic group model which is i would say if your scheme is insecure in the generic group model then it is insecure in any model it's like the baseline for security and it's also probably one of the easiest models to analyze things so that's what i went into and i'm there like in the generic group model can i find a floor they also at the time were using a random beacon um just at the end of the setup in order for the security proof to go through basically i didn't do that

i i didn't see what the random beacon was for i still don't really see what the random beacon is for so um don't worry if you don't want to use a random vehicle for the grout 16 setup it's fine you don't need one was it through doing that work that you came to this idea of the universal snarks or was it more like was that a separate problem that you were solving like more from scratch they were both quite separate okay i mean the reason why i was like had in mind the way i wanted to prove the grunt 16 setup was from all of the work that i had done on setups for the universal setting so it's not as if i was coming into it with no knowledge about how setups around i was like very much in my comfort zone um but equally

i wouldn't say that there is a link more than that mary i have one question and i know we're now kind of deep into the story but i am so curious like what were you doing before this like what did you study to lead you to this kind of working with yen squad in general were you just like you love math like i'm just kind of curious what you were up to before i did a maths degree at university of bristol cool and what why cryptography i've never had an answer for that it sounded cool is it sort of like is it puzzle breaking or doesn't even really know what it was at the time to be honest that's okay i mean like i had read the odd book here and there but like

certainly when i started my phd it was because it looked fun i hadn't reasoned more than that nice i've always been kind of curious about what got people excited about the topic do you feel like today is in doing this work like what is the kind of the thrill that you get as you crack one of these things that's sort of what i'm trying to understand uh it's really satisfying when it works okay most of the time it doesn't work i'd say for every successful attempt there are about 100 at least unsuccessful attempts but when it does work it's like you feel good nice

yeah i guess as a side comment from for someone that apparently just stumbled into cryptography it seems like that you you understand really well because i personally learned a lot from you on how to get into these things in a very deep way so um yeah i think that's a really cool experience i mean thank you i i want to go back to where we were in this story he's so sonics i remember when that came out it was quite a breakthrough was that ever implemented did anyone actually create the sonic's implementation and used it um so there were certainly proof of concept implementations i mean um sean who i should say was like

a key um person in designing sonic as well it's not it's not like i was like alone in that we were very much team effort john did an initial implementation for the paper and i think there were some people that sort of looked into implementing it afterwards as well and certainly it was one of the initial basis that they were thinking of for halo 1 before the follow-up works came out but i don't know whether anything ever made it into production i think because like literally the year after people were there like we can do it even better so okay the people who had been working on their implementations were possibly a bit put out but they um that they went with the newest schemes rather than the older one yeah as far as i remember the the metro labs team had the good implementation

um but it was never used in practice okay what did people build on from there like you mentioned marlin and plonk but like what was the part that needed to sort of be optimized more so when we had sonic initially the kind of um setting we had in mind that we were thinking of was just i'm going to prove a hundred proofs from different parties and these hundred proofs are then all going to go to a minor who's going to run some extra computation and after the miner has run the extra computation we're then going to have something which is actually succinct which you can actually verify very quickly because it's been aggregated um

trying to explain this model to like external people and to reviewers and this sort of thing didn't work very well it didn't work at all in fact we um we tried uh but what did work was coming up with an alternative scheme which was like actual universal actual um succinct from the very first time that you prove anything which we did come up with a way of doing that in order to sort of i guess get people to realize the significance of the result but our way of doing that was very proof of concept like you're talking 100 i don't think it was as much as 100 but it could have been as much of

as 100 group elements and lots of pairing equations and lots of proof of effort like it was um very much uh oh you you want it to be like you prove it in one go okay here's a hammer it's possible it's possible so um what the follow-up works were doing is they were taking our i guess um setting where i had applied a hammer and being they're like look you don't need a hammer there's like smarter ways of doing this where were they taking the techniques that they brought into it was it sort of like known cryptography techniques was it coming from different fields potentially i think say initially i would say the two main

mindsets that were solving it were ariel who came up with planck which was using this sort of permutation type argument where the permutation argument he had certainly seen in solid sonic but the way of um that he instantiated it was using lagrange polynomials and that was coming from the iop world uh interesting uh the other person who found a way of doing it and the method looks completely different is ali ali kaiser and this was marlin and he was like if we use iop techniques which he had been working on in aurora which was a post quantum system then again this is something which we can use in this setting in order to do

things smarter so yes it came from still zero knowledge space the ideas that were being applied but um different zero knowledge spaces and both planck and marlin are in production now this is just a check elio is using marlin right yes it's funny because like i always associate marlin with pratice mishra he was um i mean he's awesome he's made it work really okay he's um well not only implemented it but was every single part of the marlin paper pratish had an input in nice that sort of brings us at least research wise to today were you working at all on either of those projects as well like after working on

sonics did you kind of continue on that work or did you shift directions um so i was working on marlin i was one of the authors there okay um i would say possibly a sub-author compared to more important people um and most of the time i spent my time with my mind being blown being there like this is a really cool way of doing it i learned a lot okay it was um it was an awesome experience i would say after marlin came out i went away and was there like job done problem solved isn't this great um meanwhile other people were there like this this prover is pretty slow i mean obviously it's a million times better than what it was before

but still if you're wanting to prove something with millions of gates snarks can be pretty heavy i'm i'm sure most of the listeners will be aware of this and i would say that there were one of the key things that people have been looking at more recently as like a potential solution to this is look up arguments the people at aztec they were there like if we do a lookup argument then we can get all of these boolean gates much much cheaper they um introduced blickup as like a way of doing this and it really works i mean is not a perfect solution because you have to find a way to integrate your lookup scheme nicely

but in terms of getting your costs down it's one of the most effective techniques that people have found and the people in halo 2 which is another direction which um the field has been moving in by the way i'm happy to i wasn't involved in that but i'm happy to talk about it more if you want to i have also found that if they apply let up upgates and this is really good for their system as well so i think one of the changes that we've seen when moving from bc tv 14 and growth 16 to sonic plunk and marlin is that they were all talking different languages right like the original grot 16 was around we're using r1cs where people got used to editions being

very cheap but when you move to sonic and plonk that radically changed that's also one of the reasons that you had to introduce lookup arguments right because the things that were achieved before are not cheap anymore you you cannot do a lot of additions in one constraint anymore uh yes this is absolutely true and grout 16 editions are free you don't worry about the cost of additions so lots of people had really optimized their computations to be described with as many additions as possible and as few multiplications as possible because this is what worked with the proving system

in a universal snack it would have very much surprised me if additions were free just because you have to be able to describe your computation right and if you can't describe your computation in the setup you can't it's universal then the proof is going to have to describe it somehow and the result of this is that additions have a cost and yes for marlin and for blanc the cost of an addition is pretty much the same as the cost of a multiplication and this means that all of these lovely optimized uh arithmetizations are not quite so nice anymore it hurts really well it actually takes away from is it because those arithmetizations are they're expensive in the first place and

now they're kind of useless it's just that they were free before and now they're not okay what is arithmetization i probably should have asked that first um the way of describing a computation in a form that a snark can read it ah okay so before it was free but then they did they optimize it or they just used it a lot and now it's not free multiplications have never been free and still aren't free but additions as in like your linear constraints used to be um you didn't pay for them in terms of prover cost um so yes people did take advantage of this

and they did optimize for it and if they had not a multiplication gate which they could describe as an edition gate then they always would but i would say really the change is that you have to pay for them at all because even if you hadn't optimized for multiplications or expensive editions of free you're still in a situation where you have to pay for both multiplications and additions and this is going to have an overhead got it i want to ask you going back to the story like at some point you start working at the ef at the ethereum foundation what were you working on when you joined like what were you still working on this work that you took with you into the ef or did you kind of change directions at that point

i spent a little bit of time looking into dkgs when i first joined the ef okay what are dkgs distributed key generation it's again a trusted setup this was why i was there like ah this seems like something that i'm that i'm into but it's a different sort of trusted setup it's more a trusted setup for a threshold system so something where you might want three out of five parties to be able to sign a message um but not two out of five parties in order to run a threshold system you would typically have to run a trusted setup in order to get your public key that people can sign under okay mary actually we worked on something together

an aggregateable dkg so maybe it would be interesting to talk about why that's interesting and why that was needed oh yeah that was a that was a really fun project actually an aggregateable dkg is basically a dkg where all of the different parties transcripts can be combined into a single transcript so if you sort of end up with 100 transcripts and you would sort of pay the same cost for verification and for communication as you would for one transcript and when you consider the fact that these transcripts contain encryptions basically of every single party in the system's private inputs

that they're going to need they're quite big each transcript is you know sizeable so being able to aggregate them down gives you huge savings it's a really nice thing to be able to do where's the savings for this actually is it savings in terms of the size of the output of this or is it saving like is it savings in what you have to do to it uh it's savings in terms of communication so the amount that you have to communicate is not only smaller but it becomes um something which you can use gossip networks in order to communicate which is sort of quite nice the other saving is for the verifier if

at the end of the trusted setup you have somebody that wants to check that everybody has contributed correctly then the cost of doing that is much cheaper than it otherwise would be so one of the motivations could be that you have a random beacon and where some instantiations of it were using threshold signatures and if you have let's say a network of validators that need to produce these random beacons by producing threshold signatures then you're in a situation where you have to do this setup every time the validator set changes

so having something that is easier and faster that is one good way to to make that more practical or safer or better so for a threshold system there's sort of two things that you need one of them is the public key which you would be generally verifying your random beacon output against for example the other would be the secret key being that you do actually want people to be able to compute the random beacon output if they cooperate and people shouldn't be able to do this just by you know waving their hands they should have secret key information in order to

produce their share of the output and sharing the secret key is also something which you need to do during the trusted setup process when you generate this key so it has a few let's say popular users and one one use that we've just said this is a random icon but there are other uses that people have been talking about so for example threshold signatures and threshold encryption yeah and there's been also a lot of work around this so it's a topic that people are very interesting in it even crot had recent works around this right

yes he also has a non-interactive dkg so the scheme that we were describing is also a non-interactive dkg but it um is sharing a different type of secret to the one that um jensgrott is sharing so you when you started at ef you were working this was sort of the new problem space that you jumped into is this still what you're working on primarily or like yeah i'm just kind of curious what other work or what what you're working around on now so there's sort of two directions i've been working on sort of recently one of which is related to this one of which is um i don't know how many of you have heard of the frost dkg uh we did do a security proof for that

and the reason why i was aware that maybe we wanted a security proof for that was because i had already been looking at this aggregate aggregate ability property beforehand and read the frost security proof and was like we can we can do this better the other thing that i have been looking at is back into snark land um and that is look up tables okay i finally noticed that maybe maybe these are something that it would be nice to do better oh how do you do them better like just from what you described it's like a look up table is you have the outputs of a lot of inputs so like what does it mean to change that or make that better is it like the

reading of it to be faster or yeah so the motivation for doing a lookup table is always prove a time okay like the verifier doesn't care because the verifier is constant time if anything that there if i would rather there wasn't a lookup table because it's a little bit more more work for them but when it comes to prover costs they can make quite a big difference our primary aim for the lookup table was prove a cost can we get the prover cost to be i'm going to say better certainly there's not that much prior work on specifically this topic there's lots of prior work on like related topics like zero knowledge sets or or actually even um accumulators

but for specifically up tables i would say the main one that i'm aware of is pluck up and the issue with black up is that your prover time is linear and the way which they're able to make the proofer actually run faster is they make it so that the linear cost that the approver is paying for the lookup is the same as the cost that they're paying for the circuit itself by making it so that they're working over the same quotient i realize quotient is jargon to most people but don't worry if you don't know what equation is so i would say where we have been able

to improve on that is we've been able to make a lookup argument with very fast proof of time which doesn't need to work over the same quotient as the proving system itself it can work over a different question is quotient a technique what can can you help me understand what that is so you've changed the quotient so i think we might need to explore it okay so when you're like designing a lot of the snarks using plonk type techniques or marlin type techniques um one of the things they use um all the time is not the standard basis for polynomials but the lagrange basis so a basis where you're saying this

polynomial evaluates to three at this point and five at that point and ten at this other point like you're describing your polynomial in terms of its evaluations at certain points the quotient polynomial is basically the polynomial that evaluates to zero at all of the points that you're interested in sometimes people call it the vanishing polynomial vanishing polynomial same thing yes actually probably better terminology [Music] and that's the quotient polynomial it's a polynomial that you typically want your proving system to vanish over so in this way you can see as equation because you take a polynomial mod vanishing

polynomial oof okay when you talk about changing which quotient you're using over vanishing polynomial is better it's better are you choosing a different polynomial then is that sort of what you're saying like a better polynomial for the lookup table i wouldn't necessarily say that it's better but i would say that it is um different and this in particular means that we're not constrained in the same ways that the blackup argument is we don't have to try and make it so that our constraints nicely match up with our with our vanishing polynomial we can use a different vanishing polynomial if we want to cool

that word does help it is i think it is better in this sentence it's probably what everyone else calls it all the time and i just missed the miss the bus sorry i don't know i think it's really good for us to hear that though and even i mean the language of a lot of these things i think is something that does throw people off so i think actually like teasing that out helps i i definitely think i understand a little bit better you're not improving the lookup table you're improving the provers ability to use it yes we can make it so that the prover for our lookup table is basically log sized in the uh in the number of entries rather than linear sized if you were to consider it as a standalone

protocol i'm very excited about this yeah and so this is this is ongoing work yes this is ongoing work we plan to go public very soon hopefully it'll be public before this uh podcast goes live oh cool so is this it's going to come out as a paper yes we've called it culk culk yes this is related to pluck up it's wrong [Laughter] i think what i'm curious about here is like so the publishing of this type of work you you put it up as a paper is the expectation that like this will be adopted by teams that are using these techniques i'm kind of curious about like the

motivation as you publish this stuff like is it sort of like this is additional information that people could use if they're implementing it or do you think that this is actually like like is the ef going to be implementing it is it something where like we're already doing this you should know i'm sort of just curious about work like this i mean when you're putting a paper online you never know actually you um you sort of go in there with your um sales pitch i guess sort of saying why you think it is useful but actually why it's actually useful is something that you often find out later after you know other people have seen the work other people have talked to you about this and you discover what it works for and maybe some of the

things you thought it would be really awesome for actually it doesn't work for but maybe some other things which you haven't even thought of it's a really good application for when you first go online you just you just don't know cool and i think into your credit you've been working on other problems that are very applied in the sense that they're very close to actual pressing industry problems so i think that causes some of your work to be applied very fast which is cool and i guess like that was one of the other questions that uh i had or you had another line of work right that is about inner pairing products and snark perk which are kind of related

right yes so i one of the ways which we've discovered is like really useful for trying to get the cost of snacks down in a different direction to look up tables is snark aggregation so in halo 2 they're doing this in a really cool way they're sort of saying we can take the cost of a bulletproof snark where the verifier is linear and this would typically be a problem but by doing you know a snark of a snark of a snark of the snark of the snack we only have to pay that linear cost once so if we're for example wanting to prove that a blockchain is correct since its inception then this is like this will work for that this will work really well

is this not recursion you just you call it snarks yes this is it is okay um an alternative to recursion is to just do one layer of recursion so rather than do a snack of a snack for a snack of a snack you instead do a snack of 10 000 snacks ah you batched them into one into one and we found that you are able to batch grout 16 proofs really really effectively using something called an in a pairing product argument so an inner product argument is something we all know and love it's been used in the discrete log setting when there aren't pairings since 2016 when jensgrass and other people came up with

a really cool way of doing it and the nice thing is that the actual like maths of how you do that what's happening on happening under the surface works exactly the same way for pairings so if you see a pairing as like a multiplication and you want to say that this pairing equation is satisfied you can do that with an inner product argument and the nice thing about grout 16 is that the verification consists only of pairings so then if you want to have a snark of 10 000 snacks you can run an appearing product argument and by doing that your proven costs are really very very reasonable because you end up paying

i think six times if i remember correctly six times the cost of natively verifying the ten thousand snarks to prove and logarithmic costs on the verifier side so this is like a really fast way of aggregating the downside is that we do have to use trusted setup snarks which hurts we don't know a way to do it for plank or for marlin okay although for smartpak you could have used other universal setups that already existed right so for snack pack we don't have to do a separate setup for the aggregation scheme itself so if we already have our trusted setup snack then we don't need to do more

setups we can just take a couple of universal setups and use those to do our aggregation but the base layer snark which you're aggregating i won't say that it has to be trusted setup because for example if you wanted to use a crypto 2018 paper it would work fine for that but you can't use random oracles basically um or if you can then we don't know how to do it is this is called snark pack yes are there other projects that are also doing that sort of like multiple snarks into a snark i feel like i have heard that maybe uh yes but they're using snark pack oh they are yeah one topic that always comes up when

you're trying to use a new cryptographic protocol or system is that you suddenly stumble upon a cryptographic assumption something like the generic group model or algebraic group model or even you know these older ones the key power and knowledge of exponent and all those so how should the users of cryptographic protocols approach into choosing what's reasonable to use why they should worry about the generic model or embrace it how well do you think about it this is very much uh i would say a matter of opinion in the sense that if

you talk to a different cryptographer you will almost always get a different response so this is very helpful for practitioners and i'm well aware of that if you talk to sort of someone that is very theoretical they'll probably tell you that standard model is the only thing which is um secure and it's the only thing you should use and you should use the most standard assumptions going probably just restrict yourself to you know discrete log and rsa and you're good if you talk to people that are more applied then you will hear very different opinions and honestly i think that this is quite telling because the people who are talking to practitioners the people who are implementing things for people who are seeing things deployed the people who are

really on the front line of protocols that are going to be attacked protocols that are going to be facing real adversaries who potentially want to steal very large amounts of money for example generally don't worry about the generic group model they worry about lots of things they worry about how interaction might cause a problem they worry about synchronicity they worry about how complicated the scheme is that's a big big concern they worry about especially for snacks they worry about how easy it is to audit the scheme they worry about how much documentation there is they worry about how many people have looked at it there's so many concerns that people are

thinking about but people don't ever sort of turn around and say what if the generic group model gets broken and i think that is mostly because in 20 years it hasn't been broken i mean you can think of some very contrived examples where technically you can come up with a scheme which is secure in the generic group model but isn't secure in the standard model but when it comes to um protocols which are being deployed protocols that people are looking at this is not where the attacks lie maybe this will change maybe someone will come up with an awesome attack but the same could be said for any assumption yeah i remember that people were pretty excited or at least some people would be

excited about a group proving that groth 16 was now securing the algebraic group model but uh it was already deployed before that in zika in production as far as i remember so that's that's very much uh agrees with you what you're saying i mean the algebraic group model does have some nice features being that you do boil down to a computational assumption which then means that if you're trying to if you're sort of trying to say what security properties am i getting you can end up with something which is less pages and pages of algebra or it can be more pages of algebra it can go

either way um but for some settings like being able to say because of this assumption we don't need to worry about these components in the system that's that's quite nice but yeah i do think that there is lots of dangers when it comes to implementing snarks especially when it comes to getting the security proofs right that's another thing i should should definitely say please don't trust my security proofs when i'm the only person that's done the security period because because i'm very human please check them but i don't think that the generic group model should be top of your list of concerns it should be on the list but quite low down the list yeah i completely agree i think that nobody really knows how to audit circuits for

example today it's really an arts it's manual work and an art in the same time i guess you just sort of mentioned snark pack but there is another paper that you published quite recently called snark block are these connected is this an extension on this work uh they are connected in the sense that snark block is using snark pack so the purpose of snack block is to try and create a um a block list so a way in which you can have some anonymous system where you still have some authority who is able to detect malicious behavior and block

people from the system if they are misbehaving the nice thing about this setting is actually in this setting all of our trusted setup concerns go away because we actually do have a trusted party um namely the person who is in charge of blocking users okay or not blocking users because the people who are running the proof is actually the users themselves it's like a white list for provers kind of yeah so this is a way of having users be able to prove that they are allowed to be part of the system without revealing who they are but at the same time if they for example start spamming the

network or behave in other malicious ways the authority can say this is malicious behavior i'm going to remove you from the list and after that they should not be able to prove that they are allowed to post anymore okay so the sort of key technical challenge in that was to try and create a version of snark pack which is zero knowledge which actually making it zero knowledge is very easy because grout 16 proofs have this really nice property that they're re-randomizable so if you want to add in a bunch of randomness to the system in order to make it zero knowledge that's easy proving it was a different story proving it took many many iterations um we got there but it was it was tricky

where i'm kind of curious where some of these ideas come from like you're working at the ef is it sort of like generated through work that the ef is doing is this more like in collaboration with x because the the other co-authors here are in different universities and so i'm kind of just curious about what that work looks like and how these things kind of come about so the ef gives us lots of freedom cool as a general rule of thumb we try to be involved in the community we talk to lots of the developers we listen to see if there's anything that they want occasionally they'll come up with a protocol and be there like is this secure or that sort of thing so there is sort of that i would say

frontline as well but there's also a large fraction of our time where we're allowed to decide what we think will be useful or interesting or relevant to the community and look into those kind of areas and i think that the reason why we're allowed to do this is because a lot of the goals of the ethereum foundation a lot of what they're trying to do is try and make the community as a whole successful try and make it so that all of the technologies that the blockchain space is creating is something that will stand the test of time is something that will last is something that people will use so they do want projects which will help the community they do want things that will move science forward they do want

things which will you know enable more applications enable more people to answer the scenes or the rest of it and research in areas which are you know possibly something they wouldn't immediately have in mind for their next update is one of the key ways of doing this one question i have here though is like a lot of the systems the zk circuits and systems like they don't actually work on ethereum as it is today right like there's these limitations of ethereum so i've always been kind of curious like do you ever have that in your mind or they like don't worry about the constraints on ethereum proper just like go for it oh no we worry about it you worry about it

it's um i mean don't get me wrong sometimes i sort of look at it and go okay this is such a cool thing that we're gonna go for anyway i know it can't run on our system but um but you know there are some fairly difficult limitations i would say for a lot of the research that i'm doing being that they don't allow target group operations and this is just because we've not been able to get the pre-compile through actually we don't even support bls pairings at the moment we're still using bn256 which is um not reaching 128 bits of security is the reason why people are very keen to upgrade that

so we have just one group that we can use we can't do target groups we have to i mean technically you can but it would be so expensive that you never would without a free compile um we can do hash functions we can do group operations and we can check whether a pairing equation is equal to zero but that that's all the functionality that we have and trying to get things to work with that functionality there are some things which can and in particular most snacks can so plonk would be able to marlin would be able to and you look up argument will be able to um but i work on

snack pack and on snack block and actually on distributed key generation all of these are requiring target groups and this would be a problem but there are i mean there are other systems like there are even evm compatible systems where they have they where you are able to use some of this so i feel like it's still in a way usable like right off the bat even within a somewhat ethereum like if you think of all evm is somewhat ethereum then i mean one of the things you can do is because you have it that plonk is usable in ethereum you can always take the system that you want to have and prove it in plonk if you really want to get it on chain

this would be an extreme solution but it's it's an option okay i this actually leads me to another question i have which is about implementation and like we just talked a little bit about the constraints of specifically ethereum mainnet but how are you working with developers themselves with the engineers like what's the what's the collaboration like from where you are and are you actually implementing as well yeah i do some implementation um i only have a proof of concept but sometimes i do proof of concept and from the proof of concept this is then something which i would expect somebody who is you know potentially better trained than me to be able to work with and

integrate into into larger systems and did that change with you working at ef like had you been doing that before or is that something you're doing more now i had looked at this a little bit before mostly in python but it was something that i was very keen to change upon joining the ef actually um i mean friendly place it's not as if anyone came up to me and was like you must learn to code but i thought that in order to i guess be relevant and in order to be able to talk to the engineers and understand a lot of their concerns being able to code is such a big part of that totally what language do you work with then so i sometimes work in rest

thank you to pratish for making the artworks library i would not be able to do it without that and i sometimes work in python i've not i've not mastered c please don't ask me to use c do you have engineers in your team i just i think of the zcash story and like sean and dara when when arielle was there and that combination of a researcher and the implementer sort of in the exact same project in this exact same space do you have something like that in the ef as well where you're like going back and forth with engineers or would you say like it was more how you said it before it's like you put a paper out and then somebody's going to implement it you have a sort of initial implementation and then someone runs with it i'm just

curious about that it's a bit less formal than that i would say so occasionally when there's like a project which we do decide to take on then we will sort of be in more contact with engineers one example of this at the moment being that we're looking into single secret leader elections which is a building block that we're really hoping to use for eth2 eventually um the idea being to prevent ddos attacks and this is using a shuffle argument um and for sort of explaining how that shuffle argument would work what we would want to use or the rest of it i did do a proof of concept and since then one of the engineers in our team called george

has been taking it on and sort of actually making it decent making it good and he is someone that i would say is a real implementer so yes we do have collaboration with actual engineers we do talk to them they are in the team but it's not as if we sort of have dedicated people assigned to implement our work it's more we see first where things are actually likely to be used and where we sort of uh could actually do with the resource rather than sort of pre-assigning it one of the topics that came up on some of these earlier episodes where we talked about that relationship was the back and forth so like the researcher providing some ideas but then the implementation

providing ideas back i think halo is a great example of that where it's like coming from engineering they found the trick that then was proven more by research i think that this might be a case of sean being too modest um oh because sean doesn't see himself as a researcher somehow um yeah i mean when i was working with sean we had exactly this it would be like i would go to him with this idea he would go to me with that idea he would come to me with this idea i'd go to him with that idea there was very much that that back and forth but um and you know working with engineers in general is really nice i like doing it you do sort of get to see a perspective that you otherwise wouldn't and it does ultimately work make your work better

sort of regardless of the engineer but working with sean is something quite special oh nice maybe it's the definition of researcher and engineer which is the problem here is maybe like there's a lot more people that are combo both i guess applied cryptographer is kind of both yeah the idea that people talking to sean come up with good ideas is not surprising i think it's a last point i'm really curious to hear what kind of like upcoming work we i know you mentioned a few fields a few spaces that you're working on right now but like what can we look forward to from the work that you're doing and maybe yeah if there's any new research for us to look out for i mean i don't want to say what i'm going to be doing six months from now i

don't plan that far in advance but but do look out for culk it should be coming in the next couple of weeks very nice we're very excited about it so i also know that you've been working on another topic which is um achieving consensus and that is work that you've been doing with uh the same group that we've kind of worked on in the aggregate of dkg so can you talk a bit about that more yes um so this is really a follow-up work so for the aggregatable dkg we were talking about how do you do a dkg in synchrony so assuming that you have some kind of clock that can time people out if they don't respond quickly enough as a follow-up and the lead author on

this is glad stern so if you want to know lots of technical information then please please talk to gilad but the idea is to make it so that we can take the aggregateable dkg that we have in the synchronous setting and use it to create a dkg in the asynchronous setting which is much more challenging just because you need to be able to communicate even against parties who might never respond or might respond maliciously and the way we do that is through a leader election but the leader election is like you choose the leader after you already have all of the transcripts which the leader could be part of and it's

describing how you come to agreement for that this is for i mean when you're talking about consensus this is for validator choice i guess like validate this is the validator groups and trying to create the block production i'm assuming um so it's not specific to blockchain so okay so you could use it in other systems but if you were in a blockchain system then yes you would save validator okay maybe can you give me an example of like where it works today and where you want it to work in like more real world examples like maybe it is networks we know or maybe situations so this is specifically for generating public keys like an example would be generating a public key if you want to

do threshold bls signing actually this scheme would not work for threshold bls signing we would need to have a special purpose signature scheme but the signature scheme is you know pretty efficient you could work with it if you wanted to so this would be a way for parties to agree on what the public key is which they're going to want to sign under and it's a way for them to do that in for example internet settings where there's not necessarily that obvious a communication channel and it's certainly not easy to have like a leader or timeouts or the sorts of things that we often like to assume to make our life easy cool yeah i think one one good way to look at it maybe is that in a

synchronous setting you assume that parties um will respond online at the same time kind of that and that they will respond in some known amount of time and because you need that to hold you set you set very large timeouts and that practically makes makes things slower and in an asynchronous protocol you don't have to worry about that as much which could also be a performance boost in some cases which is nice this is kind of cool that you do need these different tools like the tools we know will have to evolve also to be able to work in these new systems in the way that you're thinking about this one

is it often in the context of blockchain or is it often not like the example you just gave was just like on the internet are you still thinking blockchain asynchronous environments uh so i'm always a little bit thinking blockchain but i'm not sure that my co-authors were who are the co-authors on that you sort of mentioned one but i'll say gillard stern italia abraham uh philippenovic sarah mecklejohn and alan tomesko phillip from the validator he's also part of the zk validator with us cool and that's already published though right that's not upcoming is there more work in that direction that you're looking at uh yes we are sort of hoping to come up with something which can do um

can do bls signatures but that's ongoing so i don't want to don't want to promise just yet nice well mary i want to say a big thank you for coming on the show oh thank you for inviting me kovy thanks for coming on as a co-host too it was a pleasure i feel like very lucky to get to be kind of in in a conversation with the two of you to be honest i mean the the levels at which you guys are working i don't think all of our listeners fully know it but i'm really also glad that we get a chance to show them sort of a look into what's going on deep deep in a zero knowledge proof in the world of ck development and research so yeah thanks so much for coming on i mean thank you so much for hosting

these podcasts they're an amazing effort and you've kept it up for years as well haven't you yeah it's we're in year four it's wild so i want to say a big thank you to tanya the podcast producer henrik the podcast editor chris who worked on research for this one and to our listeners thanks for listening