Foundations of Transaction Fee Mechanism Design with Elaine Shi | a16z crypto research talks

Transcript

I'm very happy to be here visiting this amazing group I'm going to talk about transaction fee mechanism Design This is John work with my student Hau Chan so transaction fee mechanism right this is what we need um on the blockchain because the space on the blockchain is scarce but there are many users who there who want their transactions to be confirmed so they would all bid and you know we run an auction to decide whose transactions got confirmed okay so today bitcoin's transaction is a simple first price auction essentially suppose your blog has size k then you just take the K highest bits you confirm them in the block and everyone pays

their own bid and all the payment goes to the miner The Miner who mines the block okay so essentially whenever you buy a new block this option will be run and you know as we know from classical mechanism design first price auctions they aren't awesome auctions in particular uh you know it would encourage untruthful reporting right so for example you may be incentivized to build barely enough to be among the top case so you can you know still get confirmed but pay less so that's not too great and you know one obvious question is why don't we just use the classical body of work in mechanism design you know we

have learned from um action Theory the second price auctions are awesome options and so how would you run the second price action here let's say your block um you want to confirm four transactions so you can take the top four and in this case they pay the fifth price right so this is kind of generalized version of second price auction but the issue here is like even the auctioneer itself can be a strategic player and for example so here the auctioneer obviously the miner The Miner can inject a bit which is five and now 5 becomes the fifth transaction and everyone would be paying five and the miner would be earning more so the

problem here is like not only do you want a mechanism that incentivizes the users to behave honestly you may also want to incentivize The Miner to behave honestly as well so interestingly in this decentralized world this classical mechanisms fail like the vast majority of classical mechanisms don't consider Auctioneer as a strategic player I think there's there are some works like including maths work like for instance the credible action and they consider Auctioneer as a player but there the model is completely different from this decentralized setting so you know there's a line of work that looked at transaction fee mechanism design and all of these Works they kind of agree okay on the essentially a set

of this director so what is the dream transaction fee mechanism so as I said first we want to make sure the user's best strategy is just to behave uh to bid truthfully and and this notion agrees with the classical incentive compatibility notion In classical auction Theory but in now in a decentralized world we want a couple more properties and first we want to make sure the miners best strategy is just to play by the book The minor doesn't want to deviate from the honest protocol and this is called mic and secondly in this decentralized environment we have like this smart contract and which

allows Miners and users to collude so we also want the mechanism to provide side contract proofness and specifically this notion can be parameterized by a parameter C and it means minor colluding with at most C users they should not have incentive to deviate so let's say the coalition's goal is to maximize its own giant utility because they can use the smart contract the side contract to split off the gains in the background okay so if your goal is to maximize your joint utility you should not have incentive to deviate okay so among these three properties again these last two properties are kind of new in this decentralized environment

and this is where you know decentralized mechanism design departs from classical okay so and Tim you know started this line at work and he asked an interesting open question can we have a dream transaction fee mechanism that satisfies all of all of these three properties so what's interesting is if you look at other works out there um there is actually no mechanism that that is the dream mechanism we want and the closest we have come to in terms of achieving all three properties is actually ethereum's eip1559 and this mechanism was rolled out like in August

last year and and Tim actually was invited to do an extensive analysis of the scheme so most of this talk is actually not going to be concerned about 1559 but just for your curiosity and here's briefly how the mechanism works this is very high level so the this mechanism has two modes of operation when things are congested meaning there are more transactions than the block can contain then it kind of behaves like a first price auction right just like bitcoin's auction and we know that first price auction is not awesome so when the block is uncongested let's say the block we have more block space than the number of bits then the mechanism kind of

act like a poster price auction so what's posted price it just means there's a ticket or leave it price any bit that's at least this policy price will get confirmed and they pay the posted price and however what's interesting is all the payment is burnt The Miner receives nothing and the sperm rule is kind of interesting because it's a new element in blockchain mechanism design and you might wonder you know if everything's burnt why does the miner have incentive to mind because there's a fixed block reward and even before like 1559 you know most of the reward is coming from the fixed block reward anyway and because that's a constant it

doesn't matter to the game theoretic analysis so in today's talk I'm just going to ignore that um so what's interesting about this burn rule is like you might want to ask does the burn rule actually introduce more expressive power in decentralized mechanism design and I'll try to answer that later in the talk as well okay so what I want to say is why is this the closest we have come to in terms of having a dream mechanism so Tim actually proved that um this mechanism satisfies all three properties in this uncongested regime in the congestive regime things start to fall apart but you know here is where we have this dream world but this still leaves the question open right suppose we actually have finite block size so uncongested is kind of like infinite

block size and this is kind of like finite block size so the question Still Remains open if we have finite block size um can we have a dream mechanism so let me first tell you our results and then I'll go into technical details right so first we prove an impossibility result and basically the answer is no unfortunately if you have finite block size you cannot achieve an R3 properties and this seems to have a pessimistic Outlook so then you know we ask is this the end of the world and we actually introduced like a relaxed notion that can allow us to circumvent impossibility and you you'll see this later in the talk as well

so third because blockchain decentralized mechanism design is very new like there are these new elements like the burn Rule and maybe other new elements like we want to ask do these new elements introduce more expressive power and we we also kind of try to mathematically answer such questions so let's now dive into the technical part I'm going to first try to define the formal model for transaction feed mechanism and then I'll talk about our impossibility results um and then I'll talk about the relaxing ocean Okay so what's the model we have a set of users and they each have a bit so the bit reflects let's say how much I'm willing to pay for my transaction to

be confirmed and to have a transaction fee mechanism first you have to have an inclusion rule the inclusion rule decides which of these bits to pick to include in the block right so the blocks is finite you cannot include all of them and this inclusion rule is implemented by The Miner and the miner himself is a strategic player okay and second we have confirmation and payment rule so in the most General case so here I'm taking second price auction as an example and we as I said second price action is not great here but it can still serve as a good example and to show that it's not necessary necessarily the case that every included transaction

must be confirmed because in the most general form you can in this case if you want to implement a second price option and the block size is six so you include six transactions and the top five are confirmed and they pay the sixth price so it's important that this price is actually included in the blog because the blockchain needs to be able to tell you know how much balance each user has the transaction the five transactions in the block or is it just like the number five in our model it is important because like if the number five The Miner can just like Forge any number and there's no penalty essentially but if you actually force it to put in a

transaction um like in the second part of my talk I'll mention like even if you don't get confirmed right now and your transaction may get picked up in the future block and you may still have to pay pay that fee so I think it does make a difference in this sense and so this part is actually implemented by the blockchain so you can assume the confirmation Rule and payment rule is implemented honestly right so basically this looks at the Unchained State and decides who to confirm and how much each confirmed user pays so we are always going to assume if you are not confirmed you'll pay nothing right you don't have to pay okay and and finally there's a minor Revenue Rule

and this decides how much the miner is earning and we are going to impose this natural constraint to the minor Revenue should be upper bounded by the total user payment okay so but you know when the minor rule let's say it's strictly smaller than the total user payment that means there's some burning happening you can burn part part of the payment to all of the payments um okay so that's kind of the most General model and in order for me to talk about the impossibility we also have to just Define the utility but this is defined in the most natural manner so the user's utility if its transaction is confirmed is the true value minus the payment

if it transaction is not confirmed your utility is zero obviously you also pay nothing right the minus utility is just the revenue it is making okay so throughout the talk I'm going to use this as the utility functions so again the statement I want to prove is that assuming the block size is finite then no non-trivial transaction fee mechanism can satisfy both UIC and one SCP right so UIC is user incentive compatibility one SCP means and even if the minor just colludes with a single user um if you want to set it up both UIC and one SCP then you have an impossibility so notice that to get this impossibility

we don't even need mic and this just makes the impossibility stronger and we only need collusion with one user and this also makes impossibility stronger okay so this theorem works both in the deterministic case and the randomized case but for this talk I'm going to focus on the deterministic case because the proof is a little simpler for the determinant so what I'm going to do to prove this theorem is I'm going to try to kind of understand what are the requirements being imposed by UIC and what are the requirements being imposed by one SCP and I want to show that these requirements are inherently conflicting to each other so this is a very high level okay so that's why we can start by understanding the requirements imposed by UIC and this is actually well known

because UIC agrees with the classical incentive compatibility notion In classical action Theory and Roger myosin who won Nobel Prize like he has a famous dilemma called Myerson llama and this basically says that if a transaction fee mechanism is UIC then the following must be true so first the inclusion confirmation rule must be monotone what does this mean it means let's say if my bid is confirmed right now and I increase my bids and suppose the rest of the world doesn't change then I should still be confirmed and and conversely if currently I'm not confirmed and suppose the rest of the

world doesn't change and now if I lower my bids I should still be unconfirmed so this is kind of like natural notion right and and secondly once you fix the inclusion confirmation rule then the payment rule becomes unique so there is a unique payment Rule and what should the confirmed user be paying and okay so you should be paying the minimum price it could have bid and still remain confirmed so the way to think about it is let's say I'm confirmed right now and what should I be paying so you can imagine I'm lowering my bit little by little and at some point I will hit a critical transition

point if I lower some more I will suddenly become unconfirmed and that critical transition transition point is exactly the price I should be paying okay so if your mechanism satisfy you I see then this this must be true so myosin glamor has another reverse Direction but we don't need the reverse Direction so I'm not going to talk about that okay so this imposes some strong requirements on the mechanism already right and okay so we haven't used one SCP yet in order to prove this theorem and I'm going to first prove a key Lama so the key Lama says that any mechanism that is

UIC one SCP must always have zero minor Revenue the minus Revenue always has to be zero means everything has to be burned and this key lime actually holds no matter whether the block size is infinite or finite okay so we are going to prove this kilometer first and then I'll tell you how to use this key element to get the final impossibility when the block size is uh finite it's also interesting on its own because if you think about it and it kind of says in EIP 1559 the burn rule is necessary like remember 1559 Burns everything and Tim proved that when it's uncongested it's the dream mechanism it

satisfies all three properties and it this is not an accident that they burn everything right so let's prove this kilama I'm going to do a proof by contradiction right so Suppose there is a transaction feed mechanism with positive minor Revenue that satisfies both UIC and one SCP so I want to reach a contradiction so how do I do that so first you know we are assuming this mechanism has positive minor Revenue somewhere there has to exist a bit configuration under which the miners revenue is positive and let's assume that bit configuration is B1 to BN okay so now let's do a thought experiment we will start from user one and we will lower each user's bit to

zero one by one so I want to argue as you lower a user speed to zero the minor Revenue should not change so if I can prove that then it's sufficient for proving this Lemma because you know at the end of the day we just lower everyone's bit to zero and the miners revenue is the same right so when everyone's bid is zero the only possible minor revenue is zero because the minor Revenue cannot exceed the total payment so essentially I just have to show take user one as an example when I use lower user one speed to zero I want to show um minor Revenue doesn't change and that's sufficient so throughout the proof I'm going to assume the rest of

the world doesn't change okay so there are two cases I care about in case one is when I start this first user's bid is not confirmed so okay so what happens when that user laws lowers his or her bit to zero so I have to prove two directions one is that the minor Revenue should not decrease and the other is minor Revenue should not increase so let's do One Direction because the other direction is the metric so I want to prove the minor Revenue doesn't decrease um and to prove that I have to use myerson's Lemma but I also have to use this extra requirement when one SCP okay so suppose it's not the case the minor Revenue decreases by Delta when I lower this P1

to zero so what happens then then I claim um that there is a way for user one to collude with the miner and such that the Coalition can benefit from this collusion so okay one thing to observe here is that because user one is unconfirmed anyway right it's unconfirmed in the beginning and by Myers inflammar if I lower my bid I'm still unconfirmed so the user is actually just indifferent to building zero B1 or zero its utility is always one so imagine a scenario where the user's True Value is zero so my true value is zero and now I'm including with the minor what should I bid should I be 0 or

B1 and if you think about it in this case I should be B1 right because building B1 doesn't hurt me but it helps the Minor by Delta so jointly the correlation is benefiting so therefore by the requirements of one SCP we rule out the possibility that the miners utility decreases by Delta so which means miners Revenue cannot decrease in this process and similarly we can prove that the miners Revenue cannot increase and the argument here is symmetric so I'm not going to do it again so that's case one and that's kind of the easier case and case two is slightly more complicated so in case two we start in a scenario where B1 is confirmed if you bit B1 you are confirmed and now you

are lowering from B1 to zero so I also want to argue here that the minor revenue is unaffected and so to prove this is a little bit more complicated again I have to prove that the minor revenue does not decrease and it doesn't increase so I'm going to pick One Direction which is you know I want to show it doesn't decrease and the other direction is a little easier okay so to prove this I'm going to do it in three steps and first I will lower from B1 to P1 so P1 is the price I'm paying if I'm bidding B1 this is the payment price when you beat B1 and next I'm going to lower it from P1 to P1 minus an arbitrary small Epsilon so this is a critical point because in this region

I'm confirmed and when I lower from P1 to P1 minus Epsilon I suddenly become unconfirmed and then when I lower from P1 minus Epsilon to zero I'm just always unconfirmed okay so I want to show in these three regions the minor revenue is unaffected Okay so the top region it's kind of similar to the proof we have seen for case one uh I mean I can just do it again very quickly so suppose by country for the sake of contradiction that the minor revenue does decrease by Delta in this process so what will happen in this case again the user is indifferent to building either B1 or P1 because no matter what you bid you are

confirmed and you are paying P1 by Myers and glamor so if imagine a scenario where the user's True Value is actually P1 now the user is colluding with the miner what should what should the user bid should it be what B1 or P1 if it truthfully it should be P1 but actually it's better off if if it bids untruthfully which is B1 right because building B1 is helping the miner by data but I myself and I remain indifferent okay so this means the user colluding with the miner can can benefit from this Coalition and therefore it cannot be the case that the minor revenue is actually decreasing okay so the top region is easy the bottom region actually is just the same

as case one right because here the decision is unchanged I'm always unconfirmed anyway uh so what's most interesting is actually this middle region when you lower from P1 to P1 minus arbitrally small Delta what's interesting here is like I suddenly become unconfirmed and so how do we reason about this case so suppose for the sake of contradiction and the miners Revenue decreases by Delta in this region right in some sense if there is any change between B1 to zero other change must be concentrated in this tiny region imagine if the user's True Value is P1 minus Epsilon so if it bids truthfully it would be between P1 minus Epsilon but I argue that it's better off for the user to bit P1 if it's excluding with

the miner um and why is this the case so imagine if the user is building P1 in this case it will get confirmed and it will end up paying P1 but its true value is P1 minus Epsilon so this means the user's utility is minus Epsilon right it's negative Epsilon so it's hurting me a little bit by fitting higher than my True Value but it's helping the miner a lot more The Miner gets doubted more Revenue and because we can make Epsilon arbitrarily small we can make it smaller than Delta so this actually is hurting me a little bit but it's helping the miner a lot more and so together we benefit and therefore by the requirements of one SCP it it cannot be the case that the miners revenue is decreasing in this

middle region as well and similarly actually you can prove that in this middle region the minus Revenue should not increase two but here it's actually easier because we can just imagine if the user's True Value is P1 then actually it should be with P1 minus Epsilon because if it's between P1 my utility is zero I get confirmed I pay P1 my true value is P1 so I'm getting 0 out of it if I I'm putting P1 minus Epsilon I'm not confirmed I'm getting 0 out of it so I'm indifferent to to this but the miner prefers if I bit P1 minus Epsilon right so this is an easier case okay so that's the proof right we have looked at both cases and what I have shown is

if you take any user speed lawyer to lower the bit to zero the miners revenue is unaffected so you can just lower every user's bit to zero and you can conclude then that if a transaction fee mechanism is UIC and one SCP then the minor Revenue should be zero no there being like a discretized or like non-discritis real number for the bids I just noticed that like in one step you said that we are assuming it's real because I guess like here I'm making the Assumption this Epsilon is arbitrarily smart it can be made smaller than Delta so soon oh yeah sorry I think this is the step where I'm using

real number because for any Delta that's a positive number I always want to find an Epsilon smaller than Delta so if like there's a minimal currency unit let's say Delta equal to one Satoshi or one way then you may not be able to find Epsilon smaller than Delta good said something else I think the Myers and how it applied but it oh yeah that's right Mars number assumes it's real as well there's a unique minimum payment that was the smallest like the smallest one um yeah that's assuming it's it's real like

Mars and lemon like you just lower Laura until you hit the critical point where you suddenly become unconfirmed um I actually I don't know what if there's a discrete version for Marathon maybe but that's actually an interesting question because my student and I we actually at some point we were discussing what what's the implication if it's discrete and and yeah I'm just saying like for in general can is this yeah I guess we were one you somehow intuitively if it's discreet

maybe it's like similar to like Epsilon IC or something because like this this one I I we didn't understand it like we were discussing it but uh maybe it kind of dropped at some point but this is an interesting question yeah so okay so this is the key llama we have proven and we just have to get from this key level llama to the final theorem and so so far we haven't used finite block size yeah this key lime holds no matter what the block size is so to prove the final theorem we are going to throw in the finite block size assumption so you know the skillama imposes a very strong requirement on the structure of the mechanism and now let's look at what

happens when the block size is also has to be finite so again proof by contradiction suppose that there is a non-trivial transaction fee mechanism that satisfies both UIC and one SCP and moreover it works for finite block size okay so what contradiction can we reach um so because the transaction fee mechanism is non-trivial right and there must be a bit vector and under this bit configuration some bit is confirmed so let's say BJ is confirmed so now imagine a different world now the world consists of B1 to BN but also with many other bits who are bidding BJ plus Epsilon but there are so many of these bits such

that the total number is bigger than the block size so you cannot possibly fit all of them in the block size which means if the world is like this then some person from here must be unlucky and not included so let's call that unlucky person you because you is one of these players between PJ plus Epsilon okay so now I argue actually sorry I argue this unlucky person you is better off you know if it colludes with the minor and the Coalition can gain right because the minor is just indifferent right remember because of the key lime at the minor revenue is always zero so the miner doesn't care so now let's see the if the miner can help this user you okay you will collude with the miner and it

will pit BJ instead of BJ plus Epsilon right so this is under bidding and the miner will pretend that the world contains B1 to BN and it will replace BJ with this user use bit so now it runs on its mechanism on on the speed configuration and in this case actually you will be confirmed right because that's our assumption so now the user U is getting Epsilon value out of it and again the miner is indifferent because minor revenue is always zero so therefore we we reach the impossibility so that's the proof and in our paper we also extend the proof to randomized transaction fee mechanisms but the proof is more technical so I won't go into details in this talk you can read the

paper if you are interested and then for the rest of the talk I just want to spend some time discussing something more philosophical like I want to talk about you know how do we interpret this impossibility is this like the end of the world and so I'll talk about some relaxed notion like I don't know if this is the final answer we want but I think it's like a meaningful first step and okay so one observation we had is like in the previous modeling if you cheat then so let's say you inject a fake transaction are you a bit higher than your true value and and because we are we're focusing on a single instance of the auction we're not looking at the future so if your

transaction currently is not confirmed you are paying nothing and therefore your cost of cheating is zero so this is what the previous model assume but actually if you think about it if you inject a fake transaction or you feel overbid and you are not confirmed in the present block that that doesn't mean our transaction will disappear like it's posted onto the public network right so it can't be picked up later by a future block and it'll make a confirmed in this future block so you may end up having to pay something in the future by making this event yes so uh well sometimes like let's say if you

have some transaction in the block that sets the price The Miner cannot withhold it like it cannot oh I'm only going to review it if it helps me like you actually have to put it in the blog and that that transaction is there to to set the price and that decides how much the miner gets well yes but that Trend that's um over that transaction may may be revealed but that transaction is not everything included in the block is confirmed right so like in the in the second price option example like you include um a bunch of transactions and the last one is not confirmed the last one is just there to set the price and so it could be like one of these

like you actually have to disclose it and to gain in the present but by disclosing it you may lose something in the future yes the transaction automatically get confirmed in the next block or like someone actually has to like you have to yeah so we are actually not the first one to suggest this I think there was some paper by Aviv Zohar and others they also use this and so so it's not a new technique actually um I I don't know that it has any mechanism works like this in in real world

but I think in the academic Community it has been considered for a pretty long time um but you'll also see actually after I introduced this notion like for the even for this weaker notion I can show um I prove I can prove that it is critical to allow unconfirmed transaction in the block to have any possibility if you don't have this then it's still impossible so the current modeling fails to capture this cost and now the question is okay obviously if if we somehow account for this cost maybe we can still convert this impossibility right um but actually doing this is pretty hard because it's very hard for me to characterize how much you end up paying in the future because this depends on the environment it depends on what other

people are building it also depends on the mechanism itself so what do we do there like we don't just want to give up because it's hard to characterize the cost so we start asking ourselves okay first what is the worst case cost that can happen to you if you are the offender what is the worst cause the worst case cost you can incur and should you inject a fake transaction or overbid so the worst case cost is when I end up paying the four bits sometime in the future and the cost in that case would be the bid minus My True Value right so if it's over Bill transaction it's bit minus True Value if it's a fake transaction the true value is zero so the cost is um just the bid itself so I mean of course in practice you may

not be so unlucky like you may not be incurring the worst case cost because you know it also depends on what the mechanism is it depends on what other people are building uh okay so in our model we actually allow some parameter let's say I have some kind of discount Factor gamma and you you can also view like gamma as the resident resilience knob um okay so imagine I will end up in expectation paying gamma times this worst case cost so gamma is between zero and one and you can see if gamma is equal to one then this is the same as the worst case if gamma is equal to zero it's the old model where you have no cost for this so when when gamma is equal to zero you

should still suffer from the previous impossibility so in practice I guess one question this is called the discount factor in practice you know it may not be clear how to set the gamma like you can potentially look at the history use history to figure out exactly you know how how gamma might be what range it might be but you can also think of it as a knob like if you you can always set it to be one but maybe you end up with somewhat more um you can always set it to be zero zero is like um no cost so it's the best case for the offender and the worst case for the mechanism design designer if it's one it's like the most relaxed notion in most relaxed incentive compatibility in notion because it's like the worst case

for the offender the best best case for the mechanism designer uh so it's kind of like a knob and that lets you tune the resilience of the mechanism okay so under this model we actually have some feasibility result uh we call it the burning second price auction and I will talk about a special case in this talk and I'll hint with the more General case is so the special case is when gamma equal to one essentially you're incurring the worst case cost and let's say we just we want to defend against collusion with one only a single user okay so in this case here's one mechanism that works it's kind of cute I guess

so what happens here suppose our block size is six so we include the top six transactions in the block but not all of them are confirmed only the first three are confirmed and these confirmed transactions are paid in the fourth price so from the user's perspective it's a second price auction right so that's why it's UIC so now the question is what is the minor earning so so all of these people they're included but not confirmed so they don't have to pay anything so the miner is not getting the full payment it's only getting eight plus six plus five and this part of the revenue is coming out of this uses payment just don't be confused then the rest of the payment is is just burnt

ones yeah they are pay eight uh so yeah so yeah they pay totally for the miner gets uh yeah 19. so five is burned yeah so intuitively why does this work I can give you a quick intuition this is not a formal proof so imagine uh Matt excluding with the miner and uh Matt wants to over bid so it's raising Matt is raising the bit from eight to nine right because this makes the miner earn one more like the miner is making

the sum of these numbers however this this action is not cost free for math in the worst case right because we're assuming gamma equal to one in the worst case math may end up paying nine in the future so it will cost a mat one and then now the plus and the minus they cancel out so the correlation is just basically indifferent in the sense okay so this is another formal proof if you want to do a formal proof you have to analyze our cases and that's what we do in the papers I'm not going to do that here okay so this is coming back to Andrew's question like should we allow the blocks to contain unconfirmed transactions I guess there's a debate and yes yes

and so so let's first fix c equal to one and just imagine gamma is um 0.5 so in this case The Miner would be getting 0.5 times the revenue in this this auction and um you you would be selecting um gamma time so so this is okay let's call this parameter K they are confirming the first K and then the next K Prime are used to set the the minor Revenue so so in this case you just randomly sample actually gamma fraction of the top K and those

well it's yeah you're sampling K times gamma users to be confirmed from the first k so this is what happens when you change comma but C is still equal to one but now if C is not equal to one then you are actually sampling gamma times K Over C at random to to confirm ative okay yeah yeah so you need to know what resilience you aim to achieve and then depending on the resilience you want to achieve you can choose the mechanism I'm still like I see for gamma equals 0.5 to 1

to 100 gamma the smaller the gamma the more the stronger the notion right so you are right if it's 0.5 then it implies it's like you know between 5.5 is strictly better than one yes Matt um just by including the term just by submitting a transaction with a p of eight I may lose eight and the point is that you know the mechanism you described by which I might lose a would be it's really a fake bid but my transaction is confirmed later

I'm gonna have to pay for this thing I didn't even want in the first place I have it but like if that's a genuine you know like if I really have value for something then is what you're saying that's sort of like I should really I don't know that like gamma is real gamma equals one is really describing sort of like this very special case that you're really talking about paint bids um not not really actually uh I guess uh if let's say it's over a bit transaction then the cost is the bit minus the True Value so right like like I cannot survive there

if your true value is eight and you bit bit nine you haven't in the worst case you have negative one utility because in the worst case you end up paying nine and you pay nine and suppose your true value is eight your user is negative one yeah that's the worst thing okay you can't confirm it uh okay I can't confirm it now because if you confirm it now then so like the worst thing that can happen is that somehow later there's some kind

of like um auction I wind up paying my bid and that's why I understand yeah I mean if it's confirmed now the cost is already accounted for like we're just fixing this part like if you are unconfirmed the previous model doesn't account for any cost yeah yeah change a good trade going on and everyone is trying to do a trade but it's only valuable now if they get unlucky in it for unconfirmed

yeah I guess this this is because like at least in some cryptocurrencies like Bitcoin once you post the transaction you cannot retract it I mean it's like everyone can see it then the miner later can always just take it and confirm it like it's not like I can tell people oh I don't want this transaction right so so also like for the special case like when gamma equal to one where the its worst case cost you can also think of the notion as like I want to defend the defend against paranoid players like paranoid players they only want to deviate if they can surely win um but I mean in practice you don't have to have a like really accurate estimate of gamma because this is kind of like you can view it as a

knob so it doesn't have to be oh you know I have to set it precisely experiment I should really go through is once I post this transaction with a fee of nine at some point in the future I may be included uh-huh if I'm using this option I maybe have some prior over what the expected price I wind up paying when I'm included in a block is that kind of like brand on yeah that's right yeah that's right also like back to Tim's question like for instance uh in this mechanism I mentioned like let's say when gamma is not equal to one like

you're you're sampling gamma fraction of the top key users to confirm so if gamma is equal to zero you're just sampling zero users so this agrees with the previous impossibility result because the mechanism just degenerates to something trivial when gamma is equal to one is equal to zero so so this is Andrew's question like should we allow the blocks to confirm unconfirmed contain unconfirmed transactions and so there's a debate and I remember at EC last year there was a debate in Tim's poster session and this is how I learned about this question Matt was also there I think Matt raised this question like do you have do you have to allow unconfirmed transactions in the block even with this new utility function it's weaker

incentive compatibility notion we show that if you do not allow unconfirmed transactions in the Block it's still impossible so I won't go into the proof but um at least in this case it matters okay so as I said in the paper we generalized this to General choices of gamma and c so what's interesting also as I mentioned earlier right uh I'm randomly sampling a subset of the top K users to confirm it's like gamma times K Over C users so which means like except for this case like in this special case it's deterministic because I'm just selecting the top K but any other case when gamma is not equal to 1 or C is not

equal to one it actually becomes randomized the mechanism so one question we ask is like is this randomization necessary and it turns out that indeed it is necessary like if you want the transaction fee mechanism to satisfy to to be kind of useful like unless you consider really degenerate ones where only one user is confirmed or something then the random kinds are actually necessary so this lower bound is quite sophisticated to prove um so I won't go into the details here okay just to summarize so I find the space technically fascinating and partly because like you know the vast majority of classical mechanisms just fail in the decentralized environment so I guess our work takes a step forward in

understanding transaction fee mechanism but I don't think this is close like I think it's basically widely open space and lots of exciting open questions our paper contains detail proofs and and again there are so many exciting questions like for instance how can we model this repeated nature in this transaction fee transaction fee action right now we are considering he's still a single instance and how can we model the long-scale strategies can we consider other relaxed Notions of incentive compatibility to circumvent the lower bound how can crypto help okay and before I end I also want to advertise one new work and it's called Ponyta and in this work we try to design

a side contract resilient Fair exchange protocol so fair exchange is used everywhere like in atomic swaps in payment channel in contingent payment in D5 so and so forth and other previous designs like they they consider only Alice and Bob as the players and the miner is not a player so the miner is assumed to be honest so we basically you know start asking and this is actually one question the community really cares about because of Mev minor extractable value so what happens if the miner is also a player like in particular The Miner can include with one of the users so we design new protocols that provides resilience and in this world with possible side contracts between Miner and user and what's most cool about our work is the name ponita so Ponyta is a

fire type Pokemon and in our mechanism we sometimes like if you behave dishonestly sometimes your collateral can get burnt so this is a way to incentivize you to behave honestly so Ponyta is a fire type Pokemon and it has special power it can control its flame so it can protect its Rider from getting burned so because our contract is incentive compatible it will protect the player's collateral everyone will be incentivized to behave honestly and they will protect the player's collateral from being burned thank you [Applause] like that

and the question how crypto can help yeah actually this is something we are we are thinking about right now and what's interesting is like I think about 20 years ago there's a line of work that tries to connect crypto and Game Theory but I guess these were kind of more theoretical nature like the modeling is not a great match for today's blockchain type scenarios so I think in general it's this is this is a good time to rethink about this question like how can we this question came from Andrew actually so Andrew uh when when we were working together we

had discussion about like doing Lottery like leader election protocols on blockchain and like all of these earlier protocols they require people to put in collateral and actually like I think the earliest people actually won the Oakland best paper award like in 2014 and then then it spawned like a line of work that you try to reduce the collateral and then Andrew and Edo benthof observed that okay there's this classical tournament tree protocol you can do this without any collateral at all and so we actually had some after that we had some new results like we proved some lower bound and you know like log and rounds is necessary in some model and then we prove like if you are willing to relax the security notion to Epsilon incentive compatibility you can like you know be

like beat the log and lower band maybe you have login log log rounds or maybe even lock star runs in some setting so so I have a paper actually in the upcoming crypto in August I mean that was also like did I have like a sequence of papers on this topic like there are also different variations of the problem that is the leader election and there's also like coin toss in general so this is another I think in general like for instance the question of how do you design these incentive compatible protocols like with small collateral minimize collateral is like in general very interesting question and there are often times you have to use crypto to help um and I think this is a good example

where crypto actually helps because if you don't have crypto there's a lot of impossibility results are I mean is there an assumption are you what part of where this comes from is that I think of the finite block size is you know a model approximation the reality is that the computers on the network have limited resources and Broadcasting checking them this time it's like if you've already included that transaction in the block even if you're calling it not confirmed it's already been relayed so that

doesn't cost later it's already been validated so that doesn't cost later so maybe I guess if you're asking like one trivial thing you can do is later when you actually confirm it you can just start pointing to the previous occurrence on the blockchain right so that can minimize the states sure to would it cost you less to then get that transaction confirmed later because then it's like you've made some progress like my transaction didn't get confirmed in this block but then I would get a cited benefit that later on when I go to get it confirmed for real you've already done all this work so I guess you are asking should we design mechanism that makes it cheaper if it's

already there to confirm it that I don't know I think like that's a very good question because like we we don't have anything to reason about this this repeated nature yet is that it really is necessary to waste a resource and like you can't give the user a benefit that was spoil the incentives so you have to make them go through the whole process of relaying the entire transaction again from scratch and do everything that would then even cost the whole network of this extra redundancy and maybe that isn't here but I guess like if it's already on the chain and not confirmed like the user doesn't have to broadcast it right you can just assume anything on the chain unconfirmed it's already in the mempool like that that you can assumption you can easily make but the

question is like in the mechanism design yeah in the mechanism design should you make the payment law for that user that I don't know that I think is like maybe we'll need to consider the repeated nature and consider longer scale strategies and I think it's related but it's different like is are these results sensitive to all transactions being the same size yes yes oh yeah that's that's what you were asking earlier yes we do assume they have the same size so we this doesn't actually apply to the gas model of ethereum so that's a also very

interesting I got the lower band okay so maybe I should put the lower bound holds for ethereum too for the Africa the law of when we have a lot about when they are the same size right so the lower bound holds but upper boundaries okay great sounds good thank you