Local fee markets with Abdou Ndiaye | a16z crypto research talks

Transcript

Hi everyone. Welcome to the the afternoon session where we'll have kind of two talks talking about fee markets. And first we'll have Abhilash who's a professor at NYU. Working lots of economic stuff in particular in the last few years has kind of been thinking about fees on various blockchains and Bitcoin, Ethereum, and other ecosystems. So happy to have him here talking to us about execution pricing. Great. Thank you for having us, Bernab. This is a working title and work in progress as well. Following some of my work on Bitcoin, Ethereum, this is more looking at some of the more high throughput blockchains where I think there are many questions of parallel execution that happen here. When state

is congested, we have had alluded yesterday to these discussions about even multi-proposer type of uh consensus as well. So now I put under the umbrella similar problems. The first one would be like something like in the case of Solana which is often referred to as local fee markets. So it's often hard to see what it means, but for some resources here the way to think of how Solana the life cycle of a transaction in Solana from this Amber research article, you have clients who send transactions and there is an RPC server and that sends it to several validators.

And now at this point there is a some parallelization that happens which is that most of the these validators, they just use the same scheduler. And how does the scheduler schedule the transactions is in this following way. So what is interesting about Solana and also you can think of some of others is that once you submit a transaction, you also refer to the accounts or contracts that it reads or writes. Okay, and so those when it tries to execute in parallel, it kind of locks those contracts. Here, you can see that there are turn the transactions in black do not share any overlapping accounts.

So, accounts here would be like contracts it touches. But those in red share one, which is C. Because and it starts currently by just looking at the first one that refers to C that touches C and executes that transaction. So, the transaction that will execute first will be here ABC. And then it executes D, but then it cannot execute CJ. It fails. So, because C is already the transaction that's touching C is already executed. In the second thread, C is not touched there, so it executes in the first iteration those that do not touch C and it puts CJ in the next iteration and does the same process. So, this elimination process

essentially, which is not a market mechanism driven kind of way. So, essentially even when people are paying fees and there is a certain ordering, there is a lot of uncertainty and unpredictability on when your transactions are going to go in. Okay, they are just sent to different uh threads and these threads look at those that are contested. Uh execute those transactions that do not have any element that is contested and then purges the rest and then picks the first one that is uh referring to that that is uh reading or writing that, which is the first one here. Okay, so now Solana talks about a local fee market, which is an approach to also price these this C state here, for example, that is

touched by many locally. Okay, so that uh people who want to who are if it's contested, they can put a higher price. How can you do that? Okay? And I think for their execution matters. Another example application is also what I call the DAG-based protocol. So, we're going to have here a talk later by Aptos, and this is also the case for Sui. Often, these how it happens is that there is for consensus, you create a DAG to do more things at the same time, but at the end of the day, you need to execute. And execution, because of uh the fact that, you know, to avoid double spending, execution will happen in some way secondarily, and when things are contested, there is an issue with execution.

And for example, here this is the case of the DAG-based protocol, also this is the Bullshark example. So, you have different rounds here, and each of these what they refer to are different uh sub-blocks. A1 here would be like the leader, and A2 would be another leader in the second round. And at the end of the day, when you are executing, you need to make a choice on how you're executing. Each of these sub-pieces are blocks. Okay? The only constraint that is required for consensus is that you follow the parenting, is that A1 here is a parent uh to this block, so you need to execute those that is in A1 here before executing the the rest. So, you need to follow this chain, this causal

chain. But then, the rest within a causal chain, for example, all of these are um um all of these are parents to this one, and you can uh you can order them in separate in a in a any way possible. You can order within the transaction in the same block, or across blocks you can order them. So, what do you want to do? Okay, do you want to do one global ordering, or is there anything else to do? And finally, the last one is, I think yesterday we saw the discussion around around multi-proposer blocks, and there came a lot of questions around at the end of the day, how do you price? How do you go from all these proposals to come them together? Are you going to just do

one large auction on them, or are you going to do something more? So, just two fixed ideas. This is not what I'm going to talk about is different from the execution tickets and the futures market for block proposal which you hear which is like, oh, there is some sort of uncertainty over time on what would be the future gas or I want to make guarantee that I can have I can have a block included down the line. So, I'm going to have this execution ticket. So, this is different. This is all about execution when you have this parallel parallel execution at the same time. Okay, so the question then would be because we know that when you have something like this where you have states that are different, different sort of queues, people valuing things differently, you

can do like a one large multi-dimensional knapsack problem and that is not something that is easy to implement. So, what are approximately optimal mechanisms for pricing and prioritizing parallel execution? And a good metaphor I have for it is when you have different tolls, okay, different cars, you go to different tolls, but at the end of the day, there is like a something that blocks there down the line. So, you need to choose which toll lane do you prioritize at the end of the day, okay, when things are congested. So, how do you do that and are there any insights from economics that tell us how to do it, okay? My argument is going to be that yes, there are insights from economics and in fact it's very

important. It's not just a technical thing, okay? It's economics are important. So, because it's a short talk, I'm going to give you an example first. Okay, so let me give you an example where you're going to have, let's say the queues are predefined, okay, and you have three transactions in each different queue. Think of these queues, they can be like either, let's say I define them by contract, okay, for the case or account for case of Solana or some state, okay? And then you have the three different transactions. So, each of these transactions, this is the amount of gas that they are willing to pay. Okay, A1, A2, and A3 in QA and B1, B2, and B3 what they are willing

to pay in gas. I created these where I'm considering that the expect these are generated from the same distribution. Uh the A's, which has expectation 10. Okay? And the B's, expectation six. Okay, so what happens in this situation when you need to execute and you need to when things are congested, for example, you need to go and switch because you are going to execute when by one you're going to you need to switch between the lines. What would happen if you just did one global ordering which is just going to be okay, I'm going to just pick the first the transaction that have totally a higher amount of gas. Okay, and there will be new transactions

coming in. Okay, there will be new transactions coming in under the same distributions. So, let me give you an example of what is the type of issue that can happen. So, if I just do one global order, let's say here what I'm going to do, okay? I pick A1. Okay, but then the time passed. A4 and B4 came. Okay? Generated by the same distribution. So, this is an example of what can happen and a very likely example. I pick A1, so these are the executed from global ordering. So, I just order by I pick the first. A1 has 15.

Okay, so I execute it and then A4 comes. Oh, it is 12, okay? Expectation of 10, 12, not far off. But at in the same time, B4 came. B4 is just five. So, I add it to the queue here, not going to execute it. I execute A4 because the highest. Okay? And then once I execute A4, A5 comes. What is A5? A5 is seven and B5 is seven. Okay, so from that moment what is there? Because again seven here this expectation was six, this one was 10.

So from then there, okay, I execute what will else will I execute? I'll have to execute A2 because that's the highest one. There are others coming in. And only then will I be able to execute B1. Okay? And then I'm going to revert to A5 and others are coming in. Okay, so here what I show you here is that the length of this line, okay, gets longer and longer. And in fact you can show that even if there is an infinitesimally small difference in the way in which these are valued the one of the lines will be infinitesimally small small okay? And so if people are delay sensitive there is an externality coming in from this that is not internalized here.

Okay, so this is in a sense the problem with global order. So it really matters how you're going to switch between the two lines. Okay? So now what would be so because the sort talk an example again in this example what would be something that looks like a solution. Okay, you can say oh how about I just switch from one to the other? Yeah, but you don't know the length of the lines, things can come at random and others. So let me propose something. So imagine we knew these valuations and I think what I'm going to show you later in the model is that we don't know these valuations so what would be a good proxy. Imagine we know these expectations.

So one solution, okay, I'm not saying it's the best but a simple one which is say okay, let me just weight them all relative to this expectation. Okay, so I consider these are the same messages, the same information in these transactions, but they just have as if I'm discounting the gas that they put by this expectation. So instead of 15 I'm going to have 1.5 so divided by 10. Instead of 10 I'm going to have one. Instead of 0.5, I'm going to have Instead of five, I'm going to have 0.5. Same as here, the same ones, but I divide by six.

Okay, 4/3, 1 and 2/3. Okay, and then the same A4, same A5, B4, B5 coming. So, if you do this then, okay, what you are doing actually is you are looking at the prioritization between the two the right way, which is going to be two what I call the market value weighted ordering. Okay, this market value ordering what will do, it is will help you, okay, in a way that gives it gets a signal from the market to alternate between this. Okay, so in the example that I gave you, what you will get A1 and then B1 despite the fact that A4 was higher, but because this is a market that is overall more contested, people are paying for more,

it's not going to come yet. Okay, you so you can switch between the two, you balance out. There is a more natural balance here, and you can show that with this balance actually for this distribution, none of it is going to go out to infinity. There is a bound between the two. Yes. There's something I don't understand. If at each time slot, Mhm. you are executing one of those transactions, Yes. but at each time slot, you also getting one additional to each queue, you are going to grow to infinity. In your example, you executed one, but two joined, right?

One for each line. Yeah. So, if that is the case, you are going to grow. Okay, sorry, sorry. Yeah, so let's say in each slot you executed two. Yeah, yeah, you're going to grow, yeah. You're You're right. Yeah. So, you go because you say each time so you executing one. Yeah, I agree. So, each time so you execute two, and then the the two comes. If that is the case, that you that only one is joining, then at some point you're going to in the global order, you're going to empty the high priority queue the one that pays more and then you're going to start executing from the So sorry, okay. So let me revert correct my answer. So both of those are great points, okay? We're

I think what I'm trying to mask show here is that one of the lengths will go will grow at a faster rate than the other. Right? Then the rate in which I think the D of the shortening and the lengthening is something to figure out and I'm going to think about it more. You're absolutely right on your points. Yes. Can you clarify also when when we divide the value by the fee? Yeah. So what I'm sorry, do we divide the value by the fee? That's the first question.

What are we dividing by? Yeah, no, no, we are dividing by the fee. Right? But what is the numerator and the denominator when you compute 1.5 and 0.5? So this is the gas that people are paying. The gas. Gas. And then I'm order as if they put a gas of this. Right. Or or this would be my index of the metric of ordering. Right. But I'm thinking how do we get what 1.5? We divide the gas by what? This. Yeah. We This was our transactions. 10 divided by 10 1 5 divided by 10 0.5.

I see we divide by the expected value. Yes. The current expected value the expected value Yes. By the current average, right? Because then if you add new transactions the average will change. Yeah, so the average changes with the market exactly and but this is just if you knew the underlying distribution that is generating this. All right? And I think that's the main question is that how do we generalize this idea? Of course the mechanism is not as simple as this. Okay, the market values are not known. What will be a good signal for it? Okay, how do people value different uh states?

If you just say like, "Oh, I want to just find a very mechanical way of switching I pick one or pick the other." That's not the best way. So, you need to And what if there are several queues like plenty of them and how do you define these queues? So, okay. So, for this now that's where we kind of we write down a model the way we think about it. So, we're going to have a capacity constrained blockchain system which will be an NQ system where the people are delay sensitive customers. The execution times are IID with unit mean and users submit transactions to one queue.

Okay? So, this is assumption. I'm going to talk later about what is the notion of equilibrium here. You're going to have the arrival rate or what I'll call here market size of how many people are arriving to in this queue to submit a transaction of this big lambda I. And you have I'm going to focus on uniform prices. Okay? So, think of a posted price or one way to think about it once implementation would be essentially the base fee or each base fee is different base fee for each queue. Now, users differ in their evaluations V and these evaluations are drawn from distributions fee I.

So, each queue has its own distribution. Okay? And there is an arrival rate will be here now the this market size times the CDF. And from here I can have a marginal value function. So, what is a marginal value function would be uh given a certain level this would be the cutoff will be here the value or the cutoff value will be for any given arrival rate this will be the value that corresponds to that arrival rate. Okay? V the marginal valuation that will be able to be served. Okay? So, that will be able to be served.

Essentially the the the the in in this in this queue. All right, we need some way of valuing things. So the usual way, so people have linear values on their uh private value V. But it's observed here, there is no essentially like information problem, and we can have two types of costs. One is a multiplicative delay cost, and one is a linear cost, and they pay a price. Okay P. Now, this price depends on which one they choose, which of the queues.

For price PI, you're going to have a delay and a cost that depends on the whole distribution on the uh uh the arrival rates in each queue. Okay? So it depends on this whole vector. Okay? So it depends on the whole vector, this delay, this expected delay cost function, same as the ex uh the expected discounted delay and the expected delay cost. Now, what is the equilibrium condition? So the equilibrium condition here is that the marginal value of the user who is using who's going into a queue will be zero.

Okay? So the price they'll be willing to pay up to a price of what they benefit from it. P is equal to this marginal value here. What are possible ways to interpret it when it comes to the application that I gave you earlier? One is one of Nash equilibrium. You take the other arrival rates in other queues for given, and the let's say we use a in this and the users join each queue until the marginal value is zero. Okay? So each of the contracts are valuable, or each of the states users will join to zero, or another interpretation is that there is substitutability between queues, like in the case of the uh of the scheduler which can send to this queue or another queue. One observation here, because so often we talk about

distinctions between revenue maximization or social optimum. Here I just want to mention that the revenue maximizing prices here are higher than the social optimal prices because there are externalities that are not internalized by the revenue maximizer. Okay, but I'm going to focus on when I'm looking at optimal policy, optimal mechanism here to the social optimal ones, which is maximizing just the sum of the utilities. So, how does that one look like? And here is our proposition. So, the proposition is that when you consider the protocol optimizing social welfare, which is maximizing over these different arrival rates.

Okay, so it's maximizing over the arrival rates in each of the queues of the following. So, this was the utilities. The prices are just a transfer between the users and the validators. So, they they're not accounted here. Then we obtain the following solution for the price. How do we capture what does this solution says is that at the socially optimal prices the marginal users expected net value equals the net value externality she inflicts on the system. Okay, so the net value that they get will be the net value that they inflict on the system. Okay, so if there were essentially no externality here, keep in mind this is just for So, the price would be essentially zero. So, here the

relative price here is just essentially the externality that you are putting on others. And this externality is the marginal increase in lambda I which raises the discounted delays by this change. Okay? Uh this which is the multiplicative delay and you have also the linear delays as well. Okay, so this is to internalize the costs on others. A corollary of this is that and I want to just go take now more assumptions to get to a simple expression that is generally captures the insight that I mentioned earlier. Is that for

a specific distributions of valuations and cost functions you can find actually what are the relative prices that keeps equilibrium in the each in the markets. These relative prices will be again the how what is the weight of these different externalities on other users and because for the sake of time, I'm going to give this proposition which has the intuition of what I talked about earlier. So, what is this case? So, consider the case of inelastic demand. What does inelastic demand mean? Inelastic demand mean is that if the prices, let's say, that you charge in one market

okay, the base fee, changes people will not change much how much they are willing to submit transactions in that one. So, think for example something that is very hyped like a something that people want to use like an hyped NFT drop like a contract that is heavily used. Okay? So, denote this minimum of this elasticity of the our value function that depends on the arrival rate then we can show that so for this minimum the index So, if this elasticity is going to zero then we can have this approximation here for the relative prices of the optimal pricing mechanism which depends just on

these marginal delay rates. Okay? This term here is just a big O of this market arrival rate and when you consider an exponential non-show delay function you can show that it is approximately the ratio of this uh arrival rates of the market size lambda I and lambda J defined earlier. Okay? So, this is in a sense is that the relative market size obtained by the total gas paid in a market is a good proxy of the relative pricing of this.

Now, one element that is interesting to mention, which is this term here, what is the intuition of this term is that the more you have a market that is very small, which is this lambda I small, right? For example, there is not many users one wanting to arrive here in proportion, but that is very inelastic, meaning that even when you change their base fee, people will still want to use this, the more important it is to do this relative pricing and not just put one base fee, meaning that the more it will be to have this gap important to have this gap PI over PJ to be different, not just have one uh global auction.

Okay? So, that's why I give the example of a hyped NFT contract. For conclusion and discussion, the question now is how do you implement this? Okay? So, implementation, again, in ways in which people are thinking of implementing what it either local fee market so on, one way to say, "Okay, I'm going to send to the scheduler." And then they will just take the first come first serve or order by price but first come first serve. If the transaction already hit something that was already um executed, it's going to fail. Those are certainly engineering solutions, but I argue that if you don't have a way to switch between these different and prioritize the different

uh subspaces, substates, you will have an imbalance and you might have one state growing much larger than uh what queue growing much larger than the other. And in fact, the general idea, I think the general message is if you want to do something beyond just pricing of inclusion in the block space, you need to use information that in the transactions. One we we is is let's say the con- it can be at the contract level or state level or object, for example, for some blockchains like uh Sui that have this notion of uh shared object.

So, for example, you can define what I call here the local value of each either state or contract on object at a total gas paid by transactions. Okay? Uh in previous block that read or write it. So, you consider, for example, uh like the example I give often is So, in the Solana case, you have because you refer to the uh a- um account that you're reading or writing, you can compute the from a previous block why to avoid issues around simulation and so on. From the previous block, you can measure the level of hotness or local value of that uh that state, and you can have

a reference queue. Okay? It can be like a simple account like the native token send transactions that you update its base fee from from an EIP-1559 type of mechanism. Okay? And then everything else you uh price them relative to that reference queue. Okay? Each transaction will be assigned to the queue of its contract with the highest local value because you have to transaction that can read or write many several accounts. Okay? So, you pick the one that is essentially the highest local value, the most contested, because that's the one that will make it fail.

And it will be assigned to that. And from there you define for this uh for this queue a base fee that will be P1 times the local value. Okay? Of course, normalized by the right the right magnitude. So, P1 times local value here over the local value at in the Q1. And uh another way of doing it instead of doing this also would be instead of having the set uh a different base fees would be to just have one base fee, but when you do the execution you execute by doing what I did earlier which is dividing the local value or a

function thereof uh when you when you calibrate these parameters could be a way of uh implementing. So, this is the idea. This is what I have. Happy to field any questions. One thing, so I think one of the tricky parts of this in practice is that the transactions don't cleanly separate across queues. Like of like kind of overlapping different contracts used by different transactions. Is there a Can you extend the model to incorporate that or Yeah, so that's why so for example, I say that you you would the queues is just a conceptual thing.

The the queue here how I think of it is let's say a contract that is touching many a transaction touching different contracts. I will pick its queue as the contract that has the that has the highest lock what I call local value. That was the one that was the hottest previously. Should is the right model to have like different queues for different parts of state or is it like what's the how do you map between queues and parts of state? that's so that's why I think it So, let's focus on one application, okay? So, let's take the case of Solana. Solana has accounts. So, each account you can consider it as a as a queue.

Now, imagine a contract touches several accounts. I'm going to look at each of these account which one has the highest total guy that was paid on it in the previous block. That one is the one that is most contested. That's the one that is most likely to make it fail. I see. Right? Okay. Yeah. Okay. Great. Thank you.