Nakamoto Consensus Requires Social Coordination and Subjectivity
===

<small>This post is partially based on previous unpublished work written in collaboration with Mikerah Quintyne-Collins (@mikerah). Thanks to Mustafa Al-Bassam (@musalbas), Ismail Khoffi (@ismail), and Mikerah Quintyne-Collins (@mikerah) for review.</small>

<small>HackMD mirror: https://hackmd.io/Jad6tDZ5STCzPy2LjQyZIA</small>

Nakamoto Consensus has been demonstrated as a viable permissionless consensus protocol over the past decade. During that time, the idea of replacing wasteful Proof-of-Work with more environmentally-friendly Proof-of-Stake has seen widespread support. Unfortunately, Proof-of-Stake protocols have seen pushback due to their reliance on social coordination in the form of weak subjectivity, something that Nakamoto Consensus purportedly avoids. We discuss in this post a model for objectivity, subjectivity, and weak subjectivity, and show that Nakamoto Consensus, contrary to popular understanding, is not objective.

## Prerequisite Reading

It is expected that the reader is familiar with Nakamoto Consensus, Proof-of-Stake protocols, and the long-range attack.

- [Bitcoin: A Peer-to-Peer Electronic Cash System](https://bitcoin.org/bitcoin.pdf), Nakamoto
- [On Stake and Consensus](https://nakamotoinstitute.org/static/docs/on-stake-and-consensus.pdf), Poelstra ([old](https://download.wpsoftware.net/bitcoin/old-pos.pdf))
- [Proof of Stake: How I Learned to Love Weak Subjectivity](https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/), Buterin
- [Proof-of-Stake is less wasteful](https://medium.com/@ercwl/proof-of-stake-is-less-wasteful-b2854a191766), Wall

## Permissionless Consensus

The primary difference between Nakamoto Consensus and classical consensus protocols is that the former demonstrated, for the first time, _permissionless_ consensus under certain incentivized assumptions. Classical consensus protocols have traditionally only worked in permissioned environments, but [have since been adapted](https://eth.wiki/en/concepts/proof-of-stake-faqs) to operate in incentivized permissionless environments as well.

Permissionless consensus protocols (both Nakamoto and otherwise, with a few exceptions) typically consist of [four components](https://medium.com/@adlerjohn/the-why-s-of-optimistic-rollup-7c6a22cbb61a):
- A fork choice rule (how to choose between two otherwise valid chains)
- A block validity function (state transition function)
- A leader selection algorithm (who is permitted to attempt to progress the chain by extending its tip with a new block)
- A Sybil resistance mechanism (Proof-of-Work, Proof-of-Stake, etc.)

Together, they give a blockchain economic _security_: the cost of manipulating history. Nakamoto Consensus tightly couples its Sybil resistance mechanism, leader selection algorithm, and fork choice rule, but such a tight coupling isn't strictly necessary and [various](https://arxiv.org/abs/1607.01341) [Proof-of-Stake](https://eprint.iacr.org/2016/889) [protocols](https://arxiv.org/abs/1807.04938) have been developed that choose different schemes for these components.

### Objectivity and Subjectivity

Before diving into our analysis, we begin by describing a model for _objectivity_ and _subjectivity_ in permissionless consensus protocols for blockchains. A blockchain $\mathcal{C}$ is a hash-linked totally-ordered chain of blocks $\mathcal{C} = ( \{x_1, x_2, \dots, x_{|\mathcal{C}|}\} , \leq) = \langle x_1, x_2, \dots, x_{|\mathcal{C}|} \rangle$.

The scenario we consider is the following: we are given alternative otherwise-valid (i.e. block validity function passes) chains $\mathcal{C}_1, \dots, \mathcal{C}_N$, one of which is the globally canonical chain $\mathcal{C}_c$. We don't know which of the chains is the canonical one, but we assume that one of them is (this assumption will be true eventually in a synchronous network unless there is a permanent network partition, which would by definition preclude the existence of a single globally canonical chain). We can rank these chains with a weighting function $W : \mathcal{C} \to \mathbb{N}_0$ that computes a numerical weight for a chain. The network consists of a set of nodes $\mathcal{N}_1, \dots, \mathcal{N}_M$ that each run the weighting function locally as $W^{\mathcal{N}}(\mathcal{C})$.

A consensus protocol is _objective_ if the canonical chain always has maximum weight for all nodes, i.e.
$$
\forall m,n \in \{1, \dots, M\} \, \forall i \in \{1, \dots, N\} \\
( W^{\mathcal{N}_m}(\mathcal{C}_i) \leq W^{\mathcal{N}_m}(\mathcal{C}_c) \land W^{\mathcal{N}_n}(\mathcal{C}_i) \leq W^{\mathcal{N}_n}(\mathcal{C}_c) )
$$

A consensus protocol is _subjective_ if the canonical chain does not always have maximum weight for all nodes, i.e. it is possible to construct a set of otherwise-valid chains chains $\mathcal{C}_1, \dots, \mathcal{C}_N$ including canonical chain $\mathcal{C}_c$ such that
$$
\exists m,n \in \{1, \dots, M\} \, \exists i \in \{1, \dots, N\} \\
( W^{\mathcal{N}_m}(\mathcal{C}_i) \gt W^{\mathcal{N}_n}(\mathcal{C}_c) \lor W^{\mathcal{N}_n}(\mathcal{C}_i) \gt W^{\mathcal{N}_m}(\mathcal{C}_c) )
$$
with [non-negligible probability](https://arxiv.org/abs/1906.08936).

A consensus protocol is _weakly subjective_ if, given a single "checkpoint" hash included in the canonical chain $x^{*} \in \mathcal{C}_c$ that is no older than $P$ blocks old (the _weak subjectivity period_) and modified weighting function
$$
X(\mathcal{C}) =
\begin{cases}
W(\mathcal{C}) & \text{if $x^{*} \in \mathcal{C}$} \\
0 & \text{if $x^{*} \notin \mathcal{C}$}
\end{cases}
$$
, the canonical chain always has maximum weight, but if not given a checkpoint the canonical chain does not always have maximum weight, i.e.
$$
\forall m,n \in \{1, \dots, M\} \, \forall i \in \{1, \dots, N\} \\
( X^{\mathcal{N}_m}(\mathcal{C}_i) \leq W^{\mathcal{N}_m}(\mathcal{C}_c) \land X^{\mathcal{N}_n}(\mathcal{C}_i) \leq W^{\mathcal{N}_n}(\mathcal{C}_c) ) \land \\
\exists m,n \in \{1, \dots, M\} \, \exists i \in \{1, \dots, N\} \\
( W^{\mathcal{N}_m}(\mathcal{C}_i) \gt W^{\mathcal{N}_n}(\mathcal{C}_c) \lor W^{\mathcal{N}_n}(\mathcal{C}_i) \gt W^{\mathcal{N}_m}(\mathcal{C}_c) )
$$

Aside: note that objectivity and subjectivity only relate to the fork choice rule of a consensus protocol, and not the block validity function.

## Nakamoto Consensus and Objectivity

Nakamoto Consensus can be summarized in one statement as "heaviest chain" (colloquially: "longest chain"). Out of all alternatives, the chain with the most accumulated work (heaviest) is the canonical one.

If we define our weight function $W$ as the accumulated work, then it's trivial to see that Nakamoto Consensus is objective by the previous definition,

$$
\mathcal{C}_c \in \{ \mathcal{C} \mid \ W^{\mathcal{N}_1}(\mathcal{C}) = \max_{i = 0,\dots,N}{W^{\mathcal{N}_1}(\mathcal{C}_i)} \} \implies \\
\forall m,n \in \{1, \dots, M\} \, \forall i \in \{1, \dots, N\} \\
( W^{\mathcal{N}_m}(\mathcal{C}_i) \leq W^{\mathcal{N}_m}(\mathcal{C}_c) \land W^{\mathcal{N}_n}(\mathcal{C}_i) \leq W^{\mathcal{N}_n}(\mathcal{C}_c)
$$

and no further analysis is necessary (read: further analysis is necessary).

## Proof-of-Stake and Weak Subjectivity

Permissionless consensus protocols based on Proof-of-Stake generally work by having a set of bonded coin-holders (stakers) vote on blocks, with new blocks being added to the chain once a quorum is met. Such protocols cannot use the same longest chain fork choice rule as Nakamoto Consensus, as there is no cost to producing alternative chains (known as [_costless simulation_](https://nakamotoinstitute.org/static/docs/on-stake-and-consensus.pdf)), and thus an unbounded number of equally-weighted and equally-valid chains can be produced trivially.

There are two issues that allow for costless simulation: _short-range attacks_ and _long-range attacks_. In the former, individual stakers vote for two conflicting chains (equivocate) while still bonded. This can be resolved easily by penalizing (e.g. [slashing](https://blog.ethereum.org/2014/01/15/slasher-a-punitive-proof-of-stake-algorithm/)) still-bonded stakers, introducing a cost for equivocating, much like how there is a cost to working on two different chains in Nakamoto Consensus. The latter attack is where the real issues and debates arise.

The [long-range attack](https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/) is performed by stakers who have already unbonded---and as such, cannot be penalized in any way. Previous stakers who have unbonded, and potentially even sold all their coins entirely, can create a chain from an old block with equal or greater weight than the canonical chain trivially. This can be resolved with a weak subjectivity assumption: new nodes or nodes that have been offline for longer than the weak subjectivity period $P$ must acquire a trusted checkpoint from a third party to inform their fork choice.

_Aside: the long-range attack can also be solved using forward secrecy, but that is unenforceable at the consensus level, instead requiring the use of [Trusted Execution Environments](https://en.wikipedia.org/wiki/Trusted_execution_environment). Detailing the many downsides of Trusted Execution Environments is outside the scope of this post._

Combining both mitigations, all nodes will agree on the same chain being canonical, which is guaranteed to be in the prefix of all future canonical chains unless a short-range attack occurs, which would require a significant fraction of stake to be penalized (usually > 1/3).

It should be clear that 1) such a protocol that relies on weak subjectivity actually does work, yet 2) it seems to have different trust assumptions than Nakamoto Consensus. Indeed, [Poelstra15](https://nakamotoinstitute.org/static/docs/on-stake-and-consensus.pdf) concedes the former and pinpoints the latter:
> If this is implemented correctly, there is no problem with this, except that it changes the trust model from that of Bitcoin. New users who encounter multiple histories are no longer able to distinguish them on their own; they need to ask existing participants in the network (which may include friends and family, large corporate entities with reputations to maintain, public websites, etc.) which history they know to be the true one. This is not a distributed consensus! It is a different sort of consensus, which may be formed amongst always-online peers in a decentralized way, but depends on trust for new users and temporarily offline ones. It is correspondingly vulnrable [sic] to legal pressure, attacks on "trusted" entities, and network attacks.

Rewording the above: so long as everyone is online, Proof-of-Stake protocols can be made to work just as well as Nakamoto Consensus, but such protocols require strictly stronger trust assumptions than Nakamoto Consensus for new users (note that new users are identical to users that have been offline since the genesis of the chain). This criticism is incorrect, and we will find out why in the next section.

## Nakamoto Consensus is Objective...or is It?

As discussed above, the Nakamoto Consensus protocol, at first glance, is objective. And indeed it is! However, the consensus protocol on its own does not---and [provably _cannot_](https://www.coindesk.com/gregory-maxwell-went-bitcoin-skeptic-core-developer)---work **without an incentive** to encourage a majority of the Sybil resistance mechanism to progress the canonical chain. From [Nakamoto08](https://bitcoin.org/bitcoin.pdf):

> He ought to find it more profitable to play by the rules, such rules that favour him with more new coins than everyone else combined, than to undermine the system and the validity of his own wealth.

We will call this the Nakamoto Incentive, and it applies to both Nakamoto Consensus and Proof-of-Stake-based consensus protocols. A majority of hashrate is incentivized to behave honestly as that is the most profitable strategy (barring [selfish mining strategies](https://arxiv.org/abs/1311.0243)). So long as a majority of hashrate behaves honestly at all times, the current canonical chain is guaranteed to be a common prefix of all future canonical chains with overwhelming probability.

But what, specifically, is the mechanism of this incentive? Breaking down the original text, it contains an incentive "such rules that favour him with more new coins than everyone else combined" and a disincentive: "than to undermine the system and the validity of his own wealth," the latter being the more interesting of the two. The disincentive describes _undermining the system_, which in the decade since the original design paper was published we can now describe more precisely as 1) re-organizing (re-orging) the chain by making a new canonical chain that does not include the current one as a prefix and 2) censoring transactions from being included in the chain. For simplicity, we will analyze re-orgs and leave censorship as an exercise for the reader.

_Note that we do not need to consider "the validity of his own wealth" at all, and indeed there are numerous interpretations, ranging from the price of coins held to the value of mining hardware to anything in between._

Stated more precisely, the Nakamoto Incentive is a disincentive whereby if a majority of hashrate performs a re-org, a penalty is applied that affects this dishonest majority (and potentially others, but that is the subject of another post). A penalty _must_ be applied, since without penalty there is no disincentive to attacking the chain. Therein lies the problem: how can it be _proved_ that a re-org happened?

We note that for a new node performing [Initial Block Download](https://developer.bitcoin.org/devguide/p2p_network.html#initial-block-download), a re-org is indistinguishable from stale blocks. In other words, **detecting a re-org** (and thus, detecting that the system is being undermined) **requires being online at the time of the re-org**. It is impossible to prove that a re-org happened to a new node without an additional trust assumption, and indeed it is impossible to prove an attack _did not happen_ without the same.

A new node can certainly objectively determine a canonical chain, but the user of that node is not guaranteed that that chain is the "real" chain without additional information external to the blockchain, a facet that cannot be captured by analyzing Nakamoto Consensus in isolation of its incentive. Since it is impossible to prove an attack did not happen, this additional information---a trust assumption---must be acquired by all users that have been offline for longer than a period of time (undefined and nebulous in the case of contemporary deployments of Nakamoto Consensus, well-defined in the case of modern Proof-of-Stake-based protocols), all the time, even if an attack did not occur.

Thus, the Nakamoto Incentive requires a subjective social coordination component---a trust assumption that is no weaker than weak subjectivity. Since Nakamoto Consensus is dependent on the Nakamoto Incentive, it follows that Nakamoto Consensus requires subjectivity to function.

For the purposes of illustration, consider a scenario where a 100-block re-org occurred on Bitcoin. In this example, the penalty is a significant drop in the price of the coin (the exact penalty is irrelevant, it suffices that a penalty exist). Currently-online users would support the penalty by selling their coins---now worthless as the chain has been shown to not provide security against manipulation of history. But new users would simply see a good buying opportunity for cheap Bitcoin and be completely unaware that a re-org occurred, _and existing users would be unable to cryptographically prove to them that a re-org occurred_. With---and only with---a social coordination layer however, the penalty can be applied swiftly and permanently.

## How We Learned to Love Weak Subjectivity

Now that it has been shown that Nakamoto Consensus requires a subjective component, what kind of consensus protocols can be build that explicitly parametrize for subjectivity in the form of weak subjectivity?

Among others:
- Proof-of-Stake: The only barrier to viable Proof-of-Stake-based consensus protocols over Nakamoto Consensus is the long-range attack, which is resolved perfectly using weak subjectivity. Proof-of-Stake protocols have the benefit of being substantially more energy-efficient [and secure](https://medium.com/@ercwl/proof-of-stake-is-less-wasteful-b2854a191766) than Nakamoto Consensus.
- Censorship resistance: Online nodes can detect transaction censorship, just as they can detect re-orgs, and apply penalties when censorship occurs. This opens the door for [optimistic L2 solutions](https://ethresear.ch/t/minimal-viable-merged-consensus/5617) with _equal_ security to [validity-proof-based L2 solutions](https://ethresear.ch/t/on-chain-scaling-to-potentially-500-tx-sec-through-mass-tx-validation/3477), along with [fraud and data availability proofs at the base layer](https://arxiv.org/abs/1809.09044).

## Conclusion

In this post we analyze Nakamoto Consensus and contrast it with Proof-of-Stake-based permissionless consensus protocols. We find that Proof-of-Stake protocols must be subjective, while Nakamoto Consensus is objective, but only when considering the consensus protocol in isolation. When also considering the Nakamoto Incentive---the critical feature that makes Nakamoto Consensus work in the first place---further analysis reveals that subjectivity is in fact required for the incentive, and thus Nakamoto Consensus _taken as a whole_ is subjective. As such, Proof-of-Stake protocols _do not_ have strictly stronger trust assumptions than Nakamoto Consensus.