On the Welfare of EIP-1559 with Patient Bidders with Moshe Babaioff | a16z crypto Research Series

Transcript

Welcome everyone to today's A16Z crypto research seminar. Very pleased to introduce Moshi Babayoff who's on the computer science faculty at Hebrew University. Um been working in algorithmic game theory and sort of cseon for a very very long time. He also actually wrote one of the kind of the earliest academic papers ever on sort of blockchain and bitcoin specifically. But today he'll talk about some much more recent work uh on EIP559. So Moshi, >> thank you very much Tim. I'm delighted to be here. Thanks for inviting me. So I'll talk about the welfare of EIP1559 with patient biders and this is joint work with Nom Nissan and uh please stop me with questions at any point.

Okay. So you all know Ethereum it's a you know one of the biggest second biggest blockchain with and it has a large volume of transaction fees and we will be interested in transaction fees the EIP1559 is currently this mechanism that is used to set for setting transaction fees in Ethereum and it was adopted without a formal proof of performance strategic or welfare for performance and prior work by team and others shows a nice strategic properties of this mechanism. And what we are interested in is trying to understand welfare properties and we are going to focus on

on algorithmic welfare properties without taking into account strategic behavior and pro try to prove that uh it has good strategic welfare properties. Okay, I'll give a brief introduction. Everybody knows about that but just that will be on the same page on the models that we use because our very various models. So we think about users that are submitting transactions. These transactions actually will have various sizes and values and uh then the validators are going to put those transactions in block throughout time.

Right? So that's kind of like the standard blockchain uh setting. H so each user has a transaction. Transaction has a size QI and a value vi per unit per unit size. So the total value of the transaction is vi * qi and there are there are blocks each block has a limited space and there is this meool that uh holds holds all these transactions that are pending and the validator is going to decide which transaction are going to be included and uh the mechanism determines uh also the payments inclusion and payments. Of course, we cannot pack more

than the space that is given to us and both users and validators are strategic in general although I will not spend much any time talking about strategic properties. Okay. So the classic Bitcoin solution to this problem is that the miner the validator or the minor is chosen at random solving some kind of hash puzzle and there are bids. The bids to be included in the block and these bids are to be paid to the minor. This of course will create strategic uh issues and then uh the miner will basically do the packing problem try to maximize her revenue subject to the constraints that the packing of the packing constraint

and we all know that greedy by density actually gives a good outcome if there are no huge uh transactions and the point is that uh the only reason not to include some transaction is that it just it just doesn't fit. There is no more space for it. And if it happens that the values are aligned with the bids, then it will also maximize welfare approximately. Okay. On the other hand, the 1559 EIP559 FE mechanism is slightly different. It was designed to overcome strategic behavioral and that and there are other changes. So one change is that it has this variable

block size. So the size of the block can be at most twice the target size B and then it specify the payments for transactions. The payments to the miners and some payments you all know are burned in order to create the right incentives. So you can think about this uh mechanism as kind of dynamic price mechanism for job scheduling in which there is a price per unit and this price dynamically changes according to supply and demand. Right? So I'll be more specific in few minutes. So kind of like the first approximation is that we have a block a target block size B and then we're going to have a price at

each time T. That's the base price. So the price that you need to pay in order to include one unit in the block and each agent is each user is going to specify the maximum price that she's willing to pay per unit BI and if your price is higher than the base price that then you can be included in the block and all these payments are going to be burned in order to make sure that the incentives for collusion are not uh are not there and crucially the payment H is updated at the next round using the following formula. So PT is the price at the previous round and QT is the total capacities that was actually used by

transactions in the previous round. So the next price is going to be the previous price times 1 plus some change the increment. So there is this parameter 1 over8 which is kind of the rate in which we change prices and uh this is multiplied by the quantity that was scheduled minus b over b. So you can essentially see that if the quantity is above b then the price is going to increase. If the quantity is below B then the price is going to >> you got it right >> got it right >> decrease >> yes and if it's a right on target the price will stay the same a little bit

more details about this story so now we're going to have instead of only target of B there is also maximize maximum size of 2B and then transactions can also specify priority tips and these tips will be paid by them if uh if they are included. It's kind of pay your bid. Then the question is what happens if there are too many bids that uh even for this 2B. So even 2B is not enough to include all bids then essentially the validators can do anything. uh maybe he would like to maximize the total priority tips but we are actually not going to assume any specific behavioral

he can do anything there is first the model of impatient biders so they essentially submit their transactions if it is not scheduled immediately then they leave you cannot schedule them later and assuming that the validators are myopic that is they don't h speculate about being validators was in any future round. Then there are nice strategic properties proven by team and others. Okay. We on the other hand look at the at biders that are patient. So essentially a transactions that arrive to the meool stays there and can be scheduled in

future blocks. So this is kind of corresponding to patient biders that don't lose value if they are scheduled actually not in the first block but in rather in later blocks. So we are going to study the the protocol the AAP1559 when biders are patient in the sense that uh transactions may be included in any future block with no value loss. Okay. So of course that's kind of like a simplification and later in the talk I'll talk about partially patient agents in which they might actually discount time or or lose value uh lose value at some point but for for now let's

think about patient biders. >> I think maybe Scott had a question. Uh quick question, sorry. Should we think of these like bit the set of patient biders as being sort of fixed or is it indogenous? Like it sort of are we going to see more people becoming patient if the system is allowed to to serve them in a in a way that reflects their patience or is this sort of these are like a stream of biders who don't really care when their transaction is processed. There might be other stuff going on, but they're sort of an exogenous group. >> Yeah. Yeah. We think of them as exogenous. Everybody everybody is kind of fully patient. You know all all transactions sit in the meool and you know you can schedule any transactions that is in the meool. We're going to ignore incentives and assume that we

know the true values per unit of the agents. Regarding validators, we are going to assume that they behave adversarially. So they can schedule any subset of the transactions. The only assumption that we are going to make is that they always choose some maximal by inclusion set of transactions. That is if transactions are not included in the block, it means that there is no space for them. Right? It it is never the case that the transaction will be in the meool and there is space for it and the validator did not include it. In particular, if uh if the validator is myopic, it makes sense for for her to actually not leave any such transactions

not uh not included. So I mean I get there will they'll have to only transactions that bit above the base fee eligible I assume or >> eligible to yeah to enter >> right because like >> out of these out of these that are eligible >> the the validator never leaves any of them unallocated. If if he can fit another one he would fit another one. >> Right. So you don't rely on validators to do screening by value beyond what the base fee already does is the point. Okay. >> Exactly. And we think of it as impossible for them to do or they have kind of like side incentives not to do it or you know there might be reasons for them not not to sort for example according to value right because maybe

the tips do not align with the values or something like Also like for the positive results it's only more powerful right you say you get the welfer guarantees even without assuming that they try hard basically right >> al although you know we will uh as you see we have some resource augmentation and this size of augmentation like proving that it's actually needed is kind of relying on the fact that uh you know you might not be able to to schedule say by sorting >> I see so looking ahead some of your negative results perhaps could be evaded >> exactly >> by assuming validators more >> in particular I'll show you that the online algorithms that is able to sort can have much shorter augmentation.

Okay. And we'll be interested in the social welfare. So we said that the value of transaction I to be scheduled is the quantity times the value per unit. So if it is included, it is added to the social welfare. >> Excuse me. What is Q? Can you go back to the previous slide? What is QI? >> So that's the size of the of the transaction times the value per unit. So if your size is half the block and your value per unit is 10 then your value is five. [snorts] >> Is the value is that the same as gas within value is >> it's in gas per unit of size. So you know you you are taking

>> if the ex execution time is not deterministic does does that mean the the the value has to be uh I mean this is making some assumption about a program whose running time may not be deterministic right it's it can have different branches >> okay that's beyond the model as we think of it the model that we think of it is that each transaction has a size that you know they want to take a deterministic size inside the block. >> So it's fixed >> it's fixed it's fixed is exogenous and it's known to you know it's known there's no no issues like that. So let's first discuss some basic properties of

this protocol. So we said that we are going to have variable block size. So there is a target size B and there is the maximum block size that is twice B. So I'm actually going to use a parameter C and uh for EIP1559 C equal 2. So that's the maximal size that we can uh schedule. And here's the protocol more formally. So we around we have a time time going one two three at each time the the validator is going to pick a maximal by inclusion set of transactions as long as the value is at least the price and he cannot he

cannot violate the the hard constraint of C * B but it can schedule more than B and then the price at the next round is going to be the price in the previous round and now instead of 1 plus X we approximate it by it's essentially probably what they meant to do e E to the^ of X. So it's exponent of T to times this uh ratio when QT is the total size that was in block T and we don't allow the price to drop below P min. So there is like a minimal price and if the price end up below it we round to this price. Think of it as the minimal values that we are interested in kind of. So you see that essentially now the the

protocol has five parameters. The block size, this multiplier C, ETA which is 1 over8 for the usual protocol, but we think of it as kind of a small parameter that can change. Just one second. P mean is the minimal price such that the it never drops below it and P1 is the first price that we start with. Yes. >> So when you say maximal by inclusion, is that maximizing social welfare or maximizing profit? No, it's just maximized by inclusion of sets. You know, it there is no element that you can add without removing anything and without violating the constraint of of C times B. Sorry, >> I don't understand what it means by

maximizing that. Are you maximizing the total amount of gas? No, I'm just saying that if you know some set of transactions is a smaller than C * B and there is another transaction that I can add then I add it. >> So, so, so there's like if there are multiple possible maximal >> you can do whatever you want. the adversary will pick you know any subset. We we assume that the only assumption is that the validator never leaves a transaction out if it can add it to the current set. It's a very weak assumption. So note that I said that it has a target size B but actually I'm

allowing to schedule C * B. So you know why won't the the mechanism essentially schedule twice B every round, right? In what sense is this the target block size or the average block size? So we we first formalize this. So we say that a schedule has average block size B with selectness delta if for every k transactions the total capacities that we use is k * b with [snorts] an error of delta. So you know you have you allow some slackness of amount delta beyond the k * b. So if you have 10 blocks, they should include 10 10 * B capacity up to an error of delta x B. And the theorem says

that if the values are in the range L to H, the value per unit and we have this parameter ETA and we use the price adjustment formula as EIP1559. then it actually produces schedules that have average block size B and the slackness doesn't depend on K. Okay, so it's a constant that depends on the parameter ETA on H and L and on C but it doesn't depend on K. So that's the theorem. Let me h prove it to you. So we want to essentially show that the capacities that is used in the blocks from I to J. So we have K blocks from I to J and we want to bound essentially

the capacity and show that it satisfy this average constraint with slackness uh with this slackness and the the ways that we do it is to look at the ratio between the first price the final price and the first price. Okay. So we uh this ratio you can look at it as kind of a telescopic product and Can I I mean I can can I clarify the theorem statement before you go into the proof? >> Sure. >> Is the theorem statement just is is it like saying greedy algorithm has like some approximation ratio like in terms of how the packing is it more like a packing theorem. It seems to be

analyzing some greedy packing strategy. >> No, I don't think so. I think I think the the the point here is that you know we want to show that although this protocol can schedule twice as much at some rounds this cannot accumulate accommodate accumulate too much right it cannot be that we are like on average scheduling 2B per per unit we are only scheduling B per unit and the what about under what what circumstance can it schedule to be I'm just confused about the nature of the error So the the protocol as you can see is allowed to schedule up to C * B and C is two. So it can it can schedule twice

B at every round. Right? Essentially but you want to show that you know it doesn't accumulate to twice B * K but only to B * K plus some error. So what is the intuition why it doesn't because like by >> so I I suggest we take it offline because I I have to continue and we we can discuss this offline. >> Okay. >> What's strange is like your protocol is always just trying to schedule to be. >> No, it's not schedule. It has prices and the prices changes and the quantities that you you schedule depends on the price. So once quantity is set, you can only schedule a transactions that have value above that price. You cannot schedule twice B. You schedule only

above that price. >> Also, not not you're saying not every transaction is eligible, >> right? Only transactions that have value at least the price. >> Okay. >> Okay. So, we're going to look at the ratio of prices between PJ and PI and we look at this telescopic thing. Why do we look at this telescopic thing? Because you can see that, you know, we have this ratio of PT T + 1 over PT which equals to this exponent, right? So this product is essentially a product of exponents and this product of exponents is of course equal to the sum of the exponents. Right? So we have this sum of the exponents and on the other hand we know that pi is

at least L and PJ is essentially at most H up to the last time that we might increase the price a little bit more. So we have this kind of like additional term here. Okay. So now we take a natural logarithm from both sides. So here we have kind of log h over l and this this h turns to this and then here we have this b and eta and here we have this sum of quantities that we actually want to bound. So we re reorganize we multiply by B divide by 1 / E eta and move this thing to the left. And what do we get?

We get that the total quantity from I to J is B * K. Essentially this is the number of blocks between the two. And here is the slackness which is exactly the slackness that I was arguing for. So you see that this slackness does not depend on INJ. It's independent of J. Yes. I I cannot understand the proof without understanding the intuition of the theorem. So as a sanity check uh let's say all the transactions um bit very high infinite.

>> So there is no infinite there is h which is an upper bound on the value. >> Let's see they're very very large. >> Okay. >> And then they all have unit size one. >> Yeah. So, so if say that everything is H and the price rises to H once the price will rise to H you will you will essentially E include 2B then you increase the price above H you have zero right nobody is willing to pay above H then you decrease the price to H you take 2B so you can see that you know one block will have 2B the other will have B on average you have B zero or 2B >> so this this requires like you're in a steady state because in the beginning when the price is very small and

everyone's being very large >> right exactly so so this this selectness exactly capture the fact that there is kind of like time in which it takes you to get from L to H at steps of size one /a so essentially this essentially captured your intuition your correct intuition that there there is some there are some rounds in which you accumulate too much but there cannot be too many of them this is kind of the bound of how many of them there are. Okay, so we've proven this theorem that says that the average block size is B with selectness delta for this delta.

Okay, so let's move to the main result talking about the welfare bound. >> Can I just have one question real quick? I'm just wondering how easy it is to generalize this result if I just have some general distribution over value values with some like expect expected. >> This is no there's no distribution. and everything was case. >> I know. No, no. I'm saying that the distri you said like all the values can be between L and H. >> Yes. >> What if I just told you like that uh every every person that comes along the pro probability that their val value is like expected say like L plus H O over two but with some tails.

>> Do you see what I'm asking? >> Yeah. So if you have unbounded supports I think you might be in trouble. >> I see. Okay. >> Uh okay. Okay. So why is maximizing welfare difficult in this setting? So first note that each block is kind of like an NP hard knapsack problem. Second we have kind of online algorithm. So you know we pack stuff without knowing what's the sizes and stuff that will arise in the future. And in a sense you know our result says that if you have this kind of like factor two relaxation on the hard block constraint you can overcome these two problems. And there is another issue that is significant is that this protocol is price based is it only sets pricing according to information that is

on the chain right and it cannot just do arbitrary things. So that will cause him to be a little bit too weaker than online algorithms. So let me now present the main result of the paper. So think about values that are between H and L approximately and the first price also start between H and L. For any parameters ETA and C and for every time no matter which time horizon you look at the welfare of this protocol up to time t plus gamma is better than the welfare of opt. So opt is kind of like the offline optimums that actually know

everything in advance but is still restricted to a maximal block size B. So the EAP is better than it up to this factor of 1 minus ETA. Okay. So first you see that this loss one minus ETA you know relates to this parameter the adjustment parameter of EIP1559. Second we have this gamma. So gamma now is going to be something like 1 / aa * lan h / l that's what we have seen before times some factor and also opt actually our result holds not only for the offline integral opt with maximal

block size b but also if we allow the block size b to only hold on average and allow it the allocation to be fractional. So I I'll talk a little bit more about the strengthening of this theorem later and let me talk a little bit more about the losses. So we see that you know as we make ETA smaller we lose less of welfare but we make gamma larger right so you need to wait more rounds till the price will adjust. Second, you know that the theorem holds for every t. So it should hold even for t equal one. And here you have this issue that you some many maybe start with very low price and you need to to catch a transactions that has very high

price. So this will result essentially in this loss of 1 / aa time log h / l right because it will take us this amount of steps to catch this very good transaction. And this one over 1 minus ETA essentially comes from this ETA adjustment parameter that you know we are not going to hit the right value. We have some uh slackness here because the adjustment is kind of like crude. And also note that this gamma depends on 1 / C minus 2. So in particular you see that when C equal 2 this is unbounded right?

This is kind of infinity which is kind of bad news given that C equal 2 is the parameter that is actually in use and I'll discuss that next. Okay. So our go back >> for a slide real quick back one slide real quick. Yes. >> I guess it was before that. So when you said you can relax the offline op to be just B on average that's still with a max of 2B per it still has to obey the does it have does it have any maximum on what it can do each time or >> no >> okay >> so what about this the case that C is smaller than two so first we show that not only price-based algorithm but also general online algorithms

are going to lose a constant factor if C is smaller than 2 and that constant is like the minimal of 1 / 8 and 2 - c over 3. So you see that the con so note that when ETA goes to zero we don't lose a constant factor right we can get arbitrarily close to one and this says you know h even uh if c is smaller than two you must lose a constant factor no matter how how small is and you see that when c equal 2 there is no loss here right and indeed for the case of sequel 2 we show that there is a competitive online algorithm M but the EIP1559 which is price based

actually is going to lose a constant factor and I'll if I have time I'll present that result at the end and also this thing relies on on transactions to be large. So essentially it it relies on on transactions to be as large as B. If h transaction sizes are smaller than some q max over time b then we don't need c to be larger than two. It's enough that it will be larger than 1 plus q max. >> So what is qmax?

>> Q max is the maximal size of a transaction. So there is QAX is one if the transaction can be as large as the of as the entire block and Q max is half if you can take at most half of the block but not more than that by one transaction. >> Okay. So the lower bound there so the statement is actually like no matter how much no matter how large a constant slack you get it's not good enough right because like you mentioned example with taking a to zero >> here >> uh the line above that prove a lower bound for an online algorithm with c greater than two >> yeah even ifa goes to zero I can always construct an example in which you'll

have a constant loss >> for a generic algorithm there isn't an ada right so I think what I think the statement would be that you know I give you arbitrarily large constant slack and even then you can't >> so I think it relies on the slack to be little of uh t >> okay so let me give you the full the full theorem so in the in the full theorem few things first the benchmark we can allow it to have average block size B with selectness delta prime by a loss of another delta prime in gamma. Right? So, so that's one thing. The second is that P1 the first

price might maybe be huge much louder than the values of uh of our transactions. So it will take kind of time P1 over P min for it to decrease to the right level of prices and therefore gamma might need to be growing at least as large as LAN of P1 over P min and also the ratio kind of depend on the actual value Vmax over P min not kind of the upper bound we don't need we don't even need to know it in order for this bound to And then we talked about this Q max. So

there is this parameter C prime which is C minus Q max over B. Now we need this one to be larger than zero. And then the implication is that we get this in the denominator here, right? Uh C prime. So that's kind of the adjustment to the case in which transactions are not too big. Okay. So let me give you a sketch of the proof of the main result. And we're going to start with an online algorithm which is simply the greedy by density. So this is the the algorithms that just sort the transactions according to density and greedily picks from the highest density to the lowest density and the algorithm is going to do so and at time t it will fill it will

essentially pick transactions up to the points that it is at least t. Okay. So it might be that at time t it's it's you know it's h adding another transaction that will cause it to be at one time one instead of taking transactions of size b it can take transaction of size almost twice b right because the last transaction might be of size b and uh we want to pass this parameter of 2b. Okay, so you can see that this uh online algorithm kind of have C equal to it might actually at the first round schedule twice the amount uh instead of B to B. And also we're going

to assume that QI is always at most B because the optimums that have a a a strict constraint of B can never schedule a transaction that is larger than B. Right? So we can assume kind of there are no such transactions. Okay. And what are we going to prove? We are going to prove that this online algorithm if we give it a selectness of one essentially allow it to run for one additional round compared to the optimum. It is going to beat the optimum. Its welfare is going to be at least as large as the optimum. Okay. So first note let's assume that there are always transactions enough to fill the blocks. Right? zero transaction

infinitely amount of zero transactions. We can always fill the blocks. So at time t we're going to have between t * b and t + 1 * b. Okay. So this kind of like give us some bound on the quantities that we are going to schedule. And we're going to prove the following lema that for any threshold theta. If we look at the quantity that the online algorithm scheduled from transactions of value at least theta up to time t + one it's going to be more than how much opted up to time t. Okay. So q theta of s1 to

t is essentially how much I I scheduled of value at least value density at least theta in schedule s up to time t. Okay. So if we have this lema then we can see that the theorem follows quite easily because kind of standard calculus say that the social welfare up to time t is just the integral of this quantity uh from 0 to infinity over all thresholds. And then if we combine the two, we combine these two, we see that it implies that the social welfare of online up to time one t + one is at least the social welfare of opt up to time t. Right? So, so that's kind of a

complete proof given dilemma. So let's now look at the proof of dilemma. Okay, let's look at the time and let's look at the price per unit over time. So that's kind of the graph of the price per unit over time and that's kind of the last price per unit of accepted transactions. So recall that the price is essentially the threshold such that every transaction above this threshold is scheduled, every transaction below this threshold is not scheduled and that ties can be scheduled or not.

Okay. And let's look at time alpha which is the last time in which the price was at most theta. If the price was at most theta, what does it mean? It means that every transaction that has value at least theta was scheduled, right? No matter what when it arrived before this time, it must have been scheduled, right? Because it is available to be scheduled at this time alpha. Okay? So all transactions with value density at least theta were scheduled up to time alpha. Now beyond time alpha the price was always above theta. What does it means that the price was always above theta?

It basically means that all the scheduled transactions are good right there. They have at value density at least theta. And how much of them did we schedule? If we allow the algorithm to schedule one extra step then it beats alg at the optimum. Right? The optimum could have scheduled t minus alpha amount and in if we add one additional step to the algorithm the quantities that we schedule is at least the quantities that oped good. So that's basically was the proof that one extra step was was enough for online algorithm and now we move to the

main theorem about the EIP1559. So recall that this is our algorithm. So now the theorem will be an adjustment of the previous theorem in which instead of one extra step we are going to give gamma extra steps. Right? Now one extra step will not be enough because we might schedule a stuff that is not very valuable because we cannot sort according to density. We take the the adversary is going to pick the set that is included. H but this gamma will be enough for the social welfare of the algorithm to beat the optimum. Okay. So again we look at we we prove a similar lema. Now the lema says

that if we look at EIP559 with threshold theta given extra gamma steps it bits opt up to time t with a small h change in the prices that is due to the price adjustment. Okay. So it's not theta versus theta but there is only a small adjustment. Okay. So we now look at again at this price function and we find alpha which is the last time in which the price was smaller than theta and every transaction of density at

least pt was scheduled. Okay. So there is no room to fit another transaction there. So what do we know? We know that up to time alpha, we got rid of all the transactions that have density at least theta. Right? So all transactions with value density at least theta were scheduled up to time alpha because essentially at time alpha we have space in the block and we didn't put anything. So essentially from this point onwards every time that the price was below theta it must be that the block essentially completely filled because if it wasn't completely filled then alpha

would have been bigger. Okay. So now we look at the time beta in which the price essentially reached theta up to this small arrow of e to the minus eta. So there is this time in which the price started to rise from a point alpha and it's going to reach essentially theta. So we first argues that this time interval is quite short right it's kind of like in each one of these steps the price must increase quite a lot. So we have kind of like a lower bound on the rate in which it increases.

And then beyond this point we know that all capacity was scheduled has at least this density. So this is kind of like similar to the argument before we have enough cap you essentially scheduled enough capacity from this point onwards. Okay. So the only thing that is left is that you know up to here we scheduled everything and from here onwards we scheduled enough capacity but there is this kind of interval between alpha and beta in which the optimum could have scheduled good transactions and we did very poorly and gamma is essentially chosen to be larger than beta minus alpha. So when we have this extra gamma steps at the end, we scheduled to

compensate uh the missing transactions for this time in which the price was rising and we didn't schedule anything good. Okay, that's kind of the essence of the proof. If you have any questions about that, okay, so let me briefly talks about talk about lower bounds. So our result does not extend to these more general models in the sense that a constant loss is unavailable again. So I we want one minus at a fraction and ETA can go arbitrarily small. So in these settings when there are multiple resources instead of just one or when

agents are partially patient in two senses either they discount time or it's kind of limited patience in the sense that their value doesn't change and then drop to zero right so I want to be scheduled in the next 10 rounds and then my value drops to zero in both those models we have a constant loss we show that there is a constant loss and then you can ask you So we saw that this gamma and delta depends kind of like on the ratio of H over L for EIP1559.

Actually we show that for all price based algorithm they must grow at least as large as log log of H over L. So you have you must have some dependency on this ratio in the slackness that you give and okay so let me formally >> do you know if you can get that on an upperbound side for a price based algorithm >> that's one of my open problems >> okay feels feels like you could >> okay so essentially what's going on here is that uh if you look at the scale of prices in the exponential space you have kind of log of h over l divided by one over eta scales so the ei P1559 essentially search linearly over this scale. He's kind of moving linearly. You

would think that maybe we can do binary search. We don't know how to do it. That's kind of like one of the open problems trying to design a price based algorithms. It's kind of doing binary search and then getting this extra log. >> What is a price based algorithm? I I don't understand. Pricebased algorithm is an algorithm that actually sets a price and only take transactions above that price and does not include transactions below that price. It's essentially the same as EIP 1559 but you can build a different function to >> right you can you it's more general the EAP1559 is 1559 is is kind of an example of a price based so this kind of result

says that no matter which price based mechanism you will use you will still have kind of like at least log log of h over l for gamma plus delta >> for for exactly e59 My log is is type >> for for exactly it you will need log of h over l >> type >> log okay log yes log of h >> upper bound >> yes >> yes and you need log and for for the more general case we have a lower bound of log log h over l but we don't have an upper bound okay so let's talk first about the discounting case so we have a discount factor row and if a transactions arrive

at time ta and but it is executed only at time t then the value is discounted by 1 minus row to the power of t minus ta right so that's kind of like if row is zero then the agent is fully patient as in our model row is one it is fully impatient so you know it lost value immediately and what we show so this is kind of give you the flavor of the low bounds the flavor of the Low bounce is that any online algorithm with average block size B and selectness delta ex an extension gamma where this is little of T.

Fix any H discount that is positive. Then you can mix fully patient agents with these kind of agents that have discount Roman and lose a constant factor. Okay, we can construct an example in which you have to lose this constant factor as long as this sum is little of t and to >> can I number where this 20 come from? Is it like is [clears throat] it like just some constant or it's like a tight I just wonder where this number 20 comes

>> one over 20 is just our example showing that uh you know you must lose some constant factors there exist a constant that is independent of ETA even if ETA is going to to to zero then still you will lose one at least one over 20 of the welfare some constant 5% of the 5% is loss is unavoidable once you mix fully patient agents with partially patient agents and we have similar result for the case in which the the p the value is constant and then drops to zero.

It almost feels like this should like if you can prove that you need the slack which is basically time to catch up. It almost feels like at least morally this follows, right? Like you need the catchup to get transactions that opt already scheduled. You're scheduling them later so you get less from it. >> Right. >> What is the discount ratio of zero mean? Why is this? >> So discount ratio of zero means that you have one to the power of something. One to the power of something is always one. So if row is zero, then it means it's fully patient. every time my value is still v. My value never decreases.

If row is one then uh unless this uh exponent is zero the value drops immediately to to zero. Okay. So to give you a sense of this kind how do we f we prove these kind of results. Let's think about let me show you that EIP 1559 loses a constant factor if we take C equal 2 and transactions that can be as large as the block size. Okay. So let's say that the minimal price is one and the block size is one.

So first let's wait to the price to drop to one. No transactions arrive. the price started decreasing till we have the price of one and then at every round we get two types of transactions. One we get great transaction that has size B and value 10 and then we get a bunch of low value transactions. They have only value of two and their total size is 1 plus epsilon * B. Okay, so we have 1 plus epsilon plus b bad transactions and one great transactions. So what would the adversary do? The adversary will essentially cause us to h to schedule these bad transactions.

So as long as the price is below two, only low transactions will be scheduled and the quantity of them is 1 plus epsilon * b. So there is no room to add another B because the factor is two, right? We're already at 1 plus epsilon. We cannot add another one. Okay. So it it leaves no space for this great transaction. Now let's look at the price update. The price update it sees that the total capacity that we are using is 1 plus epsilon* b. So, so sorry so this is where you're really using that all you assume is maximality on the included.

Okay. >> Here here in in some sense I'm I'm I'm thinking about an adversary that is kind of causing me to take the worst transactions that have enough value. >> So like a greedy validator would break this. Yes, >> we have better we have the online algorithms that is obtain is able to actually run with SQL 2. So an online algorithm that can do sorting can actually cope with SQL 2. Even even just vanilla EIP59 with sorting can do it or you need to like do some other tweaks to the algorithm. >> I did not check. My guess would be that it should be okay like once you have sorting you know life is very easy because you know what would you just lose because of the rounding but not more than that.

>> Okay. So let's look at the price update. The price update is kind of ETA times Q minus B / B which will give us kind of epsilon right. So it will take us omega of 1 / ETA epsilon steps to reach times two a price of two. So there are many many steps till we arrive a price of two. We can make it as small as we want right by by decreasing epsilon. So essentially uh given no matter you know how we set it if we take t to be z over two and we take gamma to be smaller than t. So we wanted gamma to be little o of t then essentially we schedule this

transaction for t rounds and then another bunch of these transactions for t rounds. So we get like 2 t * 2 instead of getting t * 10 right? So we are going to lose a constant factor. We lose half of the welfare and know that this kind of heavily relies on C being equal to T exact to two exactly right. This allows me to take epsilon to be arbitrarily small and for this argument to hold because if C was larger than two then this epsilon will become at least C minus 2 right kind of like we will not be able to take this to zero take epsilon to zero.

Okay, let me briefly talk about some open problems. So we didn't take into account strategic considerations. So trying to analyze welfare with strategic agents. Then h our our results for the case with agents with discounts is only for the case in which we mix different discounts. Right? So let's assume that all agents have exactly the same discount. Is it possible to tweak the mechanism in the algorithm to actually give positive result when we have agents that have common discount factor which seems like maybe possibly a realistic scenario and then I think we discussed that can we get little of log h over l

for gamma plus delta. We know that EIP559 needs this kind of log H over L but maybe other price based mechanism can do binary search or something interesting like that and the question whether a constant approximation mechanism exists when we have multiple race resources and partially patient agents was studied by Noam and his student and at least when the algorithm is an online algorithm not a pricing algorithm then they were able to achieve constant approximation.

Okay, so let me summarize. We study EAP 1559 for Ethereum, the pricing uh scheme. We said that there are challenges like NP hardness the online challenge and the pricing based the fact that it's price based and we show that we when we have patient biders if we make two relaxations essentially allow the average block size to be B not the worst case and also give some resource augmentation and other gamma steps then we can actually compete with the off offline uh offline opt and uh even fractional and we show that constant loss is unavailable under a various

extensions of the model. Thank you. >> So do you ever consider the problem of like if you fix the um like max block size um but you're forced to use a price based mechanism um do you know what like the optimal C is for welfare in that case? >> So you're allowed to use an arbitrary online mechanism. >> Yeah. or even something like uh either arbitrary online or even just EIP 1559. So I guess the the reason I'm asking is um like there's some sense in which like the actual max throughput you can handle like is actually 2B like you could handle that on average but you still need some slack for a price based

mechanism to make sense right like if you just let the value always fill up to 2B then there would be a well- definfined price like there'd be no way to set the next the maximal to be as as large as 2B. >> Well, so something like fix fix the maximal basically. >> So the maximal Okay. >> And then you're allowed to pick like a target that has to be less than the maximum or else you don't have a price based mechanism anymore. >> Mhm. >> And is there a sense in which we can pick an optimal target? >> So So in a sense the C equal 2 hits the target of B. If you take C larger than two, then the target will be larger than B. the target is kind of like the the the average is actually moving when you increase C.

>> Maybe another way of saying it like to map it on a practice, right? Like the hard there's some hard constraint on the max block size. >> Mhm. >> Right. So that's actually kind of like the primitive of the model. >> Right. >> Right. And then what you have full design control over is what's the target. Right. >> So it's kind of looking at it the reverse direction from you. Right. So I think >> I see >> correct me if I'm wrong but I think Vernon's question is like it would be really interesting if like a welfare analysis actually suggested how to choose the target size as a function of the maximum block size. >> I see. Okay. We we did not study that but I'll be glad to chat about that. Thank you.

>> All right. Thanks, M.