ZK10: ZK Mechanism Design: How privacy can change user guarantees - Tarun Chitra

Transcript

foreign [Music] next up we have thank you tarun chitra from Gauntlet presenting ZK mechanism design how privacy can change user guarantees so welcome to roon lovely yep great um yeah first off sorry for the wrong date I could not edit my slides last minute so uh but I think the the you know I think everyone so far has talked more about

you know proving algorithms trying to to focus on optimizing the ability to make things with ZK I'm going to try to talk a little bit more maybe somewhat pessimistically and somewhat optimistically depending on your perspective about applications and limits those applications um cool so uh you know I think there's a couple things that are worth noting first off if we're being very honest and I mean very blunt there's only really two applications of zkps today that are used in production the first is effectively State compression which is roll-ups and the

second is private verifiable compute that sort of co-processors off-chain compute for smart contracts and this may be you know if you look at Twitter I don't think the average person who isn't in crypto or in ZK is actually particularly uh enthralled with those guarantees this is not to make fun of Andreessen this is just you know if you look at this like they tried to make this thing accessible about why people should care about ZK and instead they got flogged for it so it's very clear that in some ways we do actually have to also think about applications and applications that are not just Roll-Ups which is sort of blockchains eating themselves so you know I think the the key here is

to talk about tangible benefits so what are tangible benefits so tangible benefit to a user who's interacting with either a ZK system using NPC using fhe I'm using all these interchangeably so when I say ZK here oftentimes I mean one of the three depending on the context um and they're sort of need to be certain benefits that the user can get guarantees on so one they get better prices two they get better ux and sort of three they don't have to you know have a a horrible onboarding experience so I'm going to just talk about three main types of tangible benefits from ZK programs and then we're going to talk

about how mechanism design gives you limitations and on what things you can and can't build with that so the three Horsemen I would say are provably optimal pricing so if you think about why defy grew over the last few years D5 grew in part because it was easy to price things you didn't have to think very hard and a lot of the mechanisms that worked best had the least complexity and it was easy to know whether you got the right price in some sense the second is what's called auditability and we'll talk a little bit about that uh the exact definition but you should think of odd ability as being one step further than verifiability we're sort of used to verifiability as hey I can verify a state update happened and I

don't need to actually replicate the entire State update but audibility is the idea of can I pinpoint what actually went wrong when there is an invalid State update so it's it's sort of a way of figuring out when there's what what caused an error and the final thing is what I'll call generalized compression which is adding extra conditions to things like Roll-Ups um for giving user guarantees uh and you know I I had to add a overheard tweet um so you know what sort of the end game here you know there's obviously been this huge immense r d effort to kind of like get these things production and obviously that's been nothing short of heroic um but so far the only use cases people

made are making ZK VMS uh which is effectively just a compression technique in some ways uh and so one question you might ask is you know and I think a lot of the ZK co-processing world is kind of trying to ask this is how can given that we're about to have this huge glut of proving Supply over the next 12 24 to 48 months how can we actually use that for things other than just compressing roll-ups okay so the way we're going to do that the rest of this talk we're sort of going to talk about these three properties that are useful and help users that you can guarantee happen with with ZK then we're going to talk about formalizing that via

something that's similar to an ideal functionality in cryptography so that's what I call commitment collateral games and then we'll talk about limitations and on those so as I said before if you think about d5's growth a lot of it came from being very easy to have optimal pricing it was easy to figure out what the optimal Arbitrage was it was easy to figure out optimal routing and now you you see this world where people are trying to do off-chain aggregation they're kind of you know you see a bunch of different versions of this where it's matching different chains and trying to settle prices but every user really only wants sort of two

things one is knowing that they're not getting screwed and second to not have to work hard to get a good price so that's sort of optimal pricing doesn't really need much explanation um man this is a tiny type of mine the analogy should actually be verifiability of solubility is NP as a cone P um but crypto is sort of based on verifiability the sort of proofs of State transitions being correct but if something is invalid can I figure out what caused the invalid transition and this this kind of extra step is kind of important especially when thinking about economic mechanisms so let's compare sort of a gap which is the first and second price auctions where

there is a gap in auditability so uh just for notational sake say I have a vector of n elements V1 through VN um V sub parentheses I is the order statistic so that's any ordering that guarantees that they're ordered from highest to lowest so in the first price auction you get a bunch of bids from from bidders so you have n bids and the winner pays B1 the first order statistic second price auction you get a vector of n bids the user who bid B1 gets pays B2 um if they're cheat if there's a cheating Auctioneer so cheating

Auctioneer will add fake bids to get the second price auction to pay higher than b sub 2 because that's their revenue right the auctioneer has incentive to do that so you might say okay let's suppose the users know the auctioneer cheated how much do they have to communicate with one another to figure out whether the auctioneer cheated and for the first price auction you can show that it's a constant number of bids or constant amount of communication it's very easy to see when document cheats for the second price auction everyone has to collaborate and the reason for that is the auctioneer could add as many fake bids as their users and they have to all talk to each other to figure out which subset is the actual real bids

so this is a sense in which audibility is different between two economic mechanisms you can't it's much harder to tell when there's cheating okay the the the second type of benefit that ZK systems have for users is what I call generalized compression generalized compression says you know I you know if you think about Roll-Ups in some sense what is the point of having you know ZK Roll-Ups I'm am able to prove to you these State updates given a input State an output State an ordering a transaction a set of transactions you don't have to verify the actual execution right everyone here probably knows that but one thing you might want to do is

add extra covenants so you might say actually I want to know if the set of transactions you gave me is the shortest is the smallest subset of transactions that goes between the input State and the output State and you want a certificate of that another thing you might say is you might want some type of uh thing that says like hey the ordering in which these transactions were executed satisfy some constraints so I prove that they you know certain types of things were in front run or were front run or a particular type of subsets of constraints were respected um generalized compression is anything that lets you add these extra covenants that proves that not only does this is the straight transition valid but that there's some extra special restrictions

that are meant to be good for users in there you know why are these tangible benefits so I think this is actually something I said on the ZK podcast that AWA made a meme and posted which was there's sort of this trilemma in this world which is you you sort of have this question of like can I make something efficient can I make it private and how auditable is it or as I said in the episode how easy is it to tell if I got and you kind of can't get all three but you can get very close with zkn that's kind of what we're gonna give a more formal description of okay so now we can talk a little bit more

formally you know I tried to just set the stage because again this is like you know not a talk about a proving system to some more talk about if you build an application you know what types of things should you be trying to create as a benefit so instead of thinking about auctions now let's just think about any type of financial mechanism whether it's a matching Market whether it's a DEX trade whether it's a game where there's two classes of users one is the operator the operator coordinates payments or transfers amongst players and the second is users users who submit State updates and constraints that they want satisfied the analysis of such mechanisms sort of

relies on understanding a the algorithm for computing these payments B incentives and proofs that the algorithm wasn't manipulated so that the you know in the case of the second price auction you you see that figuring out if there's a proof that the auctioneer cheated actually requires a ton of extra State and you know having those kind of in concise proofs is quite important third Communication channel for The Operators and users and a blockchain is just asynchronous communication channel for these parties and fourth of course measure of utility Financial measurement and in order to do this analysis you kind of have to blend algorithmic Game Theory information Theory so many of you have read a lot of

cryptography papers that say things like hey here's an ideal functionality for how users generate a proof or how an adversary interacts with the API of a ZK system for these kind of game theoretic things that you're trying to offer to users you you can think of having a very similar thing to an ideal functionality except it's an ideal mechanism so it's a mechanism that has a bunch of properties that you want for these users and you try to show that this holds so what are these kind of properties first there needs to be an asynchronous Public Communication channel that's what a blockchain is if we strip out all the other things in a blockchain pki whatever validators just it's just a bulletin board that people can post things publicly to so posting ZK proofs

of things publicly the second is operator incentive compatibility so this is users getting proof that the operator didn't manipulate the outcome of the mechanism the third is user truthfulness so this is proof that the users aren't colluding um and this is sort of so that the operator knows that they're getting what the maximum Revenue that are sort of what Revenue they should be getting and the final thing and this is where this these extra constraints come in is minimal communication users do not want to provide a complete description of their preferences um and and you're seeing this in a lot of things that people are building right

this whole intent world this whole like I'm giving you some sort of I'm giving you some sort of weak type of thing that says like hey I want to buy Pepe coin on five chains I don't really care how you do it uh that is sort of this this notion that users don't have to exactly prescribe their preferences so if you look at the economics literature and a lot of the mechanisms that are found in the economics literature the users have to specify their entire value and preferences for every possible thing in the universe that's obviously not possible Right like people want a concise minimal representation and so this notion of minimality is actually quite important um you know realizing these mechanisms relies on ZK and so I'll give you kind

of the high level version for incentive compatibility and truthfulness you need auditability and collateral systems you need some way of slashing some sort of financial penalty on the operator in some form of way of figuring out whether there should be a slashing penalty or not the second thing is you need this notion of minimal communication to kind of or you need some notion of extra covenants that are proved to give to satisfy minimal communication now as I said the idea of me going up to you and asking you to go into a grocery store and tell me the relative preference of every pair of items is very unlikely and yet you go to a grocery store and buy things you want all the time right so there's a sense in which many different mechanisms have different ways

of specifying the inputs so a matching market so matching markets might be something like intense kidney exchange users specify orderings and preferences for every possible alternative auctions users have to provide their distribution of values for every possible item which can be quite large and dynamic pricing the operator reprices with user elasticity so one one key thing is that any type of thing any type of description of such mechanisms needs to incorporate all three of these different types of modalities um but again there's kind of this idea that if you want to have minimal communication from the end user the user only has to specify that they want Pepe

coin not exactly how much from each chain you actually need to add this extra set of covenants that you need to prove so a natural question might be why do we need collateral if we have ZK proofs shouldn't we just be able to prove these State transitions perfectly and then you don't really need uh slashing well the problem in is in any permissionless system the mechanism operator can impersonate users right in a lot of ways Mev exists partially because of this right a sandwich attack is a operator impersonating a user and in some ways the only mitigation is over collateralization so that you can slash the operator proportional to the the penalty that they cause the users

um but again collateral isn't the only thing you need you also need this ability to attribute faults and that's where the zkp is extremely important because it allows you to prove a fault happened and then slash the operator so what is a commitment collateral game so a commitment collateral game is wrong so initialize a communication Channel where people are able to post DK commitments so that might be a public chain like a blockchain a user who has a valuation for items some type of utility for these items commits uh to some properties of their valuation they don't actually reveal the true valuation they commit to maybe you know adding some noise to it and commit to the noise version they commit to sort of

if it's a vector of values they commit to some sub vector the user also commits to what are called feasibility inequalities the feasibility inequalities are effectively the user saying hey I am actually over collateralized so this might be the equivalent of saying hey I put up some collateral and my collateral is greater than my bid but I'm not revealing to you my bid I'm only revealing to you that I've over collateralized and these inequalities are actually extremely important for this auditability piece of being able to commit to those and this is where you need a zkp also and then the user will post collateral to a private pool so that's like a shielded pool so so they can be slashed if they violate their constraints

finally the operator computes payments and allocations and sends them to users and then the users realize some utility operator realizes Revenue so at a very high level this encapsulates all of the different types of games we talked about earlier auctions matching markets Dynamic pricing you can sort of make a ZK version of all of them by mapping them to this set of the system so how should we interpret this so one very big difference so if I look at a fully public game say an nft auction or an amm the users don't actually commit to their true value they commit to some approximate sketch or of some properties of it because they don't want to reveal

everything and the proofs that they they provide are such that the sketch satisfies some constraints so that that people can detect when they're cheating and the final thing is that the algorithm for choosing the payment has to post a proof so that people can verify that the payments were distributed correctly so there's sort of two examples uh one is sort of a deferred acceptance option this is a commit reveal style auction where people commit their bids then they post a zkp that their uh collateral is greater than their bid and then the auctioneer can and then they reveal on the second step the other is what's called a commit and run mechanism which is uh basically a way of me being able to commit something

about my value it's similar to what I described uh but it's specialized for a particular type of auction it's not General okay um so the next question is what is the set of possible mechanisms that these commitment collateral games can be realized for and that's we're going to talk about some of the math for that not fully all of it so naively this commitment collateral game set up you know is sort of underspecified like it it obviously you could construct some types of mechanisms where it shouldn't work right like I could construct a sharp P complete matching game and that thing shouldn't be able to to solve it so

clearly there's some sense in which complexity theory-wise we're missing you know the the description of the thing is missing some stuff um and so I think one of the reasons by the way that I went down this line work is there's this whole line of work on intents and matching and off chain matching and one question you might ask is like how do you actually do that uh with some form of privacy and and this is this sort of working backwards towards that sort of what I was talking about earlier so one question about these commitment collateral games is you know when do when do these need to work well first of all the users need to be able to supply some constraints there also needs to be some constraint on how much the

mechanism changes if a user changes their value for something by one basis point but the mechanism changes the payments by 200 there's sort of something that's probably wrong right like there's sort of some notion of the gradient of how the mechanism describes payments should not should be sort of you can bound how much it does that relative to how much user valuations change so one way of doing this and this uh in a black box way is something called sort of a smooth mechanism so informally uh before we write sort of some of the equations a smooth mechanism is makes the following assumption suppose that instead of saying like hey the users know their exact valuation again imagine

you went to a grocery store and I said give me your value for every single item in the grocery store you wouldn't be able to do it but let's say I know up to some error like I'm willing to I know that everyone's valuation Falls within they they're able to to guess what their price is for everything within some marginal error and then the second thing is assume that the allocation so what the the mechanism does very smoothly so this is what I was talking about that the you know I can bound the maximum change in prices as a function of the maximum change in user values um this is sufficient to sort of bound how fast people can learn what the optimal revenue is and so if we zoom out the reason you want to do this is you want

users to be able to not specify their full valuations but you want the operator to be able to realize maximum revenue or optimal Revenue without learning all of the users properties this notion of smoothness is sort of a game theory version of Smooth complexity uh if you've ever heard that from kind of uh the the 90s and uh you know smooth mechanisms kind of show that auctioneers in if a mechanism is smooth you can effectively show auctioneers can learn the optimal Revenue okay so the idea is you have a bunch of users they have some distributions you have some mechanism parameters that can be

tuned by the operator so that might be Reserve prices and auctions so you know online ad auctions the the sort of parameters there are effectively Reserve prices the minimum price for bidding on a particular keyword and then you have a mechanism which takes in these distributions and these parameters and outputs payments what how much each user pays each other with the idea that there's Agent Zero which is the blockchain itself that you might burn you might burn coins um these are more technical definitions but you should basically think of like I'll show the first one in pictures in a second but there's a sort of a notion of a smooth distribution concept you can kind of upper bound it on on all sorts

of sets uh and then there's a notion of the mechanism being smoother so the payments are are smooth so ignoring the technical details both of these things can say I don't really know exactly how much the mechanism changes prices but I can bound it and I don't know how much the user's value change but I can bound it and I don't know any information to any more Precision than that so I'm not very good at drawing so I apologize in advance for this uh but this is sort of a drawing of like this notion of smooth uh which basically means that the user's value which you can think of as the x-axis doesn't have a gradient that's faster than the yellow line so if the gradients sort of are

stay below that sort of means you're you're relatively smooth but you can see in the red one it kind of jumps up quickly and that's sort of a not Sigma soon so one important thing to note is that for almost any auction in the generic setting you can learn after many iterations the optimal Revenue uh for smooth if if user valuations are smooth uh with many rounds so what this is sort of saying is things like Mev auctions that are these iterated auctions the auctioneer actually can learn how to get the optimal Revenue if the user distributions are smooth so the tldr

without going kind of going to math is the smoothness lets you understand a mechanism performance without knowing the precise utilities values of the users and it also allows a mechanisms designer to trade off the prices they charge versus how much knowledge they have of how what users value things at but all of this stuff I've said so far relies on precise knowledge of the user distributions and the question is imagine if the users only commit in ZK some fraction of their valuations like I I sample random items at the grocery store and I tell you I would pay more for this than this and I give you a small subset of items how many is

sufficient to get these same guarantees so you sort of have two worlds Computing the same thing you have the public mechanism so this is say you know an nft auction on ethereum right now and you have the commitment mechanism where the users only commit these small set of things and one question you might ask is when are they close when does the commitment version get close to the public version uh and do we get all these guarantees and so yeah we sort of have started something that's come up is we've kind of shown that there are ways where the users can commit a very small set of things and as long as they're doing homomorphic commitments they only be

partial you you basically get that the private version of these mechanisms stays close to the public one so the the tldr of this is um you can sort of Black Box take a public mechanism one where the operator knows all the information about the user and construct a private mechanism that gets very similar Financial properties uh provided the mechanism is smooth so all of the known commitment collateral commitment games um have a reveal step a public reveal step um suppose we were doing this in NPC and

we didn't actually the users didn't have to reveal can you still get these same guarantees like the users don't have to reveal any of their values um can we kind of get the matching Market case to map to this framework the matching Market case again this is intent case of like I have many possible things I want and everyone has different preferences how do I kind of get an optimal allocation and is there a stronger notion of approximation like can you get better can these private mechanisms approximate the public mechanisms even more tightly and with that uh the final thoughts are you know ZK should be providing some tangible benefits not just compression uh these commitment collateral games

provide a sort of way of thinking about games where ZK actually provides a tangible benefit and that you can measure in terms of prices these smooth mechanisms like you do that without knowing anything about the users and combining ZK with smooth mechanisms lets you have users Express minimal preferences while still being able to allow the Rev operators to maximize Revenue and so with that that's it thank you so much tarun do we have questions okay hi tarun thank you for the talk quick

question when you define smoothness are you kind of thinking of like there's a efficiency loss function when you have these private mechanisms with a public mechanism both in terms of smoothing a curve plus the cost of doing computation the cost of the incomputation has two effects one is loss of time second is a real real cost yeah that's a good question um one way of thinking about why you need this smoothness is if something is smooth I can you could imagine that I you know I have a point on the surface that's sort of like the optimal valuations people have and I if I add a bunch of noise and then I take the average that should be very close to the true optimal when

it's smooth and you could think of the ZK commitments or adding noise they're projecting down to like a lower dimensional space and adding some noise but because it's smooth it's staying in the same neighborhood of the optimum and that's the idea here is that like any mechanism that can guarantee you these pricing guarantees and you the user doesn't have to reveal all their information have to have some something like that because otherwise you have no guarantee that the commitments don't just move you kind of far away from that that's that's the idea I think we have a question back there yep um yeah I have a question specifically on sort of the the matching markets and

how it relates to these commitment games which is I think in a lot of cases you don't want to have these discrete rounds that are kind of required by commitment and reveal schemes and I'm curious whether you've given Fortress to if you can model those in a similar way or if there's a similar equivalence there yeah it's a good question I think the matching Market case I suspect can only really be done in a fixed round with fhe uh I don't think you can do in ZK in less than two rounds uh and I yeah it I think the matching Market case is actually the worst case in some sense um but I do actually think there there

is a sense in which if you're at fhe and you had a way to attribute faults in the matching game you should be able to do in one round um but yeah I don't know how to do it without it I haven't really thought about it enough to actually I haven't like proved that it's has that communication complexity but all right thanks yes uh one more question and one maybe comment or answer my first question is kind of the same as anisha's are there any other models besides smoothness smoothness that capture kind of uh yeah expressing people's preferences

without them revealing their entire set of values or a smoothness the thing we should be studying yeah so it's it's a good question I think smoothness just again the intuition for why it works right is like if the thing is smooth I randomly sample I shouldn't yeah the the question is like for for matching markets for instance those are very sharp right those are actually the the user utilities might be relatively smooth but the mechanism its allocation might jump very discreetly yeah um and for those you have to have a totally different notion um well uh and I yeah I don't know what that is but they're they're so I I take

that so Guillermo and I wrote a paper recently on on things where we we give a notion of smoothness to things that look like matching markets and when that's true you can apply this same setup um I think the main reason I'm not sure how to deal with anything that is different than smoothness is there's no way to really guarantee like if you had some notion of a type of metric embedding where I know that post commitment like you could think of like I make this you know imagine I have a vector that defines my preferences that's length n i project down to a set of commitments that size log n I there's some lower bounds on how much that I have to move I distance wise and

those kind of give you some hardness results that like other than smoothness you're not going to get something but that's the that's kind of like the limit of to what I know and that's but there might be another model I I agree with you there it's just that smoothness is the only one I think that you can kind of prove some nice properties for yeah thank you for the intuitions really helpful and as for the open questions you mentioned something about keeping data private or something or never revealing using NPC wouldn't uh commit improve Paradigm maybe with CK help like what have we just commit to the data and never open it ever yeah so in this in the known mechanisms for what it's worth and and these ones are

um in in the known mechanisms usually what happens is you commit um to say a bid and uh if you don't reveal you get slashed that's how we do fault attribution but if you have the ZK proof of auditability like oh like given this set of uh commitments and some proof of these inequalities I was talking about so both of these mechanisms don't have crucially proof of some feasibility constraints if your feasibility constraints are attributable that such that you can you can test whether they're violated by say your commitments are homomorphic and you add them and then you add the constraints and they don't some you they don't satisfy some expected Behavior then you could do it without uh without the

commit real so this the kind of crucial thing here is really these feasibility constraints and having homomorphic commitments is extremely important for that but that's a very good question thank you any other questions thank you good talk uh Terry uh my question is in relation to what we just spoke about the the collateral the commitment collateral games and the truthfulness right so just for Simplicity take one example and there may be auctions like um

you have the per block commitment let's say um multiple bits come from multiple searchers is it possible to add some contingent liability mechanism from um that you have a player coming in for one time and then if they get slashed you don't really need to have the collateral more than what the bid is but it could have this kind of condition liability that they will if they cheated or if they fail to reveal they get slashed they will only get back in the game once they uh yeah yeah I guess this is kind of what they were both they're both their questions we're getting at the prior two questions right of like oh can I do some temporal type of thing yeah so

to be fair all of these things assume myopic utilities right these utilities are stateful for only a single state they don't have time dependence um you probably could show something for time dependence but I feel like it's actually quite hard uh I I'm not sure if they're you're gonna get a formal proof but like there might be something that kind of works in sort of in practice um I I think there's a sense in which you could try to relax these incentive compatibility constraints um to something that's very approximate and then that is more favorable to do via these temporal mechanisms um yeah I haven't seen any for for what

it's worth an interesting thing about most blockchains is the slashing penalties and the blocker boards are all temporal in some weird way like you don't realize your block reward immediately for most chains you like have wind time windows for withdrawals like you receive them and same with slashing so there's clearly something to that um I'm just not sure how you formally analyze it thanks all right I think that's all we have time for lunch is starting now and we'll be back on the stage at 2PM thank you turn [Applause]