A recent blog post by Vitalik titled <A Guide to 99% Fault Tolerant Consensus> has led many to think that a new consensus algorithm like black tech has been born. However, as Vitalik himself said, this consensus algorithm is still the classic Byzantine general problem algorithm. Through analysis, we can see that the research and innovation of consensus algorithm still need to follow the proven theories such as CAP. On this basis, it is possible to apply all kinds of classic distributed algorithms and encryption algorithms to the blockchain field, and get good results.
1. Distributed system theory
In fact, before the birth of the blockchain, computer science had already done a lot of research on the consistency problem, forming a strictly proven distributed system theory. The more classical theories include FLP and CAP.
The principle of FLP impossibility is: "in a minimum asynchronous model system with network reliability and node failure (even if there is only one), there is no deterministic algorithm that can solve the consistency problem. "That is, the theoretical lower limit of the consistency problem is unsolved. There is no common algorithm that can be implemented in any scenario in an asynchronous distributed system.
The CAP principle is called the CAP impossible triangle, that is, consistency, availability and partition tolerance cannot be met simultaneously, and a feature needs to be weakened to design a distributed system. Therefore, under the premise of FLP impossibility principle, CAP principle provides theoretical guidance for engineering practice.
More generally than CAP, there are definitions of network environment characteristics in distributed systems theory: safety, liveness, communication unreliable. Distributed systems typically balance safety against availability.
2, The classic solution to the Byzantine general problem
This article will not elaborate on the description of BFT problem itself. In addition to the problems of the Byzantine general, Lamport et al. also provided two solutions in their classic paper.
The first is the OM(m) protocol for "oral messages", which means that no encryption algorithm is allowed except for the encrypted security on the link. The protocol requires a large number of messages to be delivered recursively between two parties, so the message complexity is high, is exponential, and is not very practical. However, this algorithm still has a high value. Firstly, it lays a foundation for the birth of the polynomial level complexity agreement, namely, Practical Byzantine Fault Tolerance. In addition, 1/3 of the fault-tolerant nodes are proved to be the theoretical upper limit of the algorithm.
The second is the SM(m) protocol for "encrypted messages." This algorithm is different from the first one in that it USES the signature algorithm. Each node can generate a non-forgerable signature that can be validated by other nodes. When a message is received, the node determines and verifies that the message has been received by signing. When the message is finally no longer received, the message consensus ends.
This paper has proved that the second algorithm can be fault-tolerant to any number of nodes (of course, the network should include at least two normal nodes, otherwise meaningless). The specific process can refer to the original paper.
However, this algorithm also has its limitations. Different from the hypothesis of many Byzantine algorithms in an asynchronous or semi-synchronous network environment, it is assumed to be carried out in a "synchronous" network, ignoring the communication delay between network nodes. In addition, signature identity system information needs to be determined before network operation, which is difficult to realize extension. Thus, according to the CAP theory, the approach is to achieve A high degree of consistency (C) and availability (A) without regard to tolerance for situations such as network partitioning (P).
3. "99% fault-tolerant consensus algorithm" and comparative analysis
In contrast, let's move on to what Vitalik refers to as the consensus algorithm invented by Lamport to describe and simplify the implementation (hereinafter referred to as the "implementation version"). The version in the Lamport paper becomes the "original").The implementation version still retains the original digital signature system, that is, each node can generate a non-forgery signature and can be verified by other nodes.
With the original version, in order to achieve the messaging between nodes, realize the timeout specifies the message version of the algorithm, namely node receives a message, check for news in addition to see if the signature has been received and in the collection, but also check the time should not be later than the signature of the received message corresponding to the time node.
After the specified time (calculated according to the number of rounds), the node will stop listening and select a value from the checked valid message as the consensus result according to some determined rule.
By comparison, we can find that there is no essential difference between the two algorithms. The essence of the two algorithms is based on the signature system. And Vitalik implementation version of the consensus algorithm increased the delay time requirements. This design implementation is frequently encountered when writing implementations of consensus protocols to determine the propagation cycle of messages and to ensure that message propagation can end within a specified time.
In addition, the implementation version also discusses the Observer as an independent role to pass messages across the network. The observer, acting as a passive viewer in the network, can receive, examine, and forward (unsigned) messages directly to other nodes. This needs to introduce a different delay time for the observer to solve the problem of malicious nodes intentionally sending messages to the observer late to make the normal messages time out.
4. Application and inspiration
As discussed above, the main problem of this kind of consensus method is the high demand for synchronization of network and poor scalability. Another drawback of the implementation version is that the amount of messages is also large (the process of sending messages from N nodes in round n-1 to other N nodes, that is, the message complexity is), so this kind of consensus method is more difficult to apply directly in the actual scenario.
In order to be more applicable to the blockchain field, Vitalik also mentioned in his article that this method can be combined with other current consensus algorithms (such as PBFT, PoS, etc.). For example, the algorithm can be run at intervals for some specific time. However, if the assumptions related to the two consensus algorithms cannot be satisfied, the consensus algorithm will also fail, that is, the improved optimization cannot violate the original theoretical system.
However, we can still get a lot of inspiration: fully exploring the classical theory of distributed systems and transforming it into a consensus algorithm applicable to the blockchain domain can achieve unexpected results. For example, PBFT combined with nakamoto consensus, and SM(m) algorithm in BFT paper proposed by Vitalik combined with existing blockchain consensus.
In addition, trying to apply a variety of encryption algorithms in the security field may also achieve good results. For example, for example, the use of encryption algorithms such as aggregated signatures to optimize the consensus mechanism is also being attempted by the likes of ByzCoin, which can greatly reduce the communication complexity.
my facebook：
https://www.facebook.com/bay.yu.988373， more question Contact me.
