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:
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.
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:
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 this1 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-locked2 then it shows the owner has interest in the project’s long term success.
Idea 2 (Distributed Consensus) A distributed consensus is an agreement between parties. That agreement is global. The parties don’t have to trust each-other. The parties don’t need identities. The parties didn’t need to have been present when the system started.
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).3 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.4
(Other problems with blockchains are easy and we know how to solve them.)
We can prove that distributed consensus cannot be cryptographically guaranteed on an async network.5 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.6 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.7 Also, one miner can’t control the consensus history without help from their peers.8
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”9 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.10
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:
PoS equates state to temporarily sacrificed [internal] resources. This begs the question of consensus on who owns what.11 PoS fans evade this problem with the argument:
The problem with the argument is simple.12 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.13 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).14 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 longer15 than the existing public history. But every block16 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 change17 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.
Intuitively, no, but there’s no rigorous argument.
The problem comes down to costless simulation18 or nothing at stake.19 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.)
This should get merged into the ”Distributed Consensus” part of A Treatise on Altcoins, but that article isn’t done, so this20 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.
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.
1Which context? I am guessing the context of a public(!) distributed ledger; sending cryptocoins on a public net. The list provided above plus the ”instead of …one can say …” bit.
2Time-locked means that the coins can’t be spent by the owner till some point in the future.
3ET feedback: what about if transactions happened at all? MK: We need that too. Not mentioned in the original paper.
4The author is a bit unclear b/c of the way they’ve worded it. They haven’t considered the case of two recipients, etc. Personally I think they should have left most of that out; it was unnecessary.
5The author cites: M.A. Fischer, N.A. Lynch, and M.S. Paterson, Impossibility of distributed consensus with one faulty process, J. Ass. for Comp. Mach.32(1985), no. 2, 374–382.
6Particularly proofs of work include all work done in the history the miner selects, and not proofs were from other histories.
7If they don’t, then they won’t be able to spend the reward.
8ET pointed out 51% attack is not mentioned here.
9Pfft. No it doesn’t. The laws of physics would go way faster. Also the author needs to learn about basic economics. Basic physics too.
10I think the original paper is missing some details but they’re not super important here.
11This is because we are trying to answer the question ”who owns what” (consensus) by using the last answer of ”who owns what?” I think that’s what the author means by ”begging the question”. They should try to be more clear and less fancy.
12I doubt that, but let’s continue…
13The author says ”This is abstruse”, which I hope wasn’t a joke b/c it’s stupid if it was. Also, the last paragraph started with ”The problem with this argument is simple” – get your message straight!
14Original sentence: ”This may have happened organically, if this person’s keys were chosen randomly by the stake-choosing algorithm, but it could also happen if this person tracks down the other keyholders and buys their keys.”
15”Longer” is approximately correct but it might mean different things for different networks; like for proof-of-work networks it can mean ”more work done” rather than ”more blocks”
16or epoch, whatever
17They’re changing the alternate history they’re in the process of creating.
18The author notes this is what Greg Maxwell calls it.
19The author notes this is what Andrew Miller calls it
20In this paragraph ”this” refers to the author’s original article, linked at the top.