This is a missing white paper and analysis of the Entrusted Interest Consensus algorithm (DPOS)! The purpose of this article is to provide an analysis of why DPOS works and what makes it so powerful! An early introduction to DPOS can be found at Bitshares.org, but this introduction also includes many other aspects that are not part of true consensus processing.
DPOS Consensus Algorithm
All blockchains are basically a deterministic state machine, acting on transactions. Consensus is the process of agreeing on a certain order of transactions and filtering out invalid transactions. There are many different consensus algorithms that produce the same order of transactions, but DPOS has proven to be powerful, secure and efficient by running reliably on multiple blockchains over the years.
DPOS consensus algorithm abstract
DPOS consensus algorithm is divided into two parts: electing a group of block producers and scheduling production. The election process is designed to ensure that stakeholders end up in control, because stakeholders lose the most when the network doesn’t work properly. How block producers are elected has little impact on how consensus is reached. Therefore, this article focuses on how consensus is reached when a block producer is elected.
To explain this algorithm, I assume that there are three block producers: A, B, and C. Since consensus requires a 2/3+1 majority to resolve all cases, this simple model assumes that block producer C is the winner. In the real world there would be 21 or more block producers. Like proof of work, the general rule is that the longest chain wins. Any time an honest peer sees a valid long chain it will switch itself from the current branch to the longest chain.
The normal process
Under normal flow block producers take turns to produce a block every 3 seconds. The longest chain will be created, assuming that each person in turn generates their own block. Blocks generated by a block producer at any time interval other than their own are invalid.
Minority branch
Allowing up to a third of nodes to be malevolent or malfunctioning creates a minority branch. In this case, the minority branch only produces one block every 9 seconds, while the majority branch produces two blocks every 9 seconds. Again, the honest 2/3 majority will always branch in a longer chain than the minority.
Unconnected few double production
The minority can try to generate an infinite number of branches, but the chain on all branches will be shorter than the chain on the majority, because the minority is constrained to produce blocks more slowly than the majority.
Network fragmentation
Fragmentation of the network is entirely possible, and no branch has a majority of block producers when the network is fragmented. In this case, the longest chain will occur on the largest few. When network connectivity is restored the smaller minority will automatically switch to the longest chain and clear consensus will be restored.
It’s possible to have two of the three branches that are longer, and the chains are the same length. In this case, the balance is upset when the block producer on the third (shorter) branch rejoins the network. There is an odd number of block producers so this will not be the case for long. We will also reshuffle the block producers to randomize the order of the block producers so that even if both branches have the same number of block producers, the branches will explode at different lengths, causing one branch to take over the other.
A few connected double production
In this scenario minority B produces 2 or more other blocks in his time slot. The next scheduled block producer (C) may choose to produce on any block produced by B. When C produces a block, it will become the longest chain, and all nodes that select B1 will switch to the branch of the longest chain. It doesn’t matter how many other blocks a few malicious block producers try to spread, these blocks will never last more than a turn in the longest chain.
And finally irreversible block
In network sharding events it is possible that multiple branches continue to grow for an extended period of time. In the long run, the longest chain will win out, but observers need a way to know for sure that a block is definitely part of the fastest growing chain. This can be determined by seeing more than two-thirds of the confirmation messages from block producers.
In the figure below, block B is confirmed by C and A representing the majority of 2/3+1 confirmations, so we can assume that as long as 2/3 of block producers are honest no other chain will be longer than this one.
Note that this “rule” is similar to bitcoin’s 6-block confirmation. Some clever people can devise a sequence of events in which two different nodes appear on different last irreversible blocks. This edge case requires the attacker to have full control over communication latency, and to use this control not once, but twice, within minutes. If that happens, the longest chain rule still holds in the long run. We estimate that the probability of such an attack happening is basically zero, and even if it does happen, the financial impact is basically so small that you don’t have to worry about it.
Missing block producer quorum
Although less likely, there is also the possibility that the legal number of block producers is unclear, in which case it is possible for a few to continue to produce blocks in which stakeholders can include transactions that change votes. These votes can then select a new group of block producers, restoring the block production participation rate to 100%. Once this happens, a few chains will eventually outperform other chains with less than 100% participation.
During this process all observers will know that the network state has been changing guiding the block production participation rate to 67%. Those who choose to trade in this situation are probably taking the same risk as trading without six blocks of confirmation. They did so knowing that there was a low probability that they would agree on a different fork. In reality this situation is much safer than receiving less than 3 confirmed bitcoin blocks.
Most block producers are corrupt
If most block producers become corrupt, then they can have countless forks, each with a two-thirds majority confirmation. In this case, the irreversible block algorithm eventually reverts to the longest chain algorithm. Then the chain recognized by the largest majority will be the longest chain, and the largest majority will be determined by the few remaining honest nodes. This behavior will not be sustained for a long time because stakeholders will eventually choose to vote to replace these block producers.
Transaction as Proof of interest (TaPoS)
When users sign a transaction, they do so with a certain guess about the state of the blockchain. This conjecture is based on their view of the recent block. If the consensus of the longest chain changes, it may invalidate the assumptions the signers made when they approved the transaction.
Due to TaPoS, when a block does not exist in the history of the chain, all transactions including the hash value of the most recent block are considered invalid. Anyone who signs a transaction in the orphan branch will find that the transaction is invalid and cannot be migrated to the primary branch.
A side effect of this process is security against long-term attacks that attempt to create alternative chains. Each stakeholder directly identifies the blockchain each time they make a transaction. Over time, all blocks are identified by all stakeholders, and this cannot be replicated in a forged chain.
Determine the block producer shuffle
In all the examples we show the block producer’s cyclic scheduling. In reality a group of block producers will be shuffled once after N blocks (N represents the number of block producers). This randomness ensures that block producer B does not always ignore block producer A, and that the deadlock can be broken every time there are multiple forks with the same number of block producers.
conclusion
DPOS is robust under any conceivable natural network outage and is safe from most block producer fraud. Unlike some competitive algorithms, DPOS works even when most block producers fail. During this period, the community can vote to select new block producers to replace those failing block producers until the block producer participation rate reaches 100%. I know of no other consensus algorithm that is so robust in such a high frequency and variable failure environment.
DPOS ultimately gains significant security by selecting a consensus algorithm for voting block producers and certifying high quality and uniqueness of nodes. The use of voting consent ensures that even people with 50% of the votes cannot rely on their right to choose even one block producer. DPOS is designed to optimize performance with a strong network connection and a nominal honest node participation rate of 100%. This gives DPOS the ability to confirm a transaction with 99.9% certainty in an average of 1.5 seconds, while recovering from degraded service in an elegant manner.
Other consensus algorithms are designed to support poor networks, and to face dishonest nodes. This results in slower network performance, higher latency, higher communication overhead, and a failure of the entire network in 33% of node failures.
During the successful operation of Bitshares for 3 years and Steem for 1 year, we have experienced various network conditions and software bugs. DPOS has successfully navigated this environment and demonstrated the ability to process more transactions than any other chain while maintaining consensus