zkStudyClub: Differential Privacy in Constant Function Market Makers (T Chitra, A Evans, G. Angeris)

Transcript

cool so welcome to this edition of the zk study club um today we are going to be hearing from taroun who is the sometimes co-host of the zq podcast and he's going to be talking about the differential privacy and constant function market makers and the two other co-authors alex and guillermo are here and will hopefully be jumping in with some ideas and answering questions in the chat all right so tyrone do you want to take it away yeah cool sounds good so uh yeah this talk is going to be about um differential privacy which you know is a a weaker form of privacy um than you know one normally ha looks

at uh in the zk world um but it you know does provide some level of uh some guarantees for users uh that they won't get front run or the probability of them getting front run is somewhat lower um and you know we'll go through kind of the background on how these things are defined uh also what differential privacy is and then kind of give the rough techniques used um the implementation of this actually is not shouldn't be too terrible on a blockchain with verifiable randomness um but yeah well let's start with some

background all right so before uh kind of jumping into kind of the definitions i think sometimes it's a good idea to look at history um so you know let's just start at the very basics uh so there's a lot of scenarios where uh you know we one really wants to trade assets uh which you know sort of as a basic uh uh goal uh and the traditional way of doing this is you know there are multiple parties uh some parties uh say they want to buy a certain price some parties say they want to sell a certain price buyers sort of post maximum prices that

they're willing to buy for sellers post minimum prices they're willing to sell at and trades occur when the max is greater than the min pretty simple but one interesting thing is if you actually try to analyze this from the lens of wanting to decentralize it it's actually a lot harder than you might think because a lot of the operations are non-atomic um and you end up trusting a third party to keep track of the sort of outstanding buys and cells um moreover this sort of has this linear space requirement so you need to if there are n orders uh you need to store o event space something over within space

um and uh that linear update is is kind of chaotic on the blockchain in because in the worst case scenario you know people will front run you and it'll be uh quite unstable and in fact um you know in solana this week there was a liveness fault for seven hours and at the end of the liveness fault um there was this kind of massive set of liquidations that occurred because they were do using an order book on chain and order books are not very good under network partitions because market makers have to go adjust their quotes but if there's network partitions for too long they can't actually interact with the blockchain anymore um so this linear space thing actually

for blockchains is quite uh bad and we've seen many examples that fail not just lana ether delta in the past other other things like that um one other thing is uh order books are kind of annoying in the sense that uh prices might update kind of slowly if the buyers are buying very small size relative to what the sellers are selling um and it can it can kind of the dynamics of that can can be unfavorable in certain cases and then you also have to add subsidies for market makers so one question is can you automate the process of building an order book and having sort of people quoting prices um

and so yes they're you know for the last 30 years there has been sort of study on automated market makers and the idea is you can't get sort of a perfect automated market maker uh there's sort of some natural adverse selection reasons for why not uh but you try to get one that meets some certain criteria and desired data that you're looking for such as bounded loss like the most amount of loss that a liquidity provider will take is bounded in some sense in some parameters liquidity sensitivity the idea that for a fixed size trade um prices move less when there's more liquidity provided and small storage requirements so this gets back to this linear space piece which you know in production we have

just observed that very few order book like traditional order book style uh mechanisms uh seem to ever be popular and or survive on blockchains without you know massive subsidies like we see on solano but automated market makers are a very old idea um actually starts in the statistical literature in the 1970s with savage who actually kind of invented the logarithmic market scoring rule he just called it something different but it was really popularized by hanson robin henson too um and there's sort of a simple idea which is you have a formula that's a function of

liquidity deposited so that's quantities of different assets that are deposited and liquidity providers pull these assets into a contract and the contract uh price of the asset with this deterministic formula and if the price is too low relative to an external market an agent can purchase from the contract and sell externally if the price is too high the agent can buy externally and sell to this contract and um you know there are a bunch of different security guarantees depending on the formula but the idea is that the amount of liquidity the quantity of liquidity deposited implicitly

uh implies a price um and the relative proportion of the different assets sort of gives you an idea of what that price is so if there's less of asset a than sub b asset a is more scarce and so hence its price should be higher than that acid be so the simplest example is a fixed price at all reserve amounts now that's not necessarily bad uh but it is sort of you know you're you're publicly offering a fixed price uh and if there's any external market that's a different price um you know they'll be arbitraging and the reserve will be left with the worst asset so one thing to remember in these

automated marketing makers one of the reasons you care about this bounded lost property is let's suppose i have an automated market maker uh with ethereum and usd some usd stablecoin sorry and you know the ethereum's price is going up arbor treasurers are noticing the price is lower on the automated market maker and higher externally so they buy east from the automated market maker and sell it externally but they buy east by selling usd to the market makers so they're kind of giving the crappier asset to the automated market maker and so you need to add fees to kind of balance that effective which is why the sort of fixed price

thing can oftentimes be bad unless it's something that's supposed to really be a fixed price like two stable coins um another example uh is the ratio of two assets um the ratio of the quantities so like let's say there's a hundred dollars and one ethereum then the ratio says the price of ethereum's hundred dollars um and that captures the scarcity property correctly and this this is unison um cool so now we're ready to actually talk about the formal definition of these objects uh in in um sort of more generality um so a constant function market maker

is a contract that has n assets each with reserves ri so the reserves are the quantity of assets liquidity deposited liquidity providers so people who want to provide liquidity and have the potential to earn fees but really they're they're sort of providing a service to the contract that facilitates trading um can supply these reserves and traders are allowed to add or remove coins provided that they preserve uh an invariant um called the trading function phi and

phi is without loss of generality concave and non-increasing um you might say hey concave x y equals k is not concave however you can always do a monotonic transformation by taking the square root uh and you get the same curve so slight technical detail that but for without you can sort of think of these things as concave and not increasing um the super level sets of this function determine sort of admissible trades and we'll we'll look at some pictures in a second um and you know the most popular is insult so you know just to give uh somewhat practical look at these assets

or these uh this mechanism um you know it's the most used decentralized application period uh there's like three billion dollars a day traded on these um you get a second most of course lending but uh you know it is clearly the thing that people want to use um in in sort of decentralized land it is the only application i would say that has truly kind of like hit mass adoption okay so let's think about this trading set just in pictures so you get some intuition so this is the uniform curve so x you know r a times rb equals a constant

that is a parabola that you see drawn here hyperbola really and you can see the trading set above and so the trading set the super level set uh is convex um and the boundary any cur any point on the boundary the darker shaded points are uh viable trades under no arbitrage um and one thing you know i think that we realized when we started analyzing these things is that it's actually much easier to analyze the super level sets than just the boundary um and so it turns out this still these trades are still feasible it's just that if you were a rational trader and you made a trade that

moved the state of the system to an interior point um you would immediately lose money under no arbitrage so no one would actually use them but it turns out the geometry of these sets uh is kind of very crucial to ensuring that these systems can't be manipulated in some way so yeah that's sort of the main object you might say ah who cares why do we need convexity well let's just look at it visually suppose i you know take a bite out of the trading set uh now i get two prices for with so remember it's sort of the the slope uh

of this uh these lines or the tangent line is rough is the price but now i have two uh sort of different trades at different prices and you there's kind of no difference uh between this curve and the one that fills in the hole and so basically if if there is a hole like this you can kind of show under no arbitrage like people will just basically fit you'll effectively have constant trading while you're inside the missing piece because of this kind of property that you have multiple uh reserve values like you the same price um

i will just i saw there are some questions maybe uh or sorry caramel was giving some context actually okay cool okay great uh thanks guillermo for answering uh questions um okay so you know we talked about this trading set uh that has the shape and it has sort of a boundary um there's sort of this natural intuition that somehow the curvature how flat or uh bent the the the shape is controls price impact so um before we go into the definitions

let's just take the empirical data on this so curve um is a uh automated market maker uh probably second most popular after uniform and it's just a linear combination of the constant sum which is the fixed price and the uh unisop curve curve has this property that near a certain point it's extremely flat and at that when it's very flat that basically means you can trade arbitrarily large a very large size and cause very little price impact so in some sense the flatter you are the

larger the trade trade you can make without causing more than a price change of a certain amount um and why this is important is for assets that tend to be the same price so trading two stable coins ufcc against usdt you want you you don't want people to be able to cause the price to go up easily because it effectively allows makes it a bad oracle and it's sort of much more manipulable so there's a sense in which the shape of these uh curves should somehow reflect the expected trading behavior of the assets as stochastic processes so the question is can we formalize so you might naturally say hey i took

calculus don't you just take the hessian don't you just take the gradient don't take just take the eigenvalues of the hessian then you get sort of a notion of curvature that is true um it turns out to be a little more nuanced uh in these constant function market makers because when we have this constant constraint we have an implicit function okay so what we do is we define a function called the price impact function the price impact function comes from these sort of implied constraints and the price impact function is defined as the ratio of the derivative of the trading function um and of of the two partial derivatives of the

trading function and the idea is that given a trade of size delta i compute uh you know the the change to the trading function value and then i look at the gradients in each direction so we're just pretending we're only going to talk about two dimensions like trading one asset for another in this talk you can generalize this to n assets it does get a lot more complicated um so for simplicity we'll stick to the two asset case so you know remember how we how in in the previous picture in the picture here the price implied is the slope of this line right and the slope of this line is

actually you know the ratio of a derivative in one direction to the ratio of a derivative in another direction because this function is defined by the constraint psi of x y equals constant and so this is encoding the exact same thing except for arbitrary trading functions um you can intuitively from an economic standpoint think of g of delta as the price impact after a trade of size delta so imagine we're initially at a price a dollar g of delta is equal to 20 cents then that sort of says when i make a trade a size 100 that says that you know

the price is now a dollar twenty um and the the notion of curvature that we use here is actually uh basically bounds on changes uh of the function that are sort of lipschitz style bound so an upper bound and a lower bound the upper bound is called mute stability that basically says uh basically given the traitor size delta um you get at most mu times delta price impact and we say g's cap a liquid if uh you have a lower bound um and the lower bound

uh sort of represents this idea that when you make a trade you have to change the price at least a certain amount and so in the constant sum case that we were talking about earlier uh mu and cap are zero because it's a constant price there's no price impact i can trade whatever size until the reserves are exhausted um and the price doesn't change but for something like uniswap it actually has quite a large kappa so even tiny trades do have some price impact and this is important in privacy uh as we'll sort of see because you you can kind of infer what the trades are based on the price changes and that's that's where uh this gets more complicated oh well

uh i think i messed up this slide but basically the main things i was going to mention here is uh this this curvature you know uh can be used to sort of prove properties of what happens when uh one of these constant function market makers is the dominant market and it turns out that some an analog of sort of a condition number from numerical analysis so like the ratio of the biggest to smallest uh absolute values of eigenvalues that hedges control sort of how synchronized these markets stay if they're two constant function market makers and arbitragers are trading between them okay now we can finally get to privacy so one question is can we just achieve

privacy in cfms uh by just posting uh sort of zk commitments of reserves and basically evaluating the trading function invariant uh privately uh and under a relatively simple threat model you can sort of show that that's not true an adversary only needs to know the reserves at one time and then the sequence of prices to infer all of the trade sizes um this result sort of is an impossible sort of impossibility result style thing that just basically says you can't just take unislop throw it in zk and hope that you have made it private because you're

still leaking information because prices have to be public no one is going to sort of use your automated market maker if it can't quote public prices but those public prices tell you a lot about the trade sizes so there's only really two ways of avoiding this um the first is batching so that's take 10 transactions treat them as one transaction execute and then give everyone the same price uh the second is randomizing prices adding noise to people's orders or trade sizes or adding noise to their prices uh and basically like in enough noise that an adversary can't really predict the price more than sort of some notion of

entropy of the noise batching is not very great uh ux wise unless all the trades are kind of small and randomizing prices is also not great because you're changing the price impact uh of the of the function but okay if we assume that these are the only two things we can do how how do we actually achieve some some notion of privacy uh well just as a simple kind of straw man example suppose we just added iiid gaussian noise to all the prices that wouldn't work very well because i could just basically try to learn what

your noise parameters are denoise the prices and then invert via kind of the previous model um and so that leads us to the case of hey actually we need to spend some time thinking about what types of adversaries uh are here and and i think this gets to uh to aleister's question somewhat um do you want to do you want to say some of these questions i don't know if you want to mention them sure yeah um sorry i'm not sure which one's guillermo i'm not sure which one is going to answer so i i'm just wondering what the model is

here who's keeping private from whom so if you're talking about ck proof you would assume that someone knows something and it's just the chain that's it's being hidden from so say we have a centralized entity who's doing all the trades yeah that's a good point um yeah the idea is the the model here is is strictly the the things an adversary knows and we'll kind of get to this in a second are only that a and ignoring they might not know they might not be a validator they might not have mental data they might not have any address data the only things we assume the adversary knows are the reserve values um and the prices and they can query

whether a trade is valid or not so uh they can basically learn the geometry of that trading set that but only locally they can't learn the whole thing at once in some ways and they know the trading function so what i was asking it was kind of the other question which is the the positive question someone has to know this in order to make transactions um yes so who who who are you assuming does know this or are we just assuming we're going to implement it somehow yeah yeah yeah yeah i assume it gets it gets implemented somehow i mean right now right if we think about how any v auctions work

uh basically only a small subset of validators even see the uh see these trades before they get executed so there is some notion of like a small group of validators of the layer one kind of know the trades um but yeah that's a good point uh it there is someone who has to know and that comes down to how uh the layer one actually executes transactions yeah i can hop in for like one second so essentially the the idea is that you can in in our case we don't even assume that anyone actually knows the information so like you could imagine that if even if you could create a system that had perfect privacy around the information right around anyone not knowing the

reserve amounts you're still fine um or you're still sorry not fine that's the impossibility result is that you even if like you know the person who knew the reserve amounts was super trusted and everything right using only just the information from the prices uh you can already invert the like you can already like uh infer the actual reserve amounts that's the impossibility result so even in the very strong case where you know this whole setup is like super trusted and super secure you're still screwed does that make sense right so sort of first we're trying to secure this in the case where we actually would have a trusted entity that's doing all the trades and then

maybe once you've gotten that you you'd think about how to do this in a more decentralized way right you can you can use that as your as your like best possible model if you'd like um but but the point is the result kind of holds independent of the implementation um there was i don't know if the questions fully answered there but there was another question just above al's and i don't know if we should also ask this this is alfonso's question oh sorry uh can't you infer about a trade just by looking at the change in liquidity pool sizes even if they're right right yes so this is the part i was saying where they

were part of the reason we wrote the first paper was there were a lot of like people writing or writing both code and white papers saying that they were basically going to make uniswap uh run in sgx or have a zk commitment where they hide the reserves so the reserve prices would have been hidden so that's why in our adversarial model we don't assume that the uh the adversary can know the reserves publicly so there's somehow only commitments of them posted um and so that was the part that even if that's true you can still figure out the reserves uh from the prices effectively um

cool uh so today um shall i ask my question as well um so my question was um suppose um you have a perfect anonymity network and all of the addresses of the participants private um we basically know how to do that um and so you only know the um the amounts of trades how bad is that how much in practice how much information does that give you that would allow you to infer stuff about the the actual participants it's not even necessary that you want to

infer things about the participant it's that you confront around them and you can like basically you can basically force like for instance let's suppose there's a trade that's about to cause a big liquidation on another protocol uh and you can basically ensure that that trade gets executed first cause of the liquidation and the price goes back up right so that type of and that's the type of stuff we see in practice i people don't care about the identities that much they but they do care about kind of causing harm in other ways okay can also be quite bad for privacy directly right if i know for instance that a user has transferred 100 bucks from their coinbase account and then i know there's also a trade for some asset for 100 then

i know a lot of information about that user and i can correlate it potentially to a real world identity as well depending so it depends on the model of what external information the attacker has uh at their disposal yeah yeah and we'll when we get to differential privacy definition we'll we'll talk a little about i'll try to give some um inclination as to why this that definition is natural uh because it's sort of it's the best you can do if you assume that someone can join arbitrary data against your um your existing data set cool so any mechanism we choose here the impossibility result says the phone there's always a trade-off between price

impact so you know the user says they want to do a trade of size five which in the not fully non-private version might only cause 20 cents of price impact uh but you know the impossibility result says you have to add some noise or batch so that will change that versus privacy sort of the precision in in the sense of the number of bits that an adversary and apologies this is the super villain emoji in latex i it does not look like the other super villain emoji uh normally uh but i've to save space i wanted to use the emoji uh that an adversary can estimate the trade

size up to so batching so there's kind of two extremes yeah exactly i was hoping it would look like that but unfortunately it did not uh but batching uh is uh good for privacy because if i batch all these trades you can't figure out which one is which and you only see one posted transaction in some sense uh but it's terrible for price impact and so the simplest worst case example is let's suppose we have t trades where t minus one trades are of size one and one trade is of size t um if the cfm is kappa liquid this gives a

lower bound of omega of t so like uh in price impact um and in some sense this means that the batched transaction so when i made the trade of size one i only had o of one price impact but when i get batch i actually have of t price impact now where t is the batch size um which is way worse right that's that's just like from a from a economic fairness standpoint kind of sucks um on the other hand normal cfm evaluation terrible for privacy good for price impact you everyone knows what price impact is public and computable efficiently

so our goal is actually to think about this trade-off surface between how much price impact we cause versus how many bits of information adversary can extract uh and try to parametrize that space in between these two extremes between the batch case which is terrible price impact but provides privacy versus the raw case that isn't so now we get to the adversarial model so we sort of assume the simple but general model uh which has the following uh where the adversary has the following state and queries so the state they have is at some point in time maybe it's just like the creation of the pool

they know the reserves um and so there's sort of a sense in which it's very hard to construct a cfm where you completely hide the reserve values at all time because pool creation somehow has to leak some information about that um but we assume that that that they can figure out exactly one time they don't need to know it any other time um the uh other thing they know is the marginal price so they can compute the marginal price of cfm at all its current reserves and remember the marginal price is a derivative so it's taking that trading set on the boundary and we're computing the gradient locally at whatever point we're at

is valid uh basically says is a boolean classifier that says are we in the trading set or not okay so this is how much so the idea is that the adversary can locally search the geometry of that set via these queries and tries to try to infer the exact path that was taken and note that we do not explicitly assume they know any identifying information of any form could be hidden by ckps could be hidden in in a trusted manner whatever so so just to clarify they know whether it's instantaneously valid at the current price is that right yes

okay yeah um so let's kind of consider uh adaptive adversaries so adversaries who they see some subsequence or trades and they try to adapt what their guess of where the whale trade is so the simplest example again gets back to this this bad batching example um which is uh you know this the trade of size t in the batch is look for simplicity called that the whale that's the whale trade making a big trade and all the trades with size one or the minnows or whatever i don't know random other people um so the adversary their goal is to front run the whale so they want to push the

price up in front of the whale sell back right after um which is also called a sandwich attack except this would be sort of a slightly more generalized one that'd be probabilistic uh and so the how would an adversary do this well from a sort of learning theory uh standpoint one way of viewing this is assume the adversary can construct t boolean functions which take the prices so that's what the zero to infinity in the domain is uh so they take the first i prices and returns a boolean of whether the whale is in the first i trades or not um

without going into any details on classical school learning theory uh you can show that if the adversary has any edge over a coin flip um you can use boosting style methods to improve the learner to the point that it has very high probability uh just because is the vector yes yes yes assume they're all in one direction sorry yes that's a very good point you want to say we should say that out loud so maybe or henry i don't know henry the question is what the the vector one up to t and then one is that that's a

vector of uh you know m different trades that are all specified just by you know here's what happens on input whatever or the first input yeah sorry yes yes yes yes uh so very good point so assuming we're assuming two assets uh and trade when the trade is positive it's asset a for b and when the trade is negative it's b for a uh and they're assumed to be valid so they all are in the trading set so these are all valid trades that can be made um but this worst case is all trades in the same direction so that's actually a very good point um and you're just trying to identify the whale um

yeah so so classical learning theory uh kind of says hey look if if an adversary can do a little better than the coin flip they can actually do these ensemble methods and like you know if you've ever heard of gradient boosted trees the theory of why they work is this type of stuff uh and so this basically says oh an adaptive yeah for some reason cryptography everyone says adaptive adversary and then you know the private machine learning world evidence is online learning adversary but i'm using them interchangeably because as far as i know they're roughly equivalent but this is this is sort of uh this is kind of what uh these are kind of the results from more like the

private machine learning world um but the idea is um you know control of how price noise affects the probability of these classifiers being correct impacts the adversary's success so for instance randomly permuting the trades decreases gamma if the adversary has no ability to predict the random permutation this is where the verifiable random function and non-predictability guarantees are extremely important the problem is online learning is extremely intuitive right that description of this adversary who's like

kind of learning these classifiers and then figuring out uh has some probability of the classifiers being correct extremely intuitive kind of easy uh but it's extremely hard from an analysis standpoint so it's extremely high dimensional and there's not much extra structure you can really exploit moreover the set of classifiers you choose is dependent on the instance right here i had to say the attack is there is a whale trade that needs we want to identify and we want to make boolean classes identify that and then talk about the probability of identification but the problem is there might be other types of attacks

and so if you kind of study things like you know minor objective value in general it you know you would have to basically enumerate all of those scenarios and that sucks um however and i think this is one of the greatest results in the last two years and i think the pandemic maybe hid that this kind of research happened but there's kind of this you know i call pretty groundbreaking work that shows that like the set of algorithms that are online learnable is also the same as the set of algorithms that can be made differently private um and that sort of says this sort of worst case bound over all bullying

classifiers is somehow captured by this notion of differential privacy which we'll talk about next um and this says that you know we can kind of use this to our advantage to say hey if we can construct a differentially private version of a cfm uh then we kind of get these online learning adversary guarantees and that's how i got to this result but it you know it kind of came backwards because i was trying for a long time to solve it using all my learning methods and it was just not going anywhere cool so what is differential privacy so now we're kind of at the at the

point of of thinking about this so privacy uh comes in many shapes and sizes so of course this is the zk study club so zero knowledge proofs computational proofs cheaply verified very hard to do on learning algorithms uh you know i obviously people in this audience are much better experts than me of knowing the exact complexity of that right now but uh i still haven't seen you know like a a learning algorithm kind of like one that would be trying to learn these trades be able to to be implemented um

but you know of course has this moore's law happening so maybe that will one day will be sufficient but for these kind of learning things i think it's actually still a little tricky uh homework encryption too hard heart in a lot of ways heart far from production uh too many weird algebraic properties need to be hold et cetera or whatever and then now we get to differentiate so differential priority is the weakest notion of all three of these but it's also the most used um so what the intuitive idea is you add a bunch of noise to your data such that [Music]

such that [Music] i can still compute an average correctly but i can't identify any single user so a simple example let's take the heights of people in whatever city you live in and let's say we want to compute the average height um and the uh you know let's say there's one person who's seven feet tall which seems anomalously high um and they you know but you want to compute the average and let's say the average is actually like five foot 11.

uh the person who has seven the seven foot average if if they have removed them versus add them the average might change from five to eleven to five foot six um and now i can identify that they were removed from the data set right so one way of preserving say this average is to add noise to everyone's height such that the average is preserved so it's like mean zero noise but if i remove any person i can't identify uh them from that the change in the average which is exactly what we're doing here which is we're looking at changes in price and trying to identify the trade sizes sort of and it's what is easiest to use for very

hard learning algorithms and the complexity of the privacy mechanism is much less than the complexity of the algorithm so one thing i think that at least seems empirically true about ckp's is that the complexity of generating a circuit and correctly you know setting it up can oftentimes dwarf the complexity of the algorithm that the circuit is evaluating um and in differential priority is the opposite the privacy mechanism is usually just i want to sample random numbers i noise my data and it needs to be it might be sensitive to what the data is and then that's it and the idea is it's meant to be safe under interactive usage so

uh if basically i so so a famous example that led to the definitions we're going to see in the next slide is the netflix prize so um i don't know if you remember the netflix prize which was like you know netflix was gave this million dollar prize for um optim figuring out the best recommendations so they gave you sort of this huge sparse matrix where the rows represent uh users anonymized uh and the columns represented movies and if there was an entry in the matrix it would represent someone's ranking from one to five and people famously showed that you

could use data external to netflix join it with the netflix data set uh and de-anonymize with like very high probability like 95 identification of like certain users um and so the idea of this definition is really so that hey if someone has another data set that they join they can't do that much better than like the noise level that's added um and it's used in practice at apple google the us census uses this year i think people were complaining a little bit about it this year because i think so social scientists didn't realize their data had noise added to it but saleh v uh

cool so if we if we get back to the definition um sort of this thing i was saying earlier is i have a data set and consider a nearby data set a data set where i remove one person's data so this is the in this diagram xn would be the seven foot um outlier height person and the f the function computed is the average the mean um and if we're good at being differentially private the adversary can't tell with a high probability like which data set has the anomalous person removed or to so we assume that we assume that the

adversary knows the height of that person or uh no we assume they don't know the height they only know the averages but they've they've seen the averages under two different circumstances and so they don't know that there exists a person of anomalous height that was removed or added is that right yes okay yes yes yes uh and so an a randomized algorithm is is epsilon delta differentially private um well i put measurable in the wrong place measurable should be in front of s but if for all x and x prime in the domain of the algorithm

with the x and x prime being at distance less than or equal to one so the intuition for that is in the database if i use hamming distance distance equal one is remove or add entry uh and for any s in the output any measurable f in the output the measure bill is because i'm taking this probability uh i satisfy this condition which is the probability that a of x is in the set is less than or equal to e to the epsilon plus delta and another way to write that if delta is equal to zero another way to write that is log of the ratio of the probability so the log ratio uh is bounded by epsilon

and so that is exactly what the first of these images show where you know i have the two distributions uh under this randomized algorithm of the output and i can sort of show that the distributions are close but they're far they're somewhat there's some sort of lower bound also on their deviation and the delta uh the assumption is delta supposed to be uh cryptographically small um sorry i just saw this question and the way it is to yeah yeah you should say that out loud actually sorry and the way and the question is and the way to do that is to add data to the set that sort of

sort of balances the impact of the sound foot guy going out to keep staming yeah so you add noise as alistair said um but it's also meant to be sort of post-processing invariant so someone could keep making queries on the same data set but like because there's enough noise they can't do better than that something related to that size and noise and so this epsilon and delta quantify that amount of noise that is there delta is supposed to be thought of as cryptographically small so you should think of that as like shaw collision probability um epsilon can be large and i think in practice is larger than people want

it to be uh and a lot of the apple uh i don't know if any of you have seen these uh the apple child uh deep fake thing so so those things people found that effect you know apple was supposed to like be doing this private machine learning to classify child porn or something and that's a differentially private algorithm but turned out their epsilon was gigantic and so that's why people were able to infer to how the algorithm worked and stuff so anyway this stuff is used in practice so uh that that being said uh i'm not sure that the people implementing it know what epsilon and delta are okay so this gets to this point about

noise ideally we say hey we have function f we have some privacy parameters we have a data set and we're going to output say the mean of the function expectation of the function over the data set so can we do this in a generic way um yes but sort of only if we can bound the global variation of the function over all its inputs um and what that means we'll we'll talk about right now so the laplace lapos and gaussian mechanisms so laplace distribution um if you're not familiar it's just an exponential distribution that's symmetrized so it's e it's it's you know this distribution

um uh so define delta f uh to be the uh to be the sort of maximum over all neighboring uh data sets of the difference of the function so in the case of the person with a height seven foot this maximum would be sort of the difference of the average with the person included versus not um we take in our data and now we add noise so this this is uh to alistair's point uh earlier we add noise to each data point with

for this id that is from a laplace distribution with this parameter where it depends on the global variation and now return the expect like the average of f evaluated at the data points with noise added and that achieves epsilon delta epsilon differential privacy um if you want to do something with a gaussian instead the gaussian has yeah sorry i know i look like i'm doing yoga on screen but it's uh it's like much much faster decaying tail uh and that only will achieve epsilon delta differential privacy because the differential priority definition has a single exponential in it and so so of

course anything that's decaying faster than that will have some will end up having some delta asymptotically the other mechanism is called the exponential mechanism uh and it you could think of it as effectively like a gibbs sampling mechanism and you can get different privacy but we won't talk too much about it because we don't use it the most important thing about differential privacy and i think in cryptocurrency applications this is the reason differential privacy is sort of in some ways preferable uh uh you know as a mechanism is that differential privacy has this sort of semi-ring of operations it has

the sequential composition law of if i take a differential product algorithm with uh with perimeter epsilon i apply it to a data set take the output of the algorithm applied to another differentially provided algorithm with epsilon 2 dot dot dot uh i get to say that the uh combination uh composes and still has differential privacy but now with the sum of the um the sum of the epsilons uh on the other hand there's also a parallel composition law which is if they're sort of independent queries

uh running on the same data set possibly uh we [Music] we get sort of the worst case law and so that's like sort of that's why this is sort of you could run many queries in parallel they're independent in some sense or you could run them sequentially but you can always kind of continually keep them differently private which given this and this is why delta needs to be cryptographically negligible because yes otherwise you would have that significant delta time yes although um there is a kind of famous paper by kairuz so so so and um uh vishwanathan 2016 that shows you actually the delta dependence is

actually not a sublinear uh like uh it's actually a little better than the epsilon dependence um kind of unintuitively it's it's very it's it's like an information theoretic proof that you get that it's completely not like a geometric thing um but yeah cool well one question you might say is global sensitivity sucks right because you could be just adding more noise than any value in your data set or like very close to that you know the maximum value of your data set so then like what's the point um well hey why don't we try something simpler why don't we just localize given a certain

data set only add an amount of noise based on its neighbors instead of globally over all the possible pairs and you might make this thing called local sensitivity which given a data point x you only look at the maximum deviation over its neighbors and add that much noise and the global sensitivity is related kind of kind of as you might expect bad news this doesn't work good news is there is a way to bootstrap something that does work called smooth sensitivity won't go into too many details about it but it's it's actually i think one of the most underused things i've observed and you know i've only learned about

differential priorities here in the last six months but probably i'd say one of the bigger things in differential privacy because it lets you kind of like make your amount of noise very instant specific and it gives you a kind of black box algorithm for doing it um what do you mean by a neighbor here right so a neighbor here means any two data sets that are distance less than or equal to one um the the intuitive definition is this yeah uh the intuitive definition is is like i add or remove a data point or i like change a data point but only you know by a certain amount but the choice of metric is quite important and we choose a certain metric for

uh curve for cfms but if you remember um the way we define curvature is actually an l1 norm it's an l1 lipschitz bound so that we end up using l1 but yeah that's a good question smooth sensitivity also one important part is the original definition and sort of industry around differential privacy was built around this sort of i have a database i remove or add entry and like now you you want it still to be private smooth sensitivity the beauty of it is it actually lets you choose a metric and that metric can be uh the l1 norm it could be this kind of l0 norm like difference between these things it could be l2 it could be whatever metric you want and given the

metric you can get under you can basically get this kind of local sensitivity measure of like how much noise to add given the seven data points um so the reason i even mentioned this is like we use this l1 norm hence we can't just use like hamming distance results and so the smooth sensitivity is a really nice embedding theorem for this whole stuff all right finally after an hour of background we can actually get to the real result okay don't worry i i i don't this part's actually kind of short so let phi be a kappa liquid and mu stable

uh training function processing a sequence of traits if we have a verifiable source of randomness then we can achieve mu log n little of one delta differential privacy to do this we need three types of distributions samples from distributions uh from the verifiable random function and also we need to make sure these samples don't leak much data uh like we they don't leak data about their parameters in some sense and that's a sort of technical nuance detail that can be implemented um so we need a laplace distribution sample we need a random permutation from the

uniform distribution or a symmetric group and then we need a dirichlet sample so the dirichlet distribution is a distribution on the probability simplex it's the unique unimodal distribution um that you can construct uh sorry unique unimodal distribution that's consistent uh over taking slices and so backing up for a second the probability simplex is the set of probability distributions over n elements so it's the set of vectors uh of length n who sum to one and every element is positive the dirichlet distribution is a distribution you can construct on that such that if i take any conditional distribution so i let's say i have n

elements i condition that the last element never happens the conditional distributions also are all unimodal and there's a there's amazing theorems about them and dirichlet distribution's you know one of the most fame one of the most beloved things in classical frequency statistics uh somewhat beloved invasion statistics although there are some very bad impossibility results by by diaconas and friedman 1986 or seven okay so how do we actually prove differential privacy i'm not going to really go into all the details but i'm going to give the broad strokes geometric intuition so what we do is we construct this

this tree and we'll see a picture of it in a second called the trade tree and the trade tree is made from partial sums uh of the form given a permutation sigma we look at the partial sums of the difference between the permuted trade and the real trade uh modified by uh the curvature ratio um so intuitively if we if the curvature ratio is one like this you know the impact function is uh sort of like quadratic or something like that

the uh the this sum is just the difference between the trade so let's say i have trades one two and three i permute it to three two and one the partial sum would be like partial sum one would be the difference in size between trade one and three partial sum two would be trade one and three plus trade two and two which is zero per sum four would be trade one and three again and the idea is this measures sort of the notion of discrepancy when i permute the trade order so if we go back to that example of uh all ones and then one trader size t um by permuting it uh you know most of that these elements will be zero

if mu and kappa are one but then the one trade where it where the whale trade gets moved will be large and so that's sort of a notion of like hey we can identify the whale tree um and we construct the tree by making a binary heap generated by these row eye okay so let's look at what this looks like geometrically so here we have a trait tree and uh you know we you know these partial suns get inserted and this gives you a sort of ordering um one thing to to to realize is that this definition actually bounds the price impact

um and so what you can show is that the maximum price impact after you permute the trades is bounded by the for the root element of the tree given a specific permutation in trades plus the max discrepancy times the height so now we actually have a very like geometric way of thinking about given the set of trades what's the price impact and we have sort of some course bounds which are actually easier to work with um so one thing that's interesting is is okay so now we can take the expectation over random permutations like given you know my verifiable random function draws her into permutation i randomly permeate the trades what's the expected price impact

of the worst case price impact on average overall permutation i i mean it it gives you the distribution of the price impact as well doesn't it it's not just the worst yeah it's you all the information you need about it yes yes exactly uh and yeah this tree structure is actually the key thing here because because what you then show is you say okay let's pretend to start this is a desert data that the first element the expected value of that is constant and the second part has height log n so like the tree is balanced

then we know the price impact is is now o of log n um and that basically is exponentially better than batching remember in batching the worst case we have this linear impact cost in in a when when we have this kind of whale trade and minitrade thing but here we actually can get it to be logarithmic if we can ensure these are true the beauty is that we can we can kind of ensure these are true by doing two things one adding laplace noise um that separates the trade so that they're sort of not all if they're so intuitively the reason there's some technical

reasons why you've had noise but the intuition is let's get back to that scenario of like one trait of size t t minus one trades a size one if i randomly permute that set there are much fewer than n factorial output uh sequences because all the ones are the same right so you've actually lost you don't have the true amount of entropy that you would have if you actually permeated them but by adding noise you actually make it such that you you can regain unique sequences and um a very important fact and many of you might remember this from like cs101 or is that like you you kind of learned this like recursion for why quicksort has expected log n time

what you don't know is quicksort has one of the best like random quick sort corresponds to drawing a random permutation and generating a random binary tree from that permutation where you know you pick a pivot pick left and right pick left and right dot dot dot and you can show that that random binary tree has extremely strong concentration bounds around log n not only is its concentration bounds aren't like log n plus or minus square root of log n the concentration bounds are log n plus four times log n so as n goes to infinity of your list quick sort actually can never take more than four log n time extremely strong concentration bounds so that's what we take an advantage of

to guarantee this tree actually has height log n and the other thing we have to do is split trades and the way to do that draw a distribution from the dirichlet split the trades the dirichlet at least ensures there's some noise in the trade size again in how you split them and then you know we choose n in some appropriate way to match epsilon delta okay is this combination differentially private and the answer is yes because we have all these composition laws uh and so yeah basically you can get that this result that's it's view again differently private

um and one thing that's kind of a weird technical nuance is the dirichlet sampling itself needs to be done privately because you don't want to exactly leak the parameter um and you can it turns out you can do that pretty easily uh the simple answer is dear chiles or sub gaussian i mean they're on bound on a compact domain so pretty easy to be a sub gaussian uh but that lets you use all these kind of sub gaussian tail inequalities all right so we're almost at the end which is the last two slides uh can we do better well so i got the idea for this trade tree thing

from the online learning literature where there's a a an analog of vc dimension so if you're familiar with statistical learning theory vc dimension is sort of a very coarse way of measuring sample complexity like how many samples does my learning algorithm need to get error less than some fixed amount with high probability uh and there's another notion for online learning algorithms where you're given where the sequence of your data matters not the whole data set called little stone dimension and little sun dimension has to do with constructing trees and i try to basically construct this tree based on getting a finite wilson dimension which is how this kind of very the

papers i was saying are kind of remarkable reproved yeah and the state of the art online learning dp results this kind of like duality theorem result show that the black box learning algorithms can only really do to the to the d or diesel some dimension um and so that sort of says you could kind of think of that as like sort of being not a great result of like hey there might not be that much better you can do than permuting splitting and adding noise unless you're a zero curvature so zero curvature all bets are off you need completely different theorem um so what's one natural question

sorry uh what is n here oh n is the number of trades you you want to make private uh sorry yeah i i use t and n interchangeably but yeah it's number of trades uh and the last question is you know we kind of ignored this issue and i didn't really say it in this presentation but the way we used curvature assumes the felis regime so you might be like hey well that's not realistic you swap charges 30 basis points um fees actually help a little bit they actually mean with fees you get to add less noise uh it turns out

um but you you might be like oh can we really analyze these trade trees this way uh and if you thought that you know correct you can't analyze it the way we analyzed it but there's this amazing line of literature on metric embeddings of trees and bounding worst case algorithm performance using generic chaining uh that i'm you know it's in the appendix of this but we kind of give some of the steps of how you get there did you just say that with fees you would need less noise or less trades yes no you don't have to add as much noise okay so yeah please separate the fees separate the they kind of like

push the trading function further and so one of the reasons for that that if you write out the math is the the impact function with fees is actually 1 minus the fee times the impact function so let's have the impact function with no fees uh here i'll write it in here and you know basically the the fee kind of pushes things a little further apart like you don't need to separate the trades as much because the fee sort of implicitly adds change the curvature of the trading function that's

kind of like it's like a weird proportional to the amounts always though so like wouldn't you wouldn't it sort of reflect the same so so remember this is the sequence in which you you evaluate the trades matters right so let's have a trade of size one trade side three trade size two i'm randomly permuting them maybe i do two three one or i do three one two um with fees the kind of like the the deviation it the sort of deviation that you get kind of separates slightly more than it does if they were all this if there was no fee um i i don't know exactly how to yes uh yeah i'll send the slides also

the references are in the uh there sounds good yeah it's kind of like a weird the fees are a little bit annoying to handle but i think you can definitely you can definitely handle it um the other thing is all of the stuff i've said here can be evaluated numerically and so one of the future your future work is actually just numerically permuting splitting and uh like you know implement the differentially private algorithm implement the normal algorithm sample sequences of trades and like look at the empirical price impact and uh privacy uh and just like because because these are very you know guillermo was you know chiding

me was like these are just like horrible constants hitting and all that's hidden in all these proofs uh and in practice they're probably way better and it's also really easy to implement so uh you know hopefully you see that like in a blockchain this would actually be easy to implement if you have a vrf that a smart contract can use um because then it the application itself can draw a random permutation given the entropy it can draw from the dirichlet and it can draw a laplace and then add it and so that's sort of like why you know i think this this stuff is i the bounds we have here are probably quite pessimistic relative to

reality um which is sort of future work and one other question is like given that this sort of prevents front or like makes front running harder there's sort of a sense in which this should also classify cost of mev prevention versus pn like max profit that someone gets from mev and so uh future work is kind of generalizing this to other that scenario not just amongst cool uh questions but uh these are the references in case anyone but i'll i'll send them thinking we should probably get your

slides and we can link them ideally from the youtube and there's a lot of comments this time around so just thinking this alex we might want to try to get some of these also into the youtube video for after yeah so to ruin if you want to send me the slides i'll put them up on slideshare and we'll link them in and i'll make sure to download these [Music] yeah i'll just send them in the telegram right now okay perfect easier but yeah i guess if there's any other questions now would be a good time is it coaching for me to ask a question i don't know is that against the rules i think it's totally okay all right

you'll forgive me um so tara i just want to get back to this thing about fees and and i i know we we've been mostly thinking about the f3 world so i i don't mean to throw a curveball because i genuinely don't know the answer um but maybe we can brainstorm and it's this idea that right with fees because of path deficiency which for everybody's interest is a property to rooting gear and we'll describe in the previous paper that essentially but you could imagine a cfm without fees and if you have a hundred trades of size one or one side one trade of size 100 then those two things look the same in the absence of fees um right in terms of in terms of the final reserve composition that is very much not the case

in the case of fees um we're actually splitting up your trade results in strictly worse execution uh now that means of course that in these cases where you're trying to discern a large trade you might be able to do better in the world with fees than otherwise at least that would be my first intuition uh do you think that's wrong yeah i i agree with that i guess that's what i was saying kind of trying to say is that i actually think fees mean you can use less entropy but i i think what's the intuition for that the precise ordering so uh

the dumbest intuition is in the felis case it's path independent um which means that the beginning and end price are always the same regardless of the order of the permutation but in the fee case it's not and that the max deviation there's a distribution of outcomes for the last price which is some excess you get some free entropy there dependent on your sequence of trades so you sort of if you were making a randomness extractor from this it would should need less bits that would be like the way i try to formalize it but it's not like yeah it's it's still a little bit hazy and but i think that's in my mind what alex's intuition then also is maybe right it's i mean i could sort of argue

it both ways right that makes perfect sense to me what also makes perfect sense to me is say you might actually need more uh exactly because you can infer something about the underlying trades potentially because the final price is dependent on the ordering in a way that it is not in the case without fees yeah yeah i i don't know the answer and i honestly think you'll get a better idea from like empirically trying to do something like take certain planted sequences that you can come up with an adversarial model for like i was saying with the online learning thing and try to see how well you can like

try to come up with some measure of entropy and also some like simple attacks and see numerically their probability of success that's probably right um what i find very interesting right in this in this framework is that in some sense certainly in the case with fees where you're splitting up trades and doing permutations the payoffs of the liquidity provider are going to be different because right the traders paying more but who's getting that excess it's the liquidity provider so in a certain sense you are paying the liquidity provider for more privacy actually there's a very there's an interesting point to this which is um we wrote our paper that is on curvature which defined this kind of like this idea like why you this form of creature

the slide i had missing uh one of the things that actually i should have mentioned is that you can actually show that liquidity providers are never profitable if there's no noise trading um basically you need people who are trading back and forth kind of randomly in some sense and the adding in privacy actually ensures lps are closer to profitable or profitable so there's a weird sense in which what you're doing here is take charging a fee from the trader and giving it to the liquidity provider um and like it could actually weirdly stabilize some of these markets in some cases uh but it's like you know that sort of another weird thing

uh can we bounce sorry darris how can we bound yeah go for it um okay so you said it fees could potentially make things worse um you haven't analyzed it yet but could we bound how much worse it could get um for privacy based on the ratio between the fee amounts and the trade amounts so so let's say fees are never more than 100th of a trade amount okay can we then use that to say something about yeah yeah that's that's a great question so that's that's sort of what this uh the the that we kind of it is kind of addressed in the appendix but it's like not it's not i only for uniswap so i don't think it's

easy to write that out for generic constant function market makers but for certain functional forms you can write out exactly that relation um so the last appendix in this paper appendix i i think has the uniswap calculation for that um i think i saw you on one yeah yeah you can't so in the case where the fee is really small right all these bounds apply so all of these weird you know liquidity sensitivity bounds do apply and as long as there's kind of some amount of noise in the trades you can make very similar arguments um they don't carry over directly though which is why the proof actually has like a few more like it it would take some amount of of

careful sleuthing to actually make sure that it does work but in some sense the very small fee case in the case with no fees is is almost the same when you have even just a little bit of like random noise it is not the same in the case where you have like infinitely many digits of position because you know you you can tell apart the exact ordering in which trades happen and things like that but you can imagine that like you know look if if adding fees only affects you in the third or fourth significant digit right then then it's not going to matter if your noise is on the order of two digits or sorry you know two decimal places out or something i see right that's that's kind of the intuition um but it's it's very not obvious and to me

it's certainly not obvious uh whether fees actually hurt or help in terms of getting the um and there's of actually like giving you privacy better privacy results yeah i i think the the focus at least that uh you know the direction i guess suggested in the appendix is take the feelist case take the fee case try to show that there's only there's a bound between the two of them that's what these chaining type type of arguments show you is that they're never more than this distance apart that was the intuition behind my question yeah yeah so so the thing is it does depend on the function a lot more new in a nuanced way unlike these

curvature bounds which are like these like very coarse linear upper and lower bounds so that that's why i don't think there's like a generic answer at least like we don't have a generic answer for that but that's why i think the numerical simulations of this are like the best way to kind of get some intuition for it because like again guillermo's intuition is that like we're kind of this is still quite sub-optimal like information theoretically like we could probably get away with way less entropy um and it might not be just from the fees type of thing like you you might be able to get away with fewer calls to the verified random function so that that's the question um how much

entropy and practice do you need so so pick some and um yeah uh we don't we don't know i mean that's why i said i think you can the best the best way to do a lot of these differential privacy studies that people do um they usually prove a theorem with terrible bounds like this like terrible constants um and then they do numerical simulations and like show how close the two are and then they try to like extract some notion of entropy okay yeah it's really hard because the problem with entropy console they're actually really bad right i mean fundamentally right you're assuming your adversary can do any function not even just like computable functions or even

functions that are like efficient right like they are like nsa level adversary i mean it's even worse than the nsa because they even have like unlimited computation right it's like any measurable function can be your algorithm and all those stuff so and and and tropic bounds generic they're quite bad because entropy doesn't really compose in a way that's like super nice um it composes a little bit and so you you get the same asymptotics but you don't really get constants so the usual methods that we use for proving things just like you know you take take some some mechanism you have some you know amount of privacy in this mechanism and you add more noise to add more privacy and so it kind of screws up you know the whole pipeline ends up like totally screwing up with a screen with the constants and like all this thing

and so you it's this weird um i i want to call it like essentially an academic exercise in a lot of ways i mean again if you look at the apple and google stuff it's like kind of silly um but the tldr is that you can say that these things are private and in fact in practice you choose the right constants which are going to be much better than those in theory you could probably get good privacy but even in practice people don't actually do this which is kind of funny all at once so um but the point is like i think entropy is one of those things it's really it's rather complicated because it gives you it gives your adversary kind of essentially unlimited power with the given data and it's really really hard to like have good guarantees in that

case what kind of additional assumptions might you have to make in order to get those constants down well i think that's the million dollar question isn't it is like what's a good framework that essentially is not entropic that gives you you know reasonable privacy guarantees uh there's a whole philosophical there's a there's not what it means there's a there's a thing that seems to be very popular in the differential privacy literature now which is like correlated differential privacy which gives you information theoretic bounds but they're like local or something uh but like yeah i i think like the problem is these like metric entropy type of

things are always extremely sharp because of like a very small subset of cases it's kind of a little bit like sat problems where there's the the number of worst case uh uh instances is actually extremely small but the worst case instances dominate your average if that makes sense uh and so that's that it's kind of hard to exactly do that to get that but i i do i do think like you you might be able to get something um but i think what's better in practice is just like implement it and then see what see how it looks like that's that's the easiest way yeah that i agree and and to the point of smart contract languages uh i just don't see

i to anyone developing one i feel like or like making an api i think actually providing like a probability like numpy.random but for like the vrf of like hey my smart contract wants a sample from a gaussian using the vrf and i want the certificate from the vrf um would be awesome uh also useful for some post quantum crypto algorithms yeah i i think there's a lot of stuff like this that will you know if you want to make privacy useful in like defy uh i think you kind of have to like provide the apis to like sample random numbers

to developers because otherwise like yeah it i think it's gonna be hard for them to like write their own you know it's like it's it's basically they need some verifiable randomness and like if they have to go through your consensus protocol to like dig out like the vrf hash that's not ideal awesome so i think uh we're about out of time this morning i know folks got to run to um to some other events but uh hey tyrone thank you very much for uh for the presentation slides were great yeah if you want to send them on telegram i'll put them up later and uh thanks everyone who attended and uh yeah look forward to seeing you all next time