Proof-Of-Work Is Objective, Proof-Of-Stake Is Not

The proof-of-work consensus mechanism used in Bitcoin is an objective measure of history which cannot be changed on the whims of validators.

Alan Szepieniec holds a PhD in post-quantum cryptography from KU Leuven. His research focuses on cryptography, especially the kind of cryptography that is useful for Bitcoin.

Proof-of-stake is a proposed alternative consensus mechanism to the proof-of-work that Bitcoin’s consensus mechanism uses. Instead of requiring the consumption of energy, proof-of-stake requires miners (usually called validators) to put digital assets at stake in order to contribute to the block production process. Staking incentivizes them to behave honestly, so as to avoid losing their stake. In theory, with only honest validators, the network will quickly come to consensus about the order of transactions and, therefore, about which transactions are invalid double-spends.

Proof-of-stake has been the subject of much debate. Most criticisms focus on security: Does it decrease the cost of attack? Many people also articulate sociological concerns: centralization of power, concentration of wealth, plutocracy, etc.

In this article, I articulate a much more basic criticism: Proof-of-stake is inherently subjective. The correct view of a proof-of-stake blockchain depends on whom you are asking. As a result, the cost of an attack cannot be calculated in units internal to the blockchain, making security analyses void; debts cannot be settled between parties that do not already agree on which third parties are trustworthy; and the final resolution of disputes must come from courts.

In contrast, proof-of-work is an objective consensus mechanism where any set of related or unrelated parties can come to agreement about which state of the blockchain is accurate. As a result, any two economic actors can agree on whether a payment has been made, independently of courts or influential community members. This distinction makes proof-of-work suitable — and proof-of-stake unsuitable — as a consensus mechanism for digital currencies.

One of the most basic operations that computers perform is copying information. This operation leaves the original copy intact and produces an exact replica at essentially no cost. Computers can copy just about anything, as long as it is digital.

However, there are some things that exist purely in the digital realm that can’t be copied. Things that are both digital and scarce. This description applies to bitcoin for example, as well as to other blockchain-based digital assets. They can be sent, but after sending them the original copy is gone. One might disagree with the reason why the market demands these assets, but the fact that this demand exists means that these digital assets are useful as a counterpart to balance exchanges. When condensed to a single word: they are money.

To achieve digital scarcity, the blockchain protocol replicates a ledger across a network. The ledger can be updated, but only with transactions where the owners of the spent funds agree; the net sum is zero; and the outputs are positive.

Any invalid update will be rejected. As long as there is consensus about the state of the ledger among all participants in the protocol, digital scarcity is guaranteed.

It turns out that achieving consensus is a difficult task. Imperfect network conditions generate distinct views of history. Packets are dropped or delivered out of order. Disagreement is endemic to networks.

Blockchains address this problem in two ways. First, they enforce a complete ordering on all transactions, which generates a tree of alternative views of history. Second, they define canon for histories, along with a fork-choice rule that selects the canonical branch from the tree of histories.

It is easy to derive canonicity from trusted authorities or, according to some, from a digital voting scheme backed by a citizen identity scheme. However, trusted authorities are security holes, and relying on the government to provide trusted identification services becomes a tool of politics rather than one that is independent of it. Moreover, both solutions assume agreement about the identities and the trustworthiness of third parties. We want to reduce trust assumptions; ideally we have a solution that derives entirely from mathematics.

A solution for deciding canonicity that derives entirely from mathematics generates the remarkable property that the answer is independent from whoever computes it. This is the sense in which a consensus mechanism is capable of being objective. There is one important caveat though: one must assume that all parties agree on a singular reference point, such as the genesis block or its hash digest. An objective consensus mechanism is one that enables any party to extrapolate the canonical view of history from this reference point.

Which branch of the tree is selected to be canonical is not important; what is important is that all participants can agree on this choice. Moreover, the whole tree need not be represented explicitly on any one computer. Instead, it suffices for every node to hold only a handful of branches. In this case the fork-choice rule only ever tests two candidate views of history at any one time. Strictly speaking, the phrase the canonical view of history is misleading: A view of history can only be more or less canonical relative to another view. Nodes drop whichever branch is less canonical and propagate the one that is more. Whenever a view of history is extended with a batch of new transactions, the new view is more canonical than the old one.

In order for the network to rapidly converge onto consensus about the canonical view of history, the fork-choice rule needs to satisfy two properties. First, it must be well-defined and efficiently evaluable for any two pairs’ views of history. Second, it must be transitive for any triple of views of history. For the mathematically inclined: let U,V,W be any three views of history, and let the infix “