During the early 80s, Lamport, Shostak, and Pease (listed in no particular order) initiated the study of reaching consensus in face of Byzantine failures and designed the first Byzantine Fault Tolerance (BFT) protocol for synchronous (sync) networks.
Since practical open networks, such as the Internet, are normally not sync, researchers started to look for BFT protocols for async networks. In 1985, Fischer, Lynch, and Paterson showed that there is no deterministic protocol for the BFT problem in the face of a single failure in an async network.
After this setback, researchers sought to model our Internet as a partial sync network instead of complete async. With this motivation, Dwork, Lynch, and Stockmeyer (DLS) introduced two types of partial sync networks (Type I and Type II) and proposed the first DLS BFT protocol for Type II in 1985. DLS protocol has an authenticator complexity of O(n4) and it is not practical.
Since then, researchers have been trying to propose more efficient BFT protocols in Type II partial sync networks.
DLS protocol leverages a star network, where participants only exchange messages via round leaders. By adopting a meshed network (that is, allowing all participants to broadcast their messages to all other participants), Practical Byzantine Fault Tolerance (PBFT) protocol was able to achieve consensus with reduced round complexity. By leveraging the lock-mechanisms in PBFT/Tendermint BFT protocols and changing the mesh network back to star network, HotStuff BFT/LibraBFT achieves consensus with reduced communication complexity but increased round complexity.
Until most recently, the Sperax team carried a careful analysis of all these BFT protocols for Type II networks and designed the BDLS BFT protocol (B stands for blockchain) with both reduced round complexity and reduced communication complexity.
Specifically, BDLS has the same round complexity as PBFT and the best linear communication/authenticator complexity. For example, when threshold digital signature schemes are used, HotStuff BFT/LibraBFT achieves linear authenticator complexity with 7 rounds; BDLS 3 rounds and the original DLS achieves O(n3) authenticator complexity.
The original DLS protocol was designed by Dwork, Lynch, and Stockmeyer. Two of them received the Knuth award, the most prestigious for researchers focusing on the foundations of computer science. In 2007, the DLS paper received the Dijkstra award for its pioneering contributions to distributed computation.
Hard to ensure unpredictability and verifiable fairness of node identity
In a PoS based consensus protocol, validators are selected to generate or vote for new blocks based on whether they satisfy certain conditions. These conditions are generally determined by the coins each node controls on the network. It is important to ensure the fairness of selection. However, though quantities like future block hashes, block difficulty, or timestamps seem to be ideal sources of randomness on chain, they are vulnerable to manipulation by miners.
Secure and Unpredictable random beacon or RANDAO
RANDAO not only has the characteristics of unpredictability, but it is also more accessible and provably fair. RANDAO’s protocol adopts a commit-reveal process that presents a joint random number, generated from the random strings committed by various participants in a given window of time. After a user gets this shared random number via RANDAO, one can then generate his/her own random number via some hash function.
Hard to design a secure protocol in the open internet Environment
Most current BDLS protocols apply the gossip-based broadcast protocol, based on the existence of reliable peer-to-peer communication channels, for any pair of participants one might select. This requirement is generally equivalent to a complete network topology that only exists in closed environments. This assumption is definitely not the case in more realistic scenarios on the open Internet where we interact. Open networks are particularly susceptible to DoS attacks.
Security design in the type II partial synchronous networks
Among partially synchronous networks, there are two widely accepted main types, illustrated here. In the type II network, a realistic one, Denial of Service (DoS) attacks are allowed and no reliable broadcast channels are assumed before GST. We may assume that the network alternates between good and bad synchronous periods. SperaxBDLS adopts block-lock mechanisms & block self-proof mechanisms to ensure security against such potential forks, proving liveness and safety of the BDLS protocol.
Hard to handle the problem of deadlock in a partial sync network
Liveness guarantees that all the nodes eventually agree on some value and move on. However, in the realistic network, many attacks can be launched in the format where a malicious leader sends different messages to different nodes. Some popular BDLS protocols may reach deadlock when the network is partially sync. This deadlock is not resolved when the network regains synchronization because their liveness is not robust enough to survive in a realistic Internet environment.
High efficiency consensus algorithm design
Scalability is one angle to evaluate blockchain systems. Another way is to understand the complexity of the messages passed. Although in general the performance of PoS consensus varies with the implementation, it can also be evaluated on the order of O(n2). In terms of the communication processes in SperaxBDLS however, there are only two unicast and two broadcast processes, with a O(4n) message complexity, which contributes to a linear consensus efficiency.
Four participants & one bad guy. An agreement is achieved.
- We have four participants
- Every one has a block (the bad guy may have more and send more to different people)
- They want to agree on a block. At the end of the protocol, all honest guys should have the same block
Three participants & one bad guy. No agreement can be achieved