DPOS Consensus Algorithm - The Missing White Paper

5 months ago



This is the missing white paper and analysis of delegated proof of stake (DPOS). The goal of this paper is to provide an analysis of why DPOS works and what makes it robust. An early description of DPOS can be found at bitshares.org; however, that description also includes many aspects that are not part of the actual consensus process.

All blockchains are fundamentally a deterministic state machine acted upon by transactions. Consensus is the process of agreeing on a deterministic order of transactions and filtering invalid transactions. There are many different consensus algorithms that could produce equivalent ordering of transactions, but DPOS has proven robust, secure, and efficient by years of reliable operation on multiple blockchains.

Like all consensus algorithms, the most harm the block producers can cause is censorship. All blocks must be valid according to the deterministic open source state machine logic.

Summary of DPOS Algorithm

The DPOS algorithm is divided into two parts: electing a group of block producers and scheduling production. The election process makes sure that stakeholders are ultimately in control because stakeholders lose the most when the network does not operate smoothly. How people are elected has little impact on how consensus is achieved on a minute by minute basis. Therefore, this document will focus on how consensus is reached after the block producers have been chosen.

To help explain this algorithm I want to assume 3 block producers, A, B, and C. Because consensus requires 2⁄3 + 1 to resolve all cases, this simplified model will assume that producer C is deemed the tie breaker. In the real world there would be 21 or more block producers. Like proof of work, the general rule is that longest chain wins. Any time an honest peer sees a valid strictly longer chain it will switch from its current fork to the longer one.

I will to show by example how DPOS operates under most conceivable network conditions. These examples should help you understand why DPOS is robust and hard to break.

Normal Operation

Under normal operation block producers take turns producing a block every 3 seconds. Assuming no one misses their turn then this will produce the longest possible chain. It is invalid for a block producer to produce a block at any other time slot than the one they are scheduled for.



Minority Fork

Up to 1⁄3 of the nodes can be malicious or malfunction and create a minority fork. In this case the minority fork will only produce one block every 9 seconds while the majority fork will produce 2 blocks every 9 seconds. Once again, the honest 2⁄3 majority will always be longer than the minority.



Double Production by Disconnected Minority

The minority can attempt to produce an unlimited number of forks, but all of their forks will be shorter than the majority chain because the minority is limited to growing the chain slower than the majority.



Network Fragmentation

It is entirely possible for the network to fragment in which case no fork has a majority of the block producers. In this case the longest chain will fall to the largest minority. When network connectivity is restored the smaller minorities will naturally switch to the longest chain and unambiguous consensus will be restored.



It is possible for there to be 3 forks where the two longest forks are the same length. In this case the producers on the 3rd (smaller fork) will break the tie when they rejoin the network. There is an odd number of producers so it is impossible to maintain a tie for long. Later we will cover producer shuffling which will randomize order of production to ensure that even if two forks have the same number of producers, the forks will grow in different length bursts causing one fork to take over the other.

Double Production by Connected Minority

Under this scenario minority B produced two or more alternative blocks on their time slot. The next scheduled producer ( C ), may choose to build off of any one of the alternatives produced by B. When this happens it will become the longest chain and all nodes that selected B1 will switch forks. It does not matter how many alternative blocks a minority of bad producers attempt to propagate, they will never be part of the longest chain for more than a round.



Last Irreversible Block

In the event of network fragmentation it is possible for multiple forks to continue to grow for a prolonged period of time. In the long-run, the longest chain will win, but observers require a means to know with certainty when a block is absolutely part of the fastest growing chain. This can be determined by seeing confirmation by 2⁄3+1 of the block producers.

In the diagram below, block B has been confirmed by C and A which represents 2⁄3+1 confirmation and therefore we can infer that no other chains could possibly be longer if 2⁄3 of our producers are honest.



Note that this “rule” is similar to the 6-block confirmation “rule” for Bitcoin. Some smart individuals can contrive a sequence of events where two nodes could end up on different last irreversible blocks. This edge case requires an attacker to have total control of communication delay and to utilize that control not once, but twice, minutes apart. If this were to happen, then the long-term rule of longest chain still applies. We estimate the odds of such an attack to be close enough to 0 and the economic consequences to be so insignificant that it isn’t worth worrying about.

Lack of Quorum of Producers

In the unlikely event that there is no clear quorum of producers, it is possible for the minority to continue producing blocks. In these blocks stakeholders can include transactions that change their votes. These votes can then select a new set of producers and restore block production participation to 100%. Once this happens the minority chain will eventually overtake all other chains operating with less than 100% participation.

During this process all observers will have knowledge that the network state is in flux until a chain emerges with 67% participation. Those who choose to transact under these conditions take risks similar to those who choose to accept less than 6 confirmations. They do so with the knowledge that there is some small probability that consensus may ultimately settle on a different fork. In practice this situation is far safer than accepting blocks with less than 3 Bitcoin confirmations.

Corruption of Majority of Producers

If the majority of producers become corrupt then they can produce an unlimited number of forks, each of which will appear to be advancing with 2⁄3 majority confirmation. In this case the last irreversible block algorithm reverts to longest chain algorithm. The longest chain will be the one approved by the largest-majority which will be decided by the minority of remaining honest nodes. This kind of behavior would not last long because the stakeholders would eventually vote to replace these producers.



Transactions as Proof of Stake (TaPoS)

When users sign a transaction they do so under a certain assumption about the state of the blockchain. This assumption is based upon their perception of recent blocks. If the consensus on the longest chain changes then it could potentially invalidate the assumptions the signer had when they consented to the transaction.

With TaPoS all transactions include a hash of a recent block and are considered invalid if that block does not exist in the chain history. Anyone who signs a transaction while on an orphaned fork will find the transaction invalid and unable to migrate to the main fork.

A side effect of this process is security against long-range attacks that attempt to generate alternative chains. Individual stakeholders directly confirm the blockchain every time they transact. Over time all blocks are confirmed by all stakeholders and this is something that cannot be replicated in a forged chain.

Deterministic Producer Shuffling

In all of the examples we showed a round-robin scheduling of block producers. In reality set of block producers is shuffled every N blocks where N is the number of producers. This randomization ensures that block producer B doesn’t always ignore block producer A and that anytime there are multiple forks of identical producer counts that ties are eventually broken.

Conclusion

Delegated Proof of Stake is robust under every conceivable natural network disruption and even secure in the face of corruption of a large minority of producers. Unlike some competing algorithms, DPOS can continue to function when a majority of producers fail. During this process the community can vote to replace the failed producers until it can resume 100% participation. I know of no other consensus algorithm that is robust under such a high and varied failure conditions.

Ultimately DPOS gains significant security from the algorithms chosen to select the block producers and verify that the nodes are of high quality and unique individuals. Using the process of approval voting ensures that even someone with 50% of the active voting power is unable to select even a single producer on their own. DPOS is designed to optimize performance of the nominal condition of 100% participation of honest nodes with robust network connections. This gives DPOS the power to confirm transactions with 99.9% certainty in an average of just 1.5 seconds while degrading in a graceful, detectable manner that is trivial to recover from.

Other consensus algorithms design for a nominal condition of dishonest nodes with poor network conditions. The end result of alternative designs is networks that have slower performance, higher latency, high communication overhead, and completely halt in the event 33% of nodes fail.

With 3 years of successful operation on BitShares and a year of Steem we have experienced all manner of network conditions and software bugs. DPOS has successfully navigated this environment and demonstrated its ability to maintained consensus while processing more transactions than any other blockchain.

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  trending

You share so intresting and valuable information!

Thank you very much @dantheman

Excellent review, thank you!

In light of this, what are the major criticisms to DPOS you know of?

It seems obviously superior to algorithms which waste energy, are less secure, and less performant. Do you think others are not aware of how it works or too biased by the technology they've already committed to? Is DPOS the Betamax to proof-of-work's VHS?

We know superior technology doesn't always win in the marketplace. So is the next challenge a marketing effort to gain influence and increase adoption for DPOS?

·

Biggest criticism is its reliance on votes and how it breaks down under poor token distribution. Politics is unavoidable so it's best to formalize it rather than have the kind of consensus failure bitcoin faces with scaling debate.

·
·

Thank you, Dan. I think the poor token distribution argument is a good one, but hopefully one that can be solved over time. Once things get distributed widely enough, it mostly becomes a non-issue. I have high hopes for the EOS distribution scheme. If it's like how you've done many other things, I'm thinking it'll be ahead of its time.

I also agree about the politics. Would be great to avoid it, but since we can't, it makes sense to make it clear and formal.

·
·

Sorry for jumping into your comments but non of this Steemit Techy guys are responding to me. I convinced a friend to join steemit after bragging to him for weeks now its been almost a week and he hasn't gotten a passkey, please i know him and he's gonna bail out on me if he didnt get it soon....PS - i was referred to @ned or @dantheman but none of them seems to recognise me or any of my comments since joining steemit in March, not to talk of checking some of my post, so pardon me as i just check out all the Dan i seem to come across on Steemit

·
·
·

I cannot help. Don't work for Steemit.

·
·
·
·

Alrighty, thanks......

·
·
·
·
·

I can't help with that process either, it's entirely in the hands of Steemit Inc. But if you're really eager to get him online you can fund an account for him with @anonsteem or SteemConnect (check @timcliff's recent post).

·
·
·
·
·
·

okies, now i get......thanks a bunch!

·
·
·

regarding onboarding new people on STEEMIT, there's apparently a huge backlog right now, like 50K or so! If your friend is still having trouble getting approved after a week or so, have him visit the steem.chat help forum. They should be able to help get him all sorted out!

·

We know superior technology doesn't always win in the marketplace. So is the next challenge a marketing effort to gain influence and increase adoption for DPOS?

It depends on what kind of applications are built on top of DPOS. If there are services that can only work with high capacity blockchain, it's pretty clear that there won't be any competition.

But, of course, somebody has to build those services first.

·
·

That's a great point. If a Graphene, DPOS system is the only one that can handle specific use cases, then it wouldn't be a Betamax/VHS situation since we'd be the only available decentralized blockchain option. Maybe those verticals are a good place to focus our marketing efforts.

·

I believe the market will choose the better tech in this situation. Our community is too smart to continue the adoption of an inferior tech, long term.

This is a great post. I can understand all of this.
But I need few more information.

Let's say I have 1% of tokens.

  1. Am I eligible as a producer ?
  2. What is the difference between me and someone has 2% tokens?
  3. What's the incentive for me to participate in producing?
  4. How do we store the data. I mean how do we handle the growing amount of blockchain data. Is there any kind of sharding?
·

I think the answer to the question 4 may be not related to the consensus algorithm but to the actual blockchain software.
I read the EOS.io docs and it seems like I might hold the 1% of the total size of the blockchain since I hold 1% of tokens.

See here for more

So, that's a kind of a sharding system to me.

Great! Another DPOS .... Dan Posts On Sunday.

Interesting post Dan. Thanks for sharing.

Congratulations @dantheman!
Your post was mentioned in my hit parade in the following category:

  • Pending payout - Ranked 3 with $ 850,64

Thanks! What about overall amount of full nodes? For example knocking down 21 computers simultaniously is much easier than several thousands of them like in DASH or other POW cryptocurrencies.

BTW, what are you thoughts on HF-19 in Steem?

·

There are more than 21 full nodes in steem due to runner up production and API nodes. Consensus algorithm is almost entirely independent of number of full nodes.

·
·

And what is your estimation of full nodes count in EoS? I mean, if someone looks for witnesses on steemd.com he will see that most part of witnesses after number 50+ are inactive.

Congratulations @dantheman! You have completed some achievement on Steemit and have been rewarded with new badge(s) :

Award for the number of comments received

Click on any badge to view your own Board of Honnor on SteemitBoard.
For more information about SteemitBoard, click here

If you no longer want to receive notifications, reply to this comment with the word STOP

If you want to support the SteemitBoard project, your upvote for this notification is welcome!

Dan, I want you to read my post about PoW vs PoS and see if you agree with my statement that bitcoin has likely already died and people just don't know it yet:

https://steemit.com/steemit/@r0achtheunsavory/the-r0ach-report-14-defining-if-cryptocurrency-has-a-value-or-zero-value-from-a-fundamental-scientific-perspective

My position is also that proof of stake has no inherent value at all, but I don't consider Steem itself a pure proof of stake system, but Bitshares would be. So in summary, whether Steem has a good or bad economic system and lives or dies, I believe Steem was a much more relevant invention of yours than Bitshares in the grand scheme of things.

Thks for bringing this missing part. I've been bringing DPoS Blockchain Solution in my local Blockchain community since Bitshares 2.0 and I'm happy to say for having experience for 2 years with Bitshares & Steem that it's working smootly

this looks interesting, i love DPOS

Thank you for breaking it down like this. I can't believe it is so simple and so secure.

@dantheman
I appreciate your analysis and for breaking it down for us!

Merci for the post @dantheman. This is the third blockchain white paper I've fully read. Maybe I will eventually start to understand if I keep reading. I recently experienced an orphaned block with PIVX where I lost a fair amount of staking rewards. Yet I appear to not have gone off chain. Mysterious.

This is a nicely approachable explanation of the security of DPoS, which serves to reinforce the clear advantages it holds over other blockchain securing methods.

err @dantheman, my first question is why are you always declining payout on each of your post?....2nd is i brought someone in on Steemit since last week by the name @the-commentator and he had confirmed his email link but no passkey given to him yet, is that a glitch or he was forgotten? cos i remember it took me just 2days to get mine.....PS- i just don't want him to loose interest after all my bragging that convince him.

·

regarding onboarding new people on STEEMIT, there's apparently a huge backlog right now, like 50K or so! If your friend is still having trouble getting approved after a week or so, have him visit the steem.chat help forum. They should be able to help get him all sorted out!

·
·

Without him not fully registered on steemit?....is that possible?.....so i could ask him to join

·
·
·

steem.chat has a separate registration process from steemit.com, just click on "Register a new account". You could also go on steem.chat and ask on his behalf as well if you'd like.

Great post, thank you.

Wow! This is the post! You've given me a lot of information. Thanks for sharing! You need to have a big brain to write it! Thank you!

Now I know some, and learn some on how the process made by this dpos it means all can assure of good transaction no doubts and what if? since everything was build to perform in success. afraid not of what will happen for everything is in the block chain, love it @dantheman your the man!!!

Steem on!

Thank you.

Please keep posting about EOS tech so we can keep up with it.

finally!!! After complaining for the lack of documentation here and the added threat of censorship since we are on a blockchain based social media, at long last we get more details.

Hi, I've seen some of your publications I'm going to follow, follow me and let's collaborate together

Great post thank you
I hope i will be able to explain it to lazy and conservative russian legislative and regulative authorities and implement one day bitshares blockchain for the pension system

https://steemit.com/bitshares/@rossomahar/dpos-for-blockchain-pension-system-in-russia

Thanks for the info. Hadn't thought about it like that.

Thanks you! I've been looking everywhere for this.

wow that is is great write up, just curious, do you have any stats on the current TX/S data for bitshares and steem?

Thank you

Amazing post, very informative. With all that steem, you should sit back relax and listen to some tunes, blow some steem on my music. ;) Selling my songs for Steem, for fans of Vaporwave, Electronic, a tiny bit of 80s mixed with a lot of different eras. All 3 tracks mixed by Christoffer Berg (The Knife, Fever Ray)
https://steemit.com/steemit/@wvm/my-song-i-will-run-for-steem
https://steemit.com/steemit/@wvm/my-song-sown-for-steem
https://steemit.com/steem/@wvm/selling-my-song-blood-for-steem

@dantheman congrats 4 your work ! I'd like follow each other ,and have big posts ! :)

Sorry for being off topic, but is your account really worth a couple of mil? !! If so can you give me tips on growing?

This is beautiful. I wish there was functionality in steemit to create my own reference list of postings. Meanwhile I'll just post this meaningless comment as a bookmark to refer to this posting later. :)

Hi Dantheman!
Incredible journey this! Just wrote a post "the true power of steemit, building community, empowering change - thought you might appreciate some aspects of it! https://steemit.com/anarchism/@willstephens/the-true-power-of-steemit-building-community-empowering-change
As I am new here any help you can give me to get on the ladder would be for ever appreciated, have a beautiful day ;-), Thanks, Will

Thanks for posting Dan

In the minority fork situation (for example) - how is it enforced that B waits for its turn to add new block and not just adding new block as fast as it can?
In other words:
"In this case the minority fork will only produce one block every 9 seconds while the majority fork will produce 2 blocks every 9 seconds." - how is that enforced?

Hi Dan, you mention TaPoS in the end, but do not make any mention of the cons to it. Why would you not simply build your protocol to enforce a TaPoS standard to begin with?

We need a bookmarking feature seriously

it's good.nice job.

cool!