Seeking Consensus on Consensus - DPOS or Delegated Proof of Stake and the Two Generals' Problem

[iang]

Laying down the rails for a high performance financial blockchain-based ecosystem is well understood if controversial because there are a number of approaches - centralised, decentralised, un-permissioned, walled garden.

Having chosen all that, we still have that one nagging itch of how to deal with race conditions. No matter the design, there’s always something you want to do and something someone else wants to do where these two things can’t both happen. Or, it’s cast in the sense that you want something to happen, and you want someone else to know this is going to happen too, known in the computer science worlds as Two Generals problem:

Two armies, each led by a general, are preparing to attack a fortified city. The armies are encamped near the city, each in its own valley. A third valley separates the two hills, and the only way for the two generals to communicate is by sending messengers through the valley. Unfortunately, the valley is occupied by the city's defenders and there's a chance that any given messenger sent through the valley will be captured.

Positions of the armies. Armies A1 and A2 need to communicate but their messengers may be captured by army B.

While the two generals have agreed that they will attack, they haven't agreed upon a time for attack. It is required that the two generals have their armies attack the city at the same time in order to succeed, else the lone attacker army will die trying. They must thus communicate with each other to decide on a time to attack and to agree to attack at that time, and each general must know that the other general knows that they have agreed to the attack plan. Because acknowledgement of message receipt can be lost as easily as the original message, a potentially infinite series of messages is required to come to consensus.
The thought experiment involves considering how they might go about coming to consensus. In its simplest form one general is known to be the leader, decides on the time of attack, and must communicate this time to the other general. The problem is to come up with algorithms that the generals can use, including sending messages and processing received messages, that can allow them to correctly conclude:

Yes, we will both attack at the agreed-upon time.
Allowing that it is quite simple for the generals to come to an agreement on the time to attack (i.e. one successful message with a successful acknowledgement), the subtlety of the Two Generals' Problem is in the impossibility of designing algorithms for the generals to use to safely agree to the above statement. (cite Wikipedia)

Also known as the coordination problem. In blockchains we call it the consensus problem. In the financial cryptography world, it’s the double spend problem, and in databases, atomicity. Which is to say this is a fundamental problem in all of computing science, and it’s not new just because, ya know, blockchain.

Let’s work through the evolution of this problem.

Centralised Double Spend Protection

The original mechanism in financial cryptography is the simple client-server or trusted third party (like SOX), which is to say that the issuer of a double-spendable value like a coin runs a single server that mediates the double spends. Typically, the requests are queued up on a first in, first out (FIFO) basis, which is standard in databases these days.

Blinded Cash

One notable variation of centralised double spend protection was the blinded signature over coins, invented by David Chaum in the late 1980s (Chaum, Achieving Electronic Privacy). The blinded coin was independently usable (verifiable) as a monetary token, but like all data, Alice could hand it to both Bob and Carol at the same time. The solution then was for Bob to push the coin back to the issuance server, known as a mint, and ask for a freshly signed one. Carol should do the same, and be faster!

Now, the special trick of the blinded signature on the token was that when pushed through a modified form of RSA, it could morph to create a new signature that the issuer had not created, but was still valid and therefore could identify a real coin to the issuer. Blinding therefore meant the issuer couldn’t track what Alice did with her coins, a very valuable thing! A further trick with eCash was that if Alice did try to spend the coin twice, the mint could use some crypto to combine both erstwhile spent coins, strip out the psuedonymous protection, and reveal who the naughty girl was.

I include mention of blinded double spending partly because it is an example of a very complicated scheme to catch double spending, and partly because it started our field of financial cryptography - invented back in the mid 1980s and built in the mid 1990s.

Voting

Replicated servers became the in-thing typically for purposes of reliability. For example, the early NASA space shuttles had a voting ring of 3 primary IBM mainframes (and a couple of standbys). On every important act in a voting circle, a majority would win, and a minority could be disconnected and replaced. Early simple majority voting schemes proved to be a lot of trouble, and now the ruling buzzwords are Paxos and PBFT (practical byzantine fault tolerant), but do note that behind them there are lashings of Lamport, theory, bickering Byzantine Generals, PhDs, papers and Turing Prizes, oh my!

These above variations on the theme suffer from some pretty serious limitations, chief of which are,

• they are administratively centralised, and/or/therefore
• all participants are known.

In other words, the various Byzantine Generals Solutions assume that we know who the generals are, and famously that’s not usefully true in all cases.

Proof of Work

Satoshi observed that any centralised component can be attacked, and likely will be (Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System). This observation was accurate : MTB shut its blinded eCash down due to unexpected adult shopping, DigiCash was hamstrung by authorities, WebMoney was hit by a reputation attack, e-gold was brought down by the Feds, as was LibertyReserve. DigiGold and e-Bullion failed due to founder actions. The list is exhausting, and your chastened author was closer to some of these disasters than was comfortable. You should do your own research to eliminate blame, forgetfulness and other biases.

This was observed by several (see for example “The Mining Delusion”) but it was Bitcoin that presented a solution.

Therefore, Satoshi argued, we need to eliminate the centralised vulnerability party (CVP, also known as a trusted third party or TTP). And by deduction, as we can’t trust voting by known parties, we must all share and prove the same data, and we must accept and relish easy entry and exit - psuedonymity.

Great stuff, but we still haven’t solved the double-spend problem, we’ve just moved it from a single place to a very much larger place :-(

The elegant and famous solution to this was proof of work (POW) or the nakamoto signature - a lottery based on hash-puzzle over a correct block of transactions. The cryptographic nature of the hash lottery selects one single miner at random, who produces the block. Coupling the costly hash search called mining with a reward and adding in some complicated game theory and probability is all designed to keep the miners on the straight and narrow. See comic.

Bitcoin is a brilliant and elegant solution because it opens our thinking to the possibility of fully distributed applications, with money. But PoW burns up energy to the value that the market can bear, which amounts to a horrible tax on the entire value of the currency (as of time of writing, 4% on Bitcoin, and 11% on Ethereum, big ouch!) and as the Bitcoin chain moves to a fee base this means fees will bite hard, lifting Bitcoin out of reach of most people. High rewards and the rising price also resulted in economies of scale for mining, resulting inevitably in the concentration of miners. Although the system itself happily carries on, a perverse consequence of the censorship-resistant design is that the power of censorship now rests in the hands of about a dozen businesses, with most in one country that is not famous for resisting the urge to censor.

Proof of Stake

It was observed by someone (?) that we could simply replace the voting-with-CPU with voting-with-value in order to choose who makes the decision on (the next block of) double-spends. After all, the blockchain precisely establishes who owns what currency, and those who have more skin in the game are more likely to preserve the system, so it is an aligned bias. If uncomfortable to the small player, and somewhat offensive to democratic principles.

So the theory goes. In practice, it has been criticised for (1) placing the power in the hands of those with most value, and also (2) for the “nothing at stake” problem which occurs when a bet on an alternate chain does not cost if it doesn’t survive.
Simple proof of stake then does not seem to work. Let’s see what does work - let’s break down the problem.

Let’s go to a Mining Centralisation Conference

When we look at Bitcoin’s current state of a dozen or so well-known mostly Chinese miners, it is clear that they are all known, to us and to each other, and they can and do communicate. When we get to mining pools the size of today’s country-warming rigs, Bitcoin’s assumption of psuedonymity for miners becomes tenuous - just follow the electricity. Or go to any bitcoin scaling conference.

And they could collude. So far, they have not chosen to do so, or, at least not obviously. As that’s a situation that hasn’t proven reliable historically, maybe incentives & ethics can be bolstered?

Only their incentives and their ethics keep the miners from colluding; it is the case that miners have returned the occasional fat-finger error, ones in which a trader has accidentally sent many BTC in fees instead of many satoshi, so ethics has some play here. On the other hand, some miners have mined empty blocks, even when the queue of delayed transactions or ‘mempool’ is exploding.

Not only is today’s miner concentration and cooperation unanticipated, the Bitcoin design was deliberately focussed on an alternate vision. Is miner integrity a sustainable future? Integrity is a cause that hasn’t proven reliable historically in for example banking, so maybe we should continue to bolster the incentives & ethics of blockchain?

What if we work backwards and accept the fact that the miners can be concentrated? And that we know who they are? Or more controversially, miners should be concentrated and should be identified?

If we accept miner concentration and miner identification, we could simply appoint them. But appointing the Asic Generals just brings us back to the original centralised vulnerability situation.

Delegated Proof of Stake - How to rule the Generals

How then would we govern miners better? If we can appoint them, we can dismiss them as well, which brings us back to the Two Generals’ Problem.

Given a new set of requirements forced on us by reality and experience, it is plausible to re-design the double spend system. Delegated Proof of Stake is just such a redesign, by @dantheman, using a combination of the tools above:

1. A Producer (nee miner) is selected as decision maker to prevent double spends in one block. See Figure 4. Each block produced is rewarded by new currency (no change here).
2. Many producers are selected and given a round-robin rotation for a round of blocks, thus creating a competitive market within the round, ensuring overall reliability, and resolving forks. See Figure 5.
3. The chain runs an open community poll to manage the producers, in which each member may vote according to proof of stake. Producers are both selected and dismissed in the same way - an auction for the next round. See Figure 6.

The community then is required to govern their chain by

• checking and agreeing with the transactions they perform,
• voting the producers in and out based on their record and other pronouncements (e.g,. the producers are free to offer incentives such as revenue splitting) and
• maintaining their stake or suffrage to the needs they choose.

Note that a more technical approach to attacks on DPOS can be found in DPOS Consensus Algorithm.

A Political Economy?

In consensus terms, DPOS is stake-delegation over proof - the producers provide the proof over the blocks, and the community uses its stake to delegate the producers.

In political terms, DPOS is similar to a two-layer representative democracy with landowner suffrage. Where,

• representatives are those producers that are delegated by the community to decide the day to day questions (over double spend), and
• suffrage, or the right to vote on representatives, is given to those who hold a certain form of property. This property might be a savings unit which represents a commitment to the community, and also a loss of liquidity; it resembles the historical landowner suffrage popular before more universal forms, as recognition of the wealth and commerce that the merchant class brought to society.

The precise design of this mechanism - savings account, how many producers, how long a block, how long a round, what happens if?? - is obviously a deep and interesting question, and we’ll not go there today.

How does it Perform?

This mechanism has been shown to work in at least 2 large scale systems, Bitshares and Steem, and of course DPOS is to be used in EOS. It has also been chosen by Tezos, PeerPlays and Ark.io.

While it is possible to criticise, so far the criticisms seem to be more at the level of flavour and comparison than weaknesses:

1. Proof of stake is weak because of “nothing at stake” but this only matters when the stake is put to the direct question of a block. Delegation solves that - in DPOS the stake is put to the vote on the Producers, while the block is handled by a direct Producer round. Separation by delegation solves the “nothing at stake” problem.
2. There are possibilities for the producers to behave badly - they can censor transactions. But this is actually a flipped into benefit because badly behaved producers can also be voted out - that’s the point of delegation. Contrasting with Bitcoin’s current malpractice of the month of mining empty blocks, DPOS performs far better because it has a punishment mechanism.
3. There are possibilities to collude. Of course, collusion is also possible in other chains, as the above photo suggests. The question is really about which will perform better under collusion, and so far, our money’s on the organised governance because of punishment - skin in the game. The ad hoc or un-governed arrangement of pure PoW means that miners can’t be punished, even if they decide to mount their fabled 51% attack. In DPOS, once collusion is surfaced, it’s possible to adjust governance rules to deal with it be it at 51% or at 1%.
4. The purist bitcoiner will point out that by adding a governance layer, we’ve broken the trustless nature of the blockchain. Not so, as trustlessness rests on fallacies:
   1. Fallacy that there is no governance layer in other chains. In practice there are governance layers, but they are unwritten, denied, and inconstant or abused. In essence, we are replacing ad hoc (anarchic? captured?) governance with written, constitutional, formal and transparent governance. The question is not whether this adds governance, but whether explicit governance is better than the hidden intrigue.
   2. Fallacy that the Bitcoin design means we don’t have to trust the miners. Consider the empty block syndrome again: we now have to trust the miners to produce decent blocks for the community, and they don’t, which exposes the gap between the mathematical nature of the blockchain and the human nature of ‘trust.’ The blockchain under PoW eliminates some trust but not all, and in this case, it destroys the possibility for the trust when it is needed.

DPOS comes with some advantages that are also worth stressing:

1. As it eliminates the hash mining, it is far cheaper than Proof of Work. In effect we are releasing the mining tax back to the community - as of writing 4% Bitcoin and 11% Ethereum.
2. And we’re cleaning up the planet :-) DPOS is recommended for any blockchain with a heart ♡
3. By adding a layer of formalised governance, we also set the scene for upgrades to the software. That is, users have a real mechanism to vote on a change, and producers have a real vote to follow. This mechanism pretty much makes the adversarial fork debate go away, and makes the chain fluid and dynamic - it can evolve quickly to suit evolving needs. I.e., the unsolved PoW nightmares of DAO and the blocksize debate are solved problems under DPOS.
4. The formalised governance also works to give community the voice over their chain.
5. DPOS works to channel the decision making into a high-performance and high-efficiency rig that allows truly massive throughput. Let’s leave performance to other posts, but it’s worth stating that Bitshares has tested at 1000X that which Bitcoin can achieve in its current form. That sort of performance creates a lot of headroom for forgiveness.

Benefits are of course all sins to some, but they are the sorts of sins that businesses and individuals can forgive and treasure.

Comments

[atomrigs]

The key point in DPOS consensus mechanism is how to elect the representatives(or witness) producing the blocks. You described the mechanism as "open community poll", but how to organize the poll can result in a very different governing structure.

For example, Steem has 20 witnesses plus 1 time-sharing witness, and each share can vote 30 times on different witnesses. The interesting part is why each share should have 30 times voting chances.

Under this rule, to become a witness does not necessarily depend on the majority of "community support". Instead, cross-voting structure among top 10 or 20 whales becomes the most important decision factor. If you get 20% voting, it is pretty safe to maintain the witness position and to get that amount of voting, you need just 10 other whales supports with at least 2% of the total Steem shares. You don't need to worry about all other community members' voting at all. So for the top whales, it is very "reasonable" to make agreements to do cross-voting each other and not to "betray" each other. There may not be a just one power block, there can be two or three different power groups voting internal members mostly. If one member betrays, it is very easy to pull down his seat.

If the system allows only one voting chance per share, this kind of cross-voting is impossible. Maybe one big shareholder can divide up his shares to multiple accounts and can occupy multiple witness seats, but it is very difficult to hold more than several unless he has more than 50% of the total shares.

When the number of representatives(or witness) is small (such as less than 100), and having multiple voting chances per share, it is easy for the top whales to collude to make a power block whose main goal is to maintain their prestige (and very profitable) positions.

This kind of DPOS poll system may be okay for a consortium chain with a limited number of established pre-existing power players such as a big enterprise consortium network, but not idealistic for a public chain, in particular for a public contents network where those witnesses can decide which content is good or bad.
Regarding this issue, I wrote a post several months ago,
https://steemit.com/steemit/@atomrigs/net-neutrality-and-curation-rewards

If I have a chance to design a new Steem system, I would do these things;

• At least 100 full-time witness nodes
• Only one witness vote chance per share
• Witness should have no curation voting power
• Witness rewards in terms of dollar amount should be capped.

[kyle.anderson]

I agree with this assessment entirely. Realistically there should be an infinite number of votes per user. Although this does need to be reduced in practice, 30 might be way to small. I agree that on the order of several hundred should be the target.

DPOS comes with many tradeoffs against other consensus protocols.

I would really like to see an implementation of steem on another blockchain or using another consensus mechanism. No premine would have been nice too.

[clayop]

I basically agree with him, while have some differences in specific.

For DPOS, monitoring witnesses and removing bad or lazy witnesses are very important. In this sense, 100 seems too big to make dynamics in the top active witness list. I think around 30-50 is a good number.
As he said, 30 votes can make the witnesses dependent on few whales, as Steem is now. A further problem is 30 is too many for individuals to evaluate and monitor witnesses. The bigger the number, the psychological burden will exponentially increase. 1 is good number too, but I personally prefer 3-5, which is similar to the number of "very close relationship".

[kyle.anderson]

Well if you are not using all of your 100 votes, you should delegate that power to someone who is. Plain and simple.

[clayop]

That can end up with the concentration of power.

[kyle.anderson]

This is the drawback of DPOS. The 30 limit also imposes a concentration of power. It ultimately depends on the scale of the network.

[iang]

OK - that's a really important point.

Could we set up a rule that says a Producer cannot vote for any producer?

(Enforcement is tricky, because we can't show it easily. But when found out, it would be a substantial risk.)

[tonypeacock]

Wow very thorough and educational post. :)

[jacobt]

Great post! I wrote a blog the other day stressing the need that all blockchain projects need to adopt a clear and public governance policy.

https://steemit.com/bitcoin/@jacobt/governance-models-in-crypto

[jessy69]

its too good post. @iang

[arnel]

It is a long article but very well explained I should keep this on file so I can check it everytime until I digest all the information being discussed here... Thanks for sharing!

[kyriacos]

Darn man. This was an outstanding explanation. I am not well versed with the technology yet It was rather easy to follow.

[vmsolutionsltd]

I think what @jessy69 is saying is that it's too good to post.

Posts that need to be bookmarked are books that need to be published, amazing work. Respect.

[justtryme90]

DPOS is also used by Lisk I believe, to add to your above list.

[iang]

Hmmm... OK. I did a search on Lisk and can't find any good doco that talks about its use of DPOS. But yes it seems to be there.

[almvide]

Very good post, I did not know the energy cost for Bitcoin was that high! That will be unsustainable very soon I think.

[janreyqm1]

Interesting topic. Upvoted!

[licklake]

Awesome post! Thank you for your efforts :)

[samupaha]

I was going to leave a comment but it became so long that I made a whole post: From ad hoc governance to better governance

[cybercranium]

It would probably take me a million years to understand all of this.

[iang]

Please ask! We'd like to make it as simple as possible... but no simpler ;-)

[emonandels]

i like it. it is necessary .Greetings from emonandels

[otitrader]

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

[lautenglye]

nice...upvote and resteem for you...

[mrosenquist]

Really outstanding post! Clarity for a complex problem and a breakdown of pro/con's for DPOS. Well written @iang

[steemitboard]

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

Award for the number of upvotes

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!

[steemitboard]

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

Award for the number of upvotes 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!

[newgaia]

Thanks for a detailed explantion

[kodaxx]

This is a very well-written article explaining DPOS. I did not see the utility before, but now that you've broke it down it seems....revolutionary.

[peterchen145]

Can I translate this to Chinese?

[eoslinks]

I assume this is DPOS 3.0?

[steemblast.com]

Your Post Has Been Blasted on @SteemBlast.com!
Blast any Steemit post using SteemBlast.com
How Do I Blast My Post?
Go to your Steemit Post URL
2. Erase it in the address
3. Type blast and Go
Get Blasted Instantly – Blasted posts are 100% upvoted every 2.4hrs, Blast your post to Win.