Distributed consensus
The technological research which changes it all
Ever wondered how sending and receiving money is such a simple process, also a coherent one, where you are just contacting your account through a device for doing a transaction. But it is not that simple and definitely not one single system. It uses distributed systems where many nodes are connected to perform a unified goal. Nowadays after the advent of blockchain, there has been a breakthrough in distributed consensus so let’s try to understand it in simple terms.
What is a distributed system?
A distributed system is a group of computers working together to achieve a unified goal.
What is a consensus?
Agreement of nodes in a system. Nodes are different components that work together to achieve the goal.
What are the properties of the distributed system?
- Concurrency.
- Global clock
- Independent of component failure
- Message passing
Concurrency
In the current world of computers, the data is transferred at a high rate, so many things happen simultaneously and this is what is meant by concurrency.
Global clock
For a distributed system it is hard to layout the correct order of the system due to the lack of a globalized clock. Further, as the computers are spatially distributed so it is impossible to say that one of the two events occurred in what order.
Leslie Lamport Solved this problem by considering 2 things in his paper of “Time, Clocks and Ordering of Events in a Distributed System
- Messages are sent before they are received.
- Each computer has a sequence of events.
Lamport’s paper describes an algorithm that requires each computer to hear from every other computer in the system. But this can have the system to cause anomalous behavior as in situations where this order differs from what a user external to the system perceives. Finally, Lamport discusses how such anomalies can be prevented by using properly synchronized physical clocks.
Independent failure of components
No system is fault free and there can be many reasons for the same like messages being lost, disorientation, delaying, processing, byzantine; etc.
It’s impossible to have a system free of faults.
Message passing
The is one of the most important features of the distributed system so there can be communication between 2 computers.
There are mainly 2 protocols for message passing one is Asynchronous and the other is Synchronous.
Synchronous
Messages are delivered in a fixed time or they won’t be delivered at all but are not practical because all the nodes are not always online.
Asynchronous
It takes infinite time to send the messages thus leaves with no upper bound on how long a message will take to be received.
So these were the properties till now but now how do you make out what is the biggest difference between system and consensus. A consensus algorithm achieves consensus if all the Non-faulty terminals should reach the same agreement, and eventually, they should reach an agreement on the same output value.
What is a distributed consensus?
Agreement of computers over a set of stored data in real-time where entities may not be in the same place altogether.
The most common architecture of software and hardware for reaching a consensus is
Replicated State Machine
In a replicated state machine if a transition is valid then some set of inputs let it to the next state. These operations are either complete in full or never complete at all.
In other words, a replicated state machine is a set of distributed computers that all start with the same initial value. For each state transition, each of the processes decides on the next value, and Reaching “consensus” means that all the computers must collectively agree on the output of this value.
Consensus algorithm
In a consensus algorithm there are mainly 3 actors:
- Proposers are often called leaders or coordinators.
- Acceptors, processes that listen to requests from proposers and respond with values.
- Learners, other processes in the system which learn the final values that are decided upon.
How does the consensus algorithm work?
The first algorithm elects a proposer and the proposer gives the next value. Now the nonfaulty systems vote on the value given by the proposer this is called the voting phase. In the deciding phase, the non-faulty systems should agree on one output and a threshold no. of votes should favor the consensus or the process starts against and continues till consensus is reached.
Now comes FLP impossibility
This is a game-changer type of thing for distributed consensus. We can’t use synchronous platforms for a distributed system because in the real world they are not practical. In reality, most environments don’t allow us to make the synchronous assumption. So we must design for asynchronous environments.
So we need an asynchronous environment and we need to determine the maximum time it should be given to send the message. This makes it almost impossible because even one faulty process can make it look really bad as the termination is an important condition for consensus.
Why it is called FLP
Even a single faulty process makes it impossible to reach a consensus among deterministic asynchronous processes.
To Avoid this Condition there are 2 ways
- Use synchrony assumptions.
- Use non-determinism.
Synchrony Assumption
In simple terms, we assume the time limit as the average of whatever the nonfaulty nodes are taking if some node is taking more than the average time we declare them faulty and they don’t need to terminate at all. This concept is middle of synchronous and asynchronous. But there is one thing that makes the work more difficult that is Byzantine Systems.
Byzantine systems are malicious systems that work of their own will.
As we know all the non-faulty nodes should terminate and should give the same output a byzantine system will disrupt the whole network so to make a system byzantine we use the byzantine formula.
The paper “Byzantine Generals Problem” by Leslie Lamport, Robert Shostak, and Marshall Pease provided the first proof to solve the Byzantine Generals problem: it showed that a system with x Byzantine nodes must have at least 3x + 1 total nodes to reach consensus. The proof being
If x nodes are faulty, then the system needs to operate correctly after coordinating with n minus x nodes (since x nodes might be faulty/Byzantine and not responding). However, we must prepare for the possibility that the x that doesn’t respond may not be faulty; it could be the x that does respond. If we want the number of non-faulty nodes to outnumber the number of faulty nodes, we need at least n minus x minus x > x. Hence, n > 3x + 1 is optimal.
So a system should be Synchronous and Byzantine tolerant that's a bummer. For a system to be both it will be just a miracle.
So what we do, we have to make a Byzantine + asynchronous system, thus we look at 2 algorithms that are DLS and PBFT.
DLS
D L S (Initials of researchers) introduced a major advancement in Byzantine fault-tolerant consensus: it defined models for how to achieve consensus in “a partially synchronous system.”
- Assume that fixed bounds exist for how long messages take to get delivered. But they are not known a priori. The goal is to reach consensus regardless of the actual bounds.
- Assume the upper bounds for message delivery are known, but they’re only guaranteed to hold starting at some unknown time (also called “Global Standardization Time,” GST). The goal is to design a system that can reach consensus regardless of when this time occurs.
So it introduced 2 things First safety and second liveness
Safety
This is another term for the “agreement” property we discussed earlier, where all non-faulty processes agree on the same output. So there is no point in having a malicious node because it is agreed as in unity.
Liveness
This is another term for the “termination” property we discussed earlier, where every non-faulty node eventually decides on some output value. In a blockchain setting, “liveness” means the blockchain keeps growing by adding valid new blocks. Liveness is important because it’s the only way that the network can continue to be useful — otherwise, it will stall.
The problem with DLS
If a system isn’t deciding on an output value the system will just halt so we need timeouts. But if we make timeouts this carries the risk of leading to two valid transaction logs if the synchrony assumption fails.
But the latter is worse than the former because having 2 blockchains is impractical and disruptive thus despite everything that the DLS paper offered, DLS was never widely implemented or used in a real-world Byzantine setting.
The PFBT Algorithm
In a nutshell, the PBFT algorithm showed that it could provide safety and liveness assuming (n-1)/3 nodes were faulty. As we previously discussed, that’s the minimum number of nodes we need to tolerate Byzantine faults. Therefore, the resiliency of the algorithm was optimal.
If the leader (proposer) was non-faulty, the protocol worked just fine. However, the process for detecting a bad primary and reelecting a new primary (known as a “view change”) was grossly inefficient. For instance, to reach consensus, PBFT required a quadratic number of message exchanges, meaning every computer had to communicate with every other computer in the network.
While PBFT was an improvement over previous algorithms, it wasn’t practical enough to scale for real-world use cases (such as public blockchains) where there are large numbers of participants.
Due to this, there comes the concept of Non-Determinism. The Nakamoto Consensus
The Nakamoto Consensus
In the traditional consensus discussed above, every node should know every other node that leads to a quadratic overhead and thus decreases the efficiency. So Satoshi proposed rather than having communication to all nodes through one you can do it through probabilistic statistics i.e giving the output based on the highest probable answer.
Rather than electing a leader and then coordinating with all nodes, the consensus is decided based on which node can solve the computation puzzle the fastest. Each new block in the Bitcoin blockchain is added by the node that solves this puzzle the fastest. The network continues to build on this time-stamped chain, and the canonical chain is the one with the most cumulative computation effort expended. The longest chain not only serves as proof of the sequence of blocks but proof that it came from the largest pool of CPU power. Therefore, as long as a majority of CPU power is controlled by honest nodes, they’ll continue to generate the longest chain and outpace attackers.
Problem with Nakamoto consensus
The consensus is all about the tradeoff.
There has not been a big development in building a foolproof consensus. So you may ask what is the problem with Nakamoto consensus: it is byzantine tolerant and it solves the problem of synchronicity. The problem of double-spending. As we know the node having the highest computational power (hash power) person can start a new chain linking to the original and validate it all the way through having the majority computation power. Though the minimum computation power system would require is 51% that is really to achieve in today’s world because it is going to take a lot of equipment and infrastructure which costs a mammoth, but it can be done on paper at least.
Conclusion
Satoshi made a breakthrough in the world of communication through his model, which made it possible for further more research and having new models which are breaking new grounds because we should not forget this consensus was published 10 years ago and there’s an entirely new family of protocols being developed that go beyond Nakamoto Consensus.
The consensus was a big problem from the start of computation and now with each breakthrough, we are closer to solving that problem.
Anyways this was just a brief article on how consensus works and their history with human mankind.
Source:
