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.

Digital Money And Consensus

The Problem That Needs Solving

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.

The Fork-Choice Rule

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 “<” denote the fork-choice rule favoring the right-hand side over the left. Then: either

• U<V

or

• V<U
• U<V∧V<W⇒U<W

In order for the ledger to accommodate updates, views of history must be extendable in a way that is compatible with the fork-choice rule. Therefore, two more properties are required. First, when evaluated on two views where one is an extension of the other, the fork-choice rule must always favor the extended view. Second, extensions of a (formerly) canonical view are more likely to be canonical than extensions of non-canonical views. Symbolically, let “E” denote an extension and “‖” the operation that applies it. Then:

• U<U‖E
• U<V⇒Pr[U‖E<V‖E]>12

The last property incentivizes honest extenders to focus on extending canonical views as opposed to views that they know are not canonical. As a result of this incentive, distinct views of history that arise from honest but contradictory extensions simultaneously tend to differ only in their tips, where recent events are concerned. The further back an event is logged, the less likely it will be overturned by the reorganization imposed by another, more canonical, view of history that diverges at an earlier point. From this perspective the canonical view of history is well-defined in terms of the limit of views of history to which the network converges.

The obvious disqualifier in the previous paragraph is the need for extenders to behave honestly. What about dishonest extenders? If the adversary can control the random variable implicit in the probability expression, then he can engineer it to his advantage and launch deep reorganizations with high success probability. Even if he cannot control the random variable, but can produce candidate-extensions cheaply, then he can evaluate the fork-choice rule locally and indefinitely until he finds an early-on point of divergence along with an extension that happens to generate a more canonical branch than any one that circulates.

The missing piece of the puzzle is not a mechanism that prevents dishonest extensions. In an environment of imperfect network conditions, it is impossible to delineate dishonest behavior. An attacker can always ignore messages that are not to his liking, or delay their propagation and claim that the network connection is to blame. Instead, the missing piece of the puzzle is a mechanism that makes deep reorganizations more expensive than shallow ones, and more expensive the deeper they go.

Cumulative Proof-Of-Work

Satoshi Nakamoto’s consensus mechanism achieves precisely this. In order to propose a new batch of transactions (called blocks), and thereby extend some branch, would-be extenders (called miners) must first solve a computational puzzle. This puzzle is expensive to solve but easy to verify, and is thus aptly named proof-of-work. Only with the solution to this puzzle is the new batch of transactions (and the history it commits to) a valid contender for canon. The puzzle comes with a knob for adjusting its difficulty, which is automatically turned in order to regularize the expected time before a new solution is found, regardless of the number of participants or the resources they devote to the problem. This knob has a secondary function as an unbiased indicator of puzzle-solving effort in a unit that measures difficulty.

The process is open to anyone’s participation. The limiting factor is not authority or cryptographic key material or hardware requirements, rather, the limiting factor is the resources one is willing to expend in order to have a chance to find a valid block. The probabilistic and parallel nature of the puzzle rewards the cost-effective miner who maximizes the number of computations per joule, even at the cost of a lower number of computations per second.

Given the target difficulty parameter (the knob) for every block, it is easy to calculate an unbiased estimate of the total amount of work that a given branch of history represents. The proof-of-work, fork-choice rule favors the branch where this number is larger.

Miners race against each other to find the next block. The first miner to find it and successfully propagate it wins. Assuming that miners are not sitting on valid but unpropagated new blocks, when they receive a new block from competing miners, they adopt it as the new head of the canonical branch of history because failing to do so puts them at a disadvantage. Building on top of a block that is known to be old is irrational because the miner has to catch up with the rest of the network and find two new blocks in order to be successful — a task which is, on average, twice as hard as switching to the new, longer branch and extending that. In a proof-of-work blockchain, reorganizations tend to be isolated to the tip of the tree of history not because miners are honest, but because the cost of generating reorganizations grows with the depth of the reorganization. Case in point: according to this stack exchange answer, excluding forks following software updates, the longest fork on the Bitcoin blockchain had length 4, or 0.0023% of the block height at the time.

Proof-Of-Stake’s “Solution”

Proof-of-stake is a proposed alternative to proof-of-work in which the correct view of history is not defined in terms of the greatest amount of work spent on solving cryptographic puzzles, but rather defined in terms of the public keys of special nodes called validators. Specifically, validators sign new blocks. A participating node verifies the correct view of history by verifying the signatures on the constituent blocks.

The node doesn’t have the means to distinguish valid views of history from invalid ones. The point is that a competing block is only a serious contender for the tip of the correct view of history if it has a supporting signature (or many supporting signatures). The validators are unlikely to sign alternative blocks because that signature would prove their malicious behavior and result in the loss of their stake.

The process is open to the public. Anyone can become a validator by putting a certain amount of cryptocurrency in a special escrow account. This escrowed money is the “stake” that is slashed if the validator misbehaves. Nodes verify that the signatures on new blocks match the public keys supplied by validators when they put their stakes into escrow.

Formally, in proof-of-stake blockchains, the definition of the correct view of history is entirely recursive. New blocks are valid only if they contain the right signatures. The signatures are valid with respect to the public keys of the validators. These public keys are determined by old blocks. The fork-choice rule is not defined for competing views of history, as long as both views are self-consistent.

In contrast, the correct view of history in proof-of-work blockchains is also defined recursively, but not to the exclusion of external inputs. Specifically, the fork-choice rule in proof-of-work also relies on randomness whose unbiasability is objectively verifiable.

This external input is the key difference. In proof-of-work, the fork-choice rule is defined for any pair of different competing views of history, which is why it is possible to speak of canon in the first place. In proof-of-stake, it is only possible to define correctness relative to a prior history.

Proof-Of-Stake Is Subvertible

Does it matter though? In theory, for two consistent but mutually incompatible views of history to be produced, somewhere someone must have been dishonest, and if they behaved dishonestly, it is possible to find out where, prove it and slash their stake. Since the validator set at that first point of divergence is not in dispute, it is possible to recover from there.

The problem with this argument is that it does not take time into account. If a validator from ten years ago double-signs mutually conflicting blocks — that is, publishes a newly signed contradictory counterpart to the block that was confirmed ten years ago — then the history will need to be re-written from that point onwards. The malicious validator’s stake is slashed. Transactions that spend the staking rewards are now invalid, as are transactions downstream from there. Given enough time, the validator’s rewards may percolate to a large part of the blockchain economy. A recipient of coins cannot be sure that all dependencies will remain valid in the future. There is no finality because it is not more difficult or costly to reorganize the far past than the near past.

Proof-Of-Stake Is Subjective

The only way to solve this problem is to restrict the depth at which reorganizations are admitted. Conflicting views of history whose first point of divergence is older than a certain threshold age are ignored. Nodes that are presented with another view whose first point of divergence is older, reject it out of hand without testing which is correct. As long as some nodes are live at any given time then continuity is guaranteed. There is only one way the blockchain can evolve if too-deep reorganizations are barred.

This solution makes proof-of-stake a subjective consensus mechanism. The answer to the question “what is the current state of the blockchain?” depends on whom you ask. It is not objectively verifiable. An attacker can produce an alternative view of history that is just as self-consistent as the correct one. The only way a node can know which view is correct is by selecting a set of peers and taking their word for it.

It may be argued that this hypothetical attack is not relevant if the cost of producing this alternative view of history is too large. While that counterargument might be true, cost is an objective metric and so whether it is true depends on external factors that are not represented on the blockchain. For example, the attacker might lose all of his stake in one view of history, but does not care because he can guarantee through legal or social means that the alternative view will be accepted. Any security analysis or calculation-of-attack cost that focuses on what happens on “the” blockchain, and does not take into account the objective world in which it lives, is fundamentally flawed.

Internal to a proof-of-stake cryptocurrency is that not only the cost is subjective, but so is the reward. Why would an attacker deploy his attack if the end result is not a payout mechanically determined by his ingenuity, but a broadcast from the cryptocurrency’s official team of developers explaining why they have chosen in favor of the other branch? There may be external payouts — for example, from financial options that expect the price to fall or from sheer joy of causing mayhem — but the point is that the low likelihood of internal payouts undermines the argument that the market capitalization of existing proof-of-stake cryptocurrencies constitutes an effective attack bounty.

Money And Objectivity

Money is, in essence, the object with which a debt is settled. Settling debt effectively requires consensus among the parties to the exchange — in particular, the currency and the amount of money. A dispute will lead to the perpetuation of outstanding claims and a refusal to do repeat business on equal or similar terms.

Effective debt settlement does not require the entire world to agree on the specific type of money. Therefore, a subjective money can be useful in pockets of the world economy where there happens to be consensus. However, in order to bridge the gap between any two pockets of micro economies, or more generally between any two persons in the world, global consensus is required. An objective consensus mechanism achieves that; a subjective one does not.

Proof-of-stake cryptocurrencies cannot provide a new foundation for the world’s financial backbone. The world consists of states that do not recognize each other’s courts. If a dispute arises about the correct view of history, the only recourse is war.

Foundations that develop and support proof-of-stake blockchains, as well as freelance developers that work for them — and even influencers that do not write code — expose themselves to legal liability for arbitrarily selecting a disfavorable view of history (to the plaintiff). What happens when a cryptocurrency exchange enables a large withdrawal downstream from a deposit in a proof-of-stake cryptocurrency whose transaction appears in only one branch of two competing views of history? The exchange might select the view that benefits their bottom line, but if the rest of the community — prompted by the PGP signatures and tweets and Medium posts of the foundations, developers and influencers — selects the alternative view, then the exchange is left footing the bill. They have every incentive and fiduciary responsibility to recuperate their losses from the persons responsible for them.

In the end, a court will issue a ruling on which view of history is the right one.

Conclusion

Proponents of proof-of-stake claim that it serves the same purpose as proof-of-work, but without all the energy waste. All too often, their support ignores the trade-offs present in any engineering dilemma. Yes, proof-of-stake does eliminate the energy expenditure, but this elimination sacrifices the objectivity of the resulting consensus mechanism. That is okay for situations where only pockets of local consensus suffice, but this context begs the question: What is the point of eliminating the trusted authority? For a global financial backbone, an objective mechanism is necessary.

The self-referential nature of proof-of-stake makes it inherently subjective: Which view of history is correct depends on whom you ask. The question “is proof-of-stake secure?” attempts to reduce the analysis to an objective measure of cost which does not exist. In the short term, which fork is correct depends on which fork is popular among influential community members. In the long term, courts will assume the power of deciding which fork is correct, and the pockets of local consensus will coincide with the borders that mark the end of one court’s jurisdiction and the beginning of the next.

The energy expended by miners in proof-of-work blockchains is not wasted any more than diesel is wasted fueling cars. Instead, it is exchanged for cryptographically verifiable, unbiasable randomness. We do not know how to generate an objective consensus mechanism without this key ingredient.

This is a guest post by Alan Szepieniec. Opinions expressed are entirely their own and do not necessarily reflect those of BTC Inc. or Bitcoin Magazine.