Introduction to Consensus

Transcript

hi hi my name's Dominic once I founder of just a research project called affinity which seeks to advance blockchain technology with a particular focus on scalability in the process of doing that we look at many different types of distributed algorithm and in particular many different types of consensus algorithm and in the crypto space we often spend a lot of time talking about block chains and block chain like consensus systems and think the purpose of my talk is to introduce another form of consensus which has been

around for longer Luna's byzantium fault tolerant consensus which is based on message passing so I'm going to try and do this in 20 minutes which is kind of challenging but I want to just give it a give you a fear of some of the issues involved and what these kind of consensus protocols look like so first of all quickly it's worth just asking the question we already have block chains so so why bother ways complex can concerns as protocols and the answer is they're useful for creating scale-out crips alleges that's crypt alleges that increase their transaction throughput as

more nodes join the network so you know the objective of the research effort is to transport the creation of sort of limitless to centralize clouds that can be used in the case of an open decentralized virtual machine like etherium to run you know gmail goober Facebook Twitter that kind of thing internet of things services layer and so on and the most of the three different kinds of decentralized system that I'm interested in one is the open decentralized systems like Bitcoin and athyrium also federated decentralized systems as of the type that banks are currently creating for

settlement of clearing and also think actually the centralization is a completely new computing paradigm and we're going to see it within the enterprise so people are going to create to centralize databases which highly fault tolerant because you know that's where the design they easy to administer because they're symmetric every server involved has a similar role there is no kind of master slave arrangement like you see in mysql databases or something like that and once these decentralized networks can scale multi-party computation can be introduced to secure the data inside them so you probably all

heard about the hacks that target in America and the Office of Personnel Management I think in the UK Talk Talk has just lost a lot of customer data I think we're going to see you know enterprise decentralized databases where the data is distributed across a large number of different servers and you can only access it by running running authorized requests which access the days are in a certain way you can ask when you can run a query against the day to say but you can't retrieve all the data from the database so you know with with a and a decentralized enterprise database which is using NPC all of these kind of hacks that you hear about would their laundry possible so I think the more specifically for some

lesser sister probably in the long term I think that the scale out kind of systems will use a number of different kinds of consensus system in their overall network architecture and this is an architecture that I pursue and you can see at the very top level them it's got several layers you've got a master consensus layer you got a scalable validation there and you get a storage layer and at the very top level it's going to block chain like it's going to watching it may not use proof-of-work could use something like Casper or it could use something else altogether but that's only one component of the overall

network we also have this validation layer and we have a storage layer and these green dots these represents traditional consensus processes that are being run because for various reasons it's very difficult to create strongly consistent master chain that is if you're very large number of nodes imagine if you had a million nodes in a distributed virtual machine be very difficult to have strong consistency at that level so if if the master chain can reorganize itself and drive other changes lower low down we don't want to have weekly consistent to be you know composing weekly consistent consensus

process is further down so you know consensus really does have a really important role to play in creating these kinds of network and in this diagram here these green dots are in fact traditional consensus instances soon what is the sort of xan team consensus challenge very basically you've got a bunch of nodes that are connected by some kind of network here are cool man processes so I'll try and use that non closure and then you'll have a value that they want to propose and they've got to agree on this value and the

important point is that some of these most of these nodes are correct which means they follow the protocol but some of them are faulty and that means they can behave completely arbitrarily which is what is meant by presenting so what is Byzantium consensus so I it's the easiest way to think about it is as a game the correct processes run this protocol and try and reach agreement by sending and receiving messages meanwhile the faulting processes which are controlled by anniversary try to either prevent consensus being reached or to make correct nodes decide invalid values that is think they've reached agreement

on something that they happen so on these 1402 processes what can they do their Byzantine and what that means is they can adopt arbitrary tactics they can just decide to crash and fail they can corrupt data and messages they can subtly subvert the communications protocol and they can coordinate their their actions so they really can do anything at all depending on the model that's being used the adversary can also do things like controlling the control the scheduling and messages right it can impact the network he may have full information about process States and he can during the consensus protocol you

can corrupt correct nodes at will so just to clarify what consensus is the first of all consensus is agreement here we have network of just four nodes the green ones are correct and the red one is faulty and the green cracks nodes all start off wanting to propose different values and after consensus is run they've all agreed on the same value XYZ and that's I guess pretty intuitive agreement source of validity noting in this case means that if all the nodes start off proposing the same value then

they decide that same value and there's two forms of this actually there's there's week validity which requires that every single and process starts off proposing the same value and the strong validity which requires that only the correct processes need stop to start off proposing the same value anyway in this diagram here all of the processes have started started off proposing and mo and after consensus all of the correct processes have decided an NM o of course the faulty process has come up with XYZ it could be anything it's faulty it can do what it likes can behave arbitrarily

so this is um an important one consensus is also termination or what that means is that the before contentious protocol that it would eventually terminate it can't go on forever that's a valid consensus protocol has has to terminate so as you probably guessed listening so far as there are actually many different models that these consensus protocols are designed to work for and so here some of the main ones first one is network behavior

and generally speaking consensus protocols are divided into synchronous consensus protocols and partly synchronous consensus protocols and asynchronous protocols and in synchronous protocols the network is assumed to deliver messages within some bounded predictable time and in asynchronous networks there are no timing assumptions whatsoever so and this actually is kind of realistic for the internet right you can get arbitrary partitions a correct node can be deduced right and the second one of course is the fault type so this is a pretty

oversimplification but the pretty heaven consensus algorithm called pack sauce anyone it so use it was use it's used in like Google chubby and thanks possibly zookeeper and things like that so it's a consensus algorithm where the only kinds of faults that are handled a crash fault so it can deal with processes crashing but it can't deal with them behaving arbitrarily and of course the wider set of fault fault types is presenting where processes can behave up too early so if there's anything just to take from this this useful it's that obviously if a consensus protocol is byzantium fault

tolerant it's resistant to a far greater number of faults right I would you folds of fact and works within a synchronous network that's better because it's not vulnerable to you know correct process being dido store something or that or the network just behaving strangely so just to talk about challenges but more I think one of the reasons these kind of protocols are complex is that in fact of course the state of the network is unknowable and it's easy to forget that because you always see a network diagram which shows lots of connected

nodes and some of them are correct and some of them are faulty but it but in actual fact nobody can know what the state of the network is right you can only make inferences about the current state of the network based upon the messages you receive and that's equally true actually for these kind of consensus protocols as it is from blockchain based consensus protocols you've got no way of knowing what be the overall state of the network is you can only make inferences about it based upon the messages you receive now you can send messages out to ask questions and you may or may not get answers but you can only make imprint inferences the network is a black box another big challenge is equivocation by faulty

nodes and again this applies to protocols like Casper Ola this is again as assuming a traditional consensus protocol and equivocation simply means that faulty nodes can send two different versions of a message when there any men or men ascend one so in this case process one is is faulty and it's telling process to that it's voting ABC and it's telling process through that it's voting NO and equivocation is a surprisingly powerful tool for anniversary to use can kredel kinds of problems and as a result that comes from

this which is that typically to reach consensus when you receive a message from a process you need to echo it to all the other processes to make sure that that it hasn't been equivocating and this kind of leads to quadratic message complexity which basically means that as the number of processes cooperating in consensus increases the number of messages they send increases with the square of the number of processes and that's the reason why Satoshi creatives the proof of work blockchain because it doesn't have this problem ok has a different works in a different way that people try and solve

puzzles and whoever solves the puzzle gets to cast a deciding vote right and you don't get strong consistency you get a sort of it eventual consistency as them as the chain gets longer and block gets buried deeper and deeper it gets more and more likely to be permanent so that's the limitation of this kind of protocols the number of messages they have to pass increases with the the square of the number of processes involved and so consequently they tend to be used within a larger protocol as we look sat at the beginning so here's another challenge this is network asynchrony and this is actually probably the most profound challenge of thing

which is there's no way of knowing if the network can pave it in a synchronous way why you haven't received a message so in this case he too is expecting a message from p1 ok and it hasn't received a message from p1 ok so what is p2 mother think does it continue waiting for the message from p1 so there's a system called ripple she probably all aware of and they had a consensus protocol which didn't handle a synchrony correctly and it was adopted by another cryptic article Stella and it was

absolutely plain from the way they described the the protocol that I had this issue of the synchrony that it would just make an assumption that it hadn't got a message because the sender had failed ok and as a consequence they had a day out of four so it's very easy to just imagine what haven't received a message the sending us to fails therefore I'm going to proceed with the messages i have and assume that some some part of the network's faulty but it can lead to problems so of course you know an adversary realizing that the receiver doesn't know what to do can use this as a tool you can decide to withhold

messages right and there is a kind of prefer issue that comes from that so what is the you know the maximum number of faulty processes that these kind of consensus protocols can handle and there's no easy way to think about it perhaps this is the easiest there's a thing called the Byzantine poorer and a Byzantium quorum is a subset of nodes so chosen that if two different forums are selected they will always intersect in at least one correct node and this means that you can chain operations together

and produce some kind of result or inference and so we can see here there's seven here are seven notes and these two quorums intersect there are two forums here of five nodes and you can see they both intersect in one node even though both of the quorums have selected the two faulty nodes and anyway this area there's a general result which is the the the must be less than the number of faulty nodes must be less than a third right so less than a third of the processes participating in the consensus algorithm must be faulty for the thing

to be able to reach a correct result and the issue there is that one of the one of the issues one of them other things were thinking about is that if we cannot wait for all of the messages so let's say you know they're there n processes and the consensus protocol in this case there are seven and we know up to two of them can be faulty right once we've received five messages right five messages do we wait and see if we can receive another two right there's evil 7 we can't write because the remaining two messages we haven't received may be

coming from faulty nodes and the faulty nodes may just decide not to send these messages to make to make us wait forever right so these kind of protocols need to proceed when they've received two F plus one of the messages which has another side effect which is that of course it may be that the F messages that we didn't wait for in this case to two messages we didn't wait for we're actually from correct processes and we've received two messages from faulty processes in which which means that we can only be sure f plus 1 messages from those who have collected from correct

processes and that's why it's kind of complex so I'm at a time so you're saved I was going to try and walk you through in a synchronous protocol but i'm at a time but if anyone's the deck ping me and have it thank you so much