The Blocklace: A Partially-Ordered Generalization of the Blockchain | a16z crypto research talks

Transcript

very pleased to introduce the Richard hero from the Houston professor at the lights on Institute I'm definitely one of the more interesting people I've ever met in computer science some of you have already had a chance to talk to them I hope the rest of you do too is a lot there's a lot of people talk to it's done many many different things over his career currently uh he's actually quite interested in web 3 and specifically today I'll talk about a new consensus protocol I believe the black place oh thank you thanks Tim for inviting me I already had some great discussions in the morning so I'm looking forward to continuing them today and if you have any questions during the talk feel free to ask them during the talk no need to

wait till the end so this way I understand better what what you don't understand about what I'm talking about so um the talk is based on on three papers all are available online one is a foundational computer science paper but the appendix actually describes the block list which is the data type uh I'm going to talk about as the basis for the protocol stack uh cordial miners is a joint paper with the ditkedar and R from the technion and that's the new consensus protocol um that I'm also going to talk about and third paper is a sovereign cryptocurrencies and I've already spoke to a couple of you in the morning about

them I will mention them that's not the main topic of the talk but I'll just mention them because they're relevant for the value of the stack as a whole and uh if that question time for questions I'll be happy to answer answer at the end but all are available online I will share the the PDF with the links so you can you can access them um if if if there's interest so I was thinking whether I should call it the Holy Trinity or the Unholy Trinity I said well this will offend these people this will be certain so I said it's just the Trinity the Trinity of distributed computing yeah okay dissemination is the first task uh let others know what they say or no

that's dissemination uh equivalent exclusion resolve equations in what I say double spending so if I tell uh Team One Thing uh and I tell Andy something else and they're inconsistent then eventually we should figure this out you know you should figure out that I'm telling different things to different people or double spending your money even worse so that's another task and the third task is ordering uh so you should order everything everyone said and this is necessary for example um it turns out it is not necessary for financial systems that you can do uh asset transfer networks just with

equivocation exclusion without ordering but if you want to do uh smart contracts where everyone agrees on what's going on and what what what instructions or or actions are being taken in what order then you need full ordering consensus so these are the three things that that need to be achieved uh and for example blockchain consensus achieves ordering and they should be achieved in the face of uh faulty Byzantine malicious agents or minors or or adversaries and their various Notions and definitions but but it gets interesting or difficult uh uh only when when they're fully or malicious agents these three uh tasks

are solved by for example Nakamoto consensus they're part of the protocol includes the dissemination the protocol includes ordering and it turns out that once we have ordering it's very easy to do equivocation exclusion you just all the transactions are ordered and if there's an equivocation or double spend you just ignore the second one and that's it so ordering social equation exclusion but as I mentioned one fundamental result in in in distributed computing is that you can resolve equifications without ordering that's why it's a separate separate result separate point uh so what's wrong with the existing blockchain consensus protocols such as Nakamoto consensus and uh other similar protocols first of all they try to solve

all three problems dissemination equivocation inclusion ordering jointly so it's a black box monolithic protocol and dug based protocols which I'll mention later are excluded from this the second is I contend that they're not scalable for two reasons one they use the data structure that's replicated so when they say they're distributed compute the distributed algorithms I think it's a bit of a misnomer they're not distributed protocols or algorithms are replicated so it's you don't distribute a data structure different pieces of different people you replicate a single Central data structure among multiple uh agents miners what have you so these are replicated protocols not distributed protocols or or decentralized protocols

and the third and that's specifically for blockchain protocols that are extendable at this single point at the tip so everyone is fighting who is gonna add in the next block to the tip so the that's the reason why they're not scalable and the third is that they are not affordable it requires high performance computers and networks and part of what I'm trying to achieve is to be able to run things on on on on personal uh smartphones so our goal is a smartphone ready uh protocol stack and that um first of all it's modular so it solved its problem dissemination equivocation

exclusion and ordering separately and I will show the different applications need different parts of the stack so they they don't need to pay the full price of ordering if all they need to do all they need is dissemination or they don't need to pay the full price of ordering if all they need is equivocation exclusion and I'll talk about that and scalables it uses data structures replicated locally and extendable independently and the third is Affordable so it can run on on smartphones so that's that's the overall goal and this is this goal is part of a broader Vision or or goal towards uh digital democracy Grassroots

communities Grassroots economy but but for the purpose of this talk this is a sufficient uh sufficient description of the goal uh and this is more or less a a look at the solution uh the the direction of the solution so first of all it's a protocol stack so you have layers in the stack and ultimately you need blockchain consensus or something similar to blockchain blockchain consensus but there are lower layers below that there is consensus free so you don't need consensus for that reliable broadcast typically you need a super majority two-thirds majority assuming you have less than one-third faulty agents and you can do asset transfer networks or

nft trade networks using reliable broadcast alone and uh what this part is novel is is the the suggestion that we actually want even simpler weaker protocols uh which I call Grassroots which only do dissemination or leader-based equation exclusion so you don't need Super majority but it turns out that you can do a vacation exclusion even with without the super majority and I'll uh or or to two-thirds majority and I'll talk about that and these are matching applications so if all you want is a is a social network where people know what other people are talking about locally through friends Etc think about Twitter but local local feeds then it's enough to have dissemination local

dissemination I I follow my friends my friends feeds and if if a friend follows a friend and they can see also the friends of the friends but but it's it's local dissemination and I have a notion of sovereign cryptocurrencies which actually don't even need reliable broadcast they can use leader based equation exclusion and then everything else that you talk about cryptocurrency smart contracts Dows Etc need the full the full scale blockchain consensus so let's let's uh uh so how how are we going to how am I proposed to address this it turns out that we can use a single data structure I call the blocklays uh but it's not that new I mean other people propose

similar data structures in the past so I'm the name is new but the content has been uh proposed in various ways in the past but not not the whole kind of vision but but just the data structure uh it's a it's the best thing to see the best way to view it is just a partially ordered realization of the blockchain and I'll I'm going to show you in this talk that you can do all three things with the block listing for publication uh okay there are various different definitions but let me give you uh one which is Comfort which fits what what we're doing that

if you equivalate then we approve at most one of the two things so we can if if you if you try to do two double spend then either this one succeed or this one succeed or none will succeed so it's okay it's okay in case you double spend that both of them will not succeed you have the freedom to reject both or the the result will be that both fail in blockchain this doesn't happen if you double spend the first one always succeeds and the second one always doesn't succeed so this is very it's your most strict implementation but the more general definition is that you cannot double spend so if you try to double spend you either succeed in spending once or once or never but you cannot stop you cannot not both will succeed so that's that's the formal

definition well you're already talking about him you're already talking about implementation more abstractly mathematically speaking the outcome of a double spend should be that at most one of the spending attempts will be successful that's at most one but not not exactly one at most one that's that's that's a different that's the abstract definition that's a convocation exclusion means you cannot equivocate if you try to equivocate you fail either because the other the other thing is rejected or both are rejected that's the that's the abstract difference that's the abstract requirement of equivocation exclusion is that okay

okay so once we agree that this is absolute definition although this is not the topic the this the main topic we can once we talk about Sovereign cryptocurrencies I can show you how you can achieve equivocation exclusion without consensus without super majority simply by The Sovereign deciding uh which transaction to approve I'll if there's time I'll talk about it if not after the talk but but it's it you have a point it's just it's already a mechanism a a protocol or a mechanism to realize what you're describing and I I'm at this level I'm just talking about the more abstract requirement that what you're trying to do what

you're the pro the problem you're proposing cannot happen how it cannot happen is already implementation details okay so uh let's start with a block okay so this is the block has a payload and a cryptographic collision for your cryptographic hash pointer uh hash pointer is it's not really a pointer it's just a hash value of another block and collision free it's our assumption or belief We Believe it will never have a collision okay very very very very very small probability it'll have a collision so we believe and cryptographic is important because it means you cannot uh compute x given the hash value which means you cannot effectively create Cycles even the

adversary even the malicious agent cannot create Loops using cryptographic hash pointers because because you cannot guess how the reverse pointer will be without the value of the pointer anyway cannot happen that's that's a block okay and blockchain is just a list of logs each one point in the previous one and this one has zero hash pointer so it has zero or one hash pointers this is called the Genesis block and you can look at this elephant from many different directions I know you've been looking at this elephant you know all the time but for me these are the three important properties of a blockchain first of all is tamper proof so nobody can modify anything without people who look at it seeing that it's

been tampered with another important one which is less mentioned but it's very important it's not reputable if there is something there signed by a person or an organization they cannot deny that they've done this you cannot deny creating this block you cannot deny creating a signed transaction inside the block totally ordered that's that's a blockchain okay any questions about what is a blockchain okay now all I want to do is generalize the block so you can have several pointers zero or more pointers everything else Remains the Same and a block list is just a bunch of blocks that's all that's a block list

okay so it's tamper-proof not reputable and instead of totally ordered specially about it that's all that's a block list uh and it's a data structure but it induces a mathematical entity called the directed acyclic graph so it's a bit more abstract than this directed circular graph is a bunch of entities edges directed edges they do not create cycles and remember you cannot create Cycles because these are cryptographic Arch pointers so a block list induces a dag so when people say well it's a dag it's not a dag it's a data structure that induces the Dag okay so it's a Concrete data structure okay so any questions what is a block list important thing is everything here is signed cryptographically signed so we

assume that the agents miners whoever have um cryptographic ever um key Pairs and they can sign so everything is signed and actually you can see who signed what so these are in another requirements which we'll see from the protocols is that at least locally every agent order totally orders their own block so when I create a new block it must point to the previous box so the Red Blocks are totally ordered the green blocks are totally ordered the the blue blocks are totally ordered but there is also a partial order among them okay so that's if the miners are good you know they can be bad but if they're good that's how they should behave so let's look at the Trinity of distributed computing and see how we can

use the block list to achieve them let's start with dissemination and for dissemination uh we need to let others know what I say or no so how can I know that I know something that the others do not know okay uh the answer is the block list in a block list a block reveals what its creator knows why because if every time I create a block I make sure that it points to everything I already have then people look at the Block see what I know what I point is what I know in the transitive closure of the pointers the the the subgraph that is pointed by my most recent block is what I know so if I send you a block you look at it

and you see what I know and if you know something I don't know and you're a nice person nice person or a kind Miner a cordial Miner you'll say ah I know something that you don't know here it is and you send it back to me okay so dissemination can be achieved in a very natural way by the block list but these two rules when I send the block it reveals everything I know simply by having pointers to all the most recent blocks of every other Miner or every other agent or whatever and when I receive something from someone and I know something that he doesn't know I tell him that's that's all that's blockless based dissemination now there is a huge range of trade-offs in doing this how quickly you do it you'd always do it you wait a

little do you tell him everything even though he might know it in a micro second later or do you tell him only things that happened two three rounds ago there's a there's huge trade-off now there's there's a this is a a new a new approach so it has not been well studied but uh the problem so-called reliable broadcast which is an algorithm below the hierarchy of consensus so it's a building block that people use for I'll mentioned people use it for consensus reliable broadcast is a is a well-studied problem which has well-known well-styled extreme I mean dozens and dozens of papers on reliable broadcast and there is a well-known trade-off there between communication complexity and latency uh and this

essentially the same trade-off between communication complexity and latency applies also to block list based dissemination you can be very eager telling everybody everything all the time what you know and they don't know and then you have very low latency and high communication complexity or you can be more modest and say well let's wait a little let's do it probabilistically let's do this ah let's divide the work Let's do sharding let's all sorts of tricks and then you decrease communication complexity at the expense of increasing latency so I'm not getting I will I will mention specifically How We Do The Cordial minus protocol which is an extreme end of the spectrum we just do very uh low latency higher communication throughput but in

general every idea you have heard about on this trade-off in reliable broadcast or similar protocols can be applied here to this dissemination so that's how blockless based dissemination is achieved um I will get there for now just think about the social network not even not even consensus I when I say something think about gossip just Social Network I say things you say things and if you're my friend I want you to know everything I know that you haven't haven't known so every block is just an utterance in this

social just a think about it as a post in my Facebook page or tweet in my Twitter I think that at that level that's all later specific protocols will do when we have a blockchain consensus then it will be very specific but for now just think about the most relaxed you know setup I got a question also just to make sure I'm following say if we took just practically like Bitcoin and ethereum and say we took two like L1 chains and then forced them to say every day one of the Bitcoin blocks has the point of both the Bitcoin and ethereum block and vice versa so that would be a lot of us yes yes okay so it's just what I said that this this guy knows all this

okay so when it when it receives the uh when say this block this guy receives this block he knows that he doesn't know this and doesn't know that and you can tell him that okay uh yeah and this guy knows only that Okay so the same thing holds okay I mentioned trade-off uh between message complexity and latency and all the possible optimizations send once so you maintain a communication history so if I told you something or you told me that you know something I will not say it again uh send backlog only in response delay randomize Erasure codes standard techniques uh okay

so what can we do with dissemination as I said serverless social network as a foundation think about Twitter without a server I have my feed team has his feed everybody has their own feed if I want to follow team he will tell me now we are friends he will notify me if if I want to follow Andy but but I'm not his friend and him is his friend then I will ask team to forward to me the blocks that and the issues and if we're friends he will do that that's how it will it can work intuitively of course all this can be formalized but for for social network this relaxing we don't have to resolve double spans if I tell different people different things and they will just think I'm I'm a jerk

and ignore me so it's it's all relaxed you know okay so that's that's that um equivocation exclusion how can we do equivocation exclusion so let's let's first agree what is equifocation here this is an equivalation the blue guy the green guy the green gray created two blocks that don't refer to each other okay so he he told the blue the the red guy this blog and the blue guy this block this block so that's an equivocation that's a fault and it can only be done maliciously it's not a accidental fault you kill because the the the the the green guy maliciously created two blocks knowing that they don't refer to each other okay

so it's a Byzantine malicious fault uh and as I said the the uh the blue guy knows this one the red guy knows this one that's that's it and uh but let's say there's a purple guy that happens to know both then he sees that this is equivocation okay so um we have a notion that somehow I've I haven't been speaking about this a lot but to the people I spoke with is utterly confusing I don't know why it's so simple and but people even make collaborators think it's confusing so I

don't know notion of approval approval is a relationship between blocks and basically you want to approve a block if by doing so you don't approve rectification okay that's intuitive route you want the approval approval is relationship that must solve this problem you never approve a nucleation okay formally a Block B approves a Block B Prime if it observes B Prime and does not observe an equivocation of B Prime so if it even if there is an equivocation if and I observe meaning in in the closure of the in the transitive closure of the pointers okay so every block has a the blocks it observes through the transitive closure of the pointers okay so if I observe a block and I do not observe an equifocation I approve the

block if I observe an application I don't I prove neither okay that's very simple if I see that someone is bad created the equivocation I approve I don't approve I prove neither this one nor that one but if I see only one I approve it so following this definition the red guy approves this block even though they are provocating because it doesn't see this one the blue guy approves this block because he sees this block but doesn't see this block the purple guy approves neither because it sees an equivocation okay now it's a property of a block not a person the block does not approve this this block approves this this block approves this okay that's the definition of convocation I don't know simple complicated confusing that's the

definition okay the last Green Block approves both right this one yeah it should approve yes yes this one not approves this one does not approve this one does not approve this does not approve this no but it approves the Blue Block which approves the Eco location okay formally a block a Block B approves book right if it observes B Prime and does not observe a network question this one observes this and observes this therefore it does not approve does not approve this does not approve this also this one okay it does not approve it does not so as I

said it's a property of a block not a person this block approves this this block by the same green person does not approve it so from the perspective of the green person he said okay this is fine but then he created another block which saw the configuration ah I made a mistake or I approved it but now I do not approve it anymore whatever so what does it mean to point to blocks but not approve approval is a purely mathematical Construction it's a property of a graph a property of a block integral a property of two blocks in a graph that's all think about it as an extremely abstract mathematical property relationship between two blocks the relationship holds if these blocks sees this block but doesn't see any clarification of it that's all

so it holds between this and this holds between this and this sorry holds between this and this holds between this and this does not hold between this and this because it does see this okay it's just a binary a binary relation on dogs that's it okay formally speaking okay now the important thing about it like the magic is that an agent can approve an equivocation only by being an equivocator himself okay why let's say uh okay let's say the blue guy wants to approve both both of them how can he do that he will create one block that sees the only this and he create another block that says only this

but this don't block block don't see each other so the he is the in order to approve the green equivocation the blue guy had to provocate himself or herself OK why because if the blue guy adds this pointer suddenly this block sees both this and this so it doesn't approve them okay so to approve it so if there is someone who is faulty but malicious and you want to support him the only way you can support him is by being malicious yourself so if there is a bound on how many malicious miners are there if there is a minority of a super minority of malicious less than one-third you cannot have super majority

approval for equivocations that's all because if you're ever bound on the bad guys you cannot have a super majority of the good guys that that approve an equivocation so that's that's really the the key thing that if you want to approve an equifocation you need to communicate yourself if there's if the number of people who are willing to be faulty or faulty or Byzantine is bounded You by less by minorities less than one-third when I say super minority it's less than one third Super majority greater than two-thirds think about this way you cannot have a super majority approval for equivocations if you have a super minority of of faulty miners let's I'll go back to that so this shows that if

um you use super majority for approving transactions then um you cannot have a convocations and can have asset transfers by simply by super majority okay so if if you want to if you want to see is this transfer good is this is there a double spend on this nft or coin or something it's enough to have a super majority approval by this definition of the block list and Implement a trade Network okay that's that's that's that's the conclusion of the fact that to approve an equivocation you need to be an equivocator and you need if there are super minority uh if

there's only a super minority of faulty agents you can never have a super majority approval for a revocation therefore if there is a transaction a super majority approval it means that it's okay you can trust it you will not never have super majority approval for equivocations okay so the correct to say that the safety property again assuming super majority honest safety properties you will never have two blocks confirmed from United States or the other yes yes by the same agent because it's it because it's it's a it's a it's a dag it's a block list so it's still not totally ordered but every agent has to

order their own blocks so if an agent equivalates you will never approve the agent's equivocation it's it's just per agent per Miner lioness is a straightforward uh no no nothing straightforward okay yes just to confirm so say that um there is some transaction that is initially approved in some plot plays and that later I create a blog with an equivocation and then I broadcast that block and other people become observed that equilocation that after they observe that equivocation in later blocks that they produce the so what will happen

there was a super majority of agents that approved one of the okay this is precise this is precisely the problem that this needs to address so if if I issue the block and super majority saw it and approved it and I later issued a conflicting transaction this transaction was approved by super majority it's final the other transaction will never get a super majority because no supermajority will will uh will approve it so so it's not that's why when there is an equivocation at most one will be approved it's not not I don't require that both will be rejected at most one will be approved so specifically if there is a huge delay between the first and the second

typically the first one will be approved and the second note so how do you or what are you asking the block creators to do that maintains that so I follow that super majority may be almost entire network observes and approves the first one after that's observed and approved after like way later there's a block that's in equivocation and then are the minor the block creators are supposed to never observe this other block I I'm sorry but I'm still trading in a very abstract domain still I'm not I'm I'm not yet talking about specific protocols and just at the abstract setup I'm talking about the mathematical properties of these data structures the mathematical

property is it within this data structure you cannot find two two super majorities of blocks by super majorities of the miners that approve an equivocation that's all I'm saying within this data type if if the if this data structure could be infinite think about it even infinite data structure it's Infinite Run if uh there there there's a super majority of honest miners there will never be a super majority approval of an equivocation that's all I'm saying it's a very abstract statement about an infinite data structure if you will okay so I sort of this is the first time I'm giving my talk so there's still some glitches I'm sorry so I I sort of ran ahead of myself and spoke already about this but really

I wanted to mention also this so this even doesn't this this even doesn't need the uh super majority Sovereign cryptocurrencies don't even need Super majority okay just take it on faith uh and uh let me just it's one of the papers so you can look at it and uh it's it's a whole new topic it's a whole topic which reach reaches it is Rich and interesting and I will not talk about it because there's no time if there's time I'll get back to the to the question so the answers but you see it's here it doesn't even need Super majority and that's the whole notion of Grassroots which means that communities construct independently you don't need a count of everybody involved it's all local but

I wonder if it's just helpful to have a reference naive implementation in mind so like let's like ignoring efficiency all that kind of stuff you just think about it like every time somebody creates a block if you're honest then you're actually just gonna like it's so you basically look at all the other blocks that your new block improves you just like broadcast signatures to like everybody nothing like that all the protocols are based on the fact that people cooperatively create a block list and eventually everybody sees everything and everybody computes properties locally from the block list that's it that's all everybody decides everybody can look at the block list and decide what what is true what is false what is good what is bad but the whole

the only thing that's happening here and I'll fast forward to the to the protocol to the consensus protocol in in this layer the only thing that's happening is that the the miners or the people it's true both here in the in the in the uh Social Network and and also here the only thing that's happening is that people are created cooperatively this partial order and eventually everybody is expect to say that the data structure itself already encodes yes yes yes yes so you can just look at it statically yes yes so so really the the the the thrust of the protocols I'm going to talk about here is that the only thing that's happening is people are creating blocks and sending to everybody else and

then everybody receives the blocks and locally computes whatever they want that's all yeah fix the data structure you don't care the process by which it became that data structure right the votes are just fixed size the only guarantee you need is dissemination that everybody will eventually see everything that's the correct correct miners that the correct miners will eventually have the same view that every correct every block created by the correct mind will eventually be received by every correct manner that's the only thing you need everything else is people compute locally okay so um yeah that's the no super majority for for equivocations and

we are ready to to talk about ordering okay so we know how to do a convocation exclusion with the block list now about ordering and the basic problem is uh how to turn a partial order into a total order or a block list to a blockchain that's what they want to do right and there are two requirements that you want to satisfy so the outputs the the block the blockchains so every Miner sees this ocean of partial order and they want to produce a total order locally the output every minor outputs locally to its customers to its whatever to its agents or to run the to run the local uh smart contracts VM whatever a blockchain okay that's every Miner so the outputs the

blockchain is produced by every two miners are consistent so one is the prefix of the other so I may be ahead of of team or team maybe ahead of me it doesn't matter as long as the one who's behind is a prefix of the one who is ahead that's all we need so I may I may be competing blocks more slowly but if what I computed is a prefix of prefix meaning you know beginning of whatever blockchain the other guy produced then it's we're fine it's very fine question so do you mean by outputs of every two minus the ones that they approved the block that I approve or no no no no think think about it differently the problem is turning partial order into total order okay the way these algorithms work and and I'll

say it's it's not these are the existing dag algorithms work already I'll explain it in a second the way they work is my miners communicate their blogs to every other miners so every Miner accumulates the partial order locally and they may have different partial orders simply by order I may see more blocks than you did from from team and you may see more blocks from Andy because you're closer to Andy so I may be ahead in teams blocks and you're you may be heading on these blocks okay but when I compute locally the total order the blockchain from the block list whatever I compute a new compute are consistent which means the out my output will is either longer than yours and yours is a prefix of line or your output

will be longer and mine is the prefix of yours will never will never Fork that's the whole point we'll never Fork okay that's the requirement we'll never that's that's a requirement says never Fork it's not before can we recover and with this and this no we never Fork never ever ever Fork okay and liveness just means that if uh if the correct Miner created the block then eventually everyone will output this block okay these are two mathematical requirements from from such a solution okay and uh there are solutions the the first it's not the first one but the first there was one a paper like 20 20 some years ago in this direction but no one

completely figured it out it may work it may not but Doug Riders was published in policy 21 and it has a successor called bull shark which approves it and and other people are jumping on this uh Doug bandwagon because it's actually very good uh has the following ideas first of all it uses reliable broadcast for dissemination equivocation exclusion so it's a black box protocol every Miner communicates to every other mind using reliable broadcast all their blocks and when they're when this round is done every every Miner is guaranteed to have all the blocks of the correct miners you know faulty ones are not guaranteed uh either all miners agree on the same blocks or uh or the

rock is is not there and there are no equivocations okay so there's but it by magically it filters out equilocations faulty miners everything and all the correct miners have brand new Dandy blocks of all other correct of all correct miners so that's a reliable broadcast so it achieves both dissemination and equivocation explosion and their cordial in the sense every round every Miner waits for a super majority at least two-thirds of the blocks of the other miners before issuing its next block so basically the way the protocol works is all miners cooperate they produce their blocks send to all other miners wait to receive super majority of blocks from the other Miners and then issue the next block

that's all that's the protocols and ordering is achieved and that's the key trick using uh okay how can we turn it a how do you turn a partial order into total order there's a thing called topological sort topological sort takes a partial order and just stretches it until it's a total order consistent with a partial order but it has degrees of freedom you know uh and in particular me and Andy may not have exactly the same partial orders so if I stretch it this way and he stretches it that way we may be we may have a fork so but we don't want to have before so we agree on something on leader

blocks and once we grow in leader blocks we use them as anchors for the topological sort in a way that ensures the consistency or the safety of of our total orders so the one conceptual trick that is uh uh ordering consensus protocols uh dug based protocols do is they have a magic way to agree on leaders and then use these leader blocks to to do the total ordering okay that's that so that's that paper uh these two papers let me just say uh I see faces puzzled so I'm not sure exactly how whether I should say a few more words do you want me to say and you

want you want you have a question about these yeah a question about the motivation my narrow understanding is longest chain uh allows the possibility of forks right that's why it's one of the Innovations so here with not being able to have Forks okay protocol what are we obtaining okay so let me let me go back there were this problem of so-called Byzantine Atomic broadcast the Byzantine agreement on ordering uh has been worked on for 40 years and lots and lots of protocols for that and this is like the cusp of the progress in this area and there's Nakamoto consensus which is seemingly different branch

now all the money was here right so the people who did this for 40 years said hey I want to make some money too how can I make money so they said okay well you can use these protocols by converting them into permissionless and then you can make money okay so cardano and algorand and what else okay okay you're prevented do you want to say it again okay okay okay on my shoulders okay so okay how can I make money I will take these protocols and use them uh by adding a stake based sampling okay so every Miner puts um some stake and I

learned it from some lecture amazing lecturer in column in Columbia University I will not disclose I will not implicate anybody by name but that's that's what I learned in in in in the in the course I took in Colombia so um so you do stake based sampling every Miner puts some stake and then you do random selection of miners based on the stake and then you have a fixed selection of miners for a given Epoch which could take seconds or minutes or days or weeks and for this Epoch you have a fixed set of miners which can run around this protocol of these other people who hasn't made money still and want to make money with this work and that's how these are the that's how permission permissioned protocols can participate

in the permissionless cryptocurrencies arena okay so this is a long answer to your question that uh these two separate approaches to uh consensus Nakamoto consensus and the previous Byzantine Atomic broadcast permission blah blah blah and the permission can be used in the permissionless using stake based sampling and now the gates are open anybody can join and now the name of the game is who has the best protocol and we can argue what is best but presumably high throughput low latency is is a good criteria are good criteria and specifically these protocols seem to have the highest throughput and lowest latency

okay in high throughput which should be evident because there's nothing is happening except miners who create blocks and sending to other miners that's it there's no bottleneck there's no fighting there's no Forks there's no backtracking there's no uh winning it's Cooperative we all create blocks as fast as we can and we send these blocks as fast as we can to everyone else and we're just cordial we wait for super majority of blocks before sending our next block that's all that's the only thing that's happened at the communication level the computation level here's what where the magic happens everybody looks at the partial order the dag or the block list and turns this partial order into a total order by Magic consistently with everybody else

that's it so the conversion of the partial order to a total order happens locally by each Miner independently and the magic of the protocol is that they all agree on the same total order even though they're doing it independently okay and specifically how they agree because they agree on leader blocks the leader blocks and so first approximation you can think about uh deterministic or even pseudo-random selection of leader blocks for every round so there's all we all agree on the same pseudo-random function and every round we have a block which is the anchor and then we use it everything it sees we use this to do topological sort for the rest that's that's the first

good first approximation the problem is that if the adversary knows in advance what is the the uh or order of leader selection and say they want to crush this this currency because it's a bad currency and they want all these people who are trying to join the party want them to lose a lot of money then the adversary can block the leader blocks can somehow prevent the leader blocks from succeeding and that's why these protocols actually for the for the in the in the General case use shared coins for randomly retrospective run retrospective leader selection so

that even the adversary nobody knows who is the leader beforehand and only after all Communications are said and done then we retroactively select the leader using random shared random coin and then compute the partial order in this add some latency because there are some rounds that nobody knows what's going on so we are four rounds behind or five rounds behind Okay that's very intuitively what's going on but I remind you that dissemination and convocation conclusion is not done by the block list by the partial order it's done by reliable broadcast and it turns out reliable broadcast has its overhead you need two rounds or four rounds of communication depending on the trade-off between communication complexity and and uh and latency and

that's why uh in The Cordial miners protocol which was supposed to be the main topic of this talk and next 12 minutes I'll try to to explain it we use the block list for dissemination ordering an equivocation exclusion okay we don't use reliable broadcasters as a as a as a building block we just use the block list for everything and the results are accordingly so depending on the model eventual synchrony or synchrony these are different models of adversary or network so the the latency is two compared to four or five compared to eight or whatever the numbers are okay uh so it's it's a better algorithm more efficient algorithm and the reason is

that we use the block list for everything dissemination ordering location exclusion so let me explain a little bit how this happens uh equivalent dissemination is just what I said people I tell other people the blocks I know that I don't know that they know that's all and this is happening here so let me just read this in English okay so this is a code for minority so I am minor p and what I do for every other minor which is different from me and it's not an equivocator so I if I know that someone is equivalent I already ignore him you know these are bad guys that only I can exclude them and this also improves the efficiency of the algorithm Etc so if it's not an equivocator uh I send the new blog this is the new

block I've created but not just the block but the closure so everything the block sees unless I already sent it to Q so I sent to Q everything I know except things I know this Q knows already that's it that's what it says here and I add to the history of Q what Q knows at B so now Q knows skew also knows B okay that's it so that's how dissemination is achieved every Miner tells other miners the new block he knows the new block and everything that this block points to except that the other guy already knows and that guy already knows either because I send it to the other guy before or I received it uh here when I

receive from Q something I also add to the history so when I received something from Q I know that Q knows it already okay so the history is updated when I send something to people and when I receive something from people that's that's the history okay and the definition of cordial block is just that there is a super majority uh of previous blocks of the previous round so I create I wait for super majority and then create a block so that's that's the dissemination protocol block list based dissemination and now the ordering I told her there's dissemination Trinity remember dissemination ordering a convocation exclusion so now let's talk about ordering ordering there's a function which is

called Tau for I forget why and what it does it takes a block list and turns it into blockchain that's a total ordering and the key idea for the safety is monotonicity okay with respect to supersets so Tau works the the Tau the way Tau works is that if I have a if uh if I have a block lace and I apply it out to it I get a sequence is the block system increases then the sequence increases so this means that if I have a small block list and I output something when I get more things I don't need to compute Tau from the beginning I just compute the the added uh the edit uh suffix okay

and this monotonicity is really uh uh this monotonicity implies safety why because um here let's say minor one knows brockless B1 and -2 knows brockless B2 these are two sub different subsets of the global Brokers okay and he computes the Tau of B1 he computes the Tau of B2 since tau is monotonic then both Tau of B1 and Tau of B2 are prefixes of Tau of Union B1 and B2 now if two sequences are prefixes of a third sequence they must be also consistent one is the prefix of the other it's not possible the other way so the fact that these two sequences are prefix of the Union they

also means that they are consistent so this consistency and implies safety so the only thing we need to show is monotonicity of Tau and uh that's how Tau works okay it's a very simple recursive procedure and what can I say about how it works so the ignored efficiency considerations is it obvious it's some Atomic Tau should exist but if I should go lessographically first no no it's time it's very finely tied for example Tau exists because the protocol is cordial

so you have these super majorities otherwise it will not happen and it exists because you have a notion of elected leaders otherwise it will not happen and it actually works from elect from final leader to final leader I still have I I haven't showed all it's it's a very delicate construction that works only if all components are in place so for generic dads no no no no it's very specific to the to the block list the way it's created by accordion managers protocol and the idea of of final leader selection and final leaders which I have not explained exactly how they're selected okay so it's it's a very it's not so it's really not a function from in parentheses you have partial or a total it's not a functions it's a partial

count yeah it's it's it works only on on okay you agree you're right this is this is an overage this is an average it works specifically for the block letters produces by The Cordial minor protocol okay you're right it doesn't exist in general yes okay so um okay so the key idea let me show you the key idea this is just to to uh uh to tell you that it's it's not it cannot be that complicated if it can be described by five lines of uh of pseudocode

but let me give you the the idea actually uh it's connected to biology uh so this somehow what I've been doing for the last 20 years it fits um the way DNA is replicated uh the replication machine can go only in One Direction but the Strand the DNA double strand opens like this so This strand it can go in this direction but in this trend it can go only in this direction so how how can it how can I do it it simply adds small fragments starting every time from the fork so this leg What's called the lagging strand is is is computed discontinuously by by different short fractions which are then ligated okay so if you just reorder it the other around so it's the

same direction so the output the blockchain produced by each Miner looks like that it starts from the next leader and backwards and the next leader and backward the next leader and backwards that's that's how it's constructed so it's it's it is contracted in jumps and this delay depends on the particular particular of the protocol uh which I will mention very briefly um again this is basically how it works you identify finer leaders which I have not defined what they are but in a minute and then you from a final leader you compute backwards as the blockchain block list grows you compute

backwards and this is this is all the the other dag protocols operate the same way it's not specific to the block list uh but um what what the block list does is it sorry uh there's one thing I wanted I did want it to to to to mention in the code which is very simple that the topological sort sort only the approved the blocks approved by uh by B okay so basically here you do a provocation exclusion so every Miner when when there is a final block that all have to agree upon remember we need to have consensual leaders leader blocks so once there's a consensual leader block we use it to do

convocation exclusion of everything below it in the dag and this particular place is what what it does it the the leader block is used not to be super majority will will but simply the leader itself decides who uh how to resolve equivocation the leader block so that's how they all agree on on the order and resolve equifocations should we take these leader blocks as a checkpoints um no the the way to the first it is confusing I mean uh many people they keep you changing terminology and all that the best way to think about it is an agreed upon way to break symmetry because the problem is everyone the

situation is symmetric how how can you break symmetry we cannot do it deterministically so we need to do it non-deterministically and either you use it using pseudorandom functions uh uh which are agreed upon by everyone or random coins so the leader blocks are really a way to consensually break symmetries so at that point point to someone and say pick this double spend is it a or is it yes or none yes but and that's what the the Doug Rider does and they can do it because they use reliable broadcasts so they've eliminated all equivocations before that in in in in The Cordial miners protocol you you don't do it and you win you win half of the latency because of that but

you're left with the block list with equivocations and then you have to do what uh what you've done but to do it reliably we actually have a notion of uh super ratified leader so it's if those who know the bracha historical algorithms from the 80s for for uh these are really the first algorithms for asynchronous consensus he had the notion of a super double super majority uh and it turns out that it's a fundamental notion that you really need it and so we a block an elected leader block is final only there's if there's a super majority that approves it and the super majority that observes each each one of okay there's a

super majority that each member of it observes a super majority that approves it and that's the notion of finality and the reason why we need such complicated notion of minority which is sort of at least two rounds but maybe more depending on on various things is that you want subsequent leaders not to be able to bypass this leader and here it comes the the where cordiality is needed again I'm I'm rushing this going since I have one minute but if this is has a super majority this is super ratified and this is a cordial block then for example look here there must be a a block in the intersection so this block will see this block in the

intersection which sees the super majority which sees that so basically this one sees the super majority that approves everything that can decide for this and for everything else so you have every decision does have super majority support of of minors and therefore uh you can you you can count you can count that it doesn't have faults okay that's that's uh hand waving but that's that's the core of the proof that because a combination of requirement of double super majority and cordiality this this is cordial block so it observes the super majority it either has an intersection here or it has a correct minor that is common to hear and here and since this minor is correct it

has a path because a correct Miner has a path from each block to its previous block so this guy sees this this block which goes through a path to this block which sees the super majority which sees this one all of The Cordial assumption that's just to make sure everybody knows super majority is up to today the cordiality implies that there is a super majority here that you see and since you require super majority support here they must have an intersection these two super majorities of a correct minor and therefore you have a path that goes through correct miners that sees a super majority that that approves this this is the leader and and then this leader is final if it has this

structure and that's how Tau computes and the monotonicity is guaranteed by the fact that a new leader will necessarily see this leader and therefore will only extend the the the output sequence so everything up to here can be cached because it cannot by it cannot bypass it because it's guaranteed to see a super majority that sees uh it guaranteed to see someone that sees the super majority so it can this leader cannot bypass this leader and that's why you can cash that's that's the finality that's why there's never forking because once the leader is final every future leader will see it and will never try to bypass it through another path because remember the block list or the dark that it's the

same in both protocols uh grows differently in different miners I mean different miners see different partial views of it but this guarantees that once they output something they will never regret it or never never forget it that's that's the the safety I will uh our liveness is even more complicated to prove eighty percent of the work in the in the paper was it was improving the aliveness but I I'm already over time so uh I will just uh say that we have um the protocol works for both eventual synchrony and asynchrony and these are two different models of um of distributed systems with adversars and the wavelength the the gap between two

leaders here it's two and here is five here the prospective leader selection which means random uh pseudorandom but here it's retrospective so it's shared coin and here there's some complicated conditions for finality and for completing rounds and probability of wave success here is four ninths and here's two-thirds which is the way we we from which we derive the expected latency so uh going going back to the uh to the table so we have achieved all these three goals uh within the block list in a protocol these are by far the best protocols

until now much faster than all the Alternatives and also experimentally the the bull shark guys uh have implemented it and showed performance numbers that are off the charts so this is even simpler and and faster than bullshock like twice the latency um and I should say that this is sort of an accidental it was not I was really looking at the Grassroots bottom-up kind of protocol stack and the fact that there's a cherry on top you know with the consensus protocol that's faster than all the rest is is a bonus it's not uh was not a research goal but it's is a a happy happy accident

uh yeah I guess that's the end of my talk yeah listen okay [Applause] first of all just to confirm uh there is an impossible result for asynchronous protocol right and The Cordial assumption is what makes that result actually what what makes this result work is uh is already in the dark Rider protocol it's not new to us not new to well us is sort of because I this paper cordial minus protocol is co-authored with some of the the the authors of the Doug Rider protocol so let me uh go back to that here

the ordering is used consensual leader blocks uh and these are elected using shared random coins so the the flp result or the this is is countered by electing the the the blocks that break symmetry using a shared random coin so you add randomness to address the flp theorem that's why it works for asynchrony uh that isn't prefix consistency it's just no inversions does that make sense uh and like do you think that is not sufficient or like has anyone looked high whether it's

um okay this weaker notion was invented by people who didn't want to go all the way down to here so actually you don't even need this is the this is the true weaker notion it's all you need is super majority approval you don't you don't need to talk about order at all just super majority approval uh to to eliminate equivocations here the reason we the reason I'm interested in this it's not that I'm not definitely it's important to have ordering consensus because these are important applications but these are even more important if you will uh for example if you need Democratic dials you cannot do democracy without total ordering because you need to know if votes happened before or after the

closure of the of the ballot or you know things like that so um uh for that anything that has to do with the smart contracts and and or or um replicated State machine you need total ordering because if you change the order of things the result of the computation will be different so so for for the important applications here the weaker notion of consistency is not good enough and for these applications you don't even need that so it's like a hybrid thing which is too strong for what is for this application in two weeks for these applications that's why personally I think it's not a useful notion but I may be wrong I'm I may be I maybe have I may have a narrower

perspective but from my perspective it's not needed it's too strong for this and too weak for this I'll ask one final thing um way in which to have to have safety you need for reality like is there a way what to have tough this is not well defined but it feels like to have the task property you need Cardiology yes yes do you show that or you just take this trip well uh personally I'm quite weak on negative results I prefer to work on positive results and let other people prove negative results so nobody uh this is all very new so uh I don't know I

know that we need it for how to work but we haven't proved that you cannot do without it yes at the beginning you settle one of the properties we wanted was scalability can you say a bit more about how we achieved that here yes um okay let There there it's a huge question I'll try to answer uh briefly so first of all here at this level scalability is achieved essentially like dog Rider um by um first of all you have to agree that you don't need an unmarked number of miners I mean it's not scalable with the number

of finals but who need infinitely many miners I mean people agree that with you get reasonable safety with you know few dozens or hundreds of miners you don't need more than that in in a reasonable setup to feel comfortable about depending how they're elected etc etc if they're sampled from a large population but but uh but uh so it these protocols do not the the complexities is quadratic in the number of uh of miners okay typically uh but let's assume that you have agreed on some reasonable bound on a number of miners then what's happening there is just extremely extremely simple and efficient the only thing that's happening

is that every Miner collects transactions puts them in a block creates adds to the block pointers to the most recent blocks it saw in the in the Dag and it doesn't even have to have blocks to everybody else because if I got a block from someone that already points to other blocks I don't need to point to the other blocks it's enough that I point to him you know so it it's not in the it's not necessarily even end pointers in each block you may have less and I send it to to and to the other n miners that's all I do my the round of a minor is just low transactions into block add pointers send to n minors load transactions in the block at pointers send to n minors and between them I wait

for super majority of blocks from the other miners that's all everything else is happening locally is is a is a computation so that's in that sense um just specifically head to head with the blockchain consensus or other protocols for or or other standard protocols for business in agreement which are leader based whatever this is extremely relaxed and efficient I mean I think that it's fair to believe that you can get arbitrarily large throughput with with this uh with this protocol because you just load transactions into everybody load transaction Center but that's all the only thing that happens the rest is just local computation of ordering this

that's at this level at this level I say something much stronger and broader and I want this to be Grassroots what does it mean to be Grassroots it means that uh people in Timbuktu or Senegal or Israel or tanjir or New York and all start independently their local whatever local social network local networks of sovereign cryptocurrencies they can start them independently and eventually if someone is happens to be connected to two communities then these two communities will connect or if I establish connections with someone from another Community these two

communities will be connect and still continue to work we don't need to reboot we don't need to start with a new directory we don't need the new Epoch we need it's just grows and grows and grows independently in parallel and interconnected and these protocols support this uh notion of Grassroots and in this sense that they're in in that sense they're scalable okay and again the the we need to talk specifically about the tasks but both for this task and for this task the communication is always local and linear and the number of whatever okay but that's a different notion of scalability okay thank you very much