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:

1. Propose block
2. All participants acknowledge block (pre-commitment)
3. All participants acknowledge when ⅔+ have sent them pre-commitments (commitment)
4. A block is final once a node has received ⅔+ commitments
5. Unanimous agreement on finality is guaranteed unless ⅓+ are bad and evidence of bad behavior is available to all

Abstract BFT Life Cycle

What makes the various consensus protocols different are:

1. Deciding when and who gets to propose a block
2. Deciding how commitments are logged & communicated
3. How byzantine behavior is documented
4. Punishment for byzantine behavior

Some of these differences are political and some of them are technical in nature. Examples of political differences include:

1. DPOS elects the set of proposers & validators based upon stake
2. 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
3. DPOS punishes objective and subjective bad behavior by voting people out
4. 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 BFT w/ optional Low-Latency Confirmation

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.

Disclaimer: Block.one is a software company and is producing the EOSIOsoftware as free, open source software. This software may, among other things, enable those who deploy it to launch a blockchain or decentralized applications with various features. For more information, please visit https://github.com/eosio. Block.one does not provide financial support to anyone seeking to become a block producer on any version of the EOSIO platform that may be adopted or implemented.

Block.one will not be launching any of the initial public blockchains based on the EOSIO software. It will be the sole responsibility of third parties, the community and/or those who wish to become block producers to adopt and implement EOSIO in the manner they choose, with the features they choose and/or providing the services as they choose. Block.one does not guarantee that anyone will adopt or implement such features or provide such services or that the EOSIO software will be adopted and implemented in any way.

Block.one does not endorse any third party or its products or services, even if they are mentioned herein. Block.one is not responsible for any linked content.

Please note that the statements herein are an expression of block.one’s vision, not a guarantee of anything. While we will try to make that vision come true, all aspects of it are subject to change in all respects in Block.one’s sole discretion. We call these “forward looking statements”, which includes statements in this document, other than statements of historical facts, such as statements regarding Block.one’s business strategy, plans, prospects, developments and objectives. These statements are only predictions and reflect Block.one’s current beliefs and expectations with respect to future events and are based on assumptions and are subject to risk, uncertainties and change at any time. We operate in a rapidly changing environment. New risks emerge from time to time. Given these risks and uncertainties, you are cautioned not to rely on these forward-looking statements. Actual results, performance or events may differ materially from those contained in the forward-looking statements. Some of the factors that could cause actual results, performance or events to differ materially from the forward-looking statements include, without limitation: market volatility; continued availability of capital, financing and personnel; product acceptance; the commercial success of any new products or technologies; competition; government regulation and laws; and general economic, market or business conditions.

All statements speak only as of the date of first posting and Block.one is under no obligation to, and expressly disclaims any obligation to, update or alter any statements, whether as a result of new information, subsequent events or otherwise. Nothing herein constitutes technology, financial, investment, legal or other advice, either in general or for any particular situation or implementation. Please consult with experts in appropriate areas before implementing or utilizing anything contained in this document.

The ideas and information expressed herein are solely those of the author and do not necessarily reflect the positions, views or advice of Block.one or any other employee of Block.one.