Permissionless Consensus with Andrew Lewis-Pye | a16z crypto research talks

Transcript

all right welcome everyone to today's a16z crypto research seminar uh very happy to introduce Andrew Lewis pie professor at London School of economics who will be visiting um all month uh Andy actually got his start as a computability theorist believe it or not but very luckily for sort of web 3 in the blockchains world he's gotten obsessed with um consensus for blockchain protocols we just want to tell us about today so thanks Tim uh so yeah so I'm going to talk about a joint project with Tim um which is aimed at the developing of a general framework for the analysis of permissionless consensus protocols might be the proof of work proof of stake proof of space or whatever uh so the talk I'm gonna keep things at

quite a high level so if you're if you're interested in the details then obviously I encourage you to check out the actual paper which is the same title so the permissionless consensus and you can find that in the archive what's the story with all the hands your title slide your title Slide the hands I've made lots of people voting again so yeah starting at the beginning so um I guess the most basic question is why do we need a general framework uh and the basic answer there is uh so obviously you know uh impossibility results play a crucial role in building an email developed Theory and you need a formal framework in order to proven possibility results so for the permission setting we've got lots of good examples of that right there lots of important impossibility results in the permission setting

so the permission setting is just the classical setting uh that people have been studying consensus protocols in since the 1980s right just means you have a fixed set of known participants okay so yeah in the permission setting we have a lot of good examples of important uh impossible results and results that's a significant impact the way that people go about designing protocols so the the flp theorem is a good example there so we have this um it's nice theorem by Fisher Lynch and Patterson which says that consensus protocols can't be deterministic if they're going to operate in what we call the the asynchronous setting okay whatever that is okay so we see that impacts uh the way we go about designing protocols because if you want to design a protocol that's going to work in

asynchronous setting let me know some random assist required okay so that's that's one example but there are many more examples I could give you so for the permissionless setting though okay so it's a previous Frameworks suffice the model proof of work protocols uh but not to develop a general theory so what do I say that well so in particular we're going to see various results today which can't be expressed can't be explained in the previous Frameworks okay and basically the issue is that the uh it's a previous Frameworks don't have the right language for talking about uh consensus protocols that use what we'll call some on-chain resources these resources like steak okay so one of the things we want to do is to Define uh the permission the setting right we want to map out the space of permissions protocols uh a point of complexity there is that people

often think of some protocols as being like more permissionless than others right so in particular people often think of uh like proof of work protocols as being like in some sense more permissionless than uh proof of State protocols right so is there uh somewhere we can make that besides uh so what we'll let you do is we'll Define a hierarchy of four different settings right from like most permissions if you like down to at least permissionless okay uh yeah so I'll describe those that the settings kind of at a high level now and what they find them more precisely later on okay so starting off with the uh the most permissionless setting which you call the fully permissionless setting okay so the basic idea here is at each moment in time the product has no

knowledge at all about which nodes are currently running it okay so proof of work protocols like Bitcoin and typically interpreted is operating in this setting okay of course in reality you might have some idea about who the players are but the point is that you know technically speaking that's not required for the product for the protocol to operate effectively right as I say so like uh it's a Bitcoin will operate in the fully permission setting and then you consider it like a slight relaxation the fully permission is setting uh we should call the dynamically available setting okay the thing to have in mind here is as long as chain proof of State protocols okay so now uh I think the difference now each moment in time the protocol is aware of a dynamically evolving list of IDs okay so the thing to have in mind here

as I said it's like a longest chamber for State protocol think about the uh the confirmed transactions and what they the who those those transactions say has some stake or stake in escalate yeah okay so now the protocol is aware of a dynamic evolving list of IDs importantly those are the the evolution of this this dynamically evolving list of IDs can be like a function of the protocol execution and it could also be the case that different players have like different ideas about what this list is right because different people might have seen different versions of the blockchain okay so now we have this dynamically evolving list of ideas and in the dynamically available setting we're going to allow uh we can assume that at least some uh honest members of that list of ideas are going to be turning up

and carry out the protocol yeah okay and we might also assume you know some bound on most of row fraction of those being Byzantine that sort of thing okay okay uh so as I say so proof of state only state protocols like Boris or Snow White and then we thought of as operating it should be thought of as operating in this setting okay and then we have a further relaxation which we're going to call the Quasi permissionless setting so the quality permission I said again we have this evolving list of IDs okay but now uh members of the list of these ideas is sufficient condition for membership for participation in the protocol at least if you're honest okay so now we're going to assume that everybody in that list of ideas is turning up and participating in the protocol okay if you think about it so

uh so BST style proof of State protocols like algorand or proof of state implementations of of tenement or whatever they operate in a setting right they require all of the relevant list of participants that turn up and participate otherwise Live Events will be violated okay so proof of stake that's a BST style proof of State protocols operator setting but there are also a whole bunch of proof of work protocols uh such as hybrid beliza hybrid Bitcoin it's a leader they will operate in the setting as well uh so we'll talk about them a bit more later on there's also uh there's a number of papers into some more uh the classical literature on what are called player reconfiguration protocols and these are basically lots of protocols which are like permission

protocols but now you're allowed changing sets of players and actually so proof of State protocols can really be seen as like a particular form of playery configuration protocols okay so play area reconfiguration Protocols are also seen as should be seen as operating in a QP setting the quality permission you should have already said this maybe it's worth reiterating I mean the key thing about bft style protocols is they they vote and so if you're taking your vote you need to know what constitutes a quorum and so that makes it particularly natural to assume that like okay I guess we need people to show up if we're going to get a quorum exact device you've got a certain number of people voting and you need to know what that number is so you know what two-thirds of that number is or whatever yeah Okay so we've got the QP setting uh and

then I'm kind of presuming that people may be familiar already with the permission settings so this is just the sort of classical setting we have a fixed set of known participants okay and also in the permission setting we generally assume that all participants are always active okay so as I said so this is a hierarchy going from the harshest setting down to the the easiest setting as we go down the High Rock you're allowed to make more assumptions okay so that means if we prove any impossibility results for any level of the setting any any level of the hierarchy here then that impossibility result will automatically hold for all higher levels of hierarchy right so if we've proven impossible result for the dynamically available protocols that will automatically hold for fully permissionless protocols okay so here with the filing like a hierarchy of settings rather than the hierarchy of

protocols but then what we'll do is we'll allocate a protocol to the harshest setting in which it's it's live existent or which it performs the required functionality okay so we'll refer to bitcoin as a fully permissionless protocol for example right because it operates in the harshest possible setting okay and then there's a bunch of other stuff you've got to do to fully Define the framework it's not just about finding the hierarchy settings right there's lots of other stuff we have to do but once we've formally defined the framework then we can go about defining General impossibility results yeah a question on the previous slide are you considering like a specific type of network model um and and or is it the case that you can have a protocol that's like say quasi-permancial one network model and like fully dynamic in another Network

model today but you're right so which whether you operate in the da setting on the QP setting might also depend on your similarity setting like like with ethereum or something yeah okay so once we've defined the framework we can prove General impossibility results okay uh and one of the things we're going to be interested in doing in particular is delineating what becomes different uh well possible and different levels of the hierarchy so here are uh a couple of taster theorems for you now in case you're impatient so there'll be some more theorems later on there are more theorems in the paper Okay so the first here says that protocol solving consensus in the fully permissionless

setting cannot be deterministic okay and that holds even in synchrony okay so you have the flp theorem but that's for a much harsher setting in some sense in terms of communication that's the asynchronous setting is that this holds even in synchrony in case you can sort of see that as an analog of the flp theorem in a sense if you like okay there's one theory that we'll see later and then a second theorem here says that dynamically available protocols can't solve consensus in the partial Symphony model so I haven't defined the partial Symphony model yet that you should have in mind this is just like a standard setting which most of the well-knowns permission protocols operates protocol protocols like pvft hot stuff um tender bins and so on they all operate in the partial syndrome model okay so dynamically available protocols can't

solve consensus in this this fairly standard model uh and as I said Okay so we've got this sort of strict hierarchy here so if you have this impossibility result for dynamically available protocols that then has to hold also for the fully permissionless protocols like Bitcoin so now let's start looking at how the framework actually works so if we're going to be um sort of thinking about permissionless protocols then generally we're going to think about protocols that work relative to what we'll call like resources of some kind okay so resources could be stuff things like stake uh hash rate memberships or whatever right just briefly though before we talk about resources I want to introduce like a version of the permission setting in which we don't yet get to talk about resources okay so to move from the from the permission

setting to the permissioner setting there are actually three new challenges that we've introduced simultaneously okay so maybe a slightly confusing thing to do that's what happens okay so now we move to a setting which we have an unknown set of participants okay and set of participants of also of unknown size okay we also assume that now that people can be or players knows what we call them can be active or inactive at different different time slots okay I could be active and inactive and active again and so on okay and we also have to consider a third sort of challenge now to consider the possibility of civil attacks okay it's been introduced to these three new challenges simultaneously like on a technical level on a theoretical level that's a slightly crazy thing to do right if you're

studying things directly generally you want to introduce one new challenge at a time and see what does that change and then you're interested another challenge a challenge to see will that change and so on so here introduce introducing uh three you changes at the same time and basically the reason is that there's a change in AIM right so in the permission setting we're talking about consensus protocols because we want to develop for tolerance now we have this new sort of very good defined name which is decentralization and it seems that in order to uh to have decentralization we need to meet these these three new challenges okay so we introduced the three challenges simultaneously but then when we prove each and possibility result it's going to be interesting to sort of think about so which of these three new challenges is actually required to give that using

possibility result right so sometimes well is it the case all three new challenges are required or maybe it's just one you want one of these these changes that's driving the new impossibility result So when you say the aim is now decentralization do you have a technical definition of what decentralization means or is it just uh never had that might have Labor dagger but no I guess we're we're sort of defining permissionlessness and where uh decentralizations remaining a big term for us okay uh so generally I want to keep everything at a fairly high level I'm not going to go into the sort of technical details of the framework but just to make things uh like a little bit more concrete uh I'm gonna make what I

said dare slightly more precise okay so I'm just going to say the same thing again but it's slightly more precise language okay so we consider a potentially infinite set of players p although we didn't have a finite number activity time slot so we have a potentially infinite number of players p uh each player is going to be allocated and not empty and potentially infinites of identifiers so the identify as you can think of being like a potentially unbounded list of like public keys of which p and such appears aware of the corresponding private keys okay identifier sets are disjoint we have time divide up and discrete time slots okay times like one times two so second it may be important to emphasize that the protocol can't know any of those things so the protocol description is independent of script p is

independent right so these are inputs or protocols unlike the permission set like right these are just these are just facts so the fact about that that will be stated lower down okay so we're trying to divide into discrete time slots times like one times like two and so on up to time slot D let's say we're calling D the duration D could be infinite or D's could be finite depending on what you want to consider okay let me stipulate so each player can now be active or inactive in each time slot if a player is inactive that means they they can't send or receive any messages and they come out no activity whatsoever if they're active then they can send and receive messages and if they're honest they'll carry out the the uh activity is prescribed by the protocol okay then a little bit of terminology so

by a player allocation which has been a function specifying the identifier set for each player and the time slots of each player is active okay and we assume that the player set and the player allocation are unknown okay so the protocol doesn't know that or the veritam players I don't know that obviously each player knows their own identifier set right they identify sets of other players okay and then just a couple more basic definitions so by the synchronous setting we mean a setting in which message delivery is reliable okay so there's some known bound Delta so she will never only sends a message at time T will always arrive at least by time t plus Delta okay and then the The partially synchronous setting uh I'm defining here

slightly vaguely but it's not that difficult to make it precise okay so the policy signal setting message delivery is sometimes unreliable you don't know when it's reliable when it's not but they're guaranteed to be long periods during its message deliverable delivery is reliable in this sense okay and long hair means like sufficiently long as long as you need in order to prove the required property okay so that defines uh like a version of the permissionless setting in which we don't yet have resources okay it's not that hard so well it requires a proof it's not entirely trivial but it's not that hard to see the solving consensus isn't possible in this setting because there's a more form of statement so we consider the fully permissionless I think without resources yet and suppose the player set p is finite well then for every row no protocol

stores but it's added agreement went up to a row fraction to play players maybe it was anti it's a very very great and zero right so as long as there were some buyers and team players around consensus is not possible in this setting so importantly though so this result holds even in the synchronous setting we have entirely a reliable message delivery okay even with a known player set okay as long as we'd actually know their identifiers even with a known player set and with all players active at all time slots okay so it's really it's the possibility of civil attacks that drives its impossibility okay it's not of the three complexities we introduced is this a possible it's only the possibility of civil attacks that's required to get the impossibility here and in fact so there are some results by uh coach and Dani and mortenhoffer so

they consider is setting in which you have an unknown player set okay but where players are always active and there's no possibility of civil attacks and there they are able to get positive results okay because census is possible uh and equally if you can have a like a known player sets you can have no possibility still attacks and essentially where players can be inactive and active at different time slots and there again you can get positive results okay so it's really the it's the possibility of similar tax that makes uh consensus impossible here okay so consensus isn't possible in this setting but then obviously the Innovation the Bitcoin paper is that if we consider some notion of resource like hash rate you know and we restrict the resources that the adversary could own then you can sense it does become possible okay so in our uh framework we're going

to consider resources of two types okay so we have external resources which you can think of as being things like Asics or memory chips okay and then we have on chain resources okay so stake is an example of a long chain resource uh but there exists on the form of oil chain resource and we'll talk about them later on uh so external on-chain resources have some some fundamental differences so first of all is external resources of generally alligators players on-chain resources to identify us it's also the case online resources can be selectively confiscated right so was that that becomes important when you start thinking about things like slashing and that becomes important for economic arguments uh then it's also the case so on-chain resources are user relative right in the

sense that different players may see different versions of blockchain and so they have different ideas about who owns what yeah okay and generally it's also the case that on-chain resources only change with each consensus decision okay so there are yep do you also draw a distinction that like external resources are typically infinite in a sense or you don't know what the total you don't know the denominator of them and yeah yeah so generally when we're doing the external resources we'll we'll assume that you don't know the total hash rate and that kind of thing although no you can potentially consider settings where that that is you do know the total hash rate and see what changes okay I Ask of our basic assumption will be you don't know the general hash rate and that distinction plays an important role and

improves yeah okay so they have different properties so we have to model them differently uh so we're going to model external resources using something they're called permitted oracles uh but we won't use oracles to model on-chain resources Okay so we've got external resources on-chain resources uh that's what I'm going to do now I'm going to talk about external resources for a bit then unchain resources are a bit and then we'll just start defining the different levels of the hierarchy okay thanks for fully permissionless downwards okay so the higher level first of all okay so for each external resource we consider what we call a resource allocation function okay this is a simple thing resource allocation function just allocates each player some some balance at each time slot okay so you can think of each player as having some some hash rate if you like

or some memory capacity whatever each time okay okay and then so players can send requests to the permitter oracle okay so you can think of a request as being something like a request for approval work like that okay and then the permit to Oracle will respond right uh depending on their resource balance maybe if you've got um higher hash rates you're more likely to get the cost of the proof of work that you've asked for okay so this is the very high level level description first of all so to make that a little bit more concrete I'm going to give an example of how we do it for for Bitcoin work okay okay so probably work to model that uh well suppose the request that any player P sends a bit permit to Oracle at any time clock t has to be a pair of the Form B Sigma so

here you can think of b as being some hash rate that's dedicated to this request for a proof of work and sigma is the string that we're asking for people work for so this could be like a block of transactions whatever or hash of a local transactions this R is independent of the consensus so yeah the the resource allocation function are if I didn't say it already Miriam I should have done is this is uh unknown to the protocol right so the protocol has to operate essentially for arbitrary R and unknown R although there are some small details there but yes and conversely the operation the protocol does not in turn influence script R right yeah uh Andrew

hello all right um how do you think about branding hash rate or buying it from with the cloud say again sorry what about a minor that rents the hash rate buys it from Amazon uh well yeah I guess here we're just assuming that everybody has access to a certain hash rate we're not particularly worried about uh how they're getting into the payment yep extra details that should be including the model but I'll be interested to hear it but yeah at the moment we're just assuming everybody has access to a certain hash rate at each time slot okay okay so focusing on bitcoin Okay so we've got uh we can send requests to this uh put it to Oracle for these times lot each request is a pair of the Form B

Sigma you can think of b as being the the hash rate I'm dedicating to request Sigma is the thing that I'm asking for people to work for you can make multiple requests as long as you're not reusing hash rate okay so I can make a requests b161 up to BK Sigma K okay so long as I say we don't use hash rate so interpreting the bis here is uh the hash rates devoted to each of the requests okay they don't they don't sum to more than my my total hash rate at this at this time slot okay and that's also true for Byzantine players okay so those are requests and then how does the uh meta Oracle respond okay so to integrate with the the Bitcoin difficulty adjustment algorithm we want proofs of work to have a certain quality okay so each proof of work

Oracle response is going to be a 256-bit string Tau and the quality of tau is just a number of zeros that it begins with okay then the P submits the request B Sigma at times.t okay then the permitter Oracle independently samples B and E 256-bit strings uniformly random okay responds with Tau which is the let's go back of the smallest of those and you could think that the sponsor is in some sense being sort of signed by the permitter so these proof of Works can't be faked by a players okay okay so that gives us a very simple way of modeling Bitcoin obviously we want this to work much more generally should work also for like cheers for space and so on and then you you can do these things okay I want you to emphasize this point there so the on-chain resources don't work like this in the sense the stake

you think I have may depend on the version of the blockchain you've seen okay so with the external resources I always just have I have a specific amount of hash rate at each time slots okay that's a sort of objective facts okay but with stake it's less objective subject different people have different views of the blockchain okay okay uh so that's external resources now on-chain resources uh in fact though okay so fake is one form of one chain resources uh resource there are other forms which we'll talk about later on uh for now just to keep things simple I'm just going to focus on State and we'll come to other forms later on okay so we have an initial State distribution okay okay so there's some certain uh players are allocated onto a stake at the start of the process we have transactions being issued by an

environment that's fairly standard okay and then uh we know we need some way of interpreting the transactions okay so we have what we call a stake allocation function which gives you any set of transactions determine to take that set of transactions anyway who owns Which state according to outside of transactions okay okay and then so on-chain resources uh Lake stake don't generally make much sense outside the context of blockchain protocols so we have to Define what we mean by them okay so each blockchain protocol uh specifies a confirmation rule okay it's a very simple thing the confirmation rule it's just a function that takes any set of messages including transactions and returns a subset of those messages okay so confirmation rules just takes

any set of messages Returns on subset of those and you can put in sorry many time slots if m is the set of all messages received by a player at times obsessed we could see the p is going to regard the messages and C of M has confirmed okay so it takes all the messages it's received and some of them are confirmed and some aren't so generally here I'm allowing that you can you can you can confirm messages that aren't transactions okay I don't know anything else here is quite standard right so we specify standard Notions of liveness and consistency okay so life is as I expect people to wear right like this basically just means the transactions that don't conflict others eventually become confirmed uh and consistency says to honest players uh eventually agree on the set of confirmed transactions okay and we don't actually have to set

this up so we have a total ordering on transactions here you can you can do a it's a strictly easier task of implementing a payment system you can you can consider that as well okay it's a good uh one more uh brief definition before we start considering the hierarchy okay so we need to Define what we mean by a row bounded bursary okay what do we mean by a small small adversary so most of this definition is fairly obvious okay so we're going to say first of all let's talk about executions we'll say an execution of the protocol is row bounded for some row and zero one so row might be a third or whatever if the first of all we're going to talk about external resources here okay so first of all resource allocations corresponding to external resources each allocate the adversary at most a row

fraction of the total of the external resources at each time slot okay so we're going to assume the adversary always owns like less than a half of the the hash rate or whatever yeah it's not quite straightforward and then for stake we make the following assumption so among active players Byzantine players never control more than a row fraction of the stake okay so that might something that's a informal version some more there's a more formal version uh stated uh there so formerly for any honest player P A times not t if TR is a set of transactions that are confirmed for p at that time.t execution that are most a row fraction the stake allocated players active at T by that set of transactions is allocated by xan team players

okay so this might seem like quite a sort of a natural assumption basically saying okay look at this try to confirmed transactions that was always allocate the adversity at most a third of the stake or whatever okay okay in some sense that's a it's a slightly uh odd definition though because it kind of in some sense it's it's as much a condition on the protocol as it is on the environment right why is it reasonable to assume for arbitrary protocols that this is the case you might have odd protocols like purposely try to confirm Byzantine transactions or something right okay so what we really like is a condition on the in the environment okay but for now we're gonna this is a fairly standard sense of notion that people use so we're going to use this notion and then we're going to come back to H1 and consider

like why maybe it's interesting and pop a bat in various ways okay so for now though we're just assuming any sort of confirmed transactions allocates diversary and most of Road facts in the statement at least most of the third of the state whatever okay so that was execution so when we when we say the adversaries rebounded we mean that we restrict attention to row banded executions okay and then one more easy definition we say a protocol is very resilient when it can deal with roadbounded adversaries okay yeah it's very resilience just means you can deal with rebounded adversities okay so that's the the uh those definitions now we can start uh defining the hierarchy and see what happens at

different levels of the hierarchy okay okay so let's define the fully permissionless setting first now like with resource restrictions right so the fully permission setting with resource restrictions is the same as the the setting we defined earlier on where we have these three new complexities like pairs can be active or inactive of an unknown player set and we also have to deal with civil attacks okay but now we have the following changes okay so now protocols can make use of a finite set of external resources I can run relative to an environment that sends transactions okay so now we have resources around uh and you're now also allowed to assume that the adversary is rebounded okay for some Row in zero one okay so hopefully that seems It's a reasonably natural okay and then uh our first main theorem

here is it's the one that we we saw earlier on but now I'm going to take it slightly more precisely so we consider the fully permissionless and authenticated setting okay so authentic authenticated just means we have signature schemes with no pki okay so considered the fully permissionless and authenticator setting with synchronous communication suppose the atmosphere is rebounded for some row greater than zero well then every deterministic protocol for solving by his anti agreement has infinite executions in which honest players never terminate okay so basically deterministic protocols won't work here okay okay so I haven't formally defined by his answering agreement if you know that Byzantine we can problem thank good otherwise just replace Byzantine

agreement with the word consensus there okay so that's uh an impossibility result for the fully permissionless setting okay so now let's move on to the dynamically available setting okay so the next level down on a hierarchy slightly easier setting to operate in okay so so what differentiates are setting in which proof of State Protocols are required to operate from the setting in which proof of work Protocols are normally required to operate or basically the differences that we make stronger assumptions about which players should be active okay so if you think about it with the with the fully permissionless setting we kind of allow the mistake hanging around and maybe in other forms of one chain resources that we haven't talked about yet but in some sense that they're no good so far because there's no reason that anybody who has State Should Be

Active right so we can't make use of that fact okay so now we need to actually be able to use that assumption assume we need something that allows us to assume that those players who own stake are actually going to be active and running the protocol okay so well that's just a definition of the there's a rough description of the of the fully permission the setting there to come contrast with okay so here's the definition of the dynamically available setting okay so in the in the da setting we suppose that if TR it's a set of transactions confirmed for some honest player sometimes.t then at least one honest player allocated non-zero stake by that type of transactions is active you look at the players who have stake at least some of the honest players are turning up okay then they'll normally would also add in some surround to Route

ru-bounded assumption right so if your student adversity is rebounded then we also have the most a row fraction of active players Byzantine okay so it's very simple yeah okay so that's the definition of The Da setting uh here immediately is an impossibility result for the the a setting so dynamically available protocols can't solve probabilistic presenting agreement or consensus in the partial Symphony model okay so again as I said before like the partial surgery model is a very standards of uh model in which like most of the standard permission protocols operate the dynamically available protocols can't solve consensus like even probabilistically in that setting and again the way the hierarchy works

the fact this is a impossible result for the da setting means it's also true of the fully permissionless setting okay so uh we also we saw before that fully permissionless protocols can't be deterministic okay we can conjecture the dynamically available code of those can be but haven't been a proof of that down yet okay so that's the da setting now let's move on to there the next one that the quality permissionless setting okay uh so again I said the stake there are other forms of one chain resources okay and we want to define the the quality permission of setting for on chain resources more generally but first of all I'm going to take us I'm going to State a simplified version just for stake and then I'll talk about other forms of one chain resource and then we'll Define the sort of General version okay so this is the simplified version

just for stake so in the quality permission setting we suppose that if TR it's a set of transactions confirmed for some honest player at some time slot and all honest players are getting non-zero State what they said transactions are active okay so for the for the da setting you look at the uh you're you're expecting that at least some of the honest players are turning up and participating but in the quality permissionless setting required that they all do you can if you know the way most of these these protocols like in a pbst tender minutes Etc operate or even proof of state implementations of them they require this sort of this sort of condition to operate okay otherwise you lose liveness okay so that's a simple version just for Stakes so now let's talk about uh other forms of Unchained resource okay so as I

said the stake is one from one chain resource uh there are others so introduce that idea it's useful to talk about these proof of work Protocols of hybrid Salida and bizcoin okay so these are some three slightly different protocols but at high level they all operate in a similar sort of way here's the basic idea is the proof of work is used to select the rolling sequence of committees once a committee is selected right imagine you're a certain point you've got a certain version of the blockchain we've got a certain committee who's now like the committee at this point in time okay let's fix for now once the committee is selected they just carry out like a standard permission protocol in order to implement the next consensus decision okay they're just carrying out a standard permission protocol

that consensus decision has to include like the next sequence of transactions to be committed to the blockchain right as well as determining which players are provided sufficient proof of work in the meantime for inclusion in the next committee okay it's about one version of the committee they run a standard permission protocol that determine Escape what's the next sequence of transactions Who provided enough proof of work to be the next committee and now we've got our next committee and they then carry out the uh the next consensus decision and so on yeah so in that context I'm gonna say the on chain record that P is a member of the present committee should be seen as long chain resource right because that that resource allows P allows that player to participate in the in the protocol it could potentially earn rewards could be transferable and so on now as well that these protocols

operate in some version of uh like the quality permission to be previously justifying for stake basically right because all honest players with on-chain resources are required to be active otherwise the protocol will stall right because basically the the players in the committee are going to carry out a standard permission protocol and the way those protocols work is you require all honest players to be active otherwise they don't have liveness okay so those those protocols operate in at least some version of the the QP setting okay so to define a general version of the quality permission setting we're going to allow protocols to Define arbitrary on-chain resources so that's quite simple we could say so a protocol defined resource is just a function that takes any set of messages and allocates each player some some balance

and that's all that says there okay just takes any any set of messages and allocates each player a particular balance so those are protocol Define resources and buy an Unchained resource we mean resources either stake or protocol defined so then yeah so the the general version of the QP setting I'm studying it insteading it slightly informally here but it's easy to make four more so political inequality permissionless heading Protocols are allowed to specify a set of on-chain resources S1 start to s k star and any one of these could be stake or maybe none of a mistake or whatever by definition an execution of the protocol is consistent with the Quasi permission setting everyone is players are active whenever they own on-chain resources okay so then we have uh immediately to compare we have the

settings we have a nice positive result for the QP setting so for row less than a third there exists row resilient and deterministic proof of State protocols the live and consistent in the partial Symphony model okay so that immediately separates what's possible in the QP and the da settings and in the solid permission list as well good also it's interesting another thing that's what separates or problems what's possible in different settings is accountability so I'm not going to go into accountability in any detail but people are probably some awareness and the basic idea is that a protocol is accountable if uh it has this kind of property that ethereum has if there is a consistency violation then the protocol produces proof of guilt for a significant fraction of the parties yeah okay so

there's there so protocols operating the QP setting can be accountable whereas Nazareth and others have shown that uh protocols operating in the dynamically available setting can't be accountable other interesting separation okay so to finish then I just want to sort of re-examine a little bit the assumptions that we made here going back to the sort of comment that I made earlier on okay so in order to prove this theorem here we've assumed I can talk about that we've assumed that the adversity was rebounded right and as I said before there's some some sort of aspects that definition that might seem a little bit uh suspect actually only can we rewind a second I mean this theorem resembles statements that are made for

very major layer one blockchain protocols that people are aware of so it's maybe just worth saying a little bit about it okay so yeah so this this advice is generally understood as people get people in communities will think of this as being true if you actually look for a formal proof of it there isn't any existence at least none that we can find part of writing one up Okay so we've written up a formal proof of this fact and it's uh surprisingly much more complicated than you might think it is okay so moving from The Case of the permission protocols to the proof of stake implementation has a lot of difficulty like a lot of complexities um so yeah I encourage you to check out the proof uh but it's quite it's quite a complicated so for example even though the protocol is based on tender mints

somehow the liveness and consistency for the proof of stake extension seems to get quite a bit more complex quite a bit more yeah dealing with the the changing player sets is complicated in ways that may not be obvious to him for this theorem uh yeah we have made this assumption that the adversar is rebounded okay so when I remind ourselves what that definition was so first of all there were sort of two parts to that definition part of it was kind of entirely natural right first of all for external resources it's fairly straightforward because okay obviously the adversary will earn less than a third of the hash rate or whatever at each time stop for steak it was slightly a little bit more uh uh interesting so among for steak we basically assumed that whenever you look at any confirmed set of

transactions that confirms set of transactions always allocates adversary and most of row fraction of the stake and the basic objection is well okay so why is it reasonable to assume that's the case right that seems as much as an assumption that on the protocol as it is on the execution issuing the instructions okay so let's dig down on that a little bit and to do that I want to start off by thinking about whether or not uh proof of work protocols can be live and consistent in the partial Symphony model here that might seem like a slight odd thing to do I think it shed some light okay so in particular I want to think about what goes wrong with the Bitcoin okay uh and so I describe Bitcoin at a high level before once again just to remind you what goes wrong with Bitcoin if we try

and operate it in the partial assembly model it's a remote to remind you how the protocol works so we start off with a Genesis block that specifies an initial committee now okay so that's not normal for Google work protocols okay that's what we have at proof of State protocol that's right we have initial distribution now let's imagine we have an initial distribution okay even though we're working the people work protocol okay and let's suppose that once a committee is selected they then just carry out this permission protocol I'm just reminding you how things work before so this a few minutes ago right so once the committee is selected they carry out permission protocol to execute the next consensus decision okay that consensus decision includes like the next sequence of transactions to be committed to blockchain as well as determining which players are provided

sufficient with work in the meantime for inclusion in the next committee so why doesn't that work if we try and uh operate it in the partial Century model there's no problem with the permission protocol right the permission protocols can definitely operate in partial security right they can be designed so they work perfectly well they're live and consistent in partial synchrony so we start off with our committee we're doing a permission protocol which we know will function then we have our next committee and then it's going to do the same again so what's the problem so the problem is that the proof of work produced by Honest players might not make its work make its way to the committee right so the committee that is sitting there executing the next consensus decision they're looking to see so what proof of work has come in but during a network partition we might

only hear people were provided by the presenting players yeah so during a network partition we might end up with the next committee being entirely Byzantine right because we've already heard people work from the Byzantium players so the next question is okay can something similar to that happen with proof of stake do you need Byzantine players can't you just have a classic Network partition and two parts of the network that just work in parallel well the the problem here is that we we're going to end up with the Byzantine majority right if there are nobody's anti-in players and it's going to be fine the problem is if we don't hear about proof of work from the honest players so we get a the new committee is formed by Versant and then it buys anti-players that carried have taken

over the network I I'm I'm thinking of a an impossibility without any anybody being Byzantine just do a partition of the network well those two different committees that form and make progress without hearing of each other uh yeah okay may I I have to think about it okay okay the main point is it doesn't work requires and team players or not I think I think they do but I'd have to think of the details okay okay so proof of work it won't work let's look at uh proof of stake we're asking can some something similar happen with proof of stake okay and the answer is yes okay so why is that okay so I want you to consider a uh

example which are called the payment Circle example okay so here we have a set of n players we can imagine that P0 which is one of the players that Byzantine let's call that P0 okay everybody else is honest and each player has one unit of stake and we could imagine that we'll have n uh consecutive rounds in which payments we made okay so the intersective rounds each player Pi all three always is a a new transfer of a single unit stake to the the next player in the circle if you like okay so in each round of transactions it's a player player each player transfers one other state to the next so each round of transactions changes nothing right Okay so we've got n rounds of transactions there are n transactions in each round so we have a total of N squared transactions there

okay obviously each round of transactions here uh leaves things unchanged so at the end of the this the story right when we look at the total set of all T transactions the Byzantium player P0 still only has one over n at the total stage yeah and it only has one one unit at stake okay now what we're going to do is to choose a particularly problematic subset of that set of transactions okay so now I'm going to choose T Prime a subset of T to contain the first I transactions issued by player Pi okay so if you think about things let's be precise let's imagine we're in the utxo model so that that will then be a valid set of transactions okay if you think that through that we end up now with P0 and uh P zero

the Byzantine player only all the stake okay so we have a lot of transactions T which allocates that the Byzantine player one over n of the stake we pull out the right subset and we're going to allocate them as anti-bear all the stake okay so the same sort of thing happens in a proof of State protocol or can happen as in the proof of work example I gave before right we're doing a network partition we've got a certain set of confirmed transactions the the set of all transactions out there might allocate the Byzantium players a small proportion of the stake if we see the the wrong uh subset of their transactions then we'll end up confirming dishonest majorities okay so this theorem which I'm stating just in rough form uh says a sort of uh for something more precise version of

that if we drop the assumption that the adversary is rebounded and assume instead only uh instead of all transactions issued by the environment allocates the burst rate most of row facts in the stake it says we just look at all the transactions issued by the environment instead yeah yeah okay then proof of State protocols can't be very resilient in the partial security model for any row greater than zero okay so that sounds bad but then we can save it uh so basically what was the issue here the issue was that we had these long nested sequences of transactions and the honest players were issuing transactions that relied on others before those previous transactions are confirmed okay so if we restrict to a scenario where honest players don't do that then

we can we can save things so we can have proof of State protocols that work in the parcels have been model okay so this thoughts being an issue in the utxo model at least the UTSA model if no honest player issues any transaction TR until all transactions require the TR to be valid are already confirmed okay so I'll stop there thanks for listening here I'd like to ask about the conjecture regarding the that dynamically available protocols could be deterministic I was I was inclining more towards the other conjecture that they cannot be deterministic I mean there are dynamically available protocols um that are deterministic except the leader selection part but the leader selection part still requires a vrf in those cases so

I feel like the arguments that you could you use for the fully permissions one can apply almost like extending the proof to the dynamically available setting I don't see how to do and okay my answer there which is not entirely strong is that I have in mind certain Protocols are actually leaderless Protocols of dag-based protocols which I think will work but I haven't written down the proof and so if I tried right now of course you can always come across difficulties right but yeah I have in mind protocols a protocol that I'm what's your favorite open question

ah gosh favorite open question uh well okay that one's okay I guess that would uh give us a nice formal separation between the FB setting and the da setting uh yes are they maybe questions around accountability and I are there proof of work protocols can become accountable if you work in the GP settings and that kind of thing so you talked about how accountability is not possible in the da setting but it is possible in the classical promotionless yeah have you like thought about other properties that are possible in one setting but not in another setting proof well it gave you a bunch of different examples there right so we had we had three at least there so we had deterministic you can't be deterministic in the in the FB setting

and you can and the quality permission setting maybe in the da setting also you can you can be live because it's an impartial synchron in the QP setting and not in the da setting uh I said accountability is a third one there but yeah it'd be interesting to extend their list yeah I'm I mean I guess the the general conjecture is a lot of the time indeed impossibility and possibility results are driven as much by the sort of setting you're operating in uh as well whether you're on like a proof of work or a proof of State protocol for example yeah um looks like responsiveness would be one of those properties you think that's yeah so expand on that because like the quasi-permancial response because they can operate under partial synchrony they could perhaps all be responsive whereas the dynamically available ones require

synchrony so I would doubt if they could be responsive I think you might be right about that yeah yes being responsive uh in synchronous and fairly similar to just be Library consistent in partial synchrony so I think that's a good conjecture yes okay let's look at that later this week then any other questions what are your thoughts on uh I mean you know so sort of there's this flp analogy right for the fully permissionless impossible to result in synchrony versus sort of flp asynchronous permissions is what are your thoughts on like any possible connection between the two models uh I guess okay a basic observation there is that

there is a big similarity to between the proofs when both proofs have this basic say the same basic performance of a bivalency proof where you start off in a bay of wavel in position and you extend one at a time uh so there's I guess there's obviously some sort of connection there but okay I guess yes we need to think deeper about it whether that analogy goes deeper I don't know I don't know yeah thank you [Applause]