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

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.