PoS Blockchains Require Subjectivity to Reach Consensus


#1

I came across an interesting paper under review from researchers at IC3. Among other things, it contains a mathematical proof that it is impossible to determine the “true” transaction history in a PoS blockchain without an additional source of trust. In other words, the idea of weak subjectivity promulgated by Vitalk Buterin (creator of Ethereum) is a hard requirement in the design of any PoS blockchain. The full paper from IC3 is here.

To elaborate, the proof (section 6) shows that if a node has been disconnected for a sufficiently long period of time or is bootstrapping, and is presented with two conflicting transaction histories, then it is impossible for it determine which one is the “true” chain without some external input. This is because it is impossible to know whether or not the “committee” that validates the chain is majority-honest and not post-facto corrupted (i.e. attacker-controlled). In practice, this means that the user will have to resolve the conflict out-of-band, using some a priori knowledge about the honesty of the chain’s current committee. This is not the case for PoW blockchains, where the valid chain with the most cumulative proof-of-work is always the “true” chain.

Why this is Relevant?

I bring this up because there is a lot of active research in finding open consensus algorithms that do not depend on proof-of-work. This finding has wide-ranging implications for applications built on PoS blockchains. In PoS, it is already the case that hard-forks and history-rewriting are extremely cheap, since they cost little energy to produce. Anyone can create their own history, and now we have a paper that shows that selecting the “true” history requires buy-in from the user.

I personally find this interesting because requiring users to decide on the “true” chain opens up a whole new class of “manufatured consensus” attacks against such blockchains. In a manufactured consensus attack, the adversary focuses on tricking users instead of subverting the underlying algorithms. For example, an adversary can knock nodes off-line for long enough to trick them into accepting the attacker-chosen history. This is particularly relevant for efforts that want to embed a blockchain client in IoT devices, which already have to contend with long periods of disconnected operation. As another example, an adversary can can wage a PR campaign to trick new users into accepting an alternative history where the adversary is already rich and controls many Sybil accounts. This would allow the attacker to stake more tokens than staked in the main history, and make it appear to new users like the alternative history has higher security. Neither of these attacks are feasible in PoW, since in both cases, the adversary must also produce a valid chain with more proof-of-work than any other chain.

This is not to say that PoS is insecure or is a bad idea. However, it does show that PoS and PoW make fundamentally different security assumptions. Application designers need to take these assumptions into account when choosing a blockchain to build on. For example, Blockstack calculates a per-block consensus hash that helps users select the right transaction history regardless of whether or not the underlying blockchain is PoS or PoW.


#2

I used to present this argument as an attacker presenting a sufficiently large number of conflicting histories to a node, but the framing as a new node deciding between two conflicting versions of the chain is a much better framing because it’s a more practical scenario and easier to reason about it.

It’s great to see efforts to formalize proof-of-stake protocols and have arguments around formal proofs. I haven’t read the paper in detail yet. Where is it under review?


#3

This is a great post and really highlights the problem with standalone or “native” PoS. The algorithms have their place but they have to be used very carefully alongside trustless systems. i.e. - the “external input” to determine which PoS history is true should be the available from a PoW chain history. Rather than being backwards-looking (determine which history is true), PoS can only help you determine which chain the rest of the network is committed to for the future.

You can build your way up to networks using this approach since you can bootstrap the state from a globally trustless system first. For that to work properly, you need enough information in the parent chain to enable you to resolve the conflict. To do PoS in a trustless way, it’s not stake in the chain needing conflict resolution, but a stake placed in the parent system, that you need to figure it out.


#4

So PoS as a Layer 2 system :wink:


#5

PoS can only help you determine which chain the rest of the network is committed to for the future.

That’s a really good insight. Building on this and the IC3 paper, it makes me wonder if PoS algorithms are really just reformulations of classical agreement algorithms (e.g. N processes try to agree on shared history H).

What if we drew a one-to-one correspondence between staked tokens and processes? Then, could we claim the following?

  • Agreeing on a block would be equivalent to the N processes agreeing on a sequence of transactions.
  • Each block minted would be equivalent to an epoch (i.e. a leader election)
  • Adding or removing staked tokens would be equivalent to a configuration change (i.e. some processes are admitted; others leave).

If we can claim these, then PoS would reduce to a layer of indirection. Instead of N processes trying to agree on H, we would have N “virtual” processes (tokens) spread across an arbitrary number of physical hosts trying to agree on H. But the agreement algorithms they execute would otherwise be the same well-studied algorithms from classic distributed systems.


#6

Yes PoS is just an oracle for resolving a chain conflict in the same way that PoW computational power is an oracle for resolving a chain conflict. Once you have Bitcoin you don’t have to spend power, you just spend Bitcoin, what matters is Proof of Irreversibility. Consensus algorithms and signature schemes both serve the same role of determining agreement - we pick identity (trust) or work (proof) depending on the tradeoff we want to make for performance or security. PoS and threshold crypto are very similar but one is proof-based and one is identity-based. You start merging the two when you go layer-2. I don’t see any future for ethereum unless Casper is done using BTC as the token at stake.

The great thing is it’s all just data and irreversibility, all you actually need in these systems is an economically-final global hash root with shared state you can write to.


#7

This is indeed a very good point! In regular PoS systems, both conflicting blockchains will be valid and look equally legitimate. Basically, history-rewriting is possible if you control more historic stake (at some point in the past) than stake thas has been involved in mining the legitimate chain since then.

If you are using old keys that have sold their stakes in the meantime, you will actually compete against the group of active miners starting from the branching point of your fork. So, the claim in Neucoin’s whitepaper, p. 30, that you would compete against 100% of the current stake is incorrect (or not precise enough).

However, I think I have found a method how you can leverage the votes of all miners that were active in the past to secure the blockchain for the future. In my proposed model (which is not exactly Proof-of-Stake but more like a Sybil-resistant Proof-of-Account system), every miner has to make “heartbeat” transactions (referencing a recent block) validating the current blockchain to stay alive. Non-cooperating accounts are eventually degraded. If we assume that most miners wouldn’t risk their accounts and their intrinsic monetary value, they would validate the blockchain regularly. So, the validator group would consist of the overwhelming majority of miners.

This property can be leveraged later on to make history attacks much more difficult. The idea is to have an additional chain selection rule for long-range forks: You just count the number of unique heartbeat transactions contained in (a predefined section) each chain fork, cancelling the heartbeats coming from accounts that voted for both chains. The chain with the most unique validations wins. With such a model, you can push the majority required for history attacks to well-above 90%.