Abstract
In 1985, FLP Theory was proposed in a paper written by Fischer, Lynch and Patterson. FLP Theory proves that in a completely asynchronous distributed system, no completely asynchronous consensus protocol can tolerate even a single unannounced process death.
In 2002, Lynch and Gilbert put forward CAP Theory in their paper. Cap Theory proves that in a distributed system, it is impossible to achieve all three properties: consistency, availability, and partition tolerance, at the same time. Only any two of these three properties can be achieved at the same time.
As a typical distributed system, FLP and CAP are also applicable to the blockchain. Based on FLP Theory and CAP Theory, this paper will analyze the logical relationship between consistency, availability, partition-tolerance and the trilemma of the blockchain, so as to explain why the impossible triangle of the blockchain can’t be broken through.
1. Summary of FLP Theory
In April 1985, FLP Theory, demonstrated by Fischer, Lynch and Patterson, is one of the most important distributed system theories. They also won the Dijkstra Paper Award, the most influential award in the field of distributed computing, for their paper on FLP theory.
FLP theory proves that in asynchronous communication systems, no consensus protocol can completely solve the consensus issue in spite of one faulty process.
In a synchronous system, consensus can be achieved. This is because in a synchronous system, when a process fails or a response times out, we can assume that it has crashed.
While in an asynchronous system, it is impossible for one process to tell whether another has died or is just running very slowly. In this case, if there is a problem with any of the processes, there is no distributed algorithm that can make all non-faulty processes reach a consensus.
Due to the limitations of FLP impossibility, the consensus algorithm of most blockchain projects presupposes that most nodes are honest and meet certain synchronization. PoW assumes that 51% of the nodes are honest and have some degree of synchronization. PoS and PBFT also believe that most nodes (66%) are honest.
2. Summary of CAP Theory
At the symposium on principles of distributed computing (PODC) in 2000, computer scientist Eric Brewer proposed his conjecture about the consistency, availability, and partition-tolerance of distributed computing systems. In 2002, his conjecture was proven by Nancy Lynch and Seth Gilbert, two professors at the Massachusetts Institute of Technology, and was called the CAP Theory.
CAP Theory proves that it is impossible to provide reliable atomic consistency data when the network is partitioned, while it is feasible to achieve any two of the three properties: consistency, availability, and partition-tolerance. in an asynchronous communication system, when no lock is used, there is no way to provide consistent data even if stale data is allowed to be returned when messages are lost. In a synchronous communication system, there is a tradeoff between consistency and availability.
2.1. Consistency
In CAP theory, consistency is limited to atomic data objects, which is the same as most other methods that formally define consistency services. A system that satisfies the consistency has a total order on all operations such that each operation looks as if it were completed at a single instant. This requires that all requests from the distributed system must be synchronized before operations can be performed. This is equivalent to requiring requests of the distributed share memory to act as if they were executing on a single node, responding to operations one at a time. This is the easiest consistency assurance model for users to understand and is most convenient for those attempting to design a client application that uses distributed service.
2.2 Availability
For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response. that is, any algorithm used by the service must eventually terminate.
In the argument of CAP theory, availability is defined as two types:
1. Weak availability: It puts no bound on how long the algorithm may run before terminating, and therefore allows unbounded computation.
2. Strong availability: Even when severe network failures occur, every request must terminate.
Under weak availability conditions, the system is allowed not to guarantee response time, but the response is a must. When the system has an error, it does not guarantee the termination of the request. In the case of strong availability, the request must terminate even if a system error occurs.
2.3. Partition Tolerance
In CAP theory, partition refers to the possibility of losing arbitrarily many messages sent from one node to another in a network. When a network is partitioned, all messages sent from nodes in one component of the partition to nodes in another component are lost.
Partition tolerance refers to the fact that the system still meets the consistency and availability as defined above when a partition occurs. the atomicity requirement therefore implies that every response will be atomic, although arbitrary messages sent as part of the algorithm might not be delivered. The availability requirement implies that every node receiving a request from a client must respond, although arbitrary messages that are sent may be lost.
3. Using CAP theory to explain why the impossible triangle of the blockchain can’t be broken through.
In the field of blockchain, security, scalability and decentralization are known as the “impossible triangle” of the blockchain, which means that in the same blockchain system it is impossible to achieve all three properties and meet the high requirements at the same time.
Our basic argument is that CAP theory is true in a distributed system, and the blockchain belongs to a distributed system, so blockchain must abide by the CAP theory. As long as we can prove the logical relationship between consistency, availability, partition tolerance in CAP theory and the impossible triangle of the blockchain, then we can prove that the impossible triangle of blockchain cannot be broken through.
3.1. Consistency and Security
In the proof process of CAP theory, it is proved that it is impossible in the asynchronous network model to implement a read/write data object that guarantees both availability and consistency. We apply this conclusion and proof process to the blockchain system.
In the network environment defined by CAP theory, we assume that there are two Nodes A and B in a blockchain system, and both A and B record the cryptocurrency balance of one Address H as X1, now A and B are partitioned.
When the user initiates a transaction in the partition where node a is located, the balance in address H will change to X2. When the user queries the balance in the partition where Node B is located, the balance in address H is still X1. Thus we reckon that in this blockchain system, the inconsistency occurs in the ledge.
When inconsistency occurs in a blockchain system, we conclude that such a blockchain system is not secure. Under this definition, consistency is the basic premise of blockchain system security. In other words, the security of blockchain systems is a more stringent requirement than the consistency of distributed systems. Security >consistency.
3.2. Availability and Scalability
The availability in CAP theory is divided into weak availability and strong availability, but both require that the system must respond to all normal requests. From a technical point of view, that means to implement normal read and write.
In a blockchain system, scalability refers to the number of transactions that can be processed per second. Technically, high scalability is to achieve high-frequency read and write operations per second.
Logically, we can see that availability is a more fundamental network requirement than scalability. A blockchain system that cannot achieve availability is unable to achieve scalability, that is, availability is the premise of scalability. In other words, the scalability of blockchain systems is a more stringent requirement than the availability of distributed systems.
Scalability > Availability.
3.3. Partition-tolerant and Decentralization
In CAP theory, partition is considered to be a must exist for distributed systems. Indeed, in a real distributed environment, it is impossible to guarantee that every node in the system will not fail.
As a basic feature of the blockchain, decentralization means that the blockchain system must be distributed, that is to say, decentralization will inevitably lead to the partition, which also means that the partition tolerance is the premise for the realization of decentralization.
3.4. Balance of Existing Consensus Algorithms on CAP
In CAP theory, partition is considered to be an inevitable presence of distributed systems, so it makes no sense to discuss a distributed system without partition. As a typical distributed system, the different consensus algorithms of blockchain have balanced the consistency and availability of the system under the premise of the partition.
Tendermint: Tendermint is a PoS-type consensus algorithm, which mainly includes five stages: Newheight -> propose ->prevote ->precommit ->commit. propose ->prevote ->precommit belongs to the consensus phase and is the core of the algorithm, which is called a round. Multiple rounds may be required on a single block for block commit confirmation. in multiple rounds, the height of the block will not increase, only empty blocks are submitted to the system, and once a block is confirmed, it cannot be modified. So Tendermint could theoretically get stuck, which results in the block height never increasing. This means that Tendermint is more focused on consistency when there are partitions.
Casper FFG: Casper FFG is a PoS-type consensus algorithm. In the design of Casper FFG, consistency is a priority because it doesn’t allow checkpoints to be completed without the approval of the vast majority of verifiers, so that the block will not turn into the final confirmation state.
Algorand: Algorand is a PoS-type consensus algorithm. Algorand is similar to Tendermint in the design. When there is a conflict between consistency and availability, the system tends to produce empty blocks rather than blocks of real significance. So Algorand gives priority to consistency.
Dfinity: Dfinity is a PoS-type consensus algorithm. When the network is partitioned, it automatically suspends the random beacon and does not allow any partitions in the network to continue. so Dfinity prioritizes the consistency.
PoW: When the network using PoW is partitioned, all partitions can produce blocks normally. When the network is restored and the partition ends, according to the longest chain principle, chains of different partitions will be merged and eventually become one chain. So PoW prioritizes the availability.
PoC: The full name of PoC is proof of credit, which is innovatively used in NULS, a global open-source and community-driven project. When the network using PoC is partitioned, all partitions can produce blocks normally. When the network is restored, similar to the PoW, the blockchain will be merged following the longest chain principle. Therefore, the priority of PoC innovatively used by NULS is availability.
Note: A < C represents that the consensus algorithm gives priority to consistency;
C < A means that the consensus algorithm gives priority to availability;
4. Conclusion
By deducing the above logical relationships between consistency and security, availability and scalability, partition-tolerance and decentralization, we can draw the following conclusion:
1. Consistency is necessary for security.
2. Availability is necessary for scalability.
3. Partition-tolerant is necessary for decentralization.
According to the theorem in CAP theory that it’s impossible to achieve all three properties: consistency, availability and partition tolerance, we can draw the following conclusion: Under the conditions of CAP theory, security, scalability and decentralization cannot be achieved at the same time, that is, the impossible trilemma of blockchain cannot be broken through.
About the author:
Ken Huang
A well-known blockchain expert, chief scientist of Nuchain, American Distributed Apps CEO, Member of blockchain experts committee of Chinese Institute of Electronics and NULS technical advisor.
Xiang Wenbo
Java software engineer, crypto-tech-writer and NULS core team member. He focuses on blockchain technology research and blockchain solutions.
References:
Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-tolerant Web Services; Seth Gilbert, Nancy Lynch
Impossibility of Distributed Consensus With One Faulty Process; Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson
CAP Theory for Distributed Systems: https://www.hollischuang.com/archives/666
Compare the Finality and Liveness of Various Consensus Algorithms:
https://www.odaily.com/post/5134107
Finality in Blockchain Consensus:
Https://Medium.Com/Mechanism-Labs/Finality-In-Blockchain-Consensus-D1f83c120a9a
