ZKPodcast: Consensus Algorithms & HotStuff with Ittai Abraham

Transcript

[Music] welcome to zero knowledge a podcast where we talk about the latest in zero knowledge research and the decentralized web the show is hosted by me Anna and me Fredrik before we start on this week's episode all about consensus algorithms I want to say thank you to this week's sponsor matter labs matter Labs is the company behind the first ZK roll of prototype as well as the team behind ZK sync a user centric aetherium scaling solution secured by

zero knowledge proof ZK sync can be used already today to transfer high volumes of ether and ERC 20 tokens at low cost with no trusted party involved soon smart contracts will also be possible on ZK sync this is made possible by zinc the rust based zero knowledge programming framework developed by the matter labs team the ZK sync test net is live and they invite you to try out it's simple and intuitive user interface at ZK sync IO will add the link in the show notes security audits are currently underway and once completed ZK sync version 1 will launch on the etherium maenette so thank you again mater labs and now here's our

conversation with you ty Abraham all about consensus algorithms so this week we dig into consensus algorithms and we have a guest etai Abraham from VMware research to help us just like chat about modern distributed consensus systems so welcome to the show thank you so much for having me and then Frederick cool Hey yeah excited to dig into this topic and talk about some of the work that you've been doing as a primer we have had a couple episodes on this in the past and most notably with Robert Heather Meyer from Paraty talking about sort of basics of can like proof of state consensus

algorithms some modern consensus algorithms like pbft in or Boris and whatnot so if you want sort of pre listening material to this episode you can go listen to that so let's dig in with you it's I what is the work that you do and what got you into this field what got you excited about it yeah so I'm the computer scientist and I do work in algorithms and distributed computing I've been working in the area of strict computing and concerns protocols for over 20 years what I really am fascinated about especially in the area of consensus protocols is this is such a simple problem right it was

formulated back in 1978 by Leslie Lamport and co-authors and you'd imagine that that's such a problem such a simple problem we're just being solved and then people would move on but what it seems to be happening is that every decade there's more and more work on this fascinating problem and in some sense what we're seeing now is that consensus is kind of the backbone for all these blockchain technologies and infrastructure there's something that we've never really dug into which is the original formulation of that problem so if we talk about consensus there's obviously like you and I can agree on something but there's a global consensus and then we have raft like consensus which is not Byzantine fault-tolerant

and then we have Byzantine fault tolerant consensus which I think many people's first time hearing about this concept at all is proof of work and how that you know supposedly achieves that but it like you said it's an old formulation and the Byzantine thing actually comes from like a Byzantine generals you know imagine me imagine there are these generals and they need to agree on who to attack maybe do you know that formulation by heart because I think might be interesting to just set the I set as a primer sure so you can think about the simplest type of visit the agreement where there's a bunch of generals that have to reach a decision

you can think about this as a binary decision so they have to attack either at 8:00 or 9:00 and some of these generals are actually controlled by by a malicious actor and if all the non faulty generals succeed to attack at the same time then the attack succeeds if the malicious generals managed to create disagreement then some generals attack at 8:00 some at 9:00 and the attack fails so really it's about these very simple properties the first property you want that everybody agrees on the time of the attack the second thing you want is that actually people reach agreement this is the finality property right you're seeing some systems that just never reach agreement so that's that's bad too because then you know it'll be past the

time to attack and and you know these two things together actually quite easy to do we can all kind of defaults to decide that we always attack a date we never attack at night so the third property is validity property which basically means if all the non faulty generals want to attack at nine then that must be the decision so the validity property is basically that if everybody wants to have the same starting time that's gonna be the starting time in that original concept is there a percentage that one must reach or is that sort of dependent on the system right so so in a sense reaching consensus if there's no failures is easy right we all just say what our value is and maybe we take the

maximum value or the majority value so really the problem is reaching consensus in the face of failures and this is where you introduce a failure model so whether it's a Frederic you mentioned raft where the failure model is just that some machines can crash or miss D or misbehave and in terms of missing messages or this Byzantine months and the Byzantine model the assumption is that some of these parties can act maliciously they're trying to they can send different messages to different people they can cheat and lie in order to cause disagreement so in that in that sentence Byzantine fault tolerance so the fault is this failure I guess of Byzantine is the generals fault is the failure oh yeah what are we typically

when we say a Byzantine fault it typically just means that it can do whatever it wants it can you know it can lie where as in uh like like you said in a raft type of fault the server goes down but it can say something that it you know like you can lie basically right so so the first thing you do is you define the question right consensus and then you define what is the power of the adversary whether it's Byzantine malicious or just omission or crash and then it really depends on your network model and how long your adversary can be right so if the adversary can be let's say more than 50% of your world then you have this split

brain attack right if the adversary is is more than half then you will never know who to believe right you're gonna probably believe that the adversary could controls more than half of the world so there has to be some limits on the size of the adversary and this is where this ratio comes into account so in different types of network models there are different ratios of how many Byzantine failures you can withstand and and tolerate this is where the Byzantine fault tolerance comes into play so as you said you know this has been an area of research for many decades I think pbft was published somewhere in the 90s late half of the 90s how have you seen this space of all over time

yeah so so I think there's definitely been two phases one is a phase where theoreticians people who do theory of distribute computing and theory of cryptography have published papers in this area and indeed I think it's a 1999 that pbft was published and this was a kind of a major milestone because it was not just another amazingly good protocol it was also a system that was built was built by Barbara Liskov and Miguel Castro Barbara Liskov was a turing award winner and her Turing award was was about software abstraction so the Turing award is is kind of considered a Nobel Prize of computer science and so this

was a very well architected system the sense that it had very clear separations of between layers there was a clear layer of consensus and a clear layer of state machine replication and so I think after 1999 there was this surge of systems research into Byzantine fault-tolerant systems I remember in 2008 being in a in a workshop that was focused on Byzantine fault-tolerant systems in the real world as you all know this was the same year that the Bitcoin white paper was published and the high-level theme of this workshop was we don't have any use for the businesses also distinguished mammals so this was essentially after 2004 where

the raft and paxos type protocols the ref wasn't invented then but paxos which was essentially a very similar protocol was was used in in many large companies so so Google Yahoo Microsoft Facebook all these companies use raft and raft like protocols and paxos and and this was a conference trying to say well let's use it for the next thing and this was 2008 i remember that the conclusion was we don't know what the good use case is that's wild because i mean when we talked to some of the zero knowledge researchers we hear similar stories about the early 2000 not years from them that like they had this really cool thing but there were so few use cases at

the time yeah i mean to me I think it's it's this realization that consent is kind of fundamental to to to to to disruption so there's this famous saying by Marc Andreessen that software is eating the world and we've been seeing software disrupt a lot of industries retail and artificial intelligence today is another example of how software is changing the whole landscape with you know that this kovat pandemic you're seeing that education and a lot of things are moving online so software is even more important in that sense but what we really are seeing now is that software is eating the way we're governed and software is eating how money is defined I think this is the disruption that we're living in where

even though technology has made a lot of changes in the last 50 years I think the way we're governed the way that nation states operates in this first quarter of 21st century is pretty similar to the last quarter of the 20th century not a lot has changed I think what we're seeing here is that this technology is making this change and consensuses is kind of the backbone of a lot of that so it's an enabler for kind of trying to disrupt these new areas did you did you already see its potential when you started researching it even though there weren't these like big use cases or like why were you interested in it yeah so I remember in in 2014 I I read this article from the New York

times again this is Marc Andreessen why Bitcoin matters and in this article he's actually saying that bitcoin is the first practical solution to the Byzantine agreement problem and I remember reading that article and saying you know I this is what I do I do research in business and protocols and here's a VC writing in The New York Times telling me about something that I've never known about and you know I read this thing I said he's obviously wrong and it took me actually awhile to realize that this is indeed a huge disruption and a major breakthrough in Byzantine green protocols but what were you into before like what did you see it for before oh I think I had a basically

a passion for mathematics for algorithms and I believe that kind of decentralized and distributed algorithms are important because they give you kind of the fundamental ability of fault tolerance so as you know the world has failures and so handling faders seems like a critical thing to do mmm-hmm it was for me more a mathematical curiosity at least early on in my career and then at this time though so like once the Bitcoin puzzle piece clicked for you that was when you maybe realize that this work wasn't just cool math I mean I'm sure you thought it was more than just cool math but like kind of almost goes from foundational research to applied research yeah yeah I think it

took me at least another year to kind of understand that Nakamoto consensus which is the Byzantine credo protocol that Bitcoin and aetherium and all the proof-of-work protocols use is is one instance of this larger field of business agreement protocols and and you can use you can add finality gadgets to them or you can build other systems they use different types of business agreement protocols and and I guess these different types of business even protocols are the ones that that I was more interested in and I was studying for a while I just wanted to shoot in a question here as well talking about applications and use cases and that is that you're you're working for VMware research and I can imagine

why VMware would wants a consensus protocols because it you know it deals with orchestration distributed systems and VMs potentially but why Byzantine you know agreement protocols like hey yeah it I don't know how that fits into VMware's roadmap yeah so so you know if you if you think about VMware VMware is a IT infrastructure provider right so technology infrastructure provider so it typically provides enterprises with compute infrastructure with storage infrastructure and with networking infrastructure and the high level belief is that in the future people will need a trust infrastructure so just like today kind of your basic compute is compute

storage and networking in the future will also be trust and the centralized trust in particular Dell secure my CEO he said that he believes that Bitcoin blockchain technology is as important as public key technology right and just like today you couldn't imagine the internet without a public key infrastructure I think in the future it'll be hard to imagine kind of the future event of the connected world without this decentralized trust in the structure hmm so let's dig in a little bit to consensus algorithms may be a starting point would be to talk about like I think we can now talk about consensus algorithms in the context of

blockchain I think we've understood now like where that where that lands but you've said in the past in sort of other talks and articles about you've talked about this layered view of blockchain maybe we can talk a little bit about that I'm curious to hear if you're layered view is similar to other layered views that we've talked about with other guests on the show yeah so I think this is kind of a realization that we had around 2016 that this blockchain space can be separated into into layers so the bottom layer is it is consensus a state machine replication particular that's layer one the second layer is a smart contract layer that's where you you have either a Bitcoin script or AVM web assembly and so on zero knowledge

technology can also be inside the second layer the third layer are these application that are using smart contracts and we're now seeing fourthly or fourth there's kind of a user interface this would be your wallets or your apps on the phone you can think about them as a secondary clients that talks to this third layer and this third layer is talking to their 2n and yeah I mean I think what we realize is that this abstraction is essentially following Barbara Liskov vision of how state machine replication should look like so in that sense this is work from the early 2000 of Barbara Liskov Miguel Castro Raja Goud Regas showing how you can view state machine

replication as kind of a layered abstraction of technology and and what's quite amazing is that I any type of project that I meet in this space I can usually map it to either one of these layers or I can separate the technology into each one of these layers I'm going to throw a little extra point in there because with our inner episode with them Brunei we actually talked about a one-point Flair 1.5 which is the layer that works in between the smart contracts and the consensus level and what goes in there are some of the scaling solutions using zero knowledge proof Slyke roll-up for sure yes so I agree there is kind of an additional technology and and we'll be happy to talk about how consensus and state

machine replication even though it's fundamental it causes these huge problems for a system and then you really need zero knowledge techniques and technology to overcome some of the problems that essentially consensus brings you and that I guess that that would be kind of the layer 1.5 so in that sense I think dan and I definitely agree cool so as we're talking about consensus I think one of the most important things to have clear in your mind of what a consensus algorithm does and how it works is what are its synchrony assumptions so there are synchronous consensus algorithms asynchronous ones fancy partial synchrony models and in newer algorithms

what are these concepts and sort of how do they work in consensus right so so again the the goal in these protocol is to get fault tolerance and so fault tolerance against an adversary that can cause harm to both the parties in the protocol but also to the network properties from the protocol and so these network models basically try to confine how powerful the adversary is relative to the network and so the most extreme model is the asynchronous model so in the asynchronous model the adversary can basically delay any message between any two parties any amount of time so this is kind of the extreme denial of service adversary

right it can do whatever it wants and delay messages you know you can send a message I can delay it for it for a month why is that even a model then like it just sounds like a really dangerous setup in the first place that's what that's what you want you want to model things like that that's the goal right is to be as tolerant as possible oh yeah exactly so people said what is the worst thing I can imagine and I want a protocol that actually works well in this model okay and so it it turns out that there are fundamental lower bounds so for example you know you cannot solve consensus in the asynchronous model without using randomness so deterministic protocols will always fail so a synchrony is actually pretty hard

model to to work with even today we don't have good asynchronous Byzantine Agreement protocols that work well in practice I can tell you a little bit about some of the cutting-edge research in in a synchrony but I guess this is kind of the reason why people looked at the other side of the spectrum so the other side of the spectrum is to say instead of assuming the adversary can delay messages arbitrarily there's kind of this fix known bound let's say this bound is two seconds and so basically the adversary can delay messages any any message but no more than two seconds so it can send the message immediately it can delay it by a second and a half or you know at most two seconds so that gives you some control over your world

you know that if a message in arrive after two seconds then probably the other side didn't send it and so this is kind of the this assumption of synchronous protocols for example if you at Nakamoto consensus this is the consensus protocol that Bitcoin in aetherium and other proof-of-work blockchains use they assume synchrony right they assume that once you have a solution then it this solution will arrive in a bounded times that everybody can use this hash solution and so there are there are these protocols that use synchrony traditionally in the enterprise world people try to avoid assuming synchrony and so they try to come up with a model that gives you kind

of the best of both worlds on the one hand you don't have to always assume that you're working in an extreme version of a synchrony on the other hand if the system is relatively stable then you can get reasonable types of performance and so this is this third model of partial synchrony and partial synchrony is a famous model from 1988 dwarfed Lynch stockmeyer a great paper which already has their Byzantine agreement protocol for partial synchrony this same year 1980 was a huge year for the theory of disturbed computing it's the same year that Leslie Lamport published part time parliament this is the famous Texas protocol and it's the same year that that Barbara Liskov and Brian okie published view stamp

replication which is another which is another protocol like paxos and it's a precursor to PDF tea back to partial synchrony the partial synchrony model basically says that there are two phases in the world in the first phase everything is asynchronous and then there is kind of this unknown point in time where the system becomes synchronous hmm is that dependent on how many participating or is it just like a time frame like an arbitrary time frame that's set but not shared yeah so it's it's it's it's basically a promise in the adversary model that eventually something good will happen what it's trying to model is the fact that you may

have bursts of a synchrony but most of the time your system is synchronous it's the partial like on that scale where asynchronous is the most difficult to make say is partial on the other end of that or is synchronous on the other end of that like which is partial end up in the middle I'm kind of curious how that how that Falls great yeah so in a sense you use the word safe and that's that's exactly the right term to think about because as you remember from the single-shot consensus there are two properties you want to maintain the first is safety the fact that we never decide different values and the second is liveness is the fact we actually reach a decision right there is finality

and so the what partial synchrony says is that essentially safety is always maintained so safety will be maintained even if the system is asynchronous but you're only guaranteed liveness you're only guaranteed finality when the system is synchronous and this turned out to be a very good trade-off in practice so basically says even if there is this extreme amount of service we're gonna be always safe and when the network kind of reaches some sort of reasonable state then we can try to make progress but does that put it on the other end of that scale that I'm thinking of or is it sort of there's three different levels

and there each one of them offers different benefits to one of those levels like I'm just curious if you can think about it along a spectrum or if you should be thinking about them as like separate things partial synchrony is definitely in between synchrony and a synchrony okay right ace attorney says the adversary can candle a message with arbitrarily and synchrony says that it always bounded and partial synchrony says well at the beginning it can do it every at once and later on it is bounded okay so I think in that sense it gives you a good middle ground to model protocols and I think what's important to keep in mind is it's not at a fixed point along that axis if we see the opposites as

asynchronous and synchronous partial synchrony is somewhere in between but not necessarily always in the same spot in between so like you said the model is sort of you know let's assume a spike of a synchrony what does that mean well probably means that someone is ddossing your system your being you're under attack and under attack you are asynchronous and you're supposed to survive that attack but the assumption is eventually you will survive that attack the button the attacker will eventually stop attacking and then you're back to a synchronous model and you can continue so it's not like you're you're right there in the middle or you're kinda it depends on the network conditions on the attack scenarios and everything else right and

the fascinating thing are the lower bounds so in a synchronous Byzantine agreement you can handle any minority so 49% malicious actors but in partial synchrony you can only withstand less than 1/3 so 32% malicious actors and so this is kind of this trade-off of saying you either can handle a lot more malicious actors let's say 49 percent but denial-of-service a complete analysis might cause you to lose safety or you're saying I'm willing to say I'll never lose safety if there's a denial of service attack but then I can only

withstand a third malicious actors and it's interesting because some of these percentages or ratios that you're sharing start to sound like some of the consensus protocols that we've heard of coming I guess we're gonna talk about coming from those yeah so I think you're absolutely right traditionally both for crash failures and from for Byzantine faders people have used partial synchrony and examples of those protocols are pbft or new ones like tender min to casper hot stuff cool always can only reach 1/3 failures right they can't do better than 1/3 so the difference here is that is between

synchrony and partial synchrony now what partial synchrony allows you to do is it allows you to make progress at network speed so every time you reach consensus you don't have to incur a timeout you can reach consensus as fast as your network allows you to and so that's what that can give you much better rate of doing multiple consensus per second rate versus the synchronous for the cause and in proof-of-work is a good example but I think Definity is another example of a blockchain project that is trying to use synchronous Byzantine Agreement these protocols at least have to incur a delay a fixed delay every time they reach consensus

you mentioned you use the term single shot just before what what was that what does that mean yeah so so in consensus protocols in the theoretical frame you can just think about reaching agreement on one decision which is you know do we attack it at 8:00 or at 9:00 but if you think about these blockchain technologies you really have to reach multiple decisions and so you're basically agreeing on a shared log of commands and you're not only agreeing on the shared lot of commands you're actually executing these commands so there's kind of these three layers of technologies first one is just doing a single shot consensus the second one is actually transforming that to multiple

consensus instances and there's a lot of cool new ideas that you can use for example pipelining where one instance of a consensus can actually be running the next instance of consensus and so on you can get efficiencies through that and the third layer is that it's not just about reaching consensus something it's also about executing the commands of the state machine and so these are kind of three layers of technologies that build a state machine replication protocols mm-hmm so we sort of just hinted at this but I kind of want to go back to the the difference between something like a proof of work system and a proof of stake system in the context of what you've just shared maybe we can talk a little bit more about that yeah so in the traditional distributed

computing setting you have kind of fixed set members so n n nodes right that's kind of this quintessential n number in theoretical computer science and in a sense if you think about a consensus protocol a consensus protocol is all about reaching a decision and the thing that you should ask yourself is who has power to reach the decision so it's really about distributing power to voters that have to reach a decision if we have to decide whether it eight or nine who makes that decision is it you is it somebody else and so in the traditional computer science approach you just assume there's n servers and

each one has one voting power so they get to decide on you know they get to raise their hand once if you think about proof of work then in proof of work Bitcoin white paper says this very nicely it says one CPU one vote hmm so proof of work basically what it does is it gives anybody who has the ability to compute hash voting power proportional to the ability to compute hashing health so obviously it's not one CPU you buy these huge machines that can do enormous amounts of hashing per second but but fundamentally you it's a way to distribute voting power to people that can compute or to entities that can compute hash the beauty of this way is

that there is no PKI there's no public key infrastructure anybody that can compute hashes can basically participate in this consensus protocol it does create a different type of power distribution where you know if you have a better way to compute hashes maybe you have cheaper electricity or you have access to better hardware then you get an advantage but it's a way to give voting power in a Byzantine agreement protocol proof of stake is another way to give power which basically says one coin one vote so you build some sort of coin in this case manytimes cryptocurrency and what you do is you say let's say if somebody has 32 if then it can lock this

and get one voting power and so again it's a way to distribute voting power in a consensus protocol but in the case of the POS system it's not one CPU one vote like it is one could collect a lot of votes in a different way I guess you can also collect votes in a proof of work system you just have to invest in the hardware well I mean you could depends on what you mean by collecting if you're thinking about someone getting power to vote without locking up there are tokens that's pooling resources into one person you know almost all mining activities and mining pools most people actually

delegate their voting power to mining pools so it's not any longer one CPU one vote it's one CPU one and delegation to a mining pool who gets a vote but you know I don't think that detracts from the idea from the fundamental concept right it's you're basically just saying I through other means through social means or political means I can get someone to vote for me and I vote on behalf of them so these are two important things the first is there's a smack Pro economic theory that this power can be essentially abused by money so if I have a lot of money I can buy cryptocurrency and get voting in it in a proof of stake system if I have a lot of

money I can buy mining hardware and get a lot of voting power in in a proof-of-work system so one of the open questions I don't have a good solution for that is how do you make sure that that you have a more equalized system that doesn't kind of create this effect where are people that have a lot more money have a lot more voting power and that is at the heart of like a lot of systems attempts to have good token distribution like they want better token distribution so that they're not in a state where like a small group of participants can can easily own you know more than a third or more than a half of the network exactly and the problem is even if you distribute it equally maybe people who have more power can then go

and and and buy some of these tokens and centralize more voting power and that's kind of related to the notion of delegation that you mentioned where this is how we today govern right we delegate our vote and and we kind of vote for a smaller set of people who govern us and so delegation also has you know both centralization risks and advantages of specialization where you have somebody who's specialized in governing or in this case specializing in staking so I think finding the right balance is a challenge but to me what's important is understanding the fundamental the fundamentals are that it is about distributing power so it's a how you distribute votes in a consensus protocol essentially to bring it back to

it more like foundational consensus research there's this concept in many consensus algorithms of a leader and many of the blockchain algorithms that we talk about are leaderless the you don't elect a leader who gets to pick the block and then you know is there a practical thing that you have to think about when designing algorithms to go from a leader leader phul and to leader or less algorithm yeah that's a great question so if you if you think about proof of work then whoever wins and produces the first solution to the hash riddle you can imagine you can think about that solver as a leader for a second for a second and and if you think about protocols like pbft so pbft works

in this primary backup approach where there's always one node that's leading and everybody else is a backup and then there is a view change protocol that allows you to move from one leader to the other really from a foundational perspective the question you should ask again goes back to the model is how adaptive is your adversary this is the fundamental question okay what is an adaptive adversary an adaptive adversary is one that can look at the system and decide who to attack based on what's happening and so the problem with many of these protocols where there's a leader that's known and exists for more than a second is that as an adaptive adversary I can find who this leader is

and an attack this leader you know maybe in Bitcoin the advantage is that by the time I know who this person is the the hash message has already been propagated through the whole world there is still kind of a smaller point in time where an adaptive adversary can succeed so formally speaking you can imagine very strong types of adaptive adversaries and so against them you have to do something more complex and really what we're seeing and this is a work that started from theoretical cryptographic protocols and appears in consensus protocols like cuts and coos protocol from 2006 and in some of my work is this idea where instead of

designating one leader in advance we kind of tried to spread the role of leader among everybody in the population so the idea here is that if you have a leader and there's an adversary then this aggregate is going to attack your leader right so you choose one Prime Minister so the adversary attacks this one Prime Minister and so the trick is to basically say we're all gonna be prime ministers so each one of us is gonna be a leader and then maybe after a while let's say after 10 seconds we do a random leader election to decide who in hindsight was the actual leader and everybody else is actually a decoy so you know on the one hand we did a lot more work because now instead of having one leader we had a lot of leaders on

the other hand if you're an adversary you have no idea who to attack because you don't know who is going to be important in this protocol it's only in hindsight that you learned that but in hindsight you can't go and you know go back in time and attack whoever was actually chosen what is the P and P PFT stand for so P is for practical Byzantine fault tolerance okay there's another one s PFT right so this is scaleable Byzantine fault okay are there any others that we should know about there's a lot I think everyone else kind of came up with their own name and didn't go with the something BFT naming this game but I find it funny that pbft being like as you talked about earlier

it was this big thing and finally there's a system that someone was built and it works it's called the practical me like it's just the practical system well I mean here's why it was a revolution back in 1999 at that time it was almost like the zero knowledge revolution of the last five years people thought of Byzantine Agreement as kind of this math or theoretical computer science and it can't actually be used in practice and so for the first time Miguel Castro and Barbara iske they actually built a system and and there's this amazing effect when you actually show somebody a system that works that's a that's a huge difference between that

and just talking about something in theory yeah we definitely seen that revolution Bo like practical zero knowledge and practical MPC and think we should have the first thing to actually build something they should be called the practical thing yeah you know the next phase after practical is boring oh yes boring is what we should all aspire to right exactly so you know we should have boring bft it should be what I do is is all the cutting-edge exciting consensus protocols but that should not be what people use right so I think you might be the first guest by the way who

just comes on and says this is what I do don't use it but thank you guys yeah I mean look there's this gap between what innovation is and what a quality world scale enterprise scale solution should be right this is why when you use a TLS library there is actually library called boring TLS right because because you you want it to be vetted you want to have a lot of years of very good engineering and tests and verification you don't want to live on the cutting edge it's similar to you know you don't want to roll your own crypto you also don't want to roll your own BFT protocol unfortunately I've seen too many people do that so I really hope that one day there will be kind of boring state

machine replication protocols and and people will just use them be BFT yeah yeah speaking about these different kinds of consensus algorithms you know VMware has published this hot stuff thing I assume you've worked on that too and you know it's a it was something that came to the scene relatively recently for me it really I really only like open my eyes to it with Libre and them picking that but I'm curious what hot stuff is and how it compares to those that we've already talked about yeah so so in fact I'll start with a precursor work which is SB ft so when we started the blockchain

project inside VMware we basically looked at pbft and we said this is a wonderful protocol but it's from the 20th century and we asked ourselves so what is kind of the new things that we can do today and we realize well there's better cryptographic tools we can use threshold signatures and the second thing that we realize is that we really want to create a protocol that scales for four more replicas so pbft was optimized for four or seven replicas and we wanted to kind of scale for 200 or 300 replicas and so the first thing we realized is pbft as a protocol inherently uses quadratic number of messages what does that mean it means if you have seven replicas say you know roughly speaking seven squared

so 50 messages every round now that's not that's not a lot that's not a big problem but if you have a system that has maybe 300 replicas now 300 squared is actually quite a big number and so we wanted to avoid that and what we did is we realized that that you can change some of the protocols to get a linear communication pattern so this is kind of the second thing we did the first thing we took modern threshold cryptography the second thing we did is have this linear communication complexity and the third thing we realized is that you really want to use optimism right so you can design systems that are always at war they always feel that they're being

attacked or you can design systems that actually have this kind of optimistic path that says well if things are good I'm going to try to do a little bit better and if I'm under attack I'm going to switch to kind of this second mode and so we added this optimistic fast path and so these are kind of the three components of svse scaleable Byzantine fault tolerance so this is the first system that was tested in an academic setting for 200 notes and so it's the kind of a BFD system that runs for 200 nodes does this is this also is this a partial synchronous model like I'm kicked what you just said sounds like what you just described before we're like it's it's ready to handle bad times but it kind of

assumes more good times yes you're absolutely right so it is it is a it follows the pbft path and pbft is a partial synchrony consensus protocol Byzantine fault our partial synchrony protocol and so yeah this work on sbst is kind of following the same path of partial synchrony even in synchrony there is kind of a worst-case assumption and a best-case assumption and so we kind of get better latency in the fast path the thing that we couldn't get in sbst is reducing the complexity of the view change from quadratic to linear so remember these protocols have kind of

two phases one phase that leader sends a lot a lot of commands and the other phase is that we change from one leader to the other that operation is called a view change and so we didn't know how to reduce the message complexity of the view change from quadratic which it was in PDF tea to something better than that and this is kind of where tender mint comes into play so tender mint was published in 2014 and you know we learned about tender meant basically from talking to Vitalik in 2017 when he was explaining to us how casper works so casper is kind of a adaptation of tender mint as a finality gadget for proof-of-work systems but essentially tender Minh had

this amazing breakthrough where it showed how you can do the view change protocol in a linear amount of time and so that's how we took the ideas in in svf tea and we took the this idea of the view change in kinderman and combined it together to the first version of hot stuff so the first version of hot stuff essentially has linear complexity both in the normal case and in the view change and it also uses kind of again modern threshold cryptography it doesn't have a fast path it just has kind of a regular flow so this was kind of the first step in in in hot stuff and what we realized is that

is that the protocol itself is actually very simple so it has kind of this very simple two rounds for reaching consensus roughly roughly speaking the first round guarantees that the leader cannot send two different messages of two different values the second message in this protocol basically guarantees that if somebody receives a message that will cause it to commits to a value then the view change will be safe the view change will make sure that the next leader will also see this value that's that's the role of the second round what we then figured out is that this two round protocol has still a problem and the problem is that the the view change protocol itself is

susceptible to to a sort of denial of service attack that can happen even in the synchronous model so in a sense you're forced to wait a timeout between changing leaders this this is the notion of optimistic responsiveness so optimistic responsiveness is this property where you can do a view change and you do not have to incur a delay during this view change you can run as fast as the network speed and so this is kind of the finding version of hot stuff where we add one more round so instead of two rounds it's a three round protocol this third round basically guarantees that the view change can can proceed as fast as you as the network allows you to proceed and you're

guaranteed that this new leader will be able to make progress I'm really curious to hear how you reduce the communication to linear because I mean that that's one of the most known problems with something like ten durmand yeah so so this is actually a full klore solution in distributed computing where instead of sending a message from every replica to every other replica you can basically use a collector and obviously this uses the idea of having a public key infrastructure so now everybody instead of sending the message to everybody else you you spend two rounds everybody sends the messages to the collector and the collector can gather all these messages and send them to everybody else if

you're using threshold signatures this collector could actually take all these signatures and combined into one signature so really what you're doing here is you're changing this all-to-all pattern to a pattern where everybody sends to a collector and the collector sends to everybody else so you're spending to end messages instead of N squared messages it creates a bit more delay but does that then require basically like a super node to exist in the network at all times I mean even if they don't really have power to do much what happens if that one goes down is does it become a single point of failure it is an incense from a lioness perspective the leader in pbft in SB ft in tender mint in Casper these are these

leaders are aliveness point of failure so if the leader fails you have a liveness violation and you have to replace the leader with a new view change and so in hot stuffs case it is essentially one of the participants that are the collector right so in in what what hot stuff does is it actually does a rolling change of who is the leader so every round a different leader is being chosen and so the message communication is basically everybody is sending to the leader 3-liter 3 sense to everybody then everybody sends leader 4 then leader for sense to everybody then everybody sense leader 5 and so on you basically rotate through all the leaders but then you don't have that opportunity

to make it leaderless and and sort of only elect them in hindsight because you need to know at the time who to send your message to yeah so so this is actually a new work that we some of it is already in published in 2018 this is work with sasha Spiekermann and Dalia Malky and myself it actually shows that you can take a protocol like hot stuff or like pbft and basically what you do is you run multiple worlds so instead of running one instance you run n different instances so think about these as different bubbles we're in each bubble you have a different leader and then after a kind of some stage you can do a random leader election to choose which

one of the bubbles was the real leader and all the other bubbles you basically pop them and they're just decoys right and what you remain is kind of the the one leader that was at the actual leader so you essentially have to run multiple instances of say hot stuff or SPF TR pbft in order to get kind of this stronger notion in fact you can do that and then get liveness even for asynchronous models right this is kind of the you know the the highest level of guarantees that you can get so you can take protocols that are built for partial synchrony and there's kind of a generic reduction that takes them and transforms them so that they are resilient even an asynchronous model you know right so this is kind of the

cutting edge of where theory is at we still haven't seen systems that that build it or we're starting to see systems that that that are building this type of approach that's super interesting I guess you're like if used in our proof of mistakes setup you're kind of reducing your security like your your stake at risk because you would have to distribute your stake across these different bubbles but only one is actually you know the real one only one of these bubbles have their stake at risk no one knows in advance which one it's going to be but you're not putting all of your state behind the decision that's being made but as long as you have

enough stake in the system that's fine basically yeah I mean you could either decide to split it between worlds or you can imagine that it's as if you're making a bit on all these worlds together and your actual beds is the world that is not popped okay yeah it's really a game of fighting against an adaptive adversary yeah so what you want to do is you want to be able to fool an adversary that can see the system and decide who to attack so you want to hide who's making decisions in some sense no maybe just to wrap up on sort of the hot stuff stuff what is your actual role in that project yeah so I was one of the co-authors of both the SP ft work and

the hot stuff paper cool and it was was it sold to Libre was it given like what was the relationship like what happens to hot stuff as an open it's an open source protocol or so at the time it was just an academic paper okay and my colleague Dahlia Malky she's my colleague but also my PhD advisor my mentor she left VMware and moved to Facebook and so I don't know what Facebook I have no knowledge about what Facebook is doing other than what I read from the web but it seems that that their concerns protocol Libre BFT is is using a lot of the ideas that that hot stuff introduced

well so I'm curious to compare these two to other protocols that are similarly sort of optimistic or they have this happy path and slow path and one is Avalanche and the other one is thunder Ella and they're like the two primary ones in my mind that pop up - who really talk about these two different paths as explicit things we have the same thing in polkadot where I mean we call it eventual finality because it will eventually get there but it we don't really talk about it so explicitly as like a property of the system but in particularly compared to those two because as far as I know they were like relatively novel as well yeah so I'm

going to start with thunder Ella because that's an example of a protocol that works in the synchronous model so this is synchronous Byzantine agreement and one of the major breakthroughs that happen in the synchronous billing agreement and this is Rafael past and Elaine she was this realization that even though you're running a synchronous Byzantine Agreement there is an optimistic path where if you receive more than three-quarters honest responses you can actually run at network speed so this is kind of a protocol that has a slow path which depends on Delta the synchrony Delta and the fast path which assumes optimism as

you said which assumes 3/4 and and allows you to move at a faster rate and so we actually have a new work that tries to optimize these constants so if you think about Thunder Ella then I think the relatively speaking there was a large constant in terms of how long you needed to wait for this delta delay and so we we have new results this is with with my colleagues Ling Ren and Karthik Nayak these are two different protocols one Delta in to Delta so the one that the protocol gives you kind of you know optimal latency for synchronous Byzantine agreement and the to Delta protocol gives you optimal latency with optimistic responsiveness so you get to Delta and then in the slow

path but you also get at network speed if you receive three quarters and what about avalanche yeah so avalanche I think is uh is is is so new that I don't yet fully understand the Byzantine fault tolerant model behind it hair that a lot so I'm gonna you know I'm gonna there are so many protocols right and and every time there are new ones so it's it's on my list to try to understand that and it does seem that they have a very natural and and seemingly very fast way to reach consensus I need to understand exactly what are the limits of the adversary right how adaptive is it how much it can control network Janae's and so on I think over time you're gonna see more work that tries to

analyze this in a more traditional framework of business agreement yeah I think it was actually pretty recently that they even published what it is that they're doing and I think it was close towards for a really long time and that's it's only as of a couple months ago that it's no public you know what what I've learned over these I mean this is concerns protocols that have been around for forty years but definitely the last ten years there is a there are a lot of different groups that are suggesting new protocols and on the one hand I say you know don't roll your own BFD but on the other hand I'm always amazed by how much I learn from people that that seemingly come out of nowhere

or not part of the kind of traditional disturbed computing community and and bring amazing new ideas right and Enderman I think is a great example of that I think I mean this is something that we've talked about quite a lot in in their knowledge space especially with the Z cache people this interplay that's been happening in the blockchain space between research and engineering where now for the first time in a long time they're actually working well together and this cooperation between engineering and science actual is pushing things a lot faster than if it was just academics alone absolutely I mean I I'm not working quite a bit with engineers and I'm learning a lot from

them and I realize that even though it's important to have the right protocols building the right software abstractions you know using the right tooling building all the tests all the good engineering practices is is very very important you can't just have good protocols good theoretical protocols that doesn't help anything right this goes back to the difference between an academic grade Byzantine fall current system and an enterprise-grade BFD and you know when I want to reach eventually which is a boring BFD right now there everybody's saying you know just don't just just download it and use it because it's it's it's foolproof in a recent episode was Sean Bo he was talking about

you know how they built a new system and it was kind of slow and so he was going in and like profiling and figuring out why it was slow and then we just kind of went I'm just gonna you know play around a bit here remove this thing you know it's it's way faster and still produces the same results and then he went to the researcher and said hey can you prove that this is this still works that this is still safe have you ever had that happen where we're like innovation comes from from that direction yeah a lot I mean yeah to me I think it has to be a two-way street so this is how I learn about what are the real-world problems you can't kind of just sit and think about theory you have to work with practitioners understand what are their

pain points and sometimes they explain to you things and and show you things about about protocols that you realize then that you have to change how you're thinking about about how to design these things so so I I always try to learn from from people who do real work so unfortunately we're about a time it's been a great episode and we've covered a lot of ground there so a ton left to cover as usual these episodes but maybe to tie it all together bringing it back to the topic of the show or the name sake of the show how do you see zero-knowledge proves interacting more with consensus because we touched

on this a little bit briefly and there's problems that ZK proves can solve that consensus algorithms brain you know what is the interplay between these and you know how did what do you see in the future for that interplay yeah so so definitely zero knowledge has a role to play independently this is an amazing piece of technology amazing feat of 20th century theoretical computer science but in a way if we go back and think about consensus as kind of this fundamental building block for a decentralized trust infrastructure then it brings these huge to huge problems so the first problem that concerns us brings is that all the

information is written in a public way on all the replicas so think about basically a whiteboard where the whole world is writing all the information on this public whiteboard so that's a huge problem in a huge inhibitor for use of this technology the second problem is that when you think about not just reaching consensus on some hash but actually executing some transaction on a state machine then since you're replicating now in a bunch of different replicas every time you run a transaction you actually have to run that transaction on all the replicas so again this is a huge scalability bottleneck and so this fundamental breakthrough technology of zero

knowledge helps save consensus from these two horrible things that it does right it makes everything public and it makes everything so slow because you have to rerun everything so the first part is the the fact that zero knowledge proof scan hide things from the public and yet prove their validity so like you know that it's done correctly but still be not public exactly so I can send a transaction and I can prove to you that I own a token and I can prove to you that this token hasn't been spent and I can prove to you that this token is now written in a nullifier they can do that all in a zero knowledge statement so the only thing you learn is that this token transaction is is valid in this sense and this is exactly what seek actual is doing and

we're seeing you know more and more advanced notions of that and the second problem is this just mind-blowing effect that there is this huge gap between running a transaction and actually verifying it so if you have a track somebody has to do work right so if there's a billion transactions somebody has to actually execute those billion transactions but if I have to verify what is my account value at the end of this billion transactions I don't need to rerun those billion transactions I can give a success proof that you can verify for what your account value is and so this is kind of this again amazing ability to to have success proofs that can summarize say a billion

transactions into just a constant or a logarithmic amount of work then you can then verify and our listeners will know this as you know roll up as he Cairo LUP or any of these sort of zk enabled scaling solutions that we've seen at layer 1.5 ish okay so I want to say thank you for coming on the show what's what's next in consensus algorithms yeah so I think there's two big things that are coming up in your horizon once you have consensus you can kind of go and build even more complex distributed systems and particularly going to see this multi-party computation as the next wave of technology that's gonna evolve once you have a stable broadcast and

consensus protocol you're going to have new multi-party computation protocols on top of that the second thing I think that's going to happen in next ten years is more and more use of formal verification so we've seen a lot of bugs and problems and challenges with software today informal verification I believe will help a lot with automating and and streamlining some of the problems that we're seeing with today's software cool well thank you very much it's been a great show thank you and to our listeners thanks for listening thanks for listening [Music]