ZK7: Privacy in DeFi: Challenges and Constructions - Guillermo Angeris – Bain Capital Crypto

Transcript

[Music] i want to introduce guillermo to the stage to talk about privacy in defy welcome to the stage guillermo what's this oh there we go all right ah and i've actually never used a pointer before in my life i feel very fancy uh okay cool so uh actually this talk is gonna be quite weird and in fact i suspect i'm gonna offend approximately three groups of people uh while giving it so one is cryptographers i apologize in advance i am not a cryptographer i did statistics and optimization theory um number two is going to be people who actually do uh differential privacy so this talk is going to be a caricature so to speak of differential privacy in some

ways it's going to be very powerful in some ways it's going to be completely useless um so keep that in mind and i guess number three is actually measure theorists so if anyone has anyone taken measure theory here by chance i'm so sorry it's a bad call i wouldn't recommend it but it happens and you know there's only so much you can do so okay with that uh you have you have been warned uh i apologize if you throw tomatoes at me i think someone's gonna have to clean them up so please don't but otherwise you could tell me off stage uh you know cool okay so um okay so what is you know again i've given one warning i will give a second warning but this first one was the most important one um so we're going to talk very high level about what privacy is this is so in kind

of you know we talk about privacy in a very generic sense often we talk about like there exists no privacy or there is just like kind of an infinite amount or like this notion of zero knowledge or things like you know you cannot like it is very difficult or if not impossible for you to like you know find or do a thing that kind of uncovers the actual true action at the bottom um differential privacy and and all these notions are kind of a framework to think about something in the middle so you get to specify the trade-off you want often that comes at some cost potentially economic and in particular you know with with you you've given me your your security budget or this notion of like whatever you know how much privacy you want to leak given and i i can tell you roughly speaking what

you need to do and how much economic costs it will come or how much it will cost you economically to actually receive this privacy um okay so again as i mentioned we're going to talk about like what it is in this very weird sense that most people i suspect here are not used to unless you've done differential privacy and the thing is how do we actually define it in a useful way where you have this notion of a trade-off um the specific thing that i'm going to focus on and the reason why it's going to be potentially you know i might get yelled at is because we're going to focus on really clean definitions uh if you've ever read a differential privacy paper i would say that that's unfortunately not the cleanest thing ever but it's fine it's interesting um okay so the biggest warning here is many

of you probably implicitly know a lot of this stuff right and this talk essentially will work on you you probably know it in fact in a quite different context but you know it implicitly you have this framework in your head when you're thinking and speaking of when something is private but you probably know this framework in more generality than we need for most applications we care about uh and specifically as kind of uh anna mentioned and the title of the talk is is we're talking about defy so okay so let's get to some some definitions hopefully not actually uh it gets vaguely interesting and then afterwards actually gets interesting so we'll start with some disclosure mechanism i that is a totally random thing i just came up with so but here's

the definition it's a function so we're going to call it t which maps your action space so this is this is mathcal a to your some publicly released state space so you know for defy you have to know things about what you're doing right so you have to have some notion of kind of shared or global things that everyone knows so it's public right even though like at the end of the day what you want is you want kind of individual actions to remain private and that's what we're capturing here so t as i've kind of mentioned can at the moment be pretty much anything so one example is a cfm or a constant function market maker it takes a trade and we're going to call it you know an action and

then it just reports the price right in order for you to trade with something you'd better know what the price of the thing you're trading at is otherwise you're going to have a bad time on the other hand you know you could do things like oh maybe you borrow a loan right for the bonus for some amount right and in particular this is your action and then what's released to you is roughly speaking perhaps the the interest rate of that loan cool so okay that's that's the one of the definitions so we have this protocol it has some disclosure mechanism which all it does is it takes an action that someone has done and it then reports kind of the post-state public information so alice you know our protagonist of every story uh will take some action right and in particular what are we saying well that will that action

you know goes to some smart contract and the smart contract now reveals some public information which is given by s and eve our ever loved adversary her point is to reconstruct that action a given in the underlying state s right this is just the normal classical game we all love about trying to you know screw privacy so the biggest question of course is what what can we learn right like what can eve learn about you know the action given the publicly released data so uh big warning another warning as well is we're not going to talk about history actually we're going to see how to directly encode history and kind of this framework without actually explicitly requiring it

and we're certainly not talking about anonymity so anonymity can be achieved without requiring kind of you know you can you can have fully public state and have people who interact with it be completely anonymous and i will not talk about this notion at all when i talk about privacy i mean specifically reconstructing the action that was taken at some point in time this is a really important distinction because you know surely you can do things like correlate behavior and things like that so but i'm not touching that at all this is just about reconstructing actions okay so what does eve do of course you know here's here's a very intuitive notion is eve looks at the pre-image of you know this disclosure mechanism on the publicly released data right in some sense

anything that kind of has been done right and gets mapped to a public state right is is kind you know you can only equivocate between those items okay so first obvious fact is that the pre-image on s sorry i wrote t inverse here it really does mean pre-image if your use of topology or whatever um is not empty why because it contains the true action that was actually performed okay and here's the second intuitive notion just wait one second but the larger this set is in some sense the harder finding the underlying action actually becomes right i mean this is kind of obvious right like i have a bunch of things that map to one thing if i go backwards i try to like reconstruct what happened i'm the larger

that set is the more things i can like have i could have done right this is in some sense very similar than spirit to the notion of an anonymity set perhaps and things like that but this is this is a much more generic notion here we're talking about you know kind of very general and somewhat distinct uh mechanisms okay and we're gonna quantify what it means by you know to say like something is large or small so here's the unfortunate sad news in defy unfortunately the set is very very small in fact it is so small that it is exactly one element right so for example in constant function market makers you can show at

the set and this is not obvious not immediately obvious is uh a single element uh the the reason why it involves some solution to some nonlinear differential equations and showing that that has a unique solution but that's besides the point um but the question is of course that you know i ask you and perhaps i might be asked you know is what can we do in the case in these you know so to speak worst case outcomes so before we get there finally there is one last definition maybe i think i think it's less definition um there is some notion of the size right we've talked about oh these sides have been large and small and that's very vague and no one actually cares what are we talking about when we say uh size so here is where

measure the measure theorist the single person sorry here is where you might yell at me but i'm going to call mu a measure but in fact it will not be a measure at all it will be it will there will be exactly one property it has and that is if a is a subset of b then the measure of a had better be smaller than the measure of b that's it sorry i know i know you're shaking your head i'm sorry i didn't mean it i mean i i do mean it like a little bit but not too much um so yeah apologies again so here are a set of things you know if you don't care about privacy at all here's a perfectly reasonable measure to talk about it's uh the silly measure of mu of a is zero for any a congratulations you

have achieved nothing at all with doing this so let's talk about something slightly more interesting which is the uniform entropy right which is the logarithm of the size of the set right roughly speaking that's how many bits you need how many bits of additional information you need in order to like pick out a single element from the set assuming you uniformly sample an element from a okay probability is a perfectly reasonable notion of measure and this is what one might actually call a measure but you know it's actually not as interesting and you could imagine a number of other possibilities right there's other entropic things that we can do which are for example not necessarily uniform over the entropy or the entropy is also the uniform over the distribution that we're talking about okay so now we can talk about size and

privacy very cleanly it's super simple and what is it well we're going to talk about we're going to say that the privacy of some you know disclosed data s is going to be what it's going to be the measure of the pre-image of the given set right as we kind of mentioned before intuitively the larger the set is of course it makes sense that you're going to have more privacy here is a perfectly reasonable definition you've given me a measure of privacy and i'm giving you a number which says here's how how private this specific you know disclosed state is okay and now we can talk about the you know a privacy mechanism it's what's the privacy of a mechanism well it's the smallest possible you know it's just if you take the femum over all states if you take the smallest

possible privacy over all possible resulting states that if that thing is large right by definition if that set is large then there exists no publicly disclosed data that will ever yield kind of uh you know easily distinguishable actions right so does that make sense so far i think okay cool so now let's get to the interesting stuff uh we've given an extremely general framework right it's not even clear you can say anything interesting about it at the moment it's like okay fine you gave me a measure mu and some stupid thing all right so let's do something with it okay so what does alice need going back to our original protagonist is she's to make sure that the pre-image of this

global state of this shared or public state is large for a given action right so from before how do we you know what does that mean well we're going to measure the size of the set using mu right in particular if that thing is large then we're great unfortunately for us that thing is not large for almost every kind of defy application that we can think of unless you're careful and we'll see what careful means so the worst case is that your you know your pre-image is singleton right in which case the smallest possible thing that happens is congratulations it's your measure of a single element and this is common in many different applications so can we improve on this idea okay so first

kind of simple notion is hey what happens if we can batch actions i here i'm going to be completely and perfectly abstract about what batching means so we have some notion of a batching operator it doesn't need to be associative it doesn't even really need to be anything i am simply assuming there's some canonical ordering when i write that thing right but the point is i have a you know a function right o plus which takes a bunch of actions and then just gives you one output action at the end of the day so the protocol you know intuitively what it's doing is it's taking n people's actions or transactions adding them all together and then only publicly releasing information on the batched action right so that means that recovering any

individual action is probably pretty damn hard why why is it obvious well you know here is the here's the kicker right if you have a zero action so if you have an action such that it actually doesn't do anything to the set itself then there are many many possible ways of getting the same batched action right you can imagine someone does 0 alice does a bar or you can imagine alice is a bar or 0 and then someone else's a bar or any number of possible combinations depending on the structure of your aggregation operator okay so we're going to talk about the set of possibilities for an individual player we're going to call that p so p of a bar essentially is all of the set of outputs which are consistent with the released with the known action a bar and now we can say something very

interesting if you know if the set of possibilities for any batch to action is large if it's true for every single batch action then necessarily we have privacy under the measure mu right so here's the proof it's kind of silly but so we have a list of actions through a n alice performs some action so we're going to call alice player i the protocol aggregates that action into a bar and reveals some public state then we're going to sorry i'll lie to you about the last definition this is the last definition i'm actually pretty damn sure of it um the so we're going to define the set of possibilities over a set which is just the union of the individual possibilities for every element of the set right so

that kind of means like if we have a number of consistent actions right for an individually batched thing uh the actu the set of possible actions over the kind of the set of all possible things is just the union of the individual actions the union of the possibilities of the individual actions um okay so what is the possible set of actions that alice could have taken well it's p of you know the pre-image of s and so we have the kind of obvious lower bound that the measure of p of t inverse of s is always going to be greater than or equal to the measure of the possibilities of any individual action and this bound is tight in exactly one spot and that is when uh t inverse of s is a singleton

so from there we can prove a slightly you know simpler and equal or slightly more complicated inequality by minimizing first over the actions on the right uh so on the right-hand side and then minimizing over the set of possible states on the left-hand side actually you could even derive a strictly better inequality but the point is right this is kind of a fancy way of writing it does not matter kind of what the how bad your mechanism for release is if you're batching right the worst anyone could ever hope to do to you uh alice or alice's of the world uh is pic is essentially picking the worst possible action and if that thing is large for any action then necessarily that in femum on the right hand side is also large so in some sense you have privacy independent of how bad or shitty

your publicly disclosed public disclosure mechanism actually is okay so what's the conclusion of this this is pretty simple batching never hurts well it might hurt but it only does not hurt privacy um with many players to somewhat reasonable assumptions right then batching in fact is actually quite beneficial right but here is here are two problems that we kind of we wrote some very nice little symbols but uh they're not obvious is a it means that you have to define a patching operator and in a lot of protocols it is really not obvious how to define a batching operator in any way that actually preserves the properties you might want and even if you did you have the second problem b which is that uh the ux for users actually suffers so in the case of

for example so here's a particular case of batching is if you say if you're trying to trade with a decentralized exchange one simple way of doing it is you simply add everyone's trades together and you pay out uh kind of you know you you have delta one delta two delta three which are you know how much money people are trading for usc to eth right and then you simply pay out so you pass this through one mechanism you trade this complete large trade and afterwards you spread the rewards out or the payoffs back to individual players right in proportion to how much they paid it so that's a pretty reasonable mechanism right but that's really bad for people like arbitrage and traders which you want to actually keep your protocol afloat because now it means that they have to

think about the behavior of other players right which they do not know until it's until the information is released in order to actually perform you know any sort of optimal action okay so here's another possibility it's actually adding randomness this is kind of the classic one differential privacy so here's where we're going to get to it has one benefit which is you don't actually need anyone else you don't need anyone else to ensure that you have kind of an anonymity set it also allows the user to potentially have a knob to control a privacy trade-off right more randomness you add perhaps the worse it's going to get for the user but the less randomness you add right it's better for the user but you have less anonymity and so in some sense it lets you set a

privacy budget and so to say i want you know i'm willing to pay this much for anonymity at most as much and it's like all right here here is uh how much you expect to to save in terms of you know bits of entropy for example if you're using uh that measure of course as we all know uh or maybe most of us know uh it is really hard to achieve kind of private randomness in practice this is like another thing that's pretty much not obvious okay so last but not least so we'll write f of w so it maps the action space of the action space and w is just randomly uniformly sampled it's a little w uniformly sampled from the big space uh l is going to perform some action and then the mechanism is going to map that action to another action under this

noise model so i don't really care what f is in this case you're going to have to tell me what that is but the point is the state that's released is this kind of perturbed state right it's a state that's not actually exactly what alice wanted to do it's something else that gets performed uh and the point is at the end of the day this is you know s is now kind of perturbed under t and under f and so to succeed and this is where things are going to become really useful is eve has to find an action from this kind of inverse image of this perturb function and also the you know this like this pre-image of s but she does not know w right she doesn't know the randomness that's been picked for the user okay so uh this is me the last slide i

think of uh math or second last slide of math is the uniformity over w is really really useful and the reason you can extend this to non-uniform but here is why essentially because it's uniform eve pretty much has to decide between kind of the union of all possible actions under both the map right that you have from the action to the state and also under this kind of noise function right because it's been uniformly sampled you kind of really can't tell apart we could make this very rigorous but right now be a little bit hand wavy you cannot tell apart kind of between these w's right unless you have some prior on what else is going to do and that can be encoded directly in the measure so given that alice performed some action a and the global information s was

released then we have the following easy bound which again is tight in the case that t t inverse or the pre-image of t of t is a singleton okay and finally we can kind of refine that inequality and say something a little bit more interesting that the left thing that we have here this unfortunately complicated looking expression is actually really simple it's just the privacy of your protocol right is bounded from below by kind of this inf supremum game uh of in fact just how large the pre-image of f is under w um so there's an unfortunate thing about this uh model which is that the adversarial power is actually not exactly obvious right it depends on exactly like how you define mu and what you want to prove

about mu except in one very special case which uh you know i started to talk with where me was entropy you get very strong guarantees and that case is of course differential privacy okay so anyways of inclusion and if there's any one thing that you get out of the talk that's not you know a bunch of unions and f inverses and which crap like that is there is a simple framework that you can reason about privacy right this is kind of how people think about privacy very heuristically without actually needing all the complicated parts of you know thinking about mutual information and all the stuff it does include a number of important cases right so if you kind of take a large step back you have this interesting very simple framework where she can reason kind of how bad is it for me to do x and the last thing is that at

the end of the day really the one thing that actually ends up mattering is just how large are your pre images right in other words how large are in mini sets how large is your confusion set any number of these things the point is that is the cleanest and simplest representation i think about privacy and unfortunately uh papers don't always make that obvious so with that thank you so much all right is this all right all right questions thanks for the talk uh quick question batching is there any fairness assumption for the actorhood or the part of the protocol that dispatching so there's the only fairness assumption there would be would be under the choice

of w if you do this randomness everything else is kind of independent of the protocol right so the assumption is that the protocol itself doesn't release like you know i'm kind of throwing this under like a large set of things but the point is the protocol does not release global state okay right if the vertical is global state you're kind of screwed and you're dead on arrival thank you any other questions uh the measure theory measure theorist no everything's good with me but um actually my mother was a mother that a measure theorist so if oh you had gone into the weeds it might have been a problem no i'm glad i'm glad i got the effort yeah yeah no it's good it's all good um i had a very simple question actually the second to last slide maybe where

you're talking about whether uh when you can actually prove these mounds you said something about when you have an entropy that's when you can is that an if and only if tight that is well it's it's it's tight it depends what you mean by tight and you have to be really careful you know when you specify tightness but but the answer is generally yes right it involves so the assumption kind of goes something like the following how do you prove that something is statistically hard you can prove that you require a number of bits in order to be able to reconstruct it right this is like thanos inequality or like lecom's inequality or the all these like learning tools that are really complicated and no one likes to talk about them so the answer is if only the information if the only information that's released is

kind of included within that like mutual information term and the answer is infinitely if right in fact there exists no the the answer is there exists no measurable function mapping kind of the state s back to the action a which can which succeeds with prop you know it's like this measurable question is a random variable which succeeds with the probability that's non-negligible and then like the you know the size of the problem that you're talking about okay and um does that apply to any kind of entropy here are you specifically doing shannon entropy or is it any other in this case it's specifically the mutual information although you can use rainy entropy you can you can there's like any number of bounds that you can use so actually the kind of two main ones are total variation right which is like weird notion of entropy

that's not really entropy but you can no if you're told a variation between two distributions is really small you can't tell them apart so that's one way and the other way is if you're telling a bunch of things for one big set right so you the way you think about it is you have a thing that's drawn from a set roughly uniformly randomly you have a thing that like you know as a channel so it's y right and it's like you know it's what what gets publicly released and then you have kind of an estimator for x right then what you care about is a mutual information between x and the estimator or in fact actually the lower bound our upper bound on that is the mutual information between x and the release information and that lets you say something extremely clean about the existence of

not just computable but in fact measurable functions which can reconstruct what the true thing was at the beginning okay so thanks yes are there any last questions any other questions on the stream oh oh in the stream wait in the street i don't know oh tell us i didn't even know that was possible yeah oh yeah it's 2022. so the question in the stream is can you give any examples of usage of randomness-based differential privacy in d5 well is it is it bad if i show a paper that we've written uh is that like a cool thing to do so the answer is

unfortunately i think at the moment no as far as i know that anyone's actually implemented it but there are some constructions that you can't implement they have absolutely garbage constants so maybe don't read it but the point is you can do it you probably shouldn't do it or if you do do it uh be extremely careful and actually work out the constants correctly which we did not do um so unfortunately the answer is no uh but there are some notions like batching for example penumbra that are actually done and we suspect probably give you a good amount of privacy under basic assumptions of your peers who are working with you okay cool any last questions here

all right i think that wraps up thank you so much guillermo for the talk [Applause]