Latest / Strachey Lectures / Strachey Lecture: The Computer in the Sky

Transcript

Strachey Lecture: The Computer in the Sky · Strachey Lectures

• 0:15
  Well, this demonstrates that your services are about to turn to the second set by the distinguished lecturer named after Christopher Scrunchie,
• 0:23
  research students. Um, before I tell you what, we think our sponsor is Oxford Asset Management.
• 0:27
  They've been funding this series since 2015.
• 0:31
  And so thanks to their generosity, we've got to bring people together.
• 0:36
  And also, if any students are interested in talking to company afterwards, I think very often don't do that.
• 0:45
  Before I introduce speaker, I just want to say that afterwards there's going to be some, um, microphones for asking questions.
• 0:52
  So just raise your hand. And I think as if you were asking questions about here.
• 0:58
  Probably. Um, yeah. Let's just leave out these.
• 1:02
  Okay. So I'm an enormous. Um, thank you for listening.
• 1:07
  Jim is a professor at Columbia, professor of computer science.
• 1:11
  I was building something very prominent on the world stage, uh, ever since he was a PhD student, which is quite rare.
• 1:18
  Yeah. Uh, so he's interested in lots of different areas.
• 1:23
  The connections between, uh, computer science and genomics, all aspects of algorithms.
• 1:30
  And then coming back today, which is his recent works on blockchain.
• 1:34
  I selected a few of the works. Just, um, some of them.
• 1:39
  So Jeff is the recipient of, um, ACM Grace Murphy Corporate Award in 2009 for his work on Social Security.
• 1:48
  In 2012, he got a third prize. Uh, actually, um, also with UBS, um, for work on research that limit selfish internet use.
• 1:59
  He's the winner of the Social Choice and Welfare Prizes in 2014,
• 2:04
  which is 200 outstanding accomplishments in social choice, theory of love or economics.
• 2:09
  He's the recipient of the Kalai Prize in Game Computer Science in 2016 for his paper Intrinsic Robustness in the Price of Energy.
• 2:17
  He received a The Nine Fellowship in 2017 and ACM Awards 2017.
• 2:23
  Um, that's actually a pretty small selection, a much longer list.
• 2:27
  Um, you know, a lot of just, uh, talks, including, um, being in fact,
• 2:32
  most of the international conference competitions, but just, um, quite cutting edge.
• 2:36
  Here's the shock lecture world. No question. Thank society.
• 2:40
  Um, not so many people, probably many prepared for the many books that he's written.
• 2:45
  And, um, lectures, 30 minutes, I'm not sure.
• 2:49
  Especially a lot of the younger people here, though. Uh, present.
• 2:54
  So stock rooms that accompany the whole algorithm series.
• 2:58
  20 Lectures on Algorithmic Game theory. Um, beyond endorsements, analysis of algorithms to learn.
• 3:04
  We're really competition today. Um, so if you want to come and do that.
• 3:09
  Um, today's topics have been the double, um, blockchain. I mean, it's called the computer in the sky.
• 3:14
  So. Thank you. All right.
• 3:24
  Thank you, Professor Goldberg. Thanks, everybody, for coming out. Uh, great honour to be given today's stretchy lecture.
• 3:29
  When I got the invitation, I looked at the list of some of the previous speakers and had a fair number of heroes on that list.
• 3:34
  Really? I'm very grateful to be here. Particularly cool, actually, to have Professor Goldberg, uh, do the introduction, because now,
• 3:41
  almost 25 years ago, she was one of my earliest ever supporters as a graduate student.
• 3:45
  I was totally unknown. She was so nice to me, so supportive about my early work.
• 3:49
  I've never forgotten it. So, um, really happy to be here.
• 3:55
  So what I want to talk about today is a hard computer science problem.
• 3:59
  Okay. So I want to talk about some computing functionality I think would be really cool to have.
• 4:04
  And I want to explore some of the scientific and engineering challenges that come up when you try to actually realise that functionality.
• 4:09
  For an analogy you could imagine, like 60 years ago,
• 4:13
  having a vision of a technology that enabled any two people on the globe to communicate digitally pretty much instantaneously.
• 4:20
  And you can view today's internet as some kind of approximate realisation of that functionality.
• 4:25
  And if we think of the internet as kind of a neutral infrastructure for communication, you're neutral.
• 4:30
  I just mean there's no one sort of individual or company or nation state that controls the internet.
• 4:35
  In some sense I want the analogue of that for computation.
• 4:38
  Okay. So a neutral infrastructure for general purpose computation.
• 4:42
  So the functionality I'm interested in is that of a computer.
• 4:48
  General purpose. It's going to be a computer that, you know, has its own operating system, its own processor, uh, its own storage.
• 4:55
  Um, but unlike, you know, a typical computer which has is owned by an individual or a corporation,
• 5:00
  there's someone that has root access to that computer. I want a computer with none of those properties.
• 5:05
  No owner, no operator. In some sense, it just runs, if you will, in the sky, where we can all view its computations.
• 5:12
  And it just sort of runs there on its own as a public good. I want us to have very high confidence in its computations.
• 5:20
  It'll carry out the intended computations correctly and for a very long period of time.
• 5:24
  Uh, no one should be able to shut the computer down or otherwise tamper with it.
• 5:28
  And I want it to be open access in the sense that anybody can use it and hereby use it.
• 5:32
  I mean, maybe you interact with software that's already, uh, installed on that program on that computer.
• 5:38
  Maybe you install your own programs yourself, uh, for others to use.
• 5:42
  So this is the this is the functionality I'm interested in building out.
• 5:46
  Okay. So almost all of the talks are just going to be about some of the challenges that come up in trying to realise that.
• 5:52
  Another obvious question would be like, suppose you could build it, what would you do?
• 5:56
  And this is something I'm happy to talk about at great length after the talk, but it's not going to be the focus of the talk except on this one slot.
• 6:03
  There's a bunch of different ways I could answer this question. Um, let me give you one answer that I think is really kind of, um,
• 6:09
  under discussed in popular discourse around this technology and the sort of one thing I want you to
• 6:14
  remember from today's talk is that blockchain protocols in the applications built on top of them,
• 6:19
  it's not fundamentally about cryptocurrencies or about prices or about finance.
• 6:24
  It's really a technology that's about something, in my opinion, much more profound,
• 6:27
  which is stronger notions of ownership of property rights than we've traditionally had for things we might buy or creates in the digital realm.
• 6:35
  So let me sort of unpack that a little bit. The story starts with a gift given to us now almost 50 years ago by public key cryptography.
• 6:44
  And specifically, I want to focus on secure digital signature schemes.
• 6:48
  Uh, because I claimed if you look at the cryptographic guarantees offered by digital signatures,
• 6:53
  there's kind of a loose analogy to the types of property rights that we're accustomed to for physical items, right?
• 6:59
  Like think about real estate, for example.
• 7:00
  Like imagine you buy a house or you get various property rights along with that, you get the, uh, right to use, okay.
• 7:06
  So you can live in your house if you want. No one can stop you.
• 7:10
  Uh, and that's a little bit like how sort of digital signatures no one can, if you're the owner of a public key.
• 7:15
  Should have said that at the outset. I want to think about cryptography.
• 7:19
  Is letting you own a 512 bit string okay. Representing a public key or by own, I mean, you mean you own, you know, the corresponding private key.
• 7:27
  So analogous to the right to use. Right. No one can stop you from producing valid digital signatures because you know the corresponding private key.
• 7:36
  Another property, right you might have is the right to exclude. So no one else can live in your house unless you unless you want them to.
• 7:42
  And so there there's a loose analogy with digital signatures.
• 7:45
  No one can forge signatures on your behalf because they're not the owner of that public key.
• 7:49
  They do not know the corresponding private key.
• 7:52
  Okay, so I claim we can think of digital signatures as allowing individuals to own, in a meaningful sense.
• 7:58
  Public keys. Bits of five of length 512. Let's go back to that computer in the sky.
• 8:04
  Capable of general purpose computation, certainly capable of verifying digital signatures.
• 8:10
  And now a sort of, frankly kind of trivial idea, actually,
• 8:13
  is to extend the notion of ownership of 512 bit strings that we already have to ownership
• 8:19
  in the same sense of arbitrary digital data that lives on this computer in the sky.
• 8:24
  Right. The idea conceptually, is trivial, a program running on that computer.
• 8:28
  Maybe it's the computer's native operating system. Maybe it's a user installed program.
• 8:32
  Running in that operating system just can create a pair, okay, data X coupled with a public PPK.
• 8:39
  And we can now just define ownership of arbitrary digital data X as inheritance as inherited from the associated public key.
• 8:46
  In other words,
• 8:47
  you would own X if you're capable of producing a digital signature that witnesses your knowledge of the course of the private key corresponding to PK.
• 8:56
  Okay, so I claim if you combine cryptography with the computer in the sky, you get a notion of user owned data, uh, up there in this sense.
• 9:04
  Now what is that good for. And again, happy to talk about this a great length afterwards.
• 9:08
  But you know, the upshot is it's interesting to own data on this computer in this sense.
• 9:13
  If it allows you to do something you could not otherwise do, perhaps on the computer in the sky,
• 9:19
  interacting with other programs on it, it lets you do something you couldn't otherwise do.
• 9:24
  Maybe you can exchange your ownership of some data X for ownership of some other data Y that you're curious about.
• 9:31
  Or maybe it lets you do something you couldn't otherwise do in the physical world, right?
• 9:36
  A simple example would just be representing sort of one of a limited number of membership cards that, I don't know, get you in the cool parties.
• 9:42
  That allows you to have a special communication channel, sort of with some musician for their superfans, whatever.
• 9:48
  The point I want to make is that once you have the right mental model for what this technology is trying to achieve,
• 9:53
  it is not very hard to brainstorm lots of different things you might do with it.
• 9:56
  And again, I'm happy to talk more about that in the Q&A. Okay.
• 10:01
  So moving on to some of the engineering challenges. I've optimised the talk for breadth over depth.
• 10:08
  So we're going to talk about three different, quite different, uh, threads in my recent research over the past few years.
• 10:13
  Because of because of all of them, I'll have to, you know, just touch each one, um, pretty lightly.
• 10:18
  Uh, two themes I want you to look at, I want you to look out for as we go through them.
• 10:23
  First of all, how amazingly interdisciplinary it is to work in this application domain.
• 10:28
  And I say, someone you know, I say that as someone who's almost his entire career has done interdisciplinary work.
• 10:33
  This is a totally different level I've never seen before, even the different parts of computer science that this technology touches on.
• 10:38
  There areas that historically had basically nothing to do with each other.
• 10:41
  The areas of economics that it touches historically have had nothing to do with each other.
• 10:45
  And there's other disciplines as well that you're not you're not going to see today.
• 10:49
  The second theme I want you to look out for is just the incredibly rapid pipeline from just purely theoretical work to practical impact,
• 10:57
  which is probably as short as I've ever seen in my career. It's been actually kind of wild working in this area for the last few years.
• 11:04
  So I'll tell you a couple of anecdotes about that as we go along. Okay.
• 11:09
  All right, so the first thing I want to talk about, I want to zoom in on the desired functionality of being open access,
• 11:14
  the idea that anyone can, can use, uh, this computer in the sky.
• 11:19
  And in particular, I want to ask, how do we make that economically sustainable?
• 11:22
  Okay. So demand for processing on that computer exceeds the supply.
• 11:26
  What do we do? That brings us to the idea of a transaction fee mechanism.
• 11:30
  Okay. So that's what we're going to study in this in this first part.
• 11:33
  So you really don't need to know much about sort of how blockchain protocols work.
• 11:37
  Um, for now, like fundamentally, what's the responsibility of such a protocol?
• 11:42
  It needs to maintain a running sequence of transactions.
• 11:46
  Again, I want you to think of this as a general purpose computer. So I want you to think of a transaction as a little snippet of code.
• 11:52
  Let's say Assembly language code. Low level code. A sequence of transactions is then just sort of a long sequence of assembly line assembly
• 11:59
  language instructions that are carried out in this computer in this virtual machine.
• 12:04
  Okay. So transactions get added to this running log in batches, which are known as blocks.
• 12:10
  And all that matters for us right now is that blocks are only produced every so often.
• 12:15
  And they're only so big. I'm going to use the Ethereum blockchain protocol as a running example.
• 12:20
  It will become obvious why I'm doing that later. In Ethereum you get a new block, a new batch every 12 seconds.
• 12:25
  A typical block might have something like 200 transactions in it.
• 12:29
  Okay. And if you're doing the math in your head and you're saying that's only like 16 transactions per second, that doesn't sound like it's very much.
• 12:34
  That's because it's not very much. Okay. At least for the Ethereum protocol.
• 12:38
  Yes, it's a computer, but it's a very slow computer. Okay.
• 12:42
  And so for the most popular blockchain protocols, certainly including Ethereum and Bitcoin, uh, the demand is much higher than the supply.
• 12:50
  Many more than 16 transactions per second would be like, would like to be executed in the virtual machine that the Ethereum protocol maintains.
• 12:59
  And so the job of a transaction fee mechanism then is to decide which transactions get in and which transactions don't.
• 13:06
  And in particular, the ones that get in, what price do they have to pay.
• 13:10
  So that's the job of a transaction fee mechanism. What would such a mechanism look like?
• 13:14
  Potentially. Let me tell you about the one that's been in operation, Bitcoin, for its entire 15 years of existence.
• 13:21
  It's also the one that was used in Ethereum until about two and a half years ago, called the first price auction.
• 13:26
  Uh, very simple, very natural. So if we take seriously this idea of this sort of computer in the sky as a public good,
• 13:33
  if it can't execute everything well, we should sort of allocate it fully and on the most valuable transactions.
• 13:40
  Okay. How is this computer supposed to know which transactions are valuable and which ones aren't?
• 13:44
  You ask users to bid. Okay, so a user of a blockchain protocol would submit, along with the transaction, an amount that they would willing to pay.
• 13:52
  Should that transaction be included for execution.
• 13:56
  Okay. So then the way a lot of blockchain protocols work,
• 13:59
  there's sort of a unilateral sort of one actor that's chosen, you know, usually by winning a lottery.
• 14:04
  One actor is chosen to put together one of these blocks of, say, 200 transactions.
• 14:09
  And when they do that, all 200 users that hand their transactions included their bids get transferred to the to the block producer.
• 14:15
  Okay. So users submit transactions that they want to see executed.
• 14:18
  They say how much they're willing to pay,
• 14:20
  and that gets paid to the block producer that chooses their transaction instead of others to include in the block.
• 14:26
  Okay, so what do I mean by a first price auction? And you know, this is worked reasonably well.
• 14:31
  Like I said, Bitcoin's used it for 15 years. Ethereum use it for many years.
• 14:34
  Uh, if you've studied any auction theory at all, like if you've ever heard of a Vickrey auction or a second price auction,
• 14:39
  one thing you know about first price auctions is that it's non-trivial to figure out how to bid.
• 14:44
  If I ask you to pay exactly the amount that you say you're willing to pay.
• 14:48
  You're never going to bid your maximum willingness to pay your indifference point.
• 14:52
  Okay. You're going to shade your bid. You can say, well, I'd be indifferent at not at $10.
• 14:57
  Maybe I'll bid $9. Or maybe I'll bet $8.
• 15:01
  Or you have to sort of think about how stiff the competition is.
• 15:04
  The stiffer the competition, the less you can get away with shaving your bit.
• 15:07
  So that's some difficulty in bidding on a first price auction.
• 15:10
  We've known that for decades, and being in the blockchain setting doesn't make it any easier.
• 15:16
  Like I said, if you studied a little action theory, you're aware that there are other formats.
• 15:20
  If you just change, for example, from a first price auction to a second price auction,
• 15:23
  all of a sudden you have this magical truthfulness property, which is you just you should just be honest.
• 15:27
  You should just tell the auction, you know what? This is my indifference point. This is the most I'd ever be willing to pay for this item.
• 15:33
  And then basically, the second price auction promises to underbid for you on, on, on your behalf, given what everyone else bids.
• 15:40
  And for that reason, you can sort of just delegate the under bidding process to the mechanism and you'll never regret it.
• 15:45
  That's what I mean by truthful auction. So you can ask the question with transaction fee mechanisms.
• 15:50
  Could we have a better transaction fee mechanism, one in which it's easier for users to figure out what they should bid,
• 15:55
  and in particular, why not just use something like a second price auction?
• 15:59
  Yeah. So this is the question I want to understand in this first part of the talk.
• 16:04
  And I hope this feels like a reasonably fundamental question, right?
• 16:08
  A popular blockchain protocol. Some stuff gets in, some stuff gets out.
• 16:11
  You have to make those decisions. You have to figure out pricing should seem like a basic problem, I hope.
• 16:16
  Uh, at the time I did this work, which was mostly in 2020, it was also a very timely question specifically for the Ethereum blockchain protocol,
• 16:25
  which then and now is the second biggest blockchain after after Bitcoin, uh, in 2020, the Ethereum community,
• 16:32
  um, was assessing a potential switch of its transaction fee mechanism from the first price auction.
• 16:38
  I just showed you to a very different one, which I'll show you in a couple slides called EIP 1559.
• 16:44
  And it made many big changes. Some people in the Ethereum community thought it was a really cool idea.
• 16:50
  Some people hated it. Some people just a lot of people just didn't understand it.
• 16:54
  So we're sort of scared of it.
• 16:56
  And the Ethereum community prides itself on just kind of having a strong sort of social consensus to sort of in the spirit of open source software.
• 17:03
  So whenever they have kind of a polarising issue, like should they switch the transaction fee mechanism or not,
• 17:08
  they try to come to some kind of rough consensus among the stakeholders.
• 17:12
  So this was a community outreach survey. So Tim Baker is sort of a major figure in the Ethereum community.
• 17:17
  Uh, and this was again in 2020. And so he sent out this survey to various stakeholders.
• 17:22
  Right. So, uh, sent it to various miners. This was back in the proof of work days of Ethereum.
• 17:26
  Send it to people who run exchanges, send it to people who build wallets, software.
• 17:29
  Right. Which sort of prepare bids with transactions and asked all of these stakeholders, you know,
• 17:34
  how do you feel about maybe switching the transaction fee mechanism over to in 1559?
• 17:39
  And if you're nervous or unhappy about it, what can we as a community do to make you feel more comfortable with that switch?
• 17:46
  Okay. And many things were mentioned on the survey, but what I want to highlight here was the issue of a lack of a formal specification
• 17:53
  or proof for the mechanism that people can independently evaluate and critique.
• 17:59
  Now, mind you, like none of the respondents, not not a single responding to the survey is someone who writes research papers, right?
• 18:05
  These are all people building stuff in the Ethereum trenches.
• 18:09
  But there is a very obvious hunger from this group for the kind of work that my community does in algorithmic game theory,
• 18:16
  or that you can't community the rigorous assessment of the incentive properties of, uh, of an auction of a mechanism.
• 18:22
  So that, no doubt, was sort of a major motivator for me to spend several months of my life in 2020, uh, doing this work.
• 18:28
  Okay. All right.
• 18:34
  So what I want to talk about next is like, why is this even a hard problem? Right?
• 18:37
  Like, why can't you just, you know, look at a textbook,
• 18:40
  my textbook or some other mechanisms on textbook and copy paste some cool mechanism like the Vickrey auction or the VCG mechanism?
• 18:46
  If you know about that, why can't you just copy paste that into a blockchain protocol and call it a day and you're like, you're done.
• 18:51
  You get this nice truthful mechanism. And the reason and this will be a theme through all of these sort of three parts of the talk.
• 18:58
  Is that a problem that feels like a, well, sell problem actually needs to be revisited from first principles because of the
• 19:03
  idiosyncratic constraints imposed on you by the permissionless nature of blockchain systems.
• 19:09
  Okay, we're going to see that here. I'm going to see it again in the other two parts of the talk. So in this on this slide,
• 19:14
  I want to walk through what are some of those weird challenges that don't come up in traditional mechanism design applications,
• 19:20
  which is going to motivate a couple of new types of incentive constraints that we're going to want a mechanism to satisfy.
• 19:27
  Okay, so I started with something I'm calling challenge zero because this challenge has it's,
• 19:31
  you know, it's non-trivial but has nothing to do with blockchains per se. It's just always about mechanism design and mechanism design.
• 19:37
  What are you doing? You're eliciting preferences from the participants so that you can make a good decision in some sense.
• 19:43
  And whenever you deploy a mechanism, you are always worried about the participants misrepresenting their preferences
• 19:49
  in order to for the mechanism to compute an outcome which is better for them.
• 19:53
  Okay, already, like in a first place auction under bidding is in some sense misrepresenting your preferences.
• 19:58
  So there's standard language and mechanism designed to say that you want a mechanism which is not gambol in the sense you might call it truthful,
• 20:05
  or also sometimes called a technically that's dominant strategy, incentive compatible.
• 20:09
  But don't worry about it. That just means like a second price option.
• 20:12
  You may as well just report your true value. Okay, so that's challenge zero.
• 20:16
  That's exactly what a first price option does not have. Okay.
• 20:19
  So we would like a mechanism which does have this property. But.
• 20:23
  What else? Something that's much different.
• 20:26
  The traditional mechanism design allocations is if you think about who it is, who's carrying out the mechanism.
• 20:31
  Right. If you're selling kind of like wireless licenses, you know,
• 20:35
  it's kind of like the national government, government that's sort of running the mechanism.
• 20:38
  And you genuinely kind of trust that they're going to run the mechanism that they promised they were going to run, more or less.
• 20:44
  Now, in the blockchain protocol, in the blockchain context, I mentioned that a block is assembled by one actor chosen at random using a lottery.
• 20:52
  Okay. And they can choose whatever 200 transactions they want.
• 20:56
  They can include anybody they want. They can exclude anybody they want. They can even actually inject their own shill transactions if they want.
• 21:03
  Okay. So you can, you know, as the mechanism designer, write down on your pad like, uh, this mechanism would have like really great properties.
• 21:11
  Right. But again, the block producer can throw it out if it's not in their own best interests.
• 21:15
  So you need to have a transaction fee mechanism, which is in the interest of the block producer to run it as you intend.
• 21:21
  It should be profit maximising for that block producer.
• 21:24
  So that's going to lead to our it's going to be part of our second type of incentive compatibility constraint.
• 21:29
  The other part of it I see is what I said about shill bids. The fact that the block producer can just inject whatever it wants.
• 21:36
  And if you think about it, that then tells you why we cannot copy paste a second price option into this problem.
• 21:41
  Right. So if you're allegedly running a second price auction and you get to put in your own bid after you see everybody else's,
• 21:48
  write the high bids, $10, you're going to have a show bid of $9.99.
• 21:52
  Okay. So really, the second price auction really devolves into a first price auction.
• 21:56
  Anyways, when in this block, producer has this power to insert shill bids after the fact.
• 22:01
  So that'll be the other part of MC. We want there to be no incentive to insert shill bids of this form.
• 22:07
  Finally, uh, in a blockchain context, if possible,
• 22:11
  you would like to worry about collusion a little bit more than you normally do in traditional mechanism design applications.
• 22:16
  In traditional applications, you kind of like, you know, make all of the participants kind of sign a legal contract promising that they won't collude.
• 22:22
  And if you catch people colluding, you kind of like hand them off to the to the rule of law in effect.
• 22:27
  And it's not that that's impossible in a blockchain context, but it's really harder.
• 22:30
  So if you can design a mechanism where the mechanism design itself already discourages any kind of collusion,
• 22:36
  for example, between the users and the block producer, that's a property you would like to have.
• 22:40
  And that's going to be our final set of incentive compatibility constraints, which are going to be called OCA proof.
• 22:44
  This OCA here stands for off chain agreements.
• 22:49
  The question then is going to be, is there a transaction fee mechanism that has all of these properties against the incumbents?
• 22:55
  The first place auction. It turns out it does satisfy both of these two types of constraints,
• 23:00
  not unrelated to why it's been so successful so far in a blockchain context, and it very much does not satisfy truthfulness.
• 23:06
  Again, in a first price auction, you always want to shade below your maximum willingness to pay.
• 23:11
  So the question is, can we actually get all three of these at the same time?
• 23:15
  Sure. So in the next couple of slides, I have formal definitions of the two new and available constraints.
• 23:20
  Again. So remember that's the same as truthful. So there should just be no incentive for users to misrepresent their preferences.
• 23:26
  There's two novel ones. I'm not going to go through them in detail, given what I've told you in English.
• 23:31
  These are the math definitions that any of you would write down anyways. So I'm not going to go through them carefully.
• 23:36
  I just want to point out that each of these two new types of incentive compatibility constraints
• 23:40
  kills off one of the mechanism design formats you'd be tempted to copy paste from a textbook.
• 23:45
  MSI we already talked about. This is what kills off the second price auction, because those kinds of auctions are easy to manipulate using show bids.
• 23:52
  What about okay proof? This is the one.
• 23:54
  So remember MSI says it should be profit maximising for the block producer to run the mechanism that you want them to OCA proof.
• 24:00
  And that says a cartel of users in the block producer should not be able to do better off by sort of in a,
• 24:05
  in a coordinated way, deviating from what they're supposed to be doing.
• 24:09
  And so there what this kills off is the use of a reserve price, at least of the use of a reserve price.
• 24:14
  And the most obvious way to see what I mean. Suppose you tried to have a transaction fee mechanism where you forced a price floor at ten sort of £10.
• 24:23
  You said to get a transfer, to be eligible for inclusion, you have to pay £10 for your transaction.
• 24:29
  Right. But now imagine, like it turns out there's a bunch of people that want to be included, but it's only worth £7 to all of them.
• 24:34
  Okay, so if everybody did what they're supposed to be doing, there would be an empty block because no one bid high enough to get it.
• 24:41
  But now, if you think about it, there's a real incentive to cut sort of a deal on the side.
• 24:44
  Right. The block producer could just say, hey, everybody, make sure you bid £10 on chain so you're eligible for inclusion and I'll refund you.
• 24:51
  Let's call it three and a half pounds off Shane, and we'll all be better off than we would have been otherwise.
• 24:56
  Okay, so reserve prices are the casualty of this. Uh, okay.
• 24:59
  Previous, uh, condition. Okay. All right.
• 25:03
  So those are three types in compatibility robustness to manipulation by users, by block producers and by coalitions of users and block producers.
• 25:11
  So we can assess any transaction fee mechanism. Now according to these dimensions.
• 25:15
  Let me tell you about the challenger for Ethereum. Yep.
• 25:18
  5059. And let's assess it according to those three dimensions IP.
• 25:22
  If you're wondering that stands for Ethereum Improvement Proposal.
• 25:26
  This is the way by which changes to the Ethereum protocol get vetted and discussed in that community.
• 25:31
  So what does this new transaction fee mechanism? Three pretty big changes.
• 25:35
  And it's important that they all happen together.
• 25:37
  Again this is one of the things that kind of freaked people out because it seemed like a lot of moving parts.
• 25:41
  First of all, I'm going to sound crazy. There's going to be a reserve price.
• 25:45
  Okay. This is going to be called, in this context, a base fee. But wait, I said, okay.
• 25:49
  Prudence kills off any possible use of reserve price. All right.
• 25:53
  It kills off the obvious way of using a reserve price, in which the revenue raised by the reserve price is passed on to the block producer.
• 26:01
  As you would sort of expect it to. Okay.
• 26:04
  It turns out if you redirect revenue generated by a reserve price anywhere else, actually, you can get that property.
• 26:12
  Okay. And in 50, 59, they're going to do the simplest way of directing it somewhere else,
• 26:16
  which is literally money that's used to pay the reserve price fee is simply burned, if you like.
• 26:22
  It's literally just removed from the circulating supply of the native cryptocurrency removed from the supply.
• 26:28
  Okay. So a reserve price or base fee with all revenues from it being burned.
• 26:33
  Now. Next question is how do you know what the reserve price should be? Should it be a dollar?
• 26:37
  Should be $10 should be $100. How would you know? Ideally you would like a market clearing price where supply hits demand.
• 26:42
  You'd like the price at which the number of transactions willing to pay.
• 26:46
  That price is exactly 200. Goes up the block completely. And moreover, it's the most valuable transactions that you're including.
• 26:52
  You don't know. You know your supply. You don't know the demand. So you don't have the market clearing price.
• 26:56
  So it's just going to do local search trying to find it. Okay. The current reserve price looks too high.
• 27:01
  It's going to do a local adjustment, make it a little bit lower and vice versa.
• 27:04
  Okay. How do you know whether the current reserve price looks too high or too low?
• 27:08
  Well, rather than having a hard cap of 200 transactions per per block, like I said before.
• 27:14
  So, uh, let's be a little more flexible. Let's make that a soft capacity rather than a hard capacity.
• 27:19
  We'll let you go up to say like 400 transactions if you really need to, but the target is still 200 transactions in a block.
• 27:26
  And so now the target guides the local search. If a block is produced with 300 transactions, it seems like your price is too low.
• 27:33
  So you better raise it. If the last block has only 100 transactions, it seems like you're making things too expensive, so you lower your price.
• 27:40
  Uh, for the auction. That happens 12 seconds later.
• 27:43
  Okay, so you have a reserve price adjusted through local search, using past block sizes as the unchanged signal for which way to adjust.
• 27:51
  Okay. Finally, you're going to have a built in sort of emergency first price auction.
• 27:57
  So users have the option if they want to pay above and beyond the reserve price, above and beyond the base fee,
• 28:06
  uh, in which case that extra amount is passed on to the block producer like bids were in a first price auction.
• 28:13
  Okay. And as we'll see, this is kind of in there to gracefully degrade into a first price auction.
• 28:18
  If the reserve price happens to be very, very different than what you'd like it to be, the market clearing price.
• 28:22
  Okay. So this is the EIP 5059. This is the quite a bit more sophisticated one they were considering switching to back in back in 2020.
• 28:31
  And the question I want to ask is is this better than a first price auction.
• 28:34
  And again I've set up the rules by which we mean better. I mean does it satisfy more of those incentive compatibility constraints?
• 28:39
  Disick MC and okay, let's review the incumbent first price auction.
• 28:44
  As we said, definitely not truthful. You always want to shade your bid. Easy to check.
• 28:48
  It satisfies the other two constraints. Okay.
• 28:51
  And one thing that's kind of annoying, actually, in a way, about the first price auction, it's like there's a million different applications,
• 28:57
  a million different problems having nothing to do with blockchains, where that would be a totally reasonable mechanism to use.
• 29:02
  Right?
• 29:02
  It sort of is totally insensitive to the fact that you're working in this sort of blockchain environment where it's thinking about like IP 5059,
• 29:08
  right? You're doing this stuff you would never do otherwise. You'd never think of this mechanism just like randomly, right?
• 29:14
  Like, first of all, you're using the fact that there's an auction every 12 seconds and the auction outcome is public.
• 29:19
  So you could just have this very natural local search procedure that takes what happens 12 seconds ago to inform the current base of it.
• 29:25
  All right. So that's using the repeated nature of these auctions. And then there's also that burning of the base fee revenues,
• 29:30
  which would be very hard to do in a credible way in sort of a traditional mechanism design application.
• 29:36
  And in exchange, as a reward for taking advantage of these unique kind of, you know, the enlarged design space you have in the blockchain setting,
• 29:43
  you do get a Parado improvement in the incentive compatibility compared to the incumbent compared to the first price auction.
• 29:49
  It's a little less trivial, but it is in fact still mesi and OCA proof.
• 29:53
  It's not the case that it's always truthful, but it is the case that it's usually truthful.
• 29:57
  What do I mean by that? Well, if the reserve price is zero.
• 30:02
  Then it's exactly the same as the first price auction, if you think about it. Okay, so the first price auction isn't truthful.
• 30:07
  Neither is this mechanism when the reserve price is zero.
• 30:10
  Assuming there's more than 400 transactions that are willing to get in for free. Okay.
• 30:14
  In general, if the reserve price is way too low, you revert back to this first price auction.
• 30:18
  But you can show that is the only event in which you will not be a truthful mechanism, as long as the base fee is semi calibrated.
• 30:26
  Right. If it's at least kind of high enough that there's at most 400 transactions,
• 30:30
  a double full block willing to pay that reserve price, then in fact, it's a truthful mechanism.
• 30:35
  Everybody sort of pays the reserve price. Everybody's happy. Okay.
• 30:38
  So in most cases it is in fact, uh, it is in fact, Disick.
• 30:43
  I proposed a variant of this mechanism where the usually moved from the D6 to the OCA.
• 30:48
  Proof. So always in my c always Disick usually oca proof with the exact same edge case.
• 30:54
  Uh, so that's fine. Of course you want the best of all worlds.
• 30:57
  You'd like to have. Always all three of these. Uh, but it turns out.
• 31:01
  Let's skip that back. Um, there's a very recent result.
• 31:07
  This is, um, joint with Elaine. She, uh, of Carnegie Mellon and her PhD student, Hao Chung.
• 31:12
  In fact, you cannot get all three all the time, so you need to make some kind of compromise.
• 31:16
  So both the IP 1559 and the variant that I suggested in some sense live on
• 31:19
  the Parado frontier of incentive compatibility of transaction fee mechanisms.
• 31:23
  Okay. So to tie this back to kind of the Ethereum story.
• 31:27
  Um. The epiphany 59 was indeed adopted in early August of 2021, and it's been running happily ever since for the past two and a half years.
• 31:36
  Uh, I released my initial report. It's like a 58 page report, kind of for the general public on December 1st.
• 31:41
  Immediately, the people from the community we've been talking about, you know, they sort of realised it immediately.
• 31:47
  Vitalik Buterin Oh, I forgot to say that. Yep. 5059 the designer of that mechanism is Vitalik Buterin, who's also the, uh, co-founder of Ethereum.
• 31:54
  Uh, so he and Tim Baker both sort of immediately commented on it as the day to the switchover in early August 21st approached,
• 32:01
  my report was kind of the standard reference people use to explain to a public audience,
• 32:05
  you know, what you should expect to be solved and what would not be solved by, uh, switching over to this, um, transaction fee mechanism.
• 32:12
  So now it's just been running happily ever since. There's even sort of dashboards which sort of track the amount of East it's been burned to date,
• 32:18
  kind of because of the base fee revenues and, and so on and so forth.
• 32:21
  So it's definitely kind of a, uh, um, it's a it's a critical part of today's Ethereum blockchain protocol.
• 32:29
  So that was the segment where I wanted to zoom in on this notion of the open access property.
• 32:33
  Right, and how to make this computer in the sky economically sustainable.
• 32:37
  Next, I want to sort of drill down on like, what do I actually mean when I say that has no owner, has no operator?
• 32:42
  Like what does that mean literally? And what it means literally is that actually it's not a single computer, but it's lots,
• 32:49
  maybe thousands of computers scattered all over the globe that, through cooperation, are simulating the state of a virtual machine.
• 32:57
  So this computer in the sky isn't physical. It lives in the simulation of thousands of physical nodes down on Earth.
• 33:04
  Those nodes need to stay in sync about the current state of that virtual machine.
• 33:09
  And they do that by running what's called a consensus protocol.
• 33:13
  So this is going to be joint work with Andy Lewis Pi, who's just down the road London School of Economics I just had lunch with him yesterday.
• 33:19
  Um, and sort of all my papers these days, when I release them, I usually have sort of a corresponding, uh, tweet storm.
• 33:26
  And I know that's like kind of a gimmick.
• 33:28
  On the other hand, it seems like it's been, like, super helpful for people like you haven't talked to academics and they'll say,
• 33:33
  yeah, you know, I went to this conference, you know, the formal talks were like, not that helpful.
• 33:37
  But like the quarter conversations were like, great. I went just for the quarter conversations.
• 33:41
  And these are the quarter conversations just made available to everybody, which sort of seems like a positive thing.
• 33:45
  I think this is the longest research paper I've ever co-authored, 75 pages.
• 33:49
  I know some of you have written longer ones, but for me, this is my record.
• 33:53
  Um, so this is the only time I've ever had to do a recursive tweet storm, a tweet storm, a tweet storms.
• 33:57
  So still, I think a lot faster to read than the full 75 page paper.
• 34:01
  Obviously, I'll only be able to tell you a little bit about sort of the results in here in the time that I have.
• 34:06
  Okay. So just like in the mechanism design section, it's not the traditional mechanism wasn't useful.
• 34:14
  It was we built on it, but we needed to extend it because of these sort of permissionless nature of blockchain environment.
• 34:21
  Exact same thing will happen here. Design and analysis of consensus protocols.
• 34:26
  Classic topic okay, brilliant work in the 1980s Turing Awards given to Barbara Liskov, Leslie Lamport and we will be building on that theory.
• 34:34
  But again, because of the permissionless nature of blockchain protocols, that theory has to be significantly extended.
• 34:41
  Okay. So I want to tell you about that next.
• 34:44
  Be so again since census protocol, keep a whole bunch of nodes in sync with each other on the state of a virtual machine.
• 34:50
  The minimal properties you would want of any consensus protocol is liveness and consistency.
• 34:56
  Liveness, meaning as long as there's work to get done, it should get done.
• 34:59
  If there are pending transactions, they should eventually be processed.
• 35:02
  Consistency means like really the nodes got to stay in sync, but they should not have fundamental disagreements about,
• 35:07
  for example, what instructions have been executed in this in this virtual machine?
• 35:12
  Okay. Why is that a hard problem?
• 35:15
  Two of the traditional challenges are, first of all, some of these nodes running the protocol may not do so correctly.
• 35:20
  Who knows why. Maybe they crash. Maybe they have buggy software. You know, maybe they're controlled by a malicious actor.
• 35:25
  Who knows, they may deviate from what you you expecting them to do?
• 35:29
  Same thing with the communication network. Okay, so it may be a good day for the internet.
• 35:33
  It may be a bad day for the internet. It's hard to predict exactly how long messages will be delayed before received by the intended recipient.
• 35:40
  Okay. And in my opinion, one of the reasons why the traditional, um, theory of consensus protocols has been so successful,
• 35:47
  there's this really rich, deep literature over the last 40 years or so.
• 35:51
  I really give a lot of credit to the pioneers in the 1980s for setting things up as kind of like
• 35:57
  a playground for theorists who just have a lot of fun with and with clear measures of progress.
• 36:02
  Okay. In particular, if you take these two types of challenges, nodes that are not doing the right thing, the network not being as good as you'd like.
• 36:09
  They took each of those challenges and they parameterised them using hierarchies.
• 36:13
  So in effect, they almost like gave you ladders where like better papers just meant sort of climbing further up these ladders.
• 36:20
  Okay, let's take the faults. Okay. Nodes that deviate from what you want them to do.
• 36:24
  You've got very benign types of faults. Like maybe there's just like a hardware failure.
• 36:28
  It crashes. You never hear from it again. Okay, that's relatively benign.
• 36:31
  At the other extreme, you know, maybe like a hostile nation state has taken over one of your nodes and is actually
• 36:36
  just doing everything they can to mess up your protocol be a Byzantine fault.
• 36:41
  Same thing with the communication network. You've got very easy models, like the synchronous model, where you can assume that guaranteed,
• 36:47
  every message will be received within, you know, whatever. One second, five seconds, you've got the intermediate model,
• 36:53
  the partially synchronous model where synchrony may be interrupted with periodic, periodic but finite length denial of service attacks.
• 37:00
  And then you've got the sort of, you know, challenge level of the asynchronous model,
• 37:03
  where the only thing you assume about message delivery is that eventually that happens.
• 37:07
  Okay.
• 37:08
  So obviously positive results get more and more impressive, sort of the weaker the assumptions and vice versa for for protocols for positive results.
• 37:16
  Now, when you pass to permissionless consensus protocols as familiar from Bitcoin and Ethereum,
• 37:22
  there's more challenges than just the network and faulty nodes.
• 37:26
  Okay. So one challenge is you don't know who's running your protocol.
• 37:31
  Okay, so any of us today could go download some software spin up and start contributing to the Bitcoin protocol.
• 37:38
  Literally today it's been running for 15 years. Doesn't matter.
• 37:41
  It doesn't care. You could join the party right now. That's not a property historically consensus protocols have ever wanted to have.
• 37:48
  Secondly, you've got what's known as the Sybil problem. Given that anyone can sort of join the party and start running the protocol,
• 37:54
  anyone can also join multiple times under multiple identifiers, and you'd never know the difference.
• 37:58
  So one participant can masquerade as many.
• 38:01
  So, for example, if you're trying to do something like voting, that gets a lot more complicated with symbols.
• 38:05
  If you've ever heard about like proof of work or proof of stake. Those are techniques to control the Sybil problem.
• 38:10
  What I want to talk about today is this third additional challenge of getting the permission of the setting,
• 38:15
  which is that there may be nodes which will not faulty.
• 38:18
  There's nothing wrong with them. They're periodically inactive. Okay.
• 38:21
  So someone, you know, running a node to contribute to the Bitcoin protocol.
• 38:24
  Maybe they turn it off when they go out of town for the weekend. They come back Monday morning, turn it on again.
• 38:29
  And even though the amount of fluctuation, even though sorry, the amount of participation and who's running the protocol fluctuates.
• 38:34
  You would like the protocol to just, uh, hum along, uh, you know, come along perfectly.
• 38:40
  Okay. And in the same way that in the 1980s, the challenges of false and unreliable communication were parameterised through hierarchies.
• 38:47
  In this work, we do exactly the same thing with inactivity.
• 38:51
  So we have a hierarchy of degrees of sort of stronger and stronger assumptions.
• 38:55
  We allow protocols to make about the activity of honest participants.
• 38:59
  So I'll show you the hierarchy on this slide. There's going to be four levels.
• 39:04
  Uh, the top level is going to be the one where you make the weakest assumptions. So that's gonna be the hardest one to design protocols in.
• 39:10
  And then the assumptions and protocols allowed to make is going to get stronger as we go down the slide.
• 39:14
  So you you sort of have a back. So you expect to see lots of impossibility results up here.
• 39:19
  Hopefully you expect to see lots of positive results like protocols that have good properties down here.
• 39:24
  Okay. So first level we call the fully permissionless or PHP model.
• 39:30
  And here literally the protocol is not allowed to assume anything at all about who is running it right now.
• 39:36
  No idea. Okay. And if you ask, I think people in the 20th century working on consensus protocols,
• 39:43
  whether any nontrivial functionality would be possible under that assumption.
• 39:47
  My guess is everyone would have said, no way, that's crazytown. Okay.
• 39:50
  Turns out Bitcoin protocol under reasonable assumptions actually is provably consistent in live.
• 39:55
  Knowing literally nothing about who's running it at any given moment in time.
• 39:58
  Just still to this day, I find kind of incredible. All right, so that's the most demanding, fewest assumptions setting.
• 40:04
  You know nothing about who's running a protocol. Slightly stronger assumption is what we're going to call the Da or dynamically available setting.
• 40:12
  Okay. And so here there will be this list of identifiers known to our protocol.
• 40:17
  Okay. And those of you that know a little bit about this area canonically this would be, you know,
• 40:22
  people who have locked up in escrow some stake in a staking contract of a proof of stake blockchain protocol.
• 40:27
  That would be this list of identifiers.
• 40:29
  So you're the protocol is allowed to assume that whoever is running the protocol has an identifier in this known list.
• 40:36
  Okay. So you're not going to have like a block proposal from someone you've never heard of, for example.
• 40:39
  But you could in Bitcoin. On the other hand, you know, maybe people on that list have gone away for the weekends.
• 40:45
  Okay. So it's a necessary condition but not a sufficient condition for participation.
• 40:49
  Uh, that your identifier is in that list. Third level is the quasi permissionless or QP setting.
• 40:56
  So we again have this list of identifiers. But now membership in that list is both necessary and sufficient for participation.
• 41:03
  So in other words, when you're designing a protocol, you are allowed to assume that all of the identifiers you know about controlled by
• 41:10
  honest players actually are doing what they're supposed to be doing right now.
• 41:13
  You can count on that. They are not away for the weekend. Okay.
• 41:17
  And then finally we have the classical permission model, where at the time of protocol deployment, you know exactly who all of the nodes are.
• 41:22
  They're going to say stay the same all the time, and nobody ever turns the machines off.
• 41:26
  Okay.
• 41:27
  And if you want to map these onto protocols you might have heard about, as we said, Bitcoin operates even in the PHP setting dynamically available.
• 41:35
  This is in hindsight we can take proof of stake longest chain protocols like say Cardano.
• 41:40
  And in hindsight, they're kind of built to work properly, even in a dynamically available setting.
• 41:44
  Um, if you've heard of like the Pbft protocol or things based on them, like say, Algorand, again, in hindsight,
• 41:49
  we can say and also actually today's Ethereum, in hindsight, they're meant to work in the quasi permissionless setting.
• 41:56
  Okay. Now in our paper, we show that all.
• 42:00
  We show that this hierarchy is strict. Okay, so we have separations every level of this hierarchy.
• 42:05
  We show that there are things that are possible which are provably impossible at the level above.
• 42:10
  Okay. And from our results, it would appear that the really again there's a separation everywhere.
• 42:15
  But the really big separation the chasm would appear to be between D and QP.
• 42:20
  So I just want to add a little bit, add a little bit of colour about that chasm in the middle of the hierarchy.
• 42:25
  Okay. So again lots of stuff which you'd like to do, which you can do in the q p setting, which is impossible in the day setting.
• 42:32
  Okay. So two slides, one about the negative results in the Da setting, one about the positive results in the q p setting.
• 42:40
  All right. So dynamically available setting. So again remember what this means.
• 42:43
  So if you want to think about a proof of stake protocol. But here's the protocol knows this list of identifiers.
• 42:48
  Membership in the list is necessary but not sufficient for participation.
• 42:51
  So there's still going to be like wildly fluctuating participation. Some people might have gone away for the weekend.
• 42:56
  Uh, let me say three things you would like a protocol to have that you cannot have in the dynamically available setting.
• 43:02
  You cannot have them, no matter how clever you are with your protocol. Okay. All right.
• 43:09
  So property number one okay asynchronous safety.
• 43:13
  So this means if you have a network partition or there's sort of a long denial of service attack,
• 43:17
  you would like to obviously not have a consistency violation.
• 43:20
  But if you actually remain live in the dynamically available setting, you cannot also remain consistent in the presence of network partitions.
• 43:29
  If you have like a really specific protocol in mind, like, you know, Bitcoin or longest chain protocol,
• 43:32
  you can probably kind of see in your head why you're going to lose consistency with the network partition.
• 43:36
  That's not the point here, right? There's no concrete protocol on the slot.
• 43:40
  Right. The point here is to show that fundamentally, any protocol, no matter what it looks like,
• 43:46
  if it's live in the dynamically available setting, you must suffer consistency violations under network partitions.
• 43:52
  That's the context of this first result. Okay. Second property you'd like to have something called accountability.
• 43:58
  Okay. Which is should you suffer from a consistency violation should nodes get out of sync.
• 44:03
  You would like to know why. You would like to know which nodes deviated from intended behaviour that led to that consistency violation.
• 44:10
  That's called accountability. You get a smoking gun for who's responsible.
• 44:14
  That is also impossible in the day setting. Finally optimistic responsiveness.
• 44:19
  This is like an instance optimal version of liveness.
• 44:22
  So this just says like if the network's having a particularly good day to day, like it's five times faster than usual.
• 44:28
  Your protocol should also, uh, react five times faster than usual.
• 44:32
  So transactions should be confirmed faster as the network gets faster.
• 44:36
  Also provably impossible in the day setting. Turns out all of this is true even if there are no, uh, faulty nodes.
• 44:43
  Okay? Merely the possibility of fluctuating participation triggers all of these impossibility results.
• 44:50
  Positive results on the QPR setting. So again, here a protocol can assume quite a bit more.
• 44:55
  It can assume that not only is there this list of identifiers, but membership in that list is sufficient for active participation.
• 45:03
  So any identifier you see in there, which is controlled by an honest player,
• 45:06
  you can count on them being online doing what they're supposed to be doing.
• 45:10
  Okay. Like those of you who do know a little bit about Ethereum may know that there's sort of slashing.
• 45:14
  You can actually lose funds for inactivity. Okay, so if you're running an Ethereum validator, you're supposed to be like voting on stuff all the time.
• 45:20
  If you missed your turn for a while, you'll actually start losing some of the stake that you've pledged.
• 45:24
  There's economic penalties for being inactive, and that to be kind of like a, uh, sort of a light bulb going off.
• 45:31
  Uh, I guess Ethereum is really motivated to be in the quasi permissionless setting.
• 45:35
  They really need all the people they know about to be active. That's exactly what you're punished when you're inactive in Ethereum.
• 45:41
  All right. So you obviously need some control over how powerful the adversary is.
• 45:46
  And so here the magic threshold is going to be a third. So you need less than a third of the voting power to be controlled by an adversary.
• 45:52
  Uh, but in that setting you actually get all three of those properties. Okay. So you can guarantee that you have consistency.
• 45:58
  So there's a single protocol that achieves all three of these guarantees. Asynchronous safety doesn't matter what the network does.
• 46:03
  You will never have a consistency violation if there's a consistency violation because the adversary is bigger than the one third threshold,
• 46:10
  there's a smoking gun and you can figure out who they are, possibly for punishment later.
• 46:15
  And then finally, it does automatically speed up the speed of transaction confirmation as the network speeds up as well.
• 46:21
  Okay, so this is what I mean by the chasm between D and CuPy.
• 46:24
  Again, the separations at all levels of the hierarchy, but the starkest one is the one I've summarised in these two slots.
• 46:30
  Okay. So, um, obviously there's a lot more results in the paper I'm not gonna have time to talk about, honestly.
• 46:36
  I mean, we like the we like the results in those papers, in this paper,
• 46:40
  but we're really hoping that this becomes sort of the standard model and the standard
• 46:44
  language for lots of people to prove cool results about permissionless consensus.
• 46:47
  So we have a new paper also with Eric Buddhist, which is about slashing and proof of stake protocols.
• 46:52
  It's a paper that like, feels like should have been written a long time ago,
• 46:55
  and I think the only reason it's being written now is because the previous paper I just told
• 46:58
  you about gives us the language and the framework to make it to state theorems of this form.
• 47:02
  Okay. When does slashing work in a proof of stake protocol? So hopefully much more.
• 47:06
  I'd love to see maybe some people in this room. Uh, follow on on this.
• 47:10
  The style of work. All right.
• 47:13
  So for the last part. I said at the beginning, right.
• 47:17
  The one thing I wanted you to remember from this talk is that the technology is not fundamentally about cryptocurrency, about prices, about finance.
• 47:25
  That said, at the application layer, there are some really intellectually interesting things happening with financial applications.
• 47:33
  I want to tell you about some of my work there. Last. This is going to be joint, uh, with Jason Jonas, who's my PhD student at Columbia Cmac.
• 47:41
  And well, let me who who's my colleague in the business school, Columbia, Anthony Lisanne, who's a professor of finance at University of Chicago.
• 47:46
  Booth. All right. So.
• 47:51
  Right. We talked about property rights for sort of digital assets. Once you have ownership, right.
• 47:56
  Another property right is the right to transfer. Okay.
• 47:59
  If you have transferable digital assets, you have that you have you have the possibility of exchange of markets.
• 48:04
  Okay. Very simply maybe you want to exchange some cryptocurrency like say eath for some stablecoin, something pegged to the dollar like Usdc.
• 48:15
  And, um, we need a mechanism. We would like a mechanism to enable exchange of different digital assets.
• 48:21
  And once again, why is this a hard problem? Right? Doesn't this happen like, every single day?
• 48:26
  Like on every single stock exchange? Yes it does. The usual mechanism you would use in that context would be a limit order book.
• 48:32
  So you would have standing by standing sales, you'd have sort of matching logic to sort of unclear trades as they come in.
• 48:38
  Uh, and again, it's just it's not a perfect match for the blockchain environment.
• 48:42
  Okay. For two reasons. Um, reason number one, at least for Ethereum, at least for the older blockchain protocols,
• 48:48
  uh, implementing a limit order book is computationally relatively expensive.
• 48:53
  Okay. You have to maintain this. You have to maintain the order book. You have to do the matching, uh, more modern blockchain protocols.
• 48:59
  You know, probably they have enough computational power to do this. Well, but Ethereum does not.
• 49:03
  So that motivated looking at some different designs.
• 49:06
  Uh, secondly, to secondly, limit order books, whether you're in a blockchain environment or otherwise work really well in thick markets.
• 49:15
  We have lots of people on both sides of the market's interested in trading right to trade.
• 49:19
  In a limit order book you need a counterparty. You want to buy it. You need someone to sell okay.
• 49:23
  And ETH, Usdc. I mean that's actually a very thick market. But a lot of the digital assets that people want to exchange are thin markets.
• 49:29
  And the worry would be that there's just usually not a counterparty to trade.
• 49:33
  Okay. So both of these two issues have motivated, uh, the popularity of automated market makers or amms, on blockchain protocols such as Ethereum.
• 49:44
  Okay. So what's an Am? It's a market that in some sense is always open for business.
• 49:50
  At any given moment in time, an arm will quote you a spot price, and we'll be willing to take either side of a trade at that spot price.
• 49:57
  Right? So like, you know, $3,000 for eath that'll be willing to buy it at the margin for that or sell it at the margin at that.
• 50:03
  Either way. Okay. And, um. Uh.
• 50:08
  Good. So the next question you might say is, okay, that's fine.
• 50:12
  So I guess the market maker, like the Am, is itself acting as the counterparty.
• 50:16
  So I guess, you know, there's always a counterparty there that's always open for business.
• 50:19
  But then you might be like, like, why does this arm even have any of these assets in the first place?
• 50:24
  Like where did it get its eath from? Where did it get this Usdc from?
• 50:27
  And the answer is that those are provided via deposits by entities that are here called liquidity providers or LPs.
• 50:34
  Okay. So so these are people who hand over their hard earned cryptocurrencies two and a m so the traders can trade with them.
• 50:41
  Why would you do that. What's because you earn a share of the trading fees by depositing in this way.
• 50:46
  So it's a way to earn yield on your assets by depositing them in one of these. And that's.
• 50:51
  All right. Well, if I put it that way, like, why would you not do that?
• 50:54
  Right? If you just get sort of free money, like, on your assets by putting them in the pool?
• 50:58
  Sounds like a good idea. Why would you not do that?
• 51:01
  And the, you know, so the the issue with market making and again this is not specific to the blockchain protocols,
• 51:08
  but the reason market making is scary is because of adverse selection.
• 51:12
  Okay. Whenever someone's willing to trade with you like there should be this like fear in the back of your mind that like,
• 51:17
  maybe you know something that I don't like. Maybe there's a reason they're trading.
• 51:20
  Okay. And actually, if you think about it for for purely on chain exchanges.
• 51:24
  Right. Like a Uniswap that's a, that's a popular name of a one of these automated market makers like Uniswap on Ethereum.
• 51:30
  Uh, that's going to be happening a lot because remember what I said? I said there's a new batch of transactions every 12 seconds.
• 51:36
  So Ethereum's virtual machine stays frozen for 12 seconds at a time.
• 51:40
  And in particular, the spot price of an arm, which is a function just of the state of the virtual machine, stays frozen for 12 seconds.
• 51:47
  A lot can happen on the open markets and 12 seconds, right?
• 51:50
  And so generally, often there is an arbitrage opportunity with each Ethereum block that gets that gets added.
• 51:57
  So for example, if on the open market so that the price went up,
• 52:00
  all of a sudden there's an arbitrage opportunity where you buy from the AMM at the stale low
• 52:04
  price and then flip it on a centralised exchange at the current higher open market price.
• 52:09
  Okay. So that profitable arbitrage comes at the expense of the liquidity providers are playing a zero sum game in effect.
• 52:17
  All right. So that is the cost of providing liquidity to an adverse selection costs.
• 52:22
  Uh which goes to arbitrage right. So, um, if you're thinking about possibly helping or assessing, you know, uh, I mean, in general making markets,
• 52:32
  these are the two things you're sort of weighing with each other,
• 52:35
  the fees you're making and the average selection costs you're suffering fees pretty easy to think about.
• 52:39
  They're generally just sort of a percentage of volume, because you can sort of know how to think about how much revenue you might be making.
• 52:45
  It was the adverse selection costs where people didn't really have a good mental model for how to think about that in an EMS,
• 52:51
  let's say, in 2022, when we did this, when we did this work. And so what we propose here is we propose what is now the industry standard for
• 52:58
  thinking about the adverse selection costs suffered by liquidity providers of EMS,
• 53:02
  something known as loss versus rebalancing, or LVR, which most people pronounce as lever.
• 53:08
  Okay, so let me just tell you a little about lever. There's two versions.
• 53:12
  First, I'll tell you one, which is really for empirical analysis. This is really meant to do sort of forensics.
• 53:16
  You look back at trades that happened and you ask yourself, did I do well or did I not do well?
• 53:21
  The second version of lever is going to be for predicting the future and assessing, you know,
• 53:25
  do you think it's going to be profitable to be a deposit in a, to be an LP and an arm or not?
• 53:32
  So the first one, were you looking at the past? You just consider a sequence of trades.
• 53:35
  You say and trades. You focus on a single pool like eath for Usdc.
• 53:39
  Uh, and you just the definition is you just sort of do the thought experiment and you say,
• 53:44
  how much better off would I have been had I made the exact same trades that the Am forced me to do as a, as liquidity provider?
• 53:53
  Had I done those exact same trades but done them on the open market instead?
• 53:57
  Okay, so the ideas here are the quantities, right?
• 54:00
  So this is how much sort of aether the AMA forced you to buy or force you to sell, because a trader came in and took the opposite side.
• 54:06
  The piece here is the price on the open market and the Q's.
• 54:09
  Here are the possibly stale prices of the arm. You were forced to do the trade at this price.
• 54:14
  This would have been the price in the open market. So for example, right,
• 54:17
  if you were forced to sell by your amp and the you were forced to sell at a price which was less than what it was on the open market,
• 54:24
  that would be a loss and that would contribute to your lever. Okay.
• 54:27
  So trade by trade, your lever accumulates according to the counterfactual of how much better off you would have been on the open market.
• 54:33
  Okay, so that's obviously very easy to take the data. It's about as hard as like computing the volatility of an asset, something like that.
• 54:39
  I think there's already kind of first year MBAs in certain schools that have Excel spreadsheets that are computing this on various data sets.
• 54:46
  Um, you can characterise it, you know, so why is this a good definition?
• 54:50
  Well, one sanity check that you're on the right track is if you can characterise it in
• 54:54
  multiple different ways and you can here I've given you sort of interpretation,
• 54:57
  number one, which is this kind of thought experiment about trading on the open market.
• 55:01
  You can alternatively characterise it as the best sort of the maximum arbitrage profits that could have been attained from this profit of trades.
• 55:08
  Again, remember zero sum game between the LPs and the arbitrage years.
• 55:12
  So that's kind of a you're seeing that reflected here. Um, alternatively you know,
• 55:16
  if you prefer you can think of it as kind of the residual losses after you've Delta hedged
• 55:21
  out all of the market risk that you suffer by sort of leaping in one of these pools.
• 55:25
  So three different ways to think about lever, which I take as a sign that, you know, maybe it is the right concept or a fundamental concept.
• 55:32
  So let me just talk briefly about sort of predicting the future. So, you know, the lever is going to depend on the prices, right.
• 55:38
  We had a times P minus Q. Right. So obviously the way the PS move around is going to matter for what the lever is going to be going forward.
• 55:45
  If the price never moves, never any arbitrage there's going to be zero.
• 55:49
  The price moves a lot. You might think there's going to be lots of arbitrage and the lever is going to be high okay.
• 55:54
  So we need some model for future price movements. You could experiment with a lot of different things here.
• 55:58
  This is the first paper on the topics. We decided to start with. Just the obvious Black-Scholes model.
• 56:03
  Price moving according to geometric Brownian motion. Uh, if you don't know that model, that's okay.
• 56:07
  Just think of it as like a random walk in a way. Uh, and there's one really important parameter which is the volatility sigma,
• 56:14
  which you can think of is kind of like the typical step size in a random walk in the price.
• 56:18
  Okay. And so definitely as we discussed the lever will depend on the volatility.
• 56:22
  If sigma is zero and the price never moves it's going to be no lever.
• 56:25
  If sigma is high and is moving all over the place probably lots of opportunities.
• 56:29
  It's also going to depend on the arm okay. Because remember the formula we had a times quantity p minus q q is a function of which arm you're using.
• 56:37
  Okay. So different arm designs will give you different spot prices different cookies even for the same sequence of trades.
• 56:44
  So at a bare minimum we want a formula. It's going to have to depend on sigma and arm.
• 56:49
  We would like it to depend as minimally as possible in as interpretable way as possible.
• 56:54
  So here's the main result here. And I don't know if this seems like a clean formula to you or not.
• 56:59
  Probably depends on kind of your prior, but let me just unpack this a little bit.
• 57:03
  Okay, so now we're thinking continuous time right. So the price is moving all the time.
• 57:07
  So there's ARBs happening all the time. Lever accumulates trade by trade.
• 57:11
  So we have an end. That's why we have an integral.
• 57:12
  Now trading is happening all the time at a given moment in time the instantaneous accumulation of lever is given by this formula okay.
• 57:21
  As expected the volatility is in there. Expect volatility squared which is actually pretty severe.
• 57:25
  So that's that's uh it's actually pretty high.
• 57:28
  And then the choice of the AMM does show up, but only in a very kind of local way to this DX by DP term.
• 57:34
  So what this says is this is how much at equilibrium is the um, inventory of the risky asset of the AMM,
• 57:41
  the rate at which that changes as the open market price changes.
• 57:45
  Okay. So the marginal liquidity of the AMM at the current market price, that's what this is.
• 57:50
  All right. And if I had a little bit more time, I could literally just have a slide with a single triangle.
• 57:55
  And this would be like the area of that triangle. Okay.
• 57:57
  So I actually claim if you dig into this a little bit more, it's kind of about the simplest expression you could hope for, I think in hindsight, okay.
• 58:05
  In fact, it's so simple that you can even sort of evaluate and closed form what this is for some of the most popular AMS.
• 58:11
  So there's this so-called x y equals k curve made popular by Uniswap v1 and v2.
• 58:16
  Uh, and here you can actually just compute how leaver accumulates.
• 58:20
  And in fact, it doesn't even depend on where you are in the price range. It's uniform over the prices.
• 58:24
  If you normalise by the value of the pool, you get that the lever accumulates exactly as sigma squared over eight.
• 58:31
  Okay. And this is a sharp enough prediction. Right. You can really sort of plug in numbers here.
• 58:36
  Right. So if you take sigma equal to say 5% which would be kind of typical daily volatility for eath.
• 58:41
  Uh, and if you assume you're making 0.3% fees, which again in this part of the world is sort of pretty standard,
• 58:46
  then what you learn is that for LP to be profitable, about 10.5% of the pools assets should be traded on a daily basis.
• 58:55
  If the volume is higher than that, you're going to be profitable. If the volume is lower than that, you're going to be unprofitable.
• 59:02
  Okay. So you can really evaluate this quite crisply, quite precisely okay.
• 59:07
  And, uh, so we released this paper and started giving talks about it in August of 2022.
• 59:10
  And literally by the end of 2022, this was kind of industry standard for how people were sort of thinking about these adverse selection costs.
• 59:17
  So this was a few weeks later,
• 59:18
  just a couple of sort of leaders in decentralised finance sort of saying that they thought this was the right condition.
• 59:23
  And it's a condition that future design designers should take seriously.
• 59:27
  Lots of times this is in sort of popular podcast and so on.
• 59:30
  Maybe what I'm most proud of is, uh, last year, 2023, we were voted the number one meme of the year in DeFi.
• 59:38
  So. I'm kind of trying to figure out how, like, how do I list this on my CV exactly?
• 59:45
  I feel like there should be some way to do it, but I haven't figured it out.
• 59:49
  So, um, so anyway, like I said, just really within 4 or 5 months, you know,
• 59:54
  lever was just like a really well known concept and continues to be, uh, sort of a central concept in DeFi, which has been fantastic.
• 1:00:01
  Uh, pretty much out of time. Let me just sort of reflect for sort of one minute, because I've been working full time in this area,
• 1:00:06
  maybe for, I don't know, three more than three years now. Um, and I've worked in sort of immature areas before.
• 1:00:13
  Right? So many of us in this room, you know, Julius and Lesley and other people are well,
• 1:00:17
  we're sort of in algorithmic game theory in the very early days, uh, which also have kind of a Wild West flavour at the beginning.
• 1:00:22
  But I'm being reminded of that Wild West feeling now.
• 1:00:25
  And in particular, it reminds me of everything you take for granted when you work in a mature field.
• 1:00:30
  Right? So take like algorithms or I would even put like ML theory in this bucket as well.
• 1:00:35
  Right. Like you've got like relatively low barriers to entry.
• 1:00:38
  Like yes they're technical subjects but you've got good textbooks, you've got MOOCs, etc.
• 1:00:43
  Moreover, the research community has sort of solved the coordination problem, right?
• 1:00:47
  The sort of coordinated on an equilibrium where everybody more or less agrees,
• 1:00:51
  like the language to describe basic concepts like what are the most important definitions?
• 1:00:56
  What are the yardsticks against which you measure research progress? Uh, and, you know, you work in sort of, uh, an immature field like blockchains.
• 1:01:03
  You get none of these things, right? So it's really there's frustrations.
• 1:01:07
  On the other hand, I sort of learn through experience that this is also kind of the universe trying to
• 1:01:12
  tell you that there is a chance you might be working in what's viewed in hindsight,
• 1:01:16
  as a golden age. At the time, before everything, quote unquote easy, had already been done.
• 1:01:22
  So I like, you know, because, you know, you look at like maximum and cut.
• 1:01:26
  You're like, oh, man, I was born too late. I was there in like 1955.
• 1:01:30
  I could have I could have moved on and cut. Right. But the thing to remember is like, oh, like computer science is just changing.
• 1:01:36
  Like it's always evolving. There's always some current version of the maximum and cut through.
• 1:01:40
  And the hard part is seeing it. The hard part is necessarily proving it.
• 1:01:43
  Once you see it, the hard part is seeing it. And so for those of you that are intrigued by this idea of getting in on the ground floor, uh,
• 1:01:49
  of a technology that definitely needs rigorous computer science behind it and hopefully will sort of,
• 1:01:54
  you know, eventually have a massive impact on lots of people. I would maybe encourage you to check out this area a little bit further.
• 1:02:00
  So I'm out of time. I'll leave up the summary slide here, but, uh, let me stop there.
• 1:02:04
  Thanks so much for coming.