A Mechanism for Pricing Non-fungible Resources: Toward Multi-dimensional Fee Markets

foreign [Music] I think I'm going to steal proof of optimality in this talk from Felix's talk because I really loved that but today we are not going to talk about D5 we're going to talk about multi-dimensional fee markets or kind of the fancy term is how to do Dynamic pricing for non-fungible resources and this is Joint work with Alex Evans True and chitra and guillermaranjaris all right so the first thing I hope to convince you of is that fee markets with the joint unit of account like gas are actually pretty inefficient and what we're going to slowly work towards in this talk is a framework to optimally set multi-dimensional fees so first part of this is like why are transactions so expensive why is having one market not necessarily something that you want to do and first a little bit of an aside um one of the things that we actually do sometimes see with one-dimensional fee markets are these types of denial of service attacks and this is because all op codes have fixed relative prices to each other and whenever you have a potential mismatch between a relative price and the resources that that op code consumes you can get something that takes down a network so these have been termed resource exhaustion exhaustion attacks in the literature and there is a famous one back in 2016 that took down the ethereum network or essentially made it unusable did not take it down but made it very hard to use for quite some time and this was essentially due to a disk read mispricing and of course this was patched in a subsequent EIP but if we had a multi-dimensional rather than a single dimensional Market we might have been able to adjust prices such that there was no need to actually reprice the op codes after the fact however what we're going to concentrate a little bit more on today is um throughput is why having a single dimension Market is actually bad from kind of the network designer's perspective and so this is a very very stylized example that is not at all like close to in practice but I hope it illustrates the idea let's assume that we have a bunch of users that are submitting transactions some only consume CPU some only consume bandwidth the CPU ones have some utility of four so that's kind of how much utility they give to the user that submits it and the bandwidth ones have utility of two and let's imagine we have a block each of these transactions cost one gas the gas price is three and the block can fit four CPU transactions and four bandwidth transactions well in a single dimensional Market what happens we fill this up with CPU transactions but actually we have a lot of block space that's not used because these bandwidth transactions aren't high enough utility and something like this can happen say with like an nft mint however if we have a 2d market and say CPU has that cost of three but bandwidth has a cost of one we would actually end up filling up all the CPU transactions in this block and filling up all the bandwidth transactions as well like I said this is a very stylized example but it does illustrate when you price things separately or in other words if resources are orthogonal they should be priced separately however that of course uh needs we need a mechanism for Price Discovery to do this so how do we decide that you know CPU is three and bandwidth is one or what are those prices uh what do those prices even mean how do we get to those prices and I'm going to do a little bit of an aside in that uh I've been throwing around this term resource a lot and there's a question of like what exactly do I mean by that the working definition we're going to use for this talk is anything that can be metered so a resource is anything that I can say how much of uh this thing a transaction uses so for example um one thing right now roll up data however we could also talk about like kind of big resources like compute memory and storage we could go down to the op code level and think of each individual opcode as a resource however we could also say you know sequences of op codes are resources for instance if you're calling like a hot storage slot versus a cold storage slot that's going to be um cheaper so maybe if we have several storage op codes um all in a row that's actually a different resource than calling these one by one furthermore if we're running uh full nodes on multi-core machines maybe compute on like node or on core one is a different resource than compute on core 2. and and so on you can imagine this is a very general construction resources can be very dependent on each other um and so as long as they can be metered or we can say how much of a trend of a resource a transaction uses uh that fits into our framework so to formalize this and this is kind of where we get a little bit into the math we're going to say a transaction J consumes some Vector of resources and there's so M resources and this Vector is AJ so essentially the ith element of that Vector is going to be the amount of resource I consumed by this transaction J and now that we're uh starting to build blocks we're going to denote this Vector X that essentially is the zero one vector and we have n transactions XJ is going to be one if that transaction is included in a block and zero otherwise so this allows us to very easily write kind of the quantity of resources that's consumed by a given block and we're going to denote that Y and all this is is summing up the vector of resources that's consumed by a particular transaction times XJ and XJ you know if it's zero then we're not going to include this in the sum if it's one then it's going to be included in the sum and this can be uh written in kind of this very convenient Matrix Vector notation as well where The Columns of a are going to be the transaction vector or the resource vectors for each transaction all right so now that we kind of have a notion of a resource and what each resource is we can talk about things about constraining resources targets for resources and charging for each individual resource so we're going to first Define a resource Target and that's going to be this B Star and then the deviation of the target based on what I uh introduced earlier is just ax minus B remember ax is the quantity of um or the resource utilization of a particular block and in ethereum this is one-dimensional so this is going to be a scalar and B Star is just 15 million gas we also want sometimes a resource limit that says how much or after a certain point a block is invalid and then we can have uh transactions satisfy something like this where ax has to be less than or equal to B um in ethereum this is 30 million gas so again in ethereum this is all one-dimensional however we're extending this to a multi-dimensional case finally this allows us to talk about prices for each resource so we're going to have some Vector P this is going to be an M vector and Pi is essentially going to be the resource price of uh or the price of resource I so that allows us to very easily write how much a transaction costs which is just the dot product of its resource vector and P and then this is split up into the sum here one thing here is when I talk about prices this is going to be the amount burned by the network or essentially the price that the network charges for a given resource so think like EIP 1559 it's not actually going to be the price that uh users pay say validators for inclusion in the block so nothing about tips here this is just going to be purely the amount that's burned all right so we set up all the math which is great but we still have to go back and say well how do we actually determine how to charge for each source now there's a number of very reasonable things that we want if the utilization that we have is equal to our Target utilization we probably don't want a price to update that seems to be kind of like a good price however if we're over the target utilization we would want the price of that resource to increase because if we want to make it more expensive so people decrease their usage and if we're under kind of vice versa so a number of things have been proposed kind of to this end one proposal from the ethereum research forums back in January was this price update rule here you can kind of go through and basically see that it does satisfy these properties that we want however I could write down a bunch of other price update rules that also satisfy these properties so this kind of begs the question is this a good update rule or like what is this update rule actually doing are there other update rules that are better or have different Behavior how do we go about analyzing this and kind of the punch line of this talk is that um one the all these update rules are actually implicitly solving an optimization problem and a specific choice of the objective which you can think of is how the network designer wants the network to perform of that optimization problem is going to then give you a price update rule so this means essentially what I kind of want to convey is the a good way to think about price update rules is not like oh how do I design the best price update rule it's what do I actually want the network Behavior to be so kind of what is my objective and then from there we'll show how to get to the price update rule so this brings us to what we call the resource allocation problem and the setting for now is we're going to pretend the network designer is omniscient and gets to choose all the transactions in each block I know this is entirely unrealistic or not even unrealistic it's just absolutely false however this is going to allow us to build up a very useful mathematical problem that's going to get us to the price update rule so there's a few things that we need for this problem first we want a loss function that's defined by the network designer and this loss function essentially is going to be the unhappiness with the current resource utilization so there's a few very reasonable or potentially kind of silly loss functions that we could choose one is this so the loss function of Y remember Y is going to be the resource utilization of a given block maybe it's zero if we're exactly at our Target and it's Infinity otherwise another thing we could do is we could say that actually we don't care if we're under the target we only care if we're over the target so we can say okay the loss is zero if we're under the Target and it's Infinity otherwise again these might not be what you actually want to do in practice potentially you want to have something where if you're a little bit off the target you're not that unhappy and then it grows say quadratically as you as your deviation increases but the whole point is we only need something that tells us kind of the unhappiness with the current resource utilization then we need some way to say what is the set of allowable transactions and in this we're going to encode all constraints in the set s so this is going to be this binary set that encodes things like Network constraints so like earlier a block in ethereum is invalid if it's over 30 million gas however there's a lot of complex interactions among transactions as well so for instance if a lot of Searchers are all trying to get a specific liquidation only one of them can get that liquidation and this can also be encoded in this set so this is a very general kind of object that just says what transactions are okay we're going to do a this is kind of the first mathematical trick that we play here um and this isn't that important but it's uh essentially instead of considering s we consider What's called the convex Hall of us this just means that instead of forcing X to be zero or one we allow X to be a fractional value between zero and one so the way to think about this and the way this kind of makes sense is from the network designer's perspective uh you care more about the average case or the average kind of usage of the network not one particular block so say if XJ is a fraction that would just say that we include that transaction after roughly 1 over x j blocks and we'll see that we can actually remove this constraint in a little bit but again this is just to set up kind of the mathematical formalism so this doesn't really matter this won't really matter in a bit but I just want to be complete all right the final thing that we need is we want to know how much utility a given transaction gives to the Joint user and validator set we group these two um these two parties together into what we call the transaction producers and the reason we do this is because we don't want to deal with kind of the game theoretic analysis of uh looking at bids and auctions and that type of thing um so we assume that kind of these this group of people is together they're submitting transactions and those have a specific type of utility you'll see that our mechanism actually doesn't matter it doesn't matter that we group these things into the transaction producers but this does present an area for future work and I'd like to point out that we almost never know Q in practice it's more or less impossible to know that however we will see that this actually doesn't matter once we write out this problem okay so a lot of setup I'm sorry um but this is kind of where we get to so what is the resource allocation problem it is to maximize the utility of transactions minus the loss that the network um that the network has subject to kind of the resource utilization being defined by the included transactions and the transactions being allowable so this is the ideal kind of best case scenario of what we would actually like to solve for all the reasons I mentioned earlier this is not something that we can actually solve in practice but we'll see that it turns out to be a very useful starting point um and again this is because you know the network designer doesn't include say which transactions are included Q is unknowable you can't partially include transactions all of these issues however we'll see that we can actually pull from a branch of math called convex analysis and specifically Duality Theory to take this problem and turn it into a way to set prices so that the validators and users or the transaction producers implicitly solve that optimization problem without the network designer needing to really do anything just update prices in a very simple way all right so the the 30-second version of Duality theory is essentially it allows us a way to relax constraints into penalties so I can say that you actually don't have to satisfy this constraint you just have to pay for every unit of violation and this allows us to take Y which is what the network designer cares about that's the throughput and decouple it from the transactions that uh are actually included in the block there's just going to be a penalty for these two things not matching exactly however what strong Duality tells us is that if we correctly set the penalty this penalty being the prices then the Dual problem is going to be equivalent to their original the original being this problem which is what we actually want to solve and these two utilizations are going to be equal and they're going to have the same optimal value so again this tells us we correctly set the prices and we solve this problem without you know having to know q without caring about the fractional transactions without all the things that I mentioned are issues all right so kind of turn the crank of the math a little bit and you can decompose this uh dual problem so the Dual problem is to maximize this thing or sorry to minimize this thing into a network problem and a block building problem and P is going to be the Dual variable that's going to connect these two problems together so again those are the prices and the prices are essentially a penalty that we pay per unit violation of this constraint this first term here is actually easy to evaluate you'll probably just have to trust me on this it's this object called the central conjugate it's something that we have in closed form and that means that essentially this can be run on chain however the second term is a little bit more interesting so let's look at it in a little bit more detail what does the second term actually saying well it's saying maximize the utility minus the cost so this is the net utility subject to the transactions that we can actually include this actually has the same optimal value if we just use S instead of the convex Hall of s and this is exactly the problem that is solved by the block producers so what does this mean the network never has to solve this problem it could just observe from the previous block which transactions were actually included and then it kind of gets the solution of this for free from kind of you know the decentralized block Builders so what do we get at optimality well if we assume the prices are set correctly so that's going to be P star and then the block Builders use those prices to include essentially the transactions that are optimal then what do we get well we get that the uh resource utilization of the network is exactly equal to that of the block again that's back to what I was saying earlier is that we essentially get that this constraint does hold an optimality and Y satisfies this which we can look in a little bit more detail um what this means is essentially the prices that minimize G so this is the Dual problem charge the transaction producers exactly the marginal cost faced by the network so if you set the prices optimally for whatever loss function that you define the marginal cost of like using more of that resource is exactly what the price is that you charge furthermore these prices are going to be the ones that incentivize the transaction producers to include transactions that maximize welfare generated minus the loss incurred by the network so that's back to uh that original optimization problem that we saw you correctly set prices you solve that problem the network designer doesn't need to know the utilities or anything like that all right so okay that's great I still haven't told you how to choose prices I've just kind of talked around this for a while so how do you actually do this well we can compute the gradient exactly and um what is this well essentially the network can determine this y star and I said earlier that this is computationally easy then this x-star at some current price is found by observing the transactions in the previous block so then all we do is we apply our favorite optimization method like gradient descent and we update the prices using this gradient up here there's a lot of other optimization methods that you could choose here they're going to have different convergence behavior and different trades-offs between say convergence and complexity this is all stuff that we leave for future work just to go through simple examples of what I saw showed earlier so let's say you had this loss function looks kind of silly you actually do get somewhat of a reasonable update so this is looks like the residual so you essentially just update your prices by some you know fraction of the residual if you use this one where you're only unhappy if you're over the utilization you have the same update except you essentially make it so these are non-negative so if any of these are negative you zero them out and so this you can actually see that this makes sense here in this first loss function we're unhappy if we're under the utilization so this means that we might actually want negative prices to incentivize people to use more of a particular resource here though we actually don't care if we're under utilizing based on our Target so we're never going to have negative prices and again this is to kind of get to the point that the network designer chooses the loss function and the loss function encodes exactly what your unhappiness is with a particular resource utilization and then once you do that up update rules that will maximum or sorry minimize that loss function will fall out of it so it comes down to instead of choosing what the update rule is you're choosing what the loss function is all right um so this is a lot of math we did some numerical work to kind of see how this would work and very simple um very simple examples so here we have kind of a steady state behavior of a network with only one type of transaction that's being submitted you can think of this as pretty analogous to that example that I showed at the beginning of the talk but you can see that one dimensional prices are doing about 10 transactions per block and multi-dimensional prices are able to eke out maybe like two to three more transactions per block but this is even when you you know it's the same type of transaction that's going through so even this kind of like the simplest case you get some improvement from using these multi-dimensional prices um and I'm not going to go through all the details of kind of how we set this up but I would encourage you to look at the paper for that however um where this really shines is when we have a distribution shift so in this example what we did is we have this type 1 of transactions which you saw earlier but we add this type 2 transaction which has a much different resource profile so you can think of this like an nft Mint or something and they come at about block 10. so the multi-dimensional prices are the purple and blue and you can kind of see that there's this nice Spike here where we do less of type 1 transaction more of type 2 and then kind of once we go through all of these we return to zero and we clear some backlog after we've gone through these you could also see on the right here these are the multi-dimensional prices so once we hit block 10 and the distribution shifts a lot this uh light blue price goes down the other price goes up quite a bit and then they return to steady state a little bit long a little bit afterwards um again the uniform prices are still able to adjust to a certain extent but it's going to be less throughput overall and back to what I was talking about earlier where you have some Target utilization that you want to use you can see here in the second example the dashed lines are going to be the targets so the uh multi-dimensional prices which is the top deviate from the target for a short period of time to handle kind of the big spike in transactions but then the network returns to steady state afterwards in the uniform prices where you can think of you have less dimensions for this controller you essentially get this oscillating behavior and you eventually return to somewhat of a steady state but you kind of get a lot of a mess right here as your trans as the distribution shifts cool um so there's a lot of future work to be done here um one thing that we didn't do is super extensive numerical examples and you can imagine that using real data here might lead to valuable insights that allow you to tweak the framework in specific ways in addition like I mentioned earlier we grouped the transaction producers or we group The users and validators into that transaction producer kind of set and there is some work on the dynamical behavior of like essentially how do we make the strategy proof how do we um kind of you know we just talked about essentially the amount that was burned by the network in our prices so how do we kind of you know make this into an entire system um also I mentioned earlier that uh the update rule while I chose gradient descent here there's a lot of other things that you could do you could actually choose the update rule in a way that gets you something that looks very very similar to what was proposed on the ethereum research forums back in January and there's a question of okay well which update rules are good which update rules are the most useful and how do you trade off between say convergence Behavior um and complexity so how quickly kind of your prices can adjust and how much work that you're doing on chain then of course on the system designer side so if you're actually trying to use this in practice there's a lot of questions that this General framework doesn't totally answer so for example like you know what should the actual resources be in a given system and how do you trade off kind of the complexity pricing every op code every sequence of op codes and so on and the ease of use of these things and then of course how do you determine a loss function for the desired performance characteristics again kind of the very important Point here is that system designers should be thinking about these questions but should not necessarily be thinking about okay well like how do I do the exact update rule for prices um because in this framework if you think about these questions then the update rule falls out quite naturally all right and I encourage you to check out the paper which has a lot more and is kind of like 38 pages that goes through this entire thing and excruciating detail um and happy to take any questions thank you yeah seeing as your your models you're willing to give a different cost to different op code and resources and everything uh I think something that could be interesting to see is um the order of a transaction itself if I have different costs on items specific of storage like for example Nova semi visa thing and generally speaking if you eat a storage slot earlier it does much more potential value because this menu being settled first what would be the impact of costing differently uh storage uh of code depending on where you are in the block and generally speaking in terms of resourcedurization to anything that happened earlier in the chain is more costly for the network as a whole because you need to store it for longer and uh I don't think your framework is straight up compatible with this costing because it's missing one dimension on the Vector cost Maybe I'm Wrong yeah that's actually a great question um I think it's compatible with the first but not necessarily the second or the second one you could probably put into it but it would be a little bit harder this kind of multi-block one however for a single block um you could actually view you know that set s can saying like you know this transaction goes before this one or this transaction goes after this one and then perhaps if you're the second uh transaction in the block you're actually using a different resource so you're using like the second read so that should be extremely beneficial on field from a network if you can convince more people of going this direction because this means lower cost for everyone and better reputation first one so very good direction I'm very happy to see I'm not saying it's easy to implement though very difficult to implement but if even if here it breaks like implementation is not going to be possible thank you so do you see this research being applied directly for example in ethereum in like I don't know 50 years or maybe sooner uh I think there's probably some people in this room that could answer that better than I can but um I think we we've gotten a lot of interest from different protocols that are you know Roll-Ups um Etc that are interested in us and from the ethereum research team as well um I can't speak to development timelines though and when this stuff would be like I said there's definitely quite a bit of future work that has to go into making this production ready um and I imagine that uh you know newer newer chains that maybe aren't as uh don't have to pressure test their changes quite as much we'll probably adopt something like this before ethereum would you um so in the interest of keeping this a convex optimization problem are there any limitations this puts on how we can construct different parts of the problem so such as the Lost landscape or have I missed something and is there kind of a chance we can land in a local Optimum rather than a global Optimum here um also a good question well so the loss function has to be convex uh so there's you know one immediate thing that you have from con and you can imagine that maybe I don't know if there's two states that you want to run in and maybe sometimes you want to go hit for one target sometimes you want to hit another that wouldn't be convex if you kind of your landscape looks like something like this um so there definitely are limitations the other thing here is um we kind of have this uh the resource part is very general and to the question earlier that you can kind of have these resources that are dependent so like one transaction can be dependent on another however we do encode this all in like an additive linear way um and there's it's probably not the most efficient thing to do um for the reasons that I talked about earlier is you kind of get this exploding complexity um as you do that however if you don't do that you get to kind of the non-convex world so it might be a more succinct or lower like uh complexity way of describing what it is that you want to do but you won't actually be able to solve it and this entire framework does rely on strong Duality which you only really get in convex on you mostly only get in convex optimization problems or it's very rare to get it in non-convex problems and that that allows us to look at the prices which is kind of the Dual of that instead of looking at like what transactions do I include I look at how do I set prices but that's a great question thank you the video thank you and now people let's go to the top of the mountain to find where is going to be defcom7 see you there