Making Asynchronous DAGs Practical - Pasindu Tennage

Transcript

[Music] um hello everyone my name is pasin tan and I'm going to present our work on mahim Mahi making asynchronous DS practical this is a joint work done with phip Brian Lees Alberto and ego so the context and the subject of this uh talk is bisontine fall tolerant consensus and to give a very high level of we have a number of replicas that are distributed over geographical setting and what we want to achieve is each replica execute the same set of same history of commands so we call this the consensus or state machion replication

problem and consensus ensures that despite the presence of malicious actors up to a minority we still have safety and liveness now consensus itself is not really a new topic it has been researched for more than 40 years now there are lots of published papers um and most of the deployed consensus protocol as of today are leader base meaning there's a leader node which takes all the incoming requests from clients that are scattered around the globe and then this leader will replicate these commands in a majority of the replicas get the acknowledgements and fin send the response now there are other variations

like hot stuff and several other variations which are multi-leader or rotating leader base however they more or less follow the same leader based architecture now there are problems with leader based bft uh consensus and two main uh problems are first leader performance bottleneck because if everything goes through the leader then obviously it's going to be a performance bottleneck and then adversarial Network challenge as in these leader based Protocols are designed for the partially synchronous Network model meaning they liveness Hal only if the network is synchronous so when the network becomes asynchronous or adversarial these protocols lose their likeness so these are the two challenges why uh these are

the two challenges of leader base bisontine F toan consensus so to solve these problems in the recent years D based asynchronous bft consensus have been proposed and they achieve two main properties first load balancing and second robustness so uh and it's again not a new topic uh since 20182 there have been a lot of papers in this area like for example all un is De Naval bulshar and I think this list can go uh a lot so just to give an overview about how these D based asynchronous by sometime for cons protocol work so in the uh D based protocols each valid dator can propose blocks so usually they

uh use a round base architecture round based design where in each round each validator would propose a new block and then this will continue meaning in each round a new block will be proposed by each validator now let's see how consensus is achieved in a dck so how consensus is achieved is first we elect or we Define a set of leader blocks now in this example in round R there's a leader and then in round r + 3 there's another leader and the idea is one once you elect the leader you just commit their causal history so I told you de based asynchronous BFD protocols they progress at in every round they progress in round

by round passion and once you reach some number of rounds you elect a leader and then you commit its local history now when we started our project we identified three problems in the existing de brace protocols and that's the problem for our research work so the first problem is cost of certification so let me explain you what that means so in a typical dag there are validations as I told you that would propose new blocks in every round however there are some malicious uh players malicious validators who would propose more than one block per round and in distributed ter uh systems terminology we call this as an equivocation and when we have this

equ in Block the ordering becomes Pro problematic so the traditional way of handling equ equation in the dck is called certificates so the general idea is in every round each validator would produce a new block however in addition to this block they would also prepare certificate that certifies that this block is the unique block from this validator for this round so once you have these certificates the next round of blocks would refer to these certificates and this will go forever so the general idea that you need to understand is certification guarantees one block per validator per round R now certification is nice however it comes

at a cost uh because certification requires an online reliable bytime broadcast premiu in addition to consensus so that means you're going to pay some additional number of network hops to achieve certification and this causes high latency and then also certification requires a higher number of sign signature verification and there therefore it increases the resource utilization of the protocol so the second problem that we find in the existing de base protocols is that high commit delay due to wave by wave design so to illustrate this consider a dck with four validators so as I told you before in each round they would propose

a new block and once they reach a wave a wave is actually a fixed number of rounds they would elect a leader in the first round and it will commit its caal history and the D will continue on the three rounds it will elect another leader and it will commit another set of blocks that are in the Cal history of the elected leader block now pay your attention to this block in the yellow color now this block is not included in the causal history of its immediate leader so therefore it's not committed at this point so the deck will continue another three rounds and then we'll elect another leader and only then that uh block will get committed so the idea here is in the existing de based cons

protocol if a block was not part of the Cal history of the immediate block then it will have to wait additional number of rounds for it to get committed so the last problem that we find in the existing deck base protocol is high commit delay due to crash validators to illustrate that consider the same deck now we progress three rounds elect the first leader it doesn't have a cal history we go uh three rounds and then elector leader however in this example assume validator V2 is crashed by the time it propos R plus R plus3 Block and therefore uh majority of the validators don't have that block so because there is no block from that crash validator no

block will be committed at this stage so therefore the deck will continue under three rounds a leader will be elected and then only all the blocks in the caal history will be will get committed so obviously this is not good because the moment you have a crash validator you are going to have a very high latency so in our research which we call mahim Mahi we solve these three challenges and we propose a new protocol called mahim Mahi and it achieves three goals first it reduces resource consumption second it reduces commit latency and it has minimal impact from the crash validators and in our protocol we assume the standard threat model in bft cons that is f out of three 3 f+1 nodes can

be malicious and we assume an asynchronous Network where there is no bound data on message transmission DeLay So in the mahim Mahi unlike the existing de base cons protocols which CH certification we deal with an uncertified deck meaning we don't have any explicit certification phase so in that sense a wave in mahim Mahi has five rounds propose boost boost 10 certify and note that it doesn't have any certification uh protocol and up to minority of the nodes can equivocate so therefore in a mahim Mahi wave you'll have some validators proposing more than one block in a given

round so like any other deck based protocol a block in mahim Mahi would refer to at least 2 f+ one blocks from its previous round and the second uh kind of terminology is how we elect leaders in mahim Mahi because we cannot depend on fixed leaders leaders that are pre-known in mahim Mahi because the network adversary can use that knowledge to break the liveness so therefore what we do is we elect the leader once we complete a wave so how we do that is by using threshold signature based lead election so in this uh in in in our protocol any two f+1 blocks from the certificate ation round would give us

who the leader is in the proposed round so with those background in mind I will get into details of mahimahi so the mahimahi consens protocol has one goal and that goal is to Mark leader blocks as much as possible lead blocks in either uh committed skipped or undecided so the goal of the mahimahi consensus protocol is to Mark as much as possible lead blocks as either committed skipped or if those two are not satisfied it will remain undecided so first I will illustrate what we mean by a vote in mahimahi so in the mahim Mahi we say a block in the

voting round is a vote for a leader Block in the proposed round if there is a causal history from the voting block to the leader block now in this example 41 is a vote for the leader block and also 42 and 43 are votes for the leader block and in mahim Mahi we say a block is a certificate for a leader block if a block from round certify has a has csal links to at least two f+1 blocks from the voting round now in this example 51 52 and 53 are certificate for the leader block 1 one so with those definition in place let's look at how we Mark a leader

block as committed in mahim mahi so if there are two f+1 certificate for a leader block at the end of the round R +4 we say that leader block is directly committed now if there are two f+ non vs meaning if there are two f+ one blocks in the voting round that do not vote for the leader block we say that leader block is directly skipped so with these two simple rules in place how we order the deag is first we order set of uh leader blocks by their round numbers and then we commit until the F until we meet the first undecided leader block so what we do is we first Mark each leader as

either committed skipped if not undecided and then we order them and then we will commit their entire cultural histories so there are several optimizations that I'm not going to present in this presentation uh and this optimization help us to further reduce the latency and increase the robustness of mahim mahi for more information I invite you to read our paper in archive so to summarize in mahimahi we achiev three goals first it reduces resource consumption and the reason is we use uncer we we use an uncertified deck compared to existing protocols which use a certified deck and it reduces commit latency because if its use of indirect commit pipelining and

multiple ler techniques and finally it has minimal impact from the crash validators because of its skip rule so we implemented and evaluated mahim Mahi in a geographical setting so we uh deployed it in two data centers in us one in Europe one in South Africa and another one in Asia and we deployed it in Amazon e 2 and we experimented with 10 and 50 number of validators and we also use 512 byte transactions and we compare it against two two state of thought protocols Tusk and cordial minus so task is the is a state-ofthe-art certified deck based architecture that has the highest

throughput among the set of protocols that are implemented and cordial minus is actually a theoretical work that is that uses an uncertified deck and we implemented that too and we compared it against uh mahim Mahi so in this graph I show the normal case performance of mahim Mahi in the x-axis I show the throughput the yis shows the average latency in the dotted lines I show the performance of uh 10 note configuration and in the non-ded line I show the performance of U 50 note configuration and the black color denotes tus red color denotes cordial minus green and blue color denote uh mahim Mahi so the key takeaway of this graph is that mahim

Mahi provides throughput that's compare comparable to cordial miners however with 20% lower latency cost and second mahim Mahi scales up to 50 knes with latency less than 2 seconds and with a throughput of more than 400,000 uh transactions per second and in this graph I show the performance under bad conditions so in this example we crash three out of 10 validators and the takeaway of this graph is despite crash note mahim Mahi provides high throughput and low latency because of its skip Rule and finally in this graph I show the impact of multiple leaders which is again a novel uh Innovation protocol and the key takeaway of this

graph is mahimahi reduces latency by using multiple readers per round now for more uh details about about these graphs and the paper I invite you to read our paper and also our open source code in the jiub thank you thank you very much for your insightful speech and now it's time for questions please raise your hands okay how can Avid State here same validat like they have particular state so I think um so in this uh

consensus layer we are only dealing with transaction and state is the one you create use in the transaction so there are two approaches to do this the the N approach would be to combine consensus and State and therefore State can be proposed in the consensus block but the standard approach is to decouple these so that in the consensus lay the clients are only sending transactions and then using these transactions once you have the total order the consensus layer will deliver you a cal history and then you you you will use that coal history to create your state so I think these this operate in two different layers not in the cons sler thank you very much um thank you so I have a question about

these um dag based protocols in general I've never actually understood it reading any of the papers um it has to do with how the the validators pick up transactions to put them in nodes because the model I'm used to is there's a pool of transactions and then if there's one leader the leader just picks transactions put them in their node but now all the validators do it they're all accessing the same pool if you have that model so they're all going to put the same same transactions in their block so all these blocks essentially there's a lot of redundancy so it seems you have to then filter it all out and um you have very very high TPS in your graphs when you have many nodes and I'm assuming it's because you're counting every valid dator makes a a block which is independent from the other so if you

have 50 validators you have 50 blocks in parallel whereas in practice it going be 50 times the same thing so your TPS should actually go up when your number of validators go up right so that's a really good question and this something I'm looking into so to to so I have two answers the first answer is how people evaluate consensus algorithms so when people evaluate consens algorithms what we are trying to show in our graphs of course with very high throughput and very low latency is what is the performance of consensus as a blackbox meaning in this evaluation we don't consider about the meaning of transaction because what we are dealing with dealing with is just 512 byte random byte string so of course in a

practical system this will not be the case and let me tell you why it's it's it's it will not work like that in a practical system before you propose a new transaction if you don't validate it then you're actually going to propose garbage now this is going to affect a lot of uh properties in in in in in consensus like for example if you don't validate your transaction before you propose then the chain quality will be zero even if you have two3 of the good good players sorry what do you mean by validate transaction before you propose it um so I'm I'm referring to so um let me go back so in in a in in our deck or in any tag uh we just propose a block and when we have two f+ one blocks we just go to

the next round now in this block formation we don't really care about what's inside the block because what we care is just 512 by random string that that's the payload for us so obviously in a real system what I'm trying to say is obviously real system this will not work because if everyone just proposes a transaction from mempool then it will lead to the case where everyone will be proposing the same thing so the throughput will be high but the good putut will be very low because essentially everyone is proposing same thing uh but in practice when we evaluate consensus we try to isolate this we try to show this is the performance from the consensus as a layer but if you plug it into real system with your valid dat and with your application layer on top of it then

obviously when you have the validation before you propose it will be less than this but it's a standard practice for some reason we adopt in our in our chain of research so doing things that way if everyone doing dag based protocols do the same thing you can compare one dag based protocol to another but now I want to know if I'm going to implement hot staff or D based protocol the numbers are meaningless uh well if you look at how so even in hot Stu uh so in hot stuff to commit a block you need to have the these three ch CH meaning you need to have three consec three consecutive blocks to commit the first block now in that case it's really possible that the second block will have the duplicate

transaction so even there the problem is you don't validate the transaction before you propose and the reason is we are just measuring the consensus now in a real setting this is not the case and I do have some numbers not for this but for H stuff where if you just let any transaction to be included in the block you get a throughput around 50,000 requests per second under 2 seconds however if you validate before you propose by validating I mean are there any duplicate transaction in my previous blocks which I should not include in this block then your throughput is going down around th000 request per second so in reality this is the case but in practice when we evaluate cons protocol this is how we do because we want to

show what's the performance of consensus just as single blackbox not as a connected component between the but I'm happy to take more questions if you have thank you very much so in case you have any questions uh feel free to come to our speaker afterwards thank you very much for listening us and thank you very much for this insight [Music]