A series of back and forth comments between the developing team behind the EOS new consensus mechanism, the DPOS BFT and the Co-founder of Ethereum, Vitalik Buterin took place on EOSIO GitHub. The claim by EOS developers’ team that their approach combining DPOS and BFT will not lead to the existence of two different finalized blocks at any time, by two different nodes (known as falling out of consensus) was questioned by Vitalik. He clearly addressed his concerns about the safety of the algorithm put forth by EOS, and advised them to “just use the algorithm in Casper FFG.”
What is Consensus?
The inherent tamper-proof nature of Distributed Ledger Technology DLT makes it probably one of the most significant technological breakthroughs when it comes to decentralized data sharing and processing in the last decade. In fact, when a transaction is broadcasted to the network, an “agreement” on its immutability has to be reached among the majority of network nodes, so that it can be added to the bundled encrypted series of transactions forming a block. This process is commonly referred to as consensus. However, the existence of malicious Network nodes that may alter data is a fundamental problem that may affect the overall system’s reliability. That being said, a consensus mechanism should be fault tolerant, but only to a certain extent.
The two Generals problem and the Byzantine Fault Tolerance
Let’s consider the following simple scenario: Two Generals attacking a common enemy.
While General 1 is the leader, and General 2 is the follower, both generals need to concert their efforts and launch their offensive at the same time, to successfully defeat the enemy.
General 1 has to communicate to General 2 the exact time of the attack by sending a messenger. There is a possibility that the messenger gets caught by the enemy, and that the message never gets through. Even if the messenger delivers his message, General 2 has to acknowledge (ACK) receiving it by sending a messenger back, yet repeating the same scenario. This extends the issue from an algorithmic point of view to an infinite loop of ACK’s where agreement cannot be reached. This Two Generals problem published first in 1975 was proven to be unsolvable.
Now if the Two Generals paradigm is extended to more than two allies (Commander-lieutenants) trying to defeat a common enemy, It becomes the Byzantine Generals problem. To achieve consensus the Commander and all Lieutenants must agree on the same decision and execute it accordingly at the same time. The issue is addressed in the flowing paper where Lamport, Shostak, and Pease, mathematically prove that consensus can be safely reached as long as 2/3 of the setup actors are honest.
Byzantine fault tolerance derived algorithms, tolerate the class of failure that belongs to the Byzantine Generals problem. They have already been adopted in nuclear power plants’ designs, airplane engine systems, aerospace engineering systems and so forth. It all boils down to a simple principle: consensus can be reached as long as the total number of malicious nodes, or “traitors” in a Commander-Lieutenants paradigm, does not exceed one-third of the total node delegates.
DPOS 3.0 BFT and the two finalized block issue
Decentralized ledgers are not controlled by a central authority from an architectural point of view. A solution to keep away bad network actors from hacking through the process is at the heart of the value proposed by the technology. Different consensus algorithms have been studied and implemented since the launch of Bitcoin’s Hashcash Proof-of-Work algorithm. The latest hybrid PoW/PoS Casper FFG just made public by Ethereum, HashGraph, and Tendermint, tends to optimize on a probabilistic solution to the Byzantine Generals problem described above. In their paper about the DPOS 3.0 version, EOS developers’ team claim to be introducing Inter-Blockchain Communication (IBC) to allow one chain to efficiently prove to another chain that a transaction is finalized, and had been made irreversible; the next block should start from that point, or head. Once finality occurs, reversal should not take place. In fact, the main idea behind this recent update is to make a node-validator disclose whether he/she previously confirmed an alternative block, so to make sure non-byzantine block producers cannot produce blocks on different forks at different times. However, Vitalik argued that having two finalized blocks at the same time built from a single head can still occur while reaching 2/3 byzantine tolerance.
He gave a counterexample in the discussion thread and concluded that:
“it’s not possible to achieve BFT safety on a block without at least two messages from most nodes that directly or indirectly reference that block.”
He claims that doing that safely in one round is “likely impossible to be safe.”
After a couple of exchanged messages, Daniel Larimer concluded by saying:
“After talking this over with Bart and Arhag we have concluded that a small tweak to our current algorithm will resolve this […].
- [Vitalik Buterin, Editor’s note] is right that you require double-confirmation and that our attempts at circuiting it result in edge case failures”.
The thread has been closed ever since, and a medium post by Larimer was published the following day May 15th detailing the DPOS BFT optimized consensus mechanism.