DPOS BFT— Pipelined Byzantine Fault Tolerance
There are two general blockchain consensus systems: those that produce unambiguous 100% finality given a defined set of validators and those which do not provide 100% finality but instead rely on high probability of finality.
The first generation blockchain consensus algorithms (Proof of Work, Proof of Stake, and BitShares’ Delegated Proof of Stake) only offer high probability of finality that grows with time. In theory someone could pay enough money to mine an alternative “longer” Bitcoin blockchain that goes all the way back to genesis.
More recent consensus algorithms, whether HashGraph, Casper, Tendermint, or DPOS BFT all adopt long-established principles of Paxos and related consensus algorithms. Under these models it is possible to reach unambiguous finality under all network conditions so long as more than ⅔ of participants are honest.
Objective and unambiguous 100% finality is a critical property for all blockchains that wish to support inter-blockchain communication. Absent 100% finality, a reversion on one chain could have irreconcilable ripple effects across all interconnected chains.
The abstract protocol for these more recent protocols involves:
- Propose block
- All participants acknowledge block (pre-commitment)
- All participants acknowledge when ⅔+ have sent them pre-commitments (commitment)
- A block is final once a node has received ⅔+ commitments
- Unanimous agreement on finality is guaranteed unless ⅓+ are bad and evidence of bad behavior is available to all
What makes the various consensus protocols different are:
- Deciding when and who gets to propose a block
- Deciding how commitments are logged & communicated
- How byzantine behavior is documented
- Punishment for byzantine behavior
Some of these differences are political and some of them are technical in nature. Examples of political differences include:
- DPOS elects the set of proposers & validators based upon stake
- Casper relies on proof-of-work to determine when and who and when gets to propose and bonded-stake-weight to determine who the validators are
- DPOS punishes objective and subjective bad behavior by voting people out
- Casper only punishes objective bad behavior by slashing bonds
Under normal conditions, the political differences make no day-to-day impact on the experience of users relying on the consensus mechanism to order and finalize transactions. The threshold for malicious behavior is so high and the penalties so great that for all practical purposes it doesn’t happen.
It is the technical differences in the protocols that give rise to real-world impact on user experience. This includes things such as latency until finality, degrees of finality, bandwidth, and proof generation / validation overhead.
The simplest possible algorithm has everyone reach consensus on one block before any progress can be made on the next block. This involves every participant sending every other participant two messages per block. In a global network the speed of light limits the practical latency from time of proposal to the time a node receives ⅔+ commit messages to about one second (500ms round trip latency * 2 round-trips). All networks I have observed seem to be in the 2–3 second latency camp. These simple protocols also have a “timer” which introduces a new proposal if no consensus can be reached over the validity of the current proposal. This timer is generally longer than the expected confirmation time.
Protocols like Casper attempt to minimize the overhead by relying on proof-of-work for short-term consensus and only reaching finality over every 100th block (checkpoint). This means Casper-based chains reach finality every 20 to 30 minutes.
DPOS BFT Pipeline Consensus
Modern Delegated Proof of Stake with BFT as implemented in EOSIO uses a pipelined approach to deliver the proposal, pre-commitment, and commitment messages. This means under normal operating conditions, every block advances the finality of one block and this is achieved by only requiring one proposal per time slot. In other words, the cost of DPOS with BFT finality in terms of signature verifications, hash calculations, network bandwidth, etc., is equal to the cost of older DPOS systems that relied upon eventual consistency and the longest chain rule similar to Bitcoin and Ethereum (pre Casper).
Only DPOS BFT can efficiently scale to an unlimited number of validators (at cost to latency). Other protocols grow the resource requirements for finality with O(2N) the number of participants as everyone must talk to everyone twice for each block or checkpoint. With more parties involved,more signatures, network overhead, and storage are required and there is greater latency.
Assuming DPOS BFT with two second block interval and 21 producers, finality can be reached after 1 minute, but a new block reaches finality every two seconds. This is achieved by pipelining the BFT confirmations. Platforms like EOSIO produce blocks every 500ms, but only rotate proposers every 12 blocks. This means BFT finality takes about 3 minutes based upon pure BFT DPOS block confirmations. The end result is 10x faster than Casper for finality for individual blocks, but a new block reaches finality every two seconds versus every 30 minutes.
DPOS Hybrid Pipeline / Realtime BFT
There are many applications where a three minute time for finality is undesirable and/or the DPOS proofs for light clients for a particular block are larger than desired. In this case, a blockchain can make the design choice to do a BFT pre-commit & commit message over every pending block. This gives DPOS-BFT chains finality latency of 1–2 seconds at the expense of the additional network overhead, storage requirements, and CPU usage. Unlike protocols such as Tendermint/Cosmos there can be multiple proposals “in-the pipeline” at the same time. It is even possible that some blocks never receive the “real time” commitment due to network splits, but never the less they are eventually indirectly confirmed.
With the hybrid approach light clients can validate a block with 15 signatures and/or use more advanced cryptographic techniques to merge commit signatures into a single signature. Without the commit messages light clients can still reach BFT finality using a number of consecutive block headers.
Degrees of Security
It has long been understood that for many applications, such as blog posts and social media voting, waiting for 100% finality is overkill when 99.999% finality can be achieved in less than a second. Protocols like Casper give users the option of relying on Proof of Work confirmations when waiting for the next checkpoint is overkill.
Some full nodes may not care to process the overhead of all BFT pre-commit/commit messages when all they require is blockchain state. It is enough to know that the block producers (proposers/validators) are reaching real-time consensus and that their blockheaders eventually prove BFT consensus a couple minutes later.
Each consensus algorithm makes certain choices for users and degrades to less-secure variations in different ways. Tendermint/Cosmos/Ripple don’t give users a choice to operate with anything less than full finality. Ethereum gives users a fall-back to proof-of-work, and DPOS-BFT falls back to the original DPOS guarantees.
It is even possible to layer the Casper checkpoint algorithm with slashing conditions on top of the DPOS BFT block proposal system. Such an approach would create multiple independent validator sets with both political and economic incentives for good behavior.
User Experience
Delegated Proof of Stake with BFT optimizes the nominal case while being no-worse in the worst case. Under normal conditions, elected block producers are trusted public figures with legal liabilities and highly reliable nodes. The probability that a produced block will reach finality is already 99.999% which means that the average user gets near-certain finality in under a second. This is reliable enough for almost all day-to-day financial transactions. Larger financial transactions, such as buying a car, merely require the user to wait a few seconds for absolute finality.
Each user can decide for themselves how much overhead and/or delay they wish to incur and how big the proofs they want to generate for inter-blockchain communication, whereas other protocols do not give users that choice.
Conclusion
All modern consensus algorithms that follow the BFT consensus principles originally introduced the 1980’s can reach a secure and final state in the worst-case of a partitioned network with ⅓ byzantine participants. Only DPOS BFT and EOSIO is optimized for the 99.999% case of 100% honest nodes without network partitions. DPOS BFT achieves this optimized performance without sacrificing the security guarantees that other protocols provide.
All product and company names are trademarks™ or registered® trademarks of their respective holders. Use of them does not imply any affiliation with or endorsement by them.
Important Note: All material is provided subject to this important notice and you must familiarize yourself with its terms. The notice contains important information, limitations, and restrictions relating to our software, publications, trademarks, third-party resources and forward-looking statements. By accessing any of our material, you accept and agree to the terms of the notice.