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