Latency Racing vs Bidding in Fair Transaction Ordering

Transcript

[Music] foreign [Music] so hello everyone welcome to the presentation today I will talk about buying time

latency versus bidding in Fair transaction ordering this is a join tour together with mahim na calcar who is PhD student at Cornell University Jan Christoph Schlegel who is senior lecturer at City University of London and recently he joined flashbots and Edward Felton who is co-founder and the chief scientist at of chain labs and I'm from of chain Labs doing research there so motivation is a transaction ordering policy which is one of the biggest questions in blockchains especially with the rise of D5 and we know from the traditional finance that they are maintaining order books and they are

matching buy and sell orders and their policies first come first serve and this is the same policy for all roll-up protocols that I'm aware of and in case of traditional Finance it is enforced by law that this is the only policy we know that ethereum it's a big problem that there is a lot of front running and back running sandwich attacks happening because there is one block writer for each block which can choose the transactions from the mempool and also the ordering of it and this is then exploited by them

and transactions include beats or tips but in case of Roll-Ups we don't have this and we are proposing to change that so there are a lot of advantages to first come first serve first of all it's the simplest probably and it's easy to explain to anyone it also sounds fair whoever is fastest gets executed fastest and it minimizes the latency there is nothing faster you can do just receive the transaction and execute it or put it in the execution but it comes with some disadvantages also and the biggest disadvantage is

that it creates the latency competition so transaction centers are trying hard to be fast and in case of traditional Finance we know that there is this whole industry high frequency trading and it constitutes more than half of the exchange volume so it's a huge business in case of blockchains it was acknowledged only very recently in 2020 in flashbots paper and then there is a company flashbots around around that too so we think that it's only the front running that is a bad activity and we want to prevent it but back running is a good activity because it corrects the

price in the D5 on a automated market makers and we can support it or whoever wants to get that arbitrary opportunity should be able to or whoever has the highest value for it okay so this latency racing also exists in rollups because it's all of them use first come first serve policy and we noticed that participant resources to get closer to the sequencer and the problem is that parties with more resources have always an advantage so they always win all the races and

this is problem because they are not necessarily the ones that that value the transaction fast inclusion the most so it can be someone who has less resources but better algorithm or you know better liquidity on different in different pools and can extract more value so it's also inefficient and from the protocol perspective it's complete waste because they spend resources to pay I don't know Amazon servers or some other servers or improve their internet but no resources goes to protocol and one example that was observed on arbit room is that parties create nodes a lot of nodes and connect it to

sequencer for the feed just to get feed faster than others because sequencer uses the fair feed policy which is random so whoever has more notes has higher probability to get the feed faster and these too many nodes are necessary notes slow down the sequencer so this is also a problem for the roll-ups and of course it would be much better if these resources are at least part of it captured by the protocol and this could be used later to subsidize the regular transaction fees or used for the maintenance and Improvement of the infrastructure so there are a lot of properties that we

ask for the new proposal so first two of them are more informal so we want to have good properties that first come first serve has which is low latency of course and some level of transparency and we want to reduce the waste that is caused by latency racing more formally we want to maintain a dark man pool so transactions are not transaction details are not visible until they are already scheduled and once they are scheduled then there is no problem so we want low latency so we don't want to

makes transactions especially regular transactions wait a lot so once the transaction is submitted and received by sequencer it should only take some short time bound to be executed so one more property that is maybe more exotic it's independence of irrelevant transactions and this means that we don't want two different races to interact with each other so any complicated algorithm that you may come up with we can prove that this will have this problem that it won't be independent of irrelevant transactions so different traces will affect each other also we are looking for the algorithm that is easy to decentralize

so it's stable after decentralization so it should not be something very complicated and actually turns out that third and six uh coming together in the dark mindful solution which we achieved by maintaining a community of sequencers and threshold encryption so for that we need to have some number of sequencers and this needs to be typically low number so between 7 and 16 we are thinking also we need to have this threshold encryption decryption so every sequencer only holds some share of the secret key and we need the some threshold of them to come together

to decrypt the transaction contents so we want it to be Byzantine fault tolerant namely assume that sequencers can be arbitrarily malicious and network to be asynchronous so the only assumption is that once the transaction is sent it will be delivered at some point but we don't make any assumptions about how long it will take of course higher end gives us more security because we then need more people to come together to decrypt transactions but it's also getting much slower so we cannot increase the number arbitrarily also there are other condition considerations why we don't want too many sequences so informal description of the algorithm

is that we want to mix the timestamp so arrival time with beats with a simple logic higher the beat faster the transaction needs to be scheduled and also lower the timestamp it should also be executed faster okay so if we take so if we mix bits with the timestamp this will motivate the senders instead of spending resources on the latency Improvement which is quite expensive instead of that stupid also we want to guarantee that node transaction can be output by any other transaction if G time passed so

you cannot buy more Advantage than G and G we think to be approximately half second so that's in maximum what we add to the latency and we believe that human users will not notice much difference but of course Bots and programs will see a huge difference okay so our algorithm is my opinion very simple and it also has some fairness guarantees it has all economic properties of first price all pay auction so all payment option means that you cannot

take your transaction back if you don't like the position of it so once you bid you need to pay for it even if you lose the spot you want it so your transaction is not the first in the race and yeah it's incentive compatible in that sense that if you beat more your transaction just gets earlier and in case of back running that's all you care because in front running you also care that transaction that you try to exploit comes in between your two transactions but here it's only about back running so you just want to be as fast as possible okay so we don't want to discourage people to send transactions earlier so if you sent earlier you should get some

Advantage but if buying time is not too high then you prefer to maybe wait slightly and then buy more time so priority time and we think that it gives chance to players who don't have high budget to have low latency because it costs a lot to sometimes at least win the race especially when the evaluation is high okay so with our algorithm we also avoid a situation where there is a transaction that beats low and right after it there is a transaction that beats High and the high transaction is executed later and this you cannot avoid as soon as you

have block based approach because if you have a Blog based approach some transaction just makes it in the previous block and then there might be very high beat transaction that comes quickly after but it makes to the next time block but with our approach we have this continuous time so we don't get such situations now of course we care about not sophisticated transaction centers because they constitute more than 95 percent of the transaction centers or maybe even more so when they send transaction and beat nothing the their transaction will be executed in at most G delay or more

precisely after G delay okay now more formally about the algorithm we have a stream of transactions so it's continuous time we don't have a time barrier there so the transactions just come one by one and we maintain some score of them but to calculate the score we look at the timestamp that sequencer writes on the transaction so the time that sequencer received it and bid that is denoted by bi so then we calculate the score SI and post the transaction for the execution that has the highest score and no transaction has a potential to Output it

so that's also important so now what is the score function we have a function for the priority time which is G times B divided by bit plus constant so for this talk assume that constant is one but this is set by a system and can be updated as the system goes so if you think about cs1 ethereum so that would mean that one ethereum buys you 250 milliseconds extra which I don't think you can buy by improving the latency so I guess with latency Improvement maximum you can get

maybe 100 milliseconds okay then the score is the priority times minus t or if you look at the Dual problem it's timestamp minus the priority time but because we call it score we want to maximize it so this is the negated value of updated timestamp okay so first the result is that the only algorithm that satisfies independence of irrelevant races is the one that looks at the score function so no other algorithm or any other algorithm you come up we will come up

with an example that it doesn't satisfy this property well of course I didn't show why that particular score function is the one because we could be just looking at the timestamp that would be first Confessor we could be just looking at beats that would be a bit weird because there is some time so there must be some at least waiting time well of course we can have block based approach where we look at all the transactions that come in some time interval and sort thereby bits okay or we can be looking at any other score function but regarding the choice of the function that we have so first we have normalization so we have few properties

so if you beat nothing you don't get any priority okay this is very intuitive second was that property that no matter how much you be you cannot buy more than G time so that's the second property we want it to be increasing so more you beat more priority you get and okay so the last property is the concavity of the score function so this is more technical or the it implies the convexity of the cost function which tells that at least in our modeling if you want to have equilibrium where higher valuations bid value you need to

have some some convexity of the cost function okay if you take these properties into account I think that the function that we have is the simplest one but if you have some other suggestion for for a simpler function I would be very happy to hear from you okay so algorithm I briefly already discussed but here it's more explicit so we are posting the transaction with the highest cost as long as there is no uh potential for other transaction to outped it okay complexities are very good here space complexity is linear so we just look in some time interval

to the transaction so we don't construct any additional table and runtime is n log n so as fast as as it can be okay fastest would be linear but we need to at each step find the transaction that has the highest score so for that this uh we need this additional Factor logarithm okay now let me go through some economic analysis Suppose there is some Arbitrage opportunity and Players let's say we have two players they need to decide on the technology latency technology and later maybe about the

beat okay Suppose there is this cost function C that depends on the time and of course lower you want the time so faster you want the transaction more it costs and these two users have some valuations for the Arbitrage and in principle they are different but we assume they come from some distributions of valuations okay so now we take the cost function that is 1 over T but actually it doesn't really depend on the functional form here what matters is that if you want to be right after the opportunity arises so your time is zero it costs Infinity so you cannot be

physically speaking right after the opportunities there but you can get arbitrarily close you just cause arbitrarily much and evaluations are the same distribution for both players but here also we can look at slightly different valuations also yeah big assumption here is that we assume the independence of valuations okay so there are two models that we look into in the first one players invest in the latency before they know the Arbitrage opportunity valuation and this is the most realistic one first you set up your system and your

infrastructure and then you learn about valuations from time to time but yeah so here we should think that after some time you need to change it to so it's not for forever so it's not one time cost you in Korean that's it so technology changes maybe sequencer move somewhere else so you need to change it only lasts for some time period okay and in the other we look at the model where you can invest in the in both the latency and also bits after you learn about um opportunity okay so this uh maybe less realistic but there are some cases where for example

there is this 12 second block time for the ethereum and you saw some transaction that you know if it will be executed you have some Arbitrage opportunity therefore you can condition with some service provider that if this transaction is executed in this or included in the next block then I want my transaction to be very quick so that would correspond to that case okay but in both cases bidding is interim activity so you bid once you know the evaluation okay so this is a very simple game first we look only to the latency investment

game where more you invest better your time is so your strategy is how much you invest and if you invest it more than the other player you are the one that wins then the the expected payoffs are written here and this is this game has only one so it has maybe many equilibrium Solutions but in any equilibrium solution the expected payoffs of both players are zero so they completely exhaust each other thank you okay now a slightly more interesting case is if one has lower budget than the

other situation changes again we have maybe multiplicity of equilibrium but in each equilibrium the weaker player gets expected pay of zero and the stronger player gets positive payoff and this doesn't change so this is quite robust so the one that has more resources always wins basically okay so it's not in this equilibrium it does not always win but it makes the weak player win only very seldom and the expected payoff is zero while its payoff is positive but these changes with the bidding

okay so now we add this to the model bidding suppose in the first round they invested some levels X1 and X2 then we know how much it costs to produce some score Sigma so that's the score that I was talking about okay now the players solvent optimization problem so they try to maximize their expected utility and this is done by first order condition and in the end we get a system of differential equations

so the functions map valuation into bidding or the other way around this signals into evaluations and we are not able to solve this system of differential equations analytically but we can derive some properties first case is very simple if both of them invested the same in the first round then we can even explicitly solve the functions and in particular we show that there is a completely separating equilibrium which means that as the valuation increases bid increases so we know exactly what was the

valuation depending on the beat and they bid in every case okay and gets much more complicated if it's asymmetric so if one player invested more in the latency in the first round then there is some threshold below which none of them beat so there is a pooling there is no separation here but of course the high low latency player wins or high investment player wins but as soon as we are above this threshold they start bidding and from there on we have full separation equilibrium okay so this is more formal result we can even find what is this threshold it

depends on the difference in the latency and on G and yeah so it's a lot of discussion here but I don't have time for that main takeaway is that if we take G large enough it approximates the good case where we have completely separating equilibrium so in the future work we are thinking to add more players which should not be a big problem at least the insights that we obtain should generalize also we are thinking to have more general cost function that should also not be should not change qualitative results but of course it will change quantitative

adding dependent valuations is also not very difficult also we want to estimate evaluations from the data instead of assuming theoretically that they come from some distribution and actually there is a lot of data about valuations we try to compare it to the other Alternatives and the first alternative is of course block based auction so we just take some time interval and sort them beating that time interval so we want to have some easy algorithm to update the parameters especially C so if C is small enough then we need to

increase it because it's too cheap to buy the data and if it's too high we need to lower it because it's too expensive to buy the time and G may be not in the beginning we think that half second is the good trade gives a good trade-off and also we are interested in implementing and experimenting The Proposal if our assumptions were correct or what can we improve about that so thank you I'm out of time [Applause] so I'll stay around a bit so you can ask me questions thank you