Multidimensional TFM Design with Guy Goren | a16z crypto research talks

Transcript

Thanks for joining this talk. It's going to be kind of focused on Aptos and multi-dimensional DFM pricing kind of applied there. So I'm happy to have Guy Goren here speaking to us. His PhD at Technion was a researcher at Protocol Labs for a while and now he's currently a researcher at Aptos. And so I'll hand it off to him. Thanks. So I'm going to talk about multi-dimensional gas markets and I want to start by saying this is not something that we have in production or also that is currently really a planned for production. It's an exploratory thing and we're doing some research about it. So hopefully it's going to be an informal talk. We'll see.

The questions part is not just questions from you to me about what I'm going to talk about but it's also questions from me to you about okay what would you think? How should we design those things? What are interesting problems there? And if uh you know, since it's really exploratory, if you'll have good ideas, maybe we can convince the Aptos to implement them. Well, that would be cool. So first of all a bit of the introduction. Aptos and I think almost every high throughput blockchain, the way that they work is order then execute.

So first of all, we order transactions and after they're ordered, only then execution happens. And for us actually, the consensus, the ordering part has much higher throughput. So this is not a bottleneck. The bottleneck happens in execution. So we need execution to be very efficient. And for execution to be very efficient, there are different resources that are being used in the execution. Right? You have a for example, what do I have?

This is a CPU, that's easy, and this is a disk. Like memory writes, let's say. Because we want to be very efficient, we need to also utilize our resources well. And if our CPU is uh mostly idle because our workload is uh disk intensive, we write a lot, then this is not efficient. We could have done more stuff. Um this block. Now I'm going to talk about gas. We use gas to uh evaluate the efforts that a machine puts into executing a block.

But we can also view gas as a proxy for time. A deterministic way that is consistent across all uh different validators. And we can look at it as a proxy for time in the sense that for this block how much time would it take for a benchmark machine What is a benchmark machine? That's uh different question. But how long would it take for a benchmark machine to execute this block? And why this is also important? Because it's important in an engineering sense.

We want to but we want to have a a pipeline of uh how the blockchain works. So you execute a block, but uh there is also a time that you need to transmit the result of this block or use network king. And at the same time you want to execute another block. So you want to engineer it in a way that the block execution and the networking time are more or less on the same uh the same side, like on the same duration.

This is why it's also important. Okay, that was the introduction. And now let's see how the market currently works. So the gas limit, we can see it as an upper bound on the execution time for a block, right? Currently, when we have the single gas, so what does it mean? It means that we don't want to be more than the CPU limit here. Because if we have a lot of a lot of work for the CPU, we're going to exceed the time for the block execution. The same thing is is true for the for the disk right, so it's Right? And what currently happens?

Currently, actually, we take gas and it's the same gas uh either if it's a disk operation or if it's a CPU operation. And the way we measure the gas limit, we're saying, "Okay, the CPU gas plus the disk gas should be smaller than some constant. That's the block limit." And this gives us this uh red line here. Now, this is how most things work now, and you know, it's okay. We get all this green area, which is good and viable and we're not uh taking too long, but we're not getting all this gray mostly efficient area, which actually is what

we want because we want to be as efficient as possible. And also, in theory, we have these uh red areas that are a bit problematic because they exceed the the time limit that we want, but it's in theory. In practice, it's very hard to find uh to find a workload that is only CPU or only disk, right? So, this is why the design typically it's not uh it's not even in the single uh dimension gas, it's not corner to corner, but they are we allow ourselves to steal a little bit because we do want to get maximum efficiency.

Quick question. The constraints, like, say for example, they held on average. And so, like, you start with this line and there was one block that happened to have this weird profile. that was a lot of CPU and no disk. That would be a disaster or that would be fine it will just get averaged out. So it would be problematic because imagine that you have this variability if all blocks are efficient then like they have a a good a good measure of having like from both balance then you're okay. But, if you have some blocks that have I don't know what 50% more CPU and some

blocks that have 50% more uh disk then each one of those is going to be less efficient. So, it doesn't average out, right? The variability. Oh, yeah. So, we I think it's pretty obvious that what you want is you want to have uh this kind of limit which means it's a multi-dimensional gas market. Right? If I reached this like uh the CPU limit I can still put in the block more disk operations. Well, it seems reasonable.

Uh a few things we maybe want to consider. I talked about CPU and disk, but what are the dimensions that we want? It's a question. Uh maybe we also want to take networking into account. No, maybe we want to take other stuff. Now, there's a question because the more dimensions we have the better accuracy and the better efficiency we have. In theory, what happens in practice? In practice it requires more complex gas metering. And then what might happen is that we're going to spend 20% of the time I think it in Ethereum someone did a research and they found that even with the single dimension it's something around 10%

that it took them some point for gas metering. So, instead of using your resources to execute transactions, you're using your resources for gas metering. So, this is why you don't want to have too much dimensions and too much complexity. Another thing is the orthogonality. I don't know, maybe there is some correlation between uh between disk and CPU or disk and bandwidth. So, the dimensions doesn't don't have to be orthogonal to each other.

Another thing is the shape. I'm talking here about a rectangular like a cubic shape or whatever, but we can have other shapes. You see, there is the triangle shape that we currently have. Uh maybe we want to have something more similar to a quarter of a circle. Because we are saying, "You know what? Even if there is a lot of CPU, we cannot have also the maximum disk because they are going to delay one another a little bit. So, we don't want to reach this corner because this corner is No, it's a model, it's not reality. In reality, it's not going to stay in this corner. It's going to move out. So, we want to How do We have a lot of options. We need to think, "What do we want to do What do

we want to do?" Something that you touched before and is very important in every high throughput blockchain is concurrency. All right, we want to run on machines that have a lot of concurrency for the execution. So, we can run transaction concurrently. Not everything can be run concurrently. There are sometimes conflicts. How do we account for them? In the in gas, right? So, some approach would say, "Okay, if I can run the transaction concurrently to everything else, I'm going to charge it less gas. It's going to cost less gas. And if it is conflicting with others, I'm going to it's going to consume more gas."

I think that is the wrong approach because that immediately opens the door to attacks. Let's say uh I don't know. I don't like uh Leoba and she's submitting a transaction. I want her to pay more gas, so I'm going to submit something that's going to conflict with her and all of a sudden she's paying more. She's consuming more gas. That's not a good uh user experience that we want. So, instead what we are currently thinking of is that if we have a lot of concurrency, what we can do we can actually increase the the block gas limit.

So, the transaction Leoba's transaction is going to consume the same amount of gas if it's concurrent or if it's uh not concurrent. But, if there is a lot of concurrency then actually we finished early and we have more more time. So, we're going to give the block more like a higher gas limit. We can use because that at the end is what we care about. What's the time that it takes to execute a block? So, currently this is why I don't know if that is the right approach. I'm just saying this is currently what we are thinking about.

If you can do that just by default, why don't you just do that? Do what? Increasing it. Increasing the gas limit. Because uh increasing the gas limit, what does it What does it mean? The gas is just a number that we have, right? And in practice, what you care about is the time that it takes to execute a block. So, when you have concurrency it's not so much the amount of transactions that you are executing, which in some sense is the gas that you are executing, is how much they can be in parallel. Because if you have to execute the same amount sequentially, it's going

to take you much longer. And then you have problems. I guess a lot of you do know fee markets and how they work in practice and you know that the highest fees gas fees are for storage and I haven't mentioned storage here. And this is because we think that storage should have a different kind of market and should not be together with the gas for transient costs because the execution costs are happening right now and that the validator that is executing right now is paying for them.

But storage, well, the validator 2 years from now is still going to have to have disk space to store those stuff and all the operations that's going to happen that's going to happen on a higher like larger storage are still going to cost the validator 2 years from now. So, we think that should have a different market. This is why this is out of it. Okay, so we kind of understand how the market design, but then we need to design actual building blocks that are going to be used in the market right? Assuming this is the market, how is it being implemented? We can think about the players here. So, we have the validators that are packing the block and they are very interesting for us, of course. We

need to design an algorithm for them into this market. And this algorithm, it's important to to think about the complexity of this algorithm against how much profit they are getting from running it or from deviating from it. So, if we have a block packing algorithm that is relatively simple and gives you, I don't know what, 99% of the of the best revenue that you could hope for and deviating from it would require a lot of complexity and this is a pretty much good algorithm because you don't expect a lot of deviations. It's important to think about it. Now, we have the users that are bidding for the

limited resources and for users we typically want to have a simple bidding strategy. All right, that's uh like the holy grail is to have truthful preference reporting. And that's the simplest possible. But then there is something else that that in game theory we don't think about much and that's the wallets. But I argue that we do need to think about the wallets because most of the users they don't interact with the blockchain uh directly. They interact through wallets.

And wallets actually we we can expect wallets to handle some complexity. They can run algorithms, they can have access to data. It's okay to to have wallets that are running complex algorithms. So we also need to think about designing for wallets and how the wallets can interact uh with our market. Maybe one question, maybe I missed it, but is it known sort of which state is um accessed by all of the transactions ahead of time?

That's a good question because there is no clear answer for that. In some cases you do know and of course you want to know because if you know it it gives you more power in the designing of the algorithms to be more efficient. But in other cases you don't and actually imposing it on the developers because it's imposing them imposing it on the developers to actually report what they are doing is problematic. The other option is to pre-execute stuff but this is not good for for the latency. Currently we have sub-second latency and we are very like it's very important for us to have this end-to-end very fast

latency. And if we're going to add even this pre-execution it's going to take I don't know what, another 300 milliseconds or something like that, which is something we don't want to pay. Good question, I don't have a clear answer. When we are packing a block we can think of several ways to pack it, right? We can have a multi-dimensional knapsack like a first price auction in some sense, in which case what the validator see, the value for each transaction is the price per dimension times the consumption that it reports or or that we know somehow.

Okay, and then you do a multi-dimensional knapsack. There are pretty good heuristics for that, so that is good. Can run them relatively simple. And it's efficient in the resource utilization, right? Because you want to pack it as much as possible. And it's also the nice thing about it that it's kind of incentive compatible, right? The the validator is trying to maximize its profit, so that's good for us. Then we can have the EIP-1559 style which is a simpler most of the time, right? You just say, "Oh, if you bid higher than the than the current base fee, you get in." Not as accurate generally speaking, of course

not accurate. Sometimes it's inefficient because imagine that now we're not in the steady state like if we're always in the steady state, it doesn't matter. Everything is easy. But if now there is a change and all of a sudden the demand drops, but in the mempool there are a lot of transactions that are willing to pay to pay a cheap fee, right? It's not that there is no demand at all, it's just there is no demand for high price. But the base fee is still high. The block is going to be empty. And that's not good for us, right? Because we are not utilizing our block, which is also problematic for the validators because they are not getting revenue.

And they would like to. So, we have to force them to do it. Possible, we can force them to do it, but it's it's less good. that sense. For the users, then we have the opposite way, the the first price option knapsack is much more complex for the users. Now, I do not need to tell you that. Like, how do I decide how much to bid? It's a big problem. And the IP 1559 should be simpler, but also again, it's inefficient at times that there are there is available block space and the validator would like to include my transaction, but it doesn't because the IP 1559 uh well, still too high. Didn't reduce fast enough. Now, for the wallets, then the

IP 1559 is easy. Dealing with uh a first price auction is much more complex. And I haven't talked about why is it more complex. We can estimate the the price kind of we want to estimate what is the price that you need to pay to get included or to give you some kind of a distribution. So, first of all, we can estimate it based on the past, right? What we currently think of like basically is that by on-chain information. We can look at the past blocks, what was included in them, the distribution of the prices there, and look at that. So, that is a way to do it. A nice thing is that a wallet can also add and merge uh off-chain information, like information

from the mempool, or maybe other information that it predicts uh higher demand or something because it reads the new I have no idea. There is a lot of uh high-frequency trading that is actually doing those kind of stuff, looking at the news and predicting uh stock prices based on that. Now, there is the multi-dimensional issue because when I predict the price, how do I assign a price per dimension? The thing that we are that we currently think about is uh just using statistic dispersion.

Right? We see uh across all the the transactions that are included, we see what is the price that they paid, and we are distributing it according to how much they consumed from each resource, and we are taking the average on also. It gives us kind of a dispersion statistics. Maybe there are different ways, maybe there are better ways. I don't know. That's uh, also open for uh, for research. So, questions. What can we prove here?

Interesting problem in different aspects. Even for the block packing, right? Even that would be interesting to show what can we prove how optimal is it? Okay, if we have a packing algorithm that that a guarantee we can give the validator is that, you know what, we guarantee that you're getting at least 50% of the of the maximal price, they're not going to be happy with us. But if we can prove to them that, you know what, in 99% of the cases, in some distribution, you're going to get uh, at least at most 1% off from the optimal packing, and in 1% you're going to get 50% off, they're going to be very happy.

Right? So, so what can we prove here is interesting, and there are some works on the matter. This is just uh, algorithmic stuff. Then there is game theory questions. Well, is that is that good for the users? What can we prove it? Is it strategy proof? Maybe if they know what the validators are using, the the algorithm that they're using, they can bias it somehow. So, how much do we want to have randomness involved in the wallets? Uh, those are interesting questions here.

Okay, how efficient is the price discovery that I've just uh, described before based on the past and and based on dispersion of uh, two axes and two dimensions how efficient is that? What can we say about that? I also described two possible mechanisms for the packing decision. Ethereum that they are talking a lot about multi-dimensional gas fee. They are talking about having a EIP feel like a basic per dimension. Right? But there's also the possibility of having the first price auction knapsack.

What can we say about the difference between the two? Can we give some quantifiable metric? I don't know. There are a lot of interesting problems here and I would be happy to get some ideas from the people here. Yeah. Uh this is a question I haven't answered anything. Um is the knapsack problem you're solving is like is the knapsack large in the sense that like no single transaction is going to fill up more than 1% or much less than 1% of the space or there's sometimes very large transactions and the knapsack solver has to really account for the discrete So actually typically for us it's uh that's the easier problem. Where the

where the elements are typically relatively small. So So that is good for us. We can We can assume some kind of a distribution where where it's typically relatively small. Okay. So then follow up question would be does the like say you were to look in hindsight as to like what the optimal packing happened to look like? Um how does it like like you would you know, notice that like one resource seems to be more congested than the other and you could probably like maybe there's a natural price based on that. Does that tend to be constant?

Like it like if you were to look at several blocks in history, does that change tend to change like rapidly over time that like one block everyone wants CPU, the next block everyone wants disk and or does the demand for each resource tend to stay fixed relatively? I think those are very interesting questions. I can tell you what I kind of know, but it's not the there is not enough empirical studies that I am aware of. I think Leoba does a lot of empirical studies on Ethereum in that kind of sense. I have a feeling of is that the workload typically changes like across time. You you do have on average something, but you get all of a sudden these uh 2 hours that you have a workload that is very CPU intensive.

And then like 2 hours later, you will have a very disk intensive stuff. And that currently causes us problems. Like all of a sudden there was something that I didn't even mention here, which we call a output because that is something special for us, which you can see look at that another dimension. And we had this weird contract that had a lot of demand and it produced huge outputs. So for half an hour this was the bottleneck. Yeah, and then we had a different contract that was relatively balanced and managed we managed to get I don't remember how much

I I think it was 2,000 or even 4,000 transactions like per second for almost a day. So the workloads are very very variable. Yeah. A lot of variety in them. Please feel free to talk to me if you have any ideas. Be happy to hear.