DPOS Consensus Algorithm - Missing White Paper

Original Address:
https://steemit.com/dpos/@dantheman/dpos-consensus-algorithm-this-missing-white-paper

This "missing white paper" is an analysis of delegated proof of entitlement (DPOS) to provide an analysis of the working principle of DPOS and its root causes of robustness. An early description of DPOS can be found at bitshares.org; however, that description also contains many things that are not part of the actual consensus process.

All blockchain is essentially a transaction-driven deterministic state machine. Consensus is the process of agreeing on a definitive transaction sequence and filtering out invalid transactions. There are many different consensus algorithms that generate equivalent order of transactions, but DPOS has proven itself to be robust, secure and effective through years of reliable operation across multiple blockchains.

Like all consensus algorithms, the biggest damage a block producer can cause is censorship. The validity of all blocks must be based on deterministic open-source state machine logic.

DPOS algorithm outline
The DPOS algorithm is divided into two parts: selecting a group of block producers and scheduling the production. The electoral process ensures that ultimately stakeholders are under control, as stakeholders lose the most when the network is not working. The method of election has little effect on how to reach consensus in actual operation. Therefore, this article will focus on how to reach consensus after block producers are selected.

To help explain this algorithm, I would like to assume 3 block producers A, B, and C. Since the consensus needs a 2/3 + 1 majority to solve everything, this simplified model will assume that producer C is the one who breaks the deadlock. In the real world, there will be 21 or more block producers. Like workload proof, the general rule is that the longest chain wins. Whenever an honest peer sees a valid longer chain, it switches from the current fork to the longer chain.

I will give an example of how DPOS works under the most desirable network conditions. These examples should help you understand why DPOS is robust and unbreakable.

Normal operation
In normal operation mode, block producers take turns generating a block every 3 seconds. Assuming no one missed his turn, then this will produce the longest chain. Block producers are invalid at any time outside the scheduled turn.
DPOS共识算法 -- 缺失的白皮书

A few forks
A malicious or faulty node that does not exceed one-third of the total number of nodes may create a small number of forks. In this case, a few bifurcations produce only one block every 9 seconds, whereas most forks produce two blocks every 9 seconds. In this way, an honest 2/3 majority will always be longer than the minority.

Offline a handful of multiple productions
(Offline) A few can try to produce an infinite number of bifurcations, but all their bifurcations will be shorter than most people because a few people are destined to die more slowly than most.
Network fragmentation
It is quite possible that the network will be fragmented, resulting in most bang generators without any bifurcation. In this case, the longest chain will be reversed to the largest minority. When network connectivity is restored, the smaller minority will naturally switch to the longest chain, and a clear consensus will resume.
There may be three such bifurcations where the two longest bifurcates are the same length. In this case, the 3rd (smaller) bifurcated block producer will be able to break the tie when rejoining the network. The total number of block producers is an odd number, so it is impossible to keep the draw for a long time. We will also talk about producer "shuffling" later, which randomizes the order of bins, ensuring that even two bifurcates with the same number of producers will grow in different steps, eventually leading to a bifurcation another.

Online a few multiple production
In this scenario, a few Node Bs produce two or more alternative blocks during their time period. The next plan producer (C) has the option of continuing to build the chain based on any one of the B-generated options. Once that happens, this choice becomes the longest chain, and all nodes that choose B1 will switch the fork. It does not matter that a handful of bad producers try to broadcast more of the replacement blocks, and they will never be more than one round as part of the longest chain.
The last irreversible block
In the case of network fragmentation, multiple bifurcations are likely to continue to grow for a long time. In the long run, the longest chain will eventually win, but observers need an exact way to determine if a block is definitely in the fastest growing chain. This can be determined by observing the confirmation from the majority of 2/3 + 1 producers.

In the image below, Block B has been confirmed by C and A. This represents a 2/3 + 1 majority confirmation, whereby we can conclude that no other chain will be longer than this - if 2/3 of the producers are honest.
Please note that this "rule" is similar to the 6 validated "rules" of Bitcoin. Some clever person may be able to plan a series of events such that two nodes (which should be "trades"?) Appear on different last irreversible blocks. This fringe case requires the attacker to have complete control of the communication delay, and use the control twice in a matter of minutes - not once. Even if this really happened, the long-term rule of the longest chain (win) still applies. We estimate that the probability of such an attack is close to zero and that the economic consequences are insignificant and therefore not sufficient.

Insufficient quorum for producers
In the unlikely event that there is a lack of a clear quorum for the producer, a minority can continue to block. Stakeholders can include changes to vote in these blocks. These votes will allow you to pick up a new group of producers and restore the block participation rate to 100%. If so, the minority chains will eventually outperform all other chains that run at less than 100% participation.

In the process, all observers will know that the network status is undefined until a chain with a participation rate of more than 67% is formed. Those who choose to trade under these conditions risk similarities to those who choose to receive less than six confirmations. They know that there is such a small possibility that the consensus may eventually be established on a different fork. In practice, this is safer than a block that accepts fewer than 3 bitcoin transaction confirmations.

Most producers cheat
If most producers become corrupt, then they can produce an infinite number of bifurcations, each of which appears to confirm a 2/3 majority move forward. In this case, the last irreversible block algorithm transforms into the longest chain algorithm. The longest chain is the one approved for the largest majority, and this will be determined by the few remaining honest nodes. This behavior does not last long because stakeholders will eventually vote to replace producers.
Transaction as proof of equity (TaPoS)
When users sign a transaction, they do so under certain assumptions about the state of the blockchain. This assumption is based on their perception of the last few blocks. If the consensus of the longest chain changes, the previous assumptions of the signer may be invalidated.

In the case of TaPoS, all transactions contain a hash of the most recent block, which is considered invalid if the block does not exist in the chain's history. Anyone who signs a transaction on the orphan bifurcation will find the transaction invalid and can not be migrated to the main bifurcation.

A side effect of this process is the long-term attack that tries to create alternative chains. Each stakeholder confirms the blockchain directly at each transaction. As time passed, all the blocks were identified by all stakeholders and could not be duplicated in a counterfeit chain.

Deterministic producer shuffle
In all of the above examples, we show that the block producer dispatches blocks by cycle. In fact, every N blocks (N is the number of producers), the block producer pool shuffles once. This randomness ensures that block creator B does not always ignore block creator A, and the draw will eventually be broken whenever multiple bifurcations with the same number of producers are formed.

in conclusion
In every case where we can think of a natural network split, commissioned proof of entitlement is robust and safe even in the face of fraud by a significant number of producers. Unlike other consensus algorithms, DPOS can continue to work when most producers fail. In the process, communities can vote to replace unqualified producers until a 100% participation rate is restored. I do not know yet any other algorithm that can remain robust in such a high-intensity and changing failure environment.

After all, the compelling security of DPOS comes from its choice of block producers and algorithms to verify node quality. The pro-voting process ensures that a person can not even choose a single producer, even with a 50% effective voting power. DPOS is designed to optimize the nominality of 100% participation (consensus process) in honest nodes with strong networking. This made it possible for DPOS to confirm the transaction with a 99.9% certainty in an average of only 1.5 seconds while being gracefully and detectively downgraded - returning to normal from downgrade was just a trivial matter.

Other consensus algorithms design dishonest nodes with poor network conditions as nominal conditions, so the end result of the design is a network with poorer performance, higher latency, and higher communication overhead, and the network is completely complete with 33% of node failures Shut down.

During the three years of successful BitShares and one year of running at Steem, we experienced a variety of network conditions and software errors. With DPOS running through it, it demonstrated extraordinary ability to continue to reach consensus while dealing with more transactions than any other blockchain.