An Evolution of Models for Zero-Knowledge Proofs with Sarah Meiklejohn | a16z crypto research talks

Transcript

thanks everyone for coming so this talk is designed to be accessible to everyone even if you're not familiar with zero knowledge um there are some of you in the room who are very familiar with zero knowledge i hope it won't be too boring um and of course one of the best ways to make sure it won't be is you know ask questions anytime um that goes for everyone of course this is a talk i gave um one of the invited talks at eurocrypt last year and it's really going to cover the different models for zero knowledge and how they've adapted in uh recent years and um a lot of this as i'll kind of claim has been driven by the applications that we've been seeing for zero knowledge and the kind of you know constraints um in which we want to use

their knowledge proofs um and and so there's really this nice cycle of like finding new applications using those to inform new models coming up with like really practical zero-knowledge proofs for these applications and then sort of attracting attention um for other applications so i'm gonna talk a lot about modeling and kind of like uh use cases i'm not gonna talk so much about the details um i yeah there's lots of other places to find out about kind of how we build zero-knowledge proofs um i'm sure those of you who stay around longer in the summer like for example when justin comes will also have the opportunity here to learn a lot more about that as well um so just to kind of cover the the definitions of zero knowledge again for

for those of us who might not be familiar with them so uh basically in a zero knowledge proof we have approver uh this parrot here and they want to convince some verifier this vulture that um basically there exists a witness uh w corresponding to some instance of a language um so basically they want to convince the verifier that some statement is true namely the statement that this instance is in the language um and they want to do this basically without any interaction in a non-interactive zero-knowledge proof um and they want to do this really this is kind of what zero knowledge means without revealing any information about the witness that they hold okay so the the kind of

uh setup is here the approver basically has the instance and a witness they produce a proof um they send that over to the verifier the verifier takes in just the instance not the witness and the proof and on the basis of this proof they either decide that yes this instance really is in the language or they say actually i'm not convinced okay so the two kind of intuitive properties that we want zero knowledge proofs to satisfy are we want them to be sound meaning it should be hard for the prover to convince the verifier if this statement isn't true if this instance isn't in the language um and then we also have zero knowledge which is kind of what i said intuitively that the verifier shouldn't learn anything about the witness so in particular the only information that they should learn is

that yes the statement was true the instances in the language okay so this is like very uh for i mean lots of us are very formal but this is kind of very formal very abstract so i thought i would um use my favorite example of a zero knowledge proof um which is where's waldo so um okay some of you are nodding that's already great um at eurocrypt i spent like three awkward minutes trying to explain where's waldo to people um yeah i'm well that's that's me um but yeah so where's waldo you are trying to find waldo or wally or whatever you say in your country of origin and so the idea is that you know finding waldo is

hard and um but the prover has already found waldo and they now want to convince the verifier that they know where waldo is so how do they do this um so basically the idea is that there's you know this page in this book and um it has some dimension um m by n and what the verifier is going to do is you know out of some opaque material uh cardboard or whatever they're going to cut out a rectangle that is um basically twice as big in each dimension as the page right so it's 2m by 2n and now what they do is they kind of put this big piece of cardboard um you know on whatever they hang it up in a room

um and this is kind of all the verifier can see right is this this big piece of cardboard and now what the prover does is they kind of go behind the big piece of cardboard with with the book or with the page you know the verifier can check that they don't have anything else on them um and then they sort of cut out this like little window in the middle of of the piece of cardboard and the verifier can go up and you know inspect this and they can see that this is waldo right and so there's really absolutely no way for the proverb to cheat here right either the verifier sees that waldo is in the window or or they don't right and then the prover had to know where waldo was to hold this up um or it's not waldo

and this is not convincing um and then in terms of zero knowledge the idea is that because of the dimensions of this piece of cardboard um you know maybe the prover was holding up the page here maybe they were holding it up here it really could be anywhere behind this right uh we wouldn't see it kind of hanging out over the edge we just don't see the page at all we don't see the book and so we don't know its position at all behind this uh large piece of cardboard okay so let me get into these definitions in just a little more depth in terms of like what they actually look like cryptographically right so hopefully the intuition is is now quite clear um but in terms of actually modeling them formally you know with like games uh and and stuff like

that it's not actually really clear like you know for example what does it mean to say that oh the verifier doesn't learn anything they don't learn any information about your witness um so what this means right um so first things first um before we can define anything basically we need all non-interactive zero-knowledge proofs need to have an extra thing that i didn't include in the original interaction which is a something called a common reference string or a crs for short so we know that this needs to exist um we we can't do non-interactive knowledge without it um but you know there's a lot of different um options for kind of what this string looks like and what structure it has so this is very important uh this is going to be very

important later in the talk i should say um when i get into kind of like the modern advances in zero knowledge so this reference string can be completely random um and in which case we call the the setup uh for this uh for the zero knowledge proof trustless meaning we don't need anyone to generate it or anything we can just you know pick random numbers um or it needs to have some kind of structure and if it needs to have some kind of structure then we call this a trusted setup so again we'll see these terms later on um and then also this common reference string can be um specific to a given relation so it can be used you know only to prove things for a specific language um or it can be universal meaning you can reuse this

common reference string for many different types of circuits for many different things that you might want to prove okay but basically we need this common reference string to sort of come from somewhere um and we need the prover and the verifier to both have access to it okay so then the way we define um zero knowledge is we say that now the verifier here is is the adversary and the goal of the this adversarial verifier is of course to learn information about the previous witness so what we do is we say okay you can have your interaction with approver that's one thing that can be happening um the other thing that can happen is that we can actually replace the prover with a simulator

and this simulator is actually not going to know the witness at all um they're going to run some kind of simulation algorithm that only takes that takes in the reference string and only the instance they don't know the witness and they're going to output a proof so of course the way i've written this this isn't this doesn't look good like we can't the simulator can't just take in the reference string in the instance and be able to convince the verifier that would violate soundness and so the idea is that basically the simulator can also participate in the generation of the common reference string and in generating the common reference string they can output some simulation trapdoor um that allows them to basically fake proofs all right and so then they can so

instead of just outputting the the crs they're going to output the crs and this trapdoor and then they're going to keep that trapdoor around for themselves when they go to simulate proofs okay so the we sort of have now these two different interactions one with a you know an honest prover who knows the witness one with a simulator who doesn't know the witness at all but knows some sort of like universal trap door and we basically say that zero knowledge holds if this verifier can't tell which of these interactions is happening whether it's interacting with the honest prover or with this uh simulator who again does not know the witness in any way um

so yeah that's that's your knowledge and then we say that uh we have perfect zero knowledge if in fact these distributions are um identical not just computationally indistinguishable um it's been a while since i took a crypto class but i remember i think seeing a definition without a trapdoor that just said that like the verifier can simulate the entire interaction that's probably for interactive zero knowledge when you talk about like rewinding and producing a transcript is there a relation between these like is there a relationship are there just different definitions like if you have a sigma protocol you can transform it into a non-interactive zero knowledge proof using the fiat shamer heuristic right so sigma protocol is basically the prover sends a message the verifier sends back

a fully random challenge and then the prover responds with like the third message of the protocol and so the idea is that you can collapse this by just replacing the fully random challenge with a hash of the first message um and you know if we're in the random oracle model this is as good as having the verifier pick the random challenge themselves um so but i mean you would but you would the way you would prove security for that kind of protocol is you would still prove it using the interactive style definitions you would still talk about like rewinding and issuing two different challenges or something like that and then you would just like let fiat shamir take care of the rest the way i've defined sort of uh the definition i've given here is is

really soundness right we i say there exists some witness uh for for this statement um often what we want to show is is a little stronger we want to show not only that there exists some witness but that actually i know this witness right so when when we start thinking about like how zero knowledge gets used you know especially in in cryptocurrencies and blockchains and stuff um it's often not really useful to say oh yeah like you know someone out there might know the witness or it just exists you know in a mathematical sense it's really important to say that actually i know it right so for example going back to the kind of where's waldo example it wouldn't really be very interesting for the prover to say you know wally waldo no i'm english now

that's so embarrassing waldo is on the page i'm embarrassed so yeah to say oh waldo is somewhere on the page so you know there is some configuration of the page you know such that if you hold it up you'll see waldo it's more like no i i want to know that you know that you found waldo and that you know where it is um so this is a kind of stronger definition um that we can call a proof of knowledge or um really it's uh again the into the the way we capture this formally is not necessarily super intuitive but um it's this idea that we can extract the witness from any verifying proof so now the idea is that the prover is the one who's

adversarial they're trying to convince the verifier of something that is not true um or yeah and so again we kind of do a similar thing we can say that um we're going to replace the verifier with this emu extractor and we're going to say that um basically what the emu can do is they can run this extract um algorithm that takes in the instance and any verifying proof and from that can output a witness uh for the instance right can output a witness such that x and w are in the relation so again this is like way too sketchy we would like you can't run this algorithm

as i've stated it because this was completely violates your knowledge if anyone could do this so again we're going to just do the exact same kind of thing but on the other side we're going to say that hey how about we have the extractor you know generate the crs in some special way so that instead of um just generating the crs they also output an extraction trapdoor um and then we're going to require that extraction trap door to be able to extract witnesses and so then we can say that extractability holds if there exists a polynomial time extractor that can do this and then we say that this is a proof of knowledge if this can be done for all provers computationally unbounded and that this

is an argument of knowledge um if this works for all polynomial time provers so again it's not always like basically this is the best we've come up with for saying that you know a turing machine knows something is being able to extract it um yeah so again not always the most intuitive but um hopefully not too shocking either so let's let's talk about constructions and in particular i want to focus on one particular aspect of zero knowledge so on on the left we kind of have the assumptions that they're based on so we've got like discrete log pairings um collision resistant hash

functions this little symbol means that it's like plausibly post quantum secure um and then on the the bottom here we're going to have this the size of the proof um and this is uh you know linear or whatever in the size of the witness okay so um you know we we see that a lot of can so there's sort of a feasibility results um uh that sort of says oh we can get the size of the proof to be polylog in the size of the witness but by and large you know for the first sort of two decade three decades of um research into zero knowledge we were really sort of like not stuck but we were really in this uh column in terms of having the size of the proof be linear in the size

of the witness and um yeah that that's basically where all of the constructions uh were um and then there was this kind of um you know breakthrough result um in uh 2009 by uh former colleague of mine jensgrott um and he showed that you could actually have the size of the proof be sublinear in the size of the witness so this is what we uh now call a um a succinct non-interactive argument of knowledge which you may know by its very trendy name a snark um so just to show you the distinction there a snarg is also a thing and that's when you don't have extractability you just have soundness um and then the knowledge part

is when you can uh you're guaranteed extraction uh i guess also snark sounds better than snark um okay so that's sort of where i'm going to leave things for now with the development of zero knowledge uh and then the other sort of thing i want to talk about that was happening at roughly the same time i guess as jen's work was the kind of development of blockchains um so i you know i'm just going to go through this fairly quickly i guess i'm assuming a lot of people here are familiar with this um so a blockchain is you know basically just an ordered collection of transactions um so each block is basically just a a list of transactions sort of uh in a committed form

um and you know the way things work today at least like in an l1 is that all transactions in the chain uh basically um get captured by all peers in the network uh which we can consider to be the full nodes um and then they all get sort of replayed um to ensure that they all agree on the current state of the blockchain right so we sort of all play through the transactions you know in order um and in that way we can agree you know in a simple you know let's say bitcoin or something in terms of just like transfer of coins we can all sort of replay the transactions and then that way we can all agree on you know who has coins at this given point in time uh so let me sort of like

give like basically the simplest sort of thing we could be trying to maintain the simplest state um which is really just like you know balances you know who has how much money at a given point in time so let's imagine that we have you know our four birds and we're they're all gonna have like registered addresses in the system so we can have sort of some tree um with all the leaves representing their their public keys um and then we can sort of have you know a concise representation of this in terms of the root of the tree and then we can have another tree representing the balances associated with each of these um each of these addresses or keys right and so we're going to want to maintain the leaves in in the kind of same order um and so the idea is that you know

transactions are just going to be very simple uh transfers so we're going to have the index of the sender the index of the recipient the amount being sent and then a sort of signature on all of this to make sure that you know people can't spend each other's money and we're going to say that this transaction is valid if the sender has enough money meaning when we go and we look in this balance tree at their index you know the amount that's stored there is is strictly not strictly is greater than or equal to the amount they're trying to send um and that the signature in this transaction verifies uh meaning under the public key that we obtain from the address tree um you know the signature on the rest of the transaction data verifies

and then so that's sort of making sure that transactions are are good and then the other thing we can do is we can if we do think a transaction is good we can process it meaning we can incorporate it into the global state right we can replay the transaction and use it to update the state um and and see what the new state is right and so processing this this again quite simple transaction basically means that we take uh the amount that's being sent we subtract it from the sender's balance and we add it to the recipient's balance yeah um okay so in terms of yeah checking transaction validity um oh this is an example i don't know if we need an example for this group but i'll go through it really quickly so let's imagine you know everyone starts with uh

10 coins um and then the idea is that when we go to verify um so yeah let's say we have a transaction and the parrot is sending um what is that a seagull there we go the parrot is sending two coins to the seagull no to the emu because it's a zero and no to the sequel i can't count um and so yeah so we're going to use their public key to verify the signature um and then when we go to um process a transaction we're going to again subtract uh two from the parrots thing so now they're at eight and then the seagull is now going to be at 12 because they're going to get those two

um and just to note the the other side sort of a concrete thing is that then the root of this uh balanced tree is going to be changing constantly um as we process these these transactions right so the changes we make in the leaves are going to propagate up to the root and this will result in a new root of this tree whereas if we assume like a static set of participants you know the address tree is basically never going to change okay so this is just like a kind of formal um statement of these things so that you can see where you've probably already seen where i'm going but um you know i'm just writing this out in terms of um what i've just said but showing this as a an instance and a witness in some um in some relation right so we have the

kind of like validity relationship which says that you know this the information in this transaction is is valid and then we have the kind of like state update relation which basically says that as i'm processing transactions into the current state um i'm producing this this new state so the old state is like uh in black here and then the new state is in purple and the idea here is that i'm proving the kind of collec correct relationship between the new state and the old state okay so now um let's sort of consider again like the the model that we currently have for how the state gets updated and how participants sort of um you know hear about it and

um and react so let's imagine we have a a full node represented by this flamingo and so you know being a full node in this like miniature system basically means that they maintain full copies of both of these trees the address tree and the balance tree um and now the idea is we have participants and they're sort of broadcasting their transactions out into the network um these transactions uh these transactions are getting heard about by some relayer um and you know they're just kind of collecting them and then at some point what they do is they they put all these transactions into a block right and they say um so we can already like phrase this in a slightly different way than what you know would happen like today which is we can have the kind of

header of the block be the root of the address tree um and then it can be now the new route of the balance tree taking into account all of the transactions in this block right and then the body of the block can contain all of the transactions so the idea is again like how do things kind of work today um you know the idea is that the full node is basically going you know in order to check is is everything valid here um they're basically going to replay all of those transactions and by replay them i mean they're going to apply them like sequentially to the uh state that they have stored and then they're going to get the new state this purple one and then they can you know they can compare it against what's in the header of that

block but fundamentally they're taking all the transactions um and replaying them and that's kind of the way we have to do things um yeah and then of course if they're happy then they're going to update their balance tree with the the new information okay so let's imagine doing things a different way very conveniently of course i've phrased this all in terms of uh you know statements um in a given relation so let's imagine that in the block in the body we can say okay here's the new uh balance tree for those of you who you know care about these things and who want to have that information and then here's also a proof for those two different relations so one

a proof that all the transactions that i sort of factored into this block are valid um and then two a proof that i processed all those valid transactions correctly and that i really use them to produce this new state um and so the idea is that now what does it mean to check um if this was okay well basically this just means checking so that the instance here is just like the all the roots of all these trees right so the the root of the address tree and then the two things like the root of the old balance tree and the root of the new one um and then just this proof and so the idea is that the full node can still you know check this um and they can still sort of look into the body of the block take the new balance

tree and and use it but um conveniently light clients who don't want to maintain the full state who might just be maintaining the headers like the roots of the trees can also perform this check right so we can have sort of more people doing this um and yeah this is kind of the the idea really behind um something like a roll up uh for those of you who are familiar with such things so something super funny about roll-ups and about the use of zero-knowledge proofs in roll-ups is we don't care at all if there's zero knowledge right these like the

yeah we don't care if the proof were as large as the uh witness meaning the list of transactions then this would not help us in any way we would not be interested in this at all so we actually don't care that these are zero knowledge proofs the only property that we're interested in here is uh succinctness right so there's no point in using general zero-knowledge proofs there's only a point in doing this if we're using things like snarks see this is like a zk roll up and it's funny because the zk is like totally unnecessary but there are other sort of types of roll-ups where we do care about having zero knowledge like maybe each individual transaction you prove something about it to even to the realized server but anyway um so yeah so

this is kind of again really funny um especially since this this industry has been like very excited about zero knowledge proofs and very excited about adopting them um but maybe it's not surprising that this this uh graph i showed of kind of the constructions we have you know a lot of the work over the past like decade plus has really like been on shifting this very far to the right right so again this like feasibility result in 2009 said that um the size of the proof could be sublinear in the size of the witness um you know a lot of the work um it has been on making the size of the proof constant in the size of the witness so for example um the state of the art today um

this is again jen's construction by jens the proof has three group elements and it requires three pairings to verify and that's true literally no matter what the size of the witness is so um that sounds that's crazy right like that we can do that um so let me sort of say there there are obviously downsides right it's not like we can just do whatever we want whenever we want um so one of the one of the big issues of um of snarks in particular and of so the term snark i guess is very complicated it means different things to different people um so if i say snark without

anything in front you can probably assume i'm talking about a constant size snark um meaning where the size of the proof is constant um so one of the big things that people have like been chipping away at quite steadily over the past really like three years um is focusing on this question of prover runtime so for a lot of the constructions we have the um runtime of the previewer is n log n and also like big constants it's not just like an asymptotic thing there's been a lot of really cool papers recently um focusing on having the size of the proverb be linear um rather than log in um and the only thing i'll say about that just to i mean an area i think is is cool um is that area but also i'll just mention

um so a lot of the complexity of um of these like circuits for snarks is um revolves around hash functions so like encoding sha-256 inside a circuit requires a huge amount of constraints so i just want to very briefly mention like a really i think interesting line of work um looking at coming up with like snark or stark friendly hash functions so for example even something like peterson which is like an algebraic hash function is much friendlier in terms of the number of constraints it requires which i've kind of highlighted here so um yeah this is using socrates um to basically say what how many constraints

do we require for just to prove um knowledge of a hash pre-image basically so we can see it's like uh you know an order of magnitude for pederson as compared to 256 um the downside of paterson is it's kind of like slow to compute outside of the circuit and so yeah there's like recent works like poseidon for example um that kind of tried to get the best of both worlds and in fact get better than peterson in um in terms of the number of constraints um so yeah that's just like a very brief um side you know if that's something people are interested in exploring further um so the current constructions that we have by and large for a constant site no actually all the constructions that we

have for constant size snarks require what's called a structured reference string and so again going back to this idea the common reference string i said it could be either random or it could be structured and having a structured reference string basically means sort of relying on these trusted third parties in some way so let me sort of um get into that a bit more so there's really sort of four ways that we can consider of how to generate a reference string so yeah these are shown here we can have a sort of completely trusted approach a subverted approach a transparent approach or a kind of general multi-party computation so let's first look at this idea of the trusted setup so let's imagine that we

just have one party generate this structured reference string on their own so why does this mean that we have to trust that party it's not necessarily obvious and in fact it's not like a universal fact like you you could imagine having systems where uh one party could generate it but but not necessarily um no no the trapdoor but i said a lot of the focus we have is on perfect zero knowledge and so what that means is that actually the process of generating even the honest structured reference string essentially uh incidentally produces the simulation trapdoor right so like these these algorithms for generating the simulated the simulated reference string and for generating the honest one are

actually the same algorithm so i said i would finally give like an example um so for example if we just have a really simple structured reference string um which just consists of these kind of like monomials um in alpha uh in alpha in the exponents we have like g g to the alpha g the alpha squared uh g to the alpha to the q then the idea is that the trap the simulation trap door here is just alpha and basically there's no way to like generate this reference string without knowing alpha yourself so does that make sense great okay so the idea is that this is this tau that you learn in generating the reference string single-handedly is the

simulation trap door and if you remember the definition definition of zero knowledge um with the simulation trap door you can provide proofs of uh false statements so uh in for example something like zcash you know if we allowed one single party to generate the reference string then that one single party could um spend coins that they don't have right because they could provide convincing proofs of you know oh i had like i'm sending money that i have put into the shielded pool um but that would be a lie and um but they could do it anyway because they could simulate those kinds of proofs all right so this is this is why um this is this is not really realistic in any deployed system right like there are

real consequences of allowing a single party to do this um and you know even if that party's very nice and very honest um you know they would have like significant financial incentives to um to use that simulation trapdoor in some way and so we really wouldn't feel comfortable with such a system where one party would have all that power okay so let's kind of go to the complete other end of the spectrum and let's consider a subverted reference string setup where basically now we can say you know what the adversary can just like fully generate the reference string themselves um you know however they want so this was considered by a paper at asia crypt 2016 by um mihir bellari georg fugspower and alessandro scofuro

and the idea here is uh this is a very these are very strong definitions um basically so if if we define subversion soundness then we want to say that even if the prover fully subverted the reference string meaning they fully know the trapdoor it should still be hard for them to prove false statements all right and then on the other side we can talk about subversion zero knowledge which says that even if the verifier the adversarial verifier fully subverted the setup process meaning they fully know the trapdoor um that um they still can't uh break zero knowledge they still can't tell if they're interacting with the proofer or with the simulator so again these are very very strong

definitions um and so maybe it should come as you know not a big surprise that one of the main results in this paper is a big impossibility result which basically says that you cannot achieve subversion soundness and um you know regulars your knowledge at the same time um so for those of you who are interested they do have some positive results for example they show that you can achieve subversion soundness and subversion witness and distinguishability at the same time which is like a weaker notion of zero knowledge and they show that you can achieve subversions your knowledge at the same time as regular soundness but to be honest the one we're really interested in is is the first one and so we we just know um that we can't do it so um that that's

unrealistic as well um so transparent um setup basically says that you just generate a uniformly random string um and this is kind of the the idea of a stark um that's what the t sort of stands for um so i'm not gonna say much about this i'm not really there's people in this room who are much more expert in starks than me justin is probably going to come and tell you all sorts of exciting things about starks um the thing i will say is there there is a trade-off right so in general you can't get constant-sized proofs um they're a polylog in the size of the witness but you know on the other hand you do get this really nice property that um you don't have to trust anyone for the

setup so um yeah that's really all i'll say there yeah right so in the transparent setup the reference string is random and if we have say a random oracle some random function that gives us the randomness or if we say that the digits of pi i don't know like randy then we can actually that actually then leads to subversion sounds it just probably is not in the like it's not in the playing mode it's just insane random organ there is no subverting the process if the process is just like hash pie okay so the last thing i'll talk about is um this this last model which is

basically okay we can't really let any one person do it so let's just get a kind of bunch of people together and have them generate the reference string um together all right so this um this has been done a lot um so researchers have spent a long time developing um optimized you know if we if we just wanted to use like general mpc this would be slow um mpc is not really designed to scale to you know that many participants um and so researchers have spent a lot of time developing optimized npc protocols for this exact problem right for generating these uh structured reference strings um so um yeah the this has been also run in

practice in these kind of complex uh ceremonies um so for example um oh yeah sorry you know that's actually the next um the next point i wanted to make so uh well before i get to the idea of universality you know i'll just say these again these things have really been designed to kind of scale to tolerate dropouts um you know to to to work really precisely for this setting um but there is this downside of doing these kind of ceremonies right so one is well you're still relying on all those people to not collude right so if there's a small number of purchase that's kind of why we care about scaling them i should say to a large number of participants right because essentially if all of them collude then they can take their

randomness that they used and piece back together the trapdoor and then um that's too bad so that's kind of why we really care about having more and more participants to convince ourselves that it's more and more likely that not all of those participants would get together and collude um but um the other sort of downside aside from the fact that well we're still sort of trusting in some sense um is that if the reference string is not universal meaning it doesn't work for kind of all the circuits we might want to consider proving um then we need to rerun it right basically every time the protocol changes and this isn't just hypothetical um so zcash you know has actually done this um so in the first sort of iteration of the z cash yielded

pool um sprout there were six participants in this trusted setup ceremony um and then they sort of you know changed the zero knowledge proof they were using they made a lot of changes in the protocol um and so for the second ceremony um for sapling they by that point had developed much more optimized npc protocols so there were a lot more participants but crucially it did have to be rerun and now i should say if if i am talking about zcash concretely they've really two weeks ago or something just uh got orchard out so that gets rid of the need for trusted setup ceremonies which is cool um but yeah but i hopefully that the point remains that every time we rely on trust like trusted setup ceremonies um we're

just gonna get ourselves into this cycle where every time we want to patch or update we're going to need to consider the complexity of running this kind of process which is a complexity for sure um so i just want to very briefly mention i do want to leave time for questions um this kind of alternative idea um that um i developed along with uh a bunch of my collaborators um jens grott merkel of cool vice mary mallor um ian myers and sean beau at zcash um and this is the idea of an updatable snark um so this work i think we started out focusing a lot on updatability and being kind of inspired by by that and the the model for it um but one of the main sort

of side effects of this work in some sense was actually coming up with uh actually having a snark that um gave you a universal reference string um instead but yeah so the idea of an updatable snark is that we can we sort of start out and someone says okay here's the reference string as i see it and you know i i know the trapdoor from it okay like full full disclosure um i know the trapdoor you know because so far it's just me who's contributed to it and the idea is um that this is a universal reference string from which sort of circuit specific reference strings can be uh derived okay but but what everyone is going to be contributing to and agreeing on is the universal reference string

and then they have this kind of update proof which basically says okay i took what was there before which for now is nothing um and i folded in my additional randomness um alpha okay and this proof can be made public it can be publicly verified against again the kind of using as the instance like the previous reference string and the new one and so the idea is that right now this is like a fully trusted setup right the parrot has like fully generated the reference string um by itself and they fully know the trap door behind it they fully know the randomness but now another participant can come along and can say well hey i'm going to fold in some additional randomness myself and then maybe the parrot comes along again and and is the next one to fold in

randomness um but basically this process can kind of just continue indefinitely this process is also open to anyone anyone can come along and um and say hey i'd like to participate um and so the idea is that no one is going to know the trap door you know if we just think of the trapdoor as like some combination of all the individual bits of randomness as long as one party is honest no one is going to know the trapdoor um and so crucially you know if you don't trust the existing set of participants you know just jump in and update it yourself and now you do because hopefully you trust yourself um to you know throw away your own randomness or whatever um right so this process doesn't have to have an end this

uh and that's quite different because you could say oh surely this is just like itself an npc and in some ways it is but the idea is that it's not sort of time-bounded um we don't say okay now everything's done and this is the structured reference string we can just continue updating it on the fly um and so really what we can think of this is as sort of like augmenting the security that we would get from a ceremony or something like that right so we can say okay we can run the ceremony we can generate a sort of like candidate reference string you know maybe some of us already like really believe that this reference string is good and that those parties weren't colluding um but then the idea is that you know we in a blockchain like we already have this like very sequential process that's

going on right we're already sort of generating these blocks and so the idea is that we can just sort of stick these update proofs into the blocks um and it's like a quite seamless integration right so again this is kind of a nice example of of where that we sort of looked at the existing structure we said you know there's already these parties that are generating things in a sequential way we're already trusting them to not all collude right we're not making any additional assumption at all they already have a huge amount of computational power um so you know this is really not adding a lot of overhead in terms of what's there and again the idea is that you know full nodes can actually verify these individual update proofs um so yeah so that's kind of the the story um so just to you know um so

jonathan brudel um you know had this lovely uh sort of rainbow slide showing this amazing kind of activity that's been happening in this space over the past really like 10 years honestly um and um and yeah we just have uh this is a little out of date i should say sorry um if your protocol hasn't made it to you um but yeah this is just um yeah i think it's really incredible zero knowledge is what got me into cryptography um and it's yeah it's really cool to see how this has all happened so yeah hopefully i've convinced you that it's a really active space that's for sure um it's a really exciting time to be working in this space and again i think there's a

real like the thing that's really exciting is that it's not all just about you know making things faster right so i think we sort of we got things to a point where they they were faster you know proofs were smaller things were really genuinely practical and so that kind of attracted the attention of people interested in using their knowledge proofs and applications um but i think that you know it's not just like oh here you go take the fast proof and go away you know really like working with with people actually deploying this stuff has in turn really fed back into the theory um again not just making things practical by like counting bits and stuff but also coming up with these new models coming up with things that sort of work in these models you know so the whole idea of universality for example

um you know i i feel has a really natural motivation now whereas before i i felt it wasn't explored quite as much because it wasn't as clear you know why why it was really important whereas now it's like you know do you want to have to do this every time you you know patch your software or something um so i i think it's it's not again just about making things sort of faster and smaller it's really about um really about yeah considering the constraints that people are working with and coming up with solutions you know modeling that um and yeah it's been really exciting um you know i think there's a lot of ways to contribute um you know not just the kind of cryptographic like coming up with the proofs um but really

many other things and i hope i've convinced you of that a little bit in this talk um and yeah thanks a lot for listening happy to take your questions maybe i'll start let's go back to jonathan wool's slide yeah yeah so one of the one of the i guess in the green row on the very far right you have examples of designated verifier starts do you see those do you see applications for those like where do you think those are useful the question was if so for lattices the only constructions we've seen of constant um size snarks are of designated verifier snarks which

basically means that only a specific entity or something can can verify it's not publicly verifiable um i am not the best person to answer that question i i don't personally know of any i mean obviously in something like a public blockchain it's not necessarily the most natural fit um but i am also not that active in that particular space i mean my sense is from you know from at least some of the authors on these papers and then the later work that they've done i feel like it's almost like you know oh we want to build a constant size snark but we can't quite get there but if we make it designated verifier

then it becomes feasible so it's almost just about understanding like the techniques rather than saying oh yeah this is necessarily that like in and of itself very well motivated so are things like a lot easier in that case or is your knowledge it's actually funny that's a great question basically perfect zero knowledge it just comes like for free essentially like often the proof of soundness is this like tortured like many page proof and like a really with like a really complicated definition and like you know in this um other like the algebraic group model which is like the only place we can like actually prove soundness and then the proof of zero knowledge is like three lines it's just like everything's random it's fine so yeah like we almost yeah there's basically no

benefit if you say oh yeah i don't care about zero knowledge it's not like you're just gonna get much better constructions if you can go back to the slider updated updated we'll start in the blockchain do you i guess do you imagine like you could actually update in every block of the chamber what's the cost of like redistributing that srs to everybody yeah so i would not imagine doing that um you know you could have it be like every fixed number of blocks or something like that um and then it would just like take longer to kind of believe the like non-collusion property um but yeah the question of how to get the like

srs is is challenging um and i mean i should say anyway you know like for those of you who follow this space more closely like i don't really think we're going in this direction right because basically people use the techniques in in sonic and stuff to come up with things like halo which don't like require any trusted setup and so that's more the direction things are going rather than like relying on updateability um so that's why i think a lot of the practical details of this haven't been worked out because people have come up with better things um but yeah i guess you could imagine having the reference string be stored somewhere not on chain because it's big um and then anyone given the update proofs could kind of like work out

you know could take that bass thing and like replay everything and get the the new reference string but yeah yeah i don't know if i actually agree that plonk uses exactly this model and is very widely used at least from what i've seen what happens is that you know someone did the first version of the website and then new projects say if they adapt it then they you know add some randomness so it's more of a like maybe not every block but you know certainly every project i mean that's what probably i would advise the project if they wanted to you know use some reference string then they should you know take whatever one aztec is using and add some randomness and maybe get some third party to add some randomness and then you can use it and i

think that's a beautiful property yeah so that that is something you see a lot like bootstrapping off of existing ceremonies basically exactly like i've put here but yeah instead of being happening on the blockchain in a regular way where great will we be in 10 years in terms of uh what what do you think the world will look like i have no idea i mean we're going to answer every decrease 10 to 5. gives you a descending officer i mean yeah it's just like it's all happened it's all happened so fast it's been so insane um i just yeah i literally can't imagine like basically i think you know a lot of the

applications i'm interested in like i think we kind of had we got a lot of mileage out of like the original development of snarks with like really crazy small proofs and really fast verifier runtime but i feel like now we're bumping up against applications where oops like proven runtime matters a lot too and that was kind of the part of the talk that i didn't have time to get into which is like you know situations where approvers are like run in real time right like as i stand there in front of you or like they're run on my phone um and you know with with like constant size snarks and stuff this is like very very very out of the question even with even if we dial it back you know and we use like um starks and stuff like that it's the

prover overhead is like very significant so i kind of hope we find like a nice middle ground basically where like each of these things is is fine um um yeah where the approver run time just doesn't like completely blow up the second we want to make the proof and the in the verify run time like pretty fast um but i i mean we're going in that direction for sure i hope we just continue in that direction because i think right now there are a lot of really cool applications that are just that are attracted to this space because snarks are trendy and cool but like they can't use them at all because the prover runtime is just so

so large so the idea is you know here like so for like private aggregate computations um the idea is that we we still really care about verifier this is actually kind of what i was getting at with like these applications like we really care about verifier runtime because this like central aggregate server has to verify all of the individual proofs that it's given we still really care about the size of the proofs because you know if the if the provers are like on a phone then this is like you know bandwidth costs like that's like data budget for them um but really like preview runtime is is a super big constraint so there's kind of been yeah these just very cool papers um like prio is the best example um and this the idea here is

we can get the prover to be a lot faster if we just change the model for how how things are verified and if we say hey rather than just have one verifier what if we have two verifiers and we say that these verifiers can't collude um and but somehow they're going to like jointly verify these like shares of what the prover creates um and so this is again just like an interesting take like an interesting switch of the model um and that's enabled a lot of really like real applications so namely like exposure notification the ideas like apple and google are not going to collude but now we can like do things on our phones um and then in general like isrg um which is like the non-profit behind the let's

encrypt certificate authority um will basically like run run this as a service so they'll be like i won't collude with you i'll be the other server what for whatever you want to do if you just like pay me to do that um so that's kind of the summary of that part of the talk but yeah just just another way that changing the model allows for like really dramatically different constructions not just like optimizing what we currently have but just like coming up with with something completely different yep do you think it still makes sense to look into um specialized protocols not like general scientific protocols specialized protocols for specific statements or do you think we should be mostly focusing on like optimizing it's still for sure

in my mind like a place for for that um so yeah i mean i i again i think this is kind of what we see happening we've pushed things like super super far in terms of like general computations and now you know we're especially as we work with like more and more practitioners we're starting to see more specialized things crop up but then that in turn does feed back into the theory because maybe these specialized things like you know maybe other people are interested in kind of what you can what you can do there and how when what their constraints are so yeah you