Reading: Distributed Consensus from Proof of Stake is Impossible

Date: 2020-08-30

Distributed Consensus from Proof of Stake is Impossible PDF: old-pos.pdf, (permalink)

The paper Distributed Consensus from Proof of Stake is Impossible has been criticised as being hard to read and understand.

My goal is to accurately analyse the paper to extract its arguments, and re-express them in simple language.

Links for tutorial 34:

• X, if Y, but Z

Contents

1 Reading: Introduction

People propose that proof-of-stake (PoS) can be used to protect blockchains. The proposition to use proof-of-stake is flawed. The paper looks at the history and motivation of proof-of-work (PoW) (as used in Bitcoin). PoW ”evades a impossibility result” [sic]. The paper shows PoS is not a viable replacement.

2 Reading: Proof of Stake

2.1 Reading: What is Proof of Stake?

As cryptography has progressed, the idea that [information can be real and valuable] is being taken seriously. People know about economic activity which depends on crypto stuff. Business stuff can be done on the public internet safely. People also know about bad things that happen if secret data is lost.

Since Bitcoin, Idea 1 is concrete. All at once:

• You can hold and trade a fungible ”store of value” (i.e. money).
• You can do this using the internet.
• You can do this with cryptographic security, instead of physical security.
• The security prevents fraud and theft.

Instead of ”this key is worth $X because that is the cost of it being public”, one can say ”this key is worth $X but is divisible, you can send $Y to someone but keep the rest”.

Proof-of-stake is simple in this¹ context. ”A proof of stake is a cryptographic proof of ownership.” That proof can prove (precise) ownership of coins. It can also prove that the coins satisfy some property, like being locked up.

Particularly: a proof of stake of some cryptocurrency is like a proof that the hodler/stakeholder will benefit if the projects succeeds. If the stake (from the proof) is time-locked² then it shows the owner has interest in the project’s long term success.

2.2 Reading: What is distributed consensus?

A synchronous network is required. You can’t assume nodes need to agree on precise timing of events or the order of events. You can’t make that assumption for networks over the internet anyway.

For blockchains, we just need distributed consensus on the order of transactions (and nothing else).³ That means nodes must agree on the first transaction that moves particular funds. That means the recipient can trust that the network treats those coins as his.

The double-spending problem is the reason we need distributed consensus. Someone could always try to send the same money to two different people. Both transactions could look valid. Recipients need to know that if there are conflicts about ownership they will still get their money. Distributed consensus means nodes can agree that the one recorded first is the right one.⁴

(Other problems with blockchains are easy and we know how to solve them.)

2.3 Reading: How does Bitcoin achieve distributed consensus?

We can prove that distributed consensus cannot be cryptographically guaranteed on an async network.⁵ Bitcoin gets around this by only requiring an economic guarantee. It does this via external opportunity cost. That opportunity cost is CPU time and electricity. Bitcoin provides rewards within the system, but only if consensus and an unbroken transaction history is maintained.

Proofs of work in Bitcoin prove an opportunity cost was paid and how much it was. Such a proof includes all work (past proofs) up to that point.⁶ Bitcoin nodes choose the history with the most total work as the valid history to extend. (Though it can be a bit fuzzy at the head if there are multiple options.) This history is called the consensus history. You can only spend coins on the consensus history. So miners are incentivised to all work on the same history.⁷ Also, one miner can’t control the consensus history without help from their peers.⁸

2.4 Reading: How is proof of stake used to achieve distributed consensus?

The big idea behind PoS is to move opportunity cost from outside the system to inside it. People want to do this because PoW incentivises ppl to do as much work as possible. Bitcoin work is thermodynamic work. For this kind of work, the Landauer limit lets us figure out what ”as much work as possible” means. The result is a network that uses a lot of energy. This drives us towards the heat death of the universe. It drives us ”literally as fast as the laws of physics will allow”⁹ If opportunity cost is inside the system we should be able to use fewer resources (and limit their usage).

PoS works b/c currency holders can lock up their funds (”stake”) in some staking scheme. This action is cryptographically verifiable. Particular people publish signed updates to extend the chain’s history. Normally a small random selection of people are chosen to do this, and only a majority need to agree to publish an extension. Those people get a reward and can unlock their stake later.¹⁰

PoS doesn’t depend on the high cost of taking control of the main history (unlike PoW). Instead, PoS says stakeholders will agree on the extension. They’ll do this b/c:

• they’re randomly chosen so are unlikely to collude, and
• they don’t want to undermine the system anyway, and
• they can’t do much damage anyway b/c new random stakeholders will be chosen soon who will probably agree on a single history to extend.

2.5 Reading: What is wrong with this mechanism for consensus?

PoS equates state to temporarily sacrificed [internal] resources. This begs the question of consensus on who owns what.¹¹ PoS fans evade this problem with the argument:

• False histories must be made by stakeholders, and
• Stakeholders’ power is limited to a short interval, and
• When they have power they’re incentivised to behave.
• Therefore conflicting histories won’t happen, and
• the ”weak synchronicity” is enough to agree on a single history.

The problem with the argument is simple.¹² The problem is to do with what ”short interval” means. It’s only short relative to the full history. The full history (”consensus history”) has to exist for ”short interval” to mean something. [But the full history is based on stakeholders’ balances.] So we’re still begging the question. A stakeholder has no incentive to be honest if they sell their stake (like at an exchange). This means they can’t be punished for forking the history at the time they had control. They could also expose their private keys and let others fork the history.

This is difficult to understand.¹³ We can use an example. Suppose that earlier, a single person could add blocks. It might have happened naturally, if the keys were chosen by some algorithm, or it could happen if the person got other private keys (maybe by buying them).¹⁴ The person getting all the relevant keys can happen much later, and keyholders aren’t incentivised to keep their keys secret after they use them. Keyholders also might accidentally reveal their keys, and the chance of that increases over time.

Now we have an attacker who can fork the chain at an earlier point in time. To replace the consensus history the attacker needs to make an alternate history, starting from his fork, and this new history needs to be longer¹⁵ than the existing public history. But every block¹⁶ needs new signers. Can the attacker still do the attack? Yes: we used the word ”random” but the network needs to agree on the new signers (otherwise we’d get lots of forks), so the new selection has to be based on past history. That means an attacker with enough past signing keys can change¹⁷ the history they control so that their keys are always selected for the next part. (The attacker probably needs to try lots of different options to find a way to continue the consensus history so he keeps control. It’s like the attacker replaced proof-of-stake with proof-of-work but centralised around themselves.)

This ability to control future selections of stakeholders (and maybe even the set they’re chosen from) is bad. It’s bad – even if no one is trying to attack the network – because the signers who extend history have an incentive to choose futures better for them, so the system will get centralised. They can do this by manipulating future selection processes, or blocking transactions that would introduce potential new signers.

2.6 Reading: Is it possible to obtain a distributed consensus without provably consuming some re-source outside of the system?

Intuitively, no, but there’s no rigorous argument.

The problem comes down to costless simulation¹⁸ or nothing at stake.¹⁹ If there’s (virtually) no cost for signers to make blocks, they can easily search for blocks with a better future for them. Regardless of the safeguards to prevent minority-rule, an attacker can influence the consensus history towards a future we’re they’re the majority, even if they’re the only physical party (they might have lots of keys).

It appears that whatever ”space” we want distributed consensus in, we need opportunity cost in that space. (For Bitcoin, it’s the ”space of humans”, which is roughly thermodynamic space, since we’re agents in that space.)

3 Reading: About this document.

This should get merged into the ”Distributed Consensus” part of A Treatise on Altcoins, but that article isn’t done, so this²⁰ article is being published on its own.

This topic is hard to discuss on IRC because incentive analysis and cryptography interact. The goal of this article is to make the fundamentals clear and give relevant discussions better foundations.

4 Comments

The author makes some mistakes and there are some other problems. The mistakes are partially due to using a fancy writing style. They don’t compromise the main argument, but do make the article harder to read.

There’s also some things that are unnecessary, I think. One example is going into the double-spending problem. I don’t know who would want to read this document if they don’t already understand the double-spending problem.

Some parts were hard to outline accurately b/c the sentences were complex. For those parts I made lists instead.

---

You can leave a comment anonymously. No sign up or login is required. Use a junk email if not your own; email is only for notifications—though, FYI, I will be able to see it.

---