Ordering So Fair It Ain't Fair Ordering - Tarun Chitra

foreign [Applause] [Music] first off I uh I wanna want to talk a little bit about the flaws of fair ordering um and this is not meant as a uh attack on any of the people who who worked on it before I think like it's a really interesting idea uh in Social to take some of the ideas from social Choice Theory and apply them to uh to try to make blockchains more fair but uh I think there's there's no way of doing it in the way that people have tried there might be some other stuff hopefully we'll end with some positive notes but uh before that let's bring out the hatchet um so Tina as as previous speakers have also mentioned um forced us to to say the word Mev economic somewhere um in in my case I I unlike John and James uh kind of sort of wrote a slide uh and the idea is that I and this is a quote from one of the papers on Fair ordering which is fair ordering guarantees specific ordering in a finalized Ledger on how transactions arrive to the network to reduce minor extractable value yet virtually all fair ordering mechanisms say nothing about the economics of what they do they they guarantee that like some subsets of orderings will be respected other ones will not ever happen but they never tell you the cost of that or whether certain payout functions change with that so one question is if we're putting all this extra onus and extra work on top of validators what's the real economic value of it is their economic value is it harmful and that's sort of the main thing we'll be covering so um you know what is fair ordering so fair ordering is a mechanism that coerces on its validators to respect a particular set of orderings or transactions I.E first come first serve block order fairness uh block batch order fairness um all the papers are not duplicitous they do all point out this fact that it's actually impossible to attain perfectly uh Kenneth arrow on the Nobel prize in economics for proving this which is that in in ranked Choice voting so you can think of A ranked Choice vote as a validator giving you an order permutation or sequence of transactions uh and then sort of aggregating the road together to construct final outcome that it's impossible to get something that doesn't centralize that doesn't have what's sort of known as a dictatorship so instead Fair ordering tries to you know make algorithms that are approximately the average or majority vote or some type of some type of property for most ordering so you know here I put two different definitions the other thing that's kind of funny about all these papers they all have slightly different definitions of whether a batch is fair or not um and they all involve sort of extra data like some notion of time stamps and some assumptions of honesty amongst the validators um thank you to John for making this mean um but there's something weird about these definitions right these definitions are properties of partial orders they don't say anything about the economic value per unit partial order yet on the other hand if you think about Mev Mev is actually an economic profit a rent that is extracted that rent has a size it has a magnitude um and I think you know the the three main papers on Fair ordering the Themis uh aquitous and uh quick block ordering um they had like good intentions but they completely ignore the economics and they're like hey you do this thing it's this combinatorial thing um we restrict the sets of orderings uh and it gets rid of them and it's it's kind of a crazy statement to make because again you don't quantify the actual amount of me or the value and you're agnostic to all applications which doesn't really make much sense right there's a reason that certain applications generate you know very regular Mev like amms some generate very spiky Mev like liquidations or nft options those are very different things you can't really tell me that this ordering is universal to all of them and so that's the thing we're going to kind of explain today to try to dismantle this kind of shambolic industry of of hoping that we can uh you know violate the the natural laws of social Choice Theory so you know is it really a good idea to cause these you know to to have validators have to do all this extra work when it it doesn't really have an economic payoff and hopefully you'll be convinced at least somewhat you know the full paper will be out soon so you can see the proof but uh that it's actually harmful in some cases so I want to also give a bit of uh a bit of historical context from other fields so other fields that that use social trust Theory especially things in decision Theory things in AI have studied order fairness in different contexts especially with regards to you model quality or like how much you you mutate a model by giving some fairness guarantees and they get these impossibility results the difference is model quality is is a bit like mev's economic value there's still these kind of continuous magnitude objective functions depend on the input data depend on the particular thing you're inferring but they all get these impossibility theorems so why should you not expect that for fair ordering okay so you know I've had my my uh my son but now we actually have to go into to what it is about sure ordering that's so weird so to try to dismantle uh furthering what we do is we consider a two-player game um one player is a fair ordering protocol that is proffering a set of orderings of transactions that are that are allowed to be executed and the other you can think of as an adversarial D5 developer so someone who is making a protocol that's trying to cause the fair ordering to be give a worse um value for the the users in the protocol the the rough game mechanics are nature draws a set of transactions so that's user's generating sets of transactions the developer plays first and constructs a protocol so think like a defy protocol um adapted to the set of transactions and the protocol is a payoff function so we'll talk a little bit about what those are in a second but you can think of the payoff function as the expected value for the user then the second player the fair ordering protocol draws a set of permutations from the symmetric group that's SN that's a set of permutations uh and it draws it from a distribution p and so one reason that you have this distribution is of course in in most Fair ordering protocols there's some extra metadata like the timestamps of when people different validators receive certain transactions that adds some Randomness and that Randomness means that there's not a unique ordering again errors and possibility theorem sort of guarantees that so there's a sort of set of orderings and it'll turn out that the size of the set of orderings controls uh how well the the the the fair routing protocol can win in this two-player game and finally a value V is realized uh based on these so without getting too too in the weeds to the right you'll see something that defines the value of a protocol PA which you know we can talk about by its distribution of uh orderings it generates and we can we consider a min max law so if you've seen sort of classical still game theory classical Von Norman Morgenstern stuff this is just traditional mean math and there's a loss function which takes in an ordering it's a permutation Pi in symmetric group and a uh payout function f and this loss function is meant to measure some notion of fairness and we'll talk about how they're different no different loss functions will give you different Notions of fairness but you sort of want this game to qualitatively have the same winner like usually the D5 developer wins for many loss functions even if I perturb it and so in this game the value of the game if the game is positive the adversary the D5 protocol developer wins if the values negative the fair ordering protocol win and of course this will depend a loss function but we'll talk a little bit about that so why does this represent favoriting protocols you know abstractly again you can view a fair ordering protocol is taking each validator set so transactions and some metadata Associated to those transactions like timestamps and the forwarding protocol outputs a single permutation with those transactions in the set of allowable Trend actions each but the thing is there's many of these Age and and the key uh thing we'll find out is that fair ordering protocols don't make each that small and that's where the adversarial developer can take advantage of them again the randomness comes from Network latency user demand Etc and you know how do we how do we bound the this value of this game well there's combinatorial constraints that arise from the set age another way of looking at this is given enough noise or entropy into sets of permutations you're allowed you can almost surely construct a payoff where if I restrict to those sets I get a worse value than if I am unrestricted and basically what the proof does is we explicitly construct a D5 protocol whose rules for when liquidations are allowed to happen uh exactly is optimized to be bad on these permutations generated by the forwarding um in fact the liquidation rules draw a lot of inspiration from a protocol many of you might know which is liquidy LUSD they have a staking pool that auto liquidates uh lesd uh issued assets and uh the only difference is that instead of giving Parada rewards we get six rewards but it it's a little bit more complicated to describe and what is what this sort of says is fair ordering preferences particular application so this application that looks like a defect protocol that has particular liquidation rules uh it has a worse value for users under Fair ordering which means that other protocols that have the same value uh you know are sort of preferenced and so there's there's sort of this very interesting thing that a fair ordering protocol is is sort of picking winners and losers implicitly so now the next question is what is this notion of a payoff so a payoff represents the economic value each user represents gains from a particular set of transactions a user payoff is a function from the symmetric group to the reals you can decompose any payoff into this kind of sum over indicator functions and this you know some of the end results we'll talk about at the end which I'll just sort of give a preview of rely on sort of some of the decomposition properties there so what are examples of payoffs uh one example is just an amm payoff and in in this paper earlier uh we analyzed sort of how Mev payoffs for sandwich attacks look under permutations and then sort of get some bounds there the other example is liquidations and you can think of a liquidation as really an indicator function that's parametrized on a price and a threshold so if the value of the assets below some threshold that's the indicator function um then you you know you realize a profit and if it's not it's zero and you can sort of look at this as a barrier option as well so the real question is how do you choose this loss function well there's a couple of different ways to Define sort of fairness one one version of fairness is the extremes what's the difference between the best case ordering like the the one that maximizes social welfare and the worst case ordering the one that minimizes social welfare that should say best not base um the other is sort of mean so what's the deviation of a given ordering away from from sort of the average like is a particular you know how much does do the orderings fluctuate around average we want to choose L this loss function in such a way to be robust to perturbations and uh an interesting thing is that um you know for you know finite groups there's actually ways to generate kind of lower bounds on things like V like this value of this game that we talked about um these are uncertainty principles they're very they're sort of these finite group uncertainty principles are similar but quite different to the uncertainty principle you might have learned in in a physics class or a real analysis class um but the interesting thing is that you may you may now ask this question is there an uncertainty principle for for MEP here and there's a very interesting you know that's sort of the the final thing we'll see is that there's sort of this trade-off between how much you restrict the set of orderings and how manipulable a payoff function is and that that trade-off you has sort of this lower bound and that's sort of this this hidden hidden costs and sort of you know complexity costs in it maybe which is is the reason these Fair ordering things sort of can fail uh so now let's find out how much orderings cost so the claim is suppose I have the distribution P that generates ordering and suppose that with very high probability the size of each is Omega of n factorial that means it's it's a percentage of the total number of permutations and if L is deviation from worst case so the extrema then you can show the value of the game is bounded by a positive constant which in word says if the value if the number of fair orderings is sufficiently large then this Mini max value is positive and this sort of D5 protocol we constructed always sort of does worse when you use ferriting another way of viewing this is fair ordering is actually discriminatory to particular protocols so you might say okay well is it really realistic that a fair ordering thing generates Omega n factorial permutation shouldn't it just be generating like constant in the number of transactions um and where you would where this logic sort of falls apart is um if you actually look at random ordered elections or random elections and this was studied in 19th century uh by some some actually French sort of philosophers who also did social Choice Theory uh and this guy Gilbert who kind of proved this some very Bizarro formula that in a random ranked election with three candidates there is a 91 chance uh that you don't have a condorcet paradox a condor say Paradox is candidate a beats candid B on a pairwise election basis can it B beats candid C on the pairwise election basis but candid C beats candida a on a pairwise election basis um and so when you have those types of Loops then you have no perfect ranked ordering and that's sort of like the simplest version of this and you know again to the credit of of Themis and Aquarius and all these papers they admit that this is a flaw of theirs the problem is such a thing guarantees that under and with enough Randomness your set of orderings is still Omega of n factorial it's still a percentage of the perme of the symmetric group and so that sort of says the the hypotheses here are pretty likely to happen unless your time stamp distribution is really really degenerate okay so I've given you all this bad news uh and you know a lot a lot of it involves like you know Game Theory math whatever is there anything you should be happy about and and what I would say you know maybe the the positives you should take out there are probably ways to do application specific order preferences so there are two results in this uh frame of mind um the first one which uh it released Yesterday by Co and Guillermo um is basically they looked at the kind of arbitrum first come first serve mechanism and they only looked at the top transactions so they don't care about the whole ordering they care just about the top transaction and they they were able to write a linear program be able to bound its Gap and they were able to get a lower bound uh on the ratio of the price from um the optimal uh ordering versus the sort of like first come first server ordering and show a lower bound so that it's always worse uh it under some conditions and so that's a kind of very nice simple version it doesn't capture all Mev but it kind of gets you at least you know kind of the minimum viable example and then this these papers from us um that basically construct an uncertainty principle and these uncertainty principles give you this lower bound the uncertainty principles actually show you things akin to the following uh where you can bound sort of the the worst case part of the Mini Max laws by lower Bound by a polynomial in something known as the the Fourier degree of the payoff function and also upper bounded in terms of 48 degree so what this says is you can actually control the fairness get measured in these in sort of like the deviation from worst case um by the is related how how well you can actually achieve some fairness is related to the sort of inherent computational complexity of the payoff function specified by your program uh and you know I think that's actually you know a really interesting thing because it basically says hey there's a reason people optimize smart contract programs for being less complex they actually have less of this worst case unfair bound the upper Bound in this case so with that probably did go over time so uh we'll answer some questions in the chat