Does your blockchain need multidimensional fees? with Noam Nisan | a16z crypto research talks

Transcript

very pleased to um introduce uh this morning's speaker uh nom Nissan uh who's at Hebrew University in starkware uh G sort of remains to this day a legendary complexity theorist but he also has then in the last 20 years become a legendary mechanism designer and now in really really really good news for the web 3 space he's spending some of his time thinking about um issues here and today he'll talk about uh multi-dimensional fees so no all you thank you okay so H I'm going to present more more or less work in progress that I'm doing with the males Pai Max Resnik and N L we're starting to think about questions of multi-dimensional mechanism

fees in blockchains and uh but we're one step before that trying to figure out before you start doing a mechanism design how exactly do we sell things H there's a preliminary question of what exactly are you selling and we're trying to think about that so I'll tell you the way we're thinking about it the way I like to think about it and we have a few nice but easy results H but like uh I'd be happy to hear any feedback about the whole way that we're looking at things so why do we even need me Fe me you know fee design or fee mechanism design in blockchain chains because the blocks are limited right in a blockchain we have a bunch of blocks at each point in time

and let's say focus at each point in time we have a block and you know we need to decide what goes in and because a block is limited then we need some kind of the some kind of pricing mechanism to figure out who gets in and who gets out and who is left out and why is a block size limited so basically underlying it there are some technological constraints that we want you know miners or sequences or verifiers or validators whoever there is participating in running the blockchain to be able to do what it's need what is needed to be done mechanically or you know computationally within a certain level of resources maybe we want a PC to be able to run a full node maybe and so on and that implies some kind of

constraints and how complicated how big the blocks are and so each blockchain when it design designed a system it figures out what are the constraint on the Block side and that are needed in order for you know enough participation from whoever is supposed to run this block okay and once we have this limit on the Block size then of course we need to sell this block size because this is now the resources this constrainted so let me give some examples of the notion what exactly is the size and maybe I think the historical the early historical ER you know way that these were defined is probably the most enlightening so the original blockchain was very easy a

block is 1 Megabyte original Bitcoin okay we have 1 Megabyte one megabyte you know we can send it to each other on time everything see seemed completely fine so that was very nice of course one megabyte may not be enough there was more demand than one megabyte per block and sometime around the 2017 they figured out that not all btes in a block were equally difficult to handle there were this part of the block which is called the witness where you really really didn't have to put it into the I don't know your hash tree or whatever so it was much easier to actually handle that part of the block btes of that type relative to other blocks btes which you really needed to

handle and and you know hash them and so on so they had this upgrade upgrade or you know hard Fork whatever you want to call it uh to bitcoin that basically said okay BL bites that are in the witness part of the block only count as a quarter of a bite and now we have this notion of weight where a weight of the of a bite in the original thing is one and in the new thing is a quarter and now the block size is now set to one megabyte of about of this virtual by size okay so in particular if you look what happened that b effectively increased the size of the blocks by about 70% okay simply because something like I don't know 50% of the

half of the blocks were of the witness type rather than the original thing okay once we got to H to ethereum a very you know very long and sophisticated menu if you wish for each type of operation that theum could do for you how many bytes or how many gas is that cost does that cost right so there was a very long table this is a few lines that I had some operations are very easy like addition or loading from local memory of the local memory and some of them were much more expensive for example storing something in the global memory if you wish in the state of the system and of course there were about I don't know maybe a hundred different lines of various operations

that you could do and how much each one of them cost and then the there was this H you know this was a gas cost and this is how we like to think about it now in general there is some kind of gas measure a block can be at most 15 million gas and a gas is calculated according to each operation how many gas does it take and once you have you know this gas measure once we have a size so each transaction has its own size and you have a size limit on the complete block then you need to of course somehow decide how do you allocate the 15 million gas units of the block amongst the different transactions each one with its own size and you can do a pay your bid like in Bitcoin you could do a sort

of fixed price you know with some complications that I don't want to get into like in ethereum and in both cases the underlying clever algorithm is the following you sort the transaction by the price per unit and you take it greedily from the top down okay very simple algorithm very uh clever I would say h the right way to look at it probably as like this is like the integer programming relaxation so the linear programming relaxation if we were allowed to take fractional transactions that would be exactly perfect exactly the last one we only take a fraction H but because we're not allowed to take fractional transactions this is not

perfect but some kind of approximation the exact level and meaning of approximation it does not important but I do want to note that this is algorithm that's used and not for example the one you know uh some kind of polinomial approximation skin you can do this kind of problem there is a better algorithm in terms of formal you know getting approximation up to 1 by Epsilon but no one is using the other one because this one looks much better not only is it much faster it also plays nicely with the notion of that that we think there should be like a price per gas and this algorithm really works well with this notion and the real approximation algorithms don't so in general this is what is

done okay so far we're on the same page I mean I guess it's worth saying so I mean that's what's done in like the reference client and like the major ethereum clients for example like it's not part of the protocol description I could write my own one that did a better algorith if I wanted absolutely absolutely that's completely true this is the algorithm that we suggest I don't know of anyone who does something significantly different except for you know when they want to do me or other other considerations that don't fall into this the bids but are these really this really the way to represent the constraints that our blocks have right just finding a gas measure and we can't have more than 15 million gas in a block and re really what happens is you know

it's a computer system complex kind of system with many different parts of the system are different constraints of the system and each component of the system has its own constraints each uh aspect of running the system there are own constraints okay so for example we can say that oh I want you know the time that it takes to create a block to be at most 6 seconds but I wanted the total number of bytes of the of each of of that in a block I don't want it to be more than three gigabyte or megabyte or kilobyte it doesn't matter it's like because you know these are the two different concerns I don't want I can't have my blocks too big because otherwise I won't be able to send them with enough

communication you know with the current communication uh infrastructure quickly enough and I want a time to be fast enough because otherwise you know the blocks won't just won't run on time so in general in general if you have a complex system there are multiple constraints and really the correct constraints that you really have in a block are like the conjunction of all the different constraints that everything should work you know everything should work together in the correct amount of time and the correct amount of constraint otherwise you will not be able to handle the block so this is more realistic description of what the real constraints on the block are if you actually move everything into a gas constraint it's meaning what it means is that you're somehow count something and

doing like a linear bound on that something then really instead of actually capturing this space of possible blocks you're actually allowing yourself also to only to to catch this triangle your space of the blocks which on one hand you're losing a lot of possibilities that your system really can run this thing but you're not allowing yourself to do that and on the other hand if there are pieces of the triangle outside of the square if you get a transa a block of this form then you're really in trouble because you know your system if you wish cannot really manage it well okay so actually doing this approximation is sort of problematic just having a single gas measure is problematic it doesn't really capture the constraint of the underlying

system also having a gas measure does not capture the following at least two types of constraints if you wish that you have H that are not really naturally captured in terms of gas so the first one is that some resources really imply a cost to the system but really are not constrained so a good example of that is data availability cost for for layer twos so if I'm running a layer two blockchain I have my own constraints various type of constraints and speed and so on but usually transactions that have data that needs to be put somewhere in a data availability layer for example on the underlying blockchain below a lot of times there are no constraints I can handle as much data as

I want to these constraints are not as significant as the total constraints of running my system but whenever I put them somewhere I need to pay for it for example if I put it on blobs let's say in ethereum or used to put it on call data in ethereum this is an actual cost that each transaction that uses I don't know five byes needs to pay for these five bytes and you know someone needs to pay for that okay so these are the kind of things that are not constraints but really you need to to worry about because these are actual costs that are going to be born by the system and should be passed to the transactions so that's one type of thing that you need to worry about and of course sometimes what you could do is you can try to

translate these to gas but that's inefficient because why are you putting constraints that you shouldn't put why is the price of these things cor be somehow related to the price of gas currently which corresponds to current to the current congestion rather than the underlying cost which is really what's going on so you're going to have some both the you know technical and the economic losses here the second type of constraints that are not captured by this gas measure is the long-term constraints so the classic example is a that of State in blockchain so probably the main worry today of eum is that it states really grows very quickly and that's a significant

constraint but there is no way to capture it within the gas measure the amount of money that you're paying to ethereum so today you are paying a lot of money basically for New State okay but that lot of money is on one hand maybe not enough to get the bound that you want in the long term and on the other hand maybe be much too high whenever you have like local congestion so sometimes you have congestion this minute and the price of gas really goes up so the price of new storage really goes up but it doesn't make any sense because storage only you worry about it in the very long term is a level of years okay so basically if you translate long-term constraints into normal gas

constraints you're really in for trouble you're losing a lot on efficiency H you're losing most more than that even an economic efficiency so okay so and the way that the block that you know ethereum handles it now is is really bad and we all know there were these examples where actually people bought gas when prices when bought storage when gas prices were low and gave it back at the time you could get a significant refund where if you get when prices were high and actually made money sort of used it as a gas token okay so that these are other constraints that simply don't fit into the normal single gas measure then what do you want to do the natural thing every Economist should know we have different types of

resources you know count each resource separately price each resource separately and that would be excellent because now you're giving the correct prices you're actually modeling correctly the underlying cost and constraints of the system you're handling them correctly economically so everything will be perfect okay and this is a if you wish the promise of multi-dimensional fees you decide in a different dimension and each different resource it constraints your system you price it separately and uh then you're happy okay but this is more complex than it seems okay it's obviously complex intuitively you have different prices

even now in ethereum where you have like two resources you have these blobs and you have the normal gas already it's a bit complex but there really some underlying difficulties under leas and I like to really pinpoint two complications which are really difficult to think about okay so I'm not saying that you know this complex means you can't handle it of course and there are many people exactly working on handling it but I just want to give two uh types of problems that you have with actually handling this complexity the first one is your underlying algorithmic problem becomes much more complex much more difficult so instead of just you know fitting a single gas measure like a single dimensional knapsack which has a very

nice algorithm for approximating now we have a what's called a multi-dimensional napsack I want to find you know XI is going to be the indicator variable whether I'm taking transaction I or not so I'm trying to maximize the value of transactions that I take subject to the constraint that for every resource I don't I don't go above the bound the the bound and the number of and the size of that resource within a block right so that's a multi-dimensional so it's of course NP hard but it's a more difficult NP hard if you wish problem in practice than the single dimensional one and for example one thing is the linear programming relaxation euristic we know

is very good in a single dimensional case we don't really know that in the multi-dimensional case okay so how good is a single dimmen is a relaxation you know that's sort of a ursic empirical question also somewhat theoretical it's not clear also while you can solve these LP and this is like not a completely General you have a small number of constraints it's not going to be greedy anymore so it's going to be more complex that's complicated we need to do things really really quickly and it's not clear that you really want to do it h that you can actually actually do a good job here and also one of the H real problem that we don't don't pay enough attention is these AI JS which is how much of

resource J do transaction I use we really don't get that the correct numbers we get some kind of number that we got from the users of the transactions and they usually give an upper bound and if you look at ethereum the upper bound is usually between two and three times higher than the actual use okay so when you do the algorithm if you do the single linear programming one dimensional relaxation that doesn't hurt you you still order it according to the price per unit you take whatever it takes and as long as the actual use is not too much you keep on taking more transactions what exactly do you do you do in the multi-dimensional thing is not if you only have upper bounds it's not very

clear okay so so there are algorithmic problems it's not a solved problem also there are economic problems one of them is how do you even bid for something that you have a value you have a transaction you let's say you even know exactly how much is going to use of each resource what are you actually bid on so if you're you know the natural thing would probably be to to bid for the price for your transaction how much is a value for your transaction and for each resource how much are you using of that resource okay at least the semantics is like a single-minded bid in that case this is what I want I use so much either give me or take me I can't take a fraction of it that's not completely how

it's done let's say in eum what usually what is currently done is for each resource you give a bound a number amount of price for the resource and a quantity for that resource what does that even mean I don't really have a value for a resource I have a value only for the whole transaction so what is even the semantics of this thing and if we don't know the semantics how exactly would would I know how to bid even okay so the wallet that needs to put in your bid suppose that you tell it I you know you know exactly how much your transaction is worth how will it split between the two things okay so I'm not saying that it can't be practically solved completely but it's a non-trivial kind

of issue and it causes problems and it definitely plays against this incentive compatibility uh reason you know good ux reason of why we wanted the 1559 to begin with let's say and then how do you compute the resource prices let's say if you do a like a I don't know a pay your own bid what exactly does that mean there's like some underlying inter linear programs that we think should figure out these prices but how do you get them how do these prices play with incentives it's very not clear okay so L of these are things that make it more complicated to H to do multi-dimensional fees and the basic question that I want to ask is do we need to to go there okay so actually this is actually a problem

that the company that I work for starkware is really worrying about do they need to do multi-dimensional fees okay or can we get along without it like Bitcoin is still doing okay it's not a clear question okay you are you going to complicate your whole mechanism fee mechanism kind of world with all the associated software that needs to handle it with all the associated problems both the you know cognitive complexity and the complexity of bidding and complexity of you know making mistakes in your code and so on or are you not going to do that okay that's an important question really so before I continue trying to answer this question or how I'm thinking about this question I'd like to give a few uh just a few examples of resources

that people actually worry about one of them is actually the the number of bytes in your block okay so even in ethereum now there is this new worry that blocks are sometimes too large they would like them to be maybe a mega but sometimes they you know practically can be several Mega it's rare but it happens sometime maybe they're thinking about pricing let's say call data which people sometimes still use at a higher level at a certain point to make sure because that sort of takes a lot of space relative to the current gas allocation that it gets when you build the block you know the minor validator whoever build the block of course needs to do it quickly enough and you usually you want a weak computer to do it within some so much

time if you're working in a you know Layer Two that has proof you know suin proofs then the prover needs to also prove a block that's also a different constraint because a lot of times the amount of time it takes you to build a block is sort of related to the amount of that you need to prove the block but it's only sort of there are some operations that are very easy for this and very difficult for that and vice versa h of course we have these blobs on etherium which is a kind of resource of keeping information on the on the blockchain that gets completely different kind of consideration completely different kind of costs than uh the normal

gas H if you're a layer two the question is how are you going to price your own data ER that data availability so how are you going to price transactions that want to keep information how are they what is the price that you're going to do that you going to translate it to to gas how does that work that's a different other kind of resource that you're worried about and of course we have the state that we talked about that you're worried about as a total States a total amount of memor that you need to remember all the history of the blockchain would grow too large and this is a very long-term constraint okay so these are the type of H resources that I'm worried about and I would hope to cover and probably there

are a few more that don't fall into one of these but uh hopefully these are the main types so the first thing we're going to assume as our model is that our blockchain provides a bunch of types of operations and for each operation we can tell how much is it taking from each one of the resources that we care about okay so this is going to be our input it basically explains what is the situation the mechanical situation of my blockchain and basically these are the operations that it can do for each operation this is what it takes from each resource so for example maybe you have one operation takes 50 uh something execution time and uh but only 10 bytes in Block size and another one that works

the opposite way or that works differently 2,000 much more expensive than this here and much more expensive than this here and so on and some operations have other for example the normal operations maybe don't touch storage data at all or don't create new state but maybe a new storage right that you know you know it has some time at execution in Block size but it also has some you know it creates new state and which we should worry about okay so this is going to be our input it describes our you know considerations the softwares that we're running okay yes I was just thinking it occurred to me like you have like you know state which is storage

forever you have blob data you have call data do you ever think about abstracting to sort of have like almost a third dimension which is how long the storage lasts for and you could arbitrarily okay so the question was whether we can try to have a third dimension which is not only for each type of resource and for each operation also for how long you want the resource this is not the direction that I'm going I'm I'm staying with long-term and shortterm and hopefully and and I'm even ignoring middle term oh so you're ignoring like the blob data stuff or the no The Blob data should be covered by what I'm talking about yeah I'm I'm assuming that the blob data is kept in a

good enough way and I don't care about that you know two weeks or something like that and by the way here there are some maybe also operations that are implicit maybe St stting a new transaction may have its own cost and so on right and by the way H okay so I have here a okay I have here like four example resources and the point that I want to make these two are sort of similar so they're related but not the same okay well these are completely different kind of things this is access to storage this is new storage so these so the idea of these two columns is that they're very different from these two columns and the idea of these two that they're sort of the same but not exactly the same and there are many more examples of similar columns for example

instead of block size and execution time you could talk about in l2's sequencer time Andover time which again there two resources that are sort of the same not quite and of course what we have for each one of these we have also the capacity of our block the constraint of our block and here I'm doing the first H perhaps non-trivial thing which not the natural way people think about it I'm looking at two different kind of things I'm looking at the capacity which is a normal wave we look maybe I want 10 megabytes for block of exec 10 mega I don't know seconds or millisecs whatever micros seconds H for each execution time and one Mega let's say bite per block for this so I have a capacity constraint

on the Block on each one of these resources but I also have cost in places that I don't have a capacity constraint or also when I do have a capacity con but there's also an Associated cost I can write amount of cost here so for example the cost of storage may be one blob gas blob gas is like a serum unit this is like a money for us right if I keep stuff on blobs and ethereum that's my data availability for my Layer Two that's how much it's going to cost me even if there's no constraint whatsoever and the amount of data that I can put in a block it each each bite is going to cost me money and you know some maybe I have a 25 gigabyte and now because this is not per block the here I'm going to write it in red okay so this is like the

kind of input that I'm thinking that I want to try to analyze and figure out what's going on there how do I design for this system the mechan you know the goods basically so one blob gas that's like you're thinking L1 gas where this is an L2 where you're doing the yeah yeah the one blob gas is if this an L2 then this is one blob gas is a number normally you would say here one micr cent yeah and that was my next question like are you allowing the possibility that that L1 gas is itself varying in a complicated way or should I think about that it is fixed yeah so I want to think about it as fixed as one micro sent and if it's varying it's like exchanger is varying then we'll need to handle that on top of everything that I say

independently so what am I going to do with the rest of the talk I'm trying to basically say how I'm thinking about how do I try to avoid so you know my goal is I don't like multi-dimensional mechanisms and can we avoid them or not that's a question okay how am I going to try to avoid it didn't you invent algorithmic multi-dimensional mechanism design yeah yeah but you know but then you start actually making them work and you see things are more complicated in practice and in theories and you say okay let's pedal back right so okay okay so H the first thing that I want to do is I'm going to claim this distinction between capacities and costs gives you a lot of Leverage some things you can you don't need to worry about that's the easy part then I'm going to do most of

the talk is how can I analyze you know I have all these gas measures which are sort of related how can I analyze how much are we going to lose by folding them into a single gas measure that's a second part and the third part is I'm going to show that in certain cases to a certain extent if you have very long-term constraints basically you don't need to worry about them you can completely fold them into costs and cost we already showed that we don't worry about okay so that's the agenda for the rest of the talk okay so constraint versus cost this is like a easy part it's not a constraint so you don't need to worry about it when you're building a block that's done okay okay what do I mean

that's done what do you do with the costs well the system is going to pay them so who is going to need to pay to the system in order for the system to actually pay them to whoever is doing your you know is actually implementing it of course the person who uses it so the users should pay their marginal cost if I am asking for additional bite I need to see how much is that addition bite going to cost to the system and I am going to need to pay that okay so that's important I don't pay for the total cost it's not that I need to see how much is it is it going to cost for the whole system to handle everything just how much is this additional bite this additional use of the resource cost the system and that's what I need to pay

okay now notice that this cost these costs the system pays you know there is this one person one actor that is building the block let's say the the validator that's building the block some of the cost he may need to pay some of the cost someone else will need to pay maybe you know he's only building the block and someone else is going to actually send the money to the data availability provider right it's a complicated multi you know multi server system but in any case whether it's the Builder building whether it's the the actually the guy you know leading the block who's paying the cost or some other part the user that the transaction needs to pay that cost okay that that's important

okay so who should it pay to so basically it goes in two ways the cost that the block Creator actually needs to pay actually the user can just pay directly to that like a fee that goes to the like you know the tip or any fees that goes to the block Builder the other cost cannot go to the Builder because that will destroy incentives for the you know for the Builder okay but still need to go somewhere and that somewhere it doesn't really matter as long as it's not the builder of the block right so it's important that the user pays that part of the fees it's important that this part do not go to the builder of the block and beyond that you know we can burn them we can allocate it move it

to the person actually paying when you actually operate the system whatever now the bids when you actually are bidding on this kind of thing you don't really need to you know you need to take into account the fact that you're going to pay for each unit that you're actually using of this resource okay you may or may not ask the user the user may or may not actually give a bound and how much is he willing to payer that if it's not known in advance but it's it's a number if he doesn't give you know the of course the when you actually when you actually take him into the block you can you know exactly what that number is and you can decide whether to take or not and uh but you can also give him H the ability to actually give an upper bound and that

and it doesn't change anything when you actually are doing the the allocation or pricing or anything like that okay so that's also very easy and this is like what Tim you were asking previously even if the price even if the cost the cost that you're actually going to be paying the system is going to be paying for something it will only be known later you need to know that cost for the user at sequencing time okay because the user now you have to decide whether user has enough money let's say in his balance to pay for that okay so you will have to do some kind of estimation what is the future price you can do this estimation in a simple way for example my company currently has the following estimate of following clever

prediction algorithm for the price of of gas in the future the average of the last hour okay but of course you can do much more clever computational learning and you can also do like a Futures Market kind of thing you can take the risk and take it away anyway from the point of view of the you know of thec mechanisms of a fe mechanism it's a constant okay that's one okay so this is good we already reduced some of the columns that we don't need to worry about now the second question is do we need multiple Fe Dimensions so let's go back to our H to our diagram here and let's not worry for for a second on these two columns where this column is

the one we already took care of the storage data which was an example of a of a cost without a capacity and this is a a long-term constraint that we'll take care of later so let's just worry about these two columns which are sort of the same but not quite okay and let's worry about can we fold these two columns into a single column and what will happen when we do that how much are we going to lose why is the new storage row gray out the new oh because H again because the only difference between this this line and this line is in this column which we're not worried about okay so we're only handling this now that's redundant with Right Storage that's redundant with Right Storage once

you that's redundant with Right Storage right got it got it okay so again this we already took care of this we'll later take care of okay so now we only you know have the columns that we're interested in and what does it mean moving to a single gas measure it mean we're going to have some kind of combined gas measure we're going to find out how much gas does this operation cost how much does this operation cost and so on and let's normalize without loss of generality the total capacity of the block is in gas to one and the question is what are we going to put here okay this is how we're going to actually translate these two constraint into a single constraint okay so the formal definition so let's say a guess measure is something that gives each

operation I a cost GI and the guas measure is a conservative representation of the already The Matrix that we already had okay which is w J the amount the transaction I uses of resource J and the total capacity of BJ of of resource J if whenever you take a non- negative Vector of resource use if you're within your capacity of gas then we know that for each one of the resources you're not overusing it okay so this would be a conservative guess that actually if you put these gas measures you're going to be assed assured that you're not going to

to to exceed the capacity of any resource on your blockchain and if you're thinking about oh how should I do that there's a one way basically that you want to do that if you take the maximum over all resources of the fraction of the resource that you're using that's going to ensure that each one of your resources is not overused not only that that's really the best thing that you can do if you have any other conservative approxim resource gas measure then this one is a low is lower than it okay so the anything anything High any other thing that you have is higher in each and every coordinate okay so really this is the way you do it you do a maximum okay so

for example if we go back to our thing here how do we know what is the gas measure for operation one well we look what is bigger 50 over 10 million or 10 over 1 million and I think it's 10 over 1 million and that means that the gas measure is 10 * 10 to the -6 okay and uh and so on okay so for each uh one of these resources yeah and here for example on the other hand 2,000 over 10 million or 120 over 1 1 million as this one turns out to be bigger so you WR here 200 divided by 10 m 2,000 divided by 10 million okay and this is basically the

only thing that you can do if you want to fold it into a single gas measure without doing any not being conservative now a word about why do I want to be conservative here and not allow myself somehow to extend you know maybe you know on the average I can accept a little bit more and so on and the main reason is because whenever we do this we must be robust also against adversaries right we can't have like a you know denial of service attack or anything like that so we really need to be sure that whatever bring comes to us that's not going to hurt our blockchain operation okay so I really need this condition so now I want to see this is what we do this is how we fold how much are we going to lose by this what does it mean how much are we going to lose by

this I'm going to look at three different interpretations of the question two will be very simple and one will be interesting one of them is for the worst case Matrix of costs and the worst case distribution and operations the second is a given cost Matrix and the worst case distribution of operations this is this is basically what I have as a blockchain Creator I just have my blockchain I know it's technology but I don't know the distributions that may come from an adversary just want to hurt me and the third thing is a given Matrix and a given distribution of operations suppose I know I have some statistical statistics about how much are you know operations used in my blockchain and I want to relative to that I want to

calculate what's going on okay so these are three Notions that we can study so that third one you're thinking about non-adversarial work CL basically yeah the third one okay so the third one actually I want to be a bit I'm going to be a little bit more careful I want to make sure that it's conservative in the adversarial sense that I never go beyond okay so I am limiting myself to the Maxum each one but I'm measuring my loss in the non-adversarial statistical sense so number one it's I think pretty well known that if you have K resources you can lose a factor of K and the basic example is suppose the resources are completely independent then if your normal distribution is just mixes them completely if you're each one

of them you're going to count as completely one you basically losing a factor of K okay so basically taking three inequalities turnning them into one inequality you're going to lose a factor of three no question about that that's easy okay so that's not going to be an answer that we want okay so if our answer is you're going to lose a factor of K if you really have seven different types of resources factor of seven is probably not good so now let's look at the other things I have a matrix and now I want to see what's going on in the worst case distribution so I'll say that a gas measure is an alpha approximate representation if the other direction okay not just the gas measure implies that all the constraints are are satisfied but all the constraints are satisfied implies that the gas is

satisfied within this Alpha Factor okay so for any non- negative Val Vector we have that if all the constraints are satisfied so if with load XI with load X none of the resources is overloaded then the gas measure is at most Alpha okay so I'm losing basically a factor of alpha at most in my approximation then I say that this G gas measure is an alpha approximation okay how do should one understand it the easiest way to understand it is probably in the resource augmentation framework okay so what does it mean suppose we have now our blockchain that has multi-dimensional in the real world has multi-dimensional Fe is and I now you

know something fits into a block something fits into a block this Alpha means that if I have a one-dimensional gas measure but now I allow the one-dimensional gas I increase the block size by a factor of alpha now whatever got into a single block will be accepted into my single dimensional block larger block by a factor of alpha okay so that's the the direct no problems uh interpretation of this thing you can take any block here and translate it to a block there if you previously augmented the block size by a factor of alpha the preferable probably the preferable way to look at it is if you ignore integrality constraints that you have you know two large uh blocks that

don't exactly two large transactions don't exactly fit into a block let's say that all transactions are small it just means that you're losing on the average one over Alpha Factor okay so so that uh you know that's probably the way to look at it for every Alpha block 100 times Alpha block here you need only Alpha 100 blocks here okay so let's let's go back to our single gas measure we know what is the you know what is the gas measure that we're looking at let's see how much are we going to lose by using this gas measure relative to this truth this is the question that we look at and I'm going to do this example this is going to be sort of proof by example and then I'll give the general theorem of course so I'm going to do the following kind of

thing it's easier to look at it if I first normalize everything in various ways so the first thing is I want to H normalize the operations so that the combined gas of everything is one so here we had you know the combined guess of anything was you know these word numbers but if I take an operation instead of looking at operation one I look at seven operation ones and I give everything seven times this time this execution time seven times this block size and seven times this combined gas it's exactly the same problem since I'm working in a fractional kind of thing there's no difference if I have a row for an operation or for any multiple of that operation so to make things easier I'm going to first normalize it to one okay so for example here now I have you know

10 to the five operation ones it takes this amount of execution time this amount of block size this amount of combined gas okay now I'm also going to normalize everything by column okay so you know these capacities I can arbitrarily instead of counting execution time in milliseconds I can count them in 10 to the million milliseconds or something like that so I'm going to normalize every row to be one okay it's the same problem nothing changed okay so now the nice thing is I have a a matrix that the all the combined gas is always one the capacities are always one and I need to see how much am I losing on this matrix it's exactly the same question we originally had okay so now let's think about it what are going to be which rows

are important which rows are not important for this H to for my answer for just figuring out how much am I going to lose for the worst case distribution here on operation and it's easy to see I would say that you're not going to lose these two rows are not going to change the answer why is that suppose that I you know the worst case operation that really gives me the worst case you know competitive ratio uses a little bit of this operation of this R line but notice that this operation is really a convex combination of these two rows so instead of using this operation I can use the correct convex optim convex combination of these two

things okay and I get something that here is going to be smaller than these and here is still going to be one okay so the basic H observation okay now should should be intuitive I'm not going to prove it formally the basic observation is that you always take look at the in the case of two goods two resources you always look at the most extreme r ratios between the numbers on this one and in both directions and the ones with less extreme ratios really do not matter good so now we reduce the problem even further to this Matrix and uh now we can completely solve it right so let's solve it for General A and B this a situation for General A and B what is going to be your competitive

ratio and the answer is here is this number this fraction this is going to be your Alpha this is going to be the the amount that you lose how do you see that well because what is going to be the worst case distribution here the worst case distribution is going to try to equalize these two resources because when one of them is low and one of them is high only the high one takes into comes into account so it's not going to be the one that actually maximizes a ratio between the maximum of these and this one right so really the best thing that the adversary if you wish the distribution can do actually in order to to get a large gap from the single dimensional case would be to equate equiz the amount of use of this resource and this

resource which happens with these probabilities and then you just figure it out okay so this is the ratio that you have so let's look how does this behave When A and B are zero we're back into a ratio of two which is exactly the K the worst case Cas that we have when either A or B approach one which means that either this becomes almost dominant resource or this becomes the almost dominant resource then we approach one you lose nothing in these two cases okay so it sort of behaves like we want and what happens let's say with our numbers are 0.5 and 0.6 it turns out that Alpha is 9 over 7 which means that you get 77.7% of

efficiency okay so you know now you have to worry if 77.7 the worst case is that good enough or not good enough for you okay so this argument okay so what's the general case so here's sort of a cute uh theorem if you wish for any game once you have any Matrix the value of alpha is exactly given by looking at the Zero Sum game where the utilities of the are exactly the normalized fractions of capacities and the gis are exactly as we said before the conservative you know the optimal conservative thing and you look at what is the value of that game in the case of a zero sum game between two players where the row player here is the

minimizer and that's exactly your one over Alpha if you you know I could try to prove it but it's probably as easy to actually look at it and figure out why this is true okay so this is the theem one okay so now you know now you look at your Matrix and decide is this good enough for me or not but now you also have some historical data how we going to use it so suppose now let's go to the third interpretation yes so just I mean tying this back to systems you I mean so what uh what do you think Alpha is for a lot of the current like virtual machines let let me hold on for a second with that okay what Alpha is yeah so I think that practically Alpha is not very far from

one even though this analysis may not show it okay so and presumably you're going where you like maybe cluster different rows and then Alpha is close to one within each CL no so I so okay so one would want to go okay if I have lots of lots of Dimensions resources maybe I'll cluster these into one dimension and cluster that into two Dimension now I have only a two dimensional Fe I'm not going there yet I don't like to more than one di mention at all so for now I'm sticking to the question do we need more than one but but yeah that would be the natural Second Step yes so this goes back to like how well does like execution time correlate with Pro time and this kind of stuff is like yeah but I still but I want to actually make this

thing a little bit more find for for which I'm going to look at now a statistical data so suppose now that I know so we saw it's like 77% but suppose now that I know that most of the probability is on the first operation but only 20% is on the second operation suppose now that this is you know my statistical data and I believe it for the future as well now how much am I going to get what is going to be the loss okay so the easy fact is if every block it's always exactly you know this the this distribution okay then you just you know you run it you take these probabilities you see how much are you going to use of this resource how much are you going to use of this resource and you see that basically blocks in the if you actually

use the combined gas measure because we're still sticking with the worst case gas measure that doesn't allow adversaries to hurt us and now we're just trying to you know measure things according to a known distribution then you can see that if you close blocks according to this gas measure they're going to be closed at 60% of this uh resource and 92% of that resource okay which would imply that basically you're 92% efficient right because that's what it is okay but for this you need your distribution to work on each and every block okay but here's a observation that is Trivial yet it took us some time to figure out this is you don't really need it to hold for every single block the

worst case situation is that is hold for every single block as long as the average you have 80% to 20% on the average that already ensures that you get at least 92% efficiency and okay that you have to see that if I'm adversary now choosing a distribution and I'm limited myself to be to having this over multiple blocks and how I can choose each block separately the best thing that I can do or you know to hurt the system if you wish is exactly to mix completely okay that's observation okay so this thing it really once once you have a significant way of once you have some idea of your probabilities you get a very good H guarantee if you wish

statistical guarantee on the output of your on the efficiency that you have and without relaxing it all the worst case adversarial nature of your gas measure okay so that's a is it is it strictly optimal for the adversary to equalize it every block or does it matter um it doesn't matter as long as you're not going outside of the same set of resources basically that are closed okay if you're not going outside it's exactly doesn't matter if you are going outside it strictly okay and then this is a completely General kind of thing so now the question is okay how can I play between these two things so I sort of

trust my I sort of trust my statistical information but I don't know it's going to be the same in the future how can I somehow combine between you know statistical point of view and AD case point of view in one say here's one way that I like doing it which is a little weird but I still like it so I'm going to present it and this is the following so we're back to our example and suppose that I know now I have some kind of notion on the probabilities that I'm going to be using each one of these uh operations so for example I know that at most 20% is going to be here or in general I can have an arbitrary cone if you wish of what are the reasonable probabilities that I have in blocks okay

how can I analyze that so here's one way that I like to do is let's consider and and this also takes to the following problem suppose that I have I'm improving my blockchain now and instead of this taking 0.6 now I made it use much less of this resource and now it's down to 0.1 okay then can you can see that the H the alpha that I get now suddenly grows so I improved my blockchain and instead what I got is that things actually are much worse a single dimensional is worse of course it's going to be worse relative to the new much better blockchain that I could have had okay but here's a way to analyze it but if this operation is used very rarely and

by the way most blockchains have some operations that are really almost 0 one and one zero but these are very rare operations usually in One Direction so it doesn't make sense that because I have an oper an operation that's very good and rarely used all this kind of analysis doesn't give me anything anymore okay so what I say is let's do the following kind of pretend analysis suppose that I have this is my blockchain I imagine that I have a worse blockchain with this kind of thing I just took a number here and increased it in fact I increased it to the point that this is now the dominant resource so I know that there's not going to be any loss if I move to a single dimensional block how much but okay but now of course something is Strang or I am

losing something but suppose I'm cling to see how much am I losing from going from here to here I'm going to use a statistical information from here to here I'm not using anything in the worst case so to see what is it going to cost me to move from here to here that's something that I can use the statistical information I can see that I lose 0.4 from 0.6 to 0.1 with at most 20% Which is 0.08 okay so this is the same gives you the same kind of numbers as previously but now as long as you believe that indeed the distribution that you'll see in the future satisfy these constraints then you're guaranteed that in fact your

single dimensional thing is not going to lose more than the how much you lose here times how much you lose so that gives you here 0.92 and how to play with that and how to say that in the nicest way I still don't know okay so let's H move on to the last part what happens with long-term constraints so remember we have this new thing that we have this new storage things that cost a bunch of new bites and we have some kind of capacity constraint per year how can we handle that so suppose I want to ensure 25 gigabytes per year one way to do it I can just translate it to every block which is sort of implicitly what the serum is doing so suppose that I have every year as 2.5 million blocks suppose that I you know calculated the number of blocks in

a year I just translate 25 gigabyte divided by 25.5 million it means that if you have a 10 kilobyte block capacity per ER per block that will ensure your long-term goal and everything will be fine but of course this is very wasteful because you know sometimes there is lots of demand for new data and there's no reason to constrain it now and charge high prices for it that's completely you know changing the the correct incentives so what we're going to do is we're going to translate this to costs like in the 1559 okay so we're going to have simply a price a cost if you wish for every resource that's going to be updated basically by the same 55 5 1559 type of

algorithm basically I'm going to multiply the price every time by something that's exponential and how much was I over the intended capacity as a fraction okay so B is how much I use little B capital B is how much I was expected to use in this case h 10 kiloby and this is how much am I am I over what I needed to do in percent most multiplied by some constant data so that gives you a price all the time and okay so what's going on here why is this even interesting so here's the basic idea in the short term if ETA is in the right range in the short term the prices will hardly

change okay because if AA is small the prices only change very very slowly so in the short term basically you have that the ratio between the price at any time and the price the beginning is something that's very small so this number is 1 plus Epsilon basically okay in the long term on the other hand because we have this huge gap between the short term which is minutes and the long term which is maybe a year and the long term this very small ETA is enough to make sure that you don't use too much of that resource and this analysis is exactly like the basic analysis of 1559 but now only with these Zas okay so in the long term you're with in the total number of resources that

you use is within a factor of 1 plus Delta of what you should use between J and I and so so this these are calculations are are completely trivial but let me just give an example numbers to see that it makes sense so suppose that I really want to to to be 25 gigabytes per year and suppose that I have a block every 12 seconds which gives me indeed a 2.5 million blocks a year H which means that the average block sizes should be about 10K and suppose that you know 10 minutes very small prices within 10 minutes is almost for a constant for the rest of the algorithm so remember that we're trying to to to basically simulate this long-term constraint by a constant price so the question is what is constant

enough for you and suppose it constant enough for you is something that hardly changes within 10 minutes so wallets don't need to worry about it how to bid is not an issue everything is easy if you're willing to give me 10 minutes okay so uh this means if I really want 10 minutes then the number of blocks I have in 10 minutes with this uh rate of blocks is maybe 50 blocks okay so short term is 50 blocks long term is 2.5 million blocks okay and then a you need some kind of a bound on the total price and the r ratio of possible prices the ratio of possible bids and resources and let's assume it's between 10 the 9 and 1

East per B so there's a range of 0 10 to the 9 possible range of prices that biders offer okay so you and also there's another upper bound how much is the maximum that your block can really go beyond H what expect you expect it to be there okay there this that's some kind of a constant that's either ensured by other constraints of the system or you can force it without taking it into account in your neither in your algorithms nor in your pricing or you can just use it as a part of your analysis and not and if it doesn't it hold true then your analysis will not be true but the rest still works and basically it shows that for example you can get within 9% the yearly bound while within 10 minutes never having never

having in the most extreme situation more than 2% fluctuations in price okay so this just shows that you know reasonable numbers you really can fold the long-term constraints into to short-term ones and you don't need to worry about handling them in algorithmic or economic way so the conclusion is maybe maybe we are designers of this fictitious new blockchain can get away with a single gas measure that constrains the block size and a bunch of direct pricing for other resources that we view as cost and maybe also long-term constraints and that may be very easy to implement you can do it either in a pay your pay your bid or a fixed price you can do it in both ways that we have now

and it's fine but maybe not and that's it yeah in terms of motivation um you said that one of the kind of disera is that it's easy to build blocks and so avoiding you know a builder having to to solve this multi-dimensional napsack is important um in a world where like one small set of Builders who are like very sophisticated and already extracting me is the dominant like block building regime is there any other reason to motivate a avoiding multi-dimensional gas or like like from the ux for example is it hard to for wallets to price yeah so I think that the the other point that I made there was also a pricing kind of

bidding pricing kind of issue that giving a separate bid for each resource it doesn't make much sense and if you're giving only and that's how it's currently done let's say in ethereum and if you're only giving one price and it's not clear how do you get the prices for each one of the two resources so so there is some economic difficulty there as well again I'm not saying that none of these can be handled but it's it's something not Rous that needs to be done what do you think Alpha is for ethereum L1 what I think okay so when you say Alpha for eum in L1 let's say for so what are the kinds of alpha alpas that people are worrying about okay so there's the original if you wish okay so what kind of alpha could we think about

one of them is actually the fact that they separated you know the blob data from non- blob data and suppose it's just suppose that they just would have introduced blobs right Cur their capacities but then just just a um you know charged them according to folded them into the single gas price how much would Alpha be so I don't know so I think the alpha in the worst case would be pretty terrible okay because they can really be completely independent and it's not much doesn't allow cost you a lot in normal gas in order to increase a lot of blob data but I think that maybe on the average you would get a much more

reasonable Alpha so I'm not even sure that that would have been needed the second kind of alpha that one can think about is now they're worrying again about repricing cold data because they want to incre decrease block size and you can have the same kind of question there and there I think even the worst case is not that terrible so I would don't see a reason to to do that frankly and I think a third version would be like you'd work you'd sit down with some who know zvm really well and you'd build the table that you had as your running example and you would try to like reverse engineer what was the multi-dimensional one that like yeah you know yeah metallic or whoever was projecting down and so I'm curious for that original multi-dimension I agree it would be really interesting writing down

the real constraint and taking all this you know 100 rows of eum evm I mean s obvious to me it's even like well defined maybe it is but you know like could you like actually just confidently assign a state growth number to like hm operation I'm kind of yeah it's it's a great question h of course you know it will be more difficult than just oh let's just get some numbers here's a table you know an intern can do that in a day it's more complex because you need to think about stuff but uh but I think that would be a really interesting exercise especially according to this new proposal that they're trying to think about of separating call data from normal guess yes I guess I have sort of a related table uh question because this table if it were to exist I I don't feel

like it would be fixed necessarily because like in ethereum you can call a smart contract that does a lot of things so you're still doing the execution but it doesn't affect the block size because you just have one call to a Smart contract that is already there so in a sense like all these separate things would matter sort of like there's at maybe I'm misunderstanding something but it feels like there is no direct map like there is the table depends on how the transaction is structured in the first place okay good yeah so I think the question is is there really even a table so i s there was a table and the combination of a transaction is a linear combination of the cost of the operation that's how it's currently modeled I think also inum and almost everywhere right but in reality that may not be the

case for example you know if you have recursion if you call things maybe it's not just linear maybe it's sublinear in some sense and so on probably true I think sublinearity would still sort of work I think the same kind of things shouldn't really change much if you have somewhat somewhat sublinearity ER I am not sure how big an effect this is really so I think the whole point of getting the cost for each operation is really thinking about the worst case kind of thing and making sure that your blockchain is always robust and I think from that point of view it's always okay ER so I can't say I can't answer in a negative completely because there are risks there and there are possibility and maybe there are situations where

there is a significant difference but my I don't know sort of understanding is that it's sort of linear and that sort of fine and I guess the other part of your your answer that was buried in there is like you might say okay does the cost of an OP code depend on some broader context you're just saying just think about the worst case context that's what you should fill in that table with for an off code basically right yeah if you have something that's super linear suppose if you run these two things together then you really need to add add the new stuff information you need to add that as sort of an extra operation that's implied by using these two things so getting the comp the table to be more complex is issue and by the way another thing that's really interesting small changes in the

technology underlying the technology so you know usually you keep on improving your blockchain you improve a little bit something and then it completely changes the table and that's the whole point of improving right so so it's a delicate kind of argumentation but it's by the way it also shows that it's even worse to improve a few things if you have a multi-dimensional kind of cost because then you really need to change every one of them while if you're taking the single dimensional thing it's sort of a worst case so small changes should not matter that much so the robustness how robust is all these costs relative to your technology is also a big issue so going back to the cost part uh so it seems like there's some instances where you don't have constant marginal costs like you have more of like a fixed cost

for a block so for example like once you're forced to buy a blob for the first time then if you have leftover space in your blob the marginal cost is zero um right so have you thought about this kind of yeah yeah so this is actually interesting and it's actually so let me give you an example so okay so the question was this assumption about marginal cost let's say for data Maybe the marginal cost may be zero if the blob is not full or something like that have we thought of non the non marginal cost so the truth is yeah it's very interesting what exactly is your cost for each unit of data can change very much according to the technology so for example let me uh reveal something from the situation my company currently we have this you know technical limitation

which we didn't think that you know we should Now work on the software that you have one blob per block okay so it's about the right number and we said okay for now this is enough at a certain point if you don't if our blocks are small enough then we typically do not never finish a blob we do not fill a blob completely in which case the data cost the marginal data costs are zero okay so at a certain point in time where our blocks were small the marginal cost the actual margin cost was basically zero for data so it means that if this is really your situation you should not charge anything for data you don't you don't need to try to recover the cost that you're going to have for buying this blob because you're going to buy the blob anyway so if I use

a little bit more data you don't need to to charge me for it so when you have that technology basically the marginal cost can be zero once we slightly improve our our technology and now we can basically split many blocks into the same blob which is you know not a big deal but uh we can do that of course then everything now immediately becomes a true marginal cost right because now we just have lot okay so if you wish one technological change that doesn't seem to even directly relate to your cost completely changes what you should charge according to this logic well I it's like in that instance like the first transaction would have a very high marginal cost of like having to buy the block yeah no so no no I so I don't count the marginal cost you know

sequentially that's not the way I would like to do that right the first one also would have zero marginal cost because even without it you're going to have use blog thank you